Planning from Scratch | Yunlong Liu, Jianyang Zheng | ResearchPod

Transcript: Planning from Scratch

Alex: Most planners for hidden, uncertain worlds quietly assume you already know roughly how that world works. This work asks what happens if you know nothing, and only have data. Its answer is to learn a predictive model from logged experience first. Then that model drives a tree search that picks each action.

Sam: Place it for me before we go further. Whose work is it, and what kind?

Alex: It's a 2019 arXiv preprint from Yunlong Liu and Jianyang Zheng at Xiamen University. It's a method paper with a convergence proof and experiments on four standard benchmark problems.

Sam: I work next door to planning, not in it. Why should someone like me care?

Alex: Because the main alternative depends on prior knowledge that real problems rarely provide. If this holds up, you can plan under model uncertainty starting from data alone. So we'll cover what the field relied on before, the one trick that makes this work, and how far the evidence goes.

Sam: Start with the before. What did people do when they didn't trust their model?

Alex: The standard frame is a partially observable problem, meaning the agent can't see the true state, only noisy observations. The Bayesian fix puts a probability distribution over the unknown model and updates it as data arrives. The authors point out a cost: that distribution becomes part of the hidden state. The problem gets bigger than the one you started with, and exact methods only handled toy cases.

Sam: But tree search was supposed to rescue that, wasn't it?

Alex: Partly. Monte-Carlo tree search plans by simulating many possible futures from the current moment and growing a search tree from them. A Bayesian version called BA-POMCP scaled to larger problems. But in the experiments it's compared against, it was handed a lot. In Tiger, the transition model was assumed correct and the observation model nearly correct. In the network maintenance problem, the observation model was assumed known.

Sam: So "learning the model online" really meant fine-tuning a model that was almost right to begin with.

Alex: That's the authors' critique, yes. They argue that in most domains such knowledge is hard to have in advance.

Sam: Then what replaces it? What's the one idea?

Alex: Two pieces. First, a different kind of model, called a Predictive State Representation. Instead of a hidden state you have to guess, the state is a short vector of predictions. Each entry says how likely some sequence of future observations is, given what's happened so far. You can learn it from data with a spectral method, essentially matrix decompositions of observed frequencies. No predefined hidden structure is needed, and you avoid expectation maximization and its local optima.

Planning from Scratch

Yunlong Liu, Jianyang Zheng

Apr 5, 2019·8:20·arxiv·Original Paper

Predictive State Representations (PSRs)Monte-Carlo Tree Search (MCTS)Partially Observable Markov Decision Processes (POMDP)Planning from ScratchBayes-Adaptive POMDP (BA-POMDP)Model Uncertainty

Listen

8 min

Summary

Abstract

Planning in stochastic and partially observable environments is a central issue in artificial intelligence. One commonly used technique for solving such a problem is by constructing an accurate model firstly. Although some recent approaches have been proposed for learning optimal behaviour under model uncertainty, prior knowledge about the environment is still needed to guarantee the performance of the proposed algorithms. With the benefits of the Predictive State Representations~(PSRs) approach for state representation and model prediction, in this paper, we introduce an approach for planning from scratch, where an offline PSR model is firstly learned and then combined with online Monte-Carlo tree search for planning with model uncertainty. By comparing with the state-of-the-art approach of planning with model uncertainty, we demonstrated the effectiveness of the proposed approaches along with the proof of their convergence. The effectiveness and scalability of our proposed approach are also tested on the RockSample problem, which are infeasible for the state-of-the-art BA-POMDP based approaches.

Research Question and Approach

Traditional approaches to planning in partially observable stochastic environments, such as POMDPs, typically rely on having access to a predefined, accurate model of the environment. While some methods attempt to learn optimal behavior under model uncertainty, they often still require significant prior knowledge or accurate initial models to converge. This paper addresses this challenge by proposing PSR-MCTS, an approach that allows an agent to plan from scratch.

Instead of latent-state representations, the authors utilize Predictive State Representations (PSRs). PSRs represent the state of a system as a vector of predictions about future observable events. This framework is naturally easier to learn and avoids the typical challenges associated with latent-state approaches. The proposed method consists of two stages: first, an offline PSR model is learned using training data, where certain reward signals are treated as observations. Second, this learned model acts as a simulator for online Monte-Carlo Tree Search (MCTS), enabling the agent to calculate optimal policies in real-time without relying on prior domain knowledge.

Key Findings

The authors demonstrate that their PSR-MCTS approach effectively handles planning under model uncertainty without requiring any prior information about the environment. Through both theoretical analysis and empirical testing, they show that the method is competitive with state-of-the-art Bayesian approaches, such as BA-POMCP, even when those methods are provided with nearly correct initial models. Furthermore, the approach shows excellent scalability; it was successfully applied to complex problems like the RockSample domain, where traditional BA-POMDP techniques were found to be infeasible due to the complexity of the state space.

Why It Matters

This research provides a more practical solution for real-world applications where building an accurate model of the environment is notoriously difficult. By demonstrating that one can effectively plan from scratch using only observation-based PSRs, the paper offers a robust alternative to complex Bayesian models, which often struggle with computational intractability and dependency on expert-provided prior knowledge.

Key Terms and Definitions

Predictive State Representation (PSR) — A framework for modeling partially observable systems that represents the current state as a vector of predictions regarding future observable events.
Monte-Carlo Tree Search (MCTS) — A heuristic search algorithm used for decision-making that builds a search tree through simulated experiences to estimate the value of actions.
BA-POMDP — A Bayes-Adaptive Partially Observable Markov Decision Process that accounts for model uncertainty by treating model parameters as part of the hidden state.
Hankel Matrix — A bi-infinite matrix used in spectral learning to store joint probabilities of tests (future sequences) and histories (past sequences) to characterize the dynamics of a system.
Minimal Core Tests — A set of tests that serves as a sufficient statistic, containing enough information to calculate the predictions for all other possible tests in a PSR.

Planning from Scratch: Research Paper Podcast