Regret Minimization

Ask about this topic

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

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

Apr 7, 2026

Cost-sensitive retraining via posterior learning debt

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.

Harrison Katz

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

Bayesian Decision TheoryRegret MinimizationCost-Sensitive Learning
AskPDF
Apr 7, 2026

Adaptive Incentive Design with Regret Minimization

Incentive design constitutes a foundational paradigm for influencing the behavior of strategic agents, wherein a system planner (principal) publicly commits to an incentive mechanism designed to align individual objectives with collective social welfare. This paper introduces the Regret-Minimizing Adaptive Incentive Design (RAID) problem, which aims to synthesize incentive laws under information asymmetry and achieve asymptotically minimal regret compared to an oracle with full information. To this end, we develop the RAID algorithm, which employs a switching policy alternating between probing (exploration) and estimate-based incentivization (exploitation). The associated type estimator relies only on a weaker excitation condition required for strong consistency in least squares estimation, substantially relaxing the persistence-of-excitation assumptions previously used in adaptive incentive design. In addition, we establish the strong consistency of the proposed type estimator and prove that the incentive obtained asymptotically minimizes the planner's average regret almost surely. Numerical experiments illustrate the convergence rate of the proposed methodology.

Georgios Vasileiou, Lantian Zhang, Silun Zhang

Dept. of Mathematics at the KTH Royal Institute of Technology, Stockholm, 10044, Sweden.

Regret MinimizationMechanism Design
AskPDF
Mar 30, 2026

Next-Token Prediction and Regret Minimization

We consider the question of how to employ next-token prediction algorithms in adversarial online decision-making environments. Specifically, if we train a next-token prediction model on a distribution D\mathcal{D} over sequences of opponent actions, when is it the case that the induced online decision-making algorithm (by approximately best responding to the model's predictions) has low adversarial regret (i.e., when is D\mathcal{D} a low-regret distribution)? For unbounded context windows (where the prediction made by the model can depend on all the actions taken by the adversary thus far), we show that although not every distribution D\mathcal{D} is a low-regret distribution, every distribution D\mathcal{D} is exponentially close (in TV distance) to one low-regret distribution, and hence sublinear regret can always be achieved at negligible cost to the accuracy of the original next-token prediction model. In contrast to this, for bounded context windows (where the prediction made by the model can depend only on the past ww actions taken by the adversary, as may be the case in modern transformer architectures), we show that there are some distributions D\mathcal{D} of opponent play that are Θ(1)Θ(1)-far from any low-regret distribution D′\mathcal{D'} (even when w=Ω(T)w = Ω(T) and such distributions exist). Finally, we complement these results by showing that the unbounded context robustification procedure can be implemented by layers of a standard transformer architecture, and provide empirical evidence that transformer models can be efficiently trained to represent these new low-regret distributions.

Mehryar Mohri, Clayton Sanford, Jon Schneider +2

Google Research · Google DeepMind · Microsoft Research

Regret MinimizationNext-Token Prediction
AskPDF
Mar 26, 2026

Practical Efficient Global Optimization is No-regret

Efficient global optimization (EGO) is one of the most widely used noise-free Bayesian optimization algorithms.It comprises the Gaussian process (GP) surrogate model and expected improvement (EI) acquisition function. In practice, when EGO is applied, a scalar matrix of a small positive value (also called a nugget or jitter) is usually added to the covariance matrix of the deterministic GP to improve numerical stability. We refer to this EGO with a positive nugget as the practical EGO. Despite its wide adoption and empirical success, to date, cumulative regret bounds for practical EGO have yet to be established. In this paper, we present for the first time the cumulative regret upper bound of practical EGO. In particular, we show that practical EGO has sublinear cumulative regret bounds and thus is a no-regret algorithm for commonly used kernels including the squared exponential (SE) and Matérn kernels (ν>12ν>\frac{1}{2}). Moreover, we analyze the effect of the nugget on the regret bound and discuss the theoretical implication on its choice. Numerical experiments are conducted to support and validate our findings.

Jingyi Wang, Haowei Wang, Nai-Yuan Chiang +3

