An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits
This work provides incremental improvements to bandit algorithms, benefiting researchers and practitioners in online learning and decision-making under uncertainty.
The paper tackles the problem of improving regret bounds in multi-armed bandits by introducing a new gap estimation strategy combined with EXP3++, reducing stochastic regret from (ln t)^3 to (ln t)^2 and eliminating an additive factor dependent on the minimal gap.
We present a new strategy for gap estimation in randomized algorithms for multiarmed bandits and combine it with the EXP3++ algorithm of Seldin and Slivkins (2014). In the stochastic regime the strategy reduces dependence of regret on a time horizon from $(\ln t)^3$ to $(\ln t)^2$ and eliminates an additive factor of order $Δe^{1/Δ^2}$, where $Δ$ is the minimal gap of a problem instance. In the adversarial regime regret guarantee remains unchanged.