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

arXiv: https://arxiv.org/abs/1506.03379 · HTML: https://mlsanity.com/paper/1506.03379/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jun 2015.

## Built on by (most cited first, 2 of 2)

- [Learning to be Fair: A Consequentialist Approach to Equitable Decision-Making](https://mlsanity.com/paper/2109.08792/) (2021)
- [Adversarial Online Multi-Task Reinforcement Learning](https://mlsanity.com/paper/2301.04268/) (2023)

## Abstract (arXiv)

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. This allows us to develop a new lifelong RL algorithm, whose overall sample complexity in a sequence of tasks is much smaller than single-task learning, even if the sequence of tasks is generated by an adversary. Benefits of the algorithm are demonstrated in simulated problems, including a recently introduced human-robot interaction problem.