The Partially Observable History Process

Dustin Morrill, Amy R. Greenwald, Michael BowlingarXiv 2021 · arXiv

Abstract

The Partially Observable History Process (POHP) is a new mathematical framework that unifies single-agent reinforcement learning (RL) and multi-agent game theory. By abstracting all external forces—adversaries, teammates, and chance—into a single entity called a "daimon," POHP provides a streamlined way to design and analyze algorithms that work across diverse decision-making domains. This paper establishes the theoretical foundations of POHP, proves the necessity of perfect recall for regret minimization, and demonstrates its equivalence to existing models like MDPs and Extensive-Form Games.

Introduction

In artificial intelligence research, different "languages" are traditionally used to describe different decision-making problems. Markov Decision Processes (MDPs) are the standard for single-agent tasks like robot navigation, while Extensive-Form Games (EFGs) are used for multi-agent settings like poker. This fragmentation creates silos: multi-agent models often involve heavy technical machinery, while single-agent models struggle with partial observability or the agency of other players.

The Partially Observable History Process (POHP) addresses this by providing a "unified field theory" for reinforcement learning. It offers a formalism simple enough for single-agent tasks but robust enough to handle the complexities of multi-agent, partially observable environments.

The POHP Framework

The core innovation of the POHP is the daimon: an inexplicable external force that partially determines the environment's evolution. Whether an agent faces a random dice roll, a helpful teacher, or a competitive opponent, the POHP treats all these external factors as part of the daimon’s strategy.

The interaction between the agent and the environment (the daimon) in a Partially Observable History Process.

Key components of the POHP include:

  • History-based state: Rather than assuming a hidden "true state," the model relies on a ledger of actions and observations.
  • Information States: The agent manages its own "state of mind" based on its history, allowing it to handle partial observability naturally.
  • Sub-POHPs: These allow for the analysis of an agent's performance starting from any specific information state, which is crucial for evaluating "sequential rationality" (making good decisions at every step, not just on average).

Theoretical Insights and Key Results

The POHP allows for "agent-centric" reinforcement learning. The agent does not need to model the internal logic of every other player; it only needs to react to the observations it receives. The authors prove that POHP can represent MDPs, POMDPs, Markov Games, and EFGs, making algorithms designed for POHP theoretically universal.

The Role of Perfect Recall

A significant theoretical finding is the necessity of perfect recall. Theorem 1 (The Impossibility Result) proves that without perfect recall of its own past actions and observations, an agent can be forced into situations where it suffers constant "linear regret," regardless of the learning algorithm used.

Conversely, Theorem 2 (The Convergence Result) shows that if an agent maintains perfect recall and employs a "no-immediate-regret" algorithm at every step, its total regret will grow sublinearly. This ensures the agent eventually learns to act optimally relative to its chosen set of alternative strategies.

Hindsight Rationality

The paper argues that "hindsight rationality"—evaluating choices against what could have been done given the observations received—is a superior objective for complex environments compared to traditional equilibrium concepts.

Conclusion and Future Work

While POHP provides a powerful unification, it faces challenges regarding computational efficiency. Perfect recall causes the agent's state to grow with every action, making it computationally expensive. Future research will explore ways to minimize regret without full perfect recall, perhaps through "well-formed" game conditions. Additionally, the authors suggest that POHP is a natural fit for Predictive State Representations (PSRs), and extending POHP to multi-agent PSR settings remains a promising next step.

Summary updated

Abstract

We introduce the partially observable history process (POHP) formalism for reinforcement learning. POHP centers around the actions and observations of a single agent and abstracts away the presence of other players without reducing them to stochastic processes. Our formalism provides a streamlined interface for designing algorithms that defy categorization as exclusively single or multi-agent, and for developing theory that applies across these domains. We show how the POHP formalism unifies traditional models including the Markov decision process, the Markov game, the extensive-form game, and their partially observable extensions, without introducing burdensome technical machinery or violating the philosophical underpinnings of reinforcement learning. We illustrate the utility of our formalism by concisely exploring observable sequential rationality, examining some theoretical properties of general immediate regret minimization, and generalizing the extensive-form regret minimization (EFR) algorithm.
BibTeX
@misc{morrill2021partially,
  author = {Dustin Morrill and Amy R. Greenwald and Michael Bowling},
  title = {{The Partially Observable History Process}},
  year = {2021},
  eprint = {2111.08102},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2111.08102},
}
Figure