Regret Minimization

Follow this topic Ask about this topic

Momentum

12 papers in the last four weeks, up 71% on the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 81

Jul 2, 2026cs.LG

Online Resource Allocation with Continuous Random Consumption: Regret under Degeneracy

We study online resource allocation when both rewards and consumption sizes may be continuously distributed. Requests arrive sequentially and must be accepted or rejected irrevocably under fixed resource capacities. Each request belongs to one of finitely many observable types; conditional on an observable request type, both the reward and the scalar size are random, and the realized size scales a fixed type-specific resource-consumption vector. The model allows the deterministic fluid relaxation to be degenerate. We show that additive regret is governed by the size-weighted mass of requests whose value-to-size ratios lie near the active acceptance cutoffs. We formalize this quantity through an active weighted-mass exponent p. When p > 1, this cutoff mass is thin, and the problem is genuinely hard: every online policy must incur regret of order at least

T^{1/2 - 1/(2p)}

, and this holds for every p > 1. A sample-path marginal policy matches this lower bound up to polylogarithmic factors; and when p = 1, so that the mass grows linearly near the cutoff, it attains

O((\log T)^2)

regret. For example, if the size and the value-to-size ratio are independent and uniformly distributed, then p = 1; if instead the size and the reward are independent and uniformly distributed, then p = 2. Thus the policy achieves

o(\sqrt{T})

regret throughout this regularity class without any fluid non-degeneracy assumption, allowing both primal degeneracy and dual non-uniqueness.

Jiawei Zhang

Stern School of Business New York University

Regret Minimization Online Resource Allocation

Jul 2, 2026cs.DS

Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates

This paper studies additive regret in the multi-secretary problem, defined as the gap between the expected offline prophet reward and the reward of the best online policy. Prior work established

O(\log T)

regret for bounded-density distributions with connected support and

O((\log T)^2)

upper bounds for bounded-density distributions with support gaps. It was unknown whether the extra logarithmic factor is necessary even in the one-resource model. We prove that it is necessary. For a mixture of two separated uniform distributions at the critical capacity, the optimal regret grows at least on the order of

(\log T)^2

. Thus the existing

O((\log T)^2)

upper bounds for bounded-density gapped instances, including those implied by network revenue management models with continuous rewards, are tight in this simplest specialization. The same framework also yields a matching lower bound for gapped distributions whose gap-facing densities vanish near the support edges; this companion result is given in the appendix. The proofs use Bellman certificates: feasible solutions to a relaxation of the exact Bellman recursion. This framework converts lower bounds into explicit certificate constructions and identifies why support gaps permit larger regret.

Jiawei Zhang

Department of Technologies, Operations, and Statistics Stern School of Business, New York University

Regret Minimization Online Resource Allocation

Jun 28, 2026cs.GT

Improved Multi-Dimensional Forecasting for Swap Regret

We study the problem of forecasting for an arbitrary number of downstream agents with unknown objectives, each of whom best responds to the forecaster's predictions. We seek a single forecaster that guarantees sublinear swap regret for all downstream agents simultaneously. For two-dimensional outcome spaces, we give a polynomial time algorithm that guarantees

\tilde{O}(\sqrt{kT})

swap regret for any downstream agent with

k

actions. This improves over the previously known bound of

\tilde{O}(kT^{5/8})

and avoids the exponential in

T

runtime of prior algorithms in this setting. Our algorithm extends nicely to other low dimensional environments, retaining

\tilde{O}(\sqrt{T})

downstream swap regret while the exponent of

k

in the regret bound and the exponent of

T

in the running time both grow with dimension. For arbitrary dimension

d

, we give a forecasting algorithm that guarantees

\tilde{O}(d\sqrt{kT})

swap regret, assuming the forecaster knows an upper bound

k

on the number of actions available to any downstream agent, albeit with a much longer runtime. This improves upon previous high dimensional guarantees that had

\tilde{O}(T^{2/3})

dependence and required additional behavioral assumptions.

Joey Rivkin, Ramiro N. Deo-Campo Vuong, Robert Kleinberg +3

Cornell University

Regret Minimization Online Learning

Jun 26, 2026cs.GT

Which Nash Equilibrium? Solver-Dependent Selection on Zero-Sum Nash Polytopes

Many two-player zero-sum games admit not a unique Nash equilibrium but a convex set of them: a polytope of profiles that all share the minimax value V* yet prescribe different behaviour. Standard solvers each converge to some equilibrium and are treated as interchangeable. We ask whether they instead select different members of the Nash set, systematically as a function of the algorithm rather than the seed. Using a tabular, exactly solvable testbed of six games with analytically known Nash sets -- including a two-dimensional Nash polytope and Kuhn poker -- we find that (i) selection is determined by the algorithm, not the seed, but families differ only on asymmetric Nash sets; (ii) regularized last-iterate methods (R-NaD, magnetic mirror descent) select the maximum-entropy member, the information projection of their uniform reference onto the Nash set -- exactly on the 2-D polytope and at 99.7% of maximum entropy in Kuhn -- while regret-averaging methods (CFR, CFR+, fictitious play) drift to a lower-entropy face; we confirm this on a randomized 180-game ensemble, where R-NaD attains the maximum-entropy member in 100% of converged games while CFR+ sits strictly below it in 94% (paired Wilcoxon p < 10^-27); (iii) the selected member has downstream consequences against sub-optimal opponents that scale with sequential/hidden-information structure but stay bounded -- in Kuhn the max-entropy member is a strictly better hedge, whereas on the matrix games the members differ without either dominating. We also report two negative results correcting common intuitions: removing CFR's positive-orthant (max(R,0)) projection does not eliminate boundary drift; and R-NaD's selection is anchor-following, not initialization-independent. We state the maximum-entropy / I-projection characterization as a strongly data-supported conjecture, checked throughout against analytic ground truth.

