Regret

Follow this field Ask about this field

Recent momentum

emerging

0 papers in the last 28 days · 0.0% of indexed attention

Twelve weeks of publication activity for this topic as it is defined today.

Weekly history

Recent digests

What was published in this field, kept on the site without email delivery.

Period ending 2026-09-21

2 new papers

A weekly snapshot of new work published in Regret.

Period ending 2026-09-14

8 new papers

A weekly snapshot of new work published in Regret.

Period ending 2026-09-07

4 new papers

A weekly snapshot of new work published in Regret.

Inside this field

Focused directions

Focused topic

Regret

Within Regret

100 papersExplore

Focused topic

Linear Regret

Within Regret

83 papersExplore

Focused topic

O(T^Β)$ Simultaneous Regret

Within Regret

34 papersExplore

Focused topic

Near-Optimal Regret Guarantees

Within Regret

22 papersExplore

201 papers

Latest in Regret

Browse all topics →

A Geometric Approach to Constrained Online Learning
May 20, 2026Dhruv Sarkar, Abhishek SinhaConvex Optimization O(T^Β)$ Simultaneous Regret
Finite-Time Regret Analysis of Retry-Aware Bandits
May 20, 2026Bingkui Tong, Junpei Komiyama, Soichiro Nishimori +1Multi-Armed Bandits Linear Regret
Active Context Selection Improves Simple Regret in Contextual Bandits
May 19, 2026Mohammad Shahverdikondori, Jalal Etesami, Negar KiyavashOptimal Bandit Algorithms Linear Regret
Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs
May 19, 2026Pierre Boudart, Pierre Gaillard, Alessandro RudiNear-Optimal Regret Guarantees Markov Decision Processes
Online Market Making and the Value of Observing the Order Book
May 19, 2026Davide Maran, Marcello RestelliLimit Order Book O(T^Β)$ Simultaneous Regret
Catching a Moving Subspace: Low-Rank Bandits Beyond Stationarity
May 18, 2026Hamed Khosravi, Xiaoming HuoMulti-Armed Bandits Bandits
Calibeating for general proper losses: A Bregman divergence approach
May 17, 2026Maximilian Fichtl, Cristóbal Guzmán, Nishant A. MehtaBregman Divergences Linear Regret
Boundedly Rational Meta-Learning in Sequential Consumer Choice
May 15, 2026Mehrzad Khosravi, Max Kleiman-Weiner, Hema YoganarasimhanMeta-Learning Online Shoppers Purchasing Intention
Tighter Regret Bounds for Contextual Action-Set Reinforcement Learning
May 15, 2026Zijun Chen, Zihan ZhangLinear Regret Value Functions
In-Context Learning for Data-Driven Censored Inventory Control
May 14, 2026Sohom Mukherjee, Anh-Duy Pham, Richard Pibernik +1Monotonic Inventory Estimation Linear Regret
Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization
May 13, 2026Irene AldridgeRegret Covariance Estimation
Polyhedral Instability Governs Regret in Online Learning
May 13, 2026Yuetai Li, Fengqing Jiang, Yichen Feng +6Submodular Maximization Regret
A Regret Perspective on Online Multiple Testing
May 13, 2026Qingyang Hao, Kongchang Zhou, Fang Kong +1False Discovery Rate Two-Sample Testing
IGT-OMD: Implicit Gradient Transport for Decision-Focused Learning under Delayed Feedback
May 12, 2026Benjamin Amoh, Geoffrey G. Parker, Wesley MarreroLinear Regret Bilevel Optimization
Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret
May 12, 2026Kihyun Yu, Beomhan Baek, Dabeen LeeMarkov Decision Processes Linear Regret
Online Sharp-Calibrated Bayesian Optimization
May 11, 2026Marshal Arijona Sinaga, Julien Martinelli, Teemu Turpeinen +1Bayesian Optimization Gaussian Process
Regret Minimization in Bilateral Trade With Perturbed Markets
May 11, 2026Anna Lunghi, Matteo Castiglioni, Alberto MarchesiRegret Matching Markets
Regret Analysis of Guided Diffusion for Black-Box Optimization over Structured Inputs
May 11, 2026Masaki Adachi, Anita Yang, Yakun Wang +1Black-Box Optimization Regret
Learning to Sparsify Stochastic Linear Bandits
May 11, 2026Zhengmiao Wang, Ming Chi, Zhi-Wei Liu +2O(T^Β)$ Simultaneous Regret Sparsity
PFN-TS: Thompson Sampling for Contextual Bandits via Prior-Data Fitted Networks
May 11, 2026Yan Shuo Tan, Kenyon Ng, Ruizhe Deng +3Thompson Sampling Tabular Prior-Data Fitted Network
The Value of Mechanistic Priors in Sequential Decision Making
May 11, 2026Itai Shufaro, Gal Benor, Shie MannorSequential Decision Making Prior Knowledge
Online Set Learning from Precision and Recall Feedback
May 10, 2026Lee Cohen, Yishay Mansour, Shay Moran +1Learning-Augmented Algorithms Optimal Sample Complexity
Optimal Regret for Single Index Bandits
May 10, 2026Devdan Dey, Sujoy Bhore, Avishek GhoshMulti-Armed Bandits Regret
Learning to Bid with Unknown Private Values in Budget-Constrained First-Price Auctions
May 10, 2026Zihao Hu, Yuxiao Wen, Yuan Yao +2First-Price Auctions Primal-Dual Methods
Learning Pure Quantum States in Any Dimension (Almost) Without Regret
May 9, 2026Josep Lumbreras, Marco TomamichelN$-Qubit Stabilizer States O(T^Β)$ Simultaneous Regret
The Power of Second Order Methods for Sequence Preconditioning
May 8, 2026Annie Marsden, Elad HazanSequence Linear Regret
Interpreting Reinforcement Learning Agents with Susceptibilities
May 8, 2026Chris Elliott, Einar Urdshals, David Quarel +1Deep Reinforcement Learning Posterior
Toward Optimal Regret in Robust Pricing: Decoupling Corruption and Time
May 8, 2026Kalana Kalupahana, Francesco Emanuele Stradi, Matteo Castiglioni +1Linear Regret Prices
Multi-Armed Bandits With Best-Action Queries
May 8, 2026Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi +1Multi-Armed Bandits O(T^Β)$ Simultaneous Regret
Convex Optimization with Nested Evolving Feasible Sets
May 8, 2026Karthick Krishna M., Haricharan Balasundaram, Rahul VazeConvex Optimization O(T^Β)$ Simultaneous Regret
Cost-Ordered Feasibility for Multi-Armed Bandits with Cost Subsidy
May 8, 2026Ishank Juneja, Carlee Joe-Wong, Osman YağanMulti-Armed Bandits Linear Regret
Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning
May 8, 2026Idan Attias, Steve Hanneke, Arvind RamaswamiLearning-Augmented Algorithms Regret
Towards Differentially Private Reinforcement Learning with General Function Approximation
May 7, 2026Yi He, Xingyu ZhouDifferential Privacy Offline Reinforcement Learning
$f$ -Divergence Regularized RLHF: Two Tales of Sampling and Unified Analyses
May 7, 2026Di Wu, Chengshuai Shi, Jing Yang +1Bregman Divergences Reinforcement Learning From Human Feedback
Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning
May 6, 2026Harin Lee, Min-hwan OhLinear Regret Multi-Armed Bandits
Data-dependent Exploration for Online Reinforcement Learning from Human Feedback
May 6, 2026Zhen-Yu Zhang, Yuting Tang, Jiandong Zhang +2Reinforcement Learning From Human Feedback Exploration-Exploitation Dilemma
Online Nonstochastic Prediction: Logarithmic Regret via Predictive Online Least Squares
May 6, 2026Chih-Fan Pai, Yang ZhengLinear Regret Non-Stationarity
QUIVER: Cost-Aware Adaptive Preference Querying in Surrogate-Assisted Evolutionary Multi-Objective Optimization
May 5, 2026Florian A. D. BurnatMulti-Objective Optimization Evolutionary Search
Pandora's Regret: A Proper Scoring Rule for Evaluating Sequential Search
May 3, 2026Gerardo A. Flores, Yash Deshpande, Jannis R. Brea +1Scoring Regret
The (Marginal) Value of a Search Ad: An Online Causal Framework for Repeated Second-price Auctions
May 3, 2026Yuxiao Wen, Zihao Hu, Yanjun Han +2First-Price Auctions Linear Regret
Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression
May 2, 2026Fan Chen, Jian Qian, Alexander Rakhlin +1Conformal Test Martingales Concentration Inequalities
Decision-Focused Learning via Tangent-Space Projection of Prediction Error
May 2, 2026Junhyeong Lee, Sangjin Jin, Yongjae LeeLinear Regret Reward-Prediction Error
Meritocratic Fairness in Budgeted Combinatorial Multi-armed Bandits via Shapley Values
May 1, 2026Shradha Sharma, Swapnil Dhamal, Shweta JainShapley Value Multi-Armed Bandits
Scaling Federated Linear Contextual Bandits via Sketching
May 1, 2026Hantao Yang, Hong Xie, Xutong Liu +1Linear Contextual Bandits Federated Learning
Trading off rewards and errors in multi-armed bandits
May 1, 2026Akram Erraqabi, Alessandro Lazaric, Michal Valko +2Multi-Armed Bandits Regret
Wasserstein Distributionally Robust Regret Optimization for Reinforcement Learning from Human Feedback
Apr 30, 2026Yikai Wang, Shang Liu, Jose BlanchetReinforcement Learning From Human Feedback Linear Regret
Dynamic Regret for Online Regression in RKHS via Discounted VAW and Subspace Approximation
Apr 27, 2026Dmitry B. Rokhlin, Georgiy A. KarapetyantsKernel Hilbert Spaces Kernel Method
Efficient learning by implicit exploration in bandit problems with side observations
Apr 27, 2026Tomas Kocak, Gergely Neu, Michal Valko +1Near-Optimal Regret Guarantees Bandits
Prior-Agnostic Robust Forecast Aggregation
Apr 27, 2026Zhi Chen, Cheng Peng, Wei TangLlm-Based Forecasting Methods Linear Regret
Direction-Aware Offline-to-Online Learning in Linear Contextual Bandits
Apr 27, 2026Zean Han, Ruihan Lin, Zezhen Ding +1Linear Contextual Bandits Near-Optimal Regret Guarantees
Logistic Bandits with $\tilde{O}(\sqrt{dT})$ Regret without Context Diversity Assumptions
Apr 24, 2026Seoungbin Bae, Dabeen LeeO(T^Β)$ Simultaneous Regret Multi-Armed Bandits
Rate-Optimal Regret for the Safe Learning-based Control of the Constrained Linear Quadratic Regulator
Apr 24, 2026Spencer Hutchinson, Nanfei Jiang, Mahnoosh AlizadehLinear Quadratic Regulator O(T^Β)$ Simultaneous Regret
Cover meets Robbins while Betting on Bounded Data: $\ln n$ Regret and Almost Sure $\ln\ln n$ Regret
Apr 22, 2026Shubhada Agrawal, Aaditya RamdasO(T^Β)$ Simultaneous Regret Regret
An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to $Φ$ -Regret Minimization
Apr 21, 2026Gabriele Farina, Juan Carlos PerdomoLinear Regret Online Learning
Online Conformal Prediction with Adversarial Semi-bandit Feedback via Regret Minimization
Apr 20, 2026Junyoung Yang, Kyungmin Kim, Sangdon ParkConformal Prediction Finite-Sample Coverage Guarantees
Multi-User mmWave Beam and Rate Adaptation via Combinatorial Satisficing Bandits
Apr 16, 2026Emre Özyıldırım, Barış Yaycı, Umut Eren Akturk +1Wireless Resource Allocation Millimeter Wave
Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards
Apr 16, 2026Subhodip Panda, Shubhada AgrawalOptimal Bandit Algorithms Regret
Learning from Equivalence Queries, Revisited
Apr 6, 2026Mark Braverman, Roi Livni, Yishay Mansour +2Equivalence Adversarial Training
Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spaces
Mar 9, 2026Hamish Flynn, Joe Watson, Ingmar Posner +1Gaussian Process Entropy Regularized Reinforcement Learning
Bilateral Trade Under Heavy-Tailed Valuations: Minimax Regret without a Variance Bound
Mar 6, 2026Hangyi ZhaoRegret Long-Tailed Distribution

