Regret (decision theory)

From Wikipedia, the free encyclopedia

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.

Contents 1 The minimax regret concept 2 Example: Linear estimation setting 3 References 4 See also 5 External links

[edit] The minimax regret concept

The minimax regret approach is minimizing the worst-case regret. The rational 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's not so pessimistic as the ordinary minimax approach. Similar approaches have been used in variety of areas such as:

• Hypothesis testing
• Prediction
• Universal source coding

[edit] 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 matrix with full column rank m, and w is a zero mean random vector with covariance matrix C_w, which models the noise.

Let

be a linear estimate of x from y, where G is some matrix. The MSE of this estimator is given by

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:

The MSE of is

To find the optimal G(x) we differentiate it with respect to G and equate to 0 getting

G(x) = xx ^* H ^* (C_w + Hxx ^* H ^* ) ^{− 1}

and using the Matrix Inversion Lemma

Substituting this G(x) back into MSE^o

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

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 ^[1]. Similar ideas can be used when x is random with uncertainness in the covariance matrix. For details see ^[2][3].

[edit] References

1. ^ Y. C. Eldar, A. Ben-Tal, and A. Nemirovski, "Linear Minimax regret estimation of deterministic parameters with bounded data uncertainties," IEEE Trans. Signal Process., vol. 52, no. 8, pp. 2177–2188, Aug. 2004.
2. ^ Y. C. Eldar and Neri Merhav, "A Competitive Minimax Approach to Robust Estimation of Random Parameters," IEEE Trans. Signal Processing, vol. 52, pp. 1931-1946, July 2004.
3. ^ Y. C. Eldar and Neri Merhav, "Minimax MSE-Ratio Estimation with Signal Covariance Uncertainties," IEEE Trans. Signal Processing, vol. 53, no. 4, pp. 1335-1347, Apr. 2005.

[edit] See also

• Decision theory
• Loss function

[edit] External links

• TUTORIAL G05: Decision theory
• Decision Theory