Cover Image

Multimodal Bandits: Regret Lower Bounds and Optimal Algorithms

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Réveillard, William, Combes, Richard
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Statistics Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Near-Optimal Regret for KL-Regularized Multi-Armed Bandits
by: Ji, Kaixuan, et al.
Published: (2026)

Optimal Lower Bounds for Online Multicalibration
by: Collina, Natalie, et al.
Published: (2026)

Optimal Regret of Bernoulli Bandits under Global Differential Privacy
by: Azize, Achraf, et al.
Published: (2025)

Regret Distribution in Stochastic Bandits: Optimal Trade-off between Expectation and Tail Risk
by: Simchi-Levi, David, et al.
Published: (2023)

On Instability of Minimax Optimal Optimism-Based Bandit Algorithms
by: Praharaj, Samya, et al.
Published: (2025)

An extension of McDiarmid's inequality
by: Combes, Richard
Published: (2015)

Statistical Complexity and Optimal Algorithms for Non-linear Ridge Bandits
by: Rajaraman, Nived, et al.
Published: (2023)

Minimax Rate-Optimal Algorithms for High-Dimensional Stochastic Linear Bandits
by: Liu, Jingyu, et al.
Published: (2025)

Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits
by: Zhou, Julien, et al.
Published: (2024)

Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability
by: Chen, Fan, et al.
Published: (2024)

Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs
by: Boudart, Pierre, et al.
Published: (2026)

Optimal Batched Linear Bandits
by: Ren, Xuanfei, et al.
Published: (2024)

The Fragility of Optimized Bandit Algorithms
by: Fan, Lin, et al.
Published: (2021)

Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression
by: Chen, Fan, et al.
Published: (2026)

Minimax Optimality of Score-based Diffusion Models: Beyond the Density Lower Bound Assumptions
by: Zhang, Kaihong, et al.
Published: (2024)

Cover meets Robbins while Betting on Bounded Data: $\ln n$ Regret and Almost Sure $\ln\ln n$ Regret
by: Agrawal, Shubhada, et al.
Published: (2026)

On the Natural Gradient of the Evidence Lower Bound
by: Ay, Nihat, et al.
Published: (2023)

Lower Bounds on the Size of Markov Equivalence Classes
by: Jahn, Erik, et al.
Published: (2025)

SGD with Dependent Data: Optimal Estimation, Regret, and Inference
by: Shen, Yinan, et al.
Published: (2026)

Enjoying Non-linearity in Multinomial Logistic Bandits: A Minimax-Optimal Algorithm
by: Boudart, Pierre, et al.
Published: (2025)

Design Experiments to Compare Multi-armed Bandit Algorithms
by: Meng, Huiling, et al.
Published: (2026)

Asymptotically Optimal Problem-Dependent Bandit Policies for Transfer Learning
by: Prevost, Adrien, et al.
Published: (2025)

Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits
by: Xu, Yunbei, et al.
Published: (2020)

Score Attack: A Lower Bound Technique for Optimal Differentially Private Learning
by: Cai, T. Tony, et al.
Published: (2023)

Improved Algorithm and Bounds for Successive Projection
by: Jin, Jiashun, et al.
Published: (2024)

On Stopping Times of Power-one Sequential Tests: Tight Lower and Upper Bounds
by: Agrawal, Shubhada, et al.
Published: (2025)

A Gapped Scale-Sensitive Dimension and Lower Bounds for Offset Rademacher Complexity
by: Jia, Zeyu, et al.
Published: (2025)

A Simple and Optimal Policy Design with Safety against Heavy-Tailed Risk for Stochastic Bandits
by: Simchi-Levi, David, et al.
Published: (2022)

On the Optimality of Misspecified Spectral Algorithms
by: Zhang, Haobo, et al.
Published: (2023)

General Lower Bounds for Differentially Private Federated Learning with Arbitrary Public-Transcript Interactions
by: Li, Yicheng
Published: (2026)

Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards
by: Panda, Subhodip, et al.
Published: (2026)

Asymptotically and Minimax Optimal Regret Bounds for Multi-Armed Bandits with Abstention
by: Yang, Junwen, et al.
Published: (2024)

Minimax Optimal Simple Regret in Two-Armed Best-Arm Identification
by: Kato, Masahiro
Published: (2024)

Eventually LIL Regret: Almost Sure $\ln\ln T$ Regret for a sub-Gaussian Mixture on Unbounded Data
by: Agrawal, Shubhada, et al.
Published: (2025)

Optimal Bounds for Tyler's M-Estimator for Elliptical Distributions
by: Lau, Lap Chi, et al.
Published: (2025)

Choosing the Better Bandit Algorithm under Data Sharing: When Do A/B Experiments Work?
by: Li, Shuangning, et al.
Published: (2025)

Threshold-Based Optimal Arm Selection in Monotonic Bandits: Regret Lower Bounds and Algorithms
by: Varude, Chanakya, et al.
Published: (2025)

Minimizing Human Intervention in Online Classification
by: Réveillard, William, et al.
Published: (2025)

An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds
by: Chen, Siyu, et al.
Published: (2025)

Precise Asymptotics and Refined Regret of Variance-Aware UCB
by: Fan, Yingying, et al.
Published: (2024)