Achieving Polynomial Sample Complexity in POMDPs

20 concepts16 papers1 proposal

In standard Reinforcement Learning (RL), agents typically operate within Markov Decision Processes (MDPs), assuming they have direct, perfect access to the environment's current state. Under this assumption, finding an optimal policy is highly tractable: the sample complexity scales polynomially with the number of states and actions.

Real-world applications, however, are rarely fully observable. In Partially Observable MDPs (POMDPs), the true state is hidden, and the agent must rely on a stream of noisy or incomplete observations. Historically, this lack of visibility was viewed as an information-theoretic barrier. Without knowing the exact state, an agent might need to condition its actions on its entire history of interactions, causing the sample complexity to explode exponentially with the time horizon.

A major convergence of research has shattered this pessimistic view. By identifying realistic structural regularities, researchers have shown that the exponential curse of partial observability can be bypassed. It is possible to achieve polynomial sample complexity and sublinear regret—matching the fundamental statistical efficiency of fully observable models.

Inverting the Observation Model: Undercomplete and Weakly Revealing Systems

The core reason POMDPs can become tractable is that observations, while noisy, still carry information about the latent state. If we can invert this relationship, we can maintain a distribution over the hidden states.

Consider an undercomplete POMDP, where the number of unique observations is at least equal to the number of hidden states. In this setting, Jin et al. introduced an algorithm called OOM-UCB. By leveraging Observable Operator Models (OOMs) and combining them with the principle of optimism under uncertainty, the authors proved that an agent can achieve a statistically optimal sample complexity of $\tilde{O}(1/\epsilon^2)$, demonstrating that partial observability only inflates the constant factors of learning rather than degrading the rate itself.

Undercomplete Regime:  [Hidden States]  ───►  [Observations (Equal or Larger Space)]
                                              (Directly invertible via OOMs)

Weakly Revealing:     [Hidden States]  ───►  [Multi-Step Observation Histories]
                                              (Invertible over a short horizon)

What happens if the observation space is smaller than the hidden state space (the overcomplete regime)? Here, a single observation cannot uniquely pinpoint the state. However, the system may still be weakly revealing: a short sequence of multi-step observations can collectively differentiate between hidden states. Liu et al. introduced Optimistic Maximum Likelihood Estimation (OMLE) for this setting. They proved that as long as the multi-step observation emission matrix satisfies a weakly revealing condition, the sample complexity scales polynomially rather than exponentially with the horizon. Conversely, Zhan et al. demonstrated that some form of this regularity condition is a fundamental requirement; without it, any algorithm faces an information-theoretic exponential lower bound.

Bypassing Local Minima with Spectral Learning

Even when a POMDP is structurally invertible, finding the correct parameters is computationally difficult. Traditional maximum-likelihood techniques like Expectation-Maximization (EM) frequently get trapped in local minima because the objective function is non-convex.

To solve this, researchers turned to spectral methods and the Method of Moments. Instead of iteratively guessing latent states, spectral algorithms calculate the frequency of short observation sequences (moments) and use singular value or tensor decompositions to isolate the underlying transition matrices in a single, globally optimal step.

  • Guarantees on Regret: Azizzadenesheli et al. introduced SM-UCRL, utilizing spectral tensor decomposition to achieve the first provable sublinear regret bound of $\mathcal{O}(\sqrt{N})$ for POMDPs. Concurrently, Guo et al. developed EEPORL, which transforms the episodic POMDP into an induced Hidden Markov Model (HMM) to guarantee near-optimal performance within polynomial sample limits.
  • Efficient Data Reuse: A historical limitation of frequentist spectral learning was its inability to reuse data collected across different exploration policies. Russo et al. overcame this by introducing Mixed Spectral UCRL, which aggregates data from multiple historical policies to achieve a tight $\tilde{\mathcal{O}}(\sqrt{T})$ regret bound in infinite-horizon average-reward settings. The authors further refined this in Russo et al. by designing an action-wise estimation technique that allows sample reuse across deterministic policies, matching the optimal convergence rates of fully observable systems.

The Sufficiency of Short-Term Memory

An alternative way to bypass tracking a complex latent state is to use a finite-history proxy. If the environment's dynamics ensure that the recent past tells you everything you need to know about the present, you don't need to maintain a belief distribution over the entire history.