Luis Leal

Nash Equilibrium Imperfect-Information Games Zero-Sum Games Regret Minimization Nash Equilibrium Computation

Jun 25, 2026stat.ML

The Decision Geometry of Covariance Estimation for the Global Minimum-Variance Portfolio under Heavy Tails

The global minimum-variance portfolio (GMVP) is the canonical decision built from an estimated covariance matrix, yet covariance estimators are universally evaluated by matrix-norm loss, which is not the object the decision depends on. We characterise exactly how covariance-estimation error maps into GMVP suboptimality. We prove an exact regret identity and a non-asymptotic bound showing decision regret depends on the estimation error only through its action on the portfolio weights, scaled by portfolio concentration and the conditioning of the true covariance. From this we derive the decision geometry: GMVP regret is invariant to a (p-1)-dimensional projection of the p^2-dimensional error matrix, with invariance to the covariance-scale direction as an exact special case. We then apply the framework to heavy-tailed returns (tail index kappa in (2,4)), establishing the regret convergence rate implied by the centred operator-norm rate, and confirm the theory on a skew-t/t-copula simulation design with pre-registered analysis. The decision-focused advantage is a sharper constant and a concentration discount rather than a faster rate; we report an honest high-conditioning boundary of the rate prediction. The results complement recent decision-focused learning approaches by supplying the exact estimation geometry and consistency theory they lack.

Xavier Fonseca

Academy for AI, Games and Media, Breda University of Applied Sciences, Breda, The Netherlands.

Regret Minimization Portfolio Optimization Heavy-Tailed Distributions Covariance Estimation

Jun 22, 2026cs.AI

YUKTI: From Natural-Language Situations to Robust, Verifiable Decisions An Uncertainty-Typed Proposition IR, Assumption-Robust Pareto Frontiers, and a Regret Certificate

Language models turn a worded situation into a numeric plan, and the dominant pipelines (NL4Opt, OptiMUS, ORLM, OR-LLM-Agent) commit to a single objective and point-valued coefficients, then solve once. For decisions that allocate real budget, effort, or clinical attention, that confidence is the failure mode: every objectified number is an assumption, and a plan optimal only if the guesses are exactly right is fragile -- mimicry of computation. YUKTI changes the target of autoformulation. Its representation is a typed-proposition graph whose relationships carry shape priors, coefficient uncertainty, and provenance. YUKTI routes each stage to an exact, nonlinear, or evolutionary solver; couples stages by a distributional Pareto hand-off; and introduces Assumption-Robust Pareto Frontiers (ARPF), resampling assumptions (including structural epsilon-contamination) to score how often each action survives (rho). We prove a bound making rho an exact factor of decision regret, add auditable traceability, and synthesize a benchmark-faithful data foundation when none exists (SRJANA). We validate three ways: under controlled misspecification the robust compromise cuts mean and tail regret by over 90% versus a naive point plan; on a regulated commercial decision we optimize inside a lawful action space and price the downside in euros; and on a real public dataset of 41,188 decisions an out-of-sample backtest beats the logged status quo by 34% and a naive point rule by 4% while reducing the optimizer's curse. The solvers are standard; we claim no benchmark-SOTA win. A head-to-head shows an LLM given the correct numbers, and single-objective optimization, both incur about 47x the held-out regret of YUKTI -- an LLM is a formulator, not a solver. Under long-range causal coupling, the forward hand-off becomes unsound, locating where it must become a backward-induction causal policy.

Suyash Mishra

AI Researcher

Large Language Model-Guided Optimization Robust Optimization Regret Minimization Uncertainty Propagation Multi-Objective Optimization Natural Language to Optimization Modeling+1

Jun 16, 2026stat.ML

Toward Simultaneously Optimal Regret in U-Calibration

U-calibration studies online forecasting algorithms whose predictions can be consumed by any unknown downstream agent, guaranteeing sublinear regret simultaneously for all proper loss functions. Existing U-calibration algorithms achieve worst-case optimal

O(\sqrt{T})

regret for every bounded proper loss, but they fail to adapt to easier losses: as we show, even for smooth losses such as squared loss, they incur

Ω(\sqrt{T})

regret instead of the optimal

O(\log T)

regret. In this work, we show that this limitation is not inherent. Specifically, we design a single forecast algorithm that simultaneously achieves

\tilde O(\sqrt{T})

regret for every bounded proper loss and

O(\log T)

regret for every bounded smooth proper loss. More generally, our algorithm also attains logarithmic regret for losses that are smooth relative to the log-barrier, which include several non-Lipschitz examples. Our approach is based on a novel variant of Follow-the-Perturbed-Leader (FTPL) in which perturbations are applied directly in the prediction space using self-concordant noise. The resulting analysis also departs substantially from prior FTPL analyses due to the complex nature of this noise and may be of independent interest.

Rafael Frongillo, Haipeng Luo, Nishant A. Mehta +1

University of Colorado Boulder · University of Southern California and Google Research · University of Victoria +1

Probabilistic Forecasting Proper Scoring Rules Regret Minimization

Jun 15, 2026cs.LG

Filtered ANN as a Phase Transition: When Selectivity-Estimation Error Causes Plan Regret

