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