論文の概要: 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}$係数がほぼ最適であることが示唆された。
関連論文リスト
- 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) - A Doubly Robust Approach to Sparse Reinforcement Learning [19.68978899041642]
エピソードスパークリニアマルコフ決定過程(SMDP)に対する新しい後悔アルゴリズムを提案する。
提案アルゴリズムは$tildeO(sigma-1_min s_star H sqrtN)$である。
論文 参考訳(メタデータ) (2023-10-23T18:52:17Z) - Exploring and Learning in Sparse Linear MDPs without Computationally
Intractable Oracles [39.10180309328293]
本稿では,特徴選択の観点から線形MDPを再考する。
我々の主な成果は、この問題に対する最初のアルゴリズムである。
コンベックスプログラミングによって効率よく計算できることを示す。
論文 参考訳(メタデータ) (2023-09-18T03:35:48Z) - 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) - Logarithmic Regret for Reinforcement Learning with Linear Function
Approximation [99.59319332864129]
最近提案された2つの線形MDP仮定で対数的後悔が達成可能であることを示す。
我々の知る限り、これらは線型関数近似を持つRLに対する最初の対数的後悔境界である。
論文 参考訳(メタデータ) (2020-11-23T17:25:00Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。