論文の概要: Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov
Games with Perfect Recall
- arxiv url: http://arxiv.org/abs/2106.06279v1
- Date: Fri, 11 Jun 2021 09:51:29 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-14 22:11:55.055063
- Title: Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov
Games with Perfect Recall
- Title（参考訳）: 完全リコール型ゼロサム部分可観測マルコフゲームのためのモデルフリー学習
- Authors: Tadashi Kozuno, Pierre M\'enard, R\'emi Munos, Michal Valko
- Abstract要約: 本研究では,不完全情報ゲーム(IIG)におけるナッシュ均衡(NE)学習の問題について,自己学習を通して検討する。
Inlicit Exploration Online Mirror Descent (IXOMD)アルゴリズムを提案する。
IXOMD は 1/sqrtT$ の NE への収束率に縛られる確率の高いモデルのないアルゴリズムである。
- 参考スコア（独自算出の注目度）: 34.73929457960903
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of learning a Nash equilibrium (NE) in an imperfect
information game (IIG) through self-play. Precisely, we focus on two-player,
zero-sum, episodic, tabular IIG under the perfect-recall assumption where the
only feedback is realizations of the game (bandit feedback). In particular, the
dynamic of the IIG is not known -- we can only access it by sampling or
interacting with a game simulator. For this learning setting, we provide the
Implicit Exploration Online Mirror Descent (IXOMD) algorithm. It is a
model-free algorithm with a high-probability bound on the convergence rate to
the NE of order $1/\sqrt{T}$ where $T$ is the number of played games. Moreover,
IXOMD is computationally efficient as it needs to perform the updates only
along the sampled trajectory.
- Abstract（参考訳）: 非完全情報ゲーム(iig)におけるnash平衡(ne)の学習問題を自己遊びを通して検討する。
正確には、2つのプレイヤー、ゼロサム、エピソディック、タブ状のIIGに焦点をあてる。
特にIIGのダイナミックさは知られていないが、ゲームシミュレーターをサンプリングしたり操作することでのみアクセスすることができる。
この学習環境において,Implicit Exploration Online Mirror Descent (IXOMD)アルゴリズムを提案する。
1/\sqrt{t}$(ただし$t$はプレイされたゲーム数)のneに収束率を限定したモデルフリーのアルゴリズムである。
さらに、IXOMDはサンプリングされた軌道に沿ってのみ更新を実行する必要があるため、計算的に効率的である。
関連論文リスト
- Learning to Control Unknown Strongly Monotone Games [16.327788209492805]
制御された係数をオンラインで調整し,線形制約を満たすためにゲームのNEをシフトする簡単なアルゴリズムを提案する。
我々は,2つの時間スケール近似に基づくアルゴリズムが,目的とする線形制約を満たすNEの集合に対する確率1との収束を保証することを証明した。
本稿では,NEにおけるグローバル2次コストの最適化と資源配分ゲームにおけるロードバランシングに,我々の手法を適用する方法を示す。
論文 参考訳（メタデータ） (2024-06-30T03:33:42Z) - Decentralized model-free reinforcement learning in stochastic games with
average-reward objective [1.9852463786440127]
本アルゴリズムは,次数$T3/4$のサブ線形高確率後悔と次数$T2/3$のサブ線形高確率後悔を実現する。
本アルゴリズムは,従来の手法に比べて計算量が少なく,メモリスペースも少ない。
論文 参考訳（メタデータ） (2023-01-13T15:59:53Z) - Policy Mirror Ascent for Efficient and Independent Learning in Mean
Field Games [35.86199604587823]
平均場ゲームは対称および匿名の$N$-playerゲームに対して近似的なナッシュ均衡を得るための理論的ツールとして使われてきた。
ポリシーミラーを実行する$N$エージェントは、$widetildemathcalO(varepsilon-2)$サンプル内で正規化ゲームのナッシュ平衡に収束することを示す。
論文 参考訳（メタデータ） (2022-12-29T20:25:18Z) - 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) - 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) - Towards General Function Approximation in Zero-Sum Markov Games [126.58493169301012]
本稿では,同時移動を伴う2プレーヤゼロサム有限ホライゾンマルコフゲームについて考察する。
分離された設定とコーディネートされた設定の両方の効率的なアルゴリズムが開発されている。
論文 参考訳（メタデータ） (2021-07-30T15:25:13Z) - 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) - Combining Deep Reinforcement Learning and Search for
Imperfect-Information Games [30.520629802135574]
本稿では,自己再生強化学習と探索のためのフレームワークであるReBeLを,ゼロサムゲームにおけるナッシュ均衡に確実に収束させる。
また、ReBeLは、従来のポーカーAIよりもはるかに少ないドメイン知識を使用しながら、制限なしのテキサスホールド'emポーカーのパフォーマンスを達成することを示す。
論文 参考訳（メタデータ） (2020-07-27T15:21:22Z) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-22T05:00:13Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。