Lawrence Livermore National Laboratory, CA, USA · National University of Singapore, Singapore · National Laboratory of the Rockies, CO, USA

Bayesian OptimizationGlobal OptimizationRegret Minimization
AskPDF
Mar 21, 2026

Breaking the O(T)O(\sqrt{T}) Cumulative Constraint Violation Barrier while Achieving O(T)O(\sqrt{T}) Static Regret in Constrained Online Convex Optimization

The problem of constrained online convex optimization is considered, where at each round, once a learner commits to an action xt∈X⊂Rdx_t \in \mathcal{X} \subset \mathbb{R}^d, a convex loss function ftf_t and a convex constraint function gtg_t that drives the constraint gt(x)≤0g_t(x)\le 0 are revealed. The objective is to simultaneously minimize the static regret and cumulative constraint violation (CCV) compared to the benchmark that knows the loss functions and constraint functions ftf_t and gtg_t for all tt ahead of time, and chooses a static optimal action that is feasible with respect to all gt(x)≤0g_t(x)\le 0. In recent prior work Sinha and Vaze [2024], algorithms with simultaneous regret of O(T)O(\sqrt{T}) and CCV of O(T)O(\sqrt{T}) or (CCV of O(1)O(1) in specific cases Vaze and Sinha [2025], e.g. when d=1d=1) have been proposed. It is widely believed that CCV is Ω(T)Ω(\sqrt{T}) for all algorithms that ensure that regret is O(T)O(\sqrt{T}) with the worst case input for any d≥2d\ge 2. In this paper, we refute this and show that the algorithm of Vaze and Sinha [2025] simultaneously achieves regret of O(T)O(\sqrt{T}) regret and CCV of O(T1/3)O(T^{1/3}) when d=2d=2.

Haricharan Balasundaram, Karthick Krishna Mahendran, Rahul Vaze

Online Convex OptimizationConstrained OptimizationRegret Minimization
AskPDF
Mar 21, 2026

Bayesian Learning in Episodic Zero-Sum Games

We study Bayesian learning in episodic, finite-horizon zero-sum Markov games with unknown transition and reward models. We investigate a posterior algorithm in which each player maintains a Bayesian posterior over the game model, independently samples a game model at the beginning of each episode, and computes an equilibrium policy for the sampled model. We analyze two settings: (i) Both players use the posterior sampling algorithm, and (ii) Only one player uses posterior sampling while the opponent follows an arbitrary learning algorithm. In each setting, we provide guarantees on the expected regret of the posterior sampling agent. Our notion of regret compares the expected total reward of the learning agent against the expected total reward under equilibrium policies of the true game. Our main theoretical result is an expected regret bound for the posterior sampling agent of order O(HSABHKlog⁡(SABHK))O(HS\sqrt{ABHK\log(SABHK)}) where KK is the number of episodes, HH is the episode length, SS is the number of states, and A,BA,B are the action space sizes of the two players. Experiments in a grid-world predator--prey domain illustrate the sublinear regret scaling and show that posterior sampling competes favorably with a fictitious-play baseline.

Chang-Wei Yueh, Andy Zhao, Ashutosh Nayyar +1

Department of Electrical and Computer Engineering at the University of Southern California

Zero-Sum GamesGame-Theoretic RLBayesian RLRegret Minimization
AskPDF
Mar 19, 2026

On the Peril of (Even a Little) Nonstationarity in Satisficing Regret Minimization

Motivated by the principle of satisficing in decision-making, we study satisficing regret guarantees for nonstationary KK-armed bandits. We show that in the general realizable, piecewise-stationary setting with LL stationary segments, the optimal regret is Θ(Llog⁡T)Θ(L\log T) as long as L≥2L\geq 2. This stands in sharp contrast to the case of L=1L=1 (i.e., the stationary setting), where a TT-independent Θ(1)Θ(1) satisficing regret is achievable under realizability. In other words, the optimal regret has to scale with TT even if just a little nonstationarity presents. A key ingredient in our analysis is a novel Fano-based framework tailored to nonstationary bandits via a post-interaction reference construction. This framework strictly extends the classical Fano method for passive estimation as well as recent interactive Fano techniques for stationary bandits. As a complement, we also discuss a special regime in which constant satisficing regret is again possible.

