Assume a two armed case with bernoulli rewards. We know that UCB1 gives a pretty tight bound for multiarmed bandit cases. What if we know the mean of one arm, how can we obtain a better strategy/algorithm than the UCB1?

The way I see it is that since we already know what to expect for one arm, we never explore it. So one would have to find the optimal amount of exploration for the unknown arm before we decide on one arm and exploit that forever after?

  • $\begingroup$ Do you mean that we assume the knowledge of the exact expected outcome for choosing one of the arms? $\endgroup$ Oct 12 '17 at 16:59
  • $\begingroup$ One more question: do you consider finite horizon or infinite one? Do you consider discount factor $\gamma<1$? $\endgroup$ Oct 12 '17 at 17:00
  • $\begingroup$ I don't think it will change your big-O regret, since you'll still do half the exploring you would normally do. $\endgroup$
    – combo
    Nov 2 '17 at 17:16

You may want to look at Bubeck et al..

Long story short, in the two arms case, if you know the value of the two arms but don't know which one is which you can have constant regret (with respect to horizon $T$).

However, if you know only the value of the best arm (but not its identity), it does not help much (logarithmic regret rate). If you only know the difference between the two arms, it does not help much either. (In terms of achievable rate, you may come up with simpler algorithm).

They don't treat your specific case (you know the value of arm 1 but not arm 2). I think it will depend wether arm 1 is the best or not. If arm 1 is the best, then I guess the rate is logarithmic. If arm 2 is the best, then the regret bound is constant.

My educated guess is that only arm 2 is informative. So , if explorative pulls happens to be the best, then they are harmless (even if you don't know they are). You may want to use the index $$i_1 = \mu_1$$ $$i_2 = ucb_2$$

with $\mu_1$ the known value of arm $1$ and $ucb_2$ the classic ucb index of arm 2. If arm 1 is the best, the exploration bonus on arm 2 will cause classical logarithmic rate. However, if arm 2 is the best then your ucb will be at some point with high probability above $\mu_1$ and you will stop pulling arm 1 (and hence doing mistake) forever.


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.