論文の概要: 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年)の最良の結果よりも大幅に向上した。
提案アルゴリズムは合理化可能性を保証するための新しい手法をいくつか組み込んでおり, 相関探索スキームや適応学習率など, 独立性を持つかもしれない。
保証のシャープさを示す、サンプルの複雑さの低い境界で結果を補完する。
関連論文リスト
- Sample-Efficient Multi-Agent RL: An Optimization Perspective [103.35353196535544]
一般関数近似に基づく汎用マルコフゲーム(MG)のためのマルチエージェント強化学習(MARL)について検討した。
汎用MGに対するマルチエージェントデカップリング係数(MADC)と呼ばれる新しい複雑性尺度を導入する。
我々のアルゴリズムは既存の研究に匹敵するサブリニアな後悔を与えることを示す。
論文 参考訳(メタデータ) (2023-10-10T01:39:04Z) - 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) - A Moment-Matching Approach to Testable Learning and a New
Characterization of Rademacher Complexity [15.746613321517282]
我々は、モーメントマッチングやメートル法非依存のツールを用いて、テスト可能な学習アルゴリズムを開発するための強力な新しいアプローチを提案する。
意外なことに、テスト可能な学習における情報理論の複雑さは、概念クラスのRademacher複雑さによって強く特徴づけられている。
論文 参考訳(メタデータ) (2022-11-23T21:29:51Z) - Batch Active Learning from the Perspective of Sparse Approximation [12.51958241746014]
アクティブな学習は、機械学習エージェントと人間のアノテーションとのインタラクションを活用することで、効率的なモデルトレーニングを可能にする。
スパース近似の観点からバッチアクティブラーニングを定式化する新しいフレームワークを提案し,提案する。
我々のアクティブラーニング手法は、ラベルのないデータプールから、対応するトレーニング損失関数が、そのフルデータプールに近似するように、情報的サブセットを見つけることを目的としている。
論文 参考訳(メタデータ) (2022-11-01T03:20:28Z) - Regret Minimization and Convergence to Equilibria in General-sum Markov
Games [57.568118148036376]
汎用マルコフゲームにおいて,全てのエージェントが実行した場合のサブ線形後悔保証を提供する学習アルゴリズムを初めて提示する。
我々のアルゴリズムは分散化され、計算効率が良く、エージェント間の通信は不要である。
論文 参考訳(メタデータ) (2022-07-28T16:27:59Z) - Contextual Model Aggregation for Fast and Robust Federated Learning in
Edge Computing [88.76112371510999]
フェデレーション学習は、ネットワークエッジにおける分散機械学習の第一候補である。
既存のアルゴリズムは、性能の緩やかな収束や堅牢性の問題に直面している。
そこで本稿では,損失低減に対する最適コンテキスト依存境界を実現するためのコンテキストアグリゲーション手法を提案する。
論文 参考訳(メタデータ) (2022-03-23T21:42:31Z) - Exploration-Exploitation in Multi-Agent Competition: Convergence with
Bounded Rationality [21.94743452608215]
本研究では,ゲーム報酬と探索費用のバランスを捉えたプロトタイプ学習モデルであるスムーズQ-ラーニングについて検討する。
Q-ラーニングは常に、有界な有理性の下でのゲームに対する標準的な解概念である一意の量子-応答平衡(QRE)に収束することを示す。
論文 参考訳(メタデータ) (2021-06-24T11:43:38Z) - Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning [36.015585972493575]
本稿では,一般値関数近似を用いたバッチ強化学習(RL)について考察する。
Empirical Risk Minimizer (ERM) の過剰リスクは、関数クラスの Rademacher 複雑性によって有界である。
高速統計率は局所ラデマッハ複雑性のツールを使用することで達成できる。
論文 参考訳(メタデータ) (2021-03-25T14:45:29Z) - Hindsight and Sequential Rationality of Correlated Play [18.176128899338433]
私たちは、修正された振る舞いで達成できたことに対して、強いパフォーマンスを後見で保証するアルゴリズムを検討します。
我々は,学習の隠れた枠組みを,逐次的な意思決定の場で開発し,提唱する。
本稿では,それぞれの平衡の強さと弱さを文献に示す例を示す。
論文 参考訳(メタデータ) (2020-12-10T18:30:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。