1
$\begingroup$

I was recently looking at some information on Multi-arm Bandits, and they have the notion of cumulative regret. It is defined as the following:

Consider $K$ arms, each having a normal distribution with mean $\mu_k$ taken from:

$$ \mu_k \sim N(0,1) $$

Then, the reward function $R_t(\mu_k)$ at time $t$ has distribution:

$$ R_t(\mu_k) \sim N(\mu_k, 1) $$

Then, the mean of the best arm is taken to be $\mu^* = \max_k \mu_k$.

From this, assume we have $T$ total pulls of the bandit. Then, the cumulative regret is defined to be:

$$ Regret = T\mu^* - \sum_{t=1}^T R_t $$

I was wondering how this definition of regret differs than ones with an expectation in front of the sum. Does anyone have any specific ideas here?

$\endgroup$
1
  • $\begingroup$ If the cumulative regret is computed after the rewards have been realized, then you can sum the realized rewards instead of the expected ones. $\endgroup$
    – Anna SdTC
    Apr 19 '18 at 1:07
4
$\begingroup$

In comparison to formalised theories of regret, this is a non-standard way to define "regret" (see e.g., Loomes and Sugden 1982). Within formalised regret theory, regret is defined as the foregone utility from the actual action choice in comparison to the case where the random states of the world are treated as known (hindsight knowledge). This is usually measured fully as a random variable, without any expectation, but obviously you can also measure expected regret. Within regret theory the optimisation problem for the decision-maker is usually to minimise regret, which is different to maximising utility.

Suppose we let $R_{a,t}$ denote the return at time $t$ for action $a = 1, ..., K$ and let $\boldsymbol{a} = (a_1, ..., a_T)$ denote the vector of actions that are chosen in the problem. Following your own notation, we will also let $R_t = R_{a_t, t}$ denote the return of the chosen action at time $t$. Then the usual form for the regret would be the random variable:

$$\text{Regret}(\boldsymbol{a}) = \sum_{t=1}^T ( \max_a R_{a,t} - R_t).$$

The regret function is non-negative, since it compares the actual return to the optimal return under hindsight knowledge. Within regret theory it is impossible to have negative regret (the optimum is zero regret). This also means that the expected regret is non-negative.

In the analysis you are showing, the "regret" function is taking the expected value of the first part but not the second. So the "regret" you are using is the difference between the expected gain under hindsight knowledge, compared to the actual (random) gain. One strange aspect of this measure of "regret" is that it can actually be negative (i.e., you can gain more than the expected gain under hindsight knowledge). Hence, this measure of "regret" does not correspond to either the usual definition in regret theory, nor to the expected regret in regret theory. It is a hybrid of these, and it does not obey the property of non-negativity.


Loomes, G. and Sugden, R, (1982) Regret theory: an alternative theory of rational choice under uncertainty. The Economic Journal 92(368), pp. 805–824.

$\endgroup$
3
  • $\begingroup$ Let's say you have two bandits with probabilities of winning 0.5 and 0.4 respectively. In one iteration you draw bandit #2 and win a reward of 1. I would have thought the regret for this step is 0.5 - 1, because the optimal action would have been to select the first bandit. And the expectation of that bandit is 0.5. But since you say negative regret is impossible, I'm having trouble understanding what is the correct definition. $\endgroup$
    – thecity2
    Sep 10 '19 at 17:42
  • $\begingroup$ How can we optimize the regret if we don't know the optimal R_t? $\endgroup$
    – cerebrou
    Feb 6 at 19:30
  • $\begingroup$ Optimising is a matter of finding the optimal value. (And it is too big a subject for me to give an exposition here.) $\endgroup$
    – Ben
    Feb 7 at 0:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.