Ari Weinstein
Ari Weinstein,
an American computer scientist at Google DeepMind. He holds a Ph.D. from Rutgers University under advisor Michael L. Littman on Local Planning For Continuous Markov Decision Processes, covering algorithms that create plans to maximize a numeric reward over time. While a general formulation of this problem in terms of
reinforcement learning has traditionally been restricted to small discrete domains, Weinstein thesis include both continuous and high dimensional domains, with simulations of swimming, riding a bicycle, and walking as concrete examples.
FSSS-Minimax
In their paper Rollout-based Game-tree Search Outprunes Traditional Alpha-beta, along with Sergiu Goschin and his advisor Michael Littman [1], Weinstein introduce the rollout-based FSSS (Forward-search sparse sampling) [2] applied to game-tree search, outpruning alpha-beta both empirically and formally. FSSS-Minimax only visits parts of the tree that alpha-beta visits, and is in terms of related work similar to the Score Bounded Monte-Carlo Tree Search introduced by Tristan Cazenave and Abdallah Saffidine [3].
Recently, rollout-based planning and search methods have emerged as an alternative to traditional tree-search methods. The fundamental operation in rollout-based tree search is the generation of trajectories in the search tree from root to leaf. Game-playing programs based on Monte-Carlo rollouts methods such as “UCT” have proven remarkably effective at using information from trajectories to make state-of-the-art decisions at the root. In this paper, we show that trajectories can be used to prune more aggressively than classical alpha-beta search. We modify a rollout-based method, FSSS, to allow for use in game-tree search and show it outprunes alpha-beta both empirically and formally.
While FSSS-Minimax is guaranteed to never expand more leaves than alpha-beta, the best-first approach comes at a cost in terms of memory requirements as well as computational cost.
Selected Publications
- Ari Weinstein, Michael L. Littman (2012). Bandit-Based Planning and Learning in Continuous-Action Markov Decision Processes. ICAPS 2012
- Ari Weinstein, Michael L. Littman, Sergiu Goschin (2013). Rollout-based Game-tree Search Outprunes Traditional Alpha-beta. PMLR, Vol. 24 » MCTS, UCT
- Sergiu Goschin, Ari Weinstein, Michael L. Littman (2013). The Cross-Entropy Method Optimizes for Quantiles. ICML 2013
- Ari Weinstein, Michael L. Littman (2013). Open-Loop Planning in Large-Scale Stochastic Domains. AAAI-2013
- Ari Weinstein (2013). Local Planning For Continuous Markov Decision Processes. Ph.D. thesis, Rutgers University, advisor Michael L. Littman, pdf
- Ari Weinstein, Matthew Botvinick (2017). Structure Learning in Motor Control: A Deep Reinforcement Learning Model. arXiv:1706.06827
External Links
References
- ↑ Ari Weinstein, Michael L. Littman, Sergiu Goschin (2013). Rollout-based Game-tree Search Outprunes Traditional Alpha-beta. PMLR, Vol. 24
- ↑ Thomas J. Walsh, Sergiu Goschin, Michael L. Littman (2010). Integrating sample-based planning and model-based reinforcement learning. AAAI-2010, pdf
- ↑ Tristan Cazenave, Abdallah Saffidine (2010). Score Bounded Monte-Carlo Tree Search. CG 2010, pdf
- ↑ dblp: Ari Weinstein
- ↑ Doctoral Dissertations Advised by Michael Littman