論文の概要: Two-Player Zero-Sum Games with Bandit Feedback

• arxiv url: http://arxiv.org/abs/2506.14518v1
• Date: Tue, 17 Jun 2025 13:46:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-18 17:34:59.491633
• Title: Two-Player Zero-Sum Games with Bandit Feedback
• Title（参考訳）: バンドフィードバックによるツープレイヤーゼロサムゲーム
• Authors: Elif Yılmaz, Christos Dimitrakakis,
• Abstract要約: 本研究では,列プレーヤが敵列プレーヤに対する報酬を最大化することを目的とした2プレイヤーゼロサムゲーム (TPZSG) について検討する。 本稿では,ETC-TPZSGとETC-TPZSG-AEの2つのアルゴリズムを提案する。 この結果から,ETCに基づくアルゴリズムは,対戦ゲーム設定において効果的に動作することがわかった。
• 参考スコア（独自算出の注目度）: 2.5015086558362247
• License: http://creativecommons.org/licenses/by/4.0/
• 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$ rounds, we achieve an instance-dependent regret upper bounds of $O(\Delta + \sqrt{T})$ for ETC-TPZSG and $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.
• Abstract（参考訳）: 本稿では,列プレーヤが敵列プレーヤに対するペイオフを最大化することを目的とした2プレイヤーゼロサムゲーム(TPZSG)について,帯域幅フィードバックによって推定される未知のペイオフ行列を用いて検討する。 本稿では,ETC-TPZSGとETC-TPZSG-AEの2つのアルゴリズムを提案する。 本研究の目的は,純粋な戦略であるNash Equilibriumを学習することに集中して,TPZSG設定におけるETCの適用性を実証することである。 我々の研究の重要な貢献は、両方のアルゴリズムが期待する後悔に対するインスタンス依存上界の導出であり、ゼロサムゲームに関する文献では限定的な注目を集めている。 特に、$T$のラウンドの後、ETC-TPZSGに対して$O(\Delta + \sqrt{T})$と、ECC-TPZSG-AEに対して$O(\frac{\log (T \Delta^2)}{\Delta})$のインスタンス依存後悔上限を達成する。 そこで本研究では,ETCをベースとしたアルゴリズムが,既存の手法に匹敵する残差を達成しつつ,インスタンス依存分析による洞察を提供しながら,対戦ゲーム設定において効果的に動作することを示す。

関連論文リスト

• Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback [60.610120215789976]
  純粋な戦略 ナッシュ均衡が存在するとき、$c$ は 0 となり、最適のインスタンス依存後悔境界となることを示す。 また,本アルゴリズムは最終段階の収束性も享受し,ほぼ最適サンプルを用いて純粋な戦略ナッシュ均衡を同定することができる。
  論文  参考訳（メタデータ） (2025-02-24T20:20:06Z)
• Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
  オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。 本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
  論文  参考訳（メタデータ） (2023-10-21T18:38:13Z)
• Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions [145.54544979467872]
  本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。 我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。 提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
  論文  参考訳（メタデータ） (2022-07-25T18:29:16Z)
• Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Bounds [31.5504566292927]
  我々は, 後悔を最小限に抑えるために, 中央サーバを介して協調できる$M$エージェントを含む線形帯域幅問題を考える。 これらのエージェントのわずか$alpha$は敵対的であり、任意に作用し、次の緊張に繋がる。 我々は、厳密な信頼区間を慎重に構築し、探索と探索のトレードオフをバランスさせる新しいアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2022-06-06T18:16:34Z)
• Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback [29.553652241608997]
  本研究では,テキストモオと強いモノトーンゲームの研究を行い,その学習方法について検討した。 我々はまず,新しい帯域学習アルゴリズムを構築し,$tildeTheta(nsqrtT)$の単一エージェント最適後悔を実現することを示す。 そこで我々は,このオープンな問題を解決し,広範にわたるバンディットゲーム理論学習に寄与した。
  論文  参考訳（メタデータ） (2021-12-06T08:27:54Z)
• Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games [104.74734408204749]
  マルチプレイヤーの汎用正規形式ゲームにおいて,OMWU(Optimistic Multiplicative Weights Update)を用いているエージェントが全員,O(textrmpolylog(T))$(T$)$(T$)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$)であることを示す。 外部の後悔から内部の後悔へと結果を拡張し、後悔を交換することで、近似した平衡に収束する非結合学習ダイナミクスを確立する。
  論文  参考訳（メタデータ） (2021-11-11T01:19:53Z)

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

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