Regret Minimization

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

Oct 7, 2026cs.LG

Expected Sample Complexity in Multi-Armed Bandits

Sample complexity is a widely used metric in sequential decision-making problems, defined as the number of suboptimal decisions during the interaction between the agent and an environment. We study the sample complexity of stochastic multi-armed bandit problems and introduce the expected sample complexity performance measure, analyzing it in a novel framework called approximately correct in expectation (ACE). We show that ACE guarantees imply almost sure convergence to the optimal expected reward, in contrast to high-probability guarantees found in other frameworks, and also show how to convert ACE guarantees into explicit expected regret bounds. We further show that, in contrast to existing measures, deterministic algorithms cannot obtain favorable ACE bounds, and analyze stochastic algorithms in two settings: when the allowed suboptimality level

ε

is known to the algorithm and when it is unknown. In the former, we devise an explore-then-

ε

-greedy algorithm, and in the latter, we analyze the expected sample complexity of Thompson sampling. Finally, we establish nearly matching lower bounds for both settings, showing that the algorithms are tight in

ε

and proving a performance separation between the two regimes.

Nadav Sukenik, Nadav Merlis

Technion – Institute of Technology

Multi-Armed Bandits Regret Minimization Thompson Sampling

Ask PDF

Oct 1, 2026cs.LG

The Curvature of Regret in Contextual Linear Optimization

Decision-focused learning for linear optimization is complicated by the discontinuity of the optimizer, where small cost errors may leave the decision unchanged or move it to a different vertex. We show that this non-smooth pointwise behavior becomes locally quadratic after averaging over the data distribution, and we derive the curvature in closed form, specifically, a matrix-valued measure supported on the walls of the normal fan. This measure depends only on the feasible set, with the data distribution entering only as a weight. We then offer a tractable approximation for this curvature, computable with just one projection to the feasible set. We prove that the approximation weakly converges to the true population curvature. We offer one application of our findings, a decision-aware scenario generation method for expected-cost linear optimization. Our experiments test the quadratic and weak convergence laws and show a 30.8% regret improvement over uniform allocation on battery arbitrage.

Konstantinos Ziliaskopoulos, Alexander Vinel, Alice E. Smith

Auburn University Auburn, AL, USA · University of Alabama Tuscaloosa, AL, USA

Decision-Focused Learning Regret Minimization Linear Programming

Ask PDF

Oct 1, 2026cs.LG

Minimax Optimal Regret for Causal Logistic Bandits with Counterfactual Fairness

We study causal logistic bandits with counterfactual fairness constraints. The causal structure is given through known factual and counterfactual feature maps that share an unknown logistic reward parameter, but the learner observes only factual rewards. Consequently, the directions determining counterfactual feasibility need not be identifiable from the available feedback. The closest prior analyses either omit a coverage condition or impose a comparatively strong one, and do not establish matching lower bounds. We first show that some coverage condition is necessary: without a coverage-type restriction, factually indistinguishable environments with different optimal fair actions force

Ω(T)

expected joint loss. Under a weaker full-rank condition on the factual covariance pooled across actions, we identify a target-specific information scale

V_\star

that measures the difficulty of estimating rewards and counterfactual effects from factual feedback. We construct worst-case families satisfying this condition on which every policy incurs expected joint loss

Ω\left(\left[V_\star\min\{\log K,d\}\right]^{1/3}T^{2/3}\right)

. We also give an explore--then--exploit procedure tuned using

V_\star

and an adaptive algorithm that does not require its value. Both algorithms achieve

\max\{R_T,V_T\}=\widetilde{O}\left(\left[V_\star\min\{\log K,d\}\right]^{1/3}T^{2/3}+κd/σ_0^2\right)

, where

R_T

is regret relative to the best fair action and

V_T

denotes the cumulative stage-wise positive violations. Thus the upper and lower bounds match in their leading dependence on

T

V_\star

, and

\min\{\log K,d\}

, up to logarithmic factors.

Junhyuk Huh, Seoungbin Bae, Dabeen Lee

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

Multi-Armed Bandits Minimax Regret Algorithmic Fairness Counterfactual Fairness Regret Minimization

Ask PDF

Sep 30, 2026cs.LG

Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization

We study adversarial online maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed sets. A learner commits each action before observing its objective and competes with the best fixed action in hindsight. We prove a comparator-uniform first-order inequality that gives coefficient

4/9

, improving the online

0.401

benchmark, with one gradient query and one projection per round and

O(\sqrt T)

expected approximate regret. If

ζ{\bf 1} \in K\subseteq[0,1]^d

, the coefficient improves to

\underlineα(ζ)=\tfrac12-(1-2ζ)_+^2/[2(3-2ζ)^2]

. The proof is a direct ordered-coordinate argument with an objective-independent rational action. Conversely, a three-group symmetry-gap construction yields an offline oracle upper bound

β_*=0.470438681380894\ldots

ζ=0

, even with exact value and full-gradient responses. A parameterized extension and exact finite-instance bounds define an upper function for every

ζ

. The lower and upper bounds match at

1/2

for

ζ\ge1/2

, and show that the optimal deficit from

1/2

Θ((1/2-ζ)^2)

