Provably Sample Efficient Reinforcement Learning in Competitive Linear Quadratic Systems

Jingwei Zhang, Zhuoran Yang, Zhengyuan Zhou, Zhaoran Wang

Research output: Contribution to journalConference articlepeer-review

2 Scopus citations


We study the infinite-horizon zero-sum linear quadratic (LQ) games, where the state transition is linear and the cost function is quadratic in states and actions of two players. In particular, we develop an adaptive algorithm that can properly trade off between exploration and exploitation of the unknown environment in LQ games based on the optimism-in-face-of-uncertainty (OFU) principle. We show that (i) the average regret of player 1 (the min player) can be bounded by Õ(1/√T) against any fixed linear policy of the adversary (player 2); (ii) the average cost of player 1 also converges to the value of the game at a sublinear Õ(1/√T) rate if the adversary plays adaptively against player 1 with the same algorithm, i.e., with self-play. To the best of our knowledge, this is the first time that a probably sample efficient reinforcement learning algorithm is proposed for zero-sum LQ games.

Original languageEnglish (US)
Pages (from-to)597-598
Number of pages2
JournalProceedings of Machine Learning Research
StatePublished - 2021
Event3rd Annual Conference on Learning for Dynamics and Control, L4DC 2021 - Virtual, Online, Switzerland
Duration: Jun 7 2021Jun 8 2021


  • Exploration
  • Linear-Quadratic Game
  • Optimal Control
  • Reinforcement Learning

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability


Dive into the research topics of 'Provably Sample Efficient Reinforcement Learning in Competitive Linear Quadratic Systems'. Together they form a unique fingerprint.

Cite this