Near-Optimal Pure Exploration in Matrix Games: A Generalization of Stochastic Bandits & Dueling Bandits

2023/10/25 by Maiti, Arnab, Boczar, Ross, Jamieson, Kevin +1 · 1 citation
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2310.16252

Abstract

We study the sample complexity of identifying the pure strategy Nash equilibrium (PSNE) in a two-player zero-sum matrix game with noise. Formally, we are given a stochastic model where any learner can sample an entry (i,j) of the input matrix A∈[-1,1]^{n× m} and observe A_i,j+η where η is a zero-mean 1-sub-Gaussian noise. The aim of the learner is to identify the PSNE of A, whenever it exists, with high probability while taking as few samples as possible. Zhou et al. (2017) presents an instance-dependent sample complexity lower bound that depends only on the entries in the row and column in which the PSNE lies. We design a near-optimal algorithm whose sample complexity matches the lower bound, up to log factors. The problem of identifying the PSNE also generalizes the problem of pure exploration in stochastic multi-armed bandits and dueling bandits, and our result matches the optimal bounds, up to log factors, in both the settings.

Cited by

• Two-Player Zero-Sum Games with Bandit Feedback

Related

• Instance-dependent Sample Complexity Bounds for Zero-sum Matrix Games
• Minimax Sample Complexity for Turn-based Stochastic Game
• Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games
• On the Limitations and Possibilities of Nash Regret Minimization in Zero-Sum Matrix Games under Noisy Feedback
• Near-Optimal Reinforcement Learning with Self-Play