Nonasymptotic Analysis of Monte Carlo Tree Search

References

• Agrawal R (1995) Sample mean based index policies by o (log n) regret for the multi-armed bandit problem. Adv. Appl. Probability 27(4):1054–1078.Crossref, Google Scholar
• Audibert JY, Munos R, Szepesvári C (2009) Exploration–exploitation tradeoff using variance estimates in multi-armed bandits. Theoretical Comput. Sci. 410(19):1876–1902.Crossref, Google Scholar
• Auer P, Cesa-Bianchi N, Fischer P (2002) Finite-time analysis of the multiarmed bandit problem. Machine Learn. 47(2-3):235–256.Crossref, Google Scholar
• Auger D, Couetoux A, Teytaud O (2013) Continuous upper confidence trees with polynomial exploration–consistency. Proc. Joint Eur. Conf. on Machine Learn. and Knowledge Discovery in Databases (Springer, Berlin), 194–209.Google Scholar
• Azizzadenesheli K, Yang B, Liu W, Brunskill E, Lipton ZC, Anandkumar A (2018) Sample-efficient deep RL with generative adversarial tree search. Preprint, version 4, submitted September 5, 2019, arXiv:1806.05780.Google Scholar
• Bartlett P, Gabillon V, Healey J, Valko M (2019) Scale-free adaptive planning for deterministic dynamics & discounted rewards. Chaudhuri K, Salakhutdinov R, eds. Proc. 36th Internat. Conf. on Machine Learn., vol. 97. Proceedings of Machine Learning Research (PMLR), 495–504.Google Scholar
• Bertsekas D (1975) Convergence of discretization procedures in dynamic programming. IEEE Trans. Automated Control 20(3):415–419.Crossref, Google Scholar
• Bertsekas D (2017) Dynamic Programming and Optimal Control (Athena Scientific).Google Scholar
• Browne CB, Powley E, Whitehouse D, Lucas SM, Cowling PI, Rohlfshagen P, Tavener S, et al. (2012) A survey of Monte Carlo tree search methods. IEEE Trans. Comput. Intelligent AI Games 4(1):1–43.Crossref, Google Scholar
• Chang HS, Fu MC, Hu J, Marcus SI (2005) An adaptive sampling algorithm for solving markov decision processes. Oper. Res. 53(1):126–139.Link, Google Scholar
• Coquelin PA, Munos R (2007) Bandit algorithms for tree search. Preprint, version 1, submitted March 13, https://arxiv.org/abs/ 0703062.Google Scholar
• Coulom R (2006) Efficient selectivity and backup operators in monte-carlo tree search. Proc. Internat. Conf. on Comput. and Games (Springer, Berlin), 72–83.Google Scholar
• Dufour F, Prieto-Rumeau T (2012) Approximation of Markov decision processes with general state space. J. Math. Anal. Appl. 388(2):1254–1267.Crossref, Google Scholar
• Dufour F, Prieto-Rumeau T (2013) Finite linear programming approximations of constrained discounted Markov decision processes. SIAM J. Control Optim. 51(2):1298–1324.Crossref, Google Scholar
• Efroni Y, Dalal G, Scherrer B, Mannor S (2018) Multiple-step greedy policies in approximate and online reinforcement learning. Bengio S, Wallach H, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 31 (Curran Associates, Inc.), 5244–5253.Google Scholar
• Even-Dar E, Mansour Y, Bartlett P (2003) Learning rates for Q-learning. J. Machine Learn. Res. 5(1).Google Scholar
• Guo X, Singh S, Lee H, Lewis RL, Wang X (2014) Deep learning for real-time Atari game play using offline Monte-Carlo tree search planning. Ghahramani Z, Welling M, Cortes C, Lawrence N, Weinberger KQ, eds. Advances in Neural Information Processing Systems, vol. 27 (Curran Associates, Inc.), 3338–3346.Google Scholar
• Hoeffding W (1963) Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 25:13–30.Crossref, Google Scholar
• Hren JF, Munos R (2008) Optimistic planning of deterministic systems. Proc. Eur. Workshop on Reinforcement Learn. (Springer, Berlin), 151–164.Google Scholar
• Jiang DR, Ekwedike E, Liu H (2018) Feedback-based tree search for reinforcement learning. Proc. Internat. Conf. on Machine Learn.Google Scholar
• Kakade S (2003) On the sample complexity of reinforcement learning. PhD thesis, University of London, University College London.Google Scholar
• Kaufmann E, Koolen WM (2017) Monte-carlo tree search by best arm identification. Guyon I, Luxburg UV, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 30 (Curran Associates, Inc.), 4897–4906.Google Scholar
• Kearns M, Mansour Y, Ng AY (2002) A sparse sampling algorithm for near-optimal planning in large markov decision processes. Machine Learn. 49(2-3):193–208.Crossref, Google Scholar
• Kocsis L, Szepesvári C (2006) Bandit based Monte-Carlo planning. Proc. Eur. Conf. on Machine Learn. (Springer, Berlin), 282–293.Google Scholar
• Kocsis L, Szepesvári C, Willemson J (2006) Improved Monte-Carlo search. Technical report, University of Tartu, Tartu, Estonia.Google Scholar
• Mao W, Zhang K, Xie Q, Basar T (2020) Poly-hoot: Monte-carlo planning in continuous space mdps with non-asymptotic analysis. Adv. Neural Inform. Processing Systems 33:4549–4559.Google Scholar
• Mnih V, Kavukcuoglu K, Silver D, Graves A, Antonoglou I, Wierstra D, Riedmiller M (2013) Playing atari with deep reinforcement learning. Preprint, version 1, submitted December 19, https://arxiv.org/abs/ 1312.5602.Google Scholar
• Mnih V, Badia AP, Mirza M, Graves A, Lillicrap T, Harley T, Silver D, et al. (2016) Asynchronous methods for deep reinforcement learning. Proc. Internat. Conf. on Machine Learn 1928–1937.Google Scholar
• Mnih V, Kavukcuoglu K, Silver D, Rusu AA, Veness J, Bellemare MG, Graves A, et al. (2015) Human-level control through deep reinforcement learning. Nature 518(7540):529.Crossref, Google Scholar
• Munos R (2014) From bandits to monte-carlo tree search: The optimistic principle applied to optimization and planning. Foundations Trends® Machine Learn. 7(1):1–129.Google Scholar
• Salomon A, Audibert JY (2011) Deviations of stochastic bandit regret. Proc. Internat. Conf. on Algorithmic Learn. Theory (Springer, Berlin), 159–173.Google Scholar
• Schadd MPD, Winands MHM, van den Herik HJ, Chaslot GMJB, Uiterwijk JWHM (2008) Single-player Monte-Carlo tree search. van den Herik HJ, Xu X, Ma Z, Winands MHM, eds. Computers and Games (Springer, Berlin), 1–12.Crossref, Google Scholar
• Schulman J, Levine S, Abbeel P, Jordan M, Moritz P (2015) Trust region policy optimization. Proc. Internat. Conf. on Machine Learn. 1889–1897.Google Scholar
• Schulman J, Wolski F, Dhariwal P, Radford A, Klimov O (2017) Proximal policy optimization algorithms. Preprint, version 2, submitted August 28, https://arxiv.org/abs/ 1707.06347.Google Scholar
• Shah D, Xie Q (2018) Q-learning with nearest neighbors. Bengio S, Wallach H, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 31 (Curran Associates), 3115–3125.Google Scholar
• Silver D, Huang A, Maddison CJ, Guez A, Sifre L, Van Den Driessche G, Schrittwieser J, et al. (2016) Mastering the game of go with deep neural networks and tree search. Nature 529(7587):484–489.Crossref, Google Scholar
• Silver D, Hubert T, Schrittwieser J, Antonoglou I, Lai M, Guez A, Lanctot M, et al. (2017a) Mastering chess and shogi by self-play with a general reinforcement learning algorithm. Preprint, version 1, submitted December 5, 2017, https://arxiv.org/abs/ 1712.01815.Google Scholar
• Silver D, Schrittwieser J, Simonyan K, Antonoglou I, Huang A, Guez A, Hubert T, et al. (2017b) Mastering the game of go without human knowledge. Nature 550(7676):354.Crossref, Google Scholar
• Stone CJ (1982) Optimal global rates of convergence for nonparametric regression. Ann. Statist. 10(4):1040–1053.Google Scholar
• Strehl AL, Li L, Wiewiora E, Langford J, Littman ML (2006) Pac model-free reinforcement learning. Proc. 23rd Internat. Conf. Machine Learn. (ACM, New York), 881–888.Google Scholar
• Sturtevant NR (2008) An analysis of uct in multi-player games. van den Herik HJ, Xu X, Ma Z, Winands MHM, eds. Computers and Games (Springer, Berlin), 37–49.Crossref, Google Scholar
• Sutton RS (1988) Learning to predict by the methods of temporal differences. Machine Learn. 3(1):9–44.Crossref, Google Scholar
• Teraoka K, Hatano K, Takimoto E (2014) Efficient sampling method for Monte Carlo tree search problem. IEICE Trans. Inform. Systems 97(3):392–398.Crossref, Google Scholar
• Tsybakov AB (2009) Introduction to Nonparametric Estimation. Springer Series in Statistics (Springer, Berlin).Crossref, Google Scholar
• Van Hasselt H, Guez A, Silver D (2016) Deep Reinforcement Learning with Double q-Learning, vol. 2 (AAAI, Palo Alto, CA).Crossref, Google Scholar
• Watkins CJ, Dayan P (1992) Q-learning. Machine Learn. 8(3-4):279–292.Crossref, Google Scholar
• Yang Y, Zhang G, Xu Z, Katabi D (2019) Harnessing structures for value-based planning and reinforcement learning. Preprint, version 3, submitted July 4, 2020, https://arxiv.org/abs/ 1909.12255.Google Scholar