Research map / Reinforcement learning / MDPs and planning
Model-Based Exploration in Monitored Markov Decision Processes
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 Monitored MBIE-EB, a model-based interval-estimation algorithm for Monitored MDPs that uses two MBIE-EB instances (optimism plus pessimism for unobservable rewards and an observe-phase exploration) and gives the first finite-sample bound for Mon-MDPs.
Problem
Reinforcement learning in Monitored MDPs, where a monitor decides whether the agent observes environment rewards; prior algorithms ignore Mon-MDP structure, cannot use a known monitor, lack finite-sample guarantees, and do not handle unsolvable Mon-MDPs with never-observable rewards.
Approach
Model each unknown Mon-MDP component (environment reward, monitor reward, joint transitions) with separate MBIE-EB bonuses, switch to a pessimistic reward model for never-observed environment rewards, and interleave an observe-phase KL-UCB exploration model so that observable rewards are eventually seen and minimax-optimal behavior is learned.
Key results
- Monitored MBIE-EB significantly outperforms Directed-E^2 on River Swim and the Bottleneck with Button monitor, converging to the minimax-optimal policy where Directed-E^2 does not.
- Monitored MBIE-EB outperforms Directed-E^2 in 43 of 48 benchmark Mon-MDPs and performs on par in the other five.
- With the monitor known in advance, the agent takes on average about 30% fewer steps to reach the minimax-optimal policy in the 5% Button Bottleneck.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Monitored MBIE-EB instead of Directed-E² | Mon-MDP benchmarks · 48 benchmark environments | benchmark performance: 43 of them | Helped |
| provide the Button Monitor model | Monitored MBIE-EB · Bottleneck, 5% Button Monitor | steps to find the minimax-optimal policy: 30% fewer steps | Helped |
| use Monitored MBIE-EB instead of Directed-E² | River Swim with Full Monitor · River Swim | test return | Helped |
| use pessimism for rewards that are never observable | Monitored MBIE-EB · Bottleneck, unsolvable | test return | Helped |
| use Monitored MBIE-EB instead of Directed-E² | Bottleneck with 5% Button Monitor · Bottleneck, 5% Button Monitor | test return | Helped |
| remove pessimism for unobserved rewards (ablation) | Monitored MBIE-EB · Bottleneck, solvable | test return | No clear effect |
| remove pessimism for unobserved rewards (ablation) | Monitored MBIE-EB · Bottleneck, unsolvable | test return | Hurt |
| add pessimism for unobserved rewards (ablation) | MBIE-EB · Bottleneck, unsolvable | test return | Helped |
| remove exploration targeted at observing unobserved rewards (ablation) | Monitored MBIE-EB · Bottleneck, solvable with deterministic observability | test return | No clear effect |
| remove exploration targeted at observing unobserved rewards (ablation) | Monitored MBIE-EB · Bottleneck, unsolvable with deterministic observability | test return | No clear effect |
| remove exploration targeted at observing unobserved rewards (ablation) | Monitored MBIE-EB · Bottleneck, unsolvable with stochastic observability | test return | Hurt |
| add exploration targeted at observing rewards (ablation) | pessimistic MBIE-EB · Bottleneck, unsolvable with stochastic observability | test return | Helped |
Surprising findings
- Directed-E^2 with the recommended random initialization shows essentially no learning in unsolvable Mon-MDPs, since it never updates its initial estimates of unobservable rewards.
Limitations
- Uses explicit state-action counts, limiting it to enumerable Mon-MDPs
- Switching between observe and optimize episodes via a scheduled kappa* is not a single unified objective
- Confidence hyperparameters are tuned manually per environment
Experimental setup
Datasets: River Swim Bottleneck Empty Hazard Loop One-Way Corridor Two-Room-3x5 Two-Room-2x11
Benchmarks: River Swim Bottleneck 48 Mon-MDP benchmarks from prior work (Directed-E^2 environments and monitors)
Metrics: discounted return at test time visits to goal and unobservable states
Baselines: Directed-E^2 MBIE-EB pessimistic MBIE-EB
Builds on: MBIE-EB Monitored MDP Directed-E^2 KL-UCB
Closest papers by meaning
- Improved Bounds for Reward-Agnostic and Reward-Free Exploration (ICML 2026 · similarity 0.90)
- Reinforcement Learning with State Observation Costs in Action-Contingent Noiselessly Observable Markov Decision Processes (NeurIPS 2021 · similarity 0.89)
- Learning and Planning in Average-Reward Markov Decision Processes (ICML 2021 · similarity 0.89)
- Reinforcement Learning in Reward-Mixing MDPs (NeurIPS 2021 · similarity 0.88)
- Provable Representation with Efficient Planning for Partially Observable Reinforcement Learning (ICML 2024 · similarity 0.88)
- RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluation (NeurIPS 2024 · similarity 0.87)
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.