Yixuan Zhang, Ruihao Zhu, Qiaomin Xie

Department of Industrial & Systems Engineering, University of Wisconsin-Madison · SC Johnson College of Business, Cornell University

Regret MinimizationNon-Stationary BanditsInformation-Theoretic Lower Bounds
AskPDF
Mar 10, 2026

Better Bounds for the Distributed Experts Problem

In this paper, we study the distributed experts problem, where nn experts are distributed across ss servers for TT timesteps. The loss of each expert at each time tt is the ℓp\ell_p norm of the vector that consists of the losses of the expert at each of the ss servers at time tt. The goal is to minimize the regret RR, i.e., the loss of the distributed protocol compared to the loss of the best expert, amortized over the all TT times, while using the minimum amount of communication. We give a protocol that achieves regret roughly R≳1T⋅polylog⁡(nsT)R\gtrsim\frac{1}{\sqrt{T}\cdot\text{poly}\log(nsT)}, using O(nR2+sR2)⋅max⁡(s1−2/p,1)⋅polylog⁡(nsT)\mathcal{O}\left(\frac{n}{R^2}+\frac{s}{R^2}\right)\cdot\max(s^{1-2/p},1)\cdot\text{poly}\log(nsT) bits of communication, which improves on previous work.

David P. Woodruff, Samson Zhou

Carnegie Mellon University · Texas A&M University

Regret MinimizationCommunication Complexity
AskPDF
Mar 6, 2026

Bilateral Trade Under Heavy-Tailed Valuations: Minimax Regret without a Variance Bound

In contextual bilateral trade under full feedback, the posted price does not affect which valuations are observed. We show that in this model such action-independent feedback removes the polynomial adaptation penalty familiar from heavy-tailed bandits: fully parameter-free algorithms attain the oracle minimax TT-exponents up to logarithmic factors, with no knowledge of the moment order p∈(1,2)p \in (1,2) or its scale σpσ_p, and -- in the nonparametric case -- none of the effective Hölder smoothness β∈(0,1]β\in (0,1]. The statistic that makes model selection possible is a paired squared-loss difference, whose noise-square term cancels exactly, leaving noise damped by the candidate gap. The resulting bilateral-trade regret rates are new. Trader valuations have bounded conditional densities and heavy tails -- finite pp-th moments for some p∈(1,2)p \in (1,2), with possibly infinite variance. An epoch-based algorithm with truncated means achieves regret O~(T(2−p)/p)\widetilde{O}(T^{(2-p)/p}) in the parametric model and O~(T1−2β(p−1)/(βp+d(p−1)))\widetilde{O}(T^{1-2β(p-1)/(βp + d(p-1))}) when the market value function is ββ-Hölder, with matching Ω(⋅)Ω(\cdot) lower bounds -- under a mild nondegeneracy condition -- via Assouad's method and a fixed-support mixture construction -- characterizing the minimax rate in TT up to logarithmic factors over the effective smoothness range β∈(0,1]β\in (0,1], interpolating between the classical nonparametric rate at p=2p{=}2 and the trivial linear rate as p→1+p \to 1^+. The enabling structural step extends the self-bounding property of Bachoc et al. (ICML 2025) from bounded to real-valued valuations: within our conditionally independent, conditionally centered noise model, bounded conditional densities and finite first moments suffice for the expected regret of any price ππ to satisfy E[g(m,V,W)−g(π,V,W)]≤L∣m−π∣2\mathbb{E}[g(m,V,W) - g(π,V,W)] \le L|m-π|^2 -- no second moment is needed.

Hangyi Zhao

Minimax RegretRegret MinimizationContextual Bandits
AskPDF
Mar 3, 2026

A Short Note on a Variant of the Squint Algorithm

This short note describes a simple variant of the Squint algorithm of Koolen and Van Erven [2015] for the classic expert problem. Via an equally simple modification of their proof, we prove that this variant ensures a regret bound that resembles the one shown in a recent work by Freund et al. [2026] for a variant of the NormalHedge algorithm [Chaudhuri et al., 2009].

