Research map / Reinforcement learning / MDPs and planning
Beyond Optimism: Exploration With Partially Observable Rewards
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a successor-representation-based directed exploration strategy that decouples exploration from the Q-function, guaranteeing GLIE convergence and outperforming optimism-based and count-based baselines on tabular MDPs and Monitored MDPs with unobservable rewards.
Problem
Exploration in reinforcement learning when rewards are not always observable (Monitored MDPs and partial monitoring), where optimistic and value-based exploration can converge to suboptimal policies because they never take the costly actions needed to reveal rewards.
Approach
Select the least-visited state-action pair as a goal each step and follow a goal-conditioned policy derived from learned state-action successor functions (S-functions), which are driven by an always-observable indicator reward; exploration is thus decoupled from the Q-function and from reward observability, with a beta_t threshold interleaving exploration and exploitation.
Key results
- The proposed S-function exploration is the only method converging to the optimal policy in the vast majority of seeds across environments and monitors in the Mon-MDP benchmarks.
- Pure optimism is optimal only when rewards are deterministic and always observable; it fails under stochastic transitions or unobservable rewards.
- The proposed method observes significantly more rewards than baselines in all Mon-MDPs because exploration does not depend on the Q-function.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use directed exploration with successor-functions instead of the tested baseline exploration policies | Q-Learning · Tabular MDPs and Mon-MDPs | greedy policy return | Helped |
| Use directed exploration with successor-functions rather than optimism | Q-Learning · Stochastic or partially observable reward environments | greedy policy return | Helped |
| Use directed exploration with successor-functions rather than UCB, Q-Counts, intrinsic reward, or naive epsilon-greedy exploration | Q-Learning · Harder Mon-MDPs | greedy policy return | Helped |
| Use directed exploration with successor-functions rather than the tested baselines | Q-Learning · River Swim | greedy policy return | No clear effect |
| Use pessimistic rather than optimistic Q-function initialization (ablation) | UCB, Q-Counts, Intrinsic, and Naive · Tabular MDPs and Mon-MDPs | greedy policy return | Hurt |
| Use epsilon-greedy noise starting at 1 and linearly decaying to 0 instead of the tested alternative epsilon schedules (ablation) | All algorithms · Tabular environments | performance | Helped |
Surprising findings
- Pessimistic Q-initialization (-10) worked better than optimistic initialization for the proposed method, because optimism amplifies overestimation from inaccurate reward models in Mon-MDPs.
- Even random reward observability (not agent-controlled) is enough to cause convergence to suboptimal policies for optimistic and standard exploration baselines.
Limitations
- Only tabular MDPs were evaluated; extension to continuous spaces is left to future work.
- Assumes a bounded goal-relative diameter, which requires a communicating MDP; weakly communicating MDPs are not covered.
- Exploration requires epsilon-greedy stochasticity to learn S-functions, and balanced exploration alternatives were not tested.
Experimental setup
Datasets: custom tabular MDPs (Empty, Loop, Hazard, One-Way, Corridor, Two-Room, River Swim) custom Monitored MDP variants (Random, Ask, Button, Random Experts, Level Up monitors)
Benchmarks: Empty Loop Hazard One-Way Corridor Two-Room River Swim Mon-MDP variants with Random, Ask, Button, Random Experts, Level Up monitors
Metrics: greedy policy return over training number of observed rewards during training
Baselines: optimistic greedy Q-learning naive epsilon-greedy epsilon-greedy with count-based intrinsic reward UCB exploration Q-Counts
Builds on: Q-Learning Monitored MDPs successor representation UCB epsilon-greedy
Closest papers by meaning
- Efficient Model-Based Reinforcement Learning Through Optimistic Thompson Sampling (ICLR 2025 · similarity 0.90)
- Minimax Optimal Reinforcement Learning with Quasi-Optimism (ICLR 2025 · similarity 0.90)
- OVD-Explorer: Optimism Should Not Be the Sole Pursuit of Exploration in Noisy Environments (AAAI 2024 · similarity 0.90)
- Reinforcement Learning with Lookahead Information (NeurIPS 2024 · similarity 0.90)
- NeoRL: Efficient Exploration for Nonepisodic RL (NeurIPS 2024 · similarity 0.89)
- Provably Efficient Partially Observable Risk-sensitive Reinforcement Learning with Hindsight Observation (ICML 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.