# Fairness in two-player zero-sum games with bandit feedback

arXiv: https://arxiv.org/abs/2606.01159 · HTML: https://mlsanity.com/paper/2606.01159/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 20 references that are in the map.
- First posted on arXiv 31 May 2026.

## Builds on (most cited first, 10 of 10)

- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Fairness in Reinforcement Learning](https://mlsanity.com/paper/1611.03071/) (2016)
- [Achieving Fairness in the Stochastic Multi-armed Bandit Problem](https://mlsanity.com/paper/1907.10516/) (2019)
- [Learning Fair Policies in Multiobjective (Deep) Reinforcement Learning with Average and Discounted Rewards](https://mlsanity.com/paper/2008.07773/) (2020)
- [Calibrated Fairness in Bandits](https://mlsanity.com/paper/1707.01875/) (2017)
- [Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2502.17625/) (2025)
- [Instance-dependent Sample Complexity Bounds for Zero-sum Matrix Games](https://mlsanity.com/paper/2303.10565/) (2023)
- [Two-Player Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2506.14518/) (2025)

## Abstract (arXiv)

We study two-player zero-sum games (TPZSGs) with bandit feedback under fairness constraints requiring every action to be played with probability at least α/m. Existing instance-dependent results target textitpure Nash equilibria, while fairness generically produces textitmixed equilibria, a harder learning target. Our key technical tool is a reparametrization: every fair strategy decomposes as p = (α/m)1 + (1-α)widetildep with widetildep ∈ Deltam, and substituting into the payoff form yields ptopAq = widetildeptopwidetildeA q for a fair payoff matrix widetildeA := (1-α)A + α1 ctop, where cj = tfrac1msumi A(i,j) is the column-mean vector. The fair game on A is then equivalent to a standard zero-sum game on widetildeA, so equilibrium existence, KKT structure, and LP basis stability reduce to classical results applied to widetildeA. We derive the fair minimax value, fair Nash equilibrium, fair regret, and a clean dual representation showing the price of fairness is at most α(1-1/m) and vanishes whenever the unconstrained equilibrium already has full support. Our main result is an widetildeO(T2/3) regret bound for an Explore-Then-Commit algorithm, textttFair-ETC-TPZSG, applicable to general mixed fair equilibria, together with a discussion of why naive action elimination does not readily improve it. When the fair equilibrium has a single dominant action, equivalently when widetildepstar is a vertex of Deltam, the bound sharpens to instance-dependent widetildeO(1/widetildeDelta(α)2), where widetildeDelta(α) is the LP-margin gap.