Haipeng Luo

University of Southern California

Regret Minimization
AskPDF
Feb 25, 2026

Revisiting the Bertrand Paradox via Equilibrium Analysis of No-regret Learners

We study the discrete Bertrand pricing game with a non-increasing demand function. The game has n≥2n \ge 2 players who simultaneously choose prices from the set {1/k,2/k,…,1}\{1/k, 2/k, \ldots, 1\}, where k∈Nk\in\mathbb{N}. The player who sets the lowest price captures the entire demand; if multiple players tie for the lowest price, they split the demand equally. We study the Bertrand paradox, where classical theory predicts low prices, yet real markets often sustain high prices. To understand this gap, we analyze a repeated-game model in which firms set prices using no-regret learners. Our goal is to characterize the equilibrium outcomes that can arise under different no-regret learning guarantees. We are particularly interested in questions such as whether no-external-regret learners can converge to undesirable high-price outcomes, and how stronger guarantees such as no-swap regret shape the emergence of competitive low-price behavior. We address these and related questions through a theoretical analysis, complemented by experiments that support the theory and reveal surprising phenomena for no-swap regret learners.

Arnab Maiti, Junyan Liu, Kevin Jamieson +1

University of Washington

Swap RegretGame TheoryRegret MinimizationRepeated Games
AskPDF
Feb 24, 2026

Prior-Agnostic Incentive-Compatible Exploration

In bandit settings, optimizing long-term regret metrics requires exploration, which corresponds to sometimes taking myopically sub-optimal actions. When a long-lived principal merely recommends actions to be executed by a sequence of different agents (as in an online recommendation platform) this provides an incentive misalignment: exploration is "worth it" for the principal but not for the agents. Prior work studies regret minimization under the constraint of Bayesian Incentive-Compatibility in a static stochastic setting with a fixed and common prior shared amongst the agents and the algorithm designer. We show that (weighted) swap regret bounds on their own suffice to cause agents to faithfully follow forecasts in an approximate Bayes Nash equilibrium, even in dynamic environments in which agents have conflicting prior beliefs and the mechanism designer has no knowledge of any agents beliefs. To obtain these bounds, it is necessary to assume that the agents have some degree of uncertainty not just about the rewards, but about their arrival time -- i.e. their relative position in the sequence of agents served by the algorithm. We instantiate our abstract bounds with concrete algorithms for guaranteeing adaptive and weighted regret in bandit settings.

Ramya Ramalingam, Osbert Bastani, Aaron Roth

Department of Computer and Information Sciences, University of Pennsylvania

Swap RegretMulti-Armed BanditsRegret MinimizationDynamic Regret Minimization
AskPDF
Feb 18, 2026

Discovering Multiagent Learning Algorithms with Large Language Models

Much of the advancement in Multi-Agent Reinforcement Learning (MARL) for imperfect-information games has historically depended on the manual, iterative refinement of algorithmic baselines. Recently, evolutionary coding agents powered by Large Language Models (LLMs) have emerged as powerful tools to automate this discovery process. In this work, we deploy one of such agentic frameworks, AlphaEvolve, to navigate the design spaces of two distinct game-theoretic paradigms: counterfactual regret minimization (CFR) and policy-space response oracles (PSRO). This automated search yielded two algorithms: Volatility-Adaptive Discounted (VAD-) CFR and Smoothed Hybrid Optimistic Regret (SHOR-) PSRO, which are consistently competitive with state-of-the-art human-designed baselines across an 18-game evaluation suite spanning Poker, Goofspiel, Liar's Dice, Blotto, and Battleship variants. However, because the LLM optimizes for fitness on a specific training set, it often constructs highly synergistic, complex mechanisms tailored to those environments. Through systematic ablation studies, we demonstrate that while these mechanisms are tightly coupled, the true driver of generalization lies in a minimal algorithmic core. By distilling the LLM's discoveries down to their most fundamental principles, we produce two minimal solvers: Warm-started Optimistic Predictive (WOP-)CFR and Projection Matching (PM-)PSRO. These distilled versions achieve superior performance on generalization with greatly reduced structural complexity, providing a clear methodology for using LLMs in algorithmic discovery.

