論文の概要: Fast Last-Iterate Convergence in Zero-Sum Markov Games with Bandit Feedback

• arxiv url: http://arxiv.org/abs/2610.05968v1
• Date: Mon, 05 Oct 2026 08:20:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-10 02:48:18.220241
• Title: Fast Last-Iterate Convergence in Zero-Sum Markov Games with Bandit Feedback
• Title（参考訳）: 帯域フィードバックを持つゼロサムマルコフゲームにおける終局収束の高速化
• Abstract要約: 未知の2プレイヤーゼロサム割引マルコフゲームにおけるラストイテレート収束を帯域フィードバックで検討した。 適応正規化TD学習(ARTD)を開発し、現在のポリシーに縛られた$widetildemathcalO(t-1/4)$ duality gapを実現する。 我々は、ログバリアの正規化を価値推定の進捗に適応させ、学習を通してポリシーと価値のエラーを制御します。
• 参考スコア（独自算出の注目度）: 14.692647465985916
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study last-iterate convergence in unknown two-player zero-sum discounted Markov games with bandit feedback. The players learn independently along a single trajectory without observing each other's actions. We develop Adaptive Regularized TD Learning (ARTD), which achieves a $\widetilde{\mathcal{O}}(t^{-1/4})$ duality gap bound for the current policies under a uniform hitting time assumption, with high probability simultaneously over all rounds and starting states. This improves the $\widetilde{\mathcal{O}}(t^{-1/(9+ν)})$ rate of Cai et al. (2023), for any fixed $ν>0$, under the same feedback model and hitting time assumption. Our algorithm requires no knowledge of the hitting time bound, the time horizon, or the confidence level. To stabilize policy learning as value estimates change, we separate fast temporal difference averaging from bounded value updates. We adapt log-barrier regularization to the progress of value estimation, controlling both policy and value errors throughout learning. Together, these mechanisms enable fast convergence of the policies actually played, even when the players learn independently from bandit feedback.
• Abstract（参考訳）: 未知の2プレイヤーゼロサム割引マルコフゲームにおけるラストイテレート収束を帯域フィードバックで検討した。 プレイヤーは、互いの行動を観察することなく、一つの軌道に沿って独立して学習する。 我々は,全ラウンドと開始状態に対して同時に高い確率で,一様ヒットタイムの仮定の下で,現在のポリシーに対する$\widetilde{\mathcal{O}}(t^{-1/4})$双対性ギャップを達成できる適応正規化TD学習(ARTD)を開発した。 これにより$\widetilde{\mathcal{O}}(t^{-1/(9+ν)})$ rate of Cai et al (2023), for any fixed $ν>0$, under the same feedback model and hit time assumption。 我々のアルゴリズムは、打つ時間制限、時間水平線、信頼度に関する知識を必要としない。 評価値が変化するにつれて政策学習を安定化させるため,有界値更新から平均時間差を分離する。 我々は、ログバリアの正規化を価値推定の進捗に適応させ、学習を通してポリシーと価値のエラーを制御します。 これらのメカニズムは、プレイヤーがバンドのフィードバックから独立して学習しても、実際に実行されたポリシーの迅速な収束を可能にする。

関連論文リスト

• Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions [43.45624707071202]
  ゲームにおける学習力学の最後の項目収束は、近年大きな注目を集めている。 我々は, t(-1/2) の終点収束は, バンディットフィードバックを持つゲームにおいて高い確率で達成可能であることを示す。
  論文  参考訳（メタデータ） (2026-05-10T06:23:19Z)
• The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback [46.50566806285207]
  ゼロサム行列ゲームにおいて繰り返しプレイやバンディットフィードバックで学習する問題について検討する。 プレイヤー間の通信なしに、最終項目のナッシュ均衡への収束を保証するアンカップリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-04-17T14:17:09Z)
• Scale-Invariant Fast Convergence in Games [67.02769061793619]
  我々は,スケールフリーでもスケール不変でも,高速収束を実現する学習力学を開発した。 2プレーヤゼロサムゲームに対しては、$tildeO(A_mathrmdiff)$で有界な外部後悔を伴うスケールフリーかつスケール不変のダイナミクスが得られる。 マルチプレイヤーの汎用ゲームでは、過去の観測に基づいて観察された勾配をクリップする2倍のクリッピングと呼ばれる手法によって、スケールフリーの学習も可能となる。
  論文  参考訳（メタデータ） (2026-02-12T11:57:20Z)
• From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications [54.49053278073321]
  大規模なゲームでは、非結合学習ダイナミクスの平均的な繰り返しを新しい非結合学習ダイナミクスの最後の繰り返しに変換する単純なブラックボックス還元が存在することを示す。 我々の削減は、各プレイヤーの効用が自身の戦略と全ての対戦者の共同戦略の両方において線形であるゲームに適用される。
  論文  参考訳（メタデータ） (2025-06-04T00:24:14Z)
• Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback [60.610120215789976]
  純粋な戦略 ナッシュ均衡が存在するとき、$c$ は 0 となり、最適のインスタンス依存後悔境界となることを示す。 また,本アルゴリズムは最終段階の収束性も享受し,ほぼ最適サンプルを用いて純粋な戦略ナッシュ均衡を同定することができる。
  論文  参考訳（メタデータ） (2025-02-24T20:20:06Z)
• Corrupted Learning Dynamics in Games [62.73758165845971]
  すべてのプレイヤーが楽観的な追従型リーダー(OFTRL)に従うと、平衡は$O(log T)$の速さで計算できる。 本稿では,各プレイヤーが所定のアルゴリズムによって提案される戦略から逸脱する程度に依存する速度で,適応的に平衡を求める学習ダイナミクスを提案する。
  論文  参考訳（メタデータ） (2024-12-10T02:23:44Z)
• Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback [49.1061436241109]
  非漸近収束率の非結合、収束、合理的なアルゴリズムの開発に注力する。 我々のアルゴリズムは[Chen et al., 2021, Cen et al., 2021]と関係があり、エントロピー正規化技術に基づいている。
  論文  参考訳（メタデータ） (2023-03-05T18:08:54Z)

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

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