Trading off rewards and errors in multi-armed bandits
This work addresses the fundamental exploration-exploitation dilemma for bandit algorithm designers, offering a principled way to balance information gathering and reward accumulation.
The paper studies the tradeoff between accurately estimating arm means and maximizing cumulative reward in multi-armed bandits, presenting an algorithm with regret guarantees that interpolates between these objectives, supported by upper and lower bounds and empirical validation.
In multi-armed bandits, the most-explored arms are the most informative, while reward maximization typically pulls only the best arm. We study the tradeoff between identifying arm means accurately and accumulating reward, and present an algorithm with regret guarantees that interpolates between the two objectives. We provide both upper and lower bounds and validate empirically.