Zun Li, John Schultz, Daniel Hennes +1

Google DeepMind

Counterfactual Regret MinimizationMulti-Agent Reinforcement LearningRegret MinimizationGeneralization in RLLarge Language Model-Guided Optimization
AskPDF
Feb 16, 2026

Decision Making under Imperfect Recall: Algorithms and Benchmarks

In game theory, imperfect-recall decision problems model situations in which an agent forgets information it held before. They encompass games such as the ``absentminded driver'' and team games with limited communication. In this paper, we introduce the first benchmark suite for imperfect-recall decision problems. Our benchmarks capture a variety of problem types, including ones concerning privacy in AI systems that elicit sensitive information, and AI safety via testing of agents in simulation. Across 61 problem instances generated using this suite, we evaluate the performance of different algorithms for finding first-order optimal strategies in such problems. In particular, we introduce the family of regret matching (RM) algorithms for nonlinear constrained optimization. This class of parameter-free algorithms has enjoyed tremendous success in solving large two-player zero-sum games, but, surprisingly, they were hitherto relatively unexplored beyond that setting. Our key finding is that RM algorithms consistently outperform commonly employed first-order optimizers such as projected gradient descent, often by orders of magnitude. This establishes, for the first time, the RM family as a formidable approach to large-scale constrained optimization problems.

Emanuel Tewolde, Brian Hu Zhang, Ioannis Anagnostides +2

Computer Science Dept., Carnegie Mellon University, Pittsburgh, USA · Foundations of Cooperative AI Lab (FOCAL) · Strategy Robot, Inc.; Strategic Machine, Inc.; and Optimized Markets, Inc.

Sequential Decision MakingRegret MinimizationConstrained OptimizationImperfect-Information Games
AskPDF
Jan 20, 2026

Small Gradient Norm Regret for Online Convex Optimization

This paper introduces a new problem-dependent regret measure for online convex optimization with smooth losses. The notion, which we call the G⋆G^\star regret, depends on the cumulative squared gradient norm evaluated at the decision in hindsight. We show that the G⋆G^\star regret strictly refines the existing L⋆L^\star (small loss) regret, and that it can be arbitrarily sharper when the losses have vanishing curvature around the hindsight decision. We establish upper and lower bounds on the G⋆G^\star regret and extend our results to dynamic regret and bandit settings. As a byproduct, we refine the existing convergence analysis of stochastic optimization algorithms in the interpolation regime. Some experiments validate our theoretical findings.

Wenzhi Gao, Chang He, Madeleine Udell

ICME, Stanford University · SIME, Shanghai University of Finance and Economics · Department of Management Science and Engineering, Stanford University

Online Convex OptimizationSequential Decision MakingRegret Minimization
AskPDF
Jan 5, 2026

Prior Diffusiveness and Regret in the Linear-Gaussian Bandit

We prove that Thompson sampling exhibits O~(σdT+drTr(Σ0))\tilde{O}(σd \sqrt{T} + d r \sqrt{\mathrm{Tr}(Σ_0)}) Bayesian regret in the linear-Gaussian bandit with a N(μ0,Σ0)\mathcal{N}(μ_0, Σ_0) prior distribution on the coefficients, where dd is the dimension, TT is the time horizon, rr is the maximum ℓ2\ell_2 norm of the actions, and σ2σ^2 is the noise variance. In contrast to existing regret bounds, this shows that to within logarithmic factors, the prior-dependent burn-in'' term $d r \sqrt{\mathrm{Tr}(Σ_0)}$ decouples additively from the minimax (long run) regret $σd \sqrt{T}$. Previous regret bounds exhibit a multiplicative dependence on these terms. We establish these results via a new elliptical potential'' lemma, and also provide a lower bound indicating that the burn-in term is unavoidable.

Yifan Zhu, John C. Duchi, Benjamin Van Roy

Department of Electrical Engineering, Stanford University, California, United States.

Thompson SamplingMulti-Armed BanditsRegret Minimization
AskPDF
Nov 29, 2025

