The Online Coupon-Collector Problem and Its Application to Lifelong Reinforcement Learning

Understand

Transferring knowledge across a sequence of related tasks is an important challenge in reinforcement learning (RL).

• Despite much encouraging empirical evidence, there has been little theoretical analysis.
• In this paper, we study a class of lifelong RL problems: the agent solves a sequence of tasks modeled as finite Markov decision processes (MDPs), each of which is from a finite set of MDPs with the same state/action sets and different transition/reward functions.
• Motivated by the need for cross-task exploration in lifelong learning, we formulate a novel online coupon-collector problem and give an optimal algorithm.