A filtered approximate-nearest-neighbor (ANN) query returns the k nearest vectors among those satisfying an attribute predicate P of selectivity s. The best execution strategy -- pre-filter, post-filter, or in-filter -- changes with s, so a system must estimate s and choose. We model this as an argmax over a landscape with phases (regions where each strategy wins) separated by boundaries, and show that selectivity-estimation error produces plan regret -- recall lost versus the oracle strategy -- only in the critical regions around those boundaries. The regret is a wedge of log-width equal to the multiplicative estimation error epsilon and height equal to the local cliff |V'(s*)| epsilon; the flip-margin 1/|V'(s*)| is the condition number of a sibling cardinality-estimation study reappearing as the local boundary theory. The two phase boundaries follow from independent mathematics: order statistics place the post-filter cliff at s ~ k/K, and site percolation places the in-filter cliff at s_c ~ 0.83/M for graph degree M (corpus-size independent). Criticality exists only under a constrained budget B < sqrt(k n). Under pre-registered decision rules we confirm, on synthetic sweeps and real SIFT1M, that regret concentrates ~290x at the boundary and that the regret curves obey a finite-size scaling collapse onto one universal wedge across two decades of corpus size. A real approximate index does not mis-locate the boundary, but a biased cost model opens a persistent miscalibration band that estimation-error robustness cannot fix. The contribution is a characterization, not a new index. Code and the full pre-registration are public.

Madhulatha Mandarapu, Sandeep Kunkunuru

VaidhyaMegha Private Limited, India

Regret Minimization Dense Retrieval Approximate Nearest Neighbor Search

Jun 9, 2026cs.LG

Bellman-sufficient Information Complexity

We introduce Bellman-sufficient information complexity for minimax analysis of sequential decision problems. A Bellman-sufficient state retains enough of the history to close the controlled recursion, while an index

Y=χ(Ω)

specifies the decision-relevant information being charged. The upper bound is a log-penalized Bellman program; the lower bound is a Bellman--Fano comparison along an algorithm-dependent reference trajectory. If the two values match at a common localization scale and the stated admissibility, calibration, and growth conditions hold, they form an information-risk sandwich. UCB, E2D, and AMS/EBO control or relax the upper Bellman bracket in different ways. For the main application, we give a negative answer to a widely studied form of the GP--UCB minimax-optimality question. For every

0<α<1/4

, we construct one bounded continuous kernel whose minimax regret is

Θ(T^{1-α})

along an infinite sequence of horizons, while two globally calibrated GP--UCB rules incur linear regret under one fixed truth. An epochwise finite-marginal action-index AIR Bellman policy, implemented through robust AIR/AMS/EBO control, attains the minimax order. The construction separates realized information from the cost of uniform optimism: many low-value directions inflate the exploration multiplier and change the trajectory. Through the canonical RKHS feature map, it also yields a finite-horizon polynomial minimax separation for the specified maximal-information-calibrated LinUCB rule. A reproducible experiment illustrates the mechanism.

Yunbei Xu

National University of Singapore

Multi-Armed Bandits Minimax Regret Regret Minimization UCB Algorithms Information-Theoretic Lower Bounds

Jun 9, 2026cs.MA

Phi-Actor-Critic: Steering General-Sum Games to Pareto-Efficient Correlated Equilibria

Real-world multi-agent systems, from traffic coordination to resource allocation, are often modeled as general-sum games where individual incentives conflict with collective welfare. In these settings, the central challenge is not merely finding an equilibrium, but selecting socially desirable outcomes among many suboptimal Nash equilibria. Standard deep multi-agent reinforcement learning (MARL) methods struggle with this problem, as value-decomposition approaches are constrained by monotonicity assumptions and policy-gradient methods often converge to stable but socially inefficient equilibria. To address this limitation, we propose

Φ

-Actor-Critic (

Φ

-AC), a framework that leverages swap regret minimization to steer learning toward high-welfare correlated equilibria (CE). To make counterfactual regret estimation tractable in deep MARL,

Φ

-AC employs a centralized attention critic that predicts vector-valued regrets in a single forward pass, avoiding computationally expensive counterfactual simulations. We further introduce a Lagrangian-based equilibrium selection mechanism that optimizes social welfare while enforcing stability through regret constraints. Experiments on matrix games, Multi-Agent Particle Environments (MPE), and the Melting Pot Harvest scenario demonstrate that

Φ

-AC learns efficient and stable coordination strategies across diverse mixed-motive settings while maintaining high collective return and competitive fairness.

Wongyu Lee, Francesco Lelli, Omran Ayoub +1

Politecnico di Milano · Tilburg University · University of Applied Sciences and Arts of Southern Switzerland

Multi-Agent Coordination Regret Minimization Actor-Critic Methods Cooperative MARL Multi-Agent Reinforcement Learning

Jun 8, 2026cs.LG

Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret

Contextual queueing bandits provide a framework for learning to schedule heterogeneous jobs under unknown context-dependent service rates. Under stochastic contexts, existing algorithms achieve

\widetilde{\mathcal{O}}(T^{-1/4})

queue length regret, defined as the expected difference between the learner's and oracle's queue lengths at horizon

T

. In this paper, we improve this rate to

\widetilde{\mathcal{O}}(T^{-1/2})

. The key observation is that random exploration is needed only up to a carefully chosen cutoff round, rather than throughout the entire horizon. We propose CQB-

η

-2, a three-phase algorithm: (i) pure random exploration to construct an initial estimator, (ii)

η

-random exploration combined with a UCB rule to continue learning while maintaining negative drift, and (iii) pure UCB after the exploration cutoff. Our proof decomposes the queue length regret at the cutoff round. Before the cutoff, negative drift suppresses queue length differences caused by suboptimal choices. After the cutoff, the first two phases provide sufficient random exploration samples, ensuring that UCB decisions incur small departure-rate gaps. Combining these two bounds yields queue length regret of order

\widetilde{\mathcal{O}}(T^{-1/2})

. We further prove a minimax lower bound of order

Ω(T^{-1/2})

. The proof constructs two hard instances that are statistically indistinguishable up to the final service decision, and uses a queue-specific coupling argument to convert the resulting testing error into queue length regret. Together, our upper and lower bounds characterize the minimax dependence on the horizon

T

up to logarithmic factors.

Seoungbin Bae, Dabeen Lee

Department of Industrial & Systems Engineering, KAIST · Department of Mathematical Sciences, Seoul National University

