Modern Reinforcement Learning Techniques to Deal with Large Action Spaces

Abstract

When developing reinforcement learning algorithms, the main issues are dealing withlarge state spaces and action spaces. For the most part, the state space complexity problem was solved with the advent of AlphaZero. AlphaZero is able to deal with unfathomably large state spaces by using a combination of neural networks and Monte Carlo tree search (MCTS). However, dealing with large action spaces remain an active area of research. We generalize the AlphaZero algorithm by introducing the GAIL framework andtest a variety of alterations. We find that using Thompson Sampling as a selection procedure during the MCTS could potentially improve upon AlphaZero in two-player zero-sum games. However, AlphaZero is extremely competitive with all variations. We then show the strength of GAIL by applying it to the game of Scrabble whichAlphaZero cannot be applied to due to its extremely large action space. Furthermore, GAIL coupled with the Upper Confidence Bound selection procedure and information set MCTS proves to be state of the art in the game of Scrabble. This also establishes that using information set MCTS can be used with a neural network value estimator in reinforcement learning. Finally, we extend these results to the continuous action space domain by developingROAR. A novel algorithm that drastically lowers the action space complexity by making a finite number of action recommendations based on state context and historical performance via reinforcement learning. We end by successfully training it in a nontrivial robot problem.