Provably Efficient Algorithm for Nonstationary Low-Rank MDPs
This addresses the problem of handling changing environments in deep RL for real-world applications, representing a novel theoretical extension beyond tabular and linear MDPs.
The paper tackles reinforcement learning in nonstationary low-rank Markov Decision Processes (MDPs) with unknown representations, proposing algorithms PORTAL and Ada-PORTAL that achieve sample-efficient performance with polynomial sample complexity and arbitrarily small average dynamic suboptimality gap, as long as nonstationarity is not too large.
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.