Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1649045, author = {Ashok, Pranav and Brázdil, Tomáš and Křetínský, Jan and Slámečka, Ondřej}, address = {Cham}, booktitle = {Leveraging Applications of Formal Methods, Verification and Validation (ISoLA 2018)}, doi = {http://dx.doi.org/10.1007/978-3-030-03421-4_21}, keywords = {Monte Carlo Tree Search; Reachability; Markov Decision Processes}, howpublished = {tištěná verze "print"}, language = {eng}, location = {Cham}, isbn = {978-3-030-03420-7}, pages = {322-335}, publisher = {Springer}, title = {Monte Carlo Tree Search for Verifying Reachability in Markov Decision Processes}, year = {2018} }
TY - JOUR ID - 1649045 AU - Ashok, Pranav - Brázdil, Tomáš - Křetínský, Jan - Slámečka, Ondřej PY - 2018 TI - Monte Carlo Tree Search for Verifying Reachability in Markov Decision Processes PB - Springer CY - Cham SN - 9783030034207 KW - Monte Carlo Tree Search KW - Reachability KW - Markov Decision Processes N2 - The maximum reachability probabilities in a Markov decision process can be computed using value iteration (VI). Recently, simulation-based heuristic extensions of VI have been introduced, such as bounded real-time dynamic programming (BRTDP), which often manage to avoid explicit analysis of the whole state space while preserving guarantees on the computed result. In this paper, we introduce a new class of such heuristics, based on Monte Carlo tree search (MCTS), a technique celebrated in various machine-learning settings. We provide a spectrum of algorithms ranging from MCTS to BRTDP. We evaluate these techniques and show that for larger examples, where VI is no more applicable, our techniques are more broadly applicable than BRTDP with only a minor additional overhead. ER -
ASHOK, Pranav, Tomáš BRÁZDIL, Jan KŘETÍNSKÝ and Ondřej SLÁMEČKA. Monte Carlo Tree Search for Verifying Reachability in Markov Decision Processes. In \textit{Leveraging Applications of Formal Methods, Verification and Validation (ISoLA 2018)}. Cham: Springer, 2018, p.~322-335. ISBN~978-3-030-03420-7. Available from: https://dx.doi.org/10.1007/978-3-030-03421-4\_{}21.
|