Sharing Information in Adversarial Bandit

David L. Saint-Pierre (1, 2) , Olivier Teytaud (2, 1)

1 LRI - Laboratoire de Recherche en Informatique
2 TAO - Machine Learning and Optimisation

2-Player games in general provide a popular platform for research in Artificial Intelligence (AI). One of the main challenges coming from this plat-form is approximating a Nash Equilibrium (NE) over zero-sum matrix games. While the problem of computing such a Nash Equilibrium is solvable in polyno-mial time using Linear Programming (LP), it rapidly becomes infeasible to solve as the size of the matrix grows; a situation commonly encountered in games. This paper focuses on improving the approximation of a NE for matrix games such that it outperforms the state-of-the-art algorithms given a finite (and rather small) number T of oracle requests to rewards. To reach this objective, we pro-pose to share information between the different relevant pure strategies. We show both theoretically by improving the bound and empirically by experiments on ar-tificial matrices and on a real-world game that information sharing leads to an improvement of the approximation of the NE.

Mots clés: Bandit Problem; Games; Monte-Carlo; Nash Equilibrium

Domaines: Optimisation et contrôle [math.OC]

David L. Saint-Pierre, Olivier Teytaud. Sharing Information in Adversarial Bandit. EvoGames 2014, Apr 2014, Granada, Spain. ⟨10.1007/978-3-662-45523-4_32⟩. ⟨hal-01116716⟩