No-Regret Gaussian Process Optimization of Time-Varying Functions

Sequential optimization of black-box functions from noisy evaluations has been widely studied, with Gaussian Process bandit algorithms such as GP-UCB guaranteeing no-regret in stationary settings. However, for time-varying objectives, no-regret is unattainable under pure bandit feedback unless strong and often unrealistic assumptions are imposed. We propose a novel method for optimizing time-varying rewards in the frequentist setting, where the objective has bounded RKHS norm almost surely. Time variations are captured through uncertainty injection, enabling heteroscedastic Gaussian process regression that adapts past observations to the current time step. As no-regret is unattainable in general in the strict bandit setting, we relax the latter allowing additional queries on previously observed points. Building on sparse inference and the effect of uncertainty injection on regret, we propose W-SparQ-GP-UCB, an online algorithm that achieves no-regret with a vanishing number of additional queries per iteration. To assess the theoretical limits of this approach, we establish a lower bound on the number of additional queries required for no-regret, proving the efficiency of our method. Finally, we provide a comprehensive analysis linking the temporal regime of the function to achievable regret rates, together with upper and lower bounds on the number of additional queries needed in each regime.

Eliabelle Mauduit, Eloïse Berthier, Andrea Simonetto

Unit´e de Math´ematiques Appliqu´ees ENSTA, Institut Polytechnique de Paris Palaiseau, France · U2IS ENSTA, Institut Polytechnique de Paris Palaiseau, France

Multi-Armed BanditsBayesian OptimizationGaussian Process BanditsRegret MinimizationGaussian Process Regression
AskPDF
Jul 9, 2025

Direct Regret Optimization in Bayesian Optimization

Bayesian optimization (BO) is a powerful paradigm for optimizing expensive black-box functions. Traditional BO methods typically rely on separate hand-crafted acquisition functions and surrogate models for the underlying function, and often operate in a myopic manner. In this paper, we propose a novel direct regret optimization approach that jointly learns the optimal model and non-myopic acquisition by distilling from a set of candidate models and acquisitions, and explicitly targets minimizing the multi-step regret. Our framework leverages an ensemble of Gaussian Processes (GPs) with varying hyperparameters to generate simulated BO trajectories, each guided by an acquisition function drawn from a pool of conventional choices and terminated by a Bayesian early stop criterion. These trajectories train an end-to-end Decision Transformer that selects the next query so as to improve the ultimate objective, following a dense training sparse learning paradigm: the transformer is trained on abundant simulated data, while a limited number of real evaluations refine the GPs online. On synthetic and real-world benchmarks, our method attains the best or near-best final simple regret against standard, lookahead, trust-region and amortized BO baselines, with the largest gains in high-dimensional settings. Ablations attribute the gains jointly to region-of-interest filtering and the learned policy, and matched-budget comparisons against explicit two-step lookahead acquisitions show that the advantage is not shared by lookahead alone.

Fengxue Zhang, Yuxin Chen

Department of Computer Science University of Chicago Chicago, IL 60637

Bayesian OptimizationLearning to OptimizeDecision TransformerRegret Minimization
AskPDF
Aug 1, 2024

Infrequent Resolving Algorithm for Online Linear Programming

Online linear programming (OLP) has gained significant attention from both researchers and practitioners due to its extensive applications such as online auctions, network revenue management, order fulfillment and advertising. Existing OLP algorithms fall into two categories: LP-based algorithms and LP-free algorithms. The former typically guarantees better performance but requires solving a large number of LPs, which could be computationally expensive. In contrast, LP-free algorithms only require first-order computations but induce a worse performance. In this work, we bridge the gap between these two extremes by proposing a well-performing algorithm that solves LPs at a few selected time points and conducts first-order computations at other time points. Specifically, for the case where the inputs are drawn from an unknown finite-support distribution, the proposed algorithm achieves a constant regret (even for the hard "degenerate" case) while solving LPs only O(log⁡log⁡T)O(\log\log T) times over the time horizon TT. Moreover, when we are allowed to solve LPs only MM times, we design the corresponding schedule such that the proposed algorithm can guarantee a nearly O(T(1/2)M−1)O\left(T^{(1/2)^{M-1}}\right) regret. Our work highlights the value of resolving both at the beginning and the end of the selling horizon, and provides a novel framework to prove the performance guarantee of the proposed policy under different infrequent resolving schedules. Numerical experiments are conducted to demonstrate the efficiency of the proposed algorithms.