ζ\uparrow1/2

. For coefficient-revealed polynomials we obtain

1/2

for quadratics and a geometry-dependent cubic coefficient starting at

8/17

, including

0.49

ζ=1/5

. A constant objective sequence yields an offline

(4/9-\varepsilon)

approximation with polynomially many first-order queries on the cube and projections, without requiring a supplied positive lower bound on the optimum. We also give nonanticipating adaptive-adversary and value-feedback guarantees, including

O(T^{3/4})

regret with one noisy value per round.

Vaneet Aggarwal

Purdue University

Submodular Optimization Regret Minimization

Ask PDF

Sep 29, 2026stat.ML

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

We study multi-armed bandits (MAB) with multiple optimal arms, motivated by the fact that many practical decision making problems admit multiple correct answers. For

K

-armed bandits with

A

optimal arms, we first provide a sharper analysis of previous sub-sampling algorithms (De Heide et al., 2021; Zhu and Nowak, 2020), establishing a

\tilde{O}\Big(\frac{K-A}{\sqrt{KA}}\sqrt{T} \Big)

minimax regret, where

T

is the total number of interactions and

\tilde O(\cdot)

drops all constant and logarithmic factors, improving the previous

\tilde{O}(\sqrt{KT/A})

regret. We then provide a matching lower bound up to logarithmic factors, indicating that our established rate is nearly minimax-optimal. We further show that the knowledge of

A

up to

\tilde{O}(1)

factors is necessary to achieve near-optimal regret, as near-optimal algorithms for one number of optimal arms must incur substantially larger regret than optimal regret for a smaller number. Overall, our results provide a comprehensive minimax characterization of

K

-armed bandits with

A

over the entire range of

1 \leq A \leq K-1

Kaixuan Ji, Qiwei Di, Qingyue Zhao +2

Department of Computer Science, University of California, Los Angeles, CA 90095, USA

Multi-Armed Bandits Minimax Regret Regret Minimization

Ask PDF

Sep 24, 2026math.OC

Cost-Sensitive Online Window Size Selection for Portfolio Management

This paper investigates cost-sensitive online window size selection for portfolio management under changing market conditions. Specifically, we propose a two-level framework that constructs portfolios using candidate window sizes and dynamically aggregates them through online learning. By treating candidate window sizes as ``experts,'' we dynamically update their aggregation weights using turnover-inclusive losses. Moreover, we derive finite-horizon cost-sensitive tracking-regret bounds that account for turnover of the aggregated portfolio, with static regret as a special case. Under bounded losses and cost rates, suitably tuned Fixed Share achieves asymptotically no tracking regret for sublinear switching budgets, with Hedge covering the static case.

Yi-Chen Liu, Chung-Han Hsieh

Interdisciplinary Program of Management and Technology, National Tsing Hua University · Department of Quantitative Finance, National Tsing Hua University, Taiwan.

Cost-Sensitive Learning Regret Minimization Portfolio Optimization

Ask PDF

Sep 23, 2026stat.ML

Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant

Prediction with expert advice is a fundamental problem in online learning. When the time horizon

T

is known in advance, the minimax cumulative regret over

n

experts is asymptotically

\sqrt{\frac{T \ln n}{2}}

. This is achieved by the Multiplicative Weights Update algorithm with a learning rate tuned to

T

, and is known to be tight. If instead the regret bound is required to hold simultaneously at every time

t

, the best known guarantee has been

\sqrt{t \ln n}

---a factor of

\sqrt{2}

worse---and it has remained unknown whether this factor of

\sqrt{2}

is necessary. We show that it is not. We give an algorithm, requiring no knowledge of the horizon, whose cumulative regret satisfies

R_t \le \bigl(1 + O(\sqrt{\ln \ln n / \ln n})\bigr)\sqrt{t \ln n / 2}

simultaneously for every

t \ge 1

Yang Cai, Vineet Gupta, Yanchen Jiang +4

Google Research · Yale University · Google DeepMind

Minimax Regret Regret Minimization

Ask PDF

Sep 17, 2026cs.LG

From Switching to Dynamic Regret: A Simple Reduction via Unbiased Random Sequences

In non-stationary online learning, dynamic regret has attracted increasing attention as a measure of how well an online learner performs against a time-varying comparator sequence. Despite considerable advances, attaining optimal bounds for strongly convex and exp-concave losses often involves intricate analysis. In this paper, we present a \textit{simple} framework that reduces dynamic regret minimization to switching regret minimization. As a result, we can derive dynamic regret bounds by using off-the-shelf algorithms with switching regret guarantees. The key idea of our reduction is to construct, for \textit{any} comparator sequence, an auxiliary random sequence that is unbiased at each round, with the controlled variance and a manageable number of switches. Combining this construction with suitable surrogate losses, we can decompose dynamic regret into the expected switching regret against the random sequence and its controlled variance. Theoretically, for strongly convex and exp-concave losses, we establish the

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

dynamic regret bounds, where

T

denotes the time horizon and

P_T

denotes the path-length of the comparator sequence. Moreover, for general convex losses, the same reduction also recovers the

O(\sqrt{T(1+P_T)})

