# Model-Based Exploration in Monitored Markov Decision Processes

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 13 of its 37 references that are in the map.
- First posted on arXiv 24 Feb 2025.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 13 of 13)

- [Learning Dexterous In-Hand Manipulation](https://mlsanity.com/paper/1808.00177/) (2018)
- [Unifying Count-Based Exploration and Intrinsic Motivation](https://mlsanity.com/paper/1606.01868/) (2016)
- [#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/1611.04717/) (2016)
- [Deep Exploration via Randomized Value Functions](https://mlsanity.com/paper/1703.07608/) (2017)
- [Count-Based Exploration with the Successor Representation](https://mlsanity.com/paper/1807.11622/) (2018)
- [Inverse Preference Learning: Preference-based RL without a Reward Function](https://mlsanity.com/paper/2305.15363/) (2023)
- [Count-Based Exploration in Feature Space for Reinforcement Learning](https://mlsanity.com/paper/1706.08090/) (2017)
- [Active Reinforcement Learning: Observing Rewards at a Cost](https://mlsanity.com/paper/2011.06709/) (2020)
- [Active Reinforcement Learning with Monte-Carlo Tree Search](https://mlsanity.com/paper/1803.04926/) (2018)
- [Monitored Markov Decision Processes](https://mlsanity.com/paper/2402.06819/) (2024)
- [Barrier Function-based Safe Reinforcement Learning for Emergency Control of Power Systems](https://mlsanity.com/paper/2103.14186/) (2021)
- [Learning Purposeful Behaviour in the Absence of Rewards](https://mlsanity.com/paper/1605.07700/) (2016)
- [Beyond Optimism: Exploration With Partially Observable Rewards](https://mlsanity.com/paper/2406.13909/) (2024)

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

- [Generalization in Monitored Markov Decision Processes (Mon-MDPs)](https://mlsanity.com/paper/2505.08988/) (2025)

## Abstract (arXiv)

A tenet of reinforcement learning is that the agent always observes rewards. However, this is not true in many realistic settings, e.g., a human observer may not always be available to provide rewards, sensors may be limited or malfunctioning, or rewards may be inaccessible during deployment. Monitored Markov decision processes (Mon-MDPs) have recently been proposed to model such settings. However, existing Mon-MDP algorithms have several limitations: they do not fully exploit the problem structure, cannot leverage a known monitor, lack worst-case guarantees for 'unsolvable' Mon-MDPs without specific initialization, and offer only asymptotic convergence proofs. This paper makes three contributions. First, we introduce a model-based algorithm for Mon-MDPs that addresses these shortcomings. The algorithm employs two instances of model-based interval estimation: one to ensure that observable rewards are reliably captured, and another to learn the minimax-optimal policy. Second, we empirically demonstrate the advantages. We show faster convergence than prior algorithms in over four dozen benchmarks, and even more dramatic improvement when the monitoring process is known. Third, we present the first finite-sample bound on performance. We show convergence to a minimax-optimal policy even when some rewards are never observable.