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.

本研究在探讨非平稳马尔可夫决策过程下的强化学习问题，针对低秩模型中存在未知表示的情况，提出了参数依赖的优化算法 PORTAL 和参数无关的改进版 Ada-PORTAL，通过样本复杂度进行理论分析并得出上界，证明了在非平稳性不显著时，这两种算法均能够以多项式样本复杂度实现任意小的平均动态次优差距。