在公平约束下研究双人零和博弈的在线学习，给出带探索的算法与理论保证。
Fairness in two-player zero-sum games with bandit feedback
- 通过重新参数化将公平策略分解为基线+扰动，转化为标准零和博弈。
- 提出公平后悔上界为 $\widetilde{O}(T^{2/3})$，特定情况下可优化至 $\widetilde{O}(1/\widetilde{Δ}(α)^2)$。
- 揭示公平代价最大为 $α(1-1/m)$，当原解已全支持时公平无额外代价。
我们研究在带宽反馈下的双人零和博弈（TPZSGs）中的公平性约束问题，要求每项行动被选择的概率至少为 $α/m$。现有依赖实例的结果仅针对纯纳什均衡，而公平性通常导致混合均衡，学习难度更高。本文的关键技术是重参数化：每个公平策略可表示为 $p = (α/m)\mathbf{1} + (1-α)\widetilde{p}$，其中 $\widetilde{p} \in Δ_m$。代入收益函数后，原始收益 $p^\top A q$ 等价于新矩阵 $\widetilde{A} := (1-α)A + α\mathbf{1} c^\top$ 生成的标准零和博弈，$c_j = \frac{1}{m}\sum_i A(i,j)$ 为列均值向量。因此，公平博弈等价于标准零和博弈，均衡存在性、KKT结构及线性规划基稳定性均可沿用经典结果。我们推导出公平极小极大值、公平纳什均衡与公平后悔，并获得清晰的对偶表达式，表明公平代价不超过 $α(1-1/m)$，且在原无约束均衡已有全支持时消失。主结果为一个 $\widetilde{O}(T^{2/3})$ 的后悔上界，适用于一般混合公平均衡，对应算法为 $\texttt{Fair-ETC-TPZSG}$，并讨论了为何朴素的动作剔除无法显著改进该界。当公平均衡存在唯一主导动作（即 $\widetilde{p}^\star$ 为 $Δ_m$ 的顶点）时，该上界可细化为实例相关的 $\widetilde{O}(1/\widetilde{Δ}(α)^2)$，其中 $\widetilde{Δ}(α)$ 为线性规划的边际间隙。
原文摘要 · Abstract (English)
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 $\textit{pure}$ Nash equilibria, while fairness generically produces $\textit{mixed}$ equilibria, a harder learning target. Our key technical tool is a reparametrization: every fair strategy decomposes as $p = (α/m)\mathbf{1} + (1-α)\widetilde{p}$ with $\widetilde{p} \in Δ_m$, and substituting into the payoff form yields $p^{\top}Aq = \widetilde{p}^{\top}\widetilde{A} q$ for a fair payoff matrix $\widetilde{A} := (1-α)A + α\mathbf{1} c^{\top}$, where $c_j = \tfrac{1}{m}\sum_i A(i,j)$ is the column-mean vector. The fair game on $A$ is then equivalent to a standard zero-sum game on $\widetilde{A}$, so equilibrium existence, KKT structure, and LP basis stability reduce to classical results applied to $\widetilde{A}$. 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 $\widetilde{O}(T^{2/3})$ regret bound for an Explore-Then-Commit algorithm, $\texttt{Fair-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 $\widetilde{p}^{\star}$ is a vertex of $Δ_m$, the bound sharpens to instance-dependent $\widetilde{O}(1/\widetildeΔ(α)^{2})$, where $\widetildeΔ(α)$ is the LP-margin gap.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。