Sample Complexity of Transfer Reinforcement Learning

Emma Brunskill, Lihong Li
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:342-351, 2013.

Abstract

Transferring knowledge across a sequence of reinforcement-learning tasks is challenging, and has a number of important applications. Though there is encouraging empirical evidence that transfer can improve performance in subsequent reinforcement-learning tasks, there has been very little theoretical analysis. In this paper, we intro- duce a new multi-task algorithm for a sequence of reinforcement-learning tasks when each task is sampled independently from (an unknown) dis- tribution over a finite set of Markov decision pro- cesses whose parameters are initially unknown. For this setting, we prove under certain assump- tions that the per-task sample complexity of ex- ploration is reduced significantly due to trans- fer compared to standard single-task algorithms. Our multi-task algorithm also has the desired characteristic that it is guaranteed not to exhibit negative transfer: in the worst case its per-task sample complexity is comparable to the corre- sponding single-task algorithm.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-brunskill13a, title = {Sample Complexity of Transfer Reinforcement Learning}, author = {Brunskill, Emma and Li, Lihong}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {342--351}, year = {2013}, editor = {Nicholson, Ann and Smyth, Padhraic}, volume = {R11}, series = {Proceedings of Machine Learning Research}, month = {12--14 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r11/main/assets/brunskill13a/brunskill13a.pdf}, url = {https://proceedings.mlr.press/r11/brunskill13a.html}, abstract = {Transferring knowledge across a sequence of reinforcement-learning tasks is challenging, and has a number of important applications. Though there is encouraging empirical evidence that transfer can improve performance in subsequent reinforcement-learning tasks, there has been very little theoretical analysis. In this paper, we intro- duce a new multi-task algorithm for a sequence of reinforcement-learning tasks when each task is sampled independently from (an unknown) dis- tribution over a finite set of Markov decision pro- cesses whose parameters are initially unknown. For this setting, we prove under certain assump- tions that the per-task sample complexity of ex- ploration is reduced significantly due to trans- fer compared to standard single-task algorithms. Our multi-task algorithm also has the desired characteristic that it is guaranteed not to exhibit negative transfer: in the worst case its per-task sample complexity is comparable to the corre- sponding single-task algorithm.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Sample Complexity of Transfer Reinforcement Learning %A Emma Brunskill %A Lihong Li %B Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2013 %E Ann Nicholson %E Padhraic Smyth %F pmlr-vR11-brunskill13a %I PMLR %P 342--351 %U https://proceedings.mlr.press/r11/brunskill13a.html %V R11 %X Transferring knowledge across a sequence of reinforcement-learning tasks is challenging, and has a number of important applications. Though there is encouraging empirical evidence that transfer can improve performance in subsequent reinforcement-learning tasks, there has been very little theoretical analysis. In this paper, we intro- duce a new multi-task algorithm for a sequence of reinforcement-learning tasks when each task is sampled independently from (an unknown) dis- tribution over a finite set of Markov decision pro- cesses whose parameters are initially unknown. For this setting, we prove under certain assump- tions that the per-task sample complexity of ex- ploration is reduced significantly due to trans- fer compared to standard single-task algorithms. Our multi-task algorithm also has the desired characteristic that it is guaranteed not to exhibit negative transfer: in the worst case its per-task sample complexity is comparable to the corre- sponding single-task algorithm. %Z Reissued by PMLR on 04 October 2026.
APA
Brunskill, E. & Li, L.. (2013). Sample Complexity of Transfer Reinforcement Learning. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:342-351 Available from https://proceedings.mlr.press/r11/brunskill13a.html. Reissued by PMLR on 04 October 2026.

Related Material