Research map / Bandits and online learning / Multi-armed bandits

Achieving adaptivity and optimality for multi-armed bandits using Exponential-Kullback Leibler Maillard Sampling

NeurIPS 2026 · Bandits and online learning › Multi-armed bandits · approach: Optimal stochastic bandit algorithms · 0 citations (OpenAlex)

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.

Proposes Exp-KL-MS, a Maillard-sampling-style randomized bandit algorithm for one-parameter exponential families with inverse temperature L(k)=k-1, claiming simultaneous asymptotic optimality, sqrt(ln K) minimax ratio, Sub-UCB, and adaptive variance-ratio regret bounds.

Problem

Multi-armed bandits with rewards from one-parameter exponential family (OPED) distributions lack an algorithm that simultaneously achieves asymptotic optimality, minimax optimality, Sub-UCB, and variance-adaptive regret bounds.

Approach

Extends Maillard Sampling/KL-MS to OPED rewards using KL divergence between MLE distributions with inverse temperature L(k)=k-1 (borrowed from ExpTS-style analysis), which avoids the divergence in the asymptotic analysis that arises with L(k)=k and yields simultaneous optimality guarantees.

Key results

• Exp-KL-MS regret bound yields minimax ratio of sqrt(ln K) relative to sqrt(KT) for bounded-variance OPED rewards.
• Asymptotic regret limsup Regret(T)/ln(T) equals sum over suboptimal arms of Delta_a / KL(mu_a, mu_max), matching the Lai-Robbins lower bound.
• Adaptive variance bound of order sqrt(V(mu_max) K T ln K) + K ln T under Lipschitz variance function assumption.

Surprising findings

• Using L(k)=k (plain KL-MS) fails to yield a proof of asymptotic optimality for OPED rewards in the analysis, with the authors conjecturing a fundamental limitation.

Limitations

• Assumes identity sufficient statistic (canonical OPED form); general sufficient statistics such as Beta left to future work.
• Minimax ratio of sqrt(ln K) is not removed; whether constant minimax ratio plus Sub-UCB can coexist is left open.
• Adaptive variance result requires a Lipschitz variance function assumption and bounded mean parameter range.

Experimental setup

Metrics: pseudo-regret regret upper bound order

Baselines: TS ExpTS ExpTS+ epsilon-Exploring TS kl-UCB kl-UCB++ MOSS ADA-UCB KL-MS MS+

Builds on: KL-MS MS ExpTS KL-UCB MED

Closest papers by meaning

• Kullback-Leibler Maillard Sampling for Multi-armed Bandits with Bounded Rewards (NeurIPS 2023 · similarity 0.95)
• Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits (NeurIPS 2022 · similarity 0.92)
• On Approximate Thompson Sampling with Langevin Algorithms (ICML 2020 · similarity 0.89)
• Finite-Time Analysis of Round-Robin Kullback-Leibler Upper Confidence Bounds for Optimal Adaptive Allocation with Multiple Plays and Markovian Rewards (NeurIPS 2020 · similarity 0.89)
• Adaptive Regret for Bandits Made Possible: Two Queries Suffice (ICLR 2024 · similarity 0.88)
• On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization (NeurIPS 2026 · similarity 0.88)