MAB problem with Bounded Estimates

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.

• 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. – jbowman Jan 16 '17 at 21:38
• 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$. – combo Jan 17 '17 at 1:31
• 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? – amipima Jan 17 '17 at 12:24
• That's what I get as well – combo Jan 18 '17 at 17:50

$$\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$$