I came across the following standard multi-armed bandit problem:

  • There are $k$ arms each generates rewards with unknown means $\mu_i$, $i=1,...,k$.
  • Each observed (estimate) rewards $\hat{\mu}_i$ are within $\epsilon$ of true means, that is, $|\hat{\mu}_i-\mu_i| \leq \epsilon$.
  • Let $\mu^\ast = \max_{i} \mu_i$ be the true mean of the optimal arm.

Problem: what is the minimum upper bound on the regret if we choose the arm with the best estimated reward after first round?

Note: How the regret is defined is unclear from the question. As far as I remember, the source asked the questions for different regret metrics but using regret definition in UCB1 algorithm will suffice for this question.

What I did
I defined the regret as $|\max_i \hat{\mu}_i - \mu^\ast|$. We know that the true mean of the second best arm cannot be larger than that of the optimal arm so $\max_i \hat{\mu}_i$ can be at most $\mu^\ast + \epsilon$. Therefore, it seems to me that the regret is upper bounded by $\epsilon$. Although, I do not know the correct answer, but $\epsilon$ is not it. So, where do I go wrong? I think my regret definition is problematic, but I am not sure.

Thanks for any suggestions/answers in advance.

  • 1
    $\begingroup$ Hint: you've looked at $\max_i \hat{\mu_i}$, but you haven't considered the minimum value that $\widehat{\mu_{\text{best}}}$ could achieve. $\endgroup$
    – jbowman
    Jan 16, 2017 at 21:38
  • 1
    $\begingroup$ Regret should be the difference between actual rewards (not estimates). Try using the jbowman's comment to get a lower bound for $\mu_i$ given that $\hat{\mu}_i \ge \hat{\mu}_j$ for any $j\neq i$, along with regret: $R(i) = \lvert \mu^* - \mu_i\rvert$. $\endgroup$
    – combo
    Jan 17, 2017 at 1:31
  • $\begingroup$ Thanks for the suggestions. The min. value of $\hat{\mu_{best}}$ of arm i (whether it is optimal or not) is $\mu^\ast-\epsilon$. Then assuming that $\mu_i$ is not optimal (i.e. $\mu_i \neq \mu^\ast$) and $\hat{\mu}_j \leq \hat{\mu}_i$ for any $j \neq i$, it is lower bounded by $\mu^\ast - 2 \epsilon$. Then, I think the regret is bounded: $R(i) \leq 2 \epsilon$. Is it correct this time? $\endgroup$
    – amipima
    Jan 17, 2017 at 12:24
  • $\begingroup$ That's what I get as well $\endgroup$
    – combo
    Jan 18, 2017 at 17:50

1 Answer 1


Regret is typically defined as the difference between the reward gotten by choosing the best arm and whichever choice your policy takes. In this case, the best arm has reward
$$\mu^* = \max_i \mu_i$$ and the arm we choose is $$ j \in \arg\max_i \hat{\mu}_i$$

So we are looking for the difference: $$R = \mu^* - \mu_j.$$

We know that the estimates are within epsilon of the true value, and so if $i^*$ is the index of $\mu^*$, $$\mu^* \le \hat{\mu}_{i^*}+\epsilon \le \hat{\mu}_j+\epsilon,$$ where the second inequality is due to the definition of $j$.

We can also use this fact to bound $\mu_j$ below: $$\mu_j \ge \hat{\mu}_j - \epsilon,$$ and so we have $$ R = \mu^* - \mu_j \le (\hat{\mu}_j + \epsilon) - (\hat{\mu}_j - \epsilon) \le 2\epsilon$$


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.