Definitions
Nearby Words

# Regret (decision theory)

Regret (often also called opportunity loss) is defined as the difference between one's actual payoff and the payoff in a better position that he could have got if a different course of action had been chosen. This is also called difference regret. One can define the ratio regret, namely the ratio between the actual payoff and the best one.

## The minimax regret concept

The minimax regret approach is minimizing the worst-case regret. The rationale behind this is performing uniformly close to the optimal course. Since the minimax criterion applied here to the regret (difference or ratio of the payoffs) rather that to the payoff itself, it is not as pessimistic as the ordinary minimax approach. Similar approaches have been used in variety of areas such as:

### Minimax example

Suppose an investor has to choose between investing in stocks, bonds or the money market, and the total return depends on what happens to interest rates. The following table show some possible returns:

 Return Interest rates rise Static rates Interest rates fall Worst return -4 4 12 -4 -2 3 8 -2 3 2 1 1 Best return 3 4 12

The crude minimax choice based on returns would be to invest in the money market, ensuring a return of at least 1. However, if interest rates fell then the regret associated with this choice would be large: -11 as the difference between the 1 received and the 12 which could have been received if the outturn had been known in advance. A mixed portfolio of about 11.1% in stocks and 88.9% in the money market would have ensured a return of at least 2.22, but a regret if interest rates fell of about -9.78.

The regret table for this example, constructed by subtracting actual returns from best returns, looks like

 Regret Interest rates rise Static rates Interest rates fall Worst regret -7 0 0 -7 -5 -1 -4 -5 0 -2 -11 -11

So using a minimax choice based on regret would be to invest in bonds, ensuring a regret no worse than -5. A mixed investment portfolio would do even better: 61.1% invested in stocks and 38.9% in the money market would produce a regret no worse than about -4.28.

## Example: Linear estimation setting

Here we illustrate how the concept of regret can be used to design a linear estimator. Now the regret is the difference between mean-squared error (MSE) of the linear estimator that doesn't know the parameter $x$ and the mean-squared error (MSE) of the linear estimator that knows $x$. Since the estimator is restricted to be linear the zero MSE cannot be achieved in the latter case also.

Consider the problem of estimating the unknown deterministic parameter vector $x$ from the noisy measurements in the linear model

$y=Hx+w$
where $H$ is a known $n times m$ matrix with full column rank $m$, and $w$ is a zero mean random vector with covariance matrix $C_w$, which models the noise.

Let

$hat\left\{x\right\}=Gy$
be a linear estimate of $x$ from $y$, where $G$ is some $m times n$ matrix. The MSE of this estimator is given by
$MSE = Eleft\left(||hat\left\{x\right\}-x||^2right\right) = Tr\left(GC_wG^*\right) + x^*\left(I-GH\right)^*\left(I-GH\right)x.$

Since the MSE depends explicitly on $x$ it cannot be minimized directly. Instead we can use the concept of regret in order to define a linear estimator with good MSE performance. To define the regret in this setup consider a linear estimator that knows the value of the parameter $x$, i.e. the matrix $G$ can explicitly depend on $x$:

$hat\left\{x\right\}^o=G\left(x\right)y.$
The MSE of $hat\left\{x\right\}^o$ is
$MSE^o=Eleft\left(||hat\left\{x\right\}^o-x||^2right\right) = Tr\left(G\left(x\right)C_wG\left(x\right)^*\right) + x^*\left(I-G\left(x\right)H\right)^*\left(I-G\left(x\right)H\right)x.$
To find the optimal $G\left(x\right)$ we differentiate it with respect to $G$ and equate to 0 getting
$G\left(x\right)=xx^*H^*\left(C_w+Hxx^*H^*\right)^\left\{-1\right\}$
and using the Matrix Inversion Lemma
$G\left(x\right)=frac\left\{1\right\}\left\{1+x^*H^*C_w^\left\{-1\right\}Hx\right\}xx^*H^*C_w^\left\{-1\right\}.$
Substituting this $G\left(x\right)$ back into $MSE^o$
$MSE^o=frac\left\{x^*x\right\}\left\{1+x^*H^*C_w^\left\{-1\right\}Hx\right\}.$
This is the smallest MSE achievable with a linear estimate that knows $x$. Of course, in practice this MSE cannot be achieved but it serves as a bound on the optimal MSE. Now the regret is defined by
$R\left(x,G\right)=MSE-MSE^o=Tr\left(GC_wG^*\right) + x^*\left(I-GH\right)^*\left(I-GH\right)x-frac\left\{x^*x\right\}\left\{1+x^*H^*C_w^\left\{-1\right\}Hx\right\}.$
The minimax regret approach here is to minimize the worst-case regret as defined above. This will allow us to perform as close as possible to the best achievable performance in the worst case of the parameter $x$. Although this problem appears difficult, it can be formulated as a convex optimization problem and solved definitely. For details see . Similar ideas can be used when $x$ is random with uncertainness in the covariance matrix. For details see .