Exploration-Exploitation Tradeoff Regret Minimization Contextual Bandits UCB Algorithms

Jun 4, 2026cs.LG

Regret Minimization with Adaptive Opponents in Repeated Games

In this paper, we study regret minimization in repeated games with \emph{adaptive} opponents who can respond based on histories of play. The standard metric of \emph{external regret} in online learning is known to fail to capture such adaptivity. To account for players' counterfactual reasoning, we introduce {\tt Repeated Policy Regret (RP-Regret)}, a game-theoretic metric that measures the difference between the \emph{realized} and the \emph{best-in-hindsight} accumulated utility when all players can \emph{respond} to the history of play. Compared to existing regret notions in this setting, ours is native to repeated game playing, enabling stronger comparators and opponents with fewer constraints, while maintaining the possibility of finding better equilibria when all players minimize it. We first identify necessary conditions for obtaining {\tt RP-Regret} sublinear in time, on the variation of the player's comparator strategies in the regret definition and on the memories of both the comparator and opponents' strategies. We then study additional conditions and provable algorithms to minimize {\tt RP-Regret}, which is by definition \emph{non-convex} in the strategy space. To address this challenge, we propose three algorithms: (i) one based on an optimization oracle, as assumed in some prior work in online non-convex learning; (ii) one that minimizes a convex and \emph{linearized} surrogate of {\tt RP-Regret} at each iteration; (iii) one that directly minimizes {\tt RP-Regret} when opponents change strategies slowly. Furthermore, when all players can run algorithms to minimize the {\tt RP-Regret} (or its linearized variant), certain subgame perfect equilibria of the repeated game can be learned. We also provide experiments showing that minimizing our regret notions can lead to more cooperative solutions with higher utility in games such as Stag-Hunt.

Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu +1

Massachusetts Institute of Technology · OpenAI · University of Maryland, College Park

Game-Playing Agents Game Theory Repeated Games Regret Minimization

Jun 3, 2026cs.LG

Mean-based algorithms: A lower bound and regret

Mean-based algorithms are online learning algorithms that assign low probability to actions with low average rewards. Recent research shows that they converge to serially undominated actions, which serve as approximations to Nash equilibria in economic games. However, empirical studies indicate that mean-based algorithms converge more slowly in bandit-feedback settings than established no-regret alternatives. This work investigates mean-based algorithms under unknown horizons and bandit feedback. In this setting, we provide the first lower bound on the algorithm-defining sequence

γ_t

, establishing a fundamental limit on the learning speed of such algorithms. In multi-armed bandit problems, this result constrains the rate at which any algorithm can reliably identify low-reward actions while acting according to this knowledge. We also propose two mean-based algorithms: one generalizes

ε

-greedy, and the other extends mean-based Exp3 to unknown horizons. Our experiments show that mean-based algorithms, although slightly slower, can perform competitively with other bandit-feedback algorithms. We further study the relationship to regret. Depending on the choice of

γ_t

, the intersection with no-regret algorithms is non-trivial, and we show that some algorithms are both mean-based and no-regret.

Julius Durmann, Amelie Kleber

Technical University of Munich

Multi-Armed Bandits Regret Minimization Statistical Learning Theory

Jun 3, 2026cs.LG

Streaming Knowledge Compilation: Proactive Materiality-Scored Pinning for Time-Evolving LLM Wikis

LLM wiki systems compile knowledge into pre-filled KV caches for efficient inference, but assume a static corpus -- an assumption that fails whenever the underlying information landscape evolves. We formalize Streaming Knowledge Compilation: given a document stream, a fixed token budget, and future queries unknown at ingestion time, maintain a compiled wiki that minimizes cumulative regret against an offline oracle with perfect foresight. The enabling insight is a materiality signal

φ_t(k,n)\in[0,1]

that scores document importance for entity

k

at time

t

, acting as a query-relevance surrogate for proactive pinning before queries arrive; we prove an

O(\sqrt{T\log K})

regret bound where

\varepsilon=\mathbb{E}[|φ_t-\hatφ_t|]

is the only domain-specific quantity. We instantiate in two domains: finance, where

φ_t

is abnormal stock volatility predicted by frozen Llama 3.1 8B classification head (AUROC = 0.728 on 76K articles, strict temporal split;

1.49\times

higher realized forward volatility for predicted-material articles); and Wikipedia, where

φ_t

is the Abnormal Edit Ratio (AER), a cross-sectionally normalized edit velocity -- showing the same algorithm generalizes beyond the finance domain. End-to-end QA evaluation on 173 matched pairs (finance) and 119 (Wikipedia) reveals a pervasive LLM-as-judge confound on post-training knowledge, establishing that regret analysis -- not absolute QA scores -- is the reliable evaluation metric for compiled knowledge systems. Finance cumulative regret converges to -20.0 (-0.12/step); Wikipedia to +16.0 (+0.13/step), with the positive sign confirming that Wikipedia edit content is genuinely post-training -- richer context consistently improves scores (No Wiki 3.80 vs. Oracle 4.74) -- and eliminates this confound. The

O(\sqrt{T\log K})

guarantee applies to any domain where knowledge gaps can be predicted from streaming signals.

Juan M. Huerta

Zinnia Tech Solutions 600 Steamboat Road Greenwich, CT 06830, USA

Memory-Augmented Language Models Knowledge Augmentation for Language Models KV Caching Regret Minimization

Jun 2, 2026cs.LG

Two-Action Apple Tasting with Switching Costs

We study the two-action apple-tasting problem with switching costs against an oblivious adversary. In an equivalent normalized formulation, at each round the learner chooses between a revealing action and a blind action: the revealing action gives reward

0

and reveals the hidden value

x_t\in[-1,1]

of the blind action; the blind action gives reward

x_t