Guokai Li, Zizhuo Wang, Jingwei Zhang

School of Data Science, The Chinese University of Hong Kong, Shenzhen, Guangdong, 518172, P.R. China

Sequential Decision MakingRegret MinimizationLinear ProgrammingOnline Resource Allocation
AskPDF
Aug 1, 2024

Online Linear Programming with Batching

We study Online Linear Programming (OLP) with batching. The planning horizon is cut into KK batches, and decisions on orders can be delayed to the end of their associated batch. The ability to delay decisions improves operational performance, as measured by regret. We study two questions: (1) What is a lower bound on the regret as a function of KK and the length of the planning horizon? (2) Which algorithms can achieve this regret lower bound? This paper analyzes these questions when the distribution of the reward has a continuous support. We provide an Ω(log⁡K)Ω(\log K) regret lower bound in the single-resource case, and we provide pricing algorithms having an O(log⁡K)O(\log K) regret in the setting with Poisson arrivals and multiple types of resources. All the algorithms update the prices at most KK times and only delay orders of the first and the last batches. All the regret bounds are independent of the length of the planning horizon. Finally, we study a more realistic large support setting where the number of distinct order types is finite but scales with the total number of orders. We prove that our Θ(log⁡K)Θ(\log K) bounds still hold for the batching operation of a multisecretary problem with discretized uniform rewards in this large support setting, provided the support grows fast enough. This suggests that the continuous support setting that is the paper's focus serves as a useful theoretical surrogate for the more realistic large finite support setting.

Haoran Xu, Peter W. Glynn, Yinyu Ye

Department of Management Science and Engineering, Stanford University

Sequential Decision MakingRegret MinimizationLinear ProgrammingDynamic PricingOnline Resource AllocationOperations Research
AskPDF
Jun 10, 2024

Satisficing Regret Minimization in Bandits: Constant Rate and Light-Tailed Distribution

Motivated by the concept of satisficing in decision-making, we consider the problem of satisficing regret minimization in bandit optimization. In this setting, the learner aims at selecting satisficing arms (arms with mean reward exceeding a certain threshold value) as frequently as possible. The performance is measured by satisficing regret, which is the cumulative deficit of the chosen arm's mean reward compared to the threshold. We propose SELECT, a general algorithmic template for Satisficing REgret Minimization via SampLing and LowEr Confidence bound Testing, that attains constant expected satisficing regret for a wide variety of bandit optimization problems in the realizable case (i.e., a satisficing arm exists). As a complement, SELECT also enjoys the same (standard) regret guarantee as the oracle in the non-realizable case. To further ensure stability of the algorithm, we introduce SELECT-LITE that achieves a light-tailed satisficing regret distribution plus a constant expected satisficing regret in the realizable case and a sub-linear expected (standard) regret in the non-realizable case. Notably, SELECT-LITE can operate on learning oracles with heavy-tailed (standard) regret distribution. More importantly, our results reveal the surprising compatibility between constant expected satisficing regret and light-tailed satisficing regret distribution, which is in sharp contrast to the case of (standard) regret. Finally, we conduct numerical experiments to validate the performance of SELECT and SELECT-LITE on both synthetic datasets and a real-world dynamic pricing case study.

Qing Feng, Tianyi Ma, Ruihao Zhu

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

Multi-Armed BanditsRegret Minimization
AskPDF
Jun 5, 2023

Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents

