Multimodal Bandits: Regret Lower Bounds and Optimal Algorithms

William Réveillard; Richard Combes

NeurIPS 2025poster0 citations

Multimodal Bandits: Regret Lower Bounds and Optimal Algorithms

Abstract

We consider a stochastic multi-armed bandit problem with i.i.d. rewards where the expected reward function is multimodal with at most $m$ modes. We propose the first known computationally tractable algorithm for computing the solution to the Graves-Lai optimization problem, which in turn enables the implementation of asymptotically optimal algorithms for this bandit problem.

Multi-armed banditsStructured banditsNon-convex optimization

BibTeX

@inproceedings{
reveillard2025multimodal,
title={Multimodal Bandits: Regret Lower Bounds and Optimal Algorithms},
author={William R{\'e}veillard and Richard Combes},
booktitle={The Thirty-ninth Annual Conference on Neural Information Processing Systems},
year={2025},
url={https://openreview.net/forum?id=4wnhbcppot}
}