論文の概要: Solving Hierarchical Information-Sharing Dec-POMDPs: An Extensive-Form Game Approach

• arxiv url: http://arxiv.org/abs/2402.02954v1
• Date: Mon, 5 Feb 2024 12:33:05 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-06 16:23:17.407073
• Title: Solving Hierarchical Information-Sharing Dec-POMDPs: An Extensive-Form Game Approach
• Title（参考訳）: 階層型情報共有Dec-POMDPの解法 - 汎用型ゲームアプローチ
• Authors: Johan Peralez, Aur\'elien Delage, Olivier Buffet, Jilles S. Dibangoye
• Abstract要約: 本稿では,階層的な情報共有の下での最適性を維持しつつ,決定変数をアンタングルにする方法を示す。 我々のアプローチでは、広義のゲームは常に単一ステージのサブゲームに対する解決策として存在し、時間的複雑さを著しく減少させる。
• 参考スコア（独自算出の注目度）: 2.908482270923597
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A recent theory shows that a multi-player decentralized partially observable Markov decision process can be transformed into an equivalent single-player game, enabling the application of \citeauthor{bellman}'s principle of optimality to solve the single-player game by breaking it down into single-stage subgames. However, this approach entangles the decision variables of all players at each single-stage subgame, resulting in backups with a double-exponential complexity. This paper demonstrates how to disentangle these decision variables while maintaining optimality under hierarchical information sharing, a prominent management style in our society. To achieve this, we apply the principle of optimality to solve any single-stage subgame by breaking it down further into smaller subgames, enabling us to make single-player decisions at a time. Our approach reveals that extensive-form games always exist with solutions to a single-stage subgame, significantly reducing time complexity. Our experimental results show that the algorithms leveraging these findings can scale up to much larger multi-player games without compromising optimality.
• Abstract（参考訳）: 最近の理論では、マルチプレイヤーの部分観測可能なマルコフ決定プロセスが等価な単一プレイヤーゲームに変換され、単一ステージのサブゲームに分解することで、単一プレイヤーゲームを解決するための最適性の原理が適用可能である。 しかし、このアプローチは、各シングルステージのサブゲームにおける全てのプレイヤーの決定変数を絡み合わせることで、二重指数複雑性を持つバックアップとなる。 本稿では,階層的な情報共有の下での最適性を維持しつつ,これらの決定変数を解き放つ方法を示す。 これを実現するため、我々は、より小さなサブゲームに分解することで、任意のシングルステージのサブゲームを解決するために最適性の原則を適用し、同時にシングルプレイヤーの決定を行えるようにする。 我々のアプローチでは、広義のゲームは常に単一ステージのサブゲームに対する解決策として存在し、時間的複雑さを著しく減少させる。 実験の結果,この結果を利用したアルゴリズムは,最適化を損なうことなく,より大規模なマルチプレイヤーゲームにスケールアップできることがわかった。

関連論文リスト

• Convex Markov Games: A Framework for Fairness, Imitation, and Creativity in Multi-Agent Learning [31.958202912400925]
  コンベックス・マルコフゲーム(英語版)のクラスを導入し、占有度よりも一般的なコンベックス・プレイスを可能にする。 無限の時間的地平線とマルコフゲームよりも厳密な一般性にもかかわらず、純粋な戦略 ナッシュ平衡は厳密な凸性の下で存在する。 我々の実験は、最後通しゲームにおける人間の選択を模倣し、繰り返しの囚人のジレンマに対する新しい解決策を明らかにし、反復的な非対称調整ゲームにおいて公正な解決策を見つける。
  論文  参考訳（メタデータ） (2024-10-22T00:55:04Z)
• Imperfect-Recall Games: Equilibrium Concepts and Their Complexity [74.01381499760288]
  エージェントが以前保持していた情報を忘れたとき、不完全なリコールの下で最適な意思決定を行う。 不完全なリコールを伴う広範囲形式のゲームフレームワークにおいて、マルチプレイヤー設定における平衡を求める際の計算複雑性を解析する。
  論文  参考訳（メタデータ） (2024-06-23T00:27:28Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。 我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。 我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
  論文  参考訳（メタデータ） (2023-03-22T03:28:12Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  我々は平均場相関と粗相関平衡の概念を発展させる。 ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
  論文  参考訳（メタデータ） (2022-08-22T08:31:46Z)
• 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)
• Learning in Congestion Games with Bandit Feedback [45.4542525044623]
  我々は、良質な理論構造と広い実世界の応用を持つゲームのクラスである混雑ゲームについて検討する。 まず,渋滞ゲームにおける不確実性原理に直面する楽観性に基づく集中型アルゴリズムを提案する。 次に,Frank-Wolfe法とG-Optimal設計を組み合わせた分散アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-04T02:32:26Z)
• Public Information Representation for Adversarial Team Games [31.29335755664997]
  対戦チームゲームは、プレイ中にチームメンバーが利用可能な非対称情報の中にあります。 本アルゴリズムは,対戦相手を持つ逐次チームゲームから古典的な2プレイヤーゼロサムゲームに変換する。 この問題のNPハード性のため、結果のパブリックチームゲームは元のゲームよりも指数関数的に大きいかもしれない。
  論文  参考訳（メタデータ） (2022-01-25T15:07:12Z)
• An Instance-Dependent Analysis for the Cooperative Multi-Player Multi-Armed Bandit [93.97385339354318]
  マルチプレイヤーマルチアーマッドバンドにおける情報共有と協調の課題について検討する。 まず, プレイヤーの最適度差を推定するために, 逐次的除去戦略への簡単な修正が可能であることを示す。 第2に,第1の結果を利用して,衝突の小さな報奨をプレイヤー間の協調に役立てる通信プロトコルを設計する。
  論文  参考訳（メタデータ） (2021-11-08T23:38:47Z)
• Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies in Extensive-Form Zero-Sum Games [123.76716667704625]
  我々は,不完全情報ゼロサム拡張形式ゲームにおいて,対戦相手と対決する2人の選手のチームにとって最適な戦略を見つけることの課題に焦点をあてる。 この設定では、チームができる最善のことは、ゲーム開始時の関節(つまり相関した)確率分布から潜在的にランダム化された戦略(プレイヤー1人)のプロファイルをサンプリングすることである。 各プロファイルにランダム化されるのはチームメンバーの1人だけであるプロファイルのみを用いることで、そのような最適な分布を計算するアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-09-21T17:51:57Z)

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

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