Computational-Statistical Gap in Reinforcement Learning
Computational-Statistical Gap in Reinforcement Learning
复制标题
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Daniel Kane;Sihan Liu;Shachar Lovett;G. Mahajan
中科院分区：
文献类型：
--
作者：
Daniel Kane;Sihan Liu;Shachar Lovett;G. Mahajan
用功能近似的增强学习在具有较大状态的空间的应用中取得了巨大的结果，这促使人们越来越多的理论工作提出了必要的和舒适的条件，从而可以从这种工作中进行效率的增强学习。为了有效的增强学习：MDP的最小舒适条件已出现最小的条件在某些已知的低维特征中，函数V ∗和Q ∗。计算有效的算法是将来的工作，这在社区中被认为是一个主要的开放问题。带有线性函数近似RL的计算下限：除非NP = RP，否则不存在用于确定具有恒定动作数量和线性最佳值函数的过渡MDP的随机多项式算法。 AT，我们将CNF公式转换为具有确定性转换的MDP，恒定的动作数量和低维线性最佳值函数也是如此通过线性函数近似，在增强学习中表现出第一个计算统计的差距，因为基本的统计问题是可以用多项式查询的信息来解决的，但是除非np = rp，否则在notally nocationally nocy np np = rp。 - 在随机指数时间假设下的多个单位时间下限。
Reinforcement learning with function approximation has recently achieved tremendous results in applications with large state spaces. This empirical success has motivated a growing body of theoretical work proposing necessary and sufficient conditions under which efficient reinforcement learning is possible. From this line of work, a remarkably simple minimal sufficient condition has emerged for sample efficient reinforcement learning: MDPs with optimal value function V ∗ and Q ∗ linear in some known low-dimensional features. In this setting, recent works have designed sample efficient algorithms which require a number of samples polynomial in the feature dimension and independent of the size of state space. They however leave finding computationally efficient algorithms as future work and this is considered a major open problem in the community. In this work, we make progress on this open problem by presenting the first computational lower bound for RL with linear function approximation: unless NP=RP, no randomized polynomial time algorithm exists for deterministic transition MDPs with a constant number of actions and linear optimal value functions. To prove this, we show a reduction from U NIQUE -S AT , where we convert a CNF formula into an MDP with deterministic transitions, constant number of actions and low dimensional linear optimal value functions. This result also exhibits the first computational-statistical gap in reinforcement learning with linear function approximation, as the underlying statistical problem is information-theoretically solvable with a polynomial number of queries, but no computationally efficient algorithm exists unless NP=RP. Finally, we also prove a quasi-polynomial time lower bound under the Randomized Exponential Time Hypothesis.