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.

Satisficing Regret Minimization in Bandits with Knapsacks
Oct 29, 2026Qing Feng, Tianyi Ma, Ruihao ZhuRegret Minimization Multi-Armed Bandits
School of Operations Research and Information Engineering, Cornell University · SC Johnson College of Business, Cornell University
Impossibility of No-Regret in Multi-Agent Bidding
Oct 27, 2026Zongjun Yang, Rachitesh Kumar, Christian KroerRegret Minimization Automated Bidding
Columbia University. · Carnegie Mellon University.
Minimax-Optimal Small-Loss Bounds for Online Linear Optimisation on $\ell_p$ Balls
Oct 26, 2026Jack J. MayoRegret Minimization Online Convex Optimization
Kurtos.ai Korteweg-de Vries Institute for Mathematics University of Amsterdam
Near-Optimal Regret Bounds for UCB-Style Gaussian Process Bandits via Data Thinning
Oct 20, 2026Shion Takeno, Shogo Iwazaki, Ichiro TakeuchiGaussian Process Bandits Regret Minimization
Nagoya University · MI-6 Ltd. · RIKEN AIP
No-Regret Revenue Maximization in Sequential Market Making Under Inventory Constraints
Oct 17, 2026Davide Maran, Marcello Restelli, Francesco Emanuele StradiAlgorithmic Trading Regret Minimization
Politecnico di Milano
Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization
Oct 14, 2026Haowei Wang, Yilin ZhengThompson Sampling Global Optimization
National University of Singapore Singapore
Finite-sample certification of coverage regret for budgeted document selection under adaptive stratified auditing
Oct 13, 2026Nora SerdyukovaRegret Minimization Selective Inference
Department of Statistics, University of Concepcion, Chile
Learning in Strategic Queuing with Geometric Recharge: From Bandits to Systems
Oct 13, 2026Cristian Palma Foster, Eva TardosQueueing Theory Regret Minimization
Cornell University
IR-PRM+ with Previous-Utility Prediction: Constant Regret and Best-Iterate Convergence
Oct 13, 2026Michael Sullins, Ian A. KashCounterfactual Regret Minimization Regret Minimization
University of Illinois Chicago, Chicago, Illinois, USA
Exploration strategies for Gaussian process bandit optimization with inference regret guarantees
Oct 12, 2026Hwanwoo Kim, Jungwoo Hong, Kyungjae LeeGaussian Process Bandits Bayesian Optimization
Department of Mathematical Sciences, University of Texas at Dallas · Department of Statistics, Korea University
Counterfactual Regret for Reflective Agents with Lean-Verified Guarantees
Oct 10, 2026Zhongnian Li, Shi Xu, Mengting Xu +2Self-Reflection in Language Model Agents Counterfactual Regret Minimization
School of Computer Science and Technology / School of Artificial Intelligence China University of Mining and Technology Xuzhou, China
Expected Sample Complexity in Multi-Armed Bandits
Oct 7, 2026Nadav Sukenik, Nadav MerlisMulti-Armed Bandits Regret Minimization
Technion – Institute of Technology
Instance-Dependent Regret for CMDPs with Step-Wise Constraints
Oct 1, 2026Qian Zuo, Francesco Emanuele Stradi, Leyang Xue +1Constrained RL Safe RL
University of Edinburgh · Politecnico di Milano · University College London
The Curvature of Regret in Contextual Linear Optimization
Oct 1, 2026Konstantinos Ziliaskopoulos, Alexander Vinel, Alice E. SmithDecision-Focused Learning Regret Minimization
Auburn University Auburn, AL, USA · University of Alabama Tuscaloosa, AL, USA
Minimax Optimal Regret for Causal Logistic Bandits with Counterfactual Fairness
Oct 1, 2026Junhyuk Huh, Seoungbin Bae, Dabeen LeeMulti-Armed Bandits Minimax Regret
Faculty of Mathematics, University of Cambridge · Department of Industrial & Systems Engineering, KAIST · Department of Mathematical Sciences, Seoul National University
Geometry-Dependent Online and Offline Approximation for Non-Monotone DR-Submodular Maximization
Sep 30, 2026Vaneet Aggarwal, Yiyang LuSubmodular Optimization Regret Minimization
Purdue University
Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity
Sep 29, 2026Kaixuan Ji, Qiwei Di, Qingyue Zhao +2Multi-Armed Bandits Minimax Regret
Department of Computer Science, University of California, Los Angeles, CA 90095, USA
Cost-Sensitive Online Window Size Selection for Portfolio Management
Sep 24, 2026Yi-Chen Liu, Chung-Han HsiehCost-Sensitive Learning Regret Minimization
Interdisciplinary Program of Management and Technology, National Tsing Hua University · Department of Quantitative Finance, National Tsing Hua University, Taiwan.
Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant
Sep 23, 2026Yang Cai, Vineet Gupta, Yanchen Jiang +4Minimax Regret Regret Minimization
Google Research · Yale University · Google DeepMind
Optimal No-Regret Learning for Repeated Prophet Inequality
Sep 20, 2026Kun WangRegret Minimization Optimal Stopping
Purdue University
A Horizon-Independent Regret Bound for Optimistic Hedge in General-Sum Games
Sep 19, 2026Junsoo HaGame Theory Regret Minimization
Multiplicative Optimism for Constant Regret in Games
Sep 18, 2026Ashkan Soleymani, Georgios PiliourasRegret Minimization Game-Based Learning
MIT · Google Deepmind
From Switching to Dynamic Regret: A Simple Reduction via Unbiased Random Sequences
Sep 17, 2026Yibo Wang, Wenhao Yang, Sifan Yang +3Online Convex Optimization Dynamic Regret Minimization
State Key Laboratory for Novel Software Technology, Nanjing University · School of Artificial Intelligence, Nanjing University · School of Software Technology, Zhejiang University
Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits
Sep 17, 2026Lishang Xu, Guodong Ma, Pengcheng Weng +1Multi-Armed Bandits Regret Minimization
University of Bern · EPFL
Constant Swap Regret in General-Sum Games via Two-Scale Higher-Order Optimism
Sep 15, 2026Tung MaiGame Theory Swap Regret
Adobe Research
GPU-CFR: 80x Faster Counterfactual Regret Minimization by Compiling the Game to Static Dataflow and CUDA Graph Replay
Sep 10, 2026Boning Li, Longbo HuangGPU Kernel Optimization GPU Acceleration
Institute for Interdisciplinary Information Sciences, Tsinghua University
Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions
Sep 10, 2026Rahul VazeOnline Convex Optimization Proximal Optimization
Online Inverse Integer Linear Optimization via Small-Gradient Skipping: Constant Regret and Finite Mistakes
Sep 9, 2026Akira KitaokaRegret Minimization
No-Regret Mixing of LRU and LFU with Optimal Switching Cost
Sep 7, 2026Younes Ben Mazziane, Xinying ZouCache Replacement Regret Minimization
Linköping University
Constant regret in general games via higher-order optimism
Sep 3, 2026Omar Abbadi, Rida Laraki, Panayotis MertikopoulosFollow-the-Regularized-Leader Regret Minimization
Univ. Mohammed VI Polytechnic, CMSIS, MCGT, 11103 Rabat, Morocco · Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France

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

