Low-Switching Policy Gradient with Exploration via Online Sensitivity Sampling
Low-Switching Policy Gradient with Exploration via Online Sensitivity Sampling
复制标题
DOI：
10.48550/arxiv.2306.09554
复制
发表时间：
2023-06
期刊：
影响因子：
--
通讯作者：
Yunfan Li-;Yiran Wang-;Y. Cheng;Lin F. Yang
中科院分区：
文献类型：
--
作者：
Yunfan Li-;Yiran Wang-;Y. Cheng;Lin F. Yang
策略优化方法是强化学习（RL）中功能强大的算法，因为它们能够灵活地处理策略参数化和处理模型错误指定的能力。然而，这些方法通常具有收敛速度慢和样本复杂度低的缺点。因此，重要的是设计可证明的样本有效的策略优化算法。然而，这个问题的最新进展只在表格和线性设置中取得了成功，其良性结构不能推广到非线性参数化政策。在本文中，我们解决这个问题，利用最新进展的价值为基础的算法，包括有界逃避维度和在线灵敏度采样，设计一个低切换样本效率的策略优化算法，LPO，一般非线性函数逼近。我们证明了，我们的算法只需要$\widetilde{O}（\frac{\text{poly}（d）}{\varepsilon^3}）$个样本就能得到$\varepsilon$-最优策略，其中$\varepsilon$是次优间隙，$d$是逼近策略的函数类的复杂性度量.这极大地改进了以前最著名的策略优化算法的样本边界，$\widetilde{O}（\frac{\text{poly}（d）}{\varepsilon^8}）$。此外，我们用深度神经网络对我们的理论进行了实证测试，以显示理论灵感的好处。
Policy optimization methods are powerful algorithms in Reinforcement Learning (RL) for their flexibility to deal with policy parameterization and ability to handle model misspecification. However, these methods usually suffer from slow convergence rates and poor sample complexity. Hence it is important to design provably sample efficient algorithms for policy optimization. Yet, recent advances for this problems have only been successful in tabular and linear setting, whose benign structures cannot be generalized to non-linearly parameterized policies. In this paper, we address this problem by leveraging recent advances in value-based algorithms, including bounded eluder-dimension and online sensitivity sampling, to design a low-switching sample-efficient policy optimization algorithm, LPO, with general non-linear function approximation. We show that, our algorithm obtains an $\varepsilon$-optimal policy with only $\widetilde{O}(\frac{\text{poly}(d)}{\varepsilon^3})$ samples, where $\varepsilon$ is the suboptimality gap and $d$ is a complexity measure of the function class approximating the policy. This drastically improves previously best-known sample bound for policy optimization algorithms, $\widetilde{O}(\frac{\text{poly}(d)}{\varepsilon^8})$. Moreover, we empirically test our theory with deep neural nets to show the benefits of the theoretical inspiration.