dynamic regret bound. Notably, all our findings match the minimax optimal results for these three types of losses, highlighting the versatility of our proposed framework.

Yibo Wang, Wenhao Yang, Sifan Yang +3

State Key Laboratory for Novel Software Technology, Nanjing University · School of Artificial Intelligence, Nanjing University · School of Software Technology, Zhejiang University

Online Convex Optimization Dynamic Regret Minimization Regret Minimization

Ask PDF

Sep 15, 2026cs.GT

Constant Swap Regret in General-Sum Games via Optimistic Transition Matrices

We give deterministic and uncoupled learning dynamics for finite multiplayer general-sum games under full-information feedback that achieve constant individual swap regret, independent of the horizon

T

. With

n

players and at most

m

actions each, the individual swap regret of every player is

O(\sqrt{n} m \log m \log^{5/2}(nm))

at every finite horizon. Each player predicts the deviation gains, then uses these predictions to update a row-stochastic transition matrix, and plays its stationary distribution. The proof combines a potential argument exploiting stationarity with a two-scale higher-order prediction analysis, using rooted-tree representations to handle the nonlinear dependence of deviation gains on the stationary distributions. An adversarially robust variant, obtained through a generic common-prefix switching wrapper, preserves the self-play bound up to a universal constant and guarantees individual swap regret at most

7\sqrt{m T \log m}

in the adversarial setting.

Tung Mai

Adobe Research

Game Theory Decentralized Learning Regret Minimization

Ask PDF

Sep 12, 2026cs.DC

GPU-CFR: 80x Faster Counterfactual Regret Minimization by Compiling the Game to Static Dataflow and CUDA Graph Replay

Counterfactual regret minimization (CFR) is one of the few large numerical workloads that still runs faster on CPUs than on GPUs. Each iteration sweeps a game tree with up to billions of states in millions of small, interdependent gather and scatter steps issued through a generic tree interface. On a GPU every kernel finishes in microseconds, so kernel launches and framework dispatch dominate the run time, and prior GPU implementations have lost to optimized CPU code. We observe that for a fixed game, everything about a CFR iteration except the numerical values is known before the first iteration runs. We propose GPU-CFR, a compiler and runtime built on this observation. It compiles any game once into static dataflow: flat edge and information-set arrays, precomputed indices, and depth-level batched passes fix the entire operation sequence, and only solver state changes between iterations. Static chance folding, depth-level execution blocks, and a dual-lane reach buffer cut the number of framework operations by up to 18.1x. Because shapes, indices, and buffer addresses never change, CUDA Graph Replay records the iteration once and replays it with a single graph launch. On one A100, across an eight-game suite that spans card games, dice games, and board games, GPU-CFR runs 29.8--80.4x faster than the fastest prior GPU CFR on the same accelerator, and 14--258x faster than LiteEFG, one of the fastest open-source CPU implementations, on the four largest games. The compiled representation carries most of that margin: on eight CPU threads with no accelerator it is already 2.2--51.1x faster than the GPU baseline. On the CPU the optimized path reproduces the reference iterates bitwise, and tree construction and graph capture pay for themselves within the first solve. GPU-CFR beats every CPU and GPU baseline on the mid-to-large games of the suite without changing the update rule.

Boning Li, Longbo Huang

Institute for Interdisciplinary Information Sciences, Tsinghua University

GPU Kernel Optimization GPU Acceleration Imperfect-Information Games Regret Minimization

Ask PDF

Sep 11, 2026cs.LG

Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions

Convex Optimization with Nested Evolving Feasible Sets (CONES)} was introduced in \cite{CONESVaze} where the objective function

f

remains fixed but the feasible region evolves over time as a nested sequence

S_1 \supseteq S_2 \supseteq \cdots \supseteq S_T

. The goal of an online algorithm is to simultaneously minimize the regret with respect to hindsight static optimal benchmark and the total movement cost

M_\cA(T)

while ensuring feasibility at all times. CONES is an optimization-oriented generalization of the well-known \emph{nested convex body chasing} (NCBC). In this paper, we extend CONES to allow for loss functions

f_t'

s to also change over time. When all loss functions are convex, we show that the projected proximal algorithm achieves

O(T^{1-\beta}), O(T^\beta)

simultaneous regret and movement cost, respectively, for any

\beta \in [0,1)

, over a time horizon of

T

. We also show that any {\it weakly adaptive} online algorithm with

O(T^\beta)

regret has a movement cost of

\Omega\left(T^{\frac{1-\beta}{2}}\right)

for any

\beta \in [0,1)

. When all loss functions are strongly convex, we show that the projected proximal algorithm simultaneously achieves

O(1)

regret and a movement cost of

O(\log T)

. To complement this, we show that any online algorithm with sublinear {\it anytime} regret has a movement cost of

\Omega\left(\log T\right)

Rahul Vaze

Online Convex Optimization Regret Minimization

Ask PDF

Sep 9, 2026cs.LG

Online Inverse Integer Linear Optimization via Small-Gradient Skipping: Constant Regret and Finite Mistakes

In online inverse linear optimization, the learner predicts a weight at each round, observes the optimal action of the agent, and updates its prediction. In the general setting, the gap of

