mlsanityData to 7 Oct 2026

Efficient Reinforcement Learning with Impaired Observability: Learning to Act with Delayed and Missing State Observations

arXiv 2306.01243 ↗First posted 2 Jun 2023cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

In real-world reinforcement learning (RL) systems, various forms of it impaired observability can complicate matters. These situations arise when an agent is unable to observe the most recent state of the system due to latency or lossy channels, yet the agent must still make real-time decisions. This paper introduces a theoretical investigation into efficient RL in control systems where agents must act with delayed and missing state observations. We present algorithms and establish near-optimal regret upper and lower bounds, of the form tildeO(√rm poly(H) SAK), for RL in the delayed and missing observation settings. Here S and A are the sizes of state and action spaces, H is the time horizon and K is the number of episodes. Despite impaired observability posing significant challenges to the policy class and planning, our results demonstrate that learning remains efficient, with the regret bound optimally depending on the state-action size of the original system. Additionally, we provide a characterization of the performance of the optimal policy under impaired observability, comparing it to the optimal value obtained with full observability. Numerical results are provided to support our theory.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 25 of its 58 references that are in the map. First posted on arXiv 2 Jun 2023.

Builds on

25 of 58 references.

References · 25

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  4. 2013Online Learning under Delayed Feedbackcited by 137
  5. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  6. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  7. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  8. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  9. 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
  10. 2018Linear Bandits with Stochastic Delayed Feedbackcited by 55
  11. 2017Stochastic Bandit Models for Delayed Conversionscited by 53
  12. 2022GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyondcited by 45
13 more
  1. 2022PAC Reinforcement Learning for Predictive State Representationscited by 42
  2. 2020Stochastic bandits with arm-dependent delayscited by 36
  3. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  4. 2022Sequence Model Imitation Learning with Unobserved Contextscited by 34
  5. 2021Stochastic Multi-Armed Bandits with Unrestricted Delay Distributionscited by 33
  6. 2022Hindsight Learning for MDPs with Exogenous Inputscited by 25
  7. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  8. 2022Delayed Feedback in Generalised Linear Bandits Revisitedcited by 23
  9. 2023Learning in POMDPs is Sample-Efficient with Hindsight Observabilitycited by 17
  10. 2020Blind Decision Making: Reinforcement Learning with Delayed Observationscited by 14
  11. 2023Lower Bounds for Learning in Revealing POMDPscited by 14
  12. 2023A Reduction-based Framework for Sequential Decision Making with Delayed Feedbackcited by 7
  13. 2020Contextual Bandit with Missing Rewardscited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 2; 2026: 1.

4 papers.

  1. 2024Unveil Conditional Diffusion Models with Classifier-free Guidance: A Sharp Statistical Theorycited by 58
  2. 2026Reinforcement Learning for Control Systems with Time Delays: A Comprehensive Surveycited by 1
  3. 2025Robust Remote Reinforcement Learning over Unreliable Communication Channels using Homomorphic State Encodingcited by 0
  4. 2025A Theoretical Analysis of State Similarity Between Markov Decision Processescited by 0