I am following the book Bandit Algorithms. In page 48, they introduces regret after $n$ rounds as

$$ \mathbf{R} = n\mu^\star - \mathbb{E}\Bigg[\sum_{t=1}^n \mathbf{X}_t\Bigg] \tag{1} $$

In page 55, they also define pseudo-regret as

$$ \bar{\mathbf{R}} = n\mu^\star - \sum_{t=1}^n \mu_{A_t} \tag{2} $$

In the paper Regret Analysis of Stochastic and ..., authors introduces pseudo-regret as

$$ \bar{\mathbf{R}} = n\mu^\star - \mathbb{E}\Bigg[\sum_{t=1}^n \mu_{A_t}\Bigg] \tag{3} $$

Can anyone tell me the differences in the three definitions ?

In the first definition, due to the linearity of the expectation, we can write it exactly like (2). Hence (1) and (2) should be referring to the same quantity ?

Since $\mu_{A_t}$ is not a random variable, $\mathbb{E}[\mu_{A_t}] = \mu_{A_t}$, and due to the linearity of expectation, (2) and (3) should be referring to the same quantity.

Anyone can help me out with these definitions ?


1 Answer 1


I do not think that $\mathbb{E}(X_t) = \mu_{A_t}$. Because $\mu_{A_t}$ is a random variable which depends on which arm you are pulling at time $t$. For example, let's consider a two-arm bandit. The policy is to pull the arms randomly with equal probability. And each arm has its own reward distribution $\mu_1$ and $\mu_2$. In pseudo-regret, you just ignore the randomness of reward distribution (these are very weak words and just for understanding) and you assume that you will get a fixed reward ($\mu_1$ and $\mu_2$) when you pull each of the arms. The only randomness is from your policy i.e. which arm you are pulling at each time step $t$. I think it answers both of your questions.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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