mlsanityData to 14 Oct 2026

When a Reinforcement Learning Agent Encounters Unknown Unknowns

arXiv 2505.13188 ↗First posted 19 May 2025cs.LG cs.AI stat.MLcited by 0

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

Abstract (arXiv)

An AI agent might surprisingly find she has reached an unknown state which she has never been aware of -- an unknown unknown. We mathematically ground this scenario in reinforcement learning: an agent, after taking an action calculated from value functions Q and V defined on the it aware domain, reaches a state out of the domain. To enable the agent to handle this scenario, we propose an it episodic Markov decision process with growing awareness (EMDP-GA) model, taking a new it noninformative value expansion (NIVE) approach to expand value functions to newly aware areas: when an agent arrives at an unknown unknown, value functions Q and V whereon are initialised by noninformative beliefs -- the averaged values on the aware domain. This design is out of respect for the complete absence of knowledge in the newly discovered state. The upper confidence bound momentum Q-learning is then adapted to the growing awareness for training the EMDP-GA model. We prove that (1) the regret of our approach is asymptotically consistent with the state of the art (SOTA) without exposure to unknown unknowns in an extremely uncertain environment, and (2) our computational complexity and space complexity are comparable with the SOTA -- these collectively suggest that though an unknown unknown is surprising, it will be asymptotically properly discovered with decent speed and an affordable cost.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 18 of its 41 references that are in the map. First posted on arXiv 19 May 2025.

Builds on

18 of 41 references.

Closest ancestors · 1

Same direction, newest first

  1. 2024Optimistic Q-learning for average reward and episodic reinforcement learning18 Jul

Other references · 17

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  2. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  3. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  4. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
  5. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 106
  6. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 106
  7. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  8. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  9. 2020Adaptive Reward-Free Explorationcited by 77
  10. 2021FinRL: Deep Reinforcement Learning Framework to Automate Trading in Quantitative Financecited by 58
  11. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
  12. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 46
5 more
  1. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  2. 2019Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policiescited by 39
  3. 2022A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learningcited by 31
  4. 2022From Dirichlet to Rubin: Optimistic Exploration in RL without Bonusescited by 22
  5. 2020Decentralized Reinforcement Learning: Global Decision-Making via Local Economic Transactionscited by 15

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2023Exploiting Generalization in Offline Reinforcement Learning via Unseen State Augmentations
  2. 2026Deep Epistemic Value Functions for Optimistic Exploration
  3. 2025Value Under Ignorance in Universal Artificial Intelligence
  4. 2025Know When to Explore: Difficulty-Aware Certainty as a Guide for LLM Reinforcement Learning
  5. 2026Average-Reward Policy Identification from a Single Continuing Trajectory
  6. 2025EUBRL: Epistemic Uncertainty Directed Bayesian Reinforcement Learning
  7. 2022Learning Value Functions from Undirected State-only Experience
  8. 2024Mitigating Partial Observability in Sequential Decision Processes via the Lambda Discrepancy