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

Minshuo Chen, Jie Meng, Yu Bai, Yinyu Ye, H. Vincent Poor, Mengdi Wang

Abstract

Standard Reinforcement Learning (RL) assumes that agents receive immediate and perfect state observations. In real-world applications, such as remote robotics or high-frequency trading, agents often encounter communication delays or permanent data loss. This paper provides the first theoretical framework for RL in these impaired environments, proving that agents can achieve near-optimal efficiency (regret) that scales with the original system's size. By exploiting the underlying structure of the environment, the authors demonstrate that it is possible to avoid the exponential complexity typically associated with history-dependent policies.

Introduction

In the idealized world of textbook Reinforcement Learning, an agent observes the current state $s_t$, executes an action $a_t$, and receives a reward $r_t$ instantaneously. However, physical constraints in the real world—such as signal propagation delays in remote-controlled systems or lossy channels in sensor networks—frequently violate this assumption. When observations are delayed or missing, the Markov property of the system is broken from the agent's perspective, as the optimal action now depends on the history of past events rather than just the most recent observation.

Historically, the solution to this problem has been "state augmentation," where the agent's state is redefined to include the entire history of recent actions and observations. While mathematically sound, this approach leads to a state space that grows exponentially with the length of the delay, making efficient learning seemingly impossible. This paper addresses a fundamental question: Can we learn to act efficiently in impaired environments without paying an exponential price in sample complexity?

Methodology: Efficient Augmented MDPs

The authors tackle the challenges of delayed and missing observations by constructing specialized Augmented Markov Decision Processes (MDPs) that prioritize structural efficiency.

Handling Delayed Observations

For environments where observations arrive with a delay of $d$ steps, the authors introduce an algorithm that plans over an augmented state space but utilizes a "past reward" formulation. Instead of attempting to predict the current, unobserved reward, the agent accounts for rewards as they are actually received. The algorithm employs optimistic value iteration with a custom "bonus" function designed to handle the uncertainty of transitions within the original, non-delayed MDP.

Addressing Missing Observations

To handle missing data, the authors propose two distinct strategies:

  1. Optimistic Multi-Step Planning: This algorithm handles "holes" in the data by jumping over missing observations using multi-step transition models.
  2. Model-Based Refinement: A sharper approach that proves particularly effective when the rate of missing data is relatively low.

Exploiting Sparsity

The "secret sauce" of their approach is the realization that while the augmented state space is mathematically large, the transitions within it are sparse. A delayed observation of a past state still follows the physics of the original system. By exploiting this sparsity, the authors ensure that their regret bounds depend primarily on the number of states ($S$) and actions ($A$) in the original system, rather than the inflated dimensions of the augmented space.

Key Insights and Theoretical Results

The Dichotomy of Delay

A striking finding of the research is the "dichotomy" of delay: a delay of $d$ steps may have negligible impact on performance, but a delay of $d+1$ could cause a sudden, constant drop in the optimal value. This occurs because information often has a "critical window" of utility; once a decision point passes that window, the agent is essentially forced to guess, regardless of how much data it eventually receives.

Information Loss vs. Latency

The paper quantifies the performance gap—the value lost due to the inability to see the present. In deterministic environments, the loss is zero because the agent can perfectly predict the present from the past. However, as the environment becomes more stochastic (higher entropy), the cost of impaired observability increases significantly.

Near-Optimal Regret Bounds

The authors establish rigorous regret bounds that match the minimax-optimal rates for standard, fully observable MDPs in their dependence on $S$ and $A$:

  • Stochastic Delays: They achieve a regret bound of $\tilde{O}((H \wedge D)^{5/2} \sqrt{H^3 SAK})$, where $D$ is the maximum delay and $K$ is the number of episodes.
  • Missing Data: For missing observations, they achieve a regret of $\tilde{O}(\sqrt{H^3 S^2 AK})$, which sharpens to $\tilde{O}(H^4 \sqrt{SAK})$ when the missing rate is low.

Empirical Validation

The theoretical findings were validated using synthetic tabular MDP environments (20 states, 5 actions). The experiments tested both nearly deterministic and highly stochastic transitions across various delay distributions (constant and Bernoulli). The results confirmed that regret grows predictably as the maximum delay increases and as stochasticity rises, aligning closely with the predicted theoretical bounds.

Discussion and Limitations

While this work marks a significant step forward in sample-efficient RL for impaired environments, several challenges remain:

  • Computational Complexity: Although the learning is sample-efficient, the planning process (calculating the optimal policy) remains NP-Hard in the worst case. The augmented MDP approach still faces an exponential computational wall as the delay length increases.
  • The Critical Point for Missing Data: The authors hypothesize a critical missing data rate ($1 - 1/A$) where exploration strategies must fundamentally change, a phenomenon that remains underexplored.
  • Scaling to Continuous Spaces: This research focuses on tabular RL. Extending these near-optimal bounds to deep RL or continuous state spaces is a primary objective for future work.

Summary updated

Abstract

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 $\tilde{\mathcal{O}}(\sqrt{{\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.
BibTeX
@article{chen2024efficient,
  author = {Minshuo Chen and Jie Meng and Yu Bai and Yinyu Ye and H. Vincent Poor and Mengdi Wang},
  title = {{Efficient Reinforcement Learning With Impaired Observability: Learning to Act With Delayed and Missing State Observations}},
  journal = {IEEE Trans. Information Theory},
  year = {2024},
  doi = {10.1109/tit.2024.3416202},
}
Figure