We are pleased to announce that a paper co-authored by Senior Researcher Tadashi Kozuno et al. has received the “Outstanding Paper Award” at the International Conference on Machine Learning 2023 (ICML 2023), one of the premier international conferences in the field of machine learning, held in Honolulu, Hawaii, from July 23. Among over 1,800 accepted papers, six were selected for this award, and one of them is our paper entitled “Adapting to game trees in zero-sum imperfect information games.”
・Please access herefor more details.
・Please access herefor the papers presented at ICML 2023.

This paper is the first paper to prove an information-theoretic lower bound for solving two-player zero-sum imperfect information games (IIGs) and present an algorithm whose performance guarantee given knowledge about the game structure matches the lower bound, establishing a milestone in the analysis of two-player zero-sum IIGs. In future work, we aim at developing an algorithm that requires no knowledge on games. The paper provides an idea for this research direction, which is also a reason for winning the award.

Award-winning Paper

 Adapting to game trees in zero-sum imperfect information games

Authors

Côme Fiegel^*1, Pierre Ménard^*2, Tadashi Kozuno^*3, Rémi Munos^*4, Vianney Perchet^{*1, 5},
Michal Valko<sup>*5

*1：CREST, ENSAE, IP Paris、*2：ENS Lyon、*3：OSX、*4：Google DeepMind、*5：CRITEO AI Lab</sup>

Comments from the Awardees

Côme Fiegel (CREST, ENSAE, IP Paris)
I am very honored to receive this award alongside my co-authors, acknowledging the efforts we dedicated to this work. I am hopeful that this recognition will encourage future research in this direction.

Tadashi Kozuno (Senior Researcher at OSX)
I have been working on this research since I was at the University of Alberta. During that period, we proposed an algorithm that was computationally efficient and sample-efficient although it does not have theoretically optimal sample efficiency. Based on our algorithm and analysis, other research group demonstrated that sample efficiency could be improved by using information about the game structure. This research showed that an algorithm with theoretically optimal sample efficiency can be achieved by using their techniques and recent insights from online learning. We also proposed a learning algorithm that solves IIGs while estimating information about the game structure and showed it nearly achieves theoretically optimal sample efficiency. In the future, we will work on developing practical algorithms that can be applied to even larger games and proposing algorithms with more useful theoretical guarantees.