2020/07/01 by Andrea Tirinzoni, Riccardo Poiani, Tirinzoni, Andrea +3 · 3 citations
Computer Science · Mathematics · #Action (physics) #Artificial intelligence #Computer science #Data Stream Mining Techniques #Evolutionary Algorithms and Applications #Generative grammar #Generative model #Hidden Markov model #Machine learning #Markov decision process #Markov process #Mathematics #Reinforcement Learning in Robotics #Reinforcement learning #Sample (material) #Sample complexity #Set (abstract data type) #Task (project management) #Transfer of learning #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.2007.00722
published in arXiv (Cornell University) 1, 9481-9492 (Cornell University) · ICML 2020
arxiv created 2020/07/01 · openalex publication_date 2020/07/01 · arxiv updated 2020/07/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 sub-optimal) 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.