Abstract
Modeling complex, partially observable dynamical systems is a fundamental challenge in artificial intelligence. While traditional latent-state models like POMDPs are common, they often suffer from local optima during learning. Predictive State Representations (PSRs) offer an alternative by representing state through observable future events. However, identifying the optimal set of "core tests" for a PSR is a difficult search problem. This paper proposes a novel approach using Monte-Carlo Tree Search (MCTS) guided by a model entropy metric to discover compact and accurate PSRs.
Introduction
In many real-world scenarios, agents must navigate environments where the full state is not directly observable. Standard approaches like Hidden Markov Models (HMMs) rely on hidden variables that lack physical meaning and are notoriously difficult to learn. PSRs circumvent this by using the probabilities of future observations (tests) to define the state. The primary bottleneck for PSRs is the "discovery problem": selecting a small, sufficient set of tests from an infinite space.
MCTS for Test Discovery
The authors frame the discovery of core tests as a sequential decision-making problem. They employ Monte-Carlo Tree Search (MCTS) to explore the space of possible test sets. Each "action" in the search tree corresponds to adding a specific test to the current representation.
To evaluate the quality of a test set, the authors introduce model entropy. This metric measures the degree of determinism in the transitions of a Markov Decision Process (MDP) constructed from the selected tests. A lower entropy indicates a more accurate representation of the underlying system dynamics. By maximizing the negative model entropy as a reward, MCTS efficiently identifies high-performing, compact models without the need for computationally expensive high-dimensional matrix operations.
Experimental Results
The proposed method was evaluated on three benchmarks of increasing complexity: Cheese Maze, Hallway2, and PocMan.
In the Cheese Maze (Figure 1), the MCTS-based approach demonstrates a rapid decrease in prediction error as more tests are added, reaching near-zero error. In contrast, traditional methods like Expectation-Maximization (EM) and Transformed PSRs (TPSR) plateau at much higher error levels.
The scalability of the approach is most evident in the PocMan domain, which features an astronomical state space of approximately $10^{56}$ states, making it a significant challenge for traditional modeling techniques.
As shown in Figure 5, MCTS consistently achieves lower prediction error than EM, TPSR, and Constrained PSR (CPSR) in the PocMan domain. Notably, while TPSR performance can degrade due to noise in high-dimensional matrix operations, the MCTS search remains robust and continues to improve as more dimensions are explored.
Conclusion and Future Work
By leveraging MCTS and a novel entropy-based reward, this work provides a powerful framework for learning PSRs in large-scale, partially observable environments. The resulting models are both more accurate and more compact than those produced by existing techniques. Future research will focus on reducing the computational overhead of the reward function and integrating these learned models into active planning agents for reinforcement learning.
Summary updated