Sample-optimal parametric Q-learning using linearly additive features

Lin F. Yang, Mengdi Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Consider a Markov decision process (MDP) that admits a set of state-action features, which can linearly express the process's probabilistic transition model. We propose a parametric Q-learning algorithm that finds an approximate-optimal policy using a sample size proportional to the feature dimension K and invariant with respect to the size of the state space. To further improve its sample efficiency, we exploit the monotonicity property and intrinsic noise structure of the Bellman operator, provided the existence of anchor state-actions that imply implicit non-negativity in the feature space. We augment the algorithm using techniques of variance reduction, monotonicity preservation, and confidence bounds. It is proved to find a policy which is e-optimal from any initial state with high probability using Õ(K/ 2 (1 - γ) 3 ) sample transitions for arbitrarily large-scale MDP with a discount factor γ (0,1). A matching information-theoretical lower bound is proved, confirming the sample optimality of the proposed method with respect to all parameters (up to poly-log factors).

Original languageEnglish (US)
Title of host publication36th International Conference on Machine Learning, ICML 2019
PublisherInternational Machine Learning Society (IMLS)
Pages12095-12114
Number of pages20
ISBN (Electronic)9781510886988
StatePublished - Jan 1 2019
Event36th International Conference on Machine Learning, ICML 2019 - Long Beach, United States
Duration: Jun 9 2019Jun 15 2019

Publication series

Name36th International Conference on Machine Learning, ICML 2019
Volume2019-June

Conference

Conference36th International Conference on Machine Learning, ICML 2019
CountryUnited States
CityLong Beach
Period6/9/196/15/19

All Science Journal Classification (ASJC) codes

  • Education
  • Computer Science Applications
  • Human-Computer Interaction

Fingerprint Dive into the research topics of 'Sample-optimal parametric Q-learning using linearly additive features'. Together they form a unique fingerprint.

  • Cite this

    Yang, L. F., & Wang, M. (2019). Sample-optimal parametric Q-learning using linearly additive features. In 36th International Conference on Machine Learning, ICML 2019 (pp. 12095-12114). (36th International Conference on Machine Learning, ICML 2019; Vol. 2019-June). International Machine Learning Society (IMLS).