mlsanityData to 13 Oct 2026

A Unifying View of Optimism in Episodic Reinforcement Learning

arXiv 2007.01891 ↗First posted 3 Jul 2020cs.LG stat.MLcited by 51

Not on the map. Why?

Abstract (arXiv)

The principle of optimism in the face of uncertainty underpins many theoretically successful reinforcement learning algorithms. In this paper we provide a general framework for designing, analyzing and implementing such algorithms in the episodic reinforcement learning problem. This framework is built upon Lagrangian duality, and demonstrates that every model-optimistic algorithm that constructs an optimistic MDP has an equivalent representation as a value-optimistic dynamic programming algorithm. Typically, it was thought that these two classes of algorithms were distinct, with model-optimistic algorithms benefiting from a cleaner probabilistic analysis while value-optimistic algorithms are easier to implement and thus more practical. With the framework developed in this paper, we show that it is possible to get the best of both worlds by providing a class of algorithms which have a computationally efficient dynamic-programming implementation and also a simple probabilistic analysis. Besides being able to capture many existing algorithms in the tabular setting, our framework can also address largescale problems under realizable function approximation, where it enables a simple model-based analysis of some recently proposed methods.

Key facts. Cited by 51 papers in the map (data through 13 Oct 2026). First posted on arXiv 3 Jul 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2021: 11; 2022: 13; 2023: 9; 2024: 8; 2025: 6; 2026: 4.

51 papers.

Sort:

By area:

  1. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  2. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 161
  3. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  4. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  5. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
  6. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  7. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  8. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  9. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  10. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  11. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  12. 2021A Dataset Perspective on Offline Reinforcement Learningcited by 27
38 more
  1. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  2. 2022Proximal Point Imitation Learningcited by 25
  3. 2023Kernelized Reinforcement Learning with Order Optimal Regret Boundscited by 20
  4. 2022Active Exploration via Experiment Design in Markov Chainscited by 19
  5. 2022Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learningcited by 18
  6. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 18
  7. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 17
  8. 2022Optimistic PAC Reinforcement Learning: the Instance-Dependent Viewcited by 17
  9. 2021Near-Optimal Randomized Exploration for Tabular Markov Decision Processescited by 15
  10. 2024Nesting Particle Filters for Experimental Design in Dynamical Systemscited by 12
  11. 2023Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximationcited by 9
  12. 2025BOFormer: Learning to Solve Multi-Objective Bayesian Optimization via Non-Markovian RLcited by 9
  13. 2022Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimizationcited by 8
  14. 2023Optimistic Planning by Regularized Dynamic Programmingcited by 8
  15. 2022Epistemic Monte Carlo Tree Searchcited by 7
  16. 2024Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyondcited by 7
  17. 2025SOMBRL: Scalable and Optimistic Model-Based RLcited by 7
  18. 2023On the Theory of Risk-Aware Agents: Bridging Actor-Critic and Economicscited by 6
  19. 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximationcited by 5
  20. 2021Optimism and Delays in Episodic Reinforcement Learningcited by 4
  21. 2022Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processescited by 4
  22. 2023Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPscited by 4
  23. 2023Does Sparsity Help in Learning Misspecified Linear Bandits?cited by 3
  24. 2024Behind the Myth of Exploration in Policy Gradientscited by 3
  25. 2024Efficient Model-Based Reinforcement Learning Through Optimistic Thompson Samplingcited by 3
  26. 2022Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPscited by 2
  27. 2024Offline RL via Feature-Occupancy Gradient Ascentcited by 2
  28. 2024e-COP : Episodic Constrained Optimization of Policiescited by 2
  29. 2025TW-CRL: Time-Weighted Contrastive Reward Learning for Efficient Inverse Reinforcement Learningcited by 2
  30. 2024How does Your RL Agent Explore? An Optimal Transport Analysis of Occupancy Measure Trajectoriescited by 1
  31. 2025Near-Optimal Sample Complexity in Reward-Free Kernel-Based Reinforcement Learningcited by 1
  32. 2022Dynamic mean field programmingcited by 0
  33. 2022Convex duality for stochastic shortest path problems in known and unknown environmentscited by 0
  34. 2024Misspecified Q-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Errorcited by 0
  35. 2025Reinforcement Learning Using known Invariancescited by 0
  36. 2026Multi-Agent Reinforcement Learning with Submodular Rewardcited by 0
  37. 2026Mathematical methods of reinforcement learningcited by 0
  38. 2026Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependencecited by 0

50 most cited of 51 All 51 (JSON)