# Beyond Optimism: Exploration With Partially Observable Rewards

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Placed in Deep RL algorithms and representations, one of 15 directions in Deep reinforcement learning methods.
- Builds on 46 of its 83 references that are in the map.
- First posted on arXiv 20 Jun 2024.

## Placed in

- Deep reinforcement learning methods / [Deep RL algorithms and representations](https://mlsanity.com/deeprl/deep-rl-algorithms-and-representations/)

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

- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [Prioritized Experience Replay](https://mlsanity.com/paper/1511.05952/) (2015)
- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [Unifying Count-Based Exploration and Intrinsic Motivation](https://mlsanity.com/paper/1606.01868/) (2016)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Successor Features for Transfer in Reinforcement Learning](https://mlsanity.com/paper/1606.05312/) (2016)
- [Reinforcement Learning in Healthcare: A Survey](https://mlsanity.com/paper/1908.08796/) (2019)
- [#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/1611.04717/) (2016)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [Exploration in Deep Reinforcement Learning: A Survey](https://mlsanity.com/paper/2205.00824/) (2022)
- [Deep Exploration via Randomized Value Functions](https://mlsanity.com/paper/1703.07608/) (2017)
- [Incentivizing Exploration In Reinforcement Learning With Deep Predictive Models](https://mlsanity.com/paper/1507.00814/) (2015)
- [RIDE: Rewarding Impact-Driven Exploration for Procedurally-Generated Environments](https://mlsanity.com/paper/2002.12292/) (2020)
- [Fast Task Inference with Variational Intrinsic Successor Features](https://mlsanity.com/paper/1906.05030/) (2019)
- [Why is Posterior Sampling Better than Optimism for Reinforcement Learning?](https://mlsanity.com/paper/1607.00215/) (2016)
- [Count-Based Exploration with the Successor Representation](https://mlsanity.com/paper/1807.11622/) (2018)
- [Surprise-Based Intrinsic Motivation for Deep Reinforcement Learning](https://mlsanity.com/paper/1703.01732/) (2017)
- [Active Learning for Nonlinear System Identification with Guarantees](https://mlsanity.com/paper/2006.10277/) (2020)
- [Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP](https://mlsanity.com/paper/1901.09311/) (2019)
- [Tactical Optimism and Pessimism for Deep Reinforcement Learning](https://mlsanity.com/paper/2102.03765/) (2021)
- [Temporal Abstraction in Reinforcement Learning with the Successor Representation](https://mlsanity.com/paper/2110.05740/) (2021)
- [The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits](https://mlsanity.com/paper/1610.04491/) (2016)
- [Count-Based Exploration in Feature Space for Reinforcement Learning](https://mlsanity.com/paper/1706.08090/) (2017)
- [An Information-Theoretic Approach to Minimax Regret in Partial Monitoring](https://mlsanity.com/paper/1902.00470/) (2019)
- [Information Directed Sampling for Linear Partial Monitoring](https://mlsanity.com/paper/2002.11182/) (2020)

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

- [TIDE: Trajectory-based Diagnostic Evaluation of Test-Time Improvement in LLM Agents](https://mlsanity.com/paper/2602.02196/) (2026)
- [Model-Based Exploration in Monitored Markov Decision Processes](https://mlsanity.com/paper/2502.16772/) (2025)
- [Generalization in Monitored Markov Decision Processes (Mon-MDPs)](https://mlsanity.com/paper/2505.08988/) (2025)
- [Active Measuring in Reinforcement Learning With Delayed Negative Effects](https://mlsanity.com/paper/2510.14315/) (2025)
- [Which Rewards Matter? Reward Selection for Reinforcement Learning under Limited Feedback](https://mlsanity.com/paper/2510.00144/) (2025)
- [Optimizing Algorithms for Mobile Health Interventions with Active Querying Optimization](https://mlsanity.com/paper/2512.08950/) (2025)

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