論文の概要: Near-Optimal Learning of Extensive-Form Games with Imperfect Information
- arxiv url: http://arxiv.org/abs/2202.01752v2
- Date: Thu, 30 Mar 2023 23:15:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-03 17:47:08.266336
- Title: Near-Optimal Learning of Extensive-Form Games with Imperfect Information
- Title（参考訳）: 不完全情報を用いた総合型ゲームの準最適学習
- Authors: Yu Bai, Chi Jin, Song Mei, Tiancheng Yu
- Abstract要約: 本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。
これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
- 参考スコア（独自算出の注目度）: 54.55092907312749
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper resolves the open question of designing near-optimal algorithms
for learning imperfect-information extensive-form games from bandit feedback.
We present the first line of algorithms that require only
$\widetilde{\mathcal{O}}((XA+YB)/\varepsilon^2)$ episodes of play to find an
$\varepsilon$-approximate Nash equilibrium in two-player zero-sum games, where
$X,Y$ are the number of information sets and $A,B$ are the number of actions
for the two players. This improves upon the best known sample complexity of
$\widetilde{\mathcal{O}}((X^2A+Y^2B)/\varepsilon^2)$ by a factor of
$\widetilde{\mathcal{O}}(\max\{X, Y\})$, and matches the information-theoretic
lower bound up to logarithmic factors. We achieve this sample complexity by two
new algorithms: Balanced Online Mirror Descent, and Balanced Counterfactual
Regret Minimization. Both algorithms rely on novel approaches of integrating
\emph{balanced exploration policies} into their classical counterparts. We also
extend our results to learning Coarse Correlated Equilibria in multi-player
general-sum games.
- Abstract（参考訳）: 本稿では,バンディットフィードバックから不完全な情報を広範に学習するための,最適に近いアルゴリズムを設計するという課題を解決する。
x,y$ は情報集合の数であり、$a,b$ は2人のプレイヤーのアクションの数である2人のゼロサムゲームにおいて$\varepsilon$-approximate nash平衡を見つけるためにプレイのエピソードのうち、$\widetilde{\mathcal{o}}((xa+yb)/\varepsilon^2) だけを必要とするアルゴリズムの最初の行を示す。
これにより、$\widetilde{\mathcal{O}}((X^2A+Y^2B)/\varepsilon^2)$の係数が$\widetilde{\mathcal{O}}(\max\{X, Y\})$の最もよく知られたサンプル複雑性が改善され、情報理論の下限を対数因子に合わせる。
我々はこのサンプルの複雑さを2つの新しいアルゴリズム: Balanced Online Mirror Descent と Balanced Counterfactual Regret Minimization によって達成する。
どちらのアルゴリズムも、古典的手法に『emph{balanced exploration policies}』を統合する新しい手法に依存している。
また,マルチプレイヤー汎用ゲームにおける粗相関平衡学習にも適用した。
関連論文リスト
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
オンライン学習によるセルフプレイは、大規模な2人プレイのゼロサムゲームを解くための重要な方法の1つだ。
我々は,OMWUが支払行列のサイズに対数依存するなど,いくつかの利点があることを示した。
我々は、過去のことをすぐに忘れない幅広い種類のアルゴリズムが、すべて同じ問題に悩まされていることを証明している。
論文 参考訳（メタデータ） (2024-06-15T13:26:17Z) - The complexity of approximate (coarse) correlated equilibrium for incomplete information games [16.96984593866157]
不完全情報ゲームにおける近似平衡の分散学習の複雑さについて検討する。
我々の下限は、$epsilon$-approximate $mathitco$ correlation equilibriumというより簡単な解の概念にも当てはまる。
論文 参考訳（メタデータ） (2024-06-04T14:35:27Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Adapting to game trees in zero-sum imperfect information games [41.4836057085788]
不完全な情報ゲーム(IIG)は、各プレイヤーが現在の遊技状態を部分的に観察するゲームである。
我々は,ゼロサムIIGにおいて,軌道フィードバックによる自己プレイを通じて,$epsilon$-optimal Strategyを学習する方法を研究する。
論文 参考訳（メタデータ） (2022-12-23T19:45:25Z) - Model-Based Reinforcement Learning for Offline Zero-Sum Markov Games [18.832436856339587]
本稿では,オフラインデータから2プレイヤーゼロサムマルコフゲームにおけるナッシュ均衡の学習に向けて前進する。
ベルンシュタイン型低信頼境界を持つ悲観的モデルベースアルゴリズム(VI-LCB-Game)を提案する。
論文 参考訳（メタデータ） (2022-06-08T17:58:06Z) - 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) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-22T05:00:13Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。