Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints

We study reinforcement learning (RL) with linear function approximation under\nthe adaptivity constraint. We consider two popular limited adaptivity models:\nthe batch learning model and the rare policy switch model, and propose two\nefficient online RL algorithms for episodic linear Markov decision processes,\nwhere the transition probability and the reward function can be represented as\na linear function of some known feature mapping. In specific, for the batch\nlearning model, our proposed LSVI-UCB-Batch algorithm achieves an $\\tilde\nO(\\sqrt{d^3H^3T} + dHT/B)$ regret, where $d$ is the dimension of the feature\nmapping, $H$ is the episode length, $T$ is the number of interactions and $B$\nis the number of batches. Our result suggests that it suffices to use only\n$\\sqrt{T/dH}$ batches to obtain $\\tilde O(\\sqrt{d^3H^3T})$ regret. For the rare\npolicy switch model, our proposed LSVI-UCB-RareSwitch algorithm enjoys an\n$\\tilde O(\\sqrt{d^3H^3T[1+T/(dH)]^{dH/B}})$ regret, which implies that $dH\\log\nT$ policy switches suffice to obtain the $\\tilde O(\\sqrt{d^3H^3T})$ regret. Our\nalgorithms achieve the same regret as the LSVI-UCB algorithm (Jin et al.,\n2019), yet with a substantially smaller amount of adaptivity. We also establish\na lower bound for the batch learning model, which suggests that the dependency\non $B$ in our regret bound is tight.\n