Abstract
Partially observable environments present a considerable computationalchallenge in reinforcement learning due to the need to consider long histories.Learning with a finite window of observations quickly becomes intractable asthe window length grows. In this work, we introduce memory traces. Inspired byeligibility traces, these are compact representations of the history ofobservations in the form of exponential moving averages. We prove samplecomplexity bounds for the problem of offline on-policy evaluation that quantifythe value errors achieved with memory traces for the class of Lipschitzcontinuous value estimates. We establish a close connection to the windowapproach, and demonstrate that, in certain environments, learning with memorytraces is significantly more sample efficient. Finally, we underline theeffectiveness of memory traces empirically in online reinforcement learningexperiments for both value prediction and control.