\log T

between the regret upper bound

O(d \log T)

and the lower bound

Ω(d)

is unresolved (here

T

is the total number of rounds and

d

is the dimension). When the action set is M-convex, the regret is known to be bounded by

O(d \log d)

, but the method attaining it computes a center of gravity at every round. This paper therefore proposes Small-Gradient Skipping (SGS), a mechanism that skips the update at rounds without a mistake, and applies it to online gradient descent, the online Newton step, and MetaGrad. When the forward problem is an integer linear program with a unique optimal solution, the number of mistakes is bounded, for all three, by a quantity independent of

T

; and for the online Newton step and for MetaGrad with SGS, the dimension dependence of the regret becomes

O(d^2)

, that is, the factor

\log T

is removed. Moreover, when the action set is M-convex, the regret is bounded efficiently without computing a center of gravity.

Akira Kitaoka

Regret Minimization

Ask PDF

Sep 7, 2026cs.LG

No-Regret Mixing of LRU and LFU with Optimal Switching Cost

Caching systems often rely on simple eviction policies such as Least Recently Used (LRU) and Least Frequently Used (LFU), which perform well in complementary request regimes. Recent policies such as LeCar and Cacheus combine LRU and LFU using ideas from the experts problem in online learning. Specifically, upon a miss, they randomize between the two eviction rules using probabilities derived from scores updated by tracking the history of past evictions. While these policies exhibit strong empirical performance, it remains unclear whether they are guaranteed, on every request sequence, to perform asymptotically as well as the better of LRU and LFU, i.e., whether they achieve sublinear regret with respect to this benchmark. We first show that LeCar suffers linear regret against an oblivious adversary, even with unbounded history. We then propose H-MC, a Hedge-based mixture of virtual LRU and LFU caches that preserves Hedge's selection probabilities, and hence its regret guarantees, while minimizing the switching cost among all joint selection rules with these marginals.

Younes Ben Mazziane, Xinying Zou

Linköping University

Regret Minimization Online Learning

Ask PDF

Sep 3, 2026cs.LG

Constant regret in general games via higher-order optimism

We introduce an uncoupled learning algorithm which, when employed by all players of an arbitrary

N

-player normal form game with up to

K

actions per player, guarantees

O(N^3\log^2 K)

individual regret, uniformly over the horizon of play. The proposed algorithm - which we call higher-order optimism with discounting (HOOD) is a variant of optimistic follow-the-regularized-leader (OptFTRL) that combines a discounted

(N+1)

-th order predictor with entropic regularization over a suitable "lifting" of the game's strategy space. This combination of ingredients is purposefully designed to dampen large oscillations of the induced sequence of play in a controlled manner, removing in this way a key stumbling block of previous attempts to achieve constant regret in general games. Our approach bears several striking similarities to the concurrent - and completely independent - work of Liu, Farina, and Ozdaglar (arXiv:2608.31166), who very recently derived an

O(N^{21}\log^{4} K)

regret bound through the use of higher-order optimism and an exponential moving average estimator.

Omar Abbadi, Rida Laraki, Panayotis Mertikopoulos

Univ. Mohammed VI Polytechnic, CMSIS, MCGT, 11103 Rabat, Morocco · Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France

Follow-the-Regularized-Leader Regret Minimization

Ask PDF

Sep 2, 2026cs.LG

Online Non-Monotone DR-Submodular Maximization Matching the Offline $0.401$ Factor

We study online maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed subsets of the

d

-dimensional unit cube. The best known constructive offline approximation factor is

0.401

under the corresponding meta-solvability assumptions, whereas comparable adversarial online guarantees had remained at

1/e

. We show that this factor is also achievable online. In the post-decision full-information value-oracle model, our algorithm attains factor

0.401

with sublinear approximate regret when oracle feedback is conditionally unbiased and bounded. The online algorithm does not run the offline construction on a changing objective. Instead, it replaces the offline objective-dependent box step by a weighted online learner that controls the required residual terms cumulatively. An exact asymmetric balance theorem preserves the offline coefficients despite adversarial variation. The direct implementation has

O(T^{3/4})

regret and uses

O(dT^{1/4})

oracle calls per round. More generally, for every

δ\in[0,1/4]

, batching gives

O(T^δ)

calls per round and

O(T^{4/5-δ/5})

regret, including a one-call

O(T^{4/5})

endpoint. Under a positive-anchor condition, randomized blocking retains factor

0.401

with

O(T^{5/6})

one-point bandit regret.

Vaneet Aggarwal, Yiyang Lu

Purdue University

Submodular Optimization Regret Minimization

Ask PDF

Aug 31, 2026cs.LG

Constant Individual Regret in General Games

Uncoupled no-regret dynamics provide a decentralized route to equilibrium, but prior guarantees for individual regret retain a polylogarithmic dependence on the horizon. We remove this dependence for every finite

N

-player normal-form game under full-information feedback. We introduce \emph{ECHO-OFTRL}: optimistic follow-the-regularized-leader (OFTRL) equipped with an EMA cascade for high-order optimism (ECHO), where EMA denotes exponential moving average. The algorithm is deterministic and fully uncoupled. If

m_{\max}

