An improved parametrization and analysis of the EXP3++ algorithm for stochastic and adversarial bandits

TY - GEN

T1 - An improved parametrization and analysis of the EXP3++ algorithm for stochastic and adversarial bandits

AU - Seldin, Yevgeny

AU - Lugosi, Gábor

N1 - Conference code: 30

PY - 2017

Y1 - 2017

N2 - 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 $\Delta e^{\Delta^2}$, where $\Delta$ is the minimal gap of a problem instance. In the adversarial regime regret guarantee remains unchanged.

AB - 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 $\Delta e^{\Delta^2}$, where $\Delta$ is the minimal gap of a problem instance. In the adversarial regime regret guarantee remains unchanged.

M3 - Article in proceedings

T3 - Proceedings of Machine Learning Research

SP - 1743

EP - 1759

BT - Proceedings of Conference on Learning Theory, 7-10 July 2017, Amsterdam, Netherlands

A2 - Kale, Satyen

A2 - Shamir , Ohad

PB - Proceedings of Machine Learning Research

T2 - The 30th Annual Conference on Learning Theory (COLT)

Y2 - 7 July 2017 through 10 July 2017

ER -