Sequential Transfer in Reinforcement Learning with a Generative Model

We are interested in how to design reinforcement learning agents that provably reduce the sample complexity for learning new tasks by transferring knowledge from previously-solved ones. The availability of solutions to related problems poses a fundamental trade-off: whether to seek policies that are expected to achieve high (yet suboptimal) performance in the new task immediately or whether to seek information to quickly identify an optimal solution, potentially at the cost of poor initial behavior. In this work, we focus on the second objective when the agent has access to a generative model of state-action pairs. First, given a set of solved tasks containing an approximation of the target one, we design an algorithm that quickly identifies an accurate solution by seeking the state-action pairs that are most informative for this purpose. We derive PAC bounds on its sample complexity which clearly demonstrate the benefits of using this kind of prior knowledge. Then, we show how to learn these approximate tasks sequentially by reducing our transfer setting to a hidden Markov model and employing spectral methods to recover its parameters. Finally, we empirically verify our theoretical findings in simple simulated domains. For instance, V * θ ∈ R S is the vector of optimal values, p θ (s, a) ∈ R S is the vector of transition probabilities from s, a, r θ ∈ R SA is the flattened reward matrix, and so on. To measure the distance between two models θ, θ , we define ∆ r s,a (θ, θ ) := |r θ (s, a)r θ (s, a)| for the rewards and ∆ p s,a (θ, θ ) = |(p θ (s, a)p θ (s, a)) T V * θ | for the transition probabilities. The latter measures how much the expected return of an agent taking s, a and acting optimally in θ changes when the first transition only is governed by θ . See Appendix A for a quick reference of notation.