Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structure
Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structure
复制标题
DOI：
10.1145/3589973
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
Tyler Sam;Yudong Chen;C. Yu
中科院分区：
文献类型：
--
作者：
Tyler Sam;Yudong Chen;C. Yu
强化学习算法的实用性受到问题规模的限制，因为在具有状态空间S，动作空间A和水平H的MDP的最坏情况下，学习ε-最优策略的样本复杂性为Ω（|S||A|H/ ε2）。我们考虑一类MDP，其相关的最优Q*函数是低秩的，其中潜在特征是未知的。虽然由于低秩结构，人们希望在|S|和|A|中实现线性样本复杂度，但我们表明，在不施加超出低秩Q*的进一步假设的情况下，如果一个人被约束仅使用来自条目子集的观察值来估计Q函数，则存在最坏的情况，其中必须在视界H中产生样本复杂度指数以学习接近最优策略。我们随后证明，在更强的低秩结构假设下，给定生成模型，低秩蒙特卡罗策略迭代（LR-MCPI）和低秩经验值迭代（LR-EVI）在秩d设置下实现了所需的样本复杂度Õ((|S|+| a |)poly (d，H)/ε2)，相对于|S|， | a |和ε的尺度，这是最小最大最优的。与线性和低秩mdp的文献相比，我们不需要已知的特征映射，我们的算法计算简单，我们的结果适用于很长的时间范围。我们的结果提供了关于相对于转移核和最优动作值函数的MDP所需的最小低秩结构假设的见解。
The practicality of reinforcement learning algorithms has been limited due to poor scaling with respect to the problem size, as the sample complexity of learning an ε-optimal policy is Ω(|S||A|H/ ε2) over worst case instances of an MDP with state space S, action space A, and horizon H. We consider a class of MDPs for which the associated optimal Q* function is low rank, where the latent features are unknown. While one would hope to achieve linear sample complexity in |S| and |A| due to the low rank structure, we show that without imposing further assumptions beyond low rank of Q*, if one is constrained to estimate the Q function using only observations from a subset of entries, there is a worst case instance in which one must incur a sample complexity exponential in the horizon H to learn a near optimal policy. We subsequently show that under stronger low rank structural assumptions, given access to a generative model, Low Rank Monte Carlo Policy Iteration (LR-MCPI) and Low Rank Empirical Value Iteration (LR-EVI) achieve the desired sample complexity of Õ((|S|+|A|)poly (d,H)/ε2) for a rank d setting, which is minimax optimal with respect to the scaling of |S|, |A|, and ε. In contrast to literature on linear and low-rank MDPs, we do not require a known feature mapping, our algorithm is computationally simple, and our results hold for long time horizons. Our results provide insights on the minimal low-rank structural assumptions required on the MDP with respect to the transition kernel versus the optimal action-value function.