Regret Minimization

Follow this topic Ask about this topic

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

114 papers14 papers in the last four weeks, down 7% on the four weeks before. 0.1% of all new papers.

Cost-sensitive retraining via posterior learning debt
Apr 7, 2026Harrison KatzBayesian Decision Theory Regret Minimization
Finance Data Science & Strategy, Airbnb Inc., San Francisco, CA, USA
Adaptive Incentive Design with Regret Minimization
Apr 7, 2026Georgios Vasileiou, Lantian Zhang, Silun ZhangRegret Minimization Mechanism Design
Dept. of Mathematics at the KTH Royal Institute of Technology, Stockholm, 10044, Sweden.
Next-Token Prediction and Regret Minimization
Mar 30, 2026Mehryar Mohri, Clayton Sanford, Jon Schneider +2Regret Minimization Next-Token Prediction
Google Research · Google DeepMind · Microsoft Research
Practical Efficient Global Optimization is No-regret
Mar 26, 2026Jingyi Wang, Haowei Wang, Nai-Yuan Chiang +3Bayesian Optimization Global Optimization
Lawrence Livermore National Laboratory, CA, USA · National University of Singapore, Singapore · National Laboratory of the Rockies, CO, USA
Breaking the $O(\sqrt{T})$ Cumulative Constraint Violation Barrier while Achieving $O(\sqrt{T})$ Static Regret in Constrained Online Convex Optimization
Mar 21, 2026Haricharan Balasundaram, Karthick Krishna Mahendran, Rahul VazeOnline Convex Optimization Constrained Optimization
Bayesian Learning in Episodic Zero-Sum Games
Mar 21, 2026Chang-Wei Yueh, Andy Zhao, Ashutosh Nayyar +1Zero-Sum Games Game-Theoretic RL
Department of Electrical and Computer Engineering at the University of Southern California
On the Peril of (Even a Little) Nonstationarity in Satisficing Regret Minimization
Mar 19, 2026Yixuan Zhang, Ruihao Zhu, Qiaomin XieRegret Minimization Non-Stationary Bandits
Department of Industrial & Systems Engineering, University of Wisconsin-Madison · SC Johnson College of Business, Cornell University
Better Bounds for the Distributed Experts Problem
Mar 10, 2026David P. Woodruff, Samson ZhouRegret Minimization Communication Complexity
Carnegie Mellon University · Texas A&M University
Bilateral Trade Under Heavy-Tailed Valuations: Minimax Regret without a Variance Bound
Mar 6, 2026Hangyi ZhaoMinimax Regret Regret Minimization
A Short Note on a Variant of the Squint Algorithm
Mar 3, 2026Haipeng LuoRegret Minimization
University of Southern California
Revisiting the Bertrand Paradox via Equilibrium Analysis of No-regret Learners
Feb 25, 2026Arnab Maiti, Junyan Liu, Kevin Jamieson +1Swap Regret Game Theory
University of Washington
Prior-Agnostic Incentive-Compatible Exploration
Feb 24, 2026Ramya Ramalingam, Osbert Bastani, Aaron RothSwap Regret Multi-Armed Bandits
Department of Computer and Information Sciences, University of Pennsylvania
Discovering Multiagent Learning Algorithms with Large Language Models
Feb 18, 2026Zun Li, John Schultz, Daniel Hennes +1Counterfactual Regret Minimization Multi-Agent Reinforcement Learning
Google DeepMind
Decision Making under Imperfect Recall: Algorithms and Benchmarks
Feb 16, 2026Emanuel Tewolde, Brian Hu Zhang, Ioannis Anagnostides +2Sequential Decision Making Regret Minimization
Computer Science Dept., Carnegie Mellon University, Pittsburgh, USA · Foundations of Cooperative AI Lab (FOCAL) · Strategy Robot, Inc.; Strategic Machine, Inc.; and Optimized Markets, Inc.
Small Gradient Norm Regret for Online Convex Optimization
Jan 20, 2026Wenzhi Gao, Chang He, Madeleine UdellOnline Convex Optimization Sequential Decision Making
ICME, Stanford University · SIME, Shanghai University of Finance and Economics · Department of Management Science and Engineering, Stanford University
Prior Diffusiveness and Regret in the Linear-Gaussian Bandit
Jan 5, 2026Yifan Zhu, John C. Duchi, Benjamin Van RoyThompson Sampling Multi-Armed Bandits
Department of Electrical Engineering, Stanford University, California, United States.
No-Regret Gaussian Process Optimization of Time-Varying Functions
Nov 29, 2025Eliabelle Mauduit, Eloïse Berthier, Andrea SimonettoMulti-Armed Bandits Bayesian Optimization
Unit´e de Math´ematiques Appliqu´ees ENSTA, Institut Polytechnique de Paris Palaiseau, France · U2IS ENSTA, Institut Polytechnique de Paris Palaiseau, France
Direct Regret Optimization in Bayesian Optimization
Jul 9, 2025Fengxue Zhang, Yuxin ChenBayesian Optimization Learning to Optimize
Department of Computer Science University of Chicago Chicago, IL 60637
Infrequent Resolving Algorithm for Online Linear Programming
Aug 1, 2024Guokai Li, Zizhuo Wang, Jingwei ZhangSequential Decision Making Regret Minimization
School of Data Science, The Chinese University of Hong Kong, Shenzhen, Guangdong, 518172, P.R. China
Online Linear Programming with Batching
Aug 1, 2024Haoran Xu, Peter W. Glynn, Yinyu YeSequential Decision Making Regret Minimization
Department of Management Science and Engineering, Stanford University
Satisficing Regret Minimization in Bandits: Constant Rate and Light-Tailed Distribution
Jun 10, 2024Qing Feng, Tianyi Ma, Ruihao ZhuMulti-Armed Bandits Regret Minimization
School of Operations Research and Information Engineering, Cornell University · SC Johnson College of Business, Cornell University
Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents
Jun 5, 2023Nika Haghtalab, Chara Podimata, Kunhe YangImperfect-Information Games Game Theory
University of California, Berkeley · Massachusetts Institute of Technology
Hierarchical Deep Counterfactual Regret Minimization
May 27, 2023Jiayu Chen, Xudong Wu, Zhekai Wang +1Imperfect-Information Games Hierarchical RL
The University of Hong Kong Hong Kong SAR · Peking University Beijing, China, 100871 · Purdue University2025 West Lafayette, IN 47907
Robust Budget Pacing with a Single Sample
Feb 3, 2023Santiago Balseiro, Rachitesh Kumar, Vahab Mirrokni +2Sample Complexity Online Advertising
DRO, Columbia Business School, New York, NY, USA · Google Research, New York, NY, USA · IEOR, Columbia University, New York, NY, USA

