# Optimistic Planning by Regularized Dynamic Programming

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 40 references that are in the map.
- First posted on arXiv 27 Feb 2023.

## Builds on (most cited first, 16 of 16)

- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [A unified view of entropy-regularized Markov decision processes](https://mlsanity.com/paper/1705.07798/) (2017)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles](https://mlsanity.com/paper/1910.10597/) (2019)
- [Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning](https://mlsanity.com/paper/1802.04020/) (2018)
- [A Unifying View of Optimism in Episodic Reinforcement Learning](https://mlsanity.com/paper/2007.01891/) (2020)
- [Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2007.11849/) (2020)
- [Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs](https://mlsanity.com/paper/2010.00587/) (2020)
- [Regret Bounds for Discounted MDPs](https://mlsanity.com/paper/2002.05138/) (2020)
- [Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation](https://mlsanity.com/paper/2105.01593/) (2021)
- [Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planning](https://mlsanity.com/paper/2210.02087/) (2022)
- [Exploration Bonus for Regret Minimization in Undiscounted Discrete and Continuous Markov Decision Processes](https://mlsanity.com/paper/1812.04363/) (2018)

## Built on by (most cited first, 8 of 8)

- [Imitation Learning in Discounted Linear MDPs without exploration assumptions](https://mlsanity.com/paper/2405.02181/) (2024)
- [Operator World Models for Reinforcement Learning](https://mlsanity.com/paper/2406.19861/) (2024)
- [SOMBRL: Scalable and Optimistic Model-Based RL](https://mlsanity.com/paper/2511.20066/) (2025)
- [Bisimulation Metrics are Optimal Transport Distances, and Can be Computed Efficiently](https://mlsanity.com/paper/2406.04056/) (2024)
- [IL-SOAR : Imitation Learning with Soft Optimistic Actor cRitic](https://mlsanity.com/paper/2502.19859/) (2025)
- [Inverse Q-Learning Done Right: Offline Imitation Learning in Qπ-Realizable MDPs](https://mlsanity.com/paper/2505.19946/) (2025)
- [Offline and Online KL-Regularized RLHF under Differential Privacy](https://mlsanity.com/paper/2510.13512/) (2025)
- [Value Mirror Descent for Reinforcement Learning](https://mlsanity.com/paper/2604.06039/) (2026)

## Abstract (arXiv)

We propose a new method for optimistic planning in infinite-horizon discounted Markov decision processes based on the idea of adding regularization to the updates of an otherwise standard approximate value iteration procedure. This technique allows us to avoid contraction and monotonicity arguments typically required by existing analyses of approximate dynamic programming methods, and in particular to use approximate transition functions estimated via least-squares procedures in MDPs with linear function approximation. We use our method to recover known guarantees in tabular MDPs and to provide a computationally efficient algorithm for learning near-optimal policies in discounted linear mixture MDPs from a single stream of experience, and show it achieves near-optimal statistical guarantees.