論文の概要: Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs
with a Generative Model
- arxiv url: http://arxiv.org/abs/2105.14016v1
- Date: Fri, 28 May 2021 17:49:39 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-31 13:43:24.904063
- Title: Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs
with a Generative Model
- Title（参考訳）: 生成モデルを用いた線形パラメータmdpのサンプル効率強化学習
- Authors: Bingyan Wang, Yuling Yan, Jianqing Fan
- Abstract要約: 本稿では,一連の状態対応機能を有するマルコフ決定プロセス(MDP)について考察する。
モデルに基づくアプローチ(resp.$Q-learning)が、高い確率で$varepsilon$-Optimalポリシーを確実に学習することを示す。
- 参考スコア（独自算出の注目度）: 3.749193647980305
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The curse of dimensionality is a widely known issue in reinforcement learning
(RL). In the tabular setting where the state space $\mathcal{S}$ and the action
space $\mathcal{A}$ are both finite, to obtain a nearly optimal policy with
sampling access to a generative model, the minimax optimal sample complexity
scales linearly with $|\mathcal{S}|\times|\mathcal{A}|$, which can be
prohibitively large when $\mathcal{S}$ or $\mathcal{A}$ is large. This paper
considers a Markov decision process (MDP) that admits a set of state-action
features, which can linearly express (or approximate) its probability
transition kernel. We show that a model-based approach (resp.$~$Q-learning)
provably learns an $\varepsilon$-optimal policy (resp.$~$Q-function) with high
probability as soon as the sample size exceeds the order of
$\frac{K}{(1-\gamma)^{3}\varepsilon^{2}}$
(resp.$~$$\frac{K}{(1-\gamma)^{4}\varepsilon^{2}}$), up to some logarithmic
factor. Here $K$ is the feature dimension and $\gamma\in(0,1)$ is the discount
factor of the MDP. Both sample complexity bounds are provably tight, and our
result for the model-based approach matches the minimax lower bound. Our
results show that for arbitrarily large-scale MDP, both the model-based
approach and Q-learning are sample-efficient when $K$ is relatively small, and
hence the title of this paper.
- Abstract（参考訳）: 次元性の呪いは強化学習(RL)において広く知られている問題である。
状態空間 $\mathcal{s}$ と作用空間 $\mathcal{a}$ がともに有限であるような表設定において、生成モデルへのアクセスをサンプリングしてほぼ最適なポリシーを得るため、ミニマックス最適標本複雑性は$|\mathcal{s}|\times|\mathcal{a}|$ と線形にスケールする。
本稿では,その確率遷移カーネルを線形に(あるいは近似的に)表現できる,一連の状態-作用特徴を持つマルコフ決定プロセス(MDP)について考察する。
モデルに基づくアプローチ(resp.$~$Q-learning)は、サンプルサイズが$\frac{K}{(1-\gamma)^{3}\varepsilon^{2}}$(resp.$~$\frac{K}{(1-\gamma)^{4}\varepsilon^{2}}$(resp.$~$\frac{K}{(1-\gamma)^{4}\varepsilon^{2}}$)を超えると、高い確率で$\varepsilon$-optimal Policy(resp.$~$Q-function)を確実に学習することを示す。
ここで$K$は特徴次元、$\gamma\in(0,1)$はMDPの割引係数である。
どちらのサンプルの複雑性境界も明らかに厳密であり、モデルに基づくアプローチの結果はミニマックス下界と一致する。
この結果から, モデルベースアプローチとQラーニングは, 比較的K$が小さい場合のサンプル効率が向上し, 本論文の題名となった。
関連論文リスト
- 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) - Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs [6.996002801232415]
平均回帰マルコフ決定過程(MDP)において,$varepsilon$-optimal Policyを生成モデルで学習する際のサンプル複雑性について検討した。
MDP を弱通信するためには、$widetildeO(SAfracHvarepsilon2 )$, $H$ は最適ポリシーのバイアス関数のスパンであり、$SA$ は状態作用空間の濃度である。
論文 参考訳（メタデータ） (2024-03-18T04:52:11Z) - Sharper Model-free Reinforcement Learning for Average-reward Markov
Decision Processes [21.77276136591518]
我々はマルコフ決定過程(MDPs)のための証明可能なモデルフリー強化学習(RL)アルゴリズムを開発した。
シミュレータ設定では,$widetildeO left(fracSAmathrmsp(h*)epsilon2+fracS2Amathrmsp(h*)epsilon2right)$サンプルを用いて,$epsilon$-optimal Policyを求める。
論文 参考訳（メタデータ） (2023-06-28T17:43:19Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Settling the Sample Complexity of Model-Based Offline Reinforcement
Learning [50.5790774201146]
オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。
事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。
モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
論文 参考訳（メタデータ） (2022-04-11T17:26:19Z) - Convergence of Sparse Variational Inference in Gaussian Processes
Regression [29.636483122130027]
計算コストが$mathcalO(log N)2D(log N)2)$の手法を推論に利用できることを示す。
論文 参考訳（メタデータ） (2020-08-01T19:23:34Z) - 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) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。