論文の概要: A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games

• arxiv url: http://arxiv.org/abs/2303.03100v1
• Date: Fri, 3 Mar 2023 05:01:41 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-07 16:04:37.902758
• Title: A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games
• Title（参考訳）: ゼロサム確率ゲームにおけるペイオフベース独立学習の有限サンプル解析
• Authors: Zaiwei Chen, Kaiqing Zhang, Eric Mazumdar, Asuman Ozdaglar, and Adam Wierman
• Abstract要約: 本研究では,2プレイヤーゼロサムゲームについて検討し,Douubly Smoothed Best-Response dynamicsと呼ばれる独立学習力学の形式を提案する。 結果として得られるダイナミクスは、プレイヤー間でのペイオフベース、収束、合理的、対称である。
• 参考スコア（独自算出の注目度）: 22.62123576833411
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study two-player zero-sum stochastic games, and propose a form of independent learning dynamics called Doubly Smoothed Best-Response dynamics, which integrates a discrete and doubly smoothed variant of the best-response dynamics into temporal-difference (TD)-learning and minimax value iteration. The resulting dynamics are payoff-based, convergent, rational, and symmetric among players. Our main results provide finite-sample guarantees. In particular, we prove the first-known $\tilde{\mathcal{O}}(1/\epsilon^2)$ sample complexity bound for payoff-based independent learning dynamics, up to a smoothing bias. In the special case where the stochastic game has only one state (i.e., matrix games), we provide a sharper $\tilde{\mathcal{O}}(1/\epsilon)$ sample complexity. Our analysis uses a novel coupled Lyapunov drift approach to capture the evolution of multiple sets of coupled and stochastic iterates, which might be of independent interest.
• Abstract（参考訳）: 本研究では,2人プレイのゼロサム確率ゲームについて検討し,doubly smoothed best-response dynamicsと呼ばれる独立学習ダイナミクスの形式を提案し,最良応答ダイナミクスの離散的かつ二重に平滑化した変種をtemporal-difference(td)学習とminimax値反復に統合する。 結果として得られるダイナミクスは、プレイヤー間のペイオフベース、収束、合理的、対称である。 主な結果は有限サンプル保証である。 特に、最初に知られた$\tilde{\mathcal{O}}(1/\epsilon^2)$サンプル複雑性をペイオフベースの独立学習力学に限定し、スムーズなバイアスまで証明する。 確率ゲームが一つの状態(つまり行列ゲーム)しか持たない特別な場合、よりシャープな$\tilde{\mathcal{O}}(1/\epsilon)$サンプル複雑性を提供する。 我々の分析では、結合された複数の反復と確率的反復の進化を捉えるために、新しい結合されたリアプノフドリフトアプローチを用いている。

関連論文リスト

• Last-Iterate Convergence of Payoff-Based Independent Learning in Zero-Sum Stochastic Games [31.554420227087043]
  両プレイヤー間のペイオフベース、収束、合理的、対称な学習ダイナミクスを開発する。 行列ゲーム設定では、結果はナッシュ分布を見つけるために$O(epsilon-1)$の複雑さを意味する。 ゲーム設定では、結果はナッシュ平衡を求めるために$O(epsilon-8)$の複雑さをも意味している。
  論文  参考訳（メタデータ） (2024-09-02T20:07:25Z)
• Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Games [18.11805544026393]
  本研究はマルコフポテンシャルゲームにおけるマルチエージェント強化学習問題に対する独立自然ポリシー勾配(NPG)アルゴリズムについて研究する。 技術的に微妙な仮定では、正確なポリシーを提供するオラクルを持つ独立したNPG法は、$mathcalO(1/epsilon)$イテレーション内で$epsilon$-Nash Equilibrium (NE)に達することが示されている。
  論文  参考訳（メタデータ） (2023-10-15T04:10:44Z)
• Provably Robust Temporal Difference Learning for Heavy-Tailed Rewards [27.209606183563853]
  動的勾配クリッピング機構による時間差(TD)学習は,重み付き報酬分布に対して確実に堅牢化できることを確認した。 TD学習に基づくNACの頑健な変種が$tildemathcalO(varepsilon-frac1p)$サンプル複雑性を達成することを示す。
  論文  参考訳（メタデータ） (2023-06-20T11:12:21Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。 これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。 アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
  論文  参考訳（メタデータ） (2022-10-22T19:07:26Z)
• 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)
• Tightening the Dependence on Horizon in the Sample Complexity of Q-Learning [59.71676469100807]
  この研究は、同期Q-ラーニングのサンプルの複雑さを、任意の$0varepsilon 1$に対して$frac|mathcalS| (1-gamma)4varepsilon2$の順序に絞る。 計算やストレージを余分に必要とせずに、高速なq-learningにマッチするvanilla q-learningの有効性を明らかにした。
  論文  参考訳（メタデータ） (2021-02-12T14:22:05Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)

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

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