Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structure
Proceedings of the ACM on Measurement and Analysis of Computing Systems · 19.05.2023 · 7 (2) · 1-60
DOI: 10.1145/3589973 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Measurement and Analysis of Computing Systems, online erschienen am 22.05.2023. Verfasst von Tyler Sam und 2 weiteren Autor:innen. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 56 Literaturangaben. Gefördert von: NSF.
Abstract (Originalsprache)
The practicality of reinforcement learning algorithms has been limited due to poor scaling with respect to the problem size, as the sample complexity of learning an ε-optimal policy is Ω(|S||A|H/ ε2) over worst case instances of an MDP with state space S, action space A, and horizon H. We consider a class of MDPs for which the associated optimal Q* function is low rank, where the latent features are unknown. While one would hope to achieve linear sample complexity in |S| and |A| due to the low rank structure, we show that without imposing further assumptions beyond low rank of Q*, if one is constrained to estimate the Q function using only observations from a subset of entries, there is a worst case instance in which one must incur a sample complexity exponential in the horizon H to learn a near optimal policy. We subsequently show that under stronger low rank structural assumptions, given access to a generative model, Low Rank Monte Carlo Policy Iteration (LR-MCPI) and Low Rank Empirical Value Iteration (LR-EVI) achieve the desired sample complexity of Õ((|S|+|A|)poly (d,H)/ε2) for a rank d setting, which is minimax optimal with respect to the scaling of |S|, |A|, and ε. In contrast to literature on linear and low-rank MDPs, we do not require a known feature mapping, our algorithm is computationally simple, and our results hold for long time horizons. Our results provide insights on the minimal low-rank structural assumptions required on the MDP with respect to the transition kernel versus the optimal action-value function.
Förderung
- NSF
Zitieren
APA
Sam, T., Chen, Y., & Yu, C. L. (2023). Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structure. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 7(2), 1-60. https://doi.org/10.1145/3589973
Vancouver
Sam T, Chen Y, Yu CL. Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structure. Proceedings of the ACM on Measurement and Analysis of Computing Systems. 2023;7(2):1-60. doi:10.1145/3589973
BibTeX
@article{Sam2023,
author = {Sam, Tyler and Chen, Yudong and Yu, Christina Lee},
title = {Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structure},
journal = {Proceedings of the ACM on Measurement and Analysis of Computing Systems},
year = {2023},
volume = {7},
number = {2},
pages = {1--60},
doi = {10.1145/3589973}
}
EUVIMED