Learning Predictive State Representations via Monte-Carlo Tree Search

Yunlong Liu, Hexing Zhu, Yifeng Zeng, Zongxiong DaiIJCAI 2016 · OpenReview

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.

Average prediction error in the Cheese Maze environment. MCTS significantly outperforms EM and TPSR as the model size increases.

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.

Average prediction error in the large-scale PocMan environment. MCTS maintains superior and stable prediction accuracy compared to baseline methods.

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

Abstract

Predictive State Representations (PSRs) are an efficient method for modelling partially observable dynamical systems. They have shown advantages over the latent state-based approaches by using functions of a set of observable quantities, called tests, to represent model states. As a consequence, discovering the set of tests for representing the state is one of the central problems in PSRs. Existing techniques either discover these tests through iterative methods, which can only be applied to some toy problems, or avoid the complex discovery problem by maintaining a very large set of tests, which may be prohibitively expensive. In this paper, with the benefits of Monte-Carlo tree search (MCTS) for finding solutions in complex problems, and by proposing the concept of model entropy for measuring the model accuracy as the evaluation function in MCTS, the discovery problem is formalized as a sequential decision making problem. Then such a decision making problem can be solved using MCTS, a set of tests for representing state can be obtained and the PSR model of the underlying system can be learned straightforwardly. We conduct experiments on several domains including one extremely large domain and the experimental results show the effectiveness of our approach.
BibTeX
@inproceedings{liu2016learning,
  author = {Yunlong Liu and Hexing Zhu and Yifeng Zeng and Zongxiong Dai},
  title = {{Learning Predictive State Representations via Monte-Carlo Tree Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=SJ478NMObr},
}
Figure