Action Selection for MDPs: Anytime AO* Versus UCT

Blai Bonet, Hector GeffnerAAAI 2012 · OpenReview

Abstract

In the presence of non-admissible heuristics, A and other best-first algorithms can be converted into anytime optimal algorithms over OR graphs by continuing the search after the first solution is found. However, this approach does not directly translate to AND/OR graphs, which require expanding leaf nodes that may not be part of the current best partial solution. Anytime optimal variants of AO must therefore address an exploration-exploitation tradeoff. This paper introduces Anytime AO* (AOT), a variant applied to finite-horizon MDPs that achieves optimality using non-admissible random heuristics, such as base policy rollouts. AOT is evaluated for action selection in large infinite-horizon MDPs and compared against the UCT algorithm.

Introduction

Solving large-scale Markov Decision Processes (MDPs) often involves a choice between two paradigms: heuristic search and Monte Carlo Tree Search (MCTS). Heuristic search algorithms like AO are highly efficient when provided with admissible (optimistic) heuristics but typically lack "anytime" capabilities and struggle with non-admissible guidance. Conversely, MCTS algorithms like UCT are inherently anytime and can leverage base policies through sampling, but they often fail to fully exploit the known transition model, leading to slower convergence in structured environments. This work bridges this gap by introducing Anytime AO (AOT), which brings the benefits of heuristic search to the anytime setting.

The Anytime AO* Algorithm

AOT modifies the classic AO* framework to handle non-admissible heuristics and provide anytime performance through several key mechanisms:

  1. Exploration-Exploitation Tradeoff: Standard AO* is purely exploitative, expanding only nodes in the best partial solution. AOT introduces a stochastic exploration component: with probability $p$, it expands a node outside the current best path. This ensures that the algorithm eventually explores the entire state space, preventing it from being trapped by poor initial heuristic estimates.
  2. Sampling Non-Admissible Heuristics: Traditional heuristic search requires static, optimistic bounds. AOT allows for "random heuristics," such as the cost of a base policy. It initializes leaf nodes using rollout samples and propagates these values via Bellman backups, similar to MCTS but within a structured search graph.
  3. Impact-Based Tip Selection: To optimize node expansion, AOT uses a metric $\Delta(n)$ that quantifies the change in a node's value required to alter the current best policy. By prioritizing nodes with minimal $|\Delta(n)|$, the algorithm focuses its search on the most critical decision points.

Experimental Evaluation

The performance of AOT was evaluated on three benchmark domains: the Canadian Traveller Problem (CTP), Sailing, and Racetrack.

Figure 1: Comparison of AOT and UCT on the 100x100 Sailing and barto-big Racetrack domains using a random base policy. AOT shows a clear advantage in reducing average accumulated cost as more computation time is allocated.

In the Sailing and Racetrack domains, AOT consistently outperformed UCT. As seen in Figure 1, AOT achieves lower average costs more quickly than UCT in both the 100x100 Sailing grid and the "barto-big" Racetrack instance. While UCT benefits from simple, fast rollouts, AOT's model-based updates allow it to converge to superior policies with fewer total expansions.

Figure 5: Comparison of AOT variants and LRTDP on CTP instances (20-1 and 20-4) with zero and min-min heuristics. AOT(pi_h), which utilizes base policy rollouts, significantly outperforms standard heuristic search methods like LRTDP.

In the Canadian Traveller Problem (CTP), AOT demonstrated significant gains over traditional real-time dynamic programming. Figure 5 illustrates that AOT variants, particularly those using base policy rollouts (AOT(pi_h)), achieve much lower costs than LRTDP. The authors also noted that AOT often achieved lower costs with 1,000 expansions than UCT did with 10,000 rollouts in this domain.

Conclusion

Anytime AO* (AOT) represents a powerful synthesis of heuristic search and MCTS. By incorporating an exploration-exploitation tradeoff and the ability to sample non-admissible heuristics, it provides a model-based anytime algorithm that frequently outperforms UCT in structured MDPs. While AOT has higher memory requirements and per-iteration computational costs, its superior convergence rate makes it highly effective for complex planning problems where a model is available. Future research will focus on approximating the $\Delta(n)$ selection criterion to further improve scalability.

Summary updated

Abstract

In the presence of non-admissible heuristics, A* and other best-first algorithms can be converted into anytime optimal algorithms over OR graphs, by simply continuing the search after the first solution is found. The same trick, however, does not work for best-first algorithms over AND/OR graphs, that must be able to expand leaf nodes of the explicit graph that are not necessarily part of the best partial solution. Anytime optimal variants of AO* must thus address an exploration-exploitation tradeoff: they cannot just "exploit", they must keep exploring as well. In this work, we develop one such variant of AO* and apply it to finite-horizon MDPs. This Anytime AO* algorithm eventually delivers an optimal policy while using non-admissible random heuristics that can be sampled, as when the heuristic is the cost of a base policy that can be sampled with rollouts. We then test Anytime AO* for action selection over large infinite-horizon MDPs that cannot be solved with existing off-line heuristic search and dynamic programming algorithms, and compare it with UCT.
BibTeX
@inproceedings{bonet2012action,
  author = {Blai Bonet and Hector Geffner},
  title = {{Action Selection for MDPs: Anytime AO* Versus UCT}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2012},
  url = {https://openreview.net/forum?id=SyWF3JZObr},
}
Figure