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

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.