Regret Minimization in RL

RL: Reinforcement Learning

Regret minimization studies how an agent can learn an effective policy while keeping the cumulative reward it gives up, compared with an optimal or hindsight benchmark, as small as possible. Common approaches include optimistic exploration such as UCB, posterior or Thompson sampling, policy optimization, and primal-dual methods for constrained problems; variance-aware and gap-dependent analyses aim to improve guarantees when the environment is favorable. Work spans tabular finite- and infinite-horizon Markov decision processes, linear and kernel function approximation, adversarial or changing rewards, and settings with delayed, preference-based, or risk-sensitive feedback. Many settings now have near-matching upper and lower regret bounds, but a central tension remains between guarantees that adapt to problem structure and algorithms that remain computationally efficient under weaker assumptions.

Latest papers

60 papers14 papers in the last four weeks, against 2 the four weeks before. 0.1% of all new papers.

Variance-Adaptive Optimal Algorithm for Reinforcement Learning with Multinomial Logit Function Approximation
May 27, 2026Wonyoung Kim, Min-Hwan Oh, Garud Iyengar +1Regret Minimization in RL Reinforcement Learning
Chung-Ang University · Seoul National University · Columbia University
Learning Kernel-Based MDPs from Episodic Preferential Feedback
May 22, 2026Nikola Pavlovic, Sattar Vakili, Qing ZhaoPairwise Preference Learning Regret Minimization in RL
Cornell University · MediaTek Research
Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs
May 19, 2026Pierre Boudart, Pierre Gaillard, Alessandro RudiRegret Minimization in RL Markov Decision Processes
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 ZhangRegret Minimization in RL Reinforcement Learning
Department of Computer Science and Engineering Hong Kong University of Science and Technology
Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret
May 12, 2026Kihyun Yu, Beomhan Baek, Dabeen LeeRegret Minimization in RL Markov Decision Processes
1KAIST · 2Seoul National University
Towards Differentially Private Reinforcement Learning with General Function Approximation
May 7, 2026Yi He, Xingyu ZhouRegret Minimization in RL Reinforcement Learning
Wayne State University, Detroit, USA
Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning
May 6, 2026Harin Lee, Min-hwan OhMulti-Armed Bandits Regret Minimization in RL
University of Washington · Seoul National University
Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation
May 1, 2026Haichen Hu, Jian Qian, David Simchi-LeviRegret Minimization in RL Markov Decision Processes
Laboratory for Information and Decision Systems · Department of AI and Data Science
Wasserstein Distributionally Robust Regret Optimization for Reinforcement Learning from Human Feedback
Apr 30, 2026Yikai Wang, Shang Liu, Jose BlanchetReward Over-Optimization Regret Minimization in RL
Department of Statistics and Operations Research, University of North Carolina · Imperial Business School, Imperial College London · Department of Management Science and Engineering, Stanford University
DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees
Apr 17, 2026Argyrios Gerogiannis, Yu-Han Huang, Venugopal V. VeeravalliNon-Stationary RL Regret Minimization in RL
ECE and CSL, The Grainger College of Engineering University of Illinois at Urbana-Champaign
Optimizing Neurorobot Policy under Limited Demonstration Data through Preference Regret
Apr 4, 2026Viet Dung Nguyen, Yuhang Song, Anh Nguyen +3Learning from Demonstration Robot Imitation Learning
Rochester Institute of Technology · Advanced Micro Devices, Inc. · University of Liverpool
Optimistic Online LQR via Intrinsic Rewards
Mar 30, 2026Marcell Bartos, Bruce D. Lee, Lenart Treven +3Linear Quadratic Regulator Regret Minimization in RL
ETH Zürich, Zürich, Switzerland
Functional Natural Policy Gradients
Mar 30, 2026Aurelien Bibaut, Houssam Zenati, Thibaud Rahier +1Cross-Fitting Natural Policy Gradient
Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards
Mar 29, 2026Kihyun Yu, Seoungbin Bae, Dabeen LeeAdversarial MARL Reinforcement Learning
Department of Industrial and Systems Engineering, KAIST · Department of Mathematical Sciences, Seoul National University · Research Institute of Mathematics, Seoul National University +2
Reinforcement learning for quantum processes with memory
Mar 26, 2026Josep Lumbreras, Ruo Cheng Huang, Yanglin Hu +2Quantum RL Regret Minimization in RL
Nanyang Quantum Hub, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore · Centre for Quantum Technologies, Nanyang Technological University, Singapore · QICI Quantum Information and Computation Initiative, School of Computing and Data Science, The University of Hong Kong, Pokfulam Road, Hong Kong SAR, China +2
Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
Mar 25, 2026Guy Zamir, Matthew Zurek, Yudong ChenRegret Minimization in RL Average-Reward RL
Department of Computer Sciences, University of Wisconsin–Madison
Regret Bounds for Reinforcement Learning from Multi-Source Imperfect Preferences
Mar 20, 2026Ming Shi, Yingbin Liang, Ness B. Shroff +1Preference-Based RL RL from Human Feedback
Department of Electrical Engineering, University at Buffalo, Buffalo, NY 14260, USA · Department of Electrical and Computer Engineering, The Ohio State University, Columbus, OH 43210, USA · Department of Electrical and Computer Engineering and Computer Science and Engineering, The Ohio State University, Columbus, OH 43210, USA +1
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 +1RL Control Regret Minimization in RL
Carnegie Mellon University · University of Oxford · Technical University of Darmstadt +2
Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learning
Mar 3, 2026Harin Lee, Kevin JamiesonDelayed RL Reinforcement Learning
Paul G. Allen School of Computer Science & Engineering, University of Washington, Seattle, Washington.
Learning in Markov Decision Processes with Exogenous Dynamics
Mar 3, 2026Davide Maran, Davide Salaorni, Marcello RestelliMarkov Decision Processes Sample-Efficient RL
Department of DEIB, Politecnico di Milano, Milan, Italy.
Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Values
Mar 1, 2026Shengbo Wang, Nian SiRobust Markov Decision Processes Average-Reward RL
Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California · Department of Industrial Engineering and Decision Analytics, Hong Kong University of Science and Technology
Frozen Policy Iteration: Computationally Efficient RL under Linear $Q^π$ Realizability for Deterministic Dynamics
Feb 28, 2026Yijing Ke, Zihan Zhang, Ruosong WangRegret Minimization in RL Policy Iteration
School of EECS, Peking University · Department of Computer Science and Engineering, HKUST · CFCS and School of Computer Science, Peking University
Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences
Feb 26, 2026Junghyun Lee, Minju Hong, Kwang-Sung Jun +2Regret Minimization in RL Preference-Based RL
KAIST AI · KAIST EE · POSTECH CSE/AI
Understanding Gap-Dependent Regret for Optimism-Based Reinforcement Learning with Linear Function Approximation
Feb 23, 2026Haochen Zhang, Zhong Zheng, Lingzhou XueRegret Minimization in RL Reinforcement Learning
Department of Statistics, The Pennsylvania State University · Department of Applied and Computational Mathematics and Statistics, University of Notre Dame
Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chains
Feb 18, 2026Rahul Singh, Siddharth Chandak, Eric Moulines +2Regret Minimization in RL Q-Learning
MBZUAI, UAE · Stanford University, USA · EPITA, France +1
Data- and Variance-dependent Regret Bounds for Online Tabular MDPs
Feb 2, 2026Mingyi Li, Taira Tsuchiya, Kenji YamanishiRegret Minimization in RL Markov Decision Processes
Department of Mathematical Informatics, The University of Tokyo, Tokyo, Japan · RIKEN AIP, Tokyo, Japan
Reinforcement Learning in MDPs with Information-Ordered Policies
Aug 5, 2025Zhongjun Zhang, Shipra Agrawal, Ilan Lobel +2Queueing Theory Policy Learning
Department of Industrial Engineering and Management Sciences, Northwestern University · Department of Industrial Engineering and Operations Research, Columbia University · Technology, Operations, and Statistics, Stern School of Business, New York University +1
Safe Learning Under Irreversible Dynamics via Asking for Help
Feb 19, 2025Benjamin Plaut, Juan Liévano-Karim, Hanlin Zhu +1Regret Minimization in RL Reinforcement Learning
Division of Computer Science University of California Berkeley, CA 94720-1776, USA
Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learning
Sep 22, 2024Jia Wan, Sean R. Sinclair, Devavrat Shah +1Regret Minimization in RL Markov Decision Processes
Laboratory for Information and Decision Systems, Massachusetts Institute of Technology · Department of Industrial Engineering and Management Sciences, Northwestern University
Thompson Sampling for Infinite-Horizon Discounted Decision Processes
May 14, 2024Daniel Adelman, Cagla Keceli, Alba V. Olivares-NadalThompson Sampling Regret Minimization in RL
Booth School of Business, The University of Chicago, Chicago, IL 60637, USA · United Airlines, Chicago, IL 60605, USA · UNSW Business School, UNSW, Kensington NSW 2033, Australia

May 27, 2026J/K move · Enter open · S save

Variance-Adaptive Optimal Algorithm for Reinforcement Learning with Multinomial Logit Function Approximation

Wonyoung Kim, Min-Hwan Oh, Garud Iyengar, Assaf Zeevi

Chung-Ang University · Seoul National University · Columbia University

Regret Minimization in RL Reinforcement Learning Policy Learning Function Approximation in RL

Open paper AskPDF arXiv

Reinforcement learning with multinomial logistic (MNL) function approximation has become an important framework due to its flexibility and broad applicability. While existing studies have established regret guarantees under worst-case analysis, they do not capture how performance depends on the variability of the interaction between the learner and the environment. In this paper, we develop a new theoretical analysis for MNL-based Markov decision processes that yields explicit variance-adaptive regret bounds. Our algorithm is computationally efficient and achieves the instance-wise optimal rate of regret, narrowing the gap between upper and lower bounds. Our numerical experiments validate that our method learns optimal policies more efficiently than conventional approaches.