Planning in Observable POMDPs in Quasipolynomial Time

Noah Golowich, Ankur Moitra, Dhruv RohatgiarXiv 2022 · OpenReview

Abstract

Partially Observable Markov Decision Processes (POMDPs) provide a robust framework for reinforcement learning under state uncertainty. However, planning in POMDPs is notoriously difficult, typically requiring exponential time due to the "Curse of History." In this work, we present a quasipolynomial-time algorithm for planning in (one-step) observable POMDPs. Our approach leverages the assumption that well-separated state distributions result in well-separated observation distributions. We demonstrate that under this condition, the Bayes filter is exponentially stable, allowing for near-optimal policies with quasi-succinct descriptions. Furthermore, we establish matching hardness results under the Exponential Time Hypothesis (ETH).

1. Introduction

In many real-world Reinforcement Learning (RL) scenarios, agents lack full access to the underlying state of the environment. Partially Observable Markov Decision Processes (POMDPs) model these situations by incorporating an observation model that maps states to probabilistic observations. While POMDPs are expressive, they are computationally daunting; planning—finding an optimal policy given the model parameters—is PSPACE-hard.

The primary challenge is the "Curse of History." Because current observations are incomplete, an agent's optimal decision may depend on the entire sequence of past actions and observations. This leads to a search space that grows exponentially with the planning horizon $H$. Existing approaches often rely on heuristics or strong assumptions about transition dynamics (e.g., rapid mixing), which may not hold in practice. This paper investigates whether assumptions about the observability of the system can make planning more tractable.

2. The Observability Assumption

The authors focus on the concept of $\gamma$-observability. A POMDP is $\gamma$-observable if, for any two distributions over hidden states, the distance between their corresponding observation distributions is at least a $\gamma$-fraction of the distance between the state distributions.

Crucially, this is a property of the "sensors" rather than the "physics" of the environment. Unlike prior work that required the environment to "forget" its state regardless of agent actions (mixing), $\gamma$-observability only requires that the observations are sufficiently informative to distinguish between states. This assumption is often more realistic, as sensor quality can be improved even when environment dynamics are complex or persistent.

3. Filter Stability and Short-Memory Planning

The core theoretical contribution is a new bound on filter stability. The Bayes filter is the recursive mechanism used to update an agent's belief about the current state. The authors prove that in observable POMDPs, the filter is exponentially stable: the influence of the initial (possibly incorrect) belief decays exponentially over time as new observations are processed.

To prove this, the authors utilize 2-Rényi divergence. While previous stability proofs using KL-divergence only yielded polynomial decay, the 2-Rényi divergence allows for a much tighter analysis, showing that the expected distance between the true belief and a belief based only on recent history shrinks to $\epsilon$ in $O(\gamma^{-4} \log(S/\epsilon))$ steps.

This stability implies that an agent does not need to remember the entire history. A "short-memory" window of length $L \approx \log(H)$ is sufficient to approximate the current belief and make near-optimal decisions.

4. Algorithmic Results and Complexity

By restricting the agent's memory to a logarithmic window, the number of possible histories to consider is reduced from exponential to quasipolynomial. The resulting algorithm finds an $\epsilon$-suboptimal policy in:

$$T = H(OA)^{C \log(SH/\epsilon)/\gamma^4}$$

where $H$ is the horizon, $O$ is the number of observations, $A$ is the number of actions, and $S$ is the number of states. For a fixed observability parameter $\gamma$, this complexity is quasipolynomial in the problem parameters. This represents a significant improvement over the standard exponential complexity associated with POMDP planning.

5. Hardness and Limitations

To complement the algorithmic upper bound, the authors provide a matching lower bound. Under the Exponential Time Hypothesis (ETH), they prove that planning in observable POMDPs requires quasipolynomial time. This suggests that the proposed algorithm is essentially optimal for this class of problems.

However, some limitations remain:

  • Undercomplete Setting: The $\gamma$-observability assumption typically implies there are at least as many observations as states ($O \ge S$). "Overcomplete" POMDPs, where states outnumber observations, remain a significant challenge.
  • One-Step Observability: The current analysis assumes observations are informative within a single step. Extending this to "multi-step" observability is a subject for future research.
  • Parameter Sensitivity: The runtime's dependence on $1/\gamma^4$ means that the algorithm may become slow if the observations are only marginally informative (small $\gamma$).

6. Conclusion

This work breaks the "Curse of History" for a significant class of POMDPs. By shifting the focus from transition dynamics to sensor observability and employing 2-Rényi divergence for stability analysis, the authors provide the first quasipolynomial-time planning guarantees for observable POMDPs, bridging the gap between theoretical hardness and practical tractability.

Summary updated

Abstract

Partially Observable Markov Decision Processes (POMDPs) are a natural and general model in reinforcement learning that take into account the agent's uncertainty about its current state. In the literature on POMDPs, it is customary to assume access to a planning oracle that computes an optimal policy when the parameters are known, even though the problem is known to be computationally hard. Almost all existing planning algorithms either run in exponential time, lack provable performance guarantees, or require placing strong assumptions on the transition dynamics under every possible policy. In this work, we revisit the planning problem and ask: are there natural and well-motivated assumptions that make planning easy? Our main result is a quasipolynomial-time algorithm for planning in (one-step) observable POMDPs. Specifically, we assume that well-separated distributions on states lead to well-separated distributions on observations, and thus the observations are at least somewhat informative in each step. Crucially, this assumption places no restrictions on the transition dynamics of the POMDP; nevertheless, it implies that near-optimal policies admit quasi-succinct descriptions, which is not true in general (under standard hardness assumptions). Our analysis is based on new quantitative bounds for filter stability -- i.e. the rate at which an optimal filter for the latent state forgets its initialization. Furthermore, we prove matching hardness for planning in observable POMDPs under the Exponential Time Hypothesis.
BibTeX
@misc{golowich2022planning,
  author = {Noah Golowich and Ankur Moitra and Dhruv Rohatgi},
  title = {{Planning in Observable POMDPs in Quasipolynomial Time}},
  year = {2022},
  eprint = {2201.04735},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2201.04735},
}
Figure