Minimax Regret

Follow this topic Ask about this topic

Minimax regret asks how well a decision-maker can perform, in the worst case, compared with a benchmark that knew the outcomes or model in advance. It studies settings from bandits and reinforcement learning to online prediction, pricing, and resource allocation, using methods such as UCB, elimination, mirror descent, and robust optimization. Researchers pair algorithmic regret guarantees with information-theoretic lower bounds to determine which rates are achievable. A central tension is that feedback, dimension, heavy-tailed noise, and constraints such as fairness or safety can sharply change those rates, while algorithms must often adapt without knowing which conditions apply.

Latest papers

55 papers15 papers in the last four weeks, up 67% on the four weeks before. 0.1% of all new papers.

Parameter-Free Dynamic Regret under Heavy-Tailed Noise
Jul 29, 2026Vaneet AggarwalOnline Convex Optimization Dynamic Regret Minimization
Purdue University
Experimentation and Commitment under Reward Shifts
Jul 26, 2026Puping Jiang, Wei Tang, Renyu +1Multi-Armed Bandits Exploration-Exploitation Tradeoff
Philip
The Price of Hidden Curvature: An $\widetildeΩ (d^{5/4} \sqrt{T})$ Lower Bound for Bandit Convex Optimization
Jul 21, 2026Nived RajaramanOnline Convex Optimization Minimax Regret
Microsoft Research
Min-Max Regret Task Allocation and Planning of Heterogeneous Multi-Robot System in Partially Known Environments
Jul 15, 2026Xinkai Liang, Huixuan Chan, Ying Liu +2Minimax Regret Multi-Robot Exploration
Price of Fairness in Bandits: A Tight Minimax Characterization
Jul 15, 2026Dhruv Sarkar, Soumyadeep Dutta, Sayak Ray ChowdhuryMulti-Armed Bandits Minimax Regret
1Indian Institute of Technology Kharagpur · 2Mohamed bin Zayed University of Artificial Intelligence · 3Indian Institute of Technology Kanpur
Bandit PCA with Minimax Optimal Regret
Jul 12, 2026Moïse Blanchard, Dmitrii Ostrovskii, Aadirupa SahaPrincipal Component Analysis Minimax Regret
Georgia Tech · University of Illinois, Chicago
Beyond Bayesian Nash: Learning Minimax-Regret Equilibria for Adversarial Team Games under Asymmetric Information
Jul 10, 2026Naman Aggarwal, Jonathan P. HowImperfect-Information Games Game Theory
Aerospace Control Laboratory Laboratory of Information and Decision Systems Massachusetts Institute of Technology
Bellman-sufficient Information Complexity
Jun 9, 2026Yunbei XuMulti-Armed Bandits Minimax Regret
National University of Singapore
Two-Action Apple Tasting with Switching Costs
Jun 2, 2026Tommaso Cesari, Roberto ColomboniMulti-Armed Bandits Minimax Regret
School of Electrical Engineering and Computer Science University of Ottawa Ottawa, Canada · School of Mathematics University of Bristol Bristol, United Kingdom
Minimax-Optimal Policy Regret in Partially Observable Markov Games
Jun 1, 2026Raman AroraRegret Minimization in RL Imperfect-Information Games
Department of Computer Science, Johns Hopkins University, Baltimore, MD, USA.
Batched Stochastic Linear Bandits with 1-Bit Communication Constraints
May 29, 2026Ivan Lau, Daniel McMorrow, Kevin Jamieson +1Multi-Armed Bandits Batched Bandits
National University of Singapore · University of Washington
Prudent-Banker: No Extra Fees for Baseline Safety in Adversarial Bandits With and Without Delays
May 22, 2026Ting Hu, Luanda Cai, Emmanouil-Vasileios Vlatakis-GkaragkounisMulti-Armed Bandits Minimax Regret
Department of Finance University of Wisconsin–Madison · Department of Computer Sciences University of Wisconsin–Madison
Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs
May 19, 2026Pierre Boudart, Pierre Gaillard, Alessandro RudiRegret Minimization in RL Markov Decision Processes
SIERRA · INRIA, École Normale Supérieure CNRS, PSL Research University Paris, France · Thoth +3
Tighter Regret Bounds for Contextual Action-Set Reinforcement Learning
May 15, 2026Zijun Chen, Zihan ZhangRegret Minimization in RL Reinforcement Learning
Department of Computer Science and Engineering Hong Kong University of Science and Technology
Profit Maximization in Bilateral Trade against a Smooth Adversary
May 12, 2026Simone Di Gregorio, Paul Dütting, Federico Fusco +1Mechanism Design Minimax Regret
Department of Computer, Control and Management Engineering Sapienza University of Rome · Google Research · Department of Computer Science Aarhus University
Optimal Regret for Single Index Bandits
May 10, 2026Devdan Dey, Sujoy Bhore, Avishek GhoshMulti-Armed Bandits Single-Index Models
Department of Computer Science and Engineering, Indian Institute of Technology Bombay.
Prior-Agnostic Robust Forecast Aggregation
Apr 27, 2026Zhi Chen, Cheng Peng, Wei TangMinimax Regret Probabilistic Forecasting
Chinese University of Hong Kong
Water-Filling is Universally Minimax Optimal
Mar 27, 2026Siddhartha Banerjee, Ramiro N. Deo-Campo Vuong, Robert KleinbergOnline Resource Allocation Multi-Agent Resource Allocation
Cornell University.
Globalized Adversarial Regret Optimization: Robust Decisions with Uncalibrated Predictions
Mar 26, 2026Jannis Kurtz, Bart P. G. van ParysRobust Optimization Predict-Then-Optimize
University of Amsterdam · CWI Amsterdam
Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
Mar 25, 2026Guy Zamir, Matthew Zurek, Yudong ChenRegret Minimization in RL Average-Reward RL
Department of Computer Sciences, University of Wisconsin–Madison
Few Batches or Little Memory, But Not Both: Simultaneous Space and Adaptivity Constraints in Stochastic Bandits
Mar 14, 2026Ruiyuan Huang, Zicheng Lyu, Xiaoyi Zhu +1Batched Bandits Multi-Armed Bandits
School of Data Science, Fudan University · School of Data Science, Fudan University Shanghai Innovation Institute
Bilateral Trade Under Heavy-Tailed Valuations: Minimax Regret without a Variance Bound
Mar 6, 2026Hangyi ZhaoMinimax Regret Regret Minimization
Learning Optimal Search Strategies
Mar 2, 2026Stefan Ankirchner, Maximilian Philipp ThielOptimal Stopping Minimax Regret
Institute for Mathematics, University of Jena, Inselplatz 5, 07743 Jena, Germany.
Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hypersphere
Feb 20, 2026Shogo IwazakiGaussian Process Bandits Minimax Regret
LY Corporation, Tokyo, Japan
What is the Value of Censored Data? An Exact Analysis for the Data-driven Newsvendor
Feb 18, 2026Rachitesh Kumar, Omar MouchtakiInventory Control Minimax Regret
Carnegie Mellon University · New York University

