論文の概要: Fairness in two-player zero-sum games with bandit feedback

• arxiv url: http://arxiv.org/abs/2606.01159v1
• Date: Sun, 31 May 2026 11:06:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-02 21:34:29.288069
• Title: Fairness in two-player zero-sum games with bandit feedback
• Title（参考訳）: バンディットフィードバックを持つ2プレイヤーゼロサムゲームにおけるフェアネス
• Authors: S Akash, Pratik Gajane,
• Abstract要約: 両プレイヤーゼロサムゲーム (TPZSGs) について, 公正性制約下での帯域フィードバックによる検討を行った。 公正なミニマックス値、公正なナッシュ均衡、公正な後悔、そして公正さの価格が少なくとも1-1/m)$であることを示すクリーンな二重表現を導出する。 我々の主な成果は、Explore-Then-Commitアルゴリズムに対する$widetildeO(T2/3)$ regret bound for a Explore-Then-Commit algorithm, $textttFair-ETC-TPZSG$, for general mixed equilibriaである。
• 参考スコア（独自算出の注目度）: 1.0957528713294875
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.
• Abstract（参考訳）: フェアネス制約下では,少なくとも$α/m$の確率で全てのアクションをプレイする必要がある。 既存のインスタンス依存の結果は、$\textit{pure}$ Nash equilibriaをターゲットとし、fairnessは、より難しい学習ターゲットである$\textit{mixed}$ equilibriaを汎用的に生成する。 すべてのフェアストラテジーは、$p = (α/m)\mathbf{1} + (1-α)\widetilde{p}$ with $\widetilde{p} \in Δ_m$} と分解され、ペイオフ形式に置換すると、$p^{\top}Aq = \widetilde{p}^{\top}\widetilde{A} q$ for a fair payoff matrix $\widetilde{A} := (1-α)A + α\mathbf{1} c^{\top}$, $c_j = \tfrac{1}{m}\sum_iA(i,j)$ がカラム列列列ベクトルとなる。 A$ 上のフェアゲームは、$\widetilde{A}$ 上の標準ゼロサムゲームと等価であるため、平衡存在、KKT構造、LP基底安定性は、$\widetilde{A}$ に適用される古典的な結果に還元される。 公正なミニマックス値、公正なナッシュ均衡、公正な後悔、そして公正さの価格が少なくとも$α(1-1/m)$であることを示すクリーンな二重表現を導出し、制約のない平衡が既に完全に支持されているときに消滅する。 我々の主な成果は、探索-Then-Commitアルゴリズムに対して$\widetilde{O}(T^{2/3})$ regret bound for a Explore-Then-Commit algorithm, $\texttt{Fair-ETC-TPZSG}$、一般混合平衡に適用できる。 等しく、フェア均衡が単一の支配的作用を持つとき、$\widetilde{p}^{\star}$が$Δ_m$の頂点であるとき、バウンドはインスタンス依存の$\widetilde{O}(1/\widetildeΔ(α)^{2})$、$\widetildeΔ(α)$はLPマージンギャップとなる。

関連論文リスト

• Tighter Regret Bounds for Contextual Action-Set Reinforcement Learning [17.131069269126776]
  固定報酬と遷移関数を用いて,エピソード依存の許容アクションセットを用いて,エピソード強化学習について検討した。 エピソードごとの最適値に対して累積後悔(sum_k=1K[V*,Mk - Vk,Mk]$)で評価する。 MVPアルゴリズムが自然にこのフレームワークに拡張され、強力な理論的保証を享受していることを示す。
  論文  参考訳（メタデータ） (2026-05-15T07:28:42Z)
• Offline Two-Player Zero-Sum Markov Games with KL Regularization [23.339668121961463]
  オフライン2プレイヤーゼロサムマルコフゲームにおけるナッシュ均衡の学習問題について検討する。 我々はまず,高速な$widetildemathcalO(1/n)$収束率を実現する理論フレームワークであるRegularized Offline Sequential Equilibrium (ROSE)を紹介した。 次に,最小二乗値推定と反復的自己再生更新に基づく実用的モデルフリーアルゴリズムであるSequential Offline Self-play Mirror Descent (SOS-MD)を提案する。
  論文  参考訳（メタデータ） (2026-05-13T05:29:21Z)
• Variance-Dependent Regret Lower Bounds for Contextual Bandits [65.93854043353328]
  これは従来の$tildeO(dsqrtK)$ regret bound to $tildeO(dsqrtsum_k=1Ksigma_k2)$で改善されている。
  論文  参考訳（メタデータ） (2025-03-15T07:09:36Z)
• Corrupted Learning Dynamics in Games [62.73758165845971]
  すべてのプレイヤーが楽観的な追従型リーダー(OFTRL)に従うと、平衡は$O(log T)$の速さで計算できる。 本稿では,各プレイヤーが所定のアルゴリズムによって提案される戦略から逸脱する程度に依存する速度で,適応的に平衡を求める学習ダイナミクスを提案する。
  論文  参考訳（メタデータ） (2024-12-10T02:23:44Z)
• Low-rank Matrix Bandits with Heavy-tailed Rewards [55.03293214439741]
  アンダーライン重み付きアンダーラインリワード(LowHTR)を用いたアンダーラインローランク行列バンディットの問題点について検討する。 観測されたペイオフに対するトランケーションと動的探索を利用して,LOTUSと呼ばれる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-26T21:54:31Z)
• Context-lumpable stochastic bandits [49.024050919419366]
  我々は、$S$コンテキストと$K$アクションによる文脈的盗賊問題を考える。 我々は,最大$widetilde O(r (S +K )/epsilon2)$サンプルを用いて,$epsilon$-optimal Policyを出力するアルゴリズムを提案する。 後悔の設定では、T$までの累積後悔を$widetilde O(sqrtr3(S+K)T)$で束縛するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2023-06-22T17:20:30Z)
• Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a Generative Model [50.38446482252857]
  2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。 我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。 我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
  論文  参考訳（メタデータ） (2022-08-22T17:24:55Z)
• Model-Based Reinforcement Learning for Offline Zero-Sum Markov Games [18.832436856339587]
  本稿では,オフラインデータから2プレイヤーゼロサムマルコフゲームにおけるナッシュ均衡の学習に向けて前進する。 ベルンシュタイン型低信頼境界を持つ悲観的モデルベースアルゴリズム(VI-LCB-Game)を提案する。
  論文  参考訳（メタデータ） (2022-06-08T17:58:06Z)
• Gradient Descent-Ascent Provably Converges to Strict Local Minmax Equilibria with a Finite Timescale Separation [11.091975655053547]
  有限時間スケールの分離パラメータ $tau$ は、非プレイヤ、非コンケーブゼロサムゲームにおいて勾配降下度に比例することを示す。 タイムスケールコンピューティングがパフォーマンスに与える影響を実証的に示す。
  論文  参考訳（メタデータ） (2020-09-30T17:51:28Z)
• Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
  我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。 本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-22T05:00:13Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。