In this paper, there are two formulations of regret at time $n$:

  1. $R_n=n\mu^*-\sum_{t=1}^{n}E[\mu_{I_{t}}]$

  2. $R_n=\sum_{i=1}^{K}\Delta_iE[T_i(n+1)]$


$\mu_i$ is an expected value of some unknown distribution $v_i$ of arm $i$ (distribution that generates rewards)


$I_t\in\{{1, ..., K}\}$ is the action taken at time $t$


$T_i(t)=\sum_{l=1}^{t-1}1_{\{I_l=i\}}$ is the number of times arm $i$ was pulled strictly before time $t\geq2$

Can someone show why are they equivalent?


1 Answer 1


enter image description here

Source: Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems Sebastien Bubeck and Nicolo Cesa-Bianchi2

I feel this should be self explanatory. Do let me know it is not !


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.