Provably Efficient Reinforcement Learning with Linear Function Approximation

Chi Jin, Zhuoran Yang, Zhaoran Wang, Michael I. Jordan

Research output: Contribution to journalArticlepeer-review


Modern reinforcement learning (RL) is commonly applied to practical problems with an enormous number of states, where function approximation must be deployed to approximate either the value function or the policy. The introduction of function approximation raises a fundamental set of challenges involving computational and statistical efficiency, especially given the need to manage the exploration/exploitation trade-off. As a result, a core RL question remains open: how can we design provably efficient RL algorithms that incorporate function approximation? This question persists even in a basic settingwith linear dynamics and linear rewards, forwhich only linear function approximation is needed. This paper presents the first provable RL algorithm with both polynomial run time and polynomial sample complexity in this linear setting, without requiring a "simulator"or additional assumptions. Concretely, we prove that an optimistic modification of least-squares value iteration-a classical algorithm frequently studied in the linear setting-achieves O (√ d3H3T ) regret, where d is the ambient dimension of feature space, H is the length of each episode, and T is the total number of steps. Importantly, such regret is independent of the number of states and actions.

Original languageEnglish (US)
Pages (from-to)1496-1521
Number of pages26
JournalMathematics of Operations Research
Issue number3
StatePublished - Aug 2023

All Science Journal Classification (ASJC) codes

  • General Mathematics
  • Computer Science Applications
  • Management Science and Operations Research


  • episodic MDP
  • exploration
  • linear function approximation
  • reinforcement learning


Dive into the research topics of 'Provably Efficient Reinforcement Learning with Linear Function Approximation'. Together they form a unique fingerprint.

Cite this