論文の概要: Adapting to game trees in zero-sum imperfect information games
- arxiv url: http://arxiv.org/abs/2212.12567v1
- Date: Fri, 23 Dec 2022 19:45:25 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-27 13:49:00.134622
- Title: Adapting to game trees in zero-sum imperfect information games
- Title（参考訳）: ゼロサム情報ゲームにおけるゲームツリーへの適応
- Authors: C\^ome Fiegel, Pierre M\'enard, Tadashi Kozuno, R\'emi Munos, Vianney
Perchet, Michal Valko
- Abstract要約: 不完全な情報ゲーム(IIG)は、各プレイヤーが現在の遊技状態を部分的に観察するゲームである。
我々は,ゼロサムIIGにおいて,軌道フィードバックによる自己プレイを通じて,$epsilon$-optimal Strategyを学習する方法を研究する。
- 参考スコア（独自算出の注目度）: 41.4836057085788
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Imperfect information games (IIG) are games in which each player only
partially observes the current game state. We study how to learn
$\epsilon$-optimal strategies in a zero-sum IIG through self-play with
trajectory feedback. We give a problem-independent lower bound
$\mathcal{O}(H(A_{\mathcal{X}}+B_{\mathcal{Y}})/\epsilon^2)$ on the required
number of realizations to learn these strategies with high probability, where
$H$ is the length of the game, $A_{\mathcal{X}}$ and $B_{\mathcal{Y}}$ are the
total number of actions for the two players. We also propose two Follow the
Regularize leader (FTRL) algorithms for this setting: Balanced-FTRL which
matches this lower bound, but requires the knowledge of the information set
structure beforehand to define the regularization; and Adaptive-FTRL which
needs $\mathcal{O}(H^2(A_{\mathcal{X}}+B_{\mathcal{Y}})/\epsilon^2)$ plays
without this requirement by progressively adapting the regularization to the
observations.
- Abstract（参考訳）: 不完全な情報ゲーム(IIG)は、各プレイヤーが現在の遊技状態を部分的に観察するゲームである。
我々は,軌道フィードバックを伴うセルフプレイによるゼロサムiigにおける$\epsilon$-optimal戦略の学習法について検討する。
問題に依存しない下界 $\mathcal{O}(H(A_{\mathcal{X}}+B_{\mathcal{Y}}))/\epsilon^2)$ をこれらの戦略を高い確率で学習するために必要な実現数に対して与え、$H$ はゲームの長さ、$A_{\mathcal{X}}$ と $B_{\mathcal{Y}}$ は2人のプレイヤーのアクションの総数である。
また、この設定のための正規化リーダー(ftrl)アルゴリズムを2つ提案する: この下限に一致するが、正規化を定義するために事前に情報集合構造の知識を必要とする balanced-ftrl と、観察に漸進的に正規化を適応させることで、この要件を満たさずにプレイする$\mathcal{o}(h^2(a_{\mathcal{x}}+b_{\mathcal{y}})/\epsilon^2)$ である。
関連論文リスト
- The complexity of approximate (coarse) correlated equilibrium for incomplete information games [16.96984593866157]
不完全情報ゲームにおける近似平衡の分散学習の複雑さについて検討する。
我々の下限は、$epsilon$-approximate $mathitco$ correlation equilibriumというより簡単な解の概念にも当てはまる。
論文 参考訳（メタデータ） (2024-06-04T14:35:27Z) - Can We Find Nash Equilibria at a Linear Rate in Markov Games? [95.10091348976779]
マルチプレイヤーゼロサム割引マルコフゲームにおける分散学習について検討した。
目標は、2つの特性を満たすエージェントのポリシー最適化アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2023-03-03T02:40:26Z) - Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a
Generative Model [50.38446482252857]
2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。
我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。
我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
論文 参考訳（メタデータ） (2022-08-22T17:24:55Z) - Model-Based Reinforcement Learning for Offline Zero-Sum Markov Games [18.832436856339587]
本稿では,オフラインデータから2プレイヤーゼロサムマルコフゲームにおけるナッシュ均衡の学習に向けて前進する。
ベルンシュタイン型低信頼境界を持つ悲観的モデルベースアルゴリズム(VI-LCB-Game)を提案する。
論文 参考訳（メタデータ） (2022-06-08T17: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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。