Open Problem: The Dependence of Sample Complexity Lower Bounds on Planning Horizon

Nan Jiang, Alekh Agarwal
Proceedings of the 31st Conference On Learning Theory, PMLR 75:3395-3398, 2018.

Abstract

In reinforcement learning (RL), problems with long planning horizons are perceived as very challenging. The recent advances in PAC RL, however, show that the sample complexity of RL does not depend on planning horizon except at a superficial level. How can we explain such a difference? Noting that the technical assumptions in these upper bounds might have hidden away the challenges of long horizons, we ask the question: \emph{can we prove a lower bound with a horizon dependence when such assumptions are removed?} We also provide a few observations on the desired characteristics of the lower bound construction.

Cite this Paper

BibTeX
@InProceedings{pmlr-v75-jiang18a, title = {Open Problem: The Dependence of Sample Complexity Lower Bounds on Planning Horizon}, author = {Jiang, Nan and Agarwal, Alekh}, booktitle = {Proceedings of the 31st Conference On Learning Theory}, pages = {3395--3398}, year = {2018}, editor = {Bubeck, Sébastien and Perchet, Vianney and Rigollet, Philippe}, volume = {75}, series = {Proceedings of Machine Learning Research}, month = {06--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v75/jiang18a/jiang18a.pdf}, url = {https://proceedings.mlr.press/v75/jiang18a.html}, abstract = {In reinforcement learning (RL), problems with long planning horizons are perceived as very challenging. The recent advances in PAC RL, however, show that the sample complexity of RL does not depend on planning horizon except at a superficial level. How can we explain such a difference? Noting that the technical assumptions in these upper bounds might have hidden away the challenges of long horizons, we ask the question: \emph{can we prove a lower bound with a horizon dependence when such assumptions are removed?} We also provide a few observations on the desired characteristics of the lower bound construction.} }
Endnote
%0 Conference Paper %T Open Problem: The Dependence of Sample Complexity Lower Bounds on Planning Horizon %A Nan Jiang %A Alekh Agarwal %B Proceedings of the 31st Conference On Learning Theory %C Proceedings of Machine Learning Research %D 2018 %E Sébastien Bubeck %E Vianney Perchet %E Philippe Rigollet %F pmlr-v75-jiang18a %I PMLR %P 3395--3398 %U https://proceedings.mlr.press/v75/jiang18a.html %V 75 %X In reinforcement learning (RL), problems with long planning horizons are perceived as very challenging. The recent advances in PAC RL, however, show that the sample complexity of RL does not depend on planning horizon except at a superficial level. How can we explain such a difference? Noting that the technical assumptions in these upper bounds might have hidden away the challenges of long horizons, we ask the question: \emph{can we prove a lower bound with a horizon dependence when such assumptions are removed?} We also provide a few observations on the desired characteristics of the lower bound construction.
APA
Jiang, N. & Agarwal, A.. (2018). Open Problem: The Dependence of Sample Complexity Lower Bounds on Planning Horizon. Proceedings of the 31st Conference On Learning Theory, in Proceedings of Machine Learning Research 75:3395-3398 Available from https://proceedings.mlr.press/v75/jiang18a.html.

Related Material