論文の概要: Thompson Sampling for Learning in Zero-Sum Games

• arxiv url: http://arxiv.org/abs/2610.18899v1
• Date: Sun, 11 Oct 2026 12:16:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-15 21:06:15.724847
• Title: Thompson Sampling for Learning in Zero-Sum Games
• Title（参考訳）: ゼロサムゲームにおける学習のためのトンプソンサンプリング
• Abstract要約: トンプソンサンプリングは古典的な包帯において対数的かつ等しく最適な後悔を実現する。 本稿では,ガウス帯域フィードバックを用いた未知の有限2プレーヤゼロサム行列ゲームにおいてTSについて検討する。 ユニークなナッシュ均衡を持つ任意の固定零サムゲームに対して、期待される累積双対性ギャップが$O(sqrt T)$であることを示す。
• 参考スコア（独自算出の注目度）: 26.76477328335932
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Thompson sampling (TS) achieves logarithmic and asymptotically optimal regret in classical stochastic bandits, but its behavior in multi-agent learning remains less understood. We study TS in an unknown finite two-player zero-sum matrix game with Gaussian bandit feedback. Under centralized self-play, TS samples a single payoff matrix from the posterior and plays a Nash equilibrium of the sampled game. For every fixed zero-sum game with a unique Nash equilibrium, we show that the expected cumulative duality gap is $O(\sqrt T)$. The rate improves to $O(\log T)$ for pure equilibria. We then identify the exact coefficient of the $\sqrt T$ term, which depends only on the equilibrium strategies and the noise level. We also establish a minimax lower bound matching the square-root dependence on $T$ and an instance-dependent lower bound matching the logarithmic dependence on $T$ for a class of games with a unique pure equilibrium. Experiments support the predicted rates and coefficient.
• Abstract（参考訳）: トンプソンサンプリング(TS)は古典的確率的包帯において対数的および漸近的に最適な後悔を実現するが、マルチエージェント学習におけるその振る舞いはいまだに理解されていない。 本稿では,ガウス帯域フィードバックを用いた未知の有限2プレーヤゼロサム行列ゲームにおいてTSについて検討する。 中央集権的な自己プレイの下では、TSは後部から単一のペイオフ行列をサンプリングし、サンプリングされたゲームのナッシュ平衡を再生する。 ユニークなナッシュ均衡を持つ任意の固定零サムゲームに対して、期待される累積双対性ギャップが$O(\sqrt T)$であることを示す。 純平衡では$O(\log T)$に改善される。 次に、平衡戦略と雑音レベルにのみ依存する$\sqrt T$項の正確な係数を同定する。 また、$T$に対する平方根依存に一致するミニマックス下界と、一意の純粋平衡を持つゲームのクラスに対して$T$に対する対数依存に一致するインスタンス依存下界を確立する。 実験は予測される速度と係数を支持する。

関連論文リスト

• Beyond Pessimism: Offline Learning in KL-regularized Games [20.08179140215738]
  KL規則化された2プレイヤーゼロサムゲームにおけるオフライン学習について検討し、KL制約の下でポリシーを固定参照ポリシーに最適化する。 我々は、KL正規化ベストレスポンスの滑らかさと、スキュー対称性によって誘導されるナッシュ平衡の安定性に基づいて、KL正規化ゲームのための新しい悲観的フリーアルゴリズムと解析的フレームワークを開発する。
  論文  参考訳（メタデータ） (2026-04-08T07:00:54Z)
• Scale-Invariant Fast Convergence in Games [67.02769061793619]
  我々は,スケールフリーでもスケール不変でも,高速収束を実現する学習力学を開発した。 2プレーヤゼロサムゲームに対しては、$tildeO(A_mathrmdiff)$で有界な外部後悔を伴うスケールフリーかつスケール不変のダイナミクスが得られる。 マルチプレイヤーの汎用ゲームでは、過去の観測に基づいて観察された勾配をクリップする2倍のクリッピングと呼ばれる手法によって、スケールフリーの学習も可能となる。
  論文  参考訳（メタデータ） (2026-02-12T11:57:20Z)
• Learning Equilibria in Matching Games with Bandit Feedback [2.5015086558362247]
  一般化された二面マッチング市場における均衡学習の問題について検討する。 エージェントが選好を作成し、ゲームペイオフの楽観的な推定に基づいて選択する UCB アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-04T10:15:51Z)
• Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback [60.610120215789976]
  純粋な戦略 ナッシュ均衡が存在するとき、$c$ は 0 となり、最適のインスタンス依存後悔境界となることを示す。 また,本アルゴリズムは最終段階の収束性も享受し,ほぼ最適サンプルを用いて純粋な戦略ナッシュ均衡を同定することができる。
  論文  参考訳（メタデータ） (2025-02-24T20:20:06Z)
• Policy Mirror Ascent for Efficient and Independent Learning in Mean Field Games [35.86199604587823]
  平均場ゲームは対称および匿名の$N$-playerゲームに対して近似的なナッシュ均衡を得るための理論的ツールとして使われてきた。 ポリシーミラーを実行する$N$エージェントは、$widetildemathcalO(varepsilon-2)$サンプル内で正規化ゲームのナッシュ平衡に収束することを示す。
  論文  参考訳（メタデータ） (2022-12-29T20:25:18Z)
• 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)
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
  一般的なゲームでStackelberg平衡を効率的に学習する方法は、サンプルから非常にオープンなままです。 本稿では,2プレーヤターンベース汎用ゲームにおけるStackelberg平衡のサンプル効率学習に関する理論的研究を開始する。
  論文  参考訳（メタデータ） (2021-02-23T05:11:07Z)
• Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
  我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。 本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-22T05:00:13Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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