EUVIMEDEUVIMED entdecken
Crossref

Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structure

Tyler Sam, Yudong Chen, Christina Lee Yu

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →