EUVIMEDEUVIMED entdecken
Crossref

Extreme Value Monte Carlo Tree Search for Classical Planning

Masataro Asai, Stephen Wissow

Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (43) · 36163-36171

DOI: 10.1609/aaai.v40i43.40934 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Masataro Asai und 1 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Despite being successful in board games and reinforcement learning (RL), Monte Carlo Tree Search (MCTS) combined with Multi Armed Bandit (MAB) has seen limited success in domain-independent classical planning until recently. Previous work (Wissow and Asai, 2024) showed that UCB1, designed for bounded rewards, does not perform well as applied to cost-to-go estimates in classical planning, because cost-to-go estimates are unbounded, and showed improved performance using a Gaussian reward MAB instead. This paper further sharpens our understanding of ideal bandits for planning tasks. Existing work has two issues: first, Gaussian MABs under-specify the support of cost-to-go estimates as (-∞, ∞), which we can narrow down. Second, Full Bellman backup (Schulte and Keller, 2014) that backpropagates sample max/min lacks theoretical justification. We use Peaks-Over-Threashold Extreme Value Theory to resolve both issues at once, propose a new bandit algorithm (UCB1-Uniform). We formally prove its regret bound and empirically demonstrate its performance in classical planning.

Zitieren

APA

Asai, M., & Wissow, S. (2026). Extreme Value Monte Carlo Tree Search for Classical Planning. Proceedings of the AAAI Conference on Artificial Intelligence, 40(43), 36163-36171. https://doi.org/10.1609/aaai.v40i43.40934

Vancouver

Asai M, Wissow S. Extreme Value Monte Carlo Tree Search for Classical Planning. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(43):36163-36171. doi:10.1609/aaai.v40i43.40934

BibTeX
@article{Asai2026,
  author = {Asai, Masataro and Wissow, Stephen},
  title = {Extreme Value Monte Carlo Tree Search for Classical Planning},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2026},
  volume = {40},
  number = {43},
  pages = {36163--36171},
  doi = {10.1609/aaai.v40i43.40934}
}
Kostenlos starten →