Regret Minimization in RL

RL: Reinforcement Learning

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

70 papers13 papers in the last four weeks, up 18% on the four weeks before. 0.1% of all new papers.

  1. Improved Regret via Variance-Aware Policy Optimization in Adversarial MDPs

    Nov 12, 2026Ofir Schlisselberg, Alon Cohen, Yishay MansourRegret Minimization in RLMarkov Decision Processes

  2. Introducing Feedback Delays to Non-Delayed Adversarial MDPs: Optimal S\sqrt S and K\sqrt K Dependencies in Tabular and Linear AMDPs

    Nov 12, 2026Aarush Kulkarni, Khang Nguyen, William Chang +1Regret Minimization in RLMarkov Decision Processes

  3. OPSRL-SSP: Optimistic Posterior Sampling for Stochastic Shortest Path with Minimax-Optimal Regret

    Nov 8, 2026Yiming Xu, Xian Wei, Cheng ChenReinforcement LearningRegret Minimization in RL

  4. Finite-Time Convergence and Regret Guarantees for Neural Reinforcement Learning in POMDPs

    Nov 4, 2026Jingjuan Huang, Zhiyao Zhang, Alvaro Velasquez +2Partially Observable RLRegret Minimization in RL

  5. On the Feature Evolution of Temporal Difference Learning

    Nov 3, 2026Shangzhe Li, Dechen Zhang, Difan Zou +1Temporal-Difference LearningRepresentation Learning for RL

  6. Near-Optimal K\sqrt{K}-Regret for Online Learning in Uninformed Markov Games

    Nov 1, 2026Junyan Liu, Haipeng Luo, Lillian J. Ratliff +1Regret Minimization in RLGame-Theoretic RL

  7. Closing the Log Gap: Minimax-Optimal Regret for Episodic RL

    Oct 29, 2026Guy Zamir, Victor Boone, Matthew Zurek +1Episodic RLReinforcement Learning

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

    Oct 27, 2026Jose Blanchet, Lutong Hao, Renyuan Xufitted q-iterationRegret Minimization in RL

  9. Minimax Regret for Sobolev Kernel-Based Reinforcement Learning

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

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

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

  11. From POMDP Theory to Deep RL with Particle Filters

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

  12. 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

  13. What Information Buys in Active Inference

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

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

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

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

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

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

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

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

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

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

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

  19. Rate-Optimal Algorithm for Adversarial Linear CMDPs

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

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

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

  21. 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

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

    Sep 28, 2026Gefei Lin, Rui Miao, Xiaoke Zhangfitted q-iterationReinforcement Learning

  23. 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

  24. Risk-Sensitive Reinforcement Learning with Smoothed Quantile Objectives

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

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

    Aug 13, 2026Larissa Xu, King Bi, William ChangEpisodic RLRegret Minimization in RL

  26. 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

  27. 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