Research map / Bandits and online learning / Multi-armed bandits
Multimodal Bandits: Regret Lower Bounds and Optimal Algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Computes the Graves-Lai constant for multimodal bandits on trees via discretization, dynamic programming and penalized subgradient descent, enabling asymptotically optimal OSSB and showing local search can be arbitrarily suboptimal.
Problem
Stochastic bandits whose mean reward function is at most m-modal on a known graph (tree); the Graves-Lai lower bound requires solving a non-convex semi-infinite program that is hard to compute, so asymptotically optimal algorithms were not implementable.
Approach
Decomposes the non-convex confusing-parameter set into subproblems indexed by (k,k') with fixed mode locations, discretizes the parameter space with a provable approximation error, solves each subproblem by dynamic programming on a rooted tree, and finds the sampling rate vector via penalized projected subgradient descent; also shows local search strategies can be arbitrarily suboptimal.
Key results
- Multimodal OSSB (using the proposed Graves-Lai solver) achieves lower cumulative regret than classical OSSB on both easy (sigma=0.5) and hard (sigma=4) instances up to T=10,000 over 500 trials.
- Runtime of the solver grows approximately quadratically with the number of arms K, consistent with the stated O(K^2 m n t) complexity.
- Local search strategies can be suboptimal by an arbitrarily large factor: sup over instances of C_loc/C is infinite, contradicting the optimality claim of IMED-MB.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use multimodal structure to solve the Graves-Lai problem in OSSB instead of using classical unstructured-bandit sampling rates | OSSB · Synthetic 2-modal binary-tree bandits, σ=0.5 and σ=4 | cumulative regret | Helped |
| Restrict exploration to modes and their neighbors (local search) instead of allowing non-local exploration | Multimodal bandit strategies · Multimodal bandits with |N(μ)| < K | Graves-Lai regret constant | Hurt |
| Use local search on κ-peaked reward functions | Multimodal bandit strategies · κ-peaked multimodal reward functions | ratio of local-search to optimal Graves-Lai regret constant: κ | Mixed |
Surprising findings
- Local search strategies, which are optimal for unimodal bandits, are arbitrarily suboptimal for multimodal bandits, so the published IMED-MB optimality claim does not hold.
- The number of convex components needed to write the confusing set grows exponentially in m, so a naive convex decomposition is intractable.
Limitations
- Theory and algorithm are restricted to tree graphs and Gaussian-type reward families with stated Lipschitz-type assumptions.
- Solver is approximate, with error proportional to 1/n + 1/sqrt(t); the computational complexity lower bound remains open.
- Experiments are small-scale (K=7 main experiment, line graphs for runtime) with OSSB solved via SLSQP rather than the proposed subgradient routine.
Experimental setup
Benchmarks: simulated Gaussian bandit instances (binary tree, K=7, 2 modes)
Metrics: cumulative regret runtime scaling with K
Baselines: Classical OSSB (Lai-Robbins rates) IMED-MB
Builds on: OSSB Graves-Lai lower bound unimodal bandits IMED-MB
Closest papers by meaning
- Fast Asymptotically Optimal Algorithms for Non-Parametric Stochastic Bandits (NeurIPS 2023 · similarity 0.90)
- Lenient Regret for Multi-Armed Bandits (AAAI 2021 · similarity 0.90)
- Greedy Algorithms for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure (NeurIPS 2025 · similarity 0.88)
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.88)
- Forced Exploration in Bandit Problems (AAAI 2024 · similarity 0.88)
- On the Minimax Regret for Contextual Linear Bandits and Multi-Armed Bandits with Expert Advice (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.