Consider a multi-armed bandit(MAB). There are $k$ arms, with reward distributions $R_i$ where $1 \leq i \leq k$. Let $\mu_i$ denote the mean of the $i^{th}$ distribution.

If we run the multi-armed bandit experiment for $T$ rounds, the "pseudo regret" is defined as $$\text{Regret}_T = \sum_{t=1}^T \mu^* - \mu_{it},$$ where $\mu^*$ denotes the highest mean among all the $k$ distributions.

Why is regret defined like this? From what I understand, at time-step $t$, the actual reward received is $r_t \sim R_{it} $ and not $\mu_{it}$ - so shouldn't that be a part of the expression for regret instead?

  • 5
    $\begingroup$ We don’t care what happens for one instance at one time step, we care about what happens in expectation at that time step, hence the mean $\endgroup$ – David Ireland Sep 26 '20 at 17:13
  • 2
    $\begingroup$ Another reason is that, if we were to define regret with respect to the observed rewards, we might get negative regret whenever the agent just happens to be lucky. $\endgroup$ – Robby Goetschalckx Sep 27 '20 at 15:20

In short, you don't regret your bad luck that you could do nothing about, you regret your bad choices that you could have done something about if only you knew.

The point of regret as a metric therefore is to compare your choices with the ideal choices. This makes sense in MABs, because although the primary goal is to gain the most reward, the learning part of the goal is to calculate from experience what are the best choices - usually whilst sacrificing as little as possible in the process.

The formula captures that concept, so does not concern itself with individual rewards in the past that could have been due to good or bad luck. Hence it uses expected (or mean) rewards.


What you define as regret is the case of Stochastic MAB's i.e MAB's with a fixed distribution. First of all the idea of regret in an Online setting is the loss incurred compared to the best agent (NOTE: I have used the term best agent as it can have differeing strategies, resulting in different best agents, in general we deal with a static agent, i.e whose policy/strategy is fixed over the entire horizon).

When we are talking about MAB's we always talk about what happens in 'expectation' rather than what 'actually' happens. This is because we are dealing with incomplete information i.e at each time step we don't actually know what losses we have incurred, and thus the algorithms designed to handle such problems are probabilistic in nature.

Compared to this, there are things like Online Convex Optimization where complete information about the loss function is available (i.e we are given how the loss was calculated) and we actually use the following regret formulation.

$$\sum_{t=1}^T(f_t(w_t) - f_t(u))$$ where $u$ is the minimizer of $\sum_{t=1}^Tf_t(w)$ and $f_t$ are a sequence of loss functions which are fully revealed to a learner.

Now, compared to this in MAB you don't get the loss function revealed to you. You only get to know the reward of the arm you pulled (you don't get to know what was the best arm). Hence, you deal in probabilities i.e you want to maintain a probability distribution over the arms rather than pulling a fixed arm once (NOTE: The losses maybe Stochastic, adversarial etc). This will ensure the arm which is producing the maximum reward gets the maximum probability (if the algorithm works or in technical term 'consistent').

Herein comes the the principal of importance sampling, to have a good estimate of the loss incurred in expectation without knowing the actual loss. In general $f_t$ is assumed to be a linear function (as it can be shown linear functions always have the worst case regret), and hence parametrized by $z_t$ (A vector).

Now consider defining: $$\tilde{z} = [0,0,.....\frac{z(I_t)}{p(I_t)},0,0,...0]$$ where $I_t$ is the arm pulled at time $t$ and $p$ is the probability distribution or strategy to pull your arms. You can check that $\mathbb E[\tilde{z}] = z$ i.e the actual loss vector parametrization in the first place! This $z$ in MABs are nothing but the vector of rewards obtained by pulling an arm i.e. a $k$-D vector of rewards, hence you want to pulll an arm with maximum reward. Thus we see via importance sampling we were able to recover $z$ in 'expectation'.

Thus now regret can be defined as (due to the involvement of probabilistic strategies):

$$R_T=\mathbb E[\sum_{t=1}^T<z_t,w_t> - \min_u \sum_{t=1}^T<z_t,u>]$$ where $w_t$ is nothing but $[0,0,0,...1,0,...0]$ i.e the arm you played after sampling from the probability distribution you use as strategy. Actually one uses importance sampling and pretty involved derivation to get a bound on the aforementioned expectation in the famous EXP3 algorithm. Thus, the bottomline is, due to incomplete information we use a probability distribution to pull the arms and then using an update rule which uses $\tilde{z}$ we can derive bounds for the aforementioned expression.

Now that we have understood the motivation, in Stochastic MAB our goal is to maximize rewards (we have $K$ arms, also I have used standard notations, so it might differ from your notation) i.e

$$\mathbb E[\sum_{t=1}^T X_{I_t}]$$ i.e the arm played at time $t$ which can be written as $$E[\sum_{i=1}^K \mu_iN_i(t)]$$ (NOTE: The earlier expectation was with both your probabilistic strategy of arm plays as well as the probabilistic rewards, as we are dealing with Stochastic MAB's, thus if we eliminate the expectation w.r.t $X_{I_t}$ we get $\mu_{I_t}$ which is written as $\mu_i$ multiplied with the number of times it is played $N_i$ which is a random variable or has a probability associated with it).

Thus this can be further simplified to:

$$\sum_{i=1}^K \mu_iE[N_i(t)]$$.

Now if the highest mean is $\mu^*$ it is clear from the above expression that the expression will be maximized if $\sum_{i=1}^KE[N_{i^*}(t)] = T$ where $i^*$ is the arm corresponding to $\mu^*$ and thus finally we get the regret as: $$R_T = \sum_{t=1}^K (\mu^* - \mu_i)E[N_i(t)]$$.

THe bottomline is that due to incomplete information we use probabilistic strategies, resulting in an expectation of regret, while in Stochastic MAB's the rewards are also probabilistic, but in the regret formulation the expectation w.r.t the rewards can be evaluated to $\mu_i$ (if the distribution is stationary)

A useful reference maybe here (the first part of the video).


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.