Overview

Regret minimization measures the cost of learning over time by comparing decisions with a benchmark, often the best fixed action or strategy chosen in hindsight. In bandits, UCB, Thompson sampling, and explore-then-commit balance information gathering with reward; in online optimization, Hedge, follow-the-regularized-leader, and mirror descent adapt to incoming losses. In games, counterfactual regret minimization and swap-regret methods help find equilibria, while dynamic-regret methods track changing comparators. Many classic settings have tight regret bounds, but guarantees still depend sharply on feedback, assumptions about adversaries or nonstationarity, and the chosen objective, such as cumulative versus final-decision quality.

Latest papers

CardsList

125 papers13 papers in the last four weeks, down 13% on the four weeks before. 0.1% of all new papers.

  1. Polylogarithmic Regret via Certainty Equivalence in Degenerate LQR

    Nov 16, 2026Luca Vignola, Melanie Zeilinger, Bruce D. LeeLinear Quadratic RegulatorRegret Minimization

  2. Optimal Regret for Profit Maximization in Bilateral Trade

    Nov 6, 2026Matteo Castiglioni, Anna Lunghi, Alberto MarchesiBilateral TradeRegret Minimization

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

  4. Optimal Learning in Games with Arbitrary Delays: Best-of-Both-Worlds for Self-Play and Adversarial Opponents

    Nov 5, 2026Emmanuel Esposito, Andrew Jacobsen, Hao Qiu +2Zero-Sum GamesRegret Minimization

  5. Optimistic Hedge in General-Sum Games: Fundamental Limits and Regret Bounds via Temporal Approximation

    Nov 4, 2026Yuval Dagan, Nadav Eisen, Liad Erez +1General-Sum GamesRegret Minimization

  6. Logarithmic Regret for Alternating Mirror Descent

    Nov 3, 2026Tianlong Nan, Christian KroerRegret MinimizationOnline Mirror Descent

  7. On the Convergence of Alternating Regret Matching Algorithms

    Nov 2, 2026Anh Duc Nguyen, Ioannis Anagnostides, Brian Hu Zhang +1Regret MinimizationNash Equilibrium Computation

  8. Tight Stochastic Sequential Covers for General VC Classes with Unknown i.i.d. Features

    Oct 31, 2026Changlong Wu, Wojciech SzpankowskiStatistical Learning TheoryRegret Minimization

  9. Omniprediction for All Mixable Proper Losses and Beyond

    Oct 29, 2026Junyan Liu, Haipeng Luo, Lillian J. RatliffRegret Minimization

  10. Near-Optimal First-Order Regret for Bandits with Feedback Graphs

    Oct 29, 2026Mengxiao Zhang, Yuheng Zhang, Haipeng Luo +1Graph BanditsRegret Minimization

  11. Satisficing Regret Minimization in Bandits with Knapsacks

    Oct 29, 2026Qing Feng, Tianyi Ma, Ruihao ZhuRegret MinimizationMulti-Armed Bandits

  12. Impossibility of No-Regret in Multi-Agent Bidding

    Oct 27, 2026Zongjun Yang, Rachitesh Kumar, Christian KroerRegret MinimizationAutomated Bidding

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

    Oct 26, 2026Jack J. MayoOnline LPRegret Minimization

  14. Near-Optimal Regret Bounds for UCB-Style Gaussian Process Bandits via Data Thinning

    Oct 20, 2026Shion Takeno, Shogo Iwazaki, Ichiro TakeuchiGaussian Process BanditsRegret Minimization

  15. No-Regret Revenue Maximization in Sequential Market Making Under Inventory Constraints

    Oct 17, 2026Davide Maran, Marcello Restelli, Francesco Emanuele StradiMarket MakingAlgorithmic Trading

  16. IR-PRM+ with Previous-Utility Prediction: Constant Regret and Best-Iterate Convergence

    Oct 13, 2026Michael Sullins, Ian A. KashCounterfactual Regret MinimizationRegret Minimization

  17. Exploration strategies for Gaussian process bandit optimization with inference regret guarantees

    Oct 12, 2026Hwanwoo Kim, Jungwoo Hong, Kyungjae LeeGaussian Process BanditsBayesian Optimization

  18. Counterfactual Regret for Reflective Agents with Lean-Verified Guarantees

    Oct 10, 2026Zhongnian Li, Shi Xu, Mengting Xu +2Self-Reflection in Language Model AgentsCounterfactual Regret Minimization

  19. Expected Sample Complexity in Multi-Armed Bandits

    Oct 7, 2026Nadav Sukenik, Nadav MerlisMulti-Armed BanditsRegret Minimization

  20. Instance-Dependent Regret for CMDPs with Step-Wise Constraints

    Oct 1, 2026Qian Zuo, Francesco Emanuele Stradi, Leyang Xue +1Constrained RLSafe RL

  21. The Curvature of Regret in Contextual Linear Optimization

    Oct 1, 2026Konstantinos Ziliaskopoulos, Alexander Vinel, Alice E. SmithDecision-Focused LearningRegret Minimization

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

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

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

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

  24. Cost-Sensitive Online Window Size Selection for Portfolio Management

    Sep 24, 2026Yi-Chen Liu, Chung-Han HsiehCost-Sensitive LearningRegret Minimization

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