Timezone: »

 
Poster
Learning in two-player zero-sum partially observable Markov games with perfect recall
Tadashi Kozuno · Pierre Ménard · Remi Munos · Michal Valko

Thu Dec 09 08:30 AM -- 10:00 AM (PST) @
in Poster Session 6 »
We study the problem of learning a Nash equilibrium (NE) in an extensive game with imperfect information (EGII) through self-play. Precisely, we focus on two-player, zero-sum, episodic, tabular EGII under the \textit{perfect-recall} assumption where the only feedback is realizations of the game (bandit feedback). In particular the \textit{dynamics of the EGII is not known}---we can only access it by sampling or interacting with a game simulator. For this learning setting, we provide the Implicit Exploration Online Mirror Descent (IXOMD) algorithm. It is a model-free algorithm with a high-probability bound on convergence rate to the NE of order $1/\sqrt{T}$ where~$T$ is the number of played games. Moreover IXOMD is computationally efficient as it needs to perform the updates only along the sampled trajectory.
Keywords: Reinforcement Learning and Planning · Bandits · Online Learning

Author Information

Tadashi Kozuno (University of Alberta)

Tadashi Kozuno is a postdoc at the University of Alberta. He obtained bachelor and master degrees on neuroscience from Osaka university, and a PhD degree from Okinawa Inst. of Sci. and Tech. His main interest lies in efficient decision making from both theoretical and biological sides.

Pierre Ménard (Magdeburg University)
Remi Munos (DeepMind)
Michal Valko (DeepMind Paris / Inria / ENS Paris-Saclay)
Michal Valko

Michal is a machine learning scientist in DeepMind Paris, tenured researcher at Inria, and the lecturer of the master course Graphs in Machine Learning at l'ENS Paris-Saclay. Michal is primarily interested in designing algorithms that would require as little human supervision as possible. This means 1) reducing the “intelligence” that humans need to input into the system and 2) minimizing the data that humans need to spend inspecting, classifying, or “tuning” the algorithms. That is why he is working on methods and settings that are able to deal with minimal feedback, such as deep reinforcement learning, bandit algorithms, or self-supervised learning. Michal is actively working on represenation learning and building worlds models. He is also working on deep (reinforcement) learning algorithm that have some theoretical underpinning. He has also worked on sequential algorithms with structured decisions where exploiting the structure leads to provably faster learning. He received his Ph.D. in 2011 from the University of Pittsburgh under the supervision of Miloš Hauskrecht and after was a postdoc of Rémi Munos before taking a permanent position at Inria in 2012.

More from the Same Authors