License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2020.40
URN: urn:nbn:de:0030-drops-128523
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12852/
Go to the corresponding LIPIcs Volume Portal

Busatto-Gaston, Damien ; Chakraborty, Debraj ; Raskin, Jean-Francois

Monte Carlo Tree Search Guided by Symbolic Advice for MDPs

pdf-format:
LIPIcs-CONCUR-2020-40.pdf (0.7 MB)

Abstract

In this paper, we consider the online computation of a strategy that aims at optimizing the expected average reward in a Markov decision process. The strategy is computed with a receding horizon and using Monte Carlo tree search (MCTS). We augment the MCTS algorithm with the notion of symbolic advice, and show that its classical theoretical guarantees are maintained. Symbolic advice are used to bias the selection and simulation strategies of MCTS. We describe how to use QBF and SAT solvers to implement symbolic advice in an efficient way. We illustrate our new algorithm using the popular game Pac-Man and show that the performances of our algorithm exceed those of plain MCTS as well as the performances of human players.

BibTeX - Entry

@InProceedings{busattogaston_et_al:LIPIcs:2020:12852,
  author =	{Damien Busatto-Gaston and Debraj Chakraborty and Jean-Francois Raskin},
  title =	{{Monte Carlo Tree Search Guided by Symbolic Advice for MDPs}},
  booktitle =	{31st International Conference on Concurrency Theory (CONCUR 2020)},
  pages =	{40:1--40:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-160-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{171},
  editor =	{Igor Konnov and Laura Kov{\'a}cs},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12852},
  URN =		{urn:nbn:de:0030-drops-128523},
  doi =		{10.4230/LIPIcs.CONCUR.2020.40},
  annote =	{Keywords: Markov decision process, Monte Carlo tree search, symbolic advice, simulation}
}

Keywords: Markov decision process, Monte Carlo tree search, symbolic advice, simulation
Collection: 31st International Conference on Concurrency Theory (CONCUR 2020)
Issue Date: 2020
Date of publication: 26.08.2020
Supplementary Material: http://di.ulb.ac.be/verif/debraj/pacman/

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI