Exponentiated Gradient Methods for Reinforcement Learning

Abstract

This paper introduces and evaluates a natural extension of linear exponentiated gradient methods that makes them applicable to reinforcement learning problems. Just as these methods speed up supervised learning, we find that they can also increase the efficiency of reinforcement learning. Comparisons are made with conventional reinforcement learning methods on two test problems using CMAC function approximators and replacing traces. On a small prediction task, exponentiated gradient methods showed no improvement, but on a larger control task (Mountain Car) they improved the learning speed by approximately 25%. A more detailed analysis suggests that the difference may be due to the distribution of irrelevant features. 1 INTRODUCTION Exponentiated gradient (EG) methods were first proposed by Littlestone (1988) in the form of the Winnow algorithm for training linear threshold classifiers. Kivinen and Warmuth (1994) proposed the first EG methods for on-line linear regression. The analogou...