Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
复制标题
DOI：
--
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Bingyan Wang;Yuling Yan;Jianqing Fan
中科院分区：
文献类型：
--
作者：
Bingyan Wang;Yuling Yan;Jianqing Fan
维数灾难是强化学习（RL）中一个广为人知的问题。在状态空间S和动作空间A都是有限的表格设置中，为了获得具有对生成模型的采样访问的近似最优策略，最小最大最优样本复杂度与|S| × |一|，当S或A较大时，其可能大得令人望而却步。本文考虑一个马尔可夫决策过程（MDP），它允许一组状态-动作特征，它可以线性地表示（或近似）它的概率转移核。我们表明，一个基于模型的方法（分别。Q-学习）可证明地学习ε-最优策略（分别为当样本量超过K（1 - γ）3 ε 2（分别为K（1 - γ）4 ε 2），直到某个对数因子。这里K是特征维数，γ ∈（0，1）是MDP的折扣因子。这两个样本的复杂性界限是可证明的紧，我们的结果为基于模型的方法匹配的极大极小下限。我们的研究结果表明，对于任意大规模的MDP，当K相对较小时，基于模型的方法和Q学习都是样本有效的，因此本文的标题。
The curse of dimensionality is a widely known issue in reinforcement learning (RL). In the tabular setting where the state space S and the action space 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 | S | × | A | , which can be prohibitively large when S or 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 ε-optimal policy (resp. Q-function) with high probability as soon as the sample size exceeds the order of K ( 1 - γ ) 3 ε 2 ( resp . K ( 1 - γ ) 4 ε 2 ) , up to some logarithmic factor. Here K is the feature dimension and γ ∈ (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.