denotes the largest action-set size, then, simultaneously for every horizon

T\geq1

, it guarantees that each of the

N

players in the game incurs regret upper bounded by

O(\textrm{poly}(N, \log m_{\max}))

. Our algorithm leverages a new form of optimism inspired by modern filter design.

Mingyang Liu, Gabriele Farina, Asuman Ozdaglar

LIDS, EECS, Massachusetts Institute of Technology

Game Theory Follow-the-Regularized-Leader Regret Minimization

Ask PDF

Aug 29, 2026cs.LG

PokaiTrainer: Scaling Equilibrium Search to Competitive Pokémon VGC

Decision-time equilibrium search carried poker to superhuman play, but it has so far relied on tractable subgames: a handful of actions per decision, chance confined to card deals, one player moving at a time. Competitive Pokémon in its official doubles format (VGC) breaks all three assumptions at once. Both players act simultaneously from joint menus in the hundreds, each joint action resolves to hundreds of stochastic outcomes, and the opponent's reserves and stat allocations are hidden. No prior Pokémon agent performs equilibrium search, and whether it scales to this regime was open; we show that it does, and report what it took. PokaiEngine, our Rust battle engine, enumerates a joint action's full weighted outcome distribution in one pass, at

{\sim}99\%

parity with Pokémon Showdown and a fraction of the cost of sampling it. PokaiTrainer adapts Student of Games to this scale and trains it by self-play over hundreds of human teams. Each decision is solved by counterfactual regret minimization as a Bayesian matrix game over public belief states, subgames grow under an explicit compute budget, and value targets are harvested from the interior of every solve and grounded by realized outcomes. The strength is in the search. The network's policy alone loses even to a shallow heuristic search. PokaiTrainer is, to our knowledge, the first VGC agent rated on the live Showdown ladder. Under open team sheets it wins 59% of 150 best-of-three sets against a human field averaging

{\sim}1320

Elo, holds a 1350-1400 Elo band, and at its peak reached 1492 Elo, entering the format's top 500.

Max Yu

Independent Researcher

Game-Playing Agents Self-Play RL Regret Minimization Nash Equilibrium Computation

Ask PDF

Aug 27, 2026cs.IT

Sharp Minimax Regret for Infinite-Memory Logistic Prediction

We determine the minimax cumulative log-loss regret of a finite-alphabet, exogenously driven source with genuinely infinite input memory: independent Rademacher inputs

(U_t)

are observed sequentially and the next binary mark has logit

\sum_{j\ge1}θ_jU_{t+1-j}

, the unknown coefficients obeying a summable envelope

|θ_j|\le r_j

\sum_jr_j\le B

. At horizon

T

, lag

j

can move the logit by at most

r_j

and is exercised in only

n_{T,j}=(T-j+1)_+

rounds, and the two limitations combine into the sum

Γ_T(r)=\sum_{j\le T}\log(1+n_{T,j}r_j^{2})

. One coordinate-localised Bayesian mixture achieves

R_T(r)\le CΓ_T(r)

for \emph{every} summable envelope with

C

universal. Our main result is a matching nonasymptotic converse for the canonical exponential and polynomial envelopes; its new ingredients are a modular finite-sample information bound for logistic experiments with an exogenous random design, and a conditioning estimate for the overlapping Toeplitz lag matrix obtained by exhibiting each off-diagonal Gram sum as a sum of independent Rademacher variables indexed by the edges of a forest, needing neither local asymptotic normality nor any spectral theorem for random Toeplitz matrices. So

Γ_T(r)

is the minimax regret scale here, giving

Θ(α^{-1}\log^{2}T)

for

r_j=Ae^{-αj}

and

Θ(T^{1/(2s)})

for

r_j=Aj^{-s}

s>1

--- the latter without the extra

(\log T)^{1-1/(2s)}

factor any window-truncation analysis pays. We also show memory decay cannot determine regret, and that a profile-scaled online Newton predictor attains

O_B(Γ_T(r))

in polynomial time per round.

Vaneet Aggarwal

Purdue University

Logistic Regression Bayesian Mixture Models Minimax Regret Regret Minimization Information-Theoretic Lower Bounds

Ask PDF

Aug 14, 2026cs.LG

Sequence prediction under a lying oracle

We consider the problem of sequential prediction of an

m

-ary sequence, where at each epoch, (i) the environment selects an outcome from an

m

-ary alphabet, (ii) the learner selects a probability distribution over the same alphabet (unaware of the outcome generated by the environment), and finally, (iii) the learner incurs a cost that depends on the probability assigned to the outcome. The cost function we consider captures the complexity of predicting the outcome generated by the environment, in a scenario where the aforementioned prediction is performed via comparative queries to a lying oracle. We consider both stochastic and adversarial environments, propose algorithms for both settings, and establish logarithmic upper bounds on their regret.

Puspabeethi Samanta, Nikhil Karamchandani, Jayakrishnan Nair

Department of Electrical Engineering IIT Bombay

Regret Minimization Sequence Modeling

Ask PDF

Aug 10, 2026cs.LG

Tracking the Best Strategy in an Extensive-Form Game