but reveals nothing. The learner pays one unit whenever they switches actions, and regret is measured against the best fixed action in hindsight. General feedback-graph algorithms with switching costs give

\widetilde O(T^{2/3})

regret guarantees for this problem. The two-action apple-tasting graph was the natural candidate for the missing

Ω(T^{2/3})

obstruction in the switching-cost classification: such a lower bound would have transferred to a large family of still-unclassified feedback graphs. We prove that this obstruction is not there: the oblivious minimax expected regret for this problem satisfies

\frac{1}{2\sqrt3}\cdot\sqrt T \le R_T^\star \le 2\sqrt{3}\cdot \sqrt{T}.

Tommaso Cesari, Roberto Colomboni

School of Electrical Engineering and Computer Science University of Ottawa Ottawa, Canada · School of Mathematics University of Bristol Bristol, United Kingdom

Multi-Armed Bandits Minimax Regret Regret Minimization Adversarial Bandits

Jun 1, 2026math.OC

A No-Regret Framework for Adaptive Incentive Design

Incentive design studies how a central authority can influence strategic agents through payments, subsidies, or taxes, so that individual objectives align with collective welfare. This paper introduces a No-Regret Adaptive Incentive Design (RAID) framework for nonlinear games with continuous action spaces and private agent costs. In this framework, the authority (planner) designs incentives that regulate the Nash equilibrium toward a socially optimal action profile, while simultaneously learning agents' unknown preferences from repeated strategic responses. We formulate the RAID problem and construct a least-squares estimator whose strong consistency requires only diminishing excitation. Leveraging this weak excitation requirement, we propose a switching incentive policy that alternates between probing (exploration) and estimate-based (exploitation) incentives. The resulting policy achieves an

O(t^{-0.5})

parameter estimation rate and accumulates

O(t^{0.5}\log t)

squared social-cost regret, almost surely. We further extend the framework to an endogenous-noise response model, where standard least-squares estimation is biased due to an error-in-variables correlation between the noise and agent responses. We utilize a repeated-sampling estimator and corresponding switching policy that retain the same almost-sure convergence and regret rates. Numerical experiments validate the effectiveness and predicted convergence rates of the method.

Georgios Vasileiou, Lantian Zhang, Silun Zhang

Department of Mathematics, KTH Royal Institute of Technology, Stockholm, 10044, Sweden.

Mechanism Design Game Theory Regret Minimization

Jun 1, 2026cs.LG

Tree-Guided Identify-Then-Exploit: A Unified Framework of Best Arm Identification and Regret Minimization for Dueling Bandits

We study

N

-armed stochastic dueling bandits under the Condorcet-winner assumption, where three widely adopted objectives are considered: best-arm identification (BAI), weak regret, and strong regret. We propose Tree-Guided Identify-Then-Exploit (TG-ITE), the first unified framework to tackle all these objectives to our knowledge. Without requiring stronger assumptions, we propose a shared tree-guided identification approach to find a high-confidence incumbent within

O(N)

comparisons. We further propose varied exploitation strategies to utilize this warm-start stage to optimize the specific objectives at hand. This methodology enables our approach to (1) achieve

O(N)

sample complexity in BAI without commonly adopted stronger assumptions; (2) build the first winner-stays-style algorithm to achieve

O(N)

weak regret; (3) enjoy the same

O(N \log T)

guarantee as specialized strong-regret approaches; (4) realize the joint optimization of BAI and weak regret with

O(N)

guarantees for both, eliminating the sub-optimal gap of

O(\log N)

in the existing approach. Our results provide evidence that the trade-off between BAI and regret minimization is relatively benign in dueling bandits.

Pu Wang, Yao-Xiang Ding

State Key Lab of CAD&CG, Zhejiang University

Multi-Armed Bandits Best-Arm Identification Regret Minimization

May 31, 2026cs.LG

Towards Regret Guarantees for One-Step Lookahead Bayesian Optimization

This paper studies theoretical guarantees of a one-step lookahead Bayesian optimization (BO) method. Although the empirical effectiveness of one-step lookahead BO methods, such as entropy search, has been studied extensively, they often rely on computationally intractable approximations, and their regret guarantees remain underdeveloped. Thus, this paper analyzes a one-step lookahead BO method, which we refer to as optimal-point variance reduction (OVR), that requires only posterior sampling and Monte Carlo approximations. We obtain a uniform Monte Carlo estimation error bound over an input domain in an acquisition function computation. Furthermore, we show that the regularized OVR, with a slight modification to facilitate exploration, achieves a vanishing Bayesian expected simple regret upper bound. Finally, we validate the performance of OVR and regularized OVR through numerical experiments.

Shion Takeno

Nagoya University

Bayesian Optimization Regret Minimization Variance Reduction

May 27, 2026cs.AI

TRACER: Turn-level Regret Matching with Inner Reinforcement Credit for Cooperative Multi-LLM Reasoning

Large language models increasingly rely on either reinforcement learning or multi-agent prompting to improve reasoning, yet these two paradigms remain difficult to combine. Directly applying single-agent reinforcement learning to multi-turn multi-agent systems faces following dilemmas: i) Sparse rewards, role-level free-riding and excessive training overhead. ii) Agents only imitate to collaborate. iii) Fixed collaboration protocol falls into oscillating local optimum. We introduce TRACER, a turn-level reinforcement framework for cooperative multi-LLM reasoning. TRACER separates collaborative decision making into a controller-regret layer, where controllers learn whether the agents should speak or skip the current round through regret matching, and a generation-credit layer, which optimizes proposer and reviewer utterances with role-specific GSPO rewards. This design i) assigns credit at the level of both action modes and generated utterances, thus avoiding free-riding and sparse rewards. We only expand the choices made by the controllers, thus greatly reducing computational cost of training. Moreover, ii) agents acquire collaborative capability as they learn when to utter and what to speak. Finally, iii) by designing binary actions ingeniously, we extend classical game theory established for finite action spaces to deep learning, thus achieving mathematically rigorous convergence. We train all local RL-style methods on the GSM8K training split and evaluate on held-out GSM8K, MATH500, and GPQA-Diamond to measure in-domain accuracy, cross-benchmark generalization, inference cost, and correction-preservation behavior. The resulting framework provides a compact and reproducible testbed for studying learned collaboration policies beyond fixed debate, voting, or aggregation protocols. Code is available at https://github.com/Shark-Forest/TRACER.

