Decision Tree Function Approximation in Reinforcement Learning

Abstract

The goal in reinforcement learning is to learn the value of taking each action from each possible state in order to maximize the total reward. In scaling reinforcement learning to problems with large numbers of states and/or actions, the representation of the value function becomes critical. We present a decision tree based approach to function approximation in reinforcement learning. We compare our approach with table lookup and a neural network function approximator on three problems: the well known mountain car and pole balance problems as well as a simulated automobile race car. We find that the decision tree can provide better learning performance than the neural network function approximation and can solve large problems that are infeasible using table lookup. 1 Motivation Reinforcement learning is an approach to learning by interacting with the environment. It is modeled on the type of learning that occurs in nature. When we do something that brings a positive reward (pleasure...