May 20, 2026 · cs.LGJ/K move · Enter open · S save

A Geometric Approach to Constrained Online Learning

Dhruv Sarkar, Abhishek Sinha

Indian Institute of Technology Kharagpur · Mohamed bin Zayed University of Artificial Intelligence · Tata Institute of Fundamental Research, Mumbai

We study constrained online convex optimization with adversarial time-varying constraints. At each round the learner acts before observing the loss and constraint, and is compared with the best fixed action satisfying all constraints in hindsight. The goal is to obtain minimax-optimal regret while controlling cumulative constraint violation (CCV). Prior algorithms achieved

O(\log T)

regret with

O(\sqrt{T\log T})

CCV for strongly convex losses, and

O(\sqrt{T})

regret with

O(\sqrt{T}\log T)

CCV for convex losses. We propose NP-OGD, an iterated nested-projection algorithm. For strongly convex losses it achieves

O(\log T)

regret and

O(\log T)

CCV; for convex losses it achieves

O(\sqrt{T})

regret and

O(\sqrt{T})

CCV. The analysis relies on a geometric movement bound: after lifting the nested projected-gradient trajectory to one higher dimension, the lifted path is self-contracted under a nonstandard norm, so a finite-length theorem for self-contracted curves controls the total projection movement. We also prove complementary lower bounds using layered sphere packings. For strongly convex losses, any online algorithm with polynomially sublinear regret can incur CCV at least

Ω((\log T)^{(d-1)/(d+1)}/\log\log T)

. For convex losses, we prove CCV lower bounds

Ω(T^{(d-1)/(2(d+3))})

for weakly adaptive algorithms and

Ω(T^{(d-1)/(2d)})

for NP-OGD. Finally, for the constrained experts special case over

N

experts, an active Hedge algorithm attains

O(\sqrt{T\log N})

regret and

O(N)

CCV, with a matching minimax CCV lower bound for sufficiently large horizons.

Convex Optimization O(T^Β)$ Simultaneous Regret Learning-Augmented Algorithms

Open paper Ask about it PDF