Learning in Observable POMDPs, without Computationally Intractable Oracles

Noah Golowich, Ankur Moitra, Dhruv Rohatgi

TL;DR

This paper introduces BaSeCAMP, the first computationally efficient, "oracle-free" algorithm for learning near-optimal policies in observable Partially Observable Markov Decision Processes (POMDPs). By ditching the traditional but computationally expensive "principle of optimism" in favor of barycentric spanners and policy covers, the authors achieve quasipolynomial time and sample complexity—a significant theoretical breakthrough for a problem class long thought to be intractable.

What Problem Does This Paper Address?

Reinforcement Learning (RL) usually assumes an agent has perfect knowledge of its current state (Markov Decision Processes). However, real-world applications—from robotics to healthcare—are often Partially Observable (POMDPs): the agent only gets noisy or incomplete "observations" of a hidden underlying state.

POMDPs are notoriously difficult. In the worst case, finding an optimal policy is both statistically and computationally impossible. To make progress, researchers often focus on "Observable POMDPs," where different state distributions lead to noticeably different observation distributions.

Even with this restriction, previous learning algorithms had a major "cheat": they relied on computationally intractable oracles. These algorithms assumed access to a "magic black box" that could solve NP-hard optimistic planning or maximum likelihood problems. The gap addressed here is: Can we learn in observable POMDPs using an algorithm that actually runs in reasonable time on a real computer?

Methods

The authors propose an algorithm called BaSeCAMP (Barycentric Spanner policy Cover with Approximate MDP). Its design rests on three pillars:

  1. MDP Approximation via Belief Contraction: Building on recent work, the authors show that an observable POMDP can be approximated by a large (but manageable) MDP. In this MDP, a "state" is defined by a short history of recent actions and observations.
  2. Barycentric Spanners for Exploration: This is the core innovation. Usually, RL agents explore by being "optimistic" about unknown areas. In POMDPs, calculating this optimism is computationally brutal. Instead, BaSeCAMP uses Barycentric Spanners—a geometric technique to find a small set of "basis" policies. These policies together "span" the space of all possible observation distributions, ensuring the agent explores all reachable parts of the environment.
  3. Iterative Policy Covers: The algorithm doesn't try to learn everything at once. It iteratively builds a "policy cover"—a collection of policies that, when taken together, are guaranteed to visit every important latent state with sufficient probability.

Datasets

This is a theoretical research paper. It does not use empirical datasets or benchmarks. Instead, it provides rigorous mathematical proofs for the algorithm's performance and complexity bounds.

Key Insights and Ideas

  • Moving Beyond Optimism: The "Principle of Optimism Under Uncertainty" is the dominant paradigm in RL exploration, but it often leads to non-convex optimization problems that are NP-hard. This paper demonstrates that Policy Covers (exploring everything systematically) can be a computationally superior alternative to optimism in complex state spaces.
  • Observability as a Geometric Bridge: The $\gamma$-observability assumption is used geometrically. It ensures that if two distributions over hidden states are different, their resulting observation distributions are also different. This allows the agent to "see" its progress in the latent state space through the lens of its observations.
  • Quasipolynomial is the Limit: The authors show that their quasipolynomial time complexity is likely the best one can do. Previous lower bounds suggest that even planning in these environments (where you already know the map) requires quasipolynomial time; thus, learning (where you don't know the map) cannot be faster.

Key Results

  • Theorem 3.1: BaSeCAMP learns an $\alpha$-suboptimal policy with probability $1-\beta$ using time and sample complexity of $(OA)^{C \cdot \text{poly}(\log(HSO/\alpha\gamma), 1/\gamma)}$.
  • First of its Kind: This is the first end-to-end algorithm for POMDPs that provides provable guarantees without requiring access to NP-hard oracles.
  • Computational Efficiency: While "quasipolynomial" is slower than standard polynomial time, it is vastly more efficient than the exponential time required by naive approaches, representing a major step toward practical POMDP solvers.

Limitations and Future Work

  • The Quasipolynomial Gap: While the time complexity is likely optimal, the authors suggest it might be possible to achieve polynomial sample complexity even if the computation remains quasipolynomial.
  • Strictness of Observability: The $\gamma$-observability assumption, while milder than many previous constraints (like deterministic transitions), still excludes some complex POMDPs where states are truly hidden or aliased.
  • Practical Implementation: The state space of the approximate MDP ($Z = A^L \times O^L$) grows rapidly with the history length $L$. While theoretically efficient, a direct implementation would still be very memory-intensive for problems with long horizons or large observation spaces. Future work could look into more compact representations of these history-states.

Summary updated

BibTeX
@inproceedings{golowich2022learning,
  author = {Noah Golowich and Ankur Moitra and Dhruv Rohatgi},
  title = {{Learning in Observable POMDPs, without Computationally Intractable Oracles}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=A3DCaxhxBfl},
}
Figure