Belief embedding tree search improves planning under partial observation
Belief Embedding Tree Search
Artificial IntelligenceMachine Learning
Summary
Planning decisions when you don’t know everything about a situation is very hard because you have to guess what’s really going on inside a complex hidden world. The authors developed a new method called Belief Embedding Tree Search (BETS) that keeps track of what could be true in a smart way and learns from experience how to make better guesses. This method builds on a kind of tree search that improves over past techniques by using learned representations of possible states instead of rough samples. They tested BETS on various challenging simulated problems and found it performed better or as well as other strong methods.
What this means in practice
- •For autonomous robot developers: Improve robot decision-making in uncertain environments by integrating BETS for better planning with partial information.
- •For game ai programmers: Use BETS to build more reliable AI agents that plan strategically in games with hidden information and complex state spaces.
Authors
Christopher Solinas, Radovan Haluška, Martin Schmid, Michael Buro, Nathan R. Sturtevant, Michael Bowling
Abstract
Beliefs in a Partially Observable Markov Decision Process (POMDP) are posterior distributions over the hidden state given the agent's history of actions and observations. They summarize everything the history says about the state, so planning in a POMDP is planning in a Markov decision process (MDP) over beliefs. Belief MDPs have continuous state spaces even for finite POMDPs, and exact planning in them is intractable in general. Planners must therefore approximate beliefs and estimate values. Monte Carlo planners do both inside a search tree, with an approximate belief at every node and a value estimate at every leaf. Approximations usually consist of sets of sampled states, with leaf values coming from rollouts, hand-designed bounds, or learned networks. Policies and values computed from these approximations are limited by their quality, and prior methods with learned networks rely on hand-chosen summaries of the sampled states. A belief representation should be computable from the parent node's representation through the POMDP's dynamics, let the search sample from it, and be learned so that it provides the information that policies and value functions need. We present Belief Embedding Tree Search (BETS), a Monte Carlo planner that meets these requirements by representing each node's belief with a generative distribution embedding (GDE) while updating it through the POMDP dynamics. BETS trains its belief model alongside its policy and value networks through experience, with the realized hidden state of the POMDP as the belief model's training target. We evaluate BETS on six configurations of RockSample, LightDark, and PocMan against BetaZero and three planners without learned components. BETS is competitive or leading on all six, while every baseline falls far behind on at least one. Where beliefs are highest-dimensional, it outperforms them by a large margin, even without search.