# A Unifying View of Optimism in Episodic Reinforcement Learning

arXiv: https://arxiv.org/abs/2007.01891 · HTML: https://mlsanity.com/paper/2007.01891/

## Key facts

- Cited by 52 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jul 2020.

## Built on by (most cited first, 30 of 52)

- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage](https://mlsanity.com/paper/2107.06226/) (2021)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage](https://mlsanity.com/paper/2305.09659/) (2023)
- [The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces](https://mlsanity.com/paper/2106.03352/) (2021)
- [Settling the Sample Complexity of Online Reinforcement Learning](https://mlsanity.com/paper/2307.13586/) (2023)
- [Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret](https://mlsanity.com/paper/2104.11186/) (2021)
- [Variance-Aware Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2106.11960/) (2021)
- [A General Framework for Sample-Efficient Function Approximation in Reinforcement Learning](https://mlsanity.com/paper/2209.15634/) (2022)
- [Provable Benefit of Multitask Representation Learning in Reinforcement Learning](https://mlsanity.com/paper/2206.05900/) (2022)
- [A Dataset Perspective on Offline Reinforcement Learning](https://mlsanity.com/paper/2111.04714/) (2021)
- [Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies](https://mlsanity.com/paper/2203.12922/) (2022)
- [Proximal Point Imitation Learning](https://mlsanity.com/paper/2209.10968/) (2022)
- [Kernelized Reinforcement Learning with Order Optimal Regret Bounds](https://mlsanity.com/paper/2306.07745/) (2023)
- [Active Exploration via Experiment Design in Markov Chains](https://mlsanity.com/paper/2206.14332/) (2022)
- [Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environments](https://mlsanity.com/paper/2301.13446/) (2023)
- [Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning](https://mlsanity.com/paper/2111.00633/) (2021)
- [Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learning](https://mlsanity.com/paper/2202.10678/) (2022)
- [Optimistic PAC Reinforcement Learning: the Instance-Dependent View](https://mlsanity.com/paper/2207.05852/) (2022)
- [Near-Optimal Randomized Exploration for Tabular Markov Decision Processes](https://mlsanity.com/paper/2102.09703/) (2021)
- [Nesting Particle Filters for Experimental Design in Dynamical Systems](https://mlsanity.com/paper/2402.07868/) (2024)
- [BOFormer: Learning to Solve Multi-Objective Bayesian Optimization via Non-Markovian RL](https://mlsanity.com/paper/2505.21974/) (2025)
- [Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation](https://mlsanity.com/paper/2305.06446/) (2023)
- [Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimization](https://mlsanity.com/paper/2210.12057/) (2022)
- [Optimistic Planning by Regularized Dynamic Programming](https://mlsanity.com/paper/2302.14004/) (2023)
- [Epistemic Monte Carlo Tree Search](https://mlsanity.com/paper/2210.13455/) (2022)
- [Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyond](https://mlsanity.com/paper/2406.01386/) (2024)
- [SOMBRL: Scalable and Optimistic Model-Based RL](https://mlsanity.com/paper/2511.20066/) (2025)
- [On the Theory of Risk-Aware Agents: Bridging Actor-Critic and Economics](https://mlsanity.com/paper/2310.19527/) (2023)

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