Chusen Li, Zhou Liu, Shuigeng Zhou +1

1Fudan University · 2Zhongguancun Academy · 3Academy for Advanced Interdisciplinary Studies, Peking University

Regret Minimization Multi-Agent Reasoning Cooperative MARL RL for LLM Agents Multi-Agent Reinforcement Learning

May 25, 2026cs.LG

On the Benefits of Free Exploration for Regret Minimization in Multi-Armed Bandits

We study a stochastic multi-armed bandit problem where an agent is granted a free exploration budget before regret accumulates, a setting not captured by the classic regret minimization or pure exploration paradigms. The goal is to design an adaptive policy that strategically explores the bandit instance in the initial free exploration phase and minimizes the cumulative regret in the subsequent phase. We formalize this regret minimization with free exploration problem and identify an interesting regime where the free exploration budget scales logarithmically with the time horizon. To quantify the amount of regret saved with high probability as a result of the availability of the free exploration phase, we introduce a novel set of policies known as

(α,β)

-probably saving policies. We propose a two-phase, probably saving algorithm, UFE-KLUCB-H, which consists of a principled free exploration policy, UFE, and a history-aware regret minimization policy KLUCB-H. Instance-dependent upper bounds on UFE-KLUCB-H are derived, showing that UFE-KLUCB-H accumulates strictly less regret than policies that do not have access to a free exploration phase. Complementarily, we derive instance-dependent lower bounds based on novel multi-instance perturbation arguments tailored to the free-exploration setting, demonstrating the near-optimality of UFE-KLUCB-H for two-valued bandits. Our upper and lower bounds reveal sharp phase transitions in the accumulated regret depending on the amount of available free exploration. Simulations are conducted to demonstrate that forced exploration and adaptivity in the algorithm lead to greater regret savings.

Yunlong Hou, Zixin Zhong, Vincent Y. F. Tan

Department of Mathematics, National University of Singapore · Data Science and Analytics Thrust, Hong Kong University of Science and Technology (Guangzhou) · Department of Electrical and Computer Engineering, National University of Singapore

Multi-Armed Bandits Regret Minimization

May 20, 2026cs.LG

Regret Analysis of Retry-Based Bandits

We provide the first regret analysis of ReMax in stochastic multi-armed bandits. Originally introduced for reinforcement learning, ReMax is motivated by the role of exploration when multiple attempts are allowed, and is closely related to retry-based objectives such as pass@

k

and max@

k

, which value the best outcome across those attempts. Given a posterior over arm values, ReMax chooses a sampling distribution that maximizes the posterior expected maximum arm value over

M

virtual draws. For Gaussian rewards with

K

arms and any fixed integer

M\ge2

, we characterize optimal sampling distributions through an expected-improvement balance condition and prove an

O(\sqrt{(M-1)KT\log T})

finite-time bound on expected regret. Our analysis separates a logarithmic contribution from rounds without optimal-arm underestimation and a recovery term that dominates the bound. For every fixed instance with pairwise distinct arm means, we further prove an asymptotic logarithmic regret upper bound whose coefficient is at most

M-1

times the optimal coefficient by Lai and Robbins. When

M=2

, this bound implies the asymptotic optimality of ReMax. Gaussian-bandit experiments show that ReMax performs competitively with Thompson sampling and KL-UCB. They also reveal a trade-off: larger

M

reduces regret incurred during optimal-arm underestimation, but this reduction does not necessarily translate into lower total regret. Controlled recovery experiments show that separating suboptimal means accelerates recovery, while severe underestimation of the optimal arm can lead to long delays before it is sampled again.

Bingkui Tong, Junpei Komiyama, Soichiro Nishimori +1

Mohamed bin Zayed University of Artificial Intelligence · RIKEN AIP · The University of Tokyo

Multi-Armed Bandits Regret Minimization

May 19, 2026cs.LG

Active Context Selection Improves Simple Regret in Contextual Bandits

We study the contextual multi-armed bandit problem with a finite context space (a.k.a. subpopulations), where the learner recommends a best action for each context and is evaluated by context-weighted simple regret. Our guarantees are worst-case over the reward distributions, while remaining instance-dependent with respect to the context distribution vector

p

. Akin to experimental design problems where the population of interest is fixed but the sampled subpopulation can be controlled, we allow the learner to actively choose which context to sample from. For a known

p

, we characterize tight regret rates: passive sampling where contexts are randomly revealed achieves regret of order

\sqrt{n/T \, \lVert p \rVert_{1/2}}

, whereas active sampling with allocation

q_j \propto p_j^{2/3}

achieves the tight rate

\sqrt{n/T} \, \lVert p \rVert_{2/3}

. The resulting improvement can be as large as

Θ(k^{1/4})

, where

k

is the number of contexts. We further extend the analysis to budgeted active sampling, characterize the corresponding tight rate, and identify when a limited active budget suffices to recover the fully active rate. When

p

is unknown, we propose the Explore-Explore-Then-Commit (EETC) algorithm, which optimally balances estimating the context distribution and the time to switch to active allocation, such that for large horizons, it matches the known-

p

active rate up to constants. Experiments on synthetic and real-world data support our theoretical findings.

Mohammad Shahverdikondori, Jalal Etesami, Negar Kiyavash