Full History:     (o_1, a_1) ──► (o_2, a_2) ──► ... ──► (o_t-1, a_t-1) ──► [Current Action]
                                                                           ▲
m-Step Memory:                                   [o_t-m, ..., o_t-1] ──────┘
                                                 (Sufficient to decode state)

This intuition is formalized in $m$-step decodable POMDPs. Efroni et al. proved that if the hidden state can be decoded from a short memory window of length $m$, the POMDP effectively collapses into a standard MDP where the "states" are simply the history windows. This insight yields sample complexities that scale with the size of the action space rather than being penalized by the raw size of the observation space.

Validating this approach for practical applications, Anjarlekar et al. proved that reinforcement learning agents using finite-history proxies can achieve sublinear regret, providing a rigorous theoretical foundation for why simple history-based architectures (like recurrent networks or frame-stacking) work well in practice.

Scaling to Rich, Infinite Observation Spaces

In modern applications like robotics or autonomous driving, observations are high-dimensional continuous inputs (e.g., camera images). The raw observation space is effectively infinite, yet the underlying physical system often possesses a low-dimensional latent structure.

Dann et al. proved that if the underlying hidden dynamics are deterministic, rich observations do not impede PAC-learnability; the sample complexity scales polynomially with the number of hidden states rather than the dimensionality of the observations.

When transitions are stochastic, we can model the system using a low-rank transition structure. Sekhari et al. showed that the sample complexity of agnostic RL in rich-observation settings can be bounded by the latent rank of the transition dynamics.

To exploit this structure algorithmically, Wang et al. developed the Represent to Control (RTC) framework. RTC learns a two-level representation:

  1. Low-dimensional features for individual steps.
  2. Embeddings for full histories.

By doing so, the authors achieved an information-theoretically optimal sample complexity of $\mathcal{O}(1/\epsilon^2)$ that scales with the problem's intrinsic rank rather than the raw observation size.

This structural leverage also extends to the offline RL setting, where an agent cannot interact with the environment and must learn from a fixed dataset. Guo et al. demonstrated that by combining Instrumental Variable (IV) regression—to handle the confounding nature of hidden states—with the pessimism principle, an agent can achieve a polynomial sample complexity of $\mathcal{O}(1/\epsilon^2)$ even within infinite state and observation spaces.

Alternative Paradigms: Predictive States and Active Sensing

Beyond traditional latent-state tracking, two alternative paradigms offer unique ways to achieve polynomial sample complexity.

Predictive State Representations (PSRs)

Instead of inventing an abstract hidden state and trying to learn its transitions, PSRs define the state of the system as a vector of predictions about the outcomes of future observable actions and observations (called "tests"). Zhan et al. introduced the CRANE algorithm, proving that by shifting from latent-state models to PSRs, agents can achieve polynomial sample complexity while competing against a globally optimal policy, bypassing many of the restrictive assumptions required by traditional POMDP models.

Active Sensing and Exploration

Sometimes, an agent can actively choose to mitigate its own blindness. Fox et al. analyzed environments where state information is hidden by default but accessible via a costly "full observation" action. Their UR-MAX algorithm demonstrates that by strategically paying for state information, an agent can maintain polynomial interaction complexity. When such actions are unavailable and the transition dynamics are completely unknown, Jafarnia-Jahromi et al. proved that combining posterior sampling (Thompson Sampling) with a novel pseudo-count exploration technique ensures the agent's average performance converges to the optimal policy at a sublinear rate.

Key Foundational Work

A Reinforcement Learning Algorithm with Polynomial Interaction Complexity for Only-Costly-Observable MDPs (2007) — contributed 2 concept elements to this direction.
A PAC RL Algorithm for Episodic POMDPs (2016) — contributed 1 concept elements to this direction.
Reinforcement Learning of POMDPs using Spectral Methods (2016) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_sublinear_regret_in_pomdps_5cdebe18,
  title = {sublinear regret in POMDPs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sublinear-regret-in-pomdps/rdr_5cdebe18ff5348968495787c31555a88},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_sublinear_regret_in_pomdps_5cdebe18_v1,
  title = {sublinear regret in POMDPs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sublinear-regret-in-pomdps/rdr_5cdebe18ff5348968495787c31555a88/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake