論文の概要: Provably Efficient Reinforcement Learning for Discounted MDPs with
Feature Mapping
- arxiv url: http://arxiv.org/abs/2006.13165v4
- Date: Mon, 22 Feb 2021 23:10:12 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-17 21:34:20.947376
- Title: Provably Efficient Reinforcement Learning for Discounted MDPs with
Feature Mapping
- Title（参考訳）: 特徴マッピングを用いた割引mdpの効率的強化学習
- Authors: Dongruo Zhou and Jiafan He and Quanquan Gu
- Abstract要約: 本稿では,割引決定(MDP)のための強化学習について検討する。
本稿では,特徴写像を利用した新しいアルゴリズムを提案し,$tilde O(dsqrtT/ (1-gamma)2)$ regretを求める。
以上の結果から,提案した強化学習アルゴリズムは,最大1-γ-0.5$の係数でほぼ最適であることが示唆された。
- 参考スコア（独自算出の注目度）: 99.59319332864129
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Modern tasks in reinforcement learning have large state and action spaces. To
deal with them efficiently, one often uses predefined feature mapping to
represent states and actions in a low-dimensional space. In this paper, we
study reinforcement learning for discounted Markov Decision Processes (MDPs),
where the transition kernel can be parameterized as a linear function of
certain feature mapping. We propose a novel algorithm that makes use of the
feature mapping and obtains a $\tilde O(d\sqrt{T}/(1-\gamma)^2)$ regret, where
$d$ is the dimension of the feature space, $T$ is the time horizon and $\gamma$
is the discount factor of the MDP. To the best of our knowledge, this is the
first polynomial regret bound without accessing the generative model or making
strong assumptions such as ergodicity of the MDP. By constructing a special
class of MDPs, we also show that for any algorithms, the regret is lower
bounded by $\Omega(d\sqrt{T}/(1-\gamma)^{1.5})$. Our upper and lower bound
results together suggest that the proposed reinforcement learning algorithm is
near-optimal up to a $(1-\gamma)^{-0.5}$ factor.
- Abstract（参考訳）: 強化学習における現代のタスクには、大きな状態と行動空間がある。
それらを効率的に扱うために、しばしば事前に定義された特徴マッピングを使用して、低次元空間における状態や動作を表現する。
本稿では,特定の特徴写像の線形関数として遷移核をパラメータ化できる割引マルコフ決定過程(mdps)に対する強化学習について検討する。
本稿では,特徴空間の次元が$d$,時間軸が$T$,MDPの割引係数が$\gamma$となるような,特徴写像を利用した新しいアルゴリズムを提案し,その特徴空間の次元が$\tilde O(d\sqrt{T}/(1-\gamma)^2)$ regretを求める。
我々の知る限りでは、これは生成モデルにアクセスしたり、MDPのエルゴード性のような強い仮定をしない最初の多項式後悔である。
MDP の特殊クラスを構築することにより、任意のアルゴリズムに対して、後悔は$\Omega(d\sqrt{T}/(1-\gamma)^{1.5})$で下限となることを示す。
以上の結果から,提案した強化学習アルゴリズムは最大1-\gamma)^{-0.5}$係数がほぼ最適であることが示唆された。
関連論文リスト
- Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation [1.8416014644193066]
ベルマン最適条件下で線形マルコフ決定過程(MDP)と線形混合MDPを学習するアルゴリズムを提案する。
線形MDPに対する我々のアルゴリズムは、$widetildemathcalO(d3/2mathrmsp(v*)sqrtT)$ over $T$タイムステップの最もよく知られた後悔の上限を達成する。
線形混合 MDP に対して、我々のアルゴリズムは、$widetildemathcalO(dcdotmathrm) の後悔境界に達する。
論文 参考訳（メタデータ） (2024-09-16T23:13:42Z) - Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximation [3.2703356989962518]
非線型関数近似を用いたモデルに基づく強化学習について検討する。
本研究では,無限水平平均逆法と割引逆法の両方に有効である確率効率のよい値反復型アルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-06-19T15:29:14Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Learning Adversarial Low-rank Markov Decision Processes with Unknown
Transition and Full-information Feedback [30.23951525723659]
本研究は,全情報フィードバック設定において,逆向きに損失が変化する低ランクMDPについて検討する。
政策最適化に基づくアルゴリズムPOLOを提案し、$widetildeO(Kfrac56Afrac12dln (1+M)/ (1-gamma)2)$ regret guarantee。
論文 参考訳（メタデータ） (2023-11-14T03:12:43Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function
Approximation [92.3161051419884]
我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。
我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。
また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
論文 参考訳（メタデータ） (2021-02-17T18:54:08Z) - Nearly Minimax Optimal Regret for Learning Infinite-horizon
Average-reward MDPs with Linear Function Approximation [95.80683238546499]
本論文では, 線形関数近似を用いた UCRL2 アルゴリズムの拡張として見ることのできる新しいアルゴリズム UCRL2-VTR を提案する。
Bernstein 型ボーナス付き UCRL2-VTR は $tildeO(dsqrtDT)$ の後悔を達成でき、$d$ は特徴写像の次元である。
また、一致した下界$tildeOmega(dsqrtDT)$を証明し、提案したUCRL2-VTRが対数係数の最小値であることを示す。
論文 参考訳（メタデータ） (2021-02-15T02:08:39Z) - Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs [99.59319332864129]
UCBVI-$gamma$が$tildeObig(sqrtSAT/ (1-gamma)1.5big)$ regret, where $S$ is the number of state, $A$ is the number of action, $gamma$ is the discount factor, $T$ is the number of steps。
さらに、ハードMDPのクラスを構築し、任意のアルゴリズムに対して、期待される後悔は少なくとも$tildeOmegabig(sqrtSAT/)であることを示す。
論文 参考訳（メタデータ） (2020-10-01T17:57:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。