College of Management of Technology, EPFL · Department of Computer Science, TU Munich

Multi-Armed Bandits Best-Arm Identification Adaptive Sampling Regret Minimization Contextual Bandits

May 19, 2026cs.GT

Real-Time Parallel Counterfactual Regret Minimization

Counterfactual Regret Minimization (CFR) is the dominant algorithmic family for solving large imperfect-information games, underpinning breakthroughs such as Libratus and Pluribus in No-Limit Texas Hold'em poker. In real-time game-playing systems, the solver must compute a near-equilibrium strategy within a strict time budget of only a few seconds per decision, and the number of CFR iterations completed in this window directly determines play strength. We present \textbf{Parallel CFR}, the first parallelization framework for real-time depth-limited CFR solving that seamlessly integrates pruning, abstraction, and advanced CFR variants. We decompose each CFR iteration into a pipeline of seven stages and identify two orthogonal dimensions of parallelism: \emph{by information set} and \emph{by tree node}. Leaf node evaluation is offloaded to GPUs via batched neural network inference, creating a heterogeneous CPU--GPU pipeline. Experiments on Heads-Up No-Limit Texas Hold'em demonstrate that Parallel CFR achieves

3.3

--

3.4\times

speedup over the single-threaded baseline on postflop streets, with per-iteration time of

{\sim}47

--

54

~ms on a depth-limited game tree with over

1

billion histories. All experiments run on a single desktop-class device (NVIDIA DGX Spark), enabling hundreds of CFR iterations within a typical real-time decision budget without requiring datacenter-scale infrastructure.

Boning Li, Longbo Huang

IIIS, Tsinghua University

Game-Playing Agents GPU Acceleration Imperfect-Information Games High-Performance Computing Regret Minimization Nash Equilibrium Computation

May 17, 2026cs.LG

Calibeating for general proper losses: A Bregman divergence approach

This work introduces a general framework for calibeating based on regret minimization. As compared to Foster and Hart's seminal calibeating work which had specialized treatments of Brier score (squared loss) and log loss, we consider a large family of proper losses that includes

α

-Tsallis losses (for

α\in [1, 2]

) and Lipschitz losses. Our results for Tsallis losses also hold for an unscaled version of Tsallis loss that recovers log loss. Our analysis is oriented around the Bregman divergence view of a proper loss. Technically, our results for the family of Tsallis losses that we consider are U-calibration results, simultaneously obtaining logarithmic regret for all losses in this family while having a weaker dependence on the dimension compared to previous results. Of potential independent interest, we also show a new regret equality for the regret of Be The Regularized Leader. This regret equality holds for general proper losses and itself is based on two results related to online updating formulas for the generalized variance, the latter being a previously introduced generalization of variance based on Bregman divergences.

Maximilian Fichtl, Cristóbal Guzmán, Nishant A. Mehta

Independent researcher · Institute for Mathematical and Computational Engineering, Faculty of Mathematics and School of Engineering, Pontificia Universidad Católica de Chile · Department of Computer Science, University of Victoria

Functional Bregman Divergences Proper Scoring Rules Regret Minimization

May 14, 2026cs.AI

Parallelizing Counterfactual Regret Minimization

Parallelization has played an instrumental role in the field of artificial intelligence (AI), drastically reducing the time taken to train and evaluate large AI models. In contrast to its impact in the broader field of AI, applying parallelization to computational game solving is relatively unexplored, despite its great potential. In this paper, we parallelize the family of counterfactual regret minimization (CFR) algorithms, which were central to important breakthroughs for solving large imperfect-information games. We present a generalized parallelization framework, reframing CFR as a series of linear algebra operations. Then, existing techniques for parallelizing linear algebra operations can be applied to accelerate CFR. We also describe how our technique can be applied to other tabular members of the CFR family of algorithms, including the state-of-the-art, such as CFR+, discounted CFR, and predictive variants of CFR. Experimentally, we show that our CFR implementation on a GPU is up to four orders of magnitude faster than Google DeepMind OpenSpiel's CFR implementations on a CPU.

Juho Kim, Tuomas Sandholm

Computer Science Department Carnegie Mellon University · Computer Science Department, CMU · Strategic Machine, Inc. +2

GPU Acceleration Imperfect-Information Games Game Theory High-Performance Computing Regret Minimization

May 13, 2026econ.EM

Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization

Regret is the cost of uncertainty in algorithmic decision-making. Quantifying regret typically requires computationally expensive simulation via Sample Average Approximation (SAA), with complexity

\mathcal{O}(Bn^{2}d^{3})

in the number of scenarios

B

, variables

n

, and constraints

d

. % This paper proves that expected regret in any stochastic optimization problem admits the exact decomposition % \begin{equation*} \mathrm{Regret}(c) = \mathrm{Cov}(c,,π^{}(c)) + R(c), \end{equation} % where

c

is the vector of uncertain parameters,

π^{*}(c)

is the optimal decision, and

R(c)

is a residual whose magnitude we bound explicitly under Lipschitz, smooth, and strongly convex conditions. % For linear programs and unconstrained quadratic programs, including the classical Markowitz portfolio problem, we prove

R(c)=0

exactly, so that

\mathrm{Regret}(c) = \mathrm{Cov}(c,π^{*}(c))

holds without approximation. % When historical cost-decision pairs

\{(c_i, π^*(c_i))\}

are available, the covariance can be estimated in

\mathcal{O}(nd^{2})

time, which is orders of magnitude faster than SAA. The estimation is performed by a single pass through the data. % We derive concentration bounds, a central limit theorem, and an asymptotically unbiased residual estimator, and we validate all results on synthetic LP, QP, and integer programming instances and on a rolling-window portfolio experiment using ten years of CRSP equity data.

Irene Aldridge

Stochastic Optimization Regret Minimization