Apr 7, 2026J/K move · Enter open · S save

Cost-sensitive retraining via posterior learning debt

Harrison Katz

Finance Data Science & Strategy, Airbnb Inc., San Francisco, CA, USA

Bayesian Decision Theory Regret Minimization Cost-Sensitive Learning

Open paper AskPDF arXiv

Deployed prediction systems are often retrained on fixed calendars, even when model staleness and retraining burden vary over time. This short communication formulates retraining for Bayesian prediction systems as a cost-sensitive predictive-regret decision. The central monitoring state is posterior learning debt, defined as the Kullback--Leibler divergence from a reference shadow posterior to the deployed frozen posterior. In the decision layer, a retraining cost is compared with the expected one-period predictive regret of waiting. A continuous-severity version retrains when calibrated expected regret exceeds the retraining cost, while the familiar two-state excess-loss rule is a special case. The empirical study is an exact-state proof-of-concept in a synthetic conjugate simulation with warm-started deployed and shadow normal-inverse-gamma posteriors, separate update, monitoring, and evaluation batches, lagged deployment actions, expanded baseline grids, and score-unit sensitivity. Under the primary 75th-percentile score-unit scaling, an age-adjusted debt-threshold policy improves on tuned calendar retraining in all 72 non-stable scenario cells and on tuned CUSUM in 58 of 72 cells, with mean relative objectives 0.677 and 0.975, respectively. Debt-utility and hybrid-utility policies also improve strongly over tuned calendar retraining, but they do not dominate tuned CUSUM. Median and mean score-unit sensitivities show the same main calendar result, while the CUSUM comparison remains policy-dependent. The contribution is a transparent decision layer for deployed Bayesian prediction systems, not a universal replacement for drift detection.