論文の概要: Decentralized Cooperative Reinforcement Learning with Hierarchical
Information Structure
- arxiv url: http://arxiv.org/abs/2111.00781v1
- Date: Mon, 1 Nov 2021 09:18:07 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-02 18:01:33.369391
- Title: Decentralized Cooperative Reinforcement Learning with Hierarchical
Information Structure
- Title（参考訳）: 階層型情報構造を用いた分散協調強化学習
- Authors: Hsu Kao, Chen-Yu Wei, Vijay Subramanian
- Abstract要約: 本稿では,2エージェントマルチアームバンド (MABs) とマルコフ決定プロセス (MDPs) を,アプリケーションに生じる階層的情報構造を用いて検討する。
それぞれのステップにおいて、"リーダー"はまず彼女の行動を選択し、その後に"フォロワー"はリーダーの行動を観察して自分の行動を決定する。
MDP設定の場合、$widetildemathcalO(sqrtH7S2ABT)$ regret, where $H$ is the number of episode, $S$ is the number of states。
- 参考スコア（独自算出の注目度）: 14.919120396838208
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Multi-agent reinforcement learning (MARL) problems are challenging due to
information asymmetry. To overcome this challenge, existing methods often
require high level of coordination or communication between the agents. We
consider two-agent multi-armed bandits (MABs) and Markov decision processes
(MDPs) with a hierarchical information structure arising in applications, which
we exploit to propose simpler and more efficient algorithms that require no
coordination or communication. In the structure, in each step the ``leader"
chooses her action first, and then the ``follower" decides his action after
observing the leader's action. The two agents observe the same reward (and the
same state transition in the MDP setting) that depends on their joint action.
For the bandit setting, we propose a hierarchical bandit algorithm that
achieves a near-optimal gap-independent regret of
$\widetilde{\mathcal{O}}(\sqrt{ABT})$ and a near-optimal gap-dependent regret
of $\mathcal{O}(\log(T))$, where $A$ and $B$ are the numbers of actions of the
leader and the follower, respectively, and $T$ is the number of steps. We
further extend to the case of multiple followers and the case with a deep
hierarchy, where we both obtain near-optimal regret bounds. For the MDP
setting, we obtain $\widetilde{\mathcal{O}}(\sqrt{H^7S^2ABT})$ regret, where
$H$ is the number of steps per episode, $S$ is the number of states, $T$ is the
number of episodes. This matches the existing lower bound in terms of $A, B$,
and $T$.
- Abstract（参考訳）: 情報非対称性のため,マルチエージェント強化学習(MARL)の問題は困難である。
この課題を克服するために、既存の手法では高いレベルの調整やエージェント間のコミュニケーションを必要とすることが多い。
我々は、アプリケーションに生じる階層的な情報構造を持つ2エージェントマルチアームバンド(MAB)とマルコフ決定プロセス(MDP)について検討し、協調や通信を必要としないよりシンプルで効率的なアルゴリズムを提案する。
構造では、各ステップで ``leader" がまず彼女のアクションを選択し、その後 ``follower" がリーダーのアクションを観察した後、彼のアクションを決定する。
2つのエージェントは、共同アクションに依存する同じ報酬(およびmdp設定における同じ状態遷移)を観察します。
バンドイット設定には,$\widetilde{\mathcal{o}}(\sqrt{abt})$ と$\mathcal{o}(\log(t))$ の近似的ギャップ非依存的後悔と,$a$ と $b$ がそれぞれリーダーとフォロワーのアクション数であり,$t$ がステップ数であるような階層的バンドイットアルゴリズムを提案する。
我々はさらに,複数のフォロワと深い階層を持つケースにまで拡張し,それぞれが最適に近い後悔の限界を得る。
mdp の設定では、$\widetilde{\mathcal{o}}(\sqrt{h^7s^2abt})$ regret、ただし$h$ は1エピソードあたりのステップ数、$s$ はステート数、$t$ はエピソード数である。
これは、$A、B$、および$T$という観点で既存の下限と一致する。
関連論文リスト
- Cooperative Multi-Agent Reinforcement Learning: Asynchronous
Communication and Linear Function Approximation [77.09836892653176]
マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。
本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。
我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
論文 参考訳（メタデータ） (2023-05-10T20:29:29Z) - Adversarial Online Multi-Task Reinforcement Learning [12.421997449847153]
対戦型オンラインマルチタスク強化学習環境について考察する。
K$の各エピソードにおいて、学習者は未知のタスクをM$未知有限ホライゾン MDP モデルの有限集合から与えられる。
学習者の目的は,各課題に対する最適方針に関して,その後悔を一般化することである。
論文 参考訳（メタデータ） (2023-01-11T02:18:26Z) - Provably Efficient Model-free RL in Leader-Follower MDP with Linear
Function Approximation [1.370633147306388]
エピソードの各ステップにエージェント(リーダー)が作用し、次に別のエージェント(フォロワー)が作用するマルチエージェント・エピソードMDPについて考察する。
モデルフリーなRLアルゴリズムを提案し、$tildemathcalO(sqrtd3H3T)$ regret boundsをリーダとフォロワーの両方に対して実現可能であることを示す。
これは、機能近似を持つ非明視的フォロワーを持つマルコフゲームに対する、最初のサブ線形後悔の保証である。
論文 参考訳（メタデータ） (2022-11-28T21:59:58Z) - On the Sample Complexity of Representation Learning in Multi-task
Bandits with Global and Local structure [77.60508571062958]
マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。
アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。
サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
論文 参考訳（メタデータ） (2022-11-28T08:40:12Z) - Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。
我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。
技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文 参考訳（メタデータ） (2022-10-15T09:22:22Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳（メタデータ） (2022-10-05T22:52:00Z) - Horizon-Free Reinforcement Learning in Polynomial Time: the Power of
Stationary Policies [88.75843804630772]
我々は既存の境界に対して,$Oleft(mathrmpoly(S,A,log K)sqrtKright)を後悔するアルゴリズムを設計する。
この結果は、定常政策の近似力、安定性、および濃度特性を確立する新しい構造補題の列に依存している。
論文 参考訳（メタデータ） (2022-03-24T08:14:12Z) - Distributed Bandits with Heterogeneous Agents [38.90376765616447]
本稿では、M$エージェントが協力して$K$武器の盗賊問題を解くマルチエージェントの盗賊設定に取り組む。
本稿では,ucbo と AAE の2つの学習アルゴリズムを提案する。
Oleft(sum_i:tildeDelta_i>0 log T/tildeDelta_iright)$, $tildeDelta_i$は報酬平均の最小部分最適差である。
論文 参考訳（メタデータ） (2022-01-23T20:04:15Z) - Communication Efficient Parallel Reinforcement Learning [34.77250498401055]
我々は、$m$エージェントが$s$状態と$a$アクションを持つ$m$同一および独立環境と相互作用する問題を考える。
我々はエージェントが不適切なコミュニケーションラウンドで後悔を最小限に抑えるアルゴリズムを見つけることを目的としている。
論文 参考訳（メタデータ） (2021-02-22T02:46:36Z) - Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive
Multi-Step Bootstrap [84.66885506098724]
本稿では,アダプティブ・マルチステップ・ブートストラップ (AMB) を用いた表層有限水平マルコフ決定過程 (MDP) のモデルフリーアルゴリズムを提案する。
AMBは,部分最適ギャップの逆の和でのみスケールする,ギャップ依存的後悔境界を達成できることを示す。
また、AMB は $frac|Z_mul|Delta_min$ regret という追加の $frac|Z_mul|Delta_min$ を被っていることも示しています。
論文 参考訳（メタデータ） (2021-02-09T07:46:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。