Provably Efficient Algorithm for Nonstationary Low-Rank MDPs
Yuan Cheng Jing Yang Yingbin Liang
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.