Jul 29, 2026J/K move · Enter open · S save

Parameter-Free Dynamic Regret under Heavy-Tailed Noise

Vaneet Aggarwal

Purdue University

Online Convex Optimization Dynamic Regret Minimization Minimax Regret Heavy-Tailed Noise Adaptive Gradient Methods Heavy-Tailed Stochastic Optimization

Open paper AskPDF arXiv

We study online convex optimization with one unbiased stochastic subgradient per round and noise having a finite

p

-th central moment, where

p\in(1,2]

is unknown. For a bounded convex domain of diameter

D

, subgradients bounded by

G

, noise scale

σ

, and comparator path length

P_T

, let

Λ_T=1+P_T/D

. A single algorithm, using none of

G,σ,p,P_T

, attains expected dynamic regret

O_p\left(\min\{GD\sqrt{TΛ_T}+σDT^{1/p}Λ_T^{(p-1)/p},\,GDT\}\right)

against every fixed comparator sequence. Restarted AdaGrad experts produce the noise-path exponent

(p-1)/p

, and a prior favoring longer restart intervals removes horizon-dependent logarithmic overhead. We give an explicit bound uniform in

p

; its logarithm-free form has noise coefficient

O(1+\log(p/(p-1)))

, while the static-regret constant is universal. The analysis requires only marginal noise moments and permits dependent errors. Complete pathwise proofs retain both the expert-loss range and the gradient energies preceding comparator movement. Matching lower bounds hold on every bounded convex domain of positive diameter, under the same gradient-only information model. Together with a path-budget-tuned upper bound, they characterize the minimax rate with universal constants, including its linear-regret saturation.