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

69 papers16 papers in the last four weeks, down 6% on the four weeks before. 0.1% of all new papers.

  1. The Data Debt of Stockouts: Partial Identification and Minimax-Regret Inventory Control

    Nov 14, 2026Jinbiao Chen, Shuang Jin, Hanzhang QinInventory ControlMinimax Regret

  2. Regret Bounds for Quantum Linear Bandits

    Nov 11, 2026Maoli Liu, Zhuohua Li, John C. S. LuiMulti-Armed BanditsMinimax Regret

  3. Beyond Prediction Residuals: Conformal Regret Calibration for Robust Contextual Linear Optimization

    Nov 9, 2026Lingjie Zhao, Hansheng Jiang, Wei QiPredict-Then-OptimizeConformal Prediction

  4. Tropical Gaussian Anticoncentration: Optimal Instance-Dependent Bounds for Online Learning in Extensive-Form Games

    Nov 9, 2026Ashkan Soleymani, Zhiyuan Fan, Lillian J. Ratliff +2Minimax Regret

  5. Regret without Optimal-Arm Feedback under Reward-Dependent Delays

    Nov 8, 2026Zhong HanMulti-Armed BanditsBandits with Delayed Feedback

  6. The Power of Two Choices in Dynamic Pricing: As Good As Full Feedback, Instance-Wise

    Nov 7, 2026Yan Dai, Tao Lin, Aleksandrs SlivkinsDynamic PricingMinimax Regret

  7. Regret Bounds for Profit Maximization in Bilateral Trade: Learning the Best Posted-Price Mechanism

    Nov 5, 2026Johannes Brüstle, Simone Di Gregorio, Federico Fusco +1Bilateral TradeRegret Minimization

  8. Self-Directed Apple Tasting

    Nov 4, 2026Tanmay Devale, Reed Phillips, Arvind RamaswamiOnline LearningStatistical Learning Theory

  9. Offline Learning of Reserve Prices from Censored Bids

    Nov 4, 2026Lavanya Marla, Yunzong Xu, Boxuan ZhouMinimax RegretLearning with Missing Data

  10. Closing the Log Gap: Minimax-Optimal Regret for Episodic RL

    Oct 29, 2026Guy Zamir, Victor Boone, Matthew Zurek +1Episodic RLReinforcement Learning

  11. An Ω(T3/4)Ω(T^{3/4}) lower bound for projection-free online learning with linear minimization oracles

    Oct 27, 2026Julien Weibel, Pierre Gaillard, Wouter Koolen +1Online Convex OptimizationLMO Methods

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

    Oct 26, 2026Jack J. MayoOnline LPRegret Minimization

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

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

  14. No-Regret Language Generation

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

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

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

  16. Prediction with Expert Advice under Heavy-Tailed Losses

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

  17. Simultaneous Competitive and Regret Guarantees for TCP Acknowledgment

    Oct 9, 2026Tsubasa Harada, Yasushi Kawase, Hanna SumitaOnline Learning with Expert AdviceMinimax Regret

  18. 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

  19. Optimally Pacing Budget Spending and Learning

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

  20. m-Set Adversarial Bandits with Winner Feedback

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

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

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

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

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

  23. The finite-horizon five-expert prediction problem

    Sep 29, 2026Jeff Calder, Nadejda DrenskaMinimax Regret