Rate-optimal bayesian simple regret in best arm identification
Mathematics of Operations Research, 2024•pubsonline.informs.org
We consider best arm identification in the multiarmed bandit problem. Assuming certain
continuity conditions of the prior, we characterize the rate of the Bayesian simple regret.
Differing from Bayesian regret minimization, the leading term in the Bayesian simple regret
derives from the region in which the gap between optimal and suboptimal arms is smaller
than (log T)/T. We propose a simple and easy-to-compute algorithm with its leading term
matching with the lower bound up to a constant factor; simulation results support our …
continuity conditions of the prior, we characterize the rate of the Bayesian simple regret.
Differing from Bayesian regret minimization, the leading term in the Bayesian simple regret
derives from the region in which the gap between optimal and suboptimal arms is smaller
than (log T)/T. We propose a simple and easy-to-compute algorithm with its leading term
matching with the lower bound up to a constant factor; simulation results support our …
We consider best arm identification in the multiarmed bandit problem. Assuming certain continuity conditions of the prior, we characterize the rate of the Bayesian simple regret. Differing from Bayesian regret minimization, the leading term in the Bayesian simple regret derives from the region in which the gap between optimal and suboptimal arms is smaller than . We propose a simple and easy-to-compute algorithm with its leading term matching with the lower bound up to a constant factor; simulation results support our theoretical findings.
INFORMS