論文の概要: Reward-Mixing MDPs with a Few Latent Contexts are Learnable
- arxiv url: http://arxiv.org/abs/2210.02594v1
- Date: Wed, 5 Oct 2022 22:52:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-07 16:01:08.129326
- Title: Reward-Mixing MDPs with a Few Latent Contexts are Learnable
- Title(参考訳): 遅延文脈の少ないリワードミキシングMDPを学習可能
- Authors: Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, Shie Mannor
- Abstract要約: 報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
- 参考スコア(独自算出の注目度): 75.17357040707347
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider episodic reinforcement learning in reward-mixing Markov decision
processes (RMMDPs): at the beginning of every episode nature randomly picks a
latent reward model among $M$ candidates and an agent interacts with the MDP
throughout the episode for $H$ time steps. Our goal is to learn a near-optimal
policy that nearly maximizes the $H$ time-step cumulative rewards in such a
model. Previous work established an upper bound for RMMDPs for $M=2$. In this
work, we resolve several open questions remained for the RMMDP model. For an
arbitrary $M\ge2$, we provide a sample-efficient
algorithm--$\texttt{EM}^2$--that outputs an $\epsilon$-optimal policy using
$\tilde{O} \left(\epsilon^{-2} \cdot S^d A^d \cdot \texttt{poly}(H, Z)^d
\right)$ episodes, where $S, A$ are the number of states and actions
respectively, $H$ is the time-horizon, $Z$ is the support size of reward
distributions and $d=\min(2M-1,H)$. Our technique is a higher-order extension
of the method-of-moments based approach, nevertheless, the design and analysis
of the \algname algorithm requires several new ideas beyond existing
techniques. We also provide a lower bound of $(SA)^{\Omega(\sqrt{M})} /
\epsilon^{2}$ for a general instance of RMMDP, supporting that super-polynomial
sample complexity in $M$ is necessary.
- Abstract(参考訳): 我々は、報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習を考察し、各エピソードの始めに、M$候補のうち潜在報酬モデルをランダムに選択し、エージェントはエピソード全体を通してMDPと対話し、時間ステップを$H$とする。
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する準最適政策を学ぶことである。
以前の研究では、RMMDPの上限が$M=2$であった。
本研究では,RMMDPモデルに対するいくつかのオープンな疑問を解決した。
任意の$m\ge2$に対して、サンプル効率の良いアルゴリズム--$\texttt{em}^2$-を提供し、$\tilde{o} \left(\epsilon^{-2} \cdot s^d a^d \cdot \texttt{poly}(h, z)^d \right)$ episodes を用いて$\epsilon$-optimalポリシーを出力する。
提案手法はモーメント法に基づく手法の高次拡張であるが, \algname アルゴリズムの設計と解析には,既存の手法を超越した新たなアイデアがいくつか必要である。
また、RMMDP の一般インスタンスに対して $(SA)^{\Omega(\sqrt{M})} / \epsilon^{2}$ という下界も提供し、M$ の超ポリノミカルサンプルの複雑さが必要とされることを裏付ける。
関連論文リスト
- Adversarial Online Multi-Task Reinforcement Learning [12.421997449847153]
対戦型オンラインマルチタスク強化学習環境について考察する。
K$の各エピソードにおいて、学習者は未知のタスクをM$未知有限ホライゾン MDP モデルの有限集合から与えられる。
学習者の目的は,各課題に対する最適方針に関して,その後悔を一般化することである。
論文 参考訳(メタデータ) (2023-01-11T02:18:26Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳(メタデータ) (2022-12-01T15:57:58Z) - 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-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) - On the Power of Multitask Representation Learning in Linear MDP [61.58929164172968]
本稿では,線形マルコフ決定過程(MDP)におけるマルチタスク表現学習の統計的メリットについて分析する。
簡単な最小二乗アルゴリズムが $tildeO(H2sqrtfrackappa MathcalC(Phi)2 kappa dNT+frackappa dn) というポリシーを学ぶことを証明した。
論文 参考訳(メタデータ) (2021-06-15T11:21:06Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳(メタデータ) (2020-06-06T13:34:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。