論文の概要: Provably Efficient Model-free RL in Leader-Follower MDP with Linear
Function Approximation
- arxiv url: http://arxiv.org/abs/2211.15792v1
- Date: Mon, 28 Nov 2022 21:59:58 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-30 18:16:39.388236
- Title: Provably Efficient Model-free RL in Leader-Follower MDP with Linear
Function Approximation
- Title（参考訳）: 線形関数近似を用いたリーダフォロワーMDPにおけるモデルフリーRLの確率論的評価
- Authors: Arnob Ghosh
- Abstract要約: エピソードの各ステップにエージェント(リーダー)が作用し、次に別のエージェント(フォロワー)が作用するマルチエージェント・エピソードMDPについて考察する。
モデルフリーなRLアルゴリズムを提案し、$tildemathcalO(sqrtd3H3T)$ regret boundsをリーダとフォロワーの両方に対して実現可能であることを示す。
これは、機能近似を持つ非明視的フォロワーを持つマルコフゲームに対する、最初のサブ線形後悔の保証である。
- 参考スコア（独自算出の注目度）: 1.370633147306388
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We consider a multi-agent episodic MDP setup where an agent (leader) takes
action at each step of the episode followed by another agent (follower). The
state evolution and rewards depend on the joint action pair of the leader and
the follower. Such type of interactions can find applications in many domains
such as smart grids, mechanism design, security, and policymaking. We are
interested in how to learn policies for both the players with provable
performance guarantee under a bandit feedback setting. We focus on a setup
where both the leader and followers are {\em non-myopic}, i.e., they both seek
to maximize their rewards over the entire episode and consider a linear MDP
which can model continuous state-space which is very common in many RL
applications. We propose a {\em model-free} RL algorithm and show that
$\tilde{\mathcal{O}}(\sqrt{d^3H^3T})$ regret bounds can be achieved for both
the leader and the follower, where $d$ is the dimension of the feature mapping,
$H$ is the length of the episode, and $T$ is the total number of steps under
the bandit feedback information setup. Thus, our result holds even when the
number of states becomes infinite. The algorithm relies on {\em novel}
adaptation of the LSVI-UCB algorithm. Specifically, we replace the standard
greedy policy (as the best response) with the soft-max policy for both the
leader and the follower. This turns out to be key in establishing uniform
concentration bound for the value functions. To the best of our knowledge, this
is the first sub-linear regret bound guarantee for the Markov games with
non-myopic followers with function approximation.
- Abstract（参考訳）: エピソードの各ステップでエージェント(リーダー)が行動し、次に別のエージェント(フォロワー)が続くマルチエージェント・エピソードMDPのセットアップを考える。
状態の進化と報酬は、リーダーと従者の合同行動ペアに依存する。
このようなインタラクションは、スマートグリッド、メカニズム設計、セキュリティ、ポリシー作成など、多くの分野のアプリケーションを見つけることができる。
ビジットフィードバック設定の下で、証明可能なパフォーマンス保証を持つプレイヤーの両方のポリシーを学ぶ方法に興味があります。
我々は,リーダとフォロワーの両方が非ミオピック(非ミオピック)である,すなわち,エピソード全体を通じて報酬を最大化し,多くのRLアプリケーションで非常に一般的な連続的な状態空間をモデル化可能な線形MDPを検討する,という設定に焦点を当てる。
我々は、"em model-free" rlアルゴリズムを提案し、$\tilde{\mathcal{o}}(\sqrt{d^3h^3t})$ regret boundsがリーダーとフォロワーの両方に対して達成できることを示し、ここで$d$は特徴マッピングの次元、$h$はエピソードの長さ、$t$はバンディットフィードバック情報の設定下のステップの総数であることを示した。
したがって、状態の数が無限になった場合でも結果が成り立つ。
このアルゴリズムはLSVI-UCBアルゴリズムの適応に依存している。
具体的には、標準の欲求政策を(最高の反応として)リーダーとフォロワーの両方にとってのソフトマックス政策に置き換えます。
これは値関数に対して一様濃度境界を確立する上で鍵となる。
我々の知る限りでは、これは関数近似を持つ非ミオピックフォロワを持つマルコフゲームに対する最初の半線形後悔の限度保証である。
関連論文リスト
- Provably Efficient Generalized Lagrangian Policy Optimization for Safe
Multi-Agent Reinforcement Learning [105.7510838453122]
制約付きマルコフゲームを用いたオンライン安全なマルチエージェント強化学習について検討する。
我々は,このラグランジアン問題を解くための高信頼強化学習アルゴリズムを開発した。
提案アルゴリズムは,オンラインミラー降下によるミニマックス決定主元変数と,投影勾配ステップによる双対変数を更新する。
論文 参考訳（メタデータ） (2023-05-31T22:09:24Z) - Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with
General Utilities [12.104551746465932]
安全マルチエージェント強化学習について検討し、エージェントはそれぞれの安全制約を満たしつつ、局所的な目的の総和をまとめて最大化しようとする。
我々のアルゴリズムは、$mathcalOleft(T-2/3right)$のレートで1次定常点(FOSP)に収束する。
サンプルベースの設定では、高い確率で、我々のアルゴリズムは、$epsilon$-FOSPを達成するために$widetildemathcalOleft(epsilon-3.5right)$サンプルが必要です。
論文 参考訳（メタデータ） (2023-05-27T20:08:35Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳（メタデータ） (2022-10-05T22:52:00Z) - 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) - Provably Efficient Offline Reinforcement Learning with Trajectory-Wise
Reward [66.81579829897392]
我々はPessimistic vAlue iteRaTionとrEward Decomposition (PARTED)という新しいオフライン強化学習アルゴリズムを提案する。
PartEDは、最小2乗ベースの報酬再分配を通じて、ステップごとのプロキシ報酬に軌道を分解し、学習したプロキシ報酬に基づいて悲観的な値を実行する。
私たちの知る限りでは、PartEDは、トラジェクティブな報酬を持つ一般のMDPにおいて、証明可能な効率のよい最初のオフラインRLアルゴリズムである。
論文 参考訳（メタデータ） (2022-06-13T19:11:22Z) - Collaborative Multi-agent Stochastic Linear Bandits [28.268809091816287]
我々は,ネットワークを構成するN$エージェントが局所的に通信し,全体的な後悔を最小限に抑える,協調的マルチエージェント線形帯域設定について検討する。
すべてのエージェントは、プレイされたアクションの対応する報酬を観察し、加速されたコンセンサス手順を使用して、すべてのエージェントが取得した報酬の平均の見積もりを計算する。
論文 参考訳（メタデータ） (2022-05-12T19:46:35Z) - Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
我々は、次元が$d$で、それぞれ$T$のラウンドで$M$リニアバンディットをプレイする設定を考え、これらの$M$リニアバンディットタスクは共通の$k(ll d)$次元リニア表現を共有する。
我々は$widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret boundsを達成する新しいアルゴリズムを考案した。
論文 参考訳（メタデータ） (2022-03-29T15:27:13Z) - Decentralized Cooperative Reinforcement Learning with Hierarchical
Information Structure [14.919120396838208]
本稿では,2エージェントマルチアームバンド (MABs) とマルコフ決定プロセス (MDPs) を,アプリケーションに生じる階層的情報構造を用いて検討する。
それぞれのステップにおいて、"リーダー"はまず彼女の行動を選択し、その後に"フォロワー"はリーダーの行動を観察して自分の行動を決定する。
MDP設定の場合、$widetildemathcalO(sqrtH7S2ABT)$ regret, where $H$ is the number of episode, $S$ is the number of states。
論文 参考訳（メタデータ） (2021-11-01T09:18:07Z) - Reward-Free Model-Based Reinforcement Learning with Linear Function
Approximation [92.99933928528797]
エピソードマルコフ決定過程(MDP)に対する線形関数近似を用いたモデルに基づく無報酬強化学習について検討する。
計画段階では、特定の報酬関数が与えられ、探索フェーズから収集したサンプルを使用して良い政策を学ぶ。
任意の報酬関数に対して$epsilon$-optimal Policyを得るには,最大$tilde O(H4d(H + d)epsilon-2)$ episodesをサンプリングする必要がある。
論文 参考訳（メタデータ） (2021-10-12T23:03:58Z) - Near-optimal Representation Learning for Linear Bandits and Linear RL [41.33483293243257]
私たちはまず、次元が$d$の線形バンディットを同時に$M$で演奏する設定を考えます。
これらの包帯は、$k$-次元線型表現を共有するので、$kll d$ と $k ll M$ が成り立つ。
我々は、共有表現を利用して$tildeO(MsqrtdkT + dsqrtkMT )を後悔するサンプル効率のアルゴリズムMTLR-OFULを提案する。
論文 参考訳（メタデータ） (2021-02-08T11:11:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。