Two-Player Zero-Sum Games with Bandit Feedback

We study a two-player zero-sum game in which the row player aims to maximize their payoff against a competing column player, under an unknown payoff matrix estimated through bandit feedback. We propose three algorithms based on the Explore-Then-Commit (ETC) and action pair elimination frameworks. The first adapts it to zero-sum games, the second incorporates adaptive elimination that leverages the varepsilon-Nash Equilibrium property to efficiently select the optimal action pair, and the third extends the elimination algorithm by employing non-uniform exploration. Our objective is to demonstrate the applicability of ETC and action pair elimination algorithms in a zero-sum game setting by focusing on learning pure strategy Nash Equilibria. A key contribution of our work is a derivation of instance-dependent upper bounds on the expected regret of our proposed algorithms, which has received limited attention in the literature on zero-sum games. Particularly, after T rounds, we achieve an instance-dependent regret upper bounds of O(Delta + √T) for ETC in zero-sum game setting and Oleft(fraclog (T Delta2)Deltaright) for the adaptive elimination algorithm and its variant with non-uniform exploration, where Delta denotes the suboptimality gap. Therefore, our results indicate that the ETC and action pair elimination algorithms perform effectively in zero-sum game settings, achieving regret bounds comparable to existing methods while providing insight through instance-dependent analysis.