We introduce Calibrated Stackelberg Games (CSGs), a generalization of the standard Stackelberg Games (SGs) framework. In CSGs, a principal repeatedly interacts with an agent who (contrary to standard SGs) does not have direct access to the principal's action but instead best-responds to calibrated forecasts about it. This framework provides a powerful and realistic modeling tool that goes beyond assuming that agents use ad hoc and highly specified algorithms for interacting in strategic settings and instead builds on statistical foundations of forecasts and calibration. We show that in CSGs, despite both the principal and the agent having less information than in standard SGs, the principal's optimal utility remains upper and lower bounded by the Stackelberg value of the one-shot game, in both finite and continuous settings. Alongside CSGs, we develop stronger notions of calibration and corresponding algorithms that address two central challenges for calibration in game-theoretic environments. First, achieving point-wise calibration typically incurs an error that scales exponentially with the dimension of the strategy space. Second, the principal's convergence rate in CSGs depends critically on the adaptivity of the agent's calibration algorithm. To address these challenges, we establish a meaningful, efficiently achievable relaxation of calibration based on conditioning on best-response regions. This yields the first notion of calibration in games with a statistical rate that only depends on the number of agents' actions rather than the dimension of the principal's strategy space and that leads to no-swap regret for the agent. We further develop adaptive calibration algorithms for the agents that provide fine-grained, any-time calibration guarantees against adversarial sequences, enabling the principal to achieve faster convergence in CSGs.

Nika Haghtalab, Chara Podimata, Kunhe Yang

University of California, Berkeley · Massachusetts Institute of Technology

Imperfect-Information GamesGame TheoryStackelberg GamesRegret Minimization
AskPDF
May 27, 2023

Hierarchical Deep Counterfactual Regret Minimization

Imperfect Information Games (IIGs) are used to model games under uncertainty or lack complete information. Counterfactual Regret Minimization (CFR) is one of the most successful families of algorithms for IIGs. The integration of skill-based strategy learning with CFR could potentially mirror more human-like decision-making and improve learning on complex IIGs. It enables the learning of a hierarchical strategy, wherein low-level components represent skills for solving subgames and the high-level component manages the transition between skills. In this paper, we introduce the first hierarchical version of Deep CFR (HDCFR), an innovative method that boosts learning efficiency in tasks involving extensively large state spaces and deep game trees. Notably, HDCFR enables learning with predefined (human) expertise and extracting skills transferable to similar tasks. We first present the algorithm and establish its theory in a tabular setting, including hierarchical CFR update rules and a variance-reduced Monte Carlo sampling extension for the model-free setting, where backtracking is infeasible. We then extend HDCFR to large-scale tasks via deep learning objectives that match the tabular targets under exact function fitting. Code: https://anonymous.4open.science/r/HDCFR_RUN-677B.

Jiayu Chen, Xudong Wu, Zhekai Wang +1

The University of Hong Kong Hong Kong SAR · Peking University Beijing, China, 100871 · Purdue University2025 West Lafayette, IN 47907

Imperfect-Information GamesHierarchical RLCounterfactual Regret MinimizationRegret MinimizationModel-Free RLCounterfactual Learning
AskPDF
Feb 3, 2023

Robust Budget Pacing with a Single Sample

Major Internet advertising platforms offer budget pacing tools as a standard service for advertisers to manage their ad campaigns. Given the inherent non-stationarity in an advertiser's value and also competing advertisers' values over time, a commonly used approach is to learn a target expenditure plan that specifies a target spend as a function of time, and then run a controller that tracks this plan. This raises the question: how many historical samples are required to learn a good expenditure plan? We study this question by considering an advertiser repeatedly participating in TT second-price auctions, where the tuple of her value and the highest competing bid is drawn from an unknown time-varying distribution. The advertiser seeks to maximize her total utility subject to her budget constraint. Prior work has shown the sufficiency of Tlog⁡TT\log T samples per distribution to achieve the optimal O(T)O(\sqrt{T})-regret. We dramatically improve this state-of-the-art and show that just one sample per distribution is enough to achieve the near-optimal O~(T)\tilde O(\sqrt{T})-regret, while still being robust to noise in the sampling distributions.

Santiago Balseiro, Rachitesh Kumar, Vahab Mirrokni +2

DRO, Columbia Business School, New York, NY, USA · Google Research, New York, NY, USA · IEOR, Columbia University, New York, NY, USA

Sample ComplexityOnline AdvertisingRegret Minimization
AskPDF