論文の概要: Sample-Efficient Learning of Correlated Equilibria in Extensive-Form Games

• arxiv url: http://arxiv.org/abs/2205.07223v1
• Date: Sun, 15 May 2022 08:55:28 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-17 15:02:52.576334
• Title: Sample-Efficient Learning of Correlated Equilibria in Extensive-Form Games
• Title（参考訳）: 広範囲ゲームにおける相関平衡のサンプル効率学習
• Authors: Ziang Song, Song Mei, Yu Bai
• Abstract要約: Imperfect-Information Extensive-Form Games (IIEFG) は、不完全情報とシーケンシャルプレイを含む現実世界のゲームにおいて一般的なモデルである。 Extensive-Form Correlated Equilibrium (EFCE) はマルチプレイヤー汎用IIEFGの自然解の概念として提案されている。 本稿では,バンドフィードバックからEFCEを学習するための最初のサンプル効率アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 22.94768429216664
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Imperfect-Information Extensive-Form Games (IIEFGs) is a prevalent model for real-world games involving imperfect information and sequential plays. The Extensive-Form Correlated Equilibrium (EFCE) has been proposed as a natural solution concept for multi-player general-sum IIEFGs. However, existing algorithms for finding an EFCE require full feedback from the game, and it remains open how to efficiently learn the EFCE in the more challenging bandit feedback setting where the game can only be learned by observations from repeated playing. This paper presents the first sample-efficient algorithm for learning the EFCE from bandit feedback. We begin by proposing $K$-EFCE -- a more generalized definition that allows players to observe and deviate from the recommended actions for $K$ times. The $K$-EFCE includes the EFCE as a special case at $K=1$, and is an increasingly stricter notion of equilibrium as $K$ increases. We then design an uncoupled no-regret algorithm that finds an $\varepsilon$-approximate $K$-EFCE within $\widetilde{\mathcal{O}}(\max_{i}X_iA_i^{K}/\varepsilon^2)$ iterations in the full feedback setting, where $X_i$ and $A_i$ are the number of information sets and actions for the $i$-th player. Our algorithm works by minimizing a wide-range regret at each information set that takes into account all possible recommendation histories. Finally, we design a sample-based variant of our algorithm that learns an $\varepsilon$-approximate $K$-EFCE within $\widetilde{\mathcal{O}}(\max_{i}X_iA_i^{K+1}/\varepsilon^2)$ episodes of play in the bandit feedback setting. When specialized to $K=1$, this gives the first sample-efficient algorithm for learning EFCE from bandit feedback.
• Abstract（参考訳）: Imperfect-Information Extensive-Form Games (IIEFG) は、不完全情報とシーケンシャルプレイを含む現実世界のゲームにおいて一般的なモデルである。 Extensive-Form Correlated Equilibrium (EFCE) はマルチプレイヤー汎用IIEFGの自然解の概念として提案されている。 しかし、既存のEFCEを見つけるアルゴリズムはゲームからの完全なフィードバックを必要としており、繰り返しプレイすることでしかゲームが学べないより困難な帯域幅フィードバック環境で、EFCEを効率的に学習する方法は依然としてオープンである。 本稿では,バンドフィードバックからEFCEを学習するための最初のサンプル効率アルゴリズムを提案する。 より一般化された定義である$K$-EFCEの提案から始めます。 K$-EFCE は EFCE を特殊ケースとして$K=1$ を含み、K$ が増加するにつれて平衡の概念がより厳格になる。 そして、$\widetilde{\mathcal{o}}(\max_{i}x_ia_i^{k}/\varepsilon^2)$の完全なフィードバック設定で、$x_i$ と $a_i$ が$i$-th プレーヤーの情報セットとアクションの数であるような、非結合な no-regret アルゴリズムを設計する。 我々のアルゴリズムは、全てのレコメンデーション履歴を考慮に入れた各情報集合に対する幅広い後悔を最小化する。 最後に、このアルゴリズムのサンプルベース変種を設計し、バンドイットフィードバック設定におけるプレイのエピソードを$\widetilde{\mathcal{o}}(\max_{i}x_ia_i^{k+1}/\varepsilon^2)$で学習する。 K=1$に特化すると、バンディットフィードバックからEFCEを学習するための最初のサンプル効率のアルゴリズムが得られる。

関連論文リスト

• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Efficient $\Phi$-Regret Minimization in Extensive-Form Games via Online Mirror Descent [49.93548413166884]
  $Phi$-Hedgeは、正規形式ゲーム(NFG)のための大規模な平衡を学習できる汎用アルゴリズムである。 EFGにおけるNash Equilibria(ゼロサム設定)、Normal-Form Coarse Correlated Equilibria(NFCCE)、Extensive-Form Correlated Equilibria(EFCE)の学習に$Phi$-Hedgeが直接利用できることを示す。 それらの設定において、emph$Phi$-Hedgeアルゴリズムは標準ミラーDescent(OMD)アルゴリズムと等価であることを示す。
  論文  参考訳（メタデータ） (2022-05-30T17:58:06Z)
• Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
  本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。 これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
  論文  参考訳（メタデータ） (2022-02-03T18:18:28Z)
• Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback [29.553652241608997]
  本研究では,テキストモオと強いモノトーンゲームの研究を行い,その学習方法について検討した。 我々はまず,新しい帯域学習アルゴリズムを構築し,$tildeTheta(nsqrtT)$の単一エージェント最適後悔を実現することを示す。 そこで我々は,このオープンな問題を解決し,広範にわたるバンディットゲーム理論学習に寄与した。
  論文  参考訳（メタデータ） (2021-12-06T08:27:54Z)
• When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently? [10.397170312149067]
  本稿では,m$-player General-sum Markovゲームの設定において,学習目標がより優れたサンプル複雑性を許容するものについて検討する。 まず,$epsilon$-Coarse Correlated Equilibrium (CCE)を$widetildemathcalO(H5Smax_ile m A_i / epsilon2)$ episodesで学習するアルゴリズムを設計する。 第二に、マルコフポテンシャルゲームの重要な特別な場合を考え、$widet内で$epsilon$-approximate Nash平衡を学ぶアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-10-08T15:06:22Z)
• Almost Optimal Algorithms for Two-player Markov Games with Linear Function Approximation [92.99933928528797]
  同時動作による2プレイヤーゼロサムマルコフゲームの強化学習について検討した。 我々は,「不確かさの最適性」に基づくアルゴリズムナッシュ-UCRL-VTRを提案する。 我々は、Nash-UCRL-VTR が $tildeO(dHsqrtT)$ regret を確実に達成できることを示し、$d$ は線型関数次元である。
  論文  参考訳（メタデータ） (2021-02-15T09:09:16Z)
• Impact of Representation Learning in Linear Bandits [83.17684841392754]
  本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。 我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-13T16:35:30Z)
• Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
  我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。 本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-22T05:00:13Z)

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

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