We consider the extensive-form bandit problem where on each trial the learner plays an extensive-form game against an oblivious adversary. We focus on the notion of switching regret, which measures the expected performance of the learner against that of any switching sequence of mixed strategies in retrospect. Our algorithm takes a parameter

ρ>0

and achieves a switching regret of

\tilde{\mathcal{O}}((1/ρ+ρK)\sqrt{H A T})

where

K

is the number of switches in the comparator sequence,

H

is the maximum number of the learner's information sets that can be traversed during a play of the game and

A

is the number of actions that the learner can possibly take. Our algorithm is extremely efficient, taking a per trial time of only

\mathcal{O}(H B)

where

B

is the maximum number of actions available to the learner at any of its information sets.

Stephen Pasteris, Rahul Savani, Theodore Turocy

The Alan Turing Institute · London, United Kingdom · The University of Liverpool +3

Imperfect-Information Games Regret Minimization Adversarial Bandits

Ask PDF

Aug 4, 2026cs.GT

Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization

Swap regret governs the rate at which uncoupled learning dynamics converge to correlated equilibria in multiplayer general-sum games. Under full-information feedback, the best previous guarantee when every player follows the same dynamics grows logarithmically in the horizon

T

. We construct uncoupled dynamics under which every player incurs only

O(nm^2\sqrt{\log m\log T})

swap regret, where

n

is the number of players and

m

bounds the number of actions per player. To our knowledge, this is the first sublogarithmic individual guarantee in this setting, and it implies that the time-averaged product distribution of play is an

O(nm^2\sqrt{\log m\log T}/T)

-approximate correlated equilibrium. The key algorithmic choice is to combine the Blum--Mansour reduction with optimistic follow-the-regularized-leader using a hybrid regularizer that separately weights negative Shannon entropy and the log-barrier: the entropy controls the optimistic prediction error, whereas the log-barrier controls the transition-matrix movement through its Bregman divergence. A new sensitivity theorem for stationary distributions of Markov chains, which involves neither mixing parameters nor the smallest transition probability, transfers this control to the played strategies and yields a simpler analysis without local-norm or self-concordance arguments. The guarantee is preserved by an adversarially robust variant that additionally ensures

O(nm^2\sqrt{\log m\log T}+\sqrt{mT\log m})

swap regret against arbitrary utility sequences, and by a horizon-free variant that requires no prior knowledge of

T

Taira Tsuchiya

The University of Tokyo and RIKEN

Follow-the-Regularized-Leader Regret Minimization

Ask PDF

Aug 3, 2026math.OC

A Spectral Filtering Approach to Regret Analysis of Distributed Online Control for Linear Dynamical Systems

This paper studies the distributed online control problem over a network of linear time-invariant (LTI) systems in the presence of adversarial disturbances and time-varying convex costs. The network cost is characterized by the summation of local cost functions, where each local function is sequentially revealed only to the corresponding agent. The goal of each agent is to generate a control sequence, using only local observations and neighbor communication, that competes with the best {\it centralized} linear policy in hindsight. We extend the recently proposed Online Spectral Control framework from the centralized setting to the distributed setting. In particular, each agent applies a spectral controller obtained by convolving past disturbances with the leading eigenvectors of a Hankel matrix, while the controller parameters are updated through a distributed online gradient descent step over the local surrogate costs. We formulate this problem this problem as a {\it regret} minimization problem based on the spectral parameterization, and under standard assumptions, we establish a sublinear regret bound of

O(\frac{\sqrt{T}\text{poly}(\log T)}{γ^3})

, where

T

is the time horizon and

γ

denotes the stability margin. The resulting bound also captures the dependence on the network size and connectivity.

Ting-Jui Chang

T.J. Chang is with the Department of Aeronautics and Astronautics, National Cheng Kung University, Taiwan.

Dynamical Systems Distributed Optimization Regret Minimization

Ask PDF

Jul 31, 2026stat.ML

Simple-regret rates and minimax optimality of fixed-prior expected improvement in Matérn and squared-exponential RKHSs

We study expected improvement (EI) for minimizing a deterministic function

f

in the RKHS

\mathcal H_k

of a continuous positive-semidefinite kernel

k

on a nonempty compact set

\mathcal X\subset\mathbb R^d

. Function values are observed exactly, and EI is computed from a fixed zero-mean Gaussian-process model with covariance

σ^2k

σ>0

. A weak-EI policy queries a point whose EI is at least a fixed positive fraction of its maximum. We introduce a notion of sequential separation radius relating ranked selected-point innovation norms to Kolmogorov widths, drawing on greedy approximation. Standard power-function estimates from scattered-data approximation and a finite-budget regret argument yield the rates. After

N

post-initial queries, every weak-EI policy has simple regret

O(N^{-ν/d})

for isotropic Matérn kernels of smoothness

ν>0

and

O(\exp[-c_1\min\{N,N^{1/d}\log(eN)\}])

for the isotropic squared-exponential kernel, with

c_1>0

. For

d=1

, the sharper bound

O(\exp[-c_2N\log(eN)])

holds for exact EI, with

c_2>0

. These bounds are uniform over each fixed RKHS ball. If

\mathcal X

has nonempty interior and

B>0

