Minimax Regret

Ask about this topic

Overview

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

CardsList

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

  1. Minimax-Optimal Small-Loss Bounds for Online Linear Optimisation on ℓp\ell_p Balls

    Oct 26, 2026Jack J. MayoRegret MinimizationOnline Convex Optimization

    Kurtos.ai Korteweg-de Vries Institute for Mathematics University of Amsterdam

  2. Optimal Multiclass Online Regret with Arbitrary Label Spaces

    Oct 23, 2026Sajad Ashkezari, Shai Ben-DavidMulticlass ClassificationStatistical Learning Theory

    University of Waterloo

  3. Variance-Aware Non-Stationary Bandits:All-Budget Regret Bounds and Adaptation Costs

    Oct 19, 2026Xiaojin ZhangMulti-Armed BanditsNon-Stationary Bandits

    School of Computer Science and Technology, Huazhong University of Science and Technology, China

  4. No-Regret Language Generation

    Oct 16, 2026Jiaxun Li, Vinod Raman, Ambuj TewariText GenerationMinimax Regret

    Department of Statistics, University of Michigan

  5. Dimension-Optimal Dynamic Regret in Exp-Concave Online Learning

    Oct 14, 2026Yanyi Li, Wendao Wu, Haihan Zhang +6Dynamic Regret MinimizationOnline Convex Optimization

    Peking University

  6. Online Individualized Treatment Selection under Partial Feedback: False Discovery Control and Minimax Optimality

    Oct 12, 2026Runzhe Gu, Zinan Zhao, Wenguang Sun +1FDR ControlMinimax Regret

    Center for Data Science, Zhejiang University · Department of Statistics, University of Michigan

  7. Prediction with Expert Advice under Heavy-Tailed Losses

    Oct 10, 2026Yuki Shibukawa, Shinji ItoMinimax RegretHeavy-Tailed Distributions

    The University of Tokyo and RIKEN

  8. Simultaneous Competitive and Regret Guarantees for TCP Acknowledgment

    Oct 9, 2026Tsubasa Harada, Yasushi Kawase, Hanna SumitaMinimax RegretOnline Learning

    Institute of Science Tokyo · Chuo University

  9. New Lower Bound and Upper Bounds on the Regret for Online Sparse Linear Regression

    Oct 8, 2026Xiaofeng Cao, Junfan Li, Langzhang Liang +2Linear RegressionMinimax Regret

    School of Computer Science and Technology, Tongji University, Shanghai, China · School of Computing and Artificial Intelligence, Shanghai University of Finance and Economics, Shanghai, China · AI3 Institute, Fudan University and Shanghai Innovation Institute +2

  10. A General Ω~(TγT)\widetildeΩ(\sqrt{T γ_T}) Lower Bound for Kernel Bandits

    Oct 8, 2026Chenkai Ma, Jonathan ScarlettMinimax RegretMulti-Armed Bandits

    National University of Singapore

  11. Optimally Pacing Budget Spending and Learning

    Oct 8, 2026Mark Braverman, Jingyi Liu, Jieming Mao +2Online LearningOnline Resource Allocation

    Department of Computer Science, Princeton University · Google Research

  12. m-Set Adversarial Bandits with Winner Feedback

    Oct 7, 2026Nicolò Cesa-Bianchi, Matteo PapiniMulti-Armed BanditsBandit Learning

    Universit`a degli Studi di Milano · Politecnico di Milano

  13. Expected Utility Regret Rule: Minimax and Bayes Optimal Portfolio Choice

    Oct 1, 2026Masahiro KatoPortfolio OptimizationQuantitative Finance

    The University of Tokyo

  14. Minimax Optimal Regret for Causal Logistic Bandits with Counterfactual Fairness

    Oct 1, 2026Junhyuk Huh, Seoungbin Bae, Dabeen LeeMulti-Armed BanditsMinimax Regret

    Faculty of Mathematics, University of Cambridge · Department of Industrial & Systems Engineering, KAIST · Department of Mathematical Sciences, Seoul National University

  15. Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity

    Sep 29, 2026Kaixuan Ji, Qiwei Di, Qingyue Zhao +2Multi-Armed BanditsMinimax Regret

    Department of Computer Science, University of California, Los Angeles, CA 90095, USA

  16. The finite-horizon five-expert prediction problem

    Sep 29, 2026Jeff Calder, Nadejda DrenskaMinimax Regret

    School of Mathematics, University of Minnesota · Department of Mathematics, Louisiana State University

  17. Sharp Critical Minimax Laws and No-Learning Thresholds in Continuous-Time Adaptive Control

    Sep 27, 2026Chen JiaAdaptive ControlStochastic Optimal Control

  18. Optimal Nonparametric Dynamic Pricing with Censored Demand and Adversarial Inventory

    Sep 26, 2026Mengxiao Zhang, Yingfei Wang, Haipeng LuoDynamic PricingMinimax Regret

    University of Iowa · University of Washington · University of Southern California

  19. Agnostic Smoothed Online Regression with Adversarial Responses

    Sep 26, 2026Xuanyu Chen, Yue YuStatistical Learning TheoryMinimax Regret

    Department of Statistics, University of Michigan

  20. Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant

    Sep 23, 2026Yang Cai, Vineet Gupta, Yanchen Jiang +4Minimax RegretRegret Minimization

    Google Research · Yale University · Google DeepMind

  21. The Role of Coordinates in Pareto Regret for Adversarial Multi-Objective Bandits

    Sep 19, 2026Changkun Guan, Mengfan XuMulti-Armed BanditsAdversarial Bandits

    H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology · Mechanical and Industrial Engineering University of Massachusetts Amherst

  22. Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping

    Sep 19, 2026Huikang Liu, Zhengchao Wang, Daniel Kuhn +1Multi-Armed BanditsMinimax Regret

    Shanghai Jiao Tong University · The University of Sydney · École Polytechnique Fédérale de Lausanne +1

  23. Minimax-Optimal Online Contract Design with Unrestricted Bounded Contracts

    Sep 17, 2026Rui Ai, David Simchi-Levi, Han ZhongMechanism DesignMinimax Regret

    Massachusetts Institute of Technology · Shanghai Jiao Tong University

  24. Bandits with Probing: Optimal Coverage and the Role of Feedback

    Sep 14, 2026Yongjie GuanMulti-Armed BanditsMinimax Regret

    Zhejiang University of Technology

  25. Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets

    Sep 14, 2026Tianyuan JinMulti-Armed BanditsMinimax Regret

    Data Science and Analytics Thrust The Hong Kong University of Science and Technology (Guangzhou)

  26. Continuity-Free Near-Minimax Leading-Order Regret for CVaR-UCBVI

    Aug 29, 2026Yuanlong ChenRegret Minimization in RLRisk-Sensitive RL

  27. Sharp Minimax Regret for Infinite-Memory Logistic Prediction

    Aug 27, 2026Vaneet AggarwalLogistic RegressionBayesian Mixture Models

    Purdue University

  28. Minimax Alternating Regret for the Experts Problem and Online Convex Optimization

    Aug 25, 2026Mengxiao ZhangOnline Convex OptimizationMinimax Regret

    University of Iowa

  29. The concentration game: Bayesian updating, regret, and information

    Aug 18, 2026Akshay BalsubramaniMinimax RegretZero-Sum Games

  30. Optimizing Minimax Regret in Uncertain MDPs with Small Sets of Policies

    Aug 3, 2026Sterre Lutz, Daniël Vos, Matthijs T. J. Spaan +1Markov Decision ProcessesBranch and Bound

    Delft University of Technology