This paper motivates and develops source traces for temporal difference (TD) learning in the tabular setting. Source traces are like eligibility traces, but model potential histories rather than immediate ones. This allows TD errors to be propagated to potential causal states and leads to faster generalization. Source traces can be thought of as the model-based, backward view of successor representations (SR), and share many of the same benefits. This view, however, suggests several new ideas. First, a TD( @math )-like source learning algorithm is proposed and its convergence is proven. Then, a novel algorithm for learning the source map (or SR matrix) is developed and shown to outperform the previous algorithm. Finally, various approaches to using the source SR model are explored, and it is shown that source traces can be effectively combined with other model-based methods like Dyna and experience replay.
Much like the backward and forward views of TD( @math ) offer different insights @cite_4 , so too do the backward view (source traces) and the forward view (SR) here. For instance, the forward view suggests the following useful characterization: we can think of @math as the solution @math of a derivative MRP with the same dynamics as the underlying MRP, but with zero reward everywhere state @math , where the reward is 1. This suggests that source traces may be found by TD learning as the solutions to a set of derivative MRPs (one for each state). This algorithm was proposed by dayan1993improving dayan1993improving . By contrast, the backward view prompts an alternative algorithm based on TD( @math ) that offers a faster initial learning curve at the price of increased variance. We combine the two algorithms in Section to get the best of both worlds. This shift in perspective produces several other novel ideas, which we explore below.
@cite_4
2121863487
Reinforcement learning, one of the most active research areas in artificial intelligence, is a computational approach to learning whereby an agent tries to maximize the total amount of reward it receives when interacting with a complex, uncertain environment. In Reinforcement Learning, Richard Sutton and Andrew Barto provide a clear and simple account of the key ideas and algorithms of reinforcement learning. Their discussion ranges from the history of the field's intellectual foundations to the most recent developments and applications. The only necessary mathematical background is familiarity with elementary concepts of probability. The book is divided into three parts. Part I defines the reinforcement learning problem in terms of Markov decision processes. Part II provides basic solution methods: dynamic programming, Monte Carlo methods, and temporal-difference learning. Part III presents a unified view of the solution methods and incorporates artificial neural networks, eligibility traces, and planning; the two final chapters present case studies and consider the future of reinforcement learning.