Multi-step Prediction using Tree Generation for Reinforcement Learning

The goal of reinforcement learning is to learn a policy that maximizes a reward function. In some environments with complete information, search algorithms are highly useful in simulating action sequences in a game tree. However, in many practical environments, such effective search strategies are not applicable since their state transition information may not be available. This paper proposes a novel method to approximate a game tree that enables reinforcement learning to use search strategies even in incomplete information environments. With an approximated game tree, the agent predicts all possible states multiple steps into the future and evaluates the states to determine the best action sequences with the highest return. Our proposal differs from deep reinforcement learning in that it uses deep learning for not only the state evaluation but also game tree approximation. This allows it to perform better in completing complex tasks as well as learning in sparse reward environments.