# Principled Exploration via Optimistic Bootstrapping and Backward Induction

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Builds on 43 of its 60 references that are in the map.
- First posted on arXiv 13 May 2021.

## Builds on (most cited first, 30 of 43)

- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Addressing Function Approximation Error in Actor-Critic Methods](https://mlsanity.com/paper/1802.09477/) (2018)
- [Dream to Control: Learning Behaviors by Latent Imagination](https://mlsanity.com/paper/1912.01603/) (2019)
- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [A Distributional Perspective on Reinforcement Learning](https://mlsanity.com/paper/1707.06887/) (2017)
- [Unifying Count-Based Exploration and Intrinsic Motivation](https://mlsanity.com/paper/1606.01868/) (2016)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Planning to Explore via Self-Supervised World Models](https://mlsanity.com/paper/2005.05960/) (2020)
- [#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/1611.04717/) (2016)
- [Large-Scale Study of Curiosity-Driven Learning](https://mlsanity.com/paper/1808.04355/) (2018)
- [Noisy Networks for Exploration](https://mlsanity.com/paper/1706.10295/) (2017)
- [Self-Supervised Exploration via Disagreement](https://mlsanity.com/paper/1906.04161/) (2019)
- [Count-Based Exploration with Neural Density Models](https://mlsanity.com/paper/1703.01310/) (2017)
- [Randomized Prior Functions for Deep Reinforcement Learning](https://mlsanity.com/paper/1806.03335/) (2018)
- [Never Give Up: Learning Directed Exploration Strategies](https://mlsanity.com/paper/2002.06038/) (2020)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Sample-Efficient Reinforcement Learning with Stochastic Ensemble Value Expansion](https://mlsanity.com/paper/1807.01675/) (2018)
- [Deep Exploration via Randomized Value Functions](https://mlsanity.com/paper/1703.07608/) (2017)
- [SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep Reinforcement Learning](https://mlsanity.com/paper/2007.04938/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Why is Posterior Sampling Better than Optimism for Reinforcement Learning?](https://mlsanity.com/paper/1607.00215/) (2016)
- [Optimism in Reinforcement Learning with Generalized Linear Function Approximation](https://mlsanity.com/paper/1912.04136/) (2019)
- [Episodic Curiosity through Reachability](https://mlsanity.com/paper/1810.02274/) (2018)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [Frequentist Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/1911.00567/) (2019)
- [Better Exploration with Optimistic Actor-Critic](https://mlsanity.com/paper/1910.12807/) (2019)

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

- [Pessimistic Bootstrapping for Uncertainty-Driven Offline Reinforcement Learning](https://mlsanity.com/paper/2202.11566/) (2022)
- [RORL: Robust Offline Reinforcement Learning via Conservative Smoothing](https://mlsanity.com/paper/2206.02829/) (2022)
- [Exploration in Deep Reinforcement Learning: From Single-Agent to Multiagent Domain](https://mlsanity.com/paper/2109.06668/) (2021)
- [Cross-Domain Policy Adaptation via Value-Guided Data Filtering](https://mlsanity.com/paper/2305.17625/) (2023)
- [CDE: Curiosity-Driven Exploration for Efficient Reinforcement Learning in Large Language Models](https://mlsanity.com/paper/2509.09675/) (2025)
- [Behavior Contrastive Learning for Unsupervised Skill Discovery](https://mlsanity.com/paper/2305.04477/) (2023)
- [From Dirichlet to Rubin: Optimistic Exploration in RL without Bonuses](https://mlsanity.com/paper/2205.07704/) (2022)
- [Dynamic Bottleneck for Robust Self-Supervised Exploration](https://mlsanity.com/paper/2110.10735/) (2021)
- [Seizing Serendipity: Exploiting the Value of Past Success in Off-Policy Actor-Critic](https://mlsanity.com/paper/2306.02865/) (2023)
- [Posterior Sampling for Deep Reinforcement Learning](https://mlsanity.com/paper/2305.00477/) (2023)
- [Constrained Ensemble Exploration for Unsupervised Skill Discovery](https://mlsanity.com/paper/2405.16030/) (2024)
- [Anti-Concentrated Confidence Bonuses for Scalable Exploration](https://mlsanity.com/paper/2110.11202/) (2021)
- [OVD-Explorer: Optimism Should Not Be the Sole Pursuit of Exploration in Noisy Environments](https://mlsanity.com/paper/2312.12145/) (2023)
- [Pessimistic Value Iteration for Multi-Task Data Sharing in Offline Reinforcement Learning](https://mlsanity.com/paper/2404.19346/) (2024)
- [Constrained Intrinsic Motivation for Reinforcement Learning](https://mlsanity.com/paper/2407.09247/) (2024)
- [Model-Free Active Exploration in Reinforcement Learning](https://mlsanity.com/paper/2407.00801/) (2024)
- [Deep Exploration with PAC-Bayes](https://mlsanity.com/paper/2402.03055/) (2024)
- [Learning Uncertainty-Aware Temporally-Extended Actions](https://mlsanity.com/paper/2402.05439/) (2024)
- [Uncertainty-Aware Rank-One MIMO Q Network Framework for Accelerated Offline Reinforcement Learning](https://mlsanity.com/paper/2602.19917/) (2026)
- [Adaptive trajectory-constrained exploration strategy for deep reinforcement learning](https://mlsanity.com/paper/2312.16456/) (2023)
- [CIM: Constrained Intrinsic Motivation for Sparse-Reward Continuous Control](https://mlsanity.com/paper/2211.15205/) (2022)
- [Ensemble Successor Representations for Task Generalization in Offline-to-Online Reinforcement Learning](https://mlsanity.com/paper/2405.07223/) (2024)
- [Exploration and Online Transfer with Behavioral Foundation Models](https://mlsanity.com/paper/2606.29980/) (2026)
- [Offline Reinforcement Learning with Adaptive Behavior Regularization](https://mlsanity.com/paper/2211.08251/) (2022)
- [Stability of Multi-Agent Learning: Convergence in Network Games with Many Players](https://mlsanity.com/paper/2307.13922/) (2023)
- [A Tighter Convergence Proof of Reverse Experience Replay](https://mlsanity.com/paper/2408.16999/) (2024)

## Abstract (arXiv)

One principled approach for provably efficient exploration is incorporating the upper confidence bound (UCB) into the value function as a bonus. However, UCB is specified to deal with linear and tabular settings and is incompatible with Deep Reinforcement Learning (DRL). In this paper, we propose a principled exploration method for DRL through Optimistic Bootstrapping and Backward Induction (OB2I). OB2I constructs a general-purpose UCB-bonus through non-parametric bootstrap in DRL. The UCB-bonus estimates the epistemic uncertainty of state-action pairs for optimistic exploration. We build theoretical connections between the proposed UCB-bonus and the LSVI-UCB in a linear setting. We propagate future uncertainty in a time-consistent manner through episodic backward update, which exploits the theoretical advantage and empirically improves the sample-efficiency. Our experiments in the MNIST maze and Atari suite suggest that OB2I outperforms several state-of-the-art exploration approaches.