mlsanityData to 14 Oct 2026

Monitored Markov Decision Processes

arXiv 2402.06819 ↗First posted 9 Feb 2024cs.LGcited by 10

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

In reinforcement learning (RL), an agent learns to perform a task by interacting with an environment and receiving feedback (a numerical reward) for its actions. However, the assumption that rewards are always observable is often not applicable in real-world problems. For example, the agent may need to ask a human to supervise its actions or activate a monitoring system to receive feedback. There may even be a period of time before rewards become observable, or a period of time after which rewards are no longer given. In other words, there are cases where the environment generates rewards in response to the agent's actions but the agent cannot observe them. In this paper, we formalize a novel but general RL framework - Monitored MDPs - where the agent cannot always observe rewards. We discuss the theoretical and practical consequences of this setting, show challenges raised even in toy environments, and propose algorithms to begin to tackle this novel setting. This paper introduces a powerful new formalism that encompasses both new and existing problems and lays the foundation for future research.

Key facts. Cited by 10 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 23 of its 49 references that are in the map. First posted on arXiv 9 Feb 2024.

Builds on

23 of 49 references.

References · 23

  1. 2019Mastering Atari, Go, Chess and Shogi by Planning with a Learned Modelcited by 1,353
  2. 2017Curiosity-driven Exploration by Self-supervised Predictioncited by 1,194
  3. 2016Unifying Count-Based Exploration and Intrinsic Motivationcited by 639
  4. 2019Reinforcement Learning in Healthcare: A Surveycited by 310
  5. 2019VariBAD: A Very Good Method for Bayes-Adaptive Deep RL via Meta-Learningcited by 217
  6. 2022Exploration in Deep Reinforcement Learning: A Surveycited by 166
  7. 2017Interactive Learning from Policy-Dependent Human Feedbackcited by 158
  8. 2015Incentivizing Exploration In Reinforcement Learning With Deep Predictive Modelscited by 154
  9. 2020RIDE: Rewarding Impact-Driven Exploration for Procedurally-Generated Environmentscited by 135
  10. 2020Deployment-Efficient Reinforcement Learning via Model-Based Offline Optimizationcited by 120
  11. 2016Learning values across many orders of magnitudecited by 85
  12. 2018Horizon: Facebook's Open Source Applied Reinforcement Learning Platformcited by 48
11 more
  1. 2019An Information-Theoretic Approach to Minimax Regret in Partial Monitoringcited by 42
  2. 2020Cautious Adaptation For Reinforcement Learning in Safety-Critical Settingscited by 42
  3. 2017Human-in-the-loop Artificial Intelligencecited by 40
  4. 2021Interesting Object, Curious Agent: Learning Task-Agnostic Explorationcited by 38
  5. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  6. 2020Active Reinforcement Learning: Observing Rewards at a Costcited by 20
  7. 2020Active Measure Reinforcement Learning for Observation Cost Minimizationcited by 17
  8. 2018Cleaning up the neighborhood: A full classification for adversarial partial monitoringcited by 16
  9. 2018Active Reinforcement Learning with Monte-Carlo Tree Searchcited by 11
  10. 2022Sequential Information Design: Learning to Persuade in the Darkcited by 9
  11. 2020Long-Term Visitation Value for Deep Exploration in Sparse Reward Reinforcement Learningcited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 6; 2026: 3.

10 papers.

  1. 2024Beyond Optimism: Exploration With Partially Observable Rewardscited by 6
  2. 2025Model-Based Exploration in Monitored Markov Decision Processescited by 1
  3. 2025Generalization in Monitored Markov Decision Processes (Mon-MDPs)cited by 1
  4. 2025Online Learning of Whittle Indices for Restless Bandits with Non-Stationary Transition Kernelscited by 1
  5. 2026Position: Deployed Reinforcement Learning should be Continualcited by 1
  6. 2025Which Rewards Matter? Reward Selection for Reinforcement Learning under Limited Feedbackcited by 0
  7. 2025Optimizing Algorithms for Mobile Health Interventions with Active Querying Optimizationcited by 0
  8. 2025Adaptive Accountability in Networked MAS: Tracing and Mitigating Emergent Norms at Scalecited by 0
  9. 2026Multi-objective Reinforcement Learning With Augmented States Requires Rewards After Deploymentcited by 0
  10. 2026Self-Certification of Representation Adequacy: Sequential Certification at Minimum Task Losscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Expressive Temporal Specifications for Reward Monitoring
  2. 2025Expressive Reward Synthesis with the Runtime Monitoring Language
  3. 2024On the Limitations of Markovian Rewards to Express Multi-Objective, Risk-Sensitive, and Modal Tasks
  4. 2019Reinforcement Learning with Non-Markovian Rewards
  5. 2026Synthetic Monitoring Environments for Reinforcement Learning
  6. 2025Active Measuring in Reinforcement Learning With Delayed Negative Effects
  7. 2024Mitigating Partial Observability in Sequential Decision Processes via the Lambda Discrepancy
  8. 2025Reinforcement Learning with Action-Triggered Observations