Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints

Abstract

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

21 pages, 3 figures. In NeurIPS 2021

References in corpus (9)

• Model-Based Reinforcement Learning with Value-Targeted Regression
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost

Cited by in corpus (4)

• Online Learning for Unknown Partially Observable MDPs
• Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm
• Design of Experiments for Stochastic Contextual Linear Bandits
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation