Clustering Markov Decision Processes For Continual Transfer

We consider the problem of a lifelong learning agent that continually encounters a sequence of tasks. After sufficient exposure to the domain, it is conceivable that the agent has developed a large library of task-specific optimal policies that may then be used as a basis for transfer learning - to speed up operation in a novel instance of a task from this domain. We present an algorithm for continual transfer learning in this setting of reinforcement learning with MDPs. A key question now is - is it possible to concisely encode the library to enable efficient transfer and search? Towards this end, we present a theory, framework and algorithms to cluster MDPs to select as source tasks a small subset of a large number of previous tasks. Our contributions are as follows. We present a principled policy-reuse algorithm that optimally reuses a given set of source policies when solving a particular MDP. We then present a framework for clustering the previously solved MDPs to obtain a source MDP set which optimize the reuse performance of our transfer algorithm. The framework consists of (i) a class of distance functions over MDPs which helps define clustering of MDPs; (ii) a cost function which measures how good a particular clustering is for generating useful source tasks for the transfer algorithm and (iii) provably convergent optimization algorithm for finding the optimal cluster. Finally, we present a set of experiments that illustrate the efficacy of our approach.

• Publication year

  2013

• Venue

  arXiv.org

• Publication date

  2013-11-15

• Fields of study

  Computer Science

• Identifiers
  arXiv 1311.3959
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Decision making : neural and behavioural approaches

  2013cited by this paper
• Markov chains and mixing times

  2013influential reference
• Relativized hierarchical decomposition of Markov decision processes.

  2013cited by this paper
• Regret Bounds for Reinforcement Learning with Policy Advice

  2013cited by this paper
• The variational hierarchical EM algorithm for clustering hidden Markov models

  2012cited by this paper
• Security Games with Limited Surveillance

  2012cited by this paper
• Reinforcement learning transfer via sparse coding

  2012cited by this paper
• Using Bisimulation for Policy Transfer in MDPs

  2010cited by this paper
• Probabilistic Policy Reuse for inter-task transfer learning

  2010cited by this paper
• Simulated Annealing

  2010cited by this paper
• Website Morphing

  2009cited by this paper
• Reinforcement Learning in Finite MDPs: PAC Analysis

  2009cited by this paper
• Arbitrarily modulated Markov decision processes

  2009cited by this paper
• Transfer via soft homomorphisms

  2009cited by this paper
• Transfer Learning for Reinforcement Learning Domains: A Survey

  2009cited by this paper
• An analysis of model-based Interval Estimation for Markov Decision Processes

  2008cited by this paper
• Markov Decision Processes with Arbitrary Reward Processes

  2008cited by this paper
• Transfer of samples in batch reinforcement learning

  2008cited by this paper
• Transfer of task representation in reinforcement learning using policy-based proto-value functions

  2008cited by this paper
• Multi-task reinforcement learning: a hierarchical Bayesian approach

  2007influential reference
• Building Portable Options: Skill Transfer in Reinforcement Learning

  2007cited by this paper
• An Experts Algorithm for Transfer Learning

  2007cited by this paper
• Probabilistic policy reuse in a reinforcement learning agent

  2006cited by this paper
• Prediction, learning, and games

  2006cited by this paper
• Springer

  2006cited by this paper
• Robust Control of Markov Decision Processes with Uncertain Transition Matrices

  2005cited by this paper
• Proto-value functions: developmental reinforcement learning

  2005cited by this paper
• Monte Carlo Statistical Methods

  2005cited by this paper
• Task similarity measures for transfer in reinforcement learning task libraries

  2005cited by this paper
• Metrics for Finite Markov Decision Processes

  2004cited by this paper
• Monte Carlo Statistical Methods

  2004cited by this paper
• SMDP Homomorphisms: An Algebraic Approach to Abstraction in Semi-Markov Decision Processes

  2003cited by this paper
• The Nonstochastic Multiarmed Bandit Problem

  2002influential reference
• Finite-time Analysis of the Multiarmed Bandit Problem

  2002influential reference
• Optimal Structure Identification With Greedy Search

  2002cited by this paper
• Simulated Annealing Algorithms for Continuous Global Optimization: Convergence Conditions

  2000cited by this paper
• A Model of Inductive Bias Learning

  2000cited by this paper
• Reinforcement Learning: An Introduction

  1998cited by this paper
• Reinforcement Learning: : An Introduction

  1998cited by this paper
• Learning Equivalence Classes of Bayesian Network Structures

  1996cited by this paper
• Learning from delayed rewards

  1995cited by this paper
• Explanation-based neural network learning a lifelong learning approach

  1995cited by this paper
• Markov Decision Processes: Discrete Stochastic Dynamic Programming

  1994cited by this paper
• Learning Bayesian Networks: The Combination of Knowledge and Statistical Data

  1994cited by this paper
• Lifelong robot learning

  1993cited by this paper
• Explanation-Based Neural Network Learning for Robot Control

  1992cited by this paper
• Aggregating strategies

  1990cited by this paper
• The weighted majority algorithm

  1989cited by this paper
• Simulated Annealing

  1989cited by this paper
• Robotics and autonomous systems

  1988cited by this paper
• Optimization by Simulated Annealing

  1983influential reference
• Introductory Real Analysis

  1972influential reference
• Reducibility Among Combinatorial Problems

  1972cited by this paper

• CHIRPs: Change-Induced Regret Proxy metrics for Lifelong Reinforcement Learning

  2024cites this paper
• Structural Similarity for Improved Transfer in Reinforcement Learning

  2022cites this paper
• A taxonomy for similarity metrics between Markov decision processes

  2022influential citation
• Similarity metrics for Different Market Scenarios in Abides

  2021cites this paper
• Accelerating Lifelong Reinforcement Learning via Reshaping Rewards*

  2021cites this paper
• A Taxonomy of Similarity Metrics for Markov Decision Processes

  2021cites this paper
• Unsupervised Task Clustering for Multi-task Reinforcement Learning

  2021cites this paper
• TempLe: Learning Template of Transitions for Sample Efficient Multi-task RL

  2020cites this paper
• Lipschitz Lifelong Reinforcement Learning

  2020cites this paper
• Generalizing to generalize: Humans flexibly switch between compositional and conjunctive structures during reinforcement learning

  2020cites this paper
• Sequential Transfer in Reinforcement Learning with a Generative Model

  2020cites this paper
• Information-theoretic Task Selection for Meta-Reinforcement Learning

  2020cites this paper
• Generalizing to generalize: humans flexibly switch between compositional and conjunctive structures during reinforcement learning

  2019cites this paper
• Reinforcement learning for Dialogue Systems optimization with user adaptation. (Apprentissage par Renforcement pour l'optimisation des systèmes de dialogue via l'adaptation à l'utilisateur)

  2019cites this paper
• Markov Decision Processes with Continuous Side Information

  2017cites this paper
• Compositional clustering in task structure learning

  2017cites this paper
• Online learning and transfer for user adaptation in dialogue systems

  2017cites this paper
• Explorer Bayesian Policy Reuse

  2017influential citation
• Making Friends on the Fly: Advances in Ad Hoc Teamwork

  2015cites this paper
• Bayesian policy reuse

  2015influential citation
• Learning domain abstractions for long lived robots

  2014cites this paper
• Lifelong transfer learning with an option hierarchy

  2013cites this paper