2
$\begingroup$

The thing that confuses me is as follows: no matter how many times we explore each arm at the beginning, there is some chance that the arm that performed the best on the sample is actually a suboptimal arm. Then it seems to me that this implies the regret must be linear.

$\endgroup$

1 Answer 1

2
$\begingroup$

There exists multiple Explore-then-commit algorithms so I cannot be very precise. Yet, I think you are missing the fact that Explore-then-commit knows the horizon $T$.

For a given horizon, you explore until you reach "sufficient" guarantee on your best arm. Sufficient means that you trade-off between the cost and the gain of more exploration.

If we call $T_e$ the number explorative rounds and $T_c$ the number of commit rounds. During the explore phase, you will suffer linear regret (say $\alpha T_e$). As you said, it is true that you do mistakes during the commit phase. In expectation, it is the precision $\Delta(T_e)$ that you reached in the explore phase times the number of commit rounds $T_c = T - T_e$. To sum up, we have that $$R_T(\pi) \leq \alpha T_e + \Delta(T_e)(T-T_e) $$

You can look at more precise maths in Tor Lattimore's Theorem 6.1. Yet, it is not "linear" because the precision you reach may be very small. $\Delta(T_e)$ will decrease exponentially with $T_e$ and will compensate the linear $T$ factor only with $T_e = \mathcal{O}(\log(T))$ rounds (for $T$ large enough compared to $\frac{1}{\Delta_i^2}$, you can look in the above reference).

If you don't know $T$, you may want to use the "doubling trick" which starts by guessing $T$ small (e.g $T = CK$ with $C$ a small integer) and restart the algorithm with a double horizon $T:=2T$ when you reach $t=T$. By doing so, you will restart explorative phase periodically. Indeed, you cannot handle potentially infinite horizon with only a finite amount of explorative sample, because you will end up doing $T\Delta(T_e)$ mistakes which is sublinear only if $T_e$ depends on $T$.

$\endgroup$

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.