May 13, 2026stat.ML

A Regret Perspective on Online Multiple Testing

Online Multiple Testing (OMT), a fundamental pillar of sequential statistical inference, traditionally evaluates the False Discovery Rate (FDR) and statistical power in isolation, obscuring the highly asymmetric costs of false positives and false negatives in modern automated pipelines. To unify this evaluation, we introduce

\textit{Weighted Regret}

. Under this metric, we prove the

\textit{Duality of Regret Conservation}

: purely deterministic procedures ensuring strict FDR control inevitably incur an

Ω(T)

linear regret penalty, as threshold depletion during signal-sparse cold starts forces massive false negatives. Tailored for exogenous testing streams, we propose Decoupled-OMT (DOMT) as a baseline-agnostic meta-wrapper. By incorporating a history-decoupled, strictly non-negative random perturbation, DOMT rescues purely deterministic baselines from severe threshold depletion. Crucially, it preserves exact asymptotic safety in stationary environments and rigorously bounds finite-sample error inflation during cold-starts. Guaranteeing zero additional false negatives, it yields an order-optimal

Ω(\sqrt{T})

regret reduction in bursty environments, with a derived ``Cold-Start Tax'' characterizing the exact phase transition of algorithmic superiority. Experiments validate that DOMT consistently curtails empirical weighted regret, achieving an order-optimal sublinear mitigation of threshold depletion to navigate the non-stationary Pareto frontier.

Qingyang Hao, Kongchang Zhou, Fang Kong +1

Southern University of Science and Technology

FDR Control Regret Minimization Sequential Hypothesis Testing Multiple Hypothesis Testing Statistical Hypothesis Testing

May 12, 2026cs.GT

Profit Maximization in Bilateral Trade against a Smooth Adversary

Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, who wish to trade a good. We study this problem from the perspective of a profit-maximizing broker within an online learning framework, where the agents' valuations are generated by a smooth adversary. We devise a learning algorithm that guarantees a

\tilde{O}(\sqrt{T})

regret bound, which is tight in the time horizon

T

up to poly-logarithmic factors. This matches the minimax rate for the stochastic i.i.d. case, and is also well separated from the adversarial setting, where sublinear-regret is unattainable. By extending the strong regret guarantees from the i.i.d. case to the smooth adversary, we significantly broaden the scope of settings where such fast rate is achievable, while closing an important gap in the regret landscape of this fundamental economic problem. To overcome the challenges posed by this adversary, we leverage a continuity property of smooth instances and combines this with a hierarchical net-construction of the broker's action space, which is analyzed via algorithmic chaining. We showcase the applicability of these techniques by deriving a similarly tight

\tilde{O}(\sqrt{T})

regret bound for a related mechanism design model: the joint ads problem.

Simone Di Gregorio, Paul Dütting, Federico Fusco +1

Department of Computer, Control and Management Engineering Sapienza University of Rome · Google Research · Department of Computer Science Aarhus University

Mechanism Design Minimax Regret Regret Minimization

May 11, 2026cs.GT

Regret Minimization in Bilateral Trade With Perturbed Markets

We address the problem of maximizing Gain from Trade (GFT) in repeated buyer-seller exchanges subject to global budget balance constraints. While this problem is well-understood in purely adversarial and stochastic settings, these environments exhibit a sharp dichotomy: adversarial environments allow for no-regret learning against the best fixed-price mechanism, whereas stochastic environments allow for no-regret learning against the best distribution over prices that is budget balanced in expectation. This gap is significant, as policies balanced in expectation can increase the GFT by a multiplicative factor of two. In this work, we bridge these extremes by studying perturbed markets, where an underlying stochastic distribution is subject to an adversarial corruption

C

. We design an algorithm that adaptively scales with the level of corruption, achieving an

\tilde{\mathcal{O}}(T^{3/4}) + \mathcal{O}(C\log(T))

regret bound against the best budget-balanced distribution over prices. Simultaneously, our algorithm maintains the worst-case

\tilde{\mathcal{O}}(T^{3/4})

regret bound relative to a per-round budget-balanced baseline, ensuring optimality even in fully adversarial environments.

Anna Lunghi, Matteo Castiglioni, Alberto Marchesi

Politecnico di Milano

Mechanism Design Automated Negotiation Regret Minimization

May 10, 2026cs.IT

Learning from Acceptance: Cumulative Regret in the Game of Coding

Classical coding-theoretic guarantees often rely on trust assumptions, such as requiring sufficiently many honest nodes compared with adversarial ones. These assumptions are difficult to enforce in open decentralized systems where participants are not centrally certified. At the same time, such environments often contain incentive mechanisms: participants may be rewarded only when their submitted data are accepted and the system remains functional. This changes the role of an adversary. Rather than acting as a pure saboteur, a strategic adversary may submit data that are consistent enough to be accepted while still degrading the quality of the final estimate. The game-of-coding framework models this strategic interaction between a data collector (DC) and an adversary. Existing works on the game of coding mostly consider the complete-information case, where the DC knows how the adversary trades off acceptance and estimation error. In this paper, we study an incomplete-information version of the game of coding in which the DC, acting as a Stackelberg leader, does not know the adversary's utility trade-off and must learn through repeated interaction. Prior work on the unknown-adversary setting considered an explore-then-commit objective, where only the final selected acceptance rule is evaluated. In contrast, we study the full learning trajectory: every acceptance rule used during the algorithm is executed and contributes to performance. We propose an algorithm that refines its search around promising acceptance rules, prove that it achieves sublinear cumulative regret, and evaluate its performance through numerical experiments.

Hanzaleh Akbari Nodehi, Parsa Moradi, Mohammad Ali Maddah-Ali

University of Minnesota, Twin Cities, Minneapolis, MN, USA

Imperfect-Information Games Game Theory Stackelberg Games Regret Minimization