, the exact EI policy is minimax-rate optimal over the RKHS ball of radius

B

for Matérn kernels, even among randomized strategies whose final recommendation need not be a query point. For the squared-exponential kernel, it is minimax-rate optimal up to constants in the exponent among deterministic methods whose final recommendation may be any point of

\mathcal X

Emmanuel Vazquez, Sébastien Petit

Université Paris-Saclay, CNRS, CentraleSupélec, Laboratoire des Signaux et Systèmes, 91190 Gif-sur-Yvette, France · Laboratoire national de métrologie et d’essais (LNE), 1 rue Gaston Boissier, 75724 Paris Cedex 15, France

Bayesian Optimization Gaussian Processes Regret Minimization Kernel Methods

Ask PDF

Jul 29, 2026cs.RO

Self-Adaptive Learning and Model Predictive Control for Tracking Unknown Dynamics with No Regret

We propose a self-adaptive online learning for control method for tracking unknown target dynamics. The target dynamics can exhibit switching behavior, particularly, a mixture of structured, random, and/or adversarial motion. Such challenging target tracking scenarios arise in applications of dynamic mapping, traffic control, and pursuit evasion, where robots need to track, pursue, or avoid collision with moving landmarks, objects, humans, etc., whose dynamics are unknown. Our method simultaneously learns multiple predictors from scratch, via self-supervised, one-shot, and computationally efficient learning, and adaptively selects the best one to match the observed target behavior. The method enjoys finite-time near-optimality guarantees in expectation, characterized as a function of the learning error of the target dynamics and the frequency that the target dynamics switch. In the absence of both error and switching, the method asymptotically matches the optimal non-causal control policy that knows a priori the target dynamics, i.e., the method enjoys no regret in expectation. In the presence of learning errors and switching, the method degrades gracefully, \eg when there are errors and no switching, the average regret is proportional to the average learning error and switching times. To prove these guarantees, a novel technical approach is required compared to the existing works that employ RFF-based online learning. We validate our method in Crazyflie simulations and hardware experiments, across target trajectories that vary from structured to random to adversarial, in comparison to non-stochastic, kernel-based, and neural-network-based methods for online learning.

Atharva Navsalkar, Hongyu Zhou, Vasileios Tzoumas

Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI 48109 USA

Dynamical Systems Regime-Switching Dynamical Systems Model Predictive Control Regret Minimization Adaptive Learning Online Learning

Ask PDF

Jul 25, 2026cs.LG

Training with (Swap) Regret Loss in a Single-Layer Self-Attention Model: A Case Study on the Probability Simplex

We revisit the regret loss framework introduced in Park et al. (2025), which uses decision-theoretic regret as a direct loss function for training models to make better decisions, through the lens of probability-simplex policies. Our first result shows that a single-layer self-attention model trained with regret loss admits a stationary point whose forward-pass exactly matches smoothed fictitious play with the appropriate stepsize that ensures no-regret behavior-i.e., for any given policy input, the model outputs the same update that smoothed fictitious play would produce. In parallel, we also newly introduce a swap-regret loss function, which extends the regret-loss framework beyond external regret and enables models to directly optimize for swap-deviation robustness. We further show that this swap-regret loss admits a stationary point whose forward pass implements the corresponding swap-regret update induced by classical Blum-Mansour no-pass implementation algorithm, with each head implementing an external-regret update via smoothed fictitious play. Together, these results show that regret-trained attention can realize differentiable mechanisms whose deployment induces equilibrium behavior in games: external-regret dynamics lead to coarse correlated equilibrium, while swap-regret dynamics lead to correlated equilibrium. Thus, regret-based objectives steer minimal attention architectures toward online-learning dynamics with game-theoretic guarantees, without supervised traces of those algorithms.

Chanwoo Park, Asuman Ozdaglar

1MIT EECS

Self-Attention Regret Minimization

Ask PDF

Jul 22, 2026cs.LG

Breaking the $T^{3/4}$ Barrier for Regret Minimization With Bi-Dimensional CDFs

We study regret minimization for learning CDF-related objectives of the form

g(x)\cdot\mathbb{P}_{X\sim\mathcal{D}}(X\le x),

over

[0,1]^2

, where

g

is a known Lipschitz function and

\mathcal{D}

is an unknown distribution. At each round

t

, the learner selects a point

x_t

and observes the binary feedback

\mathbb{I}(X_t\le x_t)

, where

X_t\sim\mathcal{D}

. We design an algorithm achieving regret

\widetilde{\mathcal{O}}(T^{7/10})

, improving over the previous best-known bound of

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

and showing that the curse of dimensionality can be at least partially lifted for this class of objectives, though a gap remains with the

Ω(T^{2/3})

lower bound. As an application, our techniques yield the same

\widetilde{\mathcal{O}}(T^{7/10})

regret bound for profit maximization in repeated bilateral trade with fixed prices.

Matteo Castiglioni, Anna Lunghi, Alberto Marchesi

Politecnico di Milano

Multi-Armed Bandits Regret Minimization

Ask PDF

Jul 21, 2026econ.EM

Optimizing Regret

