mlsanityData to 14 Oct 2026

Principled Exploration via Optimistic Bootstrapping and Backward Induction

arXiv 2105.06022 ↗First posted 13 May 2021cs.LGcited by 26

Not on the map. Why?

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.

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

43 of 60 references.

References · 43

  1. 2015Continuous control with deep reinforcement learningcited by 3,407
  2. 2018Addressing Function Approximation Error in Actor-Critic Methodscited by 2,417
  3. 2019Dream to Control: Learning Behaviors by Latent Imaginationcited by 1,653
  4. 2017Curiosity-driven Exploration by Self-supervised Predictioncited by 1,194
  5. 2018Exploration by Random Network Distillationcited by 993
  6. 2017A Distributional Perspective on Reinforcement Learningcited by 765
  7. 2016Unifying Count-Based Exploration and Intrinsic Motivationcited by 639
  8. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
  9. 2016Deep Exploration via Bootstrapped DQNcited by 527
  10. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  11. 2018Is Q-learning Provably Efficient?cited by 487
  12. 2020Planning to Explore via Self-Supervised World Modelscited by 368
31 more
  1. 2016#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learningcited by 309
  2. 2018Large-Scale Study of Curiosity-Driven Learningcited by 280
  3. 2017Noisy Networks for Explorationcited by 266
  4. 2019Self-Supervised Exploration via Disagreementcited by 265
  5. 2017Count-Based Exploration with Neural Density Modelscited by 257
  6. 2018Randomized Prior Functions for Deep Reinforcement Learningcited by 219
  7. 2020Never Give Up: Learning Directed Exploration Strategiescited by 212
  8. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  9. 2018Sample-Efficient Reinforcement Learning with Stochastic Ensemble Value Expansioncited by 168
  10. 2017Deep Exploration via Randomized Value Functionscited by 156
  11. 2020SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep Reinforcement Learningcited by 152
  12. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  13. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 117
  14. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  15. 2018Episodic Curiosity through Reachabilitycited by 109
  16. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 106
  17. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  18. 2019Better Exploration with Optimistic Actor-Criticcited by 88
  19. 2020Efficient Model-Based Reinforcement Learning through Optimistic Policy Search and Planningcited by 86
  20. 2017The Uncertainty Bellman Equation and Explorationcited by 82
  21. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  22. 2018Efficient Exploration through Bayesian Deep Q-Networkscited by 67
  23. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  24. 2018Information-Directed Exploration for Deep Reinforcement Learningcited by 52
  25. 2020Ready Policy One: World Building Through Active Learningcited by 33
  26. 2017Posterior sampling for reinforcement learning: worst-case regret boundscited by 29
  27. 2018Sample-Efficient Deep Reinforcement Learning via Episodic Backward Updatecited by 29
  28. 2018Contingency-Aware Exploration in Reinforcement Learningcited by 26
  29. 2020Optimistic Exploration even with a Pessimistic Initialisationcited by 25
  30. 2020Variational Dynamic for Self-Supervised Exploration in Deep Reinforcement Learningcited by 9
  31. 2019Implicit Generative Modeling for Efficient Explorationcited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 3; 2022: 5; 2023: 7; 2024: 8; 2025: 1; 2026: 2.

26 papers.

Sort:

By area:

  1. 2022Pessimistic Bootstrapping for Uncertainty-Driven Offline Reinforcement Learningcited by 125
  2. 2022RORL: Robust Offline Reinforcement Learning via Conservative Smoothingcited by 84
  3. 2021Exploration in Deep Reinforcement Learning: From Single-Agent to Multiagent Domaincited by 58
  4. 2023Cross-Domain Policy Adaptation via Value-Guided Data Filteringcited by 31
  5. 2025CDE: Curiosity-Driven Exploration for Efficient Reinforcement Learning in Large Language Modelscited by 29
  6. 2023Behavior Contrastive Learning for Unsupervised Skill Discoverycited by 26
  7. 2022From Dirichlet to Rubin: Optimistic Exploration in RL without Bonusescited by 22
  8. 2021Dynamic Bottleneck for Robust Self-Supervised Explorationcited by 21
  9. 2023Seizing Serendipity: Exploiting the Value of Past Success in Off-Policy Actor-Criticcited by 20
  10. 2023Posterior Sampling for Deep Reinforcement Learningcited by 16
  11. 2024Constrained Ensemble Exploration for Unsupervised Skill Discoverycited by 8
  12. 2021Anti-Concentrated Confidence Bonuses for Scalable Explorationcited by 7
14 more
  1. 2023OVD-Explorer: Optimism Should Not Be the Sole Pursuit of Exploration in Noisy Environmentscited by 7
  2. 2024Pessimistic Value Iteration for Multi-Task Data Sharing in Offline Reinforcement Learningcited by 7
  3. 2024Constrained Intrinsic Motivation for Reinforcement Learningcited by 6
  4. 2024Model-Free Active Exploration in Reinforcement Learningcited by 5
  5. 2024Deep Exploration with PAC-Bayescited by 4
  6. 2024Learning Uncertainty-Aware Temporally-Extended Actionscited by 3
  7. 2026Uncertainty-Aware Rank-One MIMO Q Network Framework for Accelerated Offline Reinforcement Learningcited by 3
  8. 2023Adaptive trajectory-constrained exploration strategy for deep reinforcement learningcited by 2
  9. 2022CIM: Constrained Intrinsic Motivation for Sparse-Reward Continuous Controlcited by 1
  10. 2024Ensemble Successor Representations for Task Generalization in Offline-to-Online Reinforcement Learningcited by 1
  11. 2026Exploration and Online Transfer with Behavioral Foundation Modelscited by 1
  12. 2022Offline Reinforcement Learning with Adaptive Behavior Regularizationcited by 0
  13. 2023Stability of Multi-Agent Learning: Convergence in Network Games with Many Playerscited by 0
  14. 2024A Tighter Convergence Proof of Reverse Experience Replaycited by 0