Provable self-play algorithms for competitive reinforcement learning

Yu Bai, Chi Jin

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

2 Scopus citations

Abstract

Self-play, where the algorithm learns by playing against itself without requiring any direct supervision, has become the new weapon in modern Reinforcement Learning (RL) for achieving superhuman performance in practice. However, the majority of exisiting theory in reinforcement learning only applies to the setting where the agent plays against a fixed environment; it remains largely open whether self-play algorithms can be provably effective, especially when it is necessary to manage the exploration/exploitation tradeoff. We study self-play in competitive reinforcement learning under the setting of Markov games, a generalization of Markov decision processes to the twoplayer case. We introduce a self-play algorithm-Value Iteration with Upper/Lower Confidence Bound (VI-ULCB)-And show that it achieves regret O( p T) after playing T steps of the game, where the regret is measured by the agent s performance against a fully adversarial opponent who can exploit the agent s strategy at any step. We also introduce an explore-Then-exploit style algorithm, which achieves a slightly worse regret of O(T2=3), but is guaranteed to run in polynomial time even in the worst case. To the best of our knowledge, our work presents the first line of provably sample-efficient self-play algorithms for competitive reinforcement learning.

Original languageEnglish (US)
Title of host publication37th International Conference on Machine Learning, ICML 2020
EditorsHal Daume, Aarti Singh
PublisherInternational Machine Learning Society (IMLS)
Pages528-537
Number of pages10
ISBN (Electronic)9781713821120
StatePublished - 2020
Event37th International Conference on Machine Learning, ICML 2020 - Virtual, Online
Duration: Jul 13 2020Jul 18 2020

Publication series

Name37th International Conference on Machine Learning, ICML 2020
VolumePartF168147-1

Conference

Conference37th International Conference on Machine Learning, ICML 2020
CityVirtual, Online
Period7/13/207/18/20

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Human-Computer Interaction
  • Software

Fingerprint

Dive into the research topics of 'Provable self-play algorithms for competitive reinforcement learning'. Together they form a unique fingerprint.

Cite this