The Infinite Partially Observable Markov Decision Process

Finale Doshi-VelezNeurIPS 2009 · OpenReview

TL;DR

The Infinite Partially Observable Markov Decision Process (iPOMDP) removes the need for researchers to pre-specify the number of states in a reinforcement learning environment. By using nonparametric Bayesian methods, the model starts simple and dynamically adds states only as the agent’s experience demands, often leading to faster planning and better adaptation than fixed-size models.

The Challenge of Fixed States in POMDPs

In the world of Reinforcement Learning (RL), the Partially Observable Markov Decision Process (POMDP) is a powerful framework for agents that must act under uncertainty (like a robot navigating a foggy room).

Graphical model of a POMDP showing the relationships between states, actions, observations, and rewards.

However, POMDPs have a "Goldilocks" problem: researchers must tell the agent exactly how many "hidden states" exist in the world. If you guess too few, the agent cannot represent the complexity of the task. If you guess too many, the agent gets overwhelmed trying to learn thousands of unnecessary parameters, leading to computational paralysis. Most existing Bayesian RL methods focus on learning the parameters (the probabilities of moving between states) but assume the structure (the number of states) is fixed and known. This paper tackles the problem by asking: Can we let the agent discover the states itself?

The iPOMDP Approach

The paper introduces the iPOMDP, which builds on the Infinite Hidden Markov Model (iHMM) to allow for an unbounded state space.

Key technical components include:

  • Hierarchical Dirichlet Processes (HDP): This is the "infinite" engine. It provides a prior that allows for an unbounded number of states but prefers a small number of "popular" states. As the agent explores, the HDP allows it to "break off" a new piece of the state space if current observations don't fit the existing model.
  • Beam Sampling: To handle the math of an infinite state space, the author uses an auxiliary variable method called beam sampling. This allows the agent to sample a finite, manageable subset of the infinite model to perform updates.
  • Stochastic Forward Search: Since the model space is now massive, traditional offline planning fails. Instead, the agent uses a look-ahead tree search. It simulates potential future actions and observations to estimate which current move has the highest expected reward.

Experiments and Key Insights

The iPOMDP was evaluated on several classic and modified RL benchmarks, including toy environments like Lineworld and Loopworld (designed to test if the model can distinguish between necessary and irrelevant structural complexity), a variant of the classic Tiger problem (Tiger-3), and standard benchmarks like Shuttle, Network, Gridworld, and a Dialog management task.

Performance and state evolution in Lineworld and Loopworld environments, demonstrating how the iPOMDP dynamically adjusts its state count.

Key Findings

  • "Necessary" Complexity: One of the most striking findings is that the iPOMDP often ignores the "true" state count in favor of a simpler, functional model. For example, in the Dialog task (51 true states), the iPOMDP performed well using only 2 inferred states. It learned that most of the underlying complexity didn't actually matter for making the right decision.
  • State Compression: In the Gridworld task (26 true states), the iPOMDP achieved the best reward in the group while only using about 7.36 states on average. This suggests that nonparametric models are excellent at "lossy compression" of environments.
  • Adaptability: In the Tiger-3 experiment, when the reward suddenly shifted to a new door after 100 episodes, the iPOMDP quickly "added" the necessary complexity to account for the change, whereas a fixed model might have struggled to reconcile the new data with its rigid structure.
  • Computational Efficiency through Simplicity: By starting with a tiny state space and growing it only when needed, the iPOMDP can actually be faster than models that are told the "correct" (but large) state count from the start. It avoids wasting time calculating transitions for states it hasn't even seen yet.

Limitations and Future Work

While the iPOMDP is an elegant solution to structural uncertainty, it isn't a silver bullet:

  • Computational Overhead: The Markov Chain Monte Carlo (MCMC) sampling required for belief monitoring and the forward tree search are still computationally expensive. Scaling this to real-time robotics with high-frequency updates remains a challenge.
  • Discrete Focus: The paper focuses primarily on discrete state and observation spaces. While extending this to continuous observations is straightforward, continuous action spaces or truly massive environments would require more sophisticated planning algorithms.
  • Hyperparameter Sensitivity: The model relies on concentration parameters that influence how quickly new states are created. Finding the "right" level of curiosity versus stability is still a delicate balance.

Summary updated

Abstract

The Partially Observable Markov Decision Process (POMDP) framework has proven useful in planning domains that require balancing actions that increase an agents knowledge and actions that increase an agents reward. Unfortunately, most POMDPs are complex structures with a large number of parameters. In many realworld problems, both the structure and the parameters are difficult to specify from domain knowledge alone. Recent work in Bayesian reinforcement learning has made headway in learning POMDP models; however, this work has largely focused on learning the parameters of the POMDP model. We define an infinite POMDP (iPOMDP) model that does not require knowledge of the size of the state space; instead, it assumes that the number of visited states will grow as the agent explores its world and explicitly models only visited states. We demonstrate the iPOMDP utility on several standard problems.
BibTeX
@inproceedings{doshivelez2009infinite,
  author = {Finale Doshi-Velez},
  title = {{The Infinite Partially Observable Markov Decision Process}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=S1ZYYdbOWH},
}
Figure