Why does greedy algorithm for Multi-arm bandit incur linear regret?

Question

I am watching David silver's course on Exploration and Exploitation, in the lecture he explains the greedy algorithm for multi - arm bandit in the following manner:

1. Estimate $Q_t(a)$ for each arm by Monte-Carlo evaluation
2. Pick the action $A_t = argmax_{a \in A}Q_t(a)$. Pick this action forever.

The linear regret is attained when the action that greedy chooses is a suboptimal one and every time this action is chosen, it incurs the same amount of regret from not choosing the optimal one.

Given sufficient number of times of Monte-Carlo evaluation for each arm, shouldn't the $Q_t(a)$ converge to their true value and thereby allowing greedy to pick the optimal action ?

Answer 1

Greedy action selection can get stuck in an non-optimal choice:

• The initial value estimate of one non-optimal action is relatively high

• The initial value estimate of the optimal action is lower than the true value of that non-optimal action

Over time, the estimate of whichever action is taken does get refined and become more accurate. However, with greedy actions the estimates for actions with lower than the maximum estimate do not get refined at all. An action needs to spend some time steps having the maximum action value estimate in order to get selected.

Through chance (sample bias), the initial try and evaluation of the optimal action may be lower than the true value of some other non-optimal action. If that same non-optimal action has a higher initial evaluation (again through chance), then the optimal action will never be tried again when using greedy action selection. It won't matter that the value estimate for the non-optimal action becomes more accurate, as it will remain higher than the inaccurate estimate of the optimal action.

Answer 2

I have explained in this thread why Explore-then-commit (more or less what you are describing) do have a sublinear regret rate when you know the horizon (that is, the total amount of rounds the game will last). Indeed, in that case, you can size the exploration phase so that it is relatively small compared to the total number of rounds (less than a sublinear term), and still have sufficient precision so that you incur a small error on the exploitation phase (again, something smaller than a sublinear term). I think this explanation follows your intuition.

However, notice a few things:

• If you size your exploration phase for a given horizon guess $T_g$ and if your game is much longer (horizon $T>> T_g$), then you will suffer linear regret because no fixed-size exploration can lead to infinite precision. Indeed, your regret will be something like $T \Delta$ with $\Delta$ the finite precision you reached initially. I think this is what David Silver meant. Again, $T \Delta$ can be sublinear only if $\Delta$ depends on the horizon $T$. Yet, it depends on the exploration size $T_e$ so the only way to make it work is by tuning $T_e$ with $T$.
• If you size your exploration phase for a much longer horizon than the actual real number of rounds, then you may never end your exploration (which leads obviously to linear regret).
• Yet, you can still use explore-then-commit with a doubling trick. That is, you size the exploration phase for a (not that) well-chosen $T$ and when $t=T$ (because you were wrong) you restart your exploration with $T:=2T$. However, even though the regret of this type of policies may be sublinear, it is still not as good as UCB or Thompson Sampling (I refer to Lattimore's book: chapter 6 to 8.).