Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPs
It addresses the challenge of costly policy deployment in RL for real-world applications, extending beyond prior linear MDP results.
The paper tackles the problem of minimizing policy switching costs in reinforcement learning beyond linear MDPs, achieving near-optimal regret with a switching cost logarithmic in episodes and linear in horizon H and dimension d, and proving a lower bound proportional to dH.
In many real-life reinforcement learning (RL) problems, deploying new policies is costly. In those scenarios, algorithms must solve exploration (which requires adaptivity) while switching the deployed policy sparsely (which limits adaptivity). In this paper, we go beyond the existing state-of-the-art on this problem that focused on linear Markov Decision Processes (MDPs) by considering linear Bellman-complete MDPs with low inherent Bellman error. We propose the ELEANOR-LowSwitching algorithm that achieves the near-optimal regret with a switching cost logarithmic in the number of episodes and linear in the time-horizon $H$ and feature dimension $d$. We also prove a lower bound proportional to $dH$ among all algorithms with sublinear regret. In addition, we show the ``doubling trick'' used in ELEANOR-LowSwitching can be further leveraged for the generalized linear function approximation, under which we design a sample-efficient algorithm with near-optimal switching cost.