論文の概要: Roping in Uncertainty: Robustness and Regularization in Markov Games

• arxiv url: http://arxiv.org/abs/2406.08847v1
• Date: Thu, 13 Jun 2024 06:15:44 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-14 19:03:54.788293
• Title: Roping in Uncertainty: Robustness and Regularization in Markov Games
• Title（参考訳）: 不確実性のローピング:マルコフゲームにおけるロバストさと規則化
• Authors: Jeremy McMahan, Giovanni Artiglio, Qiaomin Xie,
• Abstract要約: 頑健なマルコフゲーム(RMG)を$s$の正方形不確実性で研究する。 正方形RMGのロバストなナッシュ平衡(RNE)と、適切に構成された正規化MGのナッシュ平衡(NE)との一般的な等価性を示す。 報酬のない2プレイヤーゼロサム行列ゲームであっても、RNEの計算はPPADハードであることを示す。
• 参考スコア（独自算出の注目度）: 4.977191491791789
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study robust Markov games (RMG) with $s$-rectangular uncertainty. We show a general equivalence between computing a robust Nash equilibrium (RNE) of a $s$-rectangular RMG and computing a Nash equilibrium (NE) of an appropriately constructed regularized MG. The equivalence result yields a planning algorithm for solving $s$-rectangular RMGs, as well as provable robustness guarantees for policies computed using regularized methods. However, we show that even for just reward-uncertain two-player zero-sum matrix games, computing an RNE is PPAD-hard. Consequently, we derive a special uncertainty structure called efficient player-decomposability and show that RNE for two-player zero-sum RMG in this class can be provably solved in polynomial time. This class includes commonly used uncertainty sets such as $L_1$ and $L_\infty$ ball uncertainty sets.
• Abstract（参考訳）: 頑健なマルコフゲーム(RMG)を$s$の正方形不確実性で研究する。 正方形RMGのロバストなナッシュ平衡(RNE)と、適切に構成された正規化MGのナッシュ平衡(NE)との一般的な等価性を示す。 等価性の結果は、$s$正方形RMGを解くための計画アルゴリズムと、正規化法を用いて計算されたポリシーに対する証明可能な堅牢性を保証する。 しかし、報酬のない2プレイヤーゼロサム行列ゲームであっても、RNEの計算はPPADハードであることを示す。 その結果,このクラスにおける2-player 0-sum RMG の RNE が多項式時間で有効に解けることを示す。 このクラスは、一般に使われる$L_1$や$L_\infty$ボールの不確実性集合を含む。

関連論文リスト

• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property [89.96815099996132]
  単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。 我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
  論文  参考訳（メタデータ） (2023-12-19T11:34:10Z)
• Scalable and Independent Learning of Nash Equilibrium Policies in $n$-Player Stochastic Games with Unknown Independent Chains [1.0878040851638]
  独立な連鎖と未知の遷移行列を持つゲームについて研究する。 このクラスのゲームでは、プレイヤーは他のプレイヤーの状態や行動に依存しない内部マルコフ連鎖を制御する。 我々は、$epsilon$-NEポリシーを学ぶために、完全に分散化されたミラー降下アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-04T03:04:09Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• When are Local Queries Useful for Robust Learning? [25.832511407411637]
  本研究では,学習者が局所的なクエリを用いてより多くのパワーを与えられる学習モデルについて検討する。 我々は、ロバストな経験的リスク最小化を行う最初の分布自由アルゴリズムを与える。 我々は、0,1n$でハーフスペースに対してロバストな学習アルゴリズムを与え、その後、精度に縛られた敵に対して$mathbbRn$でハーフスペースに対してロバスト性を保証する。
  論文  参考訳（メタデータ） (2022-10-12T11:04:22Z)
• 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)
• A Sharp Analysis of Model-based Reinforcement Learning with Self-Play [49.88233710867315]
  マルチエージェントマルコフゲームのためのモデルベースセルフプレイアルゴリズムのシャープな解析を行う。 我々は,2プレイヤーゼロサムマルコフゲームのための最適化ナッシュ値イテレーション(Nash-VI)を設計する。 我々はさらに、ゼロサムマルコフゲームに対する証明可能な効率的なタスク認識アルゴリズムの設計に我々の分析を適用した。
  論文  参考訳（メタデータ） (2020-10-04T15:27:39Z)
• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification [54.22421582955454]
  逆向きに頑健な分類の過剰リスクに対する最適ミニマックス保証の最初の結果を提供する。 結果はAdvSNR(Adversarial Signal-to-Noise Ratio)の項で述べられており、これは標準的な線形分類と逆数設定との類似の考え方を一般化している。
  論文  参考訳（メタデータ） (2020-06-29T21:06:52Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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