Multimodal Bandits: Regret Lower Bounds and Optimal Algorithms

William Réveillard, Richard Combes
10/29/2025
stat.MLcs.LGmath.ST

Official code: wilrev/MultimodalBandits (0 stars, last commit 2025-10-30).

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. The code for the proposed algorithms is publicly available at https://github.com/wilrev/MultimodalBandits

View on arXivView PDF

Code Implementations(1)

wilrev/MultimodalBanditsOfficial100%

Code for "Multimodal Bandits: Regret Lower Bounds and Optimal Algorithms".

00PythonOct 28, 202411 months ago

Similar Papers

Algorithm Design and Stronger Guarantees for the Improving Multi-Armed Bandits Problem

85% match2025

Threshold-Based Optimal Arm Selection in Monotonic Bandits: Regret Lower Bounds and Algorithms

84% match2025

A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms

84% match2023

Complexity Analysis of a Countable-armed Bandit Problem

84% match2023

Rising Rested Bandits: Lower Bounds and Efficient Algorithms

83% match2024

Stochastic k-Submodular Bandits with Full Bandit Feedback

83% match2024

Cite this paper

@article{rveillard2025multimodal,
  title  = {Multimodal Bandits: Regret Lower Bounds and Optimal Algorithms},
  author = {William Réveillard and Richard Combes},
  year   = {2025},
  eprint = {2510.25811},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2510.25811v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2510.25811.svg)](https://codeofpaper.com/paper/2510.25811)

Discussion