Satisficing Regret Minimization in Bandits with Knapsacks

Qing Feng, Tianyi Ma, Ruihao Zhu

School of Operations Research and Information Engineering, Cornell University · SC Johnson College of Business, Cornell University

Regret Minimization Multi-Armed Bandits

Open paper AskPDF arXiv

We study satisficing regret minimization in bandits with knapsacks (BwK), where a learner sequentially selects randomized policies, i.e., distributions over arms, to obtain mean rewards above a satisficing threshold as frequently as possible while respecting finite resource budgets. The performance is measured by satisficing regret, the cumulative deficits of the selected policies' mean rewards below this threshold. Resource constraints introduce two difficulties: an algorithm can incur linear satisficing regret even with small standard regret as deficits to the threshold cannot be compensated, and random consumption can cause early resource depletion even when policies are feasible in expectation. To address these challenges, we propose SELECTwK, a general algorithmic template that uses a BwK learning oracle algorithm with sub-linear expected (standard) regret upper bound to search for and test candidate satisficing policies (i.e., policies whose mean rewards exceed satisficing threshold and whose expected resource consumption is feasible over the time horizon). Our regret analysis, supported by an LP-duality argument, establishes that SELECTwK attains constant expected satisficing regret when a satisficing policy exists. We further introduce a stronger regret condition that bounds the expected sum of positive reward deficits to the optimal one at each time step, under which SELECTwK achieves a sharper constant bound together with a sub-linear bound in the time horizon. As a complement, SELECTwK still preserves the oracle's sub-linear expected standard regret bound if the satisficing threshold is unattainable. Finally, we establish the oracle conditions and corresponding satisficing regret bound for existing finite-armed BwK and dynamic pricing algorithms, and conduct numerical experiments on dynamic pricing with limited inventory to demonstrate the empirical performance of SELECTwK.