論文の概要: Anytime-Constrained Multi-Agent Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2410.23637v1
• Date: Thu, 31 Oct 2024 05:07:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-01 17:02:23.884750
• Title: Anytime-Constrained Multi-Agent Reinforcement Learning
• Title（参考訳）: 時間制約付きマルチエージェント強化学習
• Authors: Jeremy McMahan, Xiaojin Zhu,
• Abstract要約: 我々は、任意の時間制約均衡(ACE)に対応する解を持つマルチエージェント設定に、任意の時間制約を導入する。 実効性のあるポリシーの計算的特徴を含む,任意の時間制約付きマルコフゲームに関する包括的理論を提案する。 また、アクション制約付きマルコフゲームに対する効率的な計算の第一理論も、独立に興味を持つかもしれない。
• 参考スコア（独自算出の注目度）: 6.981971551979697
• License:
• Abstract: We introduce anytime constraints to the multi-agent setting with the corresponding solution concept being anytime-constrained equilibrium (ACE). Then, we present a comprehensive theory of anytime-constrained Markov games, which includes (1) a computational characterization of feasible policies, (2) a fixed-parameter tractable algorithm for computing ACE, and (3) a polynomial-time algorithm for approximately computing feasible ACE. Since computing a feasible policy is NP-hard even for two-player zero-sum games, our approximation guarantees are the best possible under worst-case analysis. We also develop the first theory of efficient computation for action-constrained Markov games, which may be of independent interest.
• Abstract（参考訳）: マルチエージェント設定に任意の時間制約を導入し、対応する解の概念は任意の時間制約均衡(ACE)である。 そこで我々は,(1)実行可能ポリシーの計算的特徴付け,(2)計算可能ACEのための固定パラメータ抽出可能アルゴリズム,(3)ほぼ計算可能ACEのための多項式時間アルゴリズムを含む,任意の時間制約付きマルコフゲームに関する包括的理論を提案する。 2プレイヤゼロサムゲームでも実現可能なポリシの計算はNPハードであるため、最悪のケース分析では近似保証が最善である。 また、アクション制約付きマルコフゲームに対する効率的な計算の第一理論も開発し、これは独立した関心を持つかもしれない。

関連論文リスト

• Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time [1.223779595809275]
  本アルゴリズムは,制約付き強化学習問題に対するほぼ最適決定性ポリシーを効率的に計算する。 我々の研究は、2つの長年の研究にまたがる3つのオープンな疑問に答える。
  論文  参考訳（メタデータ） (2024-05-23T05:27:51Z)
• Independent Learning in Constrained Markov Potential Games [19.083595175045073]
  制約付きマルコフゲームは、マルチエージェント強化学習問題をモデル化するための正式なフレームワークを提供する。 近似的制約付きナッシュ平衡を学習するための独立ポリシー勾配アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-27T20:57:35Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。 我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。 我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
  論文  参考訳（メタデータ） (2023-03-22T03:28:12Z)
• Efficiently Computing Nash Equilibria in Adversarial Team Markov Games [19.717850955051837]
  我々は,同じプレイヤーが対戦相手と競合するゲームのクラスを紹介する。 この設定により、ゼロサムマルコフゲームの可能性ゲームの統一処理が可能になる。 我々の主な貢献は、対戦チームマルコフゲームにおける固定的な$epsilon$-approximate Nash平衡を計算するための最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2022-08-03T16:41:01Z)
• 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)
• The Complexity of Markov Equilibrium in Stochastic Games [44.77547027158141]
  一般ゲームにおける確率的定常なマルコフ粗相関平衡(CCE)の計算は、計算的に難解であることを示す。 この結果は、正確なCCEを効率的に計算可能な正規形式ゲームとは対照的である。
  論文  参考訳（メタデータ） (2022-04-08T10:51:01Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。 一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
  論文  参考訳（メタデータ） (2020-12-04T15:36:29Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive [57.47546090379434]
  i) 任意の状態空間, (ii) 任意の行動空間, (iii) 任意の送信者のユーティリティ関数を用いて, 一般の状況下での公衆の説得問題を考察する。 任意の公的な説得問題に対して準多項式時間ビクテリア近似アルゴリズムを提案し、特定の設定でQPTASを出力する。
  論文  参考訳（メタデータ） (2020-02-12T18:59:18Z)

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

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