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.
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