# Adversarial Online Multi-Task Reinforcement Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 34 references that are in the map.
- First posted on arXiv 11 Jan 2023.

## Builds on (most cited first, 14 of 14)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/1905.03814/) (2019)
- [RL for Latent MDPs: Regret Guarantees and a Lower Bound](https://mlsanity.com/paper/2102.04939/) (2021)
- [Sample Complexity of Multi-task Reinforcement Learning](https://mlsanity.com/paper/1309.6821/) (2013)
- [Sequential Transfer in Multi-armed Bandit with Finite Set of Models](https://mlsanity.com/paper/1307.6887/) (2013)
- [Lipschitz Lifelong Reinforcement Learning](https://mlsanity.com/paper/2001.05411/) (2020)
- [Active Model Estimation in Markov Decision Processes](https://mlsanity.com/paper/2003.03297/) (2020)
- [A Provably Efficient Sample Collection Strategy for Reinforcement Learning](https://mlsanity.com/paper/2007.06437/) (2020)
- [The Online Coupon-Collector Problem and Its Application to Lifelong Reinforcement Learning](https://mlsanity.com/paper/1506.03379/) (2015)
- [Can Agents Learn by Analogy? An Inferable Model for PAC Reinforcement Learning](https://mlsanity.com/paper/1912.10329/) (2019)

## Abstract (arXiv)

We consider the adversarial online multi-task reinforcement learning setting, where in each of K episodes the learner is given an unknown task taken from a finite set of M unknown finite-horizon MDP models. The learner's objective is to minimize its regret with respect to the optimal policy for each task. We assume the MDPs in M are well-separated under a notion of λ-separability, and show that this notion generalizes many task-separability notions from previous works. We prove a minimax lower bound of Omega(K√DSAH) on the regret of any learning algorithm and an instance-specific lower bound of Omega(fracKλ2) in sample complexity for a class of uniformly-good cluster-then-learn algorithms. We use a novel construction called 2-JAO MDP for proving the instance-specific lower bound. The lower bounds are complemented with a polynomial time algorithm that obtains tildeO(fracKλ2) sample complexity guarantee for the clustering phase and tildeO(√MK) regret guarantee for the learning phase, indicating that the dependency on K and frac1λ2 is tight.