Two-Player Zero-Sum Games with Bandit Feedback

Elif Yılmaz, Christos Dimitrakakis · 2025

Read Two-Player Zero-Sum Games with Bandit Feedback by Elif Yılmaz, Christos Dimitrakakis (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-14518.txt.

Introduction

Elif Yılmaz and Christos Dimitrakakis study a duel where neither player can see the score table. In their two-player zero-sum game, payoffs stay hidden and are learned only through bandit feedback, the result of moves actually played. Both sides adapt, so each learner chases a moving target.

They adapt explore-then-commit and action pair elimination ideas to this setting, in three variants of rising cleverness. One uses the near-equilibrium structure to prune pairs faster; another explores unevenly on purpose. Their main prize is instance-dependent regret bounds, guarantees that tighten on easy games. Pure strategy equilibria are the quarry, and the bounds show when bandit duels can find them cheaply.

Catalog record

CREATORElif Yılmaz, Christos Dimitrakakis
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE64 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-14518

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Two-Player Zero-Sum Games with Bandit Feedback Elif Yılmaz, Christos Dimitrakakis Abstract We study a two-player zero-sum game (TPZSG) in which the row player aims to maximize their payoff against an adversarial column player, under an unknown payoff matrix estimated through bandit feedback. We propose and analyze two algorithms: ETC-TPZSG, which directly applies ETC to the TPZSG setting and ETC-TPZSG-AE, which improves upon it by incorporating an action pair elimination (AE) strategy that leverages the ε \varepsilon -Nash Equilibrium property to efficiently select the optimal action pair. Our objective is to demonstrate the applicability of ETC in a TPZSG setting by focusing on learning pure strategy Nash Equilibrium. A key contribution of our work is a derivation of instance-dependent upper bounds on the expected regret for both algorithms, has received limited attention in the literature on zero-sum games. Particularly, after T T rounds, we achieve an instance-dependent regret upper bounds of O ⁡ ( Δ + T ) O(\Delta+\sqrt{T}) for ETC-TPZSG and O ⁡ ( log ⁡ ( T ​ Δ 2 ) Δ ) O(\frac{\log(T\Delta^{2})}{\Delta}) for ETC-TPZSG-AE, where Δ \Delta denotes the suboptimality gap. Therefore, our results indicate that ETC-based algorithms perform effectively in adversarial game settings, achieving regret bounds comparable to existing methods while providing insights through instance-dependent analysis. 1 Introduction This paper focuses on finite two-player zero-sum games (TPZSGs), where two players interact in an adversarial setting with strictly opposing objectives, as first analyzed in v1928theorie ; vonneumanandmorgenstern . These games play a foundational role in game theory and online learning, capturing adversarial interactions in various applications such as economic competition and adversarial machine learning. In such settings, players repeatedly select actions from finite sets, with payoffs determined by a fixed but unknown game matrix. Studies on learning in games typically use either full information feedback where players observe the opponent’s actions or the entire payoff matrix after each round or partial feedback , also called bandit feedback, where each player observes only their own payoffs without access to the opponent’s strategy or the full matrix blum2007external . In this paper, we focus specifically on a TPZSG setting with bandit feedback and propose two algorithms, ETC-TPZSG and ETC-TPZSG-AE, designed to minimize regret by learning pure strategies for both players through balancing of exploration and exploitation. Several existing studies have advanced our understanding of how players learn to play optimally in zero-sum games with bandit feedback. The variant of UCB algorithm for adversarial games under bandit feedback have been analyzed using worst-case regret bounds in o2021matrix . In particular, worst-case analyses lead to all games as equally hard by ignoring the specific structure of the game. Instance-dependent analysis adapts the regret guarantees to the specific properties of a game to provide more practical performance guarantees. More recently, instance-dependent regret bounds have been investigated for the Tsallis-INF algorithm in TPZSGs ito2025instance . However an understanding of instance-dependent regret in TPZSGs under bandit feedback remains incomplete. Contributions. This paper investigates the effectiveness of the Explore-Then-Commit (ETC) algorithm and extensions in the context of TPZSGs. While ETC has been widely studied in standard multi-armed bandit (MAB) problems, there has been no prior work specifically analyzing its performance to adversarial game settings, which makes this the first work to provide its detailed analysis in such a setting. A key motivation for studying ETC is its algorithmic simplicity allowing for a clear structure. In particular, we propose two algorithms that adapt the ETC approach to TPZSG setting and present their instance-dependent regret analyses. The first one, ETC-TPZSG, follows the classical ETC framework by uniformly selecting actions for a fixed number of steps and then committing to a pure strategy, achieves an upper bound of \tilde{O}(\Delta+\sqrt{T}) . The second algorithm, ETC-TPZSG-AE, incorporates an adaptive elimination approach, similar to auer2010ucb , by sequentially eliminating actions which, with high probability, are not part of an \varepsilon -Nash Equilibrium ( \varepsilon -NE), gives us an upper regret bound of O(\frac{\log(T\Delta^{2})}{\Delta}) . Intuitively, this design is expected to converge more rapidly to the optimal strategy by efficiently reducing uncertainty and narrowing the action spaces of the players. Consequently, despite the simplicity of ETC framework, our results demonstrate that ETC-based approaches can be highly effective in adversarial settings. In both cases, the regret bounds depend on a suitable \Delta notion, which varies depending on the type of the regret we are analyzing. Paper structure. This paper is organized as follows. Section 2 reviews related work. Section 3 introduces preliminaries and formalizes the two-player zero-sum game (TPZSG) setting. In Section 4 , we present the ETC in a TPZSG setting, ETC-TPZSG, and analyze its regret. Section 5 introduces an elimination based algorithm, ETC-TPZSG-AE, that leverages the \varepsilon -NE property, and provides its regret analysis. Section 6 offers empirical results validating their theoretical performances. Finally, Section 7 discusses our conclusions and future research directions. 2 Related Work The multi-armed bandit (MAB) problem, has been introduced by thompson1933likelihood and originally described by robbins1952some , has been widely explored and has become a crucial framework for online decision-making under uncertainty, as explored in works such as audibert2009exploration ; auer2002finite ; auer1995gambling ; auer2010ucb ; blum2007learning ; bubeck2012regret . The MAB problem models scenarios in which a player must repeatedly choose from a set of actions to maximize their own rewards while balancing exploration-exploitation tradeoff, has formalized by lai1985asymptotically and further explored in studies such as audibert2007tuning ; maes2012learning . A central challenge is identifying the action with the highest expected reward while minimizing suboptimal choices, requiring efficient exploration and statistical confidence. Several approaches guarantee low error probabilities within finite trials, aiming to minimize regret audibert2010best ; gabillon2012best . Since the player has no prior knowledge of expected rewards, a dedicated exploration phase is essential, has motivated numerous studies such as bubeck2009pure ; neu2015explore . The Explore-Then-Commit (ETC) algorithm, which has been introduced by perchet2016batched , is one of the fundamental approaches in the MAB setting. It explores each action a fixed number of times, then commits to the best-performing action for the remaining rounds. Due to its simplicity and effectiveness, variants of the ETC algorithm are widely used in various decision-making scenarios garivier2016explore ; yekkehkhany2019etc . Zero-sum games, are a fundamental concept in game theory. They describe competitive scenarios where one player’s gain exactly equals the other’s loss. First highlighted by v1928theorie ; vonneumanandmorgenstern , their theory and applications have been extensively explored blum2007learning ; cesa2006prediction ; washburn2014two . The Minimax Theorem in v1928theorie ; vonneumanandmorgenstern guarantees equilibrium existence in TPZSGs, but finding equilibria becomes significantly harder when the payoff matrix is unknown daskalakis2011near ; daskalakis2009complexity ; mazumdar2019finding ; zinkevich2007new . A more general concept are Nash Equilibria nash1950equilibrium ; nash1951non . While these are identical to the minimax equilibria in TZPSGs, they are not as easy to compute in general games daskalakis2009complexity . The concept of \varepsilon -Nash Equilibrium provides an approximate solution where each player’s strategy is within an \varepsilon tolerance level. daskalakis2009note used the \varepsilon -NE concept to efficiently approximate equilibrium in two-player games. In a zero-sum game setting with bandit feedback, players engage in repeated interactions without full knowledge of the payoff matrix, making it essential to estimate the unknown payoffs by previous observations. Various approaches, such as UCB o2021matrix

Read the complete text