Provably Efficient Algorithm for Nonstationary Low-Rank MDPs
Provably Efficient Algorithm for Nonstationary Low-Rank MDPs
复制标题
DOI：
10.48550/arxiv.2308.05471
复制
发表时间：
2023-08
期刊：
影响因子：
--
通讯作者：
Yuan Cheng;J. Yang;Yitao Liang
中科院分区：
文献类型：
--
作者：
Yuan Cheng;J. Yang;Yitao Liang
变化环境下的强化学习（RL）通过非平稳马尔可夫决策过程（MDP）对许多现实世界的应用进行建模，因此受到了广泛的关注。然而，文献中对非平稳MDP的理论研究主要集中在表格和线性（混合）MDP上，这些MDP没有捕捉到深度RL中未知表示的本质。在本文中，我们第一次尝试研究非平稳RL下的情节低秩MDP，其中的过渡内核和奖励可能会随着时间的推移而变化，低秩模型包含未知的表示除了线性状态嵌入函数。我们首先提出了一个参数依赖的策略优化算法PORTAL，并进一步改进PORTAL的Ada-PORTAL，它能够自适应地调整其超参数，而无需任何先验知识的非平稳性的无参数版本。对于这两种算法，我们提供了上界的平均动态次优间隙，这表明，只要非平稳性不是显着大，PORTAL和Ada-PORTAL是样本有效的，可以实现任意小的平均动态次优间隙多项式样本复杂度。
Reinforcement learning (RL) under changing environment models many real-world applications via nonstationary Markov Decision Processes (MDPs), and hence gains considerable interest. However, theoretical studies on nonstationary MDPs in the literature have mainly focused on tabular and linear (mixture) MDPs, which do not capture the nature of unknown representation in deep RL. In this paper, we make the first effort to investigate nonstationary RL under episodic low-rank MDPs, where both transition kernels and rewards may vary over time, and the low-rank model contains unknown representation in addition to the linear state embedding function. We first propose a parameter-dependent policy optimization algorithm called PORTAL, and further improve PORTAL to its parameter-free version of Ada-PORTAL, which is able to tune its hyper-parameters adaptively without any prior knowledge of nonstationarity. For both algorithms, we provide upper bounds on the average dynamic suboptimality gap, which show that as long as the nonstationarity is not significantly large, PORTAL and Ada-PORTAL are sample-efficient and can achieve arbitrarily small average dynamic suboptimality gap with polynomial sample complexity.