Regret Bound for Multi-Armed Bandits with Discounting: A Robust Stochastic Control Approach

We investigate the exact regret bound for stochastic multi-armed bandit problems with discounting, by formulating the regret bound as the value of a robust stochastic control problem. We first show that the regret bound coincides with the value associated with the Bayesian optimization problem under the worst prior. However, a solution to this Bayesian optimization may not be an optimal strategy for the robust control problem. To resolve this dilemma, we introduce an entropy regularization term into the cost function. In this way, we prove the existence of a saddle point for the entropy-regularized robust control. Moreover, the unique optimal strategy for the Bayesian optimization under the worst prior is also an (almost) optimal strategy for the original robust stochastic control problem.