mlsanityData to 7 Oct 2026

Beyond Optimism: Exploration With Partially Observable Rewards

arXiv 2406.13909 ↗First posted 20 Jun 2024cs.LGcited by 6

Not on the map. Why?

Abstract (arXiv)

Exploration in reinforcement learning (RL) remains an open challenge. RL algorithms rely on observing rewards to train the agent, and if informative rewards are sparse the agent learns slowly or may not learn at all. To improve exploration and reward discovery, popular algorithms rely on optimism. But what if sometimes rewards are unobservable, e.g., situations of partial monitoring in bandits and the recent formalism of monitored Markov decision process? In this case, optimism can lead to suboptimal behavior that does not explore further to collapse uncertainty. With this paper, we present a novel exploration strategy that overcomes the limitations of existing methods and guarantees convergence to an optimal policy even when rewards are not always observable. We further propose a collection of tabular environments for benchmarking exploration in RL (with and without unobservable rewards) and show that our method outperforms existing ones.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 46 of its 83 references that are in the map. First posted on arXiv 20 Jun 2024.

Builds on

46 of 83 references.

References · 46

  1. 2015Continuous control with deep reinforcement learningcited by 3,279
  2. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  3. 2019Mastering Atari, Go, Chess and Shogi by Planning with a Learned Modelcited by 1,327
  4. 2017Curiosity-driven Exploration by Self-supervised Predictioncited by 1,173
  5. 2015Prioritized Experience Replaycited by 1,070
  6. 2018Exploration by Random Network Distillationcited by 966
  7. 2016Unifying Count-Based Exploration and Intrinsic Motivationcited by 632
  8. 2018Is Q-learning Provably Efficient?cited by 485
  9. 2016Successor Features for Transfer in Reinforcement Learningcited by 331
  10. 2019Reinforcement Learning in Healthcare: A Surveycited by 308
  11. 2016#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learningcited by 307
  12. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
34 more
  1. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  2. 2014Learning to Optimize via Information-Directed Samplingcited by 168
  3. 2022Exploration in Deep Reinforcement Learning: A Surveycited by 158
  4. 2017Deep Exploration via Randomized Value Functionscited by 155
  5. 2015Incentivizing Exploration In Reinforcement Learning With Deep Predictive Modelscited by 154
  6. 2020RIDE: Rewarding Impact-Driven Exploration for Procedurally-Generated Environmentscited by 135
  7. 2019Fast Task Inference with Variational Intrinsic Successor Featurescited by 131
  8. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 116
  9. 2018Count-Based Exploration with the Successor Representationcited by 112
  10. 2017Surprise-Based Intrinsic Motivation for Deep Reinforcement Learningcited by 83
  11. 2020Active Learning for Nonlinear System Identification with Guaranteescited by 78
  12. 2021Tactical Optimism and Pessimism for Deep Reinforcement Learningcited by 55
  13. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 53
  14. 2021Temporal Abstraction in Reinforcement Learning with the Successor Representationcited by 52
  15. 2016The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Banditscited by 48
  16. 2017Count-Based Exploration in Feature Space for Reinforcement Learningcited by 48
  17. 2019An Information-Theoretic Approach to Minimax Regret in Partial Monitoringcited by 41
  18. 2020Information Directed Sampling for Linear Partial Monitoringcited by 39
  19. 2021Interesting Object, Curious Agent: Learning Task-Agnostic Explorationcited by 38
  20. 2023Optimistic Active Exploration of Dynamical Systemscited by 32
  21. 2023Deep Laplacian-based Options for Temporally-Extended Explorationcited by 28
  22. 2023Planning Goals for Explorationcited by 28
  23. 2023Flipping Coins to Estimate Pseudocounts for Exploration in Reinforcement Learningcited by 28
  24. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  25. 2022An information-theoretic perspective on intrinsic motivation in reinforcement learning: a surveycited by 25
  26. 2021Information Directed Reward Learning for Reinforcement Learningcited by 24
  27. 2020Active Reinforcement Learning: Observing Rewards at a Costcited by 20
  28. 2019Explicit Explore-Exploit Algorithms in Continuous State Spacescited by 19
  29. 2018Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processescited by 14
  30. 2018Active Reinforcement Learning with Monte-Carlo Tree Searchcited by 11
  31. 2023Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applicationscited by 11
  32. 2024Monitored Markov Decision Processescited by 9
  33. 2021Successor Feature Representationscited by 6
  34. 2020Long-Term Visitation Value for Deep Exploration in Sparse Reward Reinforcement Learningcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 5; 2026: 1.

6 papers.

  1. 2026TIDE: Trajectory-based Diagnostic Evaluation of Test-Time Improvement in LLM Agentscited by 7
  2. 2025Model-Based Exploration in Monitored Markov Decision Processescited by 1
  3. 2025Generalization in Monitored Markov Decision Processes (Mon-MDPs)cited by 1
  4. 2025Active Measuring in Reinforcement Learning With Delayed Negative Effectscited by 1
  5. 2025Which Rewards Matter? Reward Selection for Reinforcement Learning under Limited Feedbackcited by 0
  6. 2025Optimizing Algorithms for Mobile Health Interventions with Active Querying Optimizationcited by 0