Regret

Follow this topic Ask about this topic

Momentum

5 papers in the last four weeks, down 17% on the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 80

All topics

The Curvature of Regret in Contextual Linear Optimization
Oct 1, 2026Konstantinos Ziliaskopoulos, Alexander Vinel, Alice E. SmithLinear Programming Regret
Auburn University Auburn, AL, USA · University of Alabama Tuscaloosa, AL, USA
Minimax Optimal Regret for Causal Logistic Bandits with Counterfactual Fairness
Oct 1, 2026Junhyuk Huh, Seoungbin Bae, Dabeen LeeStochastic Multi-Armed Bandits Algorithmic Fairness
Faculty of Mathematics, University of Cambridge · Department of Industrial & Systems Engineering, KAIST · Department of Mathematical Sciences, Seoul National University
Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant
Sep 23, 2026Yang Cai, Vineet Gupta, Yanchen Jiang +4\Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Regret
Google Research · Yale University · Google DeepMind
RegRet: Enhancing Region-Level Retrieval in Large Multimodal Models
Sep 15, 2026Xun Liang, Honghui Yang, Weihang Pan +6Multimodal Retrieval Large Multimodal Models
State Key Lab of CAD&CG, Zhejiang University · Xiaohongshu Inc. · School of Software Technology, Zhejiang University
Exact-Form Regret for Gradient Descent, Mirror Descent and Follow-the-Regularized-Leader
Sep 8, 2026Ashkan Soleymani, Gabriele Farina, Patrick JailletMirror Descent Learning-Augmented Algorithms
MIT
Constant regret in general games via higher-order optimism
Sep 3, 2026Omar Abbadi, Rida Laraki, Panayotis Mertikopoulos\Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Regret
Univ. Mohammed VI Polytechnic, CMSIS, MCGT, 11103 Rabat, Morocco · Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France
Posterior Tempering Explains Variance Inflation in Linear and Generalized Linear Thompson Sampling
Sep 2, 2026Prateek Jaiswal, Debdeep Pati, Anirban Bhattacharya +1Thompson Sampling \Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret
Daniels School of Business, Purdue University. · Department of Statistics, University of Wisconsin-Madison. · Department of Statistics, Texas A&M University.
Sharp Minimax Regret for Infinite-Memory Logistic Prediction
Aug 27, 2026Vaneet AggarwalRegret Minimax
Purdue University
Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization
Aug 17, 2026Shion Takeno, Shogo IwazakiGaussian Process Thompson Sampling
Nagoya University · MI-6 Ltd.
Coordinating the Unknown Lipschitz Constant in Multiplayer Bandits
Aug 11, 2026Ricardo Parada, Chenzhang Zhao, William ChangStochastic Multi-Armed Bandits Lipschitz Continuity
University of California, Riverside Riverside, CA, USA · University of California, Los Angeles Los Angeles, CA, USA
Regret, equilibrium, and learning in games: A guided tour
Aug 10, 2026Panayotis MertikopoulosImperfect-Information Games Equilibrium
Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France.
Sharp Characterization of Bias in Post-Bandit Inference
Aug 2, 2026Lisu Wang, Yilun Chen, Jiaqi LuStochastic Multi-Armed Bandits Stochastic Exploration
School of Data Science, The Chinese University of Hong Kong, Shenzhen · School of Management and Economics, The Chinese University of Hong Kong, Shenzhen
Convergence and Regret of the Policy Gradient for Multi-Armed Bandits in Diffusion Environment
Jul 31, 2026Yanwei Jia, Du OuyangPolicy Gradient Stochastic Multi-Armed Bandits
Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, New Territories, Hong Kong SAR · Department of Mathematical Sciences, Tsinghua University, Beijing, Beijing 100084, China
Self-Adaptive Learning and Model Predictive Control for Tracking Unknown Dynamics with No Regret
Jul 29, 2026Atharva Navsalkar, Hongyu Zhou, Vasileios TzoumasModel Predictive Control Optimal Control
Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI 48109 USA
Data-Dependent Regret and Polyak Corrections for Constrained Online Convex Optimization
Jul 28, 2026Wentao ZhangConvex Optimization \Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret
Tsinghua Shenzhen International Graduate School · Tsinghua University
One More Turn, Less Regret: A Regret-Based Multi-Turn Benchmark for LLMs' Clarification Policies
Jul 23, 2026Minh Ngoc Ta, My Anh Tran Nguyen, Duong D. Nguyen +2Clarification Question
MBZUAI · BKAI Research Center, Hanoi University of Science and Technology · INSAIT, Sofia University "St. Kliment Ohridski"
Breaking the $T^{3/4}$ Barrier for Regret Minimization With Bi-Dimensional CDFs
Jul 22, 2026Matteo Castiglioni, Anna Lunghi, Alberto Marchesi\Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Regret
Politecnico di Milano
Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence
Jul 22, 2026Runlong Zhou, Zihan Zhang, Maryam Fazel +1Model-Free Reinforcement Learning Value Functions
University of Washington. · Hong Kong University of Science and Technology. · §University of Washington. +1
Optimizing Regret
Jul 21, 2026Irene AldridgeRegret Policy Gradient
Risk AI Center
When Is Delegated Play Truthful? Within-Range Regret and the Trilemma of Aligned Delegation
Jul 15, 2026Taksch DubeHonesty Incentives
Kent State University, Kent, OH, USA
Bandit PCA with Minimax Optimal Regret
Jul 12, 2026Moïse Blanchard, Dmitrii Ostrovskii, Aadirupa SahaPrincipal Component Analysis \Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret
Georgia Tech · University of Illinois, Chicago
Probably Correct Optimal Stable Matching under Two-Sided Uncertainty
Jul 6, 2026Andreas Athanasopoulos, Anne-Marie George, Christos DimitrakakisDistribution Matching Matching Markets
University of Neuchâtel, Neuchâtel, Switzerland · University of Oslo, Oslo, Norway
Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions
Jul 3, 2026Zihao Hu, Yuan Yao, Jiheng Zhang +1Contextual Bandit Framework Regret
Department of Mathematics, The Hong Kong University of Science and Technology
Online Resource Allocation with Continuous Random Consumption: Regret under Degeneracy
Jul 2, 2026Jiawei Zhang\Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Regret
Stern School of Business New York University
When Classic Cache Policies Fail: Learning-Augmented Replacement for Semantic Retrieval Buffers
Jul 1, 2026Yushi Sun, Bowen Cao, Wai LamCache Feedback
LIGHTSPEED, Tencent · Shenzhen, China · The Chinese University of Hong Kong +1
Contextual Slate GLM Bandits with Limited Adaptivity
Jun 30, 2026Tanmay Goyal, Sukruta Prakash Midigeshi, Gaurav SinhaContextual Bandit Framework Generalized Linear Model
Microsoft Research India
Improved Multi-Dimensional Forecasting for Swap Regret
Jun 28, 2026Joey Rivkin, Ramiro N. Deo-Campo Vuong, Robert Kleinberg +3Regret Downstream Reasoning
Cornell University
Leveraging Similarities in Multi-Armed Bandits
Jun 22, 2026Khaled Eldowa, Thibaud Rahier, Augustin Cablant +2Stochastic Multi-Armed Bandits Regret
Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK, 38000 Grenoble, France · Criteo AI Lab, Paris, France · Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France
YUKTI: From Natural-Language Situations to Robust, Verifiable Decisions An Uncertainty-Typed Proposition IR, Assumption-Robust Pareto Frontiers, and a Regret Certificate
Jun 22, 2026Suyash MishraPareto Frontier Situation Calculus
AI Researcher
Adversarial Bandit Optimization with Globally Bounded Perturbations to Convex Losses
Jun 18, 2026Zhuoyu Cheng, Kohei Hatano, Eiji TakimotoConvex Loss Convex Optimization
Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan · RIKEN AIP, Japan · Department of Informatics, Kyushu University, Japan
Toward Simultaneously Optimal Regret in U-Calibration
Jun 16, 2026Rafael Frongillo, Haipeng Luo, Nishant A. Mehta +1Optimal Regret Regret
University of Colorado Boulder · University of Southern California and Google Research · University of Victoria +1
Filtered ANN as a Phase Transition: When Selectivity-Estimation Error Causes Plan Regret
Jun 15, 2026Madhulatha Mandarapu, Sandeep KunkunuruApproximate Nearest-Neighbor Search Plan Regret
VaidhyaMegha Private Limited, India
When Does q-error Predict Plan Regret? Three Regimes of Cardinality-Estimation Error
Jun 14, 2026Madhulatha Mandarapu, Sandeep KunkunuruPrediction Error Plan Regret
VaidhyaMegha Private Limited, India
Repeated Bilateral Trade: The Quest for Fairness
Jun 13, 2026François Bachoc, Roberto Colomboni, Emilie KaufmannNash Equilibrium Algorithmic Fairness
University of Lille Institut Universitaire de France (IUF) Lille, France · School of Mathematics University of Bristol Fry Building, Woodland Road Bristol BS8 1UG, United Kingdom · Univ. Lille, CNRS, Inria, Centrale Lille, UMR 9189-CRIStAL F-59000 Lille, France
Online Convex Optimization with Sublinear Noisy Probes
Jun 12, 2026Simone Di Gregorio, Anupam Gupta, Stefano Leonardi +1\Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Convex Optimization
Sapienza University of Rome, Italy · New York University, USA · EPFL, Switzerland
Learning with Simulators: No Regret in a Computationally Bounded World
Jun 11, 2026Sasha Voitovych, Abhishek Shetty, Noah Golowich +1Learnability Regret
MIT · Microsoft Research
Online Learning with Gradient-Variation Interval Regret
Jun 2, 2026Yan-Feng Xie, Shuche Wang, Peng Zhao +1Learning-Augmented Algorithms Interval Regret
Regret Pre-training: Bridging Prior and Posterior Views for Enhanced Knowledge Grounding
Jun 2, 2026Mingkuan Zhao, Xiayu Sun, Wentao Hu +5Token-Level Supervision Causal Attention
The School of Computer Science and Technology, Xi’an Jiaotong University, China.
Coherent Swap Regret and Channel-Proof Learning
Jun 1, 2026Sohail SarkarRegret
University of Toronto
Efficient Exploration for Iterative Nash Preference Optimization
May 31, 2026Tianlong Nan, Xiaopeng Li, Christian Kroer +1Reinforcement Learning From Human Feedback Nash Equilibrium
Columbia University⋄ · The Chinese University of Hong Kong, Shenzhen†
Optimal-Point Variance Reduction For Bayesian Optimization With Regret Guarantee
May 31, 2026Shion TakenoBayesian Optimization Variance Reduction
1Nagoya University
Instance-dependent Stochastic Lipschitz bandit
May 28, 2026Marius Potfer, Vianney PerchetStochastic Multi-Armed Bandits Optimality
Crest (Fairplay joint team), ENSAE · EDF R&D · Criteo AI Lab
On the Learnability of Test-Time Adaptation: A Recovery Complexity Perspective
May 27, 2026Zhi Zhou, Ming Yang, Shi-Yu Tian +3Stable Test-Time Adaptation Test-Time Adaptation
State Key Laboratory of Novel Software Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China · School of Intelligence Science and Technology, Nanjing University, China
Near-Optimal Regret in Adversarial Kernel Bandits
May 26, 2026Yu-Jie Zhang, Hao Qiu, Jonathan Scarlett +1\Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Minimax Rate
National University of Singapore
Prudent-Banker: No Extra Fees for Baseline Safety in Adversarial Bandits With and Without Delays
May 22, 2026Ting Hu, Luanda Cai, Emmanouil-Vasileios Vlatakis-GkaragkounisBandits Bounded Adversary
Department of Finance University of Wisconsin–Madison · Department of Computer Sciences University of Wisconsin–Madison
Regret Analysis of Retry-Based Bandits
May 20, 2026Bingkui Tong, Junpei Komiyama, Soichiro Nishimori +1Stochastic Multi-Armed Bandits Regret
Mohamed bin Zayed University of Artificial Intelligence · RIKEN AIP · The University of Tokyo
Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs
May 19, 2026Pierre Boudart, Pierre Gaillard, Alessandro RudiMarkov Decision Processes Minimax
SIERRA · INRIA, École Normale Supérieure CNRS, PSL Research University Paris, France · Thoth +3
Tighter Regret Bounds for Contextual Action-Set Reinforcement Learning
May 15, 2026Zijun Chen, Zihan ZhangOptimal Regret Offline Reinforcement Learning
Department of Computer Science and Engineering Hong Kong University of Science and Technology
Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization
May 13, 2026Irene AldridgeOptimal Regret Regret
Polyhedral Instability Governs Regret in Online Learning
May 13, 2026Yuetai Li, Fengqing Jiang, Yichen Feng +6\Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Submodular Functions
♣University of Washington · ♢Western Washington University · ♠King Abdulaziz City for Science and Technology ♡HUMAIN
A Regret Perspective on Online Multiple Testing
May 13, 2026Qingyang Hao, Kongchang Zhou, Fang Kong +1False Discovery Rate Two-Sample Testing
Southern University of Science and Technology
Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret
May 12, 2026Kihyun Yu, Beomhan Baek, Dabeen LeeMarkov Decision Processes Optimal Regret
1KAIST · 2Seoul National University
Regret Analysis of Guided Diffusion for Black-Box Optimization over Structured Inputs
May 11, 2026Masaki Adachi, Anita Yang, Yakun Wang +1Black-Box Optimization Diffusion Models
Toyota Motor Corporation · Lattice Lab · University of Bristol
Optimal Regret for Single Index Bandits
May 10, 2026Devdan Dey, Sujoy Bhore, Avishek GhoshStochastic Multi-Armed Bandits Optimal Regret
Department of Computer Science and Engineering, Indian Institute of Technology Bombay.
Learning Pure Quantum States in Any Dimension (Almost) Without Regret
May 9, 2026Josep Lumbreras, Marco TomamichelQubit \Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret
Centre for Quantum Technologies, National University of Singapore, Singapore · 2Nanyang Quantum Hub, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore · Department of Electrical and Computer Engineering, National University of Singapore, Singapore
Interpreting Reinforcement Learning Agents with Susceptibilities
May 8, 2026Chris Elliott, Einar Urdshals, David Quarel +1Posterior Regret
Timaeus
Toward Optimal Regret in Robust Pricing: Decoupling Corruption and Time
May 8, 2026Kalana Kalupahana, Francesco Emanuele Stradi, Matteo Castiglioni +1Dynamic Pricing Regret
Politecnico di Milano
Towards Differentially Private Reinforcement Learning with General Function Approximation
May 7, 2026Yi He, Xingyu ZhouModel-Based Reinforcement Learning Regret
Wayne State University, Detroit, USA
Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning
May 6, 2026Harin Lee, Min-hwan OhStochastic Multi-Armed Bandits Regret
University of Washington · Seoul National University
Pandora's Regret: A Proper Scoring Rule for Evaluating Sequential Search
May 3, 2026Gerardo A. Flores, Yash Deshpande, Jannis R. Brea +1Regret Evaluation Metrics
MIT · Independent · NYU

Oct 1, 2026, cs.LGJ/K move · Enter open · S save

The Curvature of Regret in Contextual Linear Optimization

Konstantinos Ziliaskopoulos, Alexander Vinel, Alice E. Smith

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

Linear Programming Regret Scenario Generation

Open paper AskPDF arXiv

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.

Momentum

Related topics

Latest papers 80