論文の概要: Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret
Learning in Markov Games
- arxiv url: http://arxiv.org/abs/2206.01588v1
- Date: Fri, 3 Jun 2022 14:18:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-06 18:40:30.749467
- Title: Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret
Learning in Markov Games
- Title（参考訳）: 偏集中型楽観的超ポリシーミラー降下:マルコフゲームにおける証明可能非回帰学習
- Authors: Wenhao Zhan, Jason D. Lee, Zhuoran Yang
- Abstract要約: 我々はマルコフゲームにおいて、非定常的でおそらく敵対的な相手と遊べる単一のエージェントを制御する分散ポリシー学習について研究する。
我々は、新しいアルゴリズム、アンダーラインデ集中型アンダーラインハイプラインRpolicy munderlineIrror deunderlineScent (DORIS)を提案する。
DORISは、一般的な関数近似の文脈で$sqrtK$-regretを達成する。
- 参考スコア（独自算出の注目度）: 95.10091348976779
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: We study decentralized policy learning in Markov games where we control a
single agent to play with nonstationary and possibly adversarial opponents. Our
goal is to develop a no-regret online learning algorithm that (i) takes actions
based on the local information observed by the agent and (ii) is able to find
the best policy in hindsight. For such a problem, the nonstationary state
transitions due to the varying opponent pose a significant challenge. In light
of a recent hardness result \citep{liu2022learning}, we focus on the setting
where the opponent's previous policies are revealed to the agent for decision
making. With such an information structure, we propose a new algorithm,
\underline{D}ecentralized \underline{O}ptimistic hype\underline{R}policy
m\underline{I}rror de\underline{S}cent (DORIS), which achieves
$\sqrt{K}$-regret in the context of general function approximation, where $K$
is the number of episodes. Moreover, when all the agents adopt DORIS, we prove
that their mixture policy constitutes an approximate coarse correlated
equilibrium. In particular, DORIS maintains a \textit{hyperpolicy} which is a
distribution over the policy space. The hyperpolicy is updated via mirror
descent, where the update direction is obtained by an optimistic variant of
least-squares policy evaluation. Furthermore, to illustrate the power of our
method, we apply DORIS to constrained and vector-valued MDPs, which can be
formulated as zero-sum Markov games with a fictitious opponent.
- Abstract（参考訳）: 我々はマルコフゲームにおいて、非定常的でおそらく敵対的な相手と遊ぶために単一のエージェントを制御する分散ポリシー学習を研究する。
私たちのゴールは、未学習のオンライン学習アルゴリズムを開発することです。
(i)代理人が観察した地域情報に基づいて行動をとる
(二)後見の最良の政策を見つけることができる。
このような問題に対して、異なる相手による非定常状態遷移は大きな課題となる。
近年の難易度結果である「citep{liu2022learning}」を踏まえ, 意思決定エージェントに対して, 相手の以前の方針を明らかにする設定に焦点を当てた。
このような情報構造を用いて,一般関数近似の文脈で$\sqrt{K}$-regretを達成する新しいアルゴリズム, \underline{D}ecentralized \underline{O}ptimistic hype\underline{R}policy m\underline{I}rror de\underline{S}cent (DORIS)を提案する。
さらに、全てのエージェントがDORISを採用すると、それらの混合ポリシーが近似粗相関平衡を構成することが証明される。
特に、DORISは政策空間上の分布である「textit{hyperpolicy}」を維持している。
ハイパーポリシーはミラー降下により更新され、更新方向は最小二乗政策評価の楽観的な変種によって得られる。
さらに,本手法のパワーを説明するために,制約付きおよびベクトル値のMDPにDORISを適用し,虚偽の相手を持つゼロサムマルコフゲームとして定式化することができる。
関連論文リスト
- When is Agnostic Reinforcement Learning Statistically Tractable? [76.1408672715773]
エンフスパンニング容量と呼ばれる新しい複雑性測度は、設定された$Pi$にのみ依存し、MDPダイナミクスとは独立である。
我々は、学習するためにスーパーポリノミカルな数のサンプルを必要とする制限付きスパンリング能力を持つポリシークラス$Pi$が存在することを示した。
これにより、生成的アクセスとオンラインアクセスモデルの間の学習可能性の驚くほどの分離が明らかになる。
論文 参考訳（メタデータ） (2023-10-09T19:40:54Z) - Learning Diverse Risk Preferences in Population-based Self-play [23.07952140353786]
現在のセルフプレイアルゴリズムはエージェントを最適化し、現在のコピーや歴史的なコピーに対して期待される勝利率を最大化する。
我々は,不確実性に直面したエージェントが多様なリスク嗜好を持つという観点から,多様性を導入する。
本手法は,競技ゲームにおいて,同等あるいは優れた性能を達成可能であることを示す。
論文 参考訳（メタデータ） (2023-05-19T06:56:02Z) - Decentralized model-free reinforcement learning in stochastic games with
average-reward objective [1.9852463786440127]
本アルゴリズムは,次数$T3/4$のサブ線形高確率後悔と次数$T2/3$のサブ線形高確率後悔を実現する。
本アルゴリズムは,従来の手法に比べて計算量が少なく,メモリスペースも少ない。
論文 参考訳（メタデータ） (2023-01-13T15:59:53Z) - Autoregressive Bandits [58.46584210388307]
本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。
報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。
次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
論文 参考訳（メタデータ） (2022-12-12T21:37:36Z) - Provably Efficient Fictitious Play Policy Optimization for Zero-Sum
Markov Games with Structured Transitions [145.54544979467872]
本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。
我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。
提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
論文 参考訳（メタデータ） (2022-07-25T18:29:16Z) - Byzantine-Robust Online and Offline Distributed Reinforcement Learning [60.970950468309056]
本稿では,複数のエージェントが環境を探索し,その経験を中央サーバを通じて伝達する分散強化学習環境について考察する。
エージェントの$alpha$-fractionは敵対的であり、任意の偽情報を報告することができる。
我々は、これらの対立エージェントの存在下で、マルコフ決定プロセスの根底にある準最適政策を特定することを模索する。
論文 参考訳（メタデータ） (2022-06-01T00:44:53Z) - Decentralized Multi-Agent Reinforcement Learning: An Off-Policy Method [6.261762915564555]
本稿では,分散型マルチエージェント強化学習(MARL)の問題について議論する。
我々の設定では、グローバルステート、アクション、報酬は、完全に監視可能であると仮定され、一方、ローカルポリシーは各エージェントによってプライバシとして保護されているため、他の人と共有することはできない。
政策評価と政策改善のアルゴリズムはそれぞれ、離散的かつ連続的な状態-行動空間マルコフ決定プロセス(MDP)のために設計されている。
論文 参考訳（メタデータ） (2021-10-31T09:08:46Z) - Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。
各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。
我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
論文 参考訳（メタデータ） (2021-01-31T16:49:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。