Regret

It is important to note that the models presented here are not the only accepted ways to make good decisions. In game theory, the key idea is to minimize ``regret.'' This is the feeling you get after making a bad decision and wishing that you could change it after the game is finished. Suppose that after you choose some $ u \in U$, you are told which $ \theta \in \Theta$ was applied by nature. The regret is the amount of cost that you could have saved by picking a different action, given the nature action that was applied.

For each combination of $ u \in U$ and $ \theta \in \Theta$, the regret, $ T$, is defined as

$\displaystyle T(u,\theta) = \max_{u' \in U} \Big\{ L(u,\theta) - L(u',\theta) \Big\} .$ (9.20)

For Formulation 9.3, if $ U$ and $ \Theta$ are finite, then a $ \vert\Theta\vert \times \vert U\vert$ regret matrix can be defined.

Suppose that minimizing regret is the primary concern, as opposed to the actual cost received. Under the nondeterministic model, the action that minimizes the worst-case regret is

$\displaystyle u^* = \operatornamewithlimits{argmin}_{u \in U} \Big\{ \max_{\theta \in \Theta}\Big\{ T(u,\theta)\Big\} \Big\}.$ (9.21)

In the probabilistic model, the action that minimizes the expected regret is

$\displaystyle u^* = \operatornamewithlimits{argmin}_{u \in U} \Big\{ E_\theta \Big[ T(u,\theta) \Big] \Big\}.$ (9.22)

The only difference with respect to (9.14) and (9.15) is that $ L$ has been replaced by $ T$. In Section 9.3.2, regret will be discussed in more detail because it forms the basis of optimality concepts in game theory.

Example 9..10 (Regret Matrix)   The regret matrix for Example 9.8 is
  $ \Theta$
$ U$
$ 2$ 0 $ 2$
0 $ 3$ 0
$ 3$ 0 $ 3$
Using the nondeterministic model, $ u^* = u_1$, which results in a worst-case regret of $ 2$ using (9.21). Under the probabilistic model, let $ P(\theta_1) = P(\theta_2) = P(\theta_3) =
1/3$. In this case, $ u^* = u_1$, which yields the optimal expected regret, calculated as $ 1$ using (9.22).

Steven M LaValle 2012-04-20