A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost

Abstract

Many real-world applications, such as those in medical domains, recommendation systems, etc, can be formulated as large state space reinforcement learning problems with only a small budget of the number of policy changes, i.e., low switching cost. This paper focuses on the linear Markov Decision Process (MDP) recently studied in [Yang et al 2019, Jin et al 2020] where the linear function approximation is used for generalization on the large state space. We present the first algorithm for linear MDP with a low switching cost. Our algorithm achieves an $\tilde{O}\left(\sqrt{d^3{H}^{4}K}\right)$ regret bound with a near-optimal $O\left(dH\log K\right)$ global switching cost where $d$ is the feature dimension, $H$ is the planning horizon and $K$ is the number of episodes the agent plays. Our regret bound matches the best existing polynomial algorithm by [Jin et al 2020] and our switching cost is exponentially smaller than theirs. When specialized to tabular MDP, our switching cost bound improves those in [Bai et al 2019, Zhang et al 20020]. We complement our positive result with an $\Omega \left(dH/\log d\right)$ global switching cost lower bound for any no-regret algorithm.

References in corpus (19)

• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Learning to Optimize Join Queries With Deep Reinforcement Learning
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Learning Near Optimal Policies with Low Inherent Bellman Error
• Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• On Lower Bounds for Regret in Reinforcement Learning
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
• Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
• Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes

Cited by in corpus (4)

• Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
• Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing
• Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation