Regret (decision theory)

Regret (decision theory)

Regret (often also called opportunity loss) is defined as the difference between the actual payoff and the payoff that would have been obtained if a different course of action had been chosen. This is also called difference regret. Furthermore, the ratio regret is the ratio between the actual payoff and the best one.

Contents

Minimax regret

The minimax regret approach is to minimize the worst-case regret[1]. The aim of this is to perform as closely as possible to the optimal course. Since the minimax criterion applied here is to the regret (difference or ratio of the payoffs) rather than to the payoff itself, it is not as pessimistic as the ordinary minimax approach. Similar approaches have been used in a variety of areas such as:

One benefit of minimax (as opposed to expected regret) is that it is independent of the probabilities of the various outcomes: thus if regret can be accurately computed, one can reliably use minimax regret. However, probabilities of outcomes are hard to estimate.

This differs from the standard minimax approach in that it uses differences or ratios between outcomes, and thus requires interval or ratio measurements, as well as ordinal measurements (ranking), as in standard minimax.

Maximin 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 shows some possible returns:

Return Interest rates rise Static rates Interest rates fall Worst return
Stocks −4 4 12 −4
Bonds −2 3 8 −2
Money market 3 2 1 1
Best return 3 4 12

The crude maximin 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. This would be −11, which is 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, if interest rates fell, there would be a regret of about −9.78.

The regret table for this example, constructed by subtracting best returns from actual returns, is as follows:

Regret Interest rates rise Static rates Interest rates fall Worst regret
Stocks −7 0 0 −7
Bonds −5 −1 −4 −5
Money market 0 −2 −11 −11

Therefore, using a minimax choice based on regret, the best course would be to invest in bonds, ensuring a regret of 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.

Regret theory

Regret theory is a model of choice under uncertainty. Developed by Graham Loomes and Robert Sugden, it generalizes the minimax regret approach[2]. Choice is modelled as the minimising of a function of the regret vector, defined as the difference between the outcome yielded by a given choice and the best outcome that could have been achieved in that state of nature.

Example: Linear estimation setting

What follows is an illustration of how the concept of regret can be used to design a linear estimator. The regret is the difference between the 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. Also, since the estimator is restricted to be linear, the zero MSE cannot be achieved in the latter case.

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 Cw, which models the noise.

Let

\hat{x}=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 = E\left(||\hat{x}-x||^2\right) = Tr(GC_wG^*) + x^*(I-GH)^*(I-GH)x.

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

\hat{x}^o=G(x)y.

The MSE of \hat{x}^o is

MSE^o=E\left(||\hat{x}^o-x||^2\right) = Tr(G(x)C_wG(x)^*) + x^*(I-G(x)H)^*(I-G(x)H)x.

To find the optimal G(x), it is differentated with respect to G and equated to 0 getting

G(x) = xx * H * (Cw + Hxx * H * ) − 1

and using the Matrix Inversion Lemma

G(x)=\frac{1}{1+x^*H^*C_w^{-1}Hx}xx^*H^*C_w^{-1}.

Substituting this G(x) back into MSEo

MSE^o=\frac{x^*x}{1+x^*H^*C_w^{-1}Hx}.

This is the smallest MSE achievable with a linear estimate that knows x. In practice this MSE cannot be achieved, but it serves as a bound on the optimal MSE. The regret is defined by

R(x,G)=MSE-MSE^o=Tr(GC_wG^*) + x^*(I-GH)^*(I-GH)x-\frac{x^*x}{1+x^*H^*C_w^{-1}Hx}.

The minimax regret approach here is to minimize the worst-case regret as defined above. This will allow a performance 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 of this see Eldar, Tal and Nemirovski (2004)[3]. Similar ideas can be used when x is random with uncertainty in the covariance matrix. For this see Eldar and Merhav (2004), and Eldar and Merhav (2005)[4][5].

References

  1. ^ Savage, L.J. (I95I). The theory of statistical decision. Journal of the American Statistical Association, vol. 46, pp. 55-67.
  2. ^ Loomes, G. and Sugden, R. (1982), ‘Regret theory: An alternative theory of rational choice under uncertainty’, Economic Journal, 92(4), 805–24.
  3. ^ 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.
  4. ^ 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.
  5. ^ 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.

See also

External links


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Regret — wiktionarypar|regret NOTOC Regret or Regrets may refer to: Science * Regret (emotion), an intelligent or emotional dislike for personal past acts and behaviours. * Regret (decision theory), the difference between expected loss and actual loss… …   Wikipedia

  • Decision making — For Decision making in groups, see Group decision making. Sample flowchart representing the decision process to add a new article to Wikipedia. Decision making can be regarded as the mental processes (cognitive process) resulting in the selection …   Wikipedia

  • Group decision making — (also known as collaborative decision making) is a situation faced when individuals are brought together in a group to solve problems. According to the idea of synergy, decisions made collectively tend to be more effective than decisions made by… …   Wikipedia

  • Emotions in Decision Making — One of the most common theories in the field of decision making is the expected utility theory (EU). According to this theory, people usually make their decisions by weighing the severity and likelihood of the possible outcomes of different… …   Wikipedia

  • Swap regret — is a concept from game theory. It is a generalization of regret in a repeated, n decision game.DefinitionA player s swap regret is defined to be the following:: mbox{swap regret}=sum {i=1}^n max {j leq n}frac{1}{T}sum {t=1}^T x^t i cdot (p^t j… …   Wikipedia

  • Loss function — In statistics and decision theory a loss function is a function that maps an event onto a real number intuitively representing some cost associated with the event. Typically it is used for parameter estimation, and the event in question is some… …   Wikipedia

  • Buyer's remorse — is an emotional condition whereby a person feels remorse or regret after a purchase. It is frequently associated with the purchase of higher value items which could be considered bad although it may also stem from a sense of not wishing to be… …   Wikipedia

  • Risk — takers redirects here. For the Canadian television program, see Risk Takers. For other uses, see Risk (disambiguation). Risk is the potential that a chosen action or activity (including the choice of inaction) will lead to a loss (an undesirable… …   Wikipedia

  • Choice — For other uses, see Choice (disambiguation). Choice consists of the mental process of judging the merits of multiple options and selecting one of them. While a choice can be made between imagined options ( what would I do if ...? ), often a… …   Wikipedia

  • Minimax — This article is about the decision theory concept. For other uses, see Minimax (disambiguation). Minimax (sometimes minmax) is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”