Building on the identity that expected regret equals the covariance between costs and decisions, this paper develops a derivative theory of the covariance regret functional. We derive the Gâteaux derivative, showing that the universal steepest-descent direction is the contrarian policy

-(c-\bar c)

, while ascent yields momentum. For linear policies

\hatπ(c)=Ac+b

, the gradient is the cost covariance matrix

Σ_c

, with a zero Hessian implying boundary-optimal solutions such as the minimum-variance portfolio. We extend to constrained optimization, sign-gradient duality between regret minimization and alpha maximization, finite-sample convergence bounds paralleling Thompson Sampling, and gradient-descent algorithms requiring only input observations.

Irene Aldridge

Risk AI Center

Gradient Descent Regret Minimization Decision-Making under Uncertainty

Ask PDF

Jul 13, 2026cs.LG

Efficient Online Proportional Sampling with Applications to Smoothed Online Learning

We study the problem of efficient online proportional sampling from a high-dimensional domain under a

σ

-smoothed adversary, where the sampling distribution is induced by a dynamically evolving weight function defined over a sequence of piecewise-structured partitions. This setting captures a broad range of applications, including principal-agent games (e.g., pricing and contract design), and algorithm configuration and parameter tuning. The central challenge is maintaining an efficient data structure as the induced partition grows increasingly complex over time -- naively, the number of subregions can grow as

O(t^d)

by round

t

d

dimensions. We design a data structure that supports efficient updates and proportional sampling while avoiding the cost of explicitly maintaining this exponential growth, where the discontinuities are structured from axis-parallel hyperplanes. Under a

σ

-smoothed adaptive adversary, we prove a tight

O(\sqrt{σT})

bound on the depth of our data structure, and an

O(\log T)

bound under a random-order adversary -- to our knowledge, the first such results for this class of problems. We apply this framework to online learning with piecewise-structured rewards, obtaining efficient no-regret algorithms under both full-information and bandit feedback, with provable sublinear regret guarantees.

Amirmahdi Mirfakhar, Maria-Florina Balcan, Hedyeh Beyhaghi

University of Massachusetts Amherst · Carnegie Mellon University

Adaptive Sampling Regret Minimization

Ask PDF

Jul 12, 2026cs.LG

Bandit PCA with Minimax Optimal Regret

We study the bandit-feedback version of online principal component analysis (Bandit PCA): in each round

t = 1,\dots,T

, the adversary selects a

d \times d

symmetric gain matrix

G_t

with spectrum in

[0,1]

and rank at most

r

; the learner simultaneously selects a unit vector

w_t \in S^{d-1}

and receives the reward

w_t^\top G_t w_t

. The learner receives no other feedback, and aims to minimize the regret against the best unit vector in hindsight. This problem was introduced by Kotlowski and Neu (2019), who gave an algorithm with regret

O(d\sqrt{rT \log T})

and showed the lower bound of

Ω(r\sqrt{T/\log T})

. We improve upon both of these bounds and essentially bridge the gap between them, establishing the minimax regret of order

r\sqrt{dT}

up to polylogarithmic factors in

d

and

T

. The upper bound is attained by a novel algorithm, which combines online mirror descent on the spectrahedron of (real) density matrices with a multiscale exploration scheme in which the eigenspaces with different spectral magnitudes are updated at different rates. For the lower bound, we construct an adaptive adversary that refines a hidden large-reward subspace based on the learner's actions, in such a way that low regret is impossible without estimating the subspace; as a result, lower-bounding the regret reduces to studying the arising subspace estimation problem. Finally, we discuss connections of Bandit PCA with adaptive-measurement quantum tomography.

Moïse Blanchard, Dmitrii Ostrovskii, Aadirupa Saha

Georgia Tech · University of Illinois, Chicago

Principal Component Analysis Minimax Regret Online Mirror Descent Regret Minimization Adversarial Bandits

Ask PDF

Jul 7, 2026cs.GT

Contextual Procurement Auctions with Bandit Learning

We study repeated contextual procurement auctions in which producers have private costs and the platform must learn context-dependent product values from bandit feedback. The objective is welfare rather than revenue or a virtual-cost surrogate: regret is the total surplus loss relative to the full-information efficient procurement rule. We first show that the natural UCB allocation rule attains

\tilde O(\sqrt{ngT})

welfare regret under truthful bids, but its adaptive bid-dependent learning path does not by itself give a truthfulness guarantee. To obtain exact incentives, we design a bid-independent explore-then-commit mechanism with empirical critical payments; it is dominant-strategy truthful and has

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

regret. We then introduce frozen-payment UCB, which estimates payments in an initial bid-independent exploration phase, freezes those payment estimates, and continues adaptive UCB allocation learning afterwards. Under a smoothed truthful-path margin condition, this mechanism gives a regret-incentive tradeoff: the near-UCB tuning attains

\tilde O(\sqrt{ngT})

welfare regret, while the average per-round gain from any fixed deviation is at most

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

for fixed

n,g

. A matching lower bound shows that this frozen-payment frontier is unavoidable.

Yiling Chen, Shi Feng, Sadie Zhao

Harvard University

Mechanism Design Regret Minimization Contextual Bandits

Ask PDF

Momentum

Related topics

Latest papers 81