論文の概要: Learning Rationalizable Equilibria in Multiplayer Games

• arxiv url: http://arxiv.org/abs/2210.11402v1
• Date: Thu, 20 Oct 2022 16:49:00 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-21 13:23:27.285546
• Title: Learning Rationalizable Equilibria in Multiplayer Games
• Title（参考訳）: マルチプレイヤーゲームにおける合理的平衡の学習
• Authors: Yuanhao Wang, Dingwen Kong, Yu Bai, Chi Jin
• Abstract要約: 既存のアルゴリズムでは、帯域幅フィードバックの下で合理化可能な平衡を学習するために、プレイヤー数で指数関数的に多くのサンプルを必要とする。 本稿では、合理化可能な粗相関平衡(CCE)と相関平衡(CE)を学習するための効率的なアルゴリズムの第一線を開発する。 本アルゴリズムは,合理化可能性を保証するための新しい手法と,相関探索スキームと適応学習率を含む(スワップ-)レグレットを同時に備えている。
• 参考スコア（独自算出の注目度）: 38.922957434291554
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A natural goal in multiagent learning besides finding equilibria is to learn rationalizable behavior, where players learn to avoid iteratively dominated actions. However, even in the basic setting of multiplayer general-sum games, existing algorithms require a number of samples exponential in the number of players to learn rationalizable equilibria under bandit feedback. This paper develops the first line of efficient algorithms for learning rationalizable Coarse Correlated Equilibria (CCE) and Correlated Equilibria (CE) whose sample complexities are polynomial in all problem parameters including the number of players. To achieve this result, we also develop a new efficient algorithm for the simpler task of finding one rationalizable action profile (not necessarily an equilibrium), whose sample complexity substantially improves over the best existing results of Wu et al. (2021). Our algorithms incorporate several novel techniques to guarantee rationalizability and no (swap-)regret simultaneously, including a correlated exploration scheme and adaptive learning rates, which may be of independent interest. We complement our results with a sample complexity lower bound showing the sharpness of our guarantees.
• Abstract（参考訳）: マルチエージェント学習の自然な目標は、均衡を見つけること以外に合理的な行動を学ぶことであり、プレイヤーは反復的に支配される行動を避けることを学ぶ。 しかし、マルチプレイヤーの汎用ゲームの基本設定でさえ、既存のアルゴリズムは、バンドイットフィードバックの下で合理化可能な平衡を学習するために、プレイヤー数で指数関数的に多くのサンプルを必要とする。 本稿では,プレイヤー数を含む全ての問題パラメータにおいて,サンプルの複雑度が多項式である有理化可能な粗相関平衡 (CCE) と相関平衡 (CE) を学習するためのアルゴリズムの最初の行を開発する。 この結果を達成するために、より単純なタスクのための新しい効率的なアルゴリズム(必ずしも平衡ではない)を開発し、そのサンプルの複雑さは、wu等(2021年)の最良の結果よりも大幅に向上した。 提案アルゴリズムは合理化可能性を保証するための新しい手法をいくつか組み込んでおり, 相関探索スキームや適応学習率など, 独立性を持つかもしれない。 保証のシャープさを示す、サンプルの複雑さの低い境界で結果を補完する。

関連論文リスト

• Tractable Equilibrium Computation in Markov Games through Risk Aversion [12.980882140751895]
  リスク-逆量子応答平衡(RQE)は,すべての$n$プレーヤ行列と有限ホリゾンマルコフゲームで計算可能であることを示す。 RQEは下層のゲーム構造とは独立であり、エージェントのリスク回避度と有界有理性にのみ依存する。
  論文  参考訳（メタデータ） (2024-06-20T09:53:56Z)
• Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learning [50.92957910121088]
  本研究は,情報指向サンプリング(IDS)の原理に基づくマルチエージェント強化学習(MARL)のための新しいアルゴリズムの設計と解析を行う。 エピソディックな2プレーヤゼロサムMGに対して、ナッシュ平衡を学習するための3つのサンプル効率アルゴリズムを提案する。 我々は、Reg-MAIDSをマルチプレイヤー汎用MGに拡張し、ナッシュ平衡または粗相関平衡をサンプル効率良く学習できることを証明する。
  論文  参考訳（メタデータ） (2024-04-30T06:48:56Z)
• On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring [105.13668993076801]
  マルチエージェント強化学習(MARL)理論における中心的な問題は、構造条件やアルゴリズムの原理がサンプル効率の学習保証につながるかを理解することである。 本稿では,複数のエージェントを用いた対話型意思決定のための一般的な枠組みとして,この問題について考察する。 マルチエージェント意思決定における統計的複雑性を特徴付けることは、単一エージェント決定の統計的複雑性を特徴付けることと等価であることを示す。
  論文  参考訳（メタデータ） (2023-05-01T06:46:22Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。 所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。 我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
  論文  参考訳（メタデータ） (2023-04-12T14:51:47Z)
• Batch Active Learning from the Perspective of Sparse Approximation [12.51958241746014]
  アクティブな学習は、機械学習エージェントと人間のアノテーションとのインタラクションを活用することで、効率的なモデルトレーニングを可能にする。 スパース近似の観点からバッチアクティブラーニングを定式化する新しいフレームワークを提案し,提案する。 我々のアクティブラーニング手法は、ラベルのないデータプールから、対応するトレーニング損失関数が、そのフルデータプールに近似するように、情報的サブセットを見つけることを目的としている。
  論文  参考訳（メタデータ） (2022-11-01T03:20:28Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。 これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。 アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
  論文  参考訳（メタデータ） (2022-10-22T19:07:26Z)
• Regret Minimization and Convergence to Equilibria in General-sum Markov Games [57.568118148036376]
  汎用マルコフゲームにおいて,全てのエージェントが実行した場合のサブ線形後悔保証を提供する学習アルゴリズムを初めて提示する。 我々のアルゴリズムは分散化され、計算効率が良く、エージェント間の通信は不要である。
  論文  参考訳（メタデータ） (2022-07-28T16:27:59Z)
• Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationality [21.94743452608215]
  本研究では,ゲーム報酬と探索費用のバランスを捉えたプロトタイプ学習モデルであるスムーズQ-ラーニングについて検討する。 Q-ラーニングは常に、有界な有理性の下でのゲームに対する標準的な解概念である一意の量子-応答平衡(QRE)に収束することを示す。
  論文  参考訳（メタデータ） (2021-06-24T11:43:38Z)
• Hindsight and Sequential Rationality of Correlated Play [18.176128899338433]
  私たちは、修正された振る舞いで達成できたことに対して、強いパフォーマンスを後見で保証するアルゴリズムを検討します。 我々は,学習の隠れた枠組みを,逐次的な意思決定の場で開発し,提唱する。 本稿では,それぞれの平衡の強さと弱さを文献に示す例を示す。
  論文  参考訳（メタデータ） (2020-12-10T18:30:21Z)

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

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