Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Monte-Carlo Planning: Theoretically Fast Convergence Meets Practical Efficiency
Zohar Feldman, Carmel Domshlak
Abstract:
Popular Monte-Carlo tree search (MCTS) algorithms for online planning, such as epsilon-greedy tree search and UCT, aim at rapidly identifying a reasonably good action, but provide rather poor worst-case guarantees on performance improvement over time. In contrast, a recently introduced MCTS algorithm BRUE guarantees exponential-rate improvement over time, yet it is not geared towards identifying reasonably good choices right at the go. We take a stand on the individual strengths of these two classes of algorithms, and show how they can be effectively connected. We then rationalize a principle of ``selective tree expansion", and suggest a concrete implementation of this principle within MCTS. The resulting algorithm,s favorably compete with other MCTS algorithms under short planning times, while preserving the attractive convergence properties of BRUE.
Keywords:
Pages: 212-221
PS Link:
PDF Link: /papers/13/p212-feldman.pdf
BibTex:
@INPROCEEDINGS{Feldman13,
AUTHOR = "Zohar Feldman and Carmel Domshlak",
TITLE = "Monte-Carlo Planning: Theoretically Fast Convergence Meets Practical Efficiency",
BOOKTITLE = "Proceedings of the Twenty-Ninth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-13)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2013",
PAGES = "212--221"
}


hosted by DSL   •   site info   •   help