Regret Minimization in RL

RL: Reinforcement Learning

Ask about this topic

Overview

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

CardsList

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

  1. Frequency-Uniform Log-Regret Reinforcement Learning for Diffusions

    Oct 27, 2026Jose Blanchet, Lutong Hao, Renyuan XuRegret Minimization in RLModel-Based RL

    Department of Management Science and Engineering, Stanford University.

  2. Minimax Regret for Sobolev Kernel-Based Reinforcement Learning

    Oct 25, 2026Haichen Hu, David Simchi-LeviRegret Minimization in RLReinforcement Learning

    Center for Computational Science and Engineering, MIT · Department of Civil and Environmental Engineering, MIT · Institute for Data, Systems, and Society, MIT

  3. Recommender regret for improving regularised RL estimation with bandits and MCTS

    Oct 23, 2026Danilo Vucetic, Alexandre Larouche, Mohammad Pedramfar +2Regularized RLReinforcement Learning

    Université de Montréal · Mila - Québec AI Institute · Université Laval +2

  4. From POMDP Theory to Deep RL with Particle Filters

    Oct 20, 2026Kevin Tan, Ziping XuPartially Observable RLModel-Based RL

    Wharton Statistics and Data Science, University of Pennsylvania · School of Data and Information Sciences, University of North Carolina at Chapel Hill

  5. Towards instance-dependent regret optimality in Episodic MDPs with Posterior Sampling

    Oct 19, 2026Victor Boone, Cyrille Kone, Waris Radji +2Regret Minimization in RLMarkov Decision Processes

    IRIT, Université de Toulouse, CNRS, Toulouse INP, Toulouse, France · LAAS-CNRS, Université de Toulouse, CNRS, Toulouse, France · Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189-CRIStAL, F-59000 Lille, France +1

  6. What Information Buys in Active Inference

    Oct 13, 2026Melih Kandemir, Mustafa Mert ÇelikokRL ExplorationActive Inference

    Department of Mathematics and Computer Science, University of Southern Denmark

  7. Conformal Sequential Decision Making With Cost and Sublinear Policy Regret Guarantees

    Oct 10, 2026Jayadev Naram, Giuseppe Durisi, Matteo Zecchin +1Sequential Decision MakingOnline Learning

    Department of Electrical Engineering, Chalmers University of Technology, 412 96 Göteborg, Sweden · Communication Systems Department, EURECOM, 06410 Sophia Antipolis, France · Institute for Intelligent Networked Systems (INSI), Northeastern University London, E1W 1LP London, UK

  8. Closing the Horizon Gap in Policy Optimization for Adversarial MDPs

    Oct 8, 2026Mingyi Li, Taira TsuchiyaRegret Minimization in RLMarkov Decision Processes

    The University of Tokyo · The University of Tokyo, The University of Osaka, and RIKEN

  9. Toward Optimal Regret in Adversarial MDPs with Stochastic Hard Constraints

    Oct 8, 2026Qian Zuo, Francesco Emanuele StradiMarkov Decision ProcessesConstrained RL

    University of Edinburgh · Politecnico di Milano

  10. Reinforcement Learning with Segment Reward Feedback under Linear Function Approximation

    Oct 6, 2026Fengxu Liu, Siwei Wang, Gal Dalal +2Regret Minimization in RLReinforcement Learning

    National University of Singapore. · Microsoft Research Asia. · NVIDIA Research. +2

  11. Variance-Aware Fine-Grained Gap-Dependent Bounds for Online Reinforcement Learning

    Oct 3, 2026Haochen Zhang, Lingzhou Xue, Zhong ZhengReinforcement LearningModel-Free RL

    Department of Statistics, The Pennsylvania State University · Department of Applied and Computational Mathematics and Statistics, University of Notre Dame

  12. Rate-Optimal Algorithm for Adversarial Linear CMDPs

    Oct 1, 2026Kihyun Yu, Honghao Wei, Dabeen LeeRegret Minimization in RLMarkov Decision Processes

    KAIST · Washington State University · Seoul National University

  13. Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation

    Sep 30, 2026Kihyun Yu, Seoungbin Bae, Dabeen LeeRegret Minimization in RLMarkov Decision Processes

    KAIST · Seoul National University

  14. Pointwise or Pairwise: When Do Pairwise Losses Help Reward Learning, Provably?

    Sep 29, 2026Junghyun Lee, Minsoo Ha, Sanghwa Kim +4Offline-to-Online Contextual BanditsContextual Bandits

    Kim Jaechul Graduate School of AI, KAIST Seoul 02455, Republic of Korea · Graduate School of AI, POSTECH Pohang 37673, Republic of Korea · Samsung Research Seoul 06765, Republic of Korea +1

  15. Finite-Sample Theory for Fitted Q-Iteration When Actions Are Functions

    Sep 28, 2026Gefei Lin, Rui Miao, Xiaoke ZhangReinforcement LearningOffline RL

    Department of Statistics, The George Washington University · Department of Mathematical Sciences, The University of Texas at Dallas

  16. Minimax-Optimality of Posterior Sampling for Reinforcement Learning

    Sep 27, 2026Taewon Goo, Kihyuk HongRegret Minimization in RLMarkov Decision Processes

    KAIST

  17. Provably Efficient Reinforcement Learning in Continuous-Time Episodic MDPs with Poisson Decision Epochs

    Sep 19, 2026Kenny Guo, Valentio Iverson, Sahan Wijetunga +1Markov Decision ProcessesContinuous-Time RL

    Department of Economics, Yale University, New Haven, Connecticut, USA · Department of Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA · Department of Mathematics, University of California, Los Angeles, Los Angeles, California, USA

  18. Continuity-Free Near-Minimax Leading-Order Regret for CVaR-UCBVI

    Aug 29, 2026Yuanlong ChenRegret Minimization in RLRisk-Sensitive RL

  19. Risk-Sensitive Reinforcement Learning with Smoothed Quantile Objectives

    Aug 23, 2026Mohammad Alipour-Vaezi, Huaiyang Zhong, Sajad KhodadadianRisk-Sensitive RLRegret Minimization in RL

    Grado Department of Industrial & Systems Engineering, Virginia Tech, Blacksburg, VA 24061, USA

  20. Decentralized Multi-Player Q-Learning in Episodic Markov Decision Processes with Information Asymmetry

    Aug 13, 2026Larissa Xu, King Bi, William ChangRegret Minimization in RLReinforcement Learning

    Department of Mathematics University of California, Los Angeles Los Angeles, USA · Department of Computer Science University of California, Los Angeles Los Angeles, USA

  21. Finite Constant Frontiers and Auditable Regret Certificates for Average-Reward Reinforcement Learning

    Aug 7, 2026Ibne Farabi Shihab, Abu Sa-Adat Mohamed Moon-Im Al Ahsan, Md Najmus SwaqeebRegret Minimization in RLMarkov Decision Processes

    Department of Computer Science, Iowa State University · Department of Computer Science & Engineering, BRAC University

  22. Convergence and Regret of the Policy Gradient for Multi-Armed Bandits in Diffusion Environment

    Jul 31, 2026Yanwei Jia, Du OuyangMulti-Armed BanditsRegret Minimization in RL

    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

  23. A Unified Algorithmic Framework for Hybrid Reinforcement Learning in Tabular MDPs with Shifted Transition Dynamics

    Jul 28, 2026Zheshun Wu, Renjie Zheng, Jinhang Zuo +2Non-Stationary RLRegret Minimization in RL

    Southern University of Science and Technology · Harbin Institute of Technology, Shenzhen Shenzhen, Guangdong, China · Southern University of Science and Technology Shenzhen, Guangdong, China +4

  24. Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence

    Jul 22, 2026Runlong Zhou, Zihan Zhang, Maryam Fazel +1Regret Minimization in RLMarkov Decision Processes

    University of Washington. · Hong Kong University of Science and Technology. · §University of Washington. +1

  25. Policy Optimization Achieves Data-Dependent Regret Bounds in MDPs with Unknown Transitions

    Jun 30, 2026Mingyi Li, Taira Tsuchiya, Kenji YamanishiRegret Minimization in RLMarkov Decision Processes

    Department of Mathematical Informatics, The University of Tokyo · Center for Advanced Intelligence Project, RIKEN

  26. Quantile of Means: A Bonus-Free Ensemble Method for Minimax Optimal Reinforcement Learning

    Jun 18, 2026Asaf Cassel, Aviv RosenbergRegret Minimization in RLReinforcement Learning

    Google Research

  27. A Regret Minimization Framework on Preference Learning in Large Language Models

    Jun 8, 2026Suhwan Kim, Taehyun Cho, Geon-Hyeong Kim +4Regret Minimization in RLLLM Alignment

    Seoul National University, Seoul, South Korea · LG AI Research, Seoul, South Korea · UNIST, Ulsan, South Korea +1

  28. Online KL-Regularized Reinforcement Learning with Function Approximation under Misspecification

    Jun 4, 2026Haoyang Hong, Zichen Wang, Quanquan Gu +1Regret Minimization in RLReinforcement Learning

    School of Electrical Engineering and Computer Science, Oregon State University · Department of Electrical and Computer Engineering and Coordinated Science Laboratory, University of Illinois Urbana-Champaign · Department of Computer Science, University of California, Los Angeles

  29. Minimax-Optimal Policy Regret in Partially Observable Markov Games

    Jun 1, 2026Raman AroraRegret Minimization in RLImperfect-Information Games

    Department of Computer Science, Johns Hopkins University, Baltimore, MD, USA.

  30. Information-Directed Offline-to-Online Reinforcement Learning

    May 28, 2026Keru ChenRegret Minimization in RLBayesian RL

    School of Electrical, Computer and Energy Engineering, Arizona State University