Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes

Abstract

We study reinforcement learning (RL) with linear function approximation where the underlying transition probability kernel of the Markov decision process (MDP) is a linear mixture model (Jia et al., 2020; Ayoub et al., 2020; Zhou et al., 2020) and the learning agent has access to either an integration or a sampling oracle of the individual basis kernels. We propose a new Bernstein-type concentration inequality for self-normalized martingales for linear bandit problems with bounded noise. Based on the new inequality, we propose a new, computationally efficient algorithm with linear function approximation named ${\text{UCRL-VTR}}^{+}$ for the aforementioned linear mixture MDPs in the episodic undiscounted setting. We show that ${\text{UCRL-VTR}}^{+}$ attains an $\tilde{O}(dH\sqrt{T})$ regret where $d$ is the dimension of feature mapping, $H$ is the length of the episode and $T$ is the number of interactions with the MDP. We also prove a matching lower bound $\Omega (dH\sqrt{T})$ for this setting, which shows that ${\text{UCRL-VTR}}^{+}$ is minimax optimal up to logarithmic factors. In addition, we propose the ${\text{UCLK}}^{+}$ algorithm for the same family of MDPs under discounting and show that it attains an $\tilde{O}(d\sqrt{T}/(1-\gamma {)}^{1.5})$ regret, where $\gamma \in [0,1)$ is the discount factor. Our upper bound matches the lower bound $\Omega (d\sqrt{T}/(1-\gamma {)}^{1.5})$ proved by Zhou et al. (2020) up to logarithmic factors, suggesting that ${\text{UCLK}}^{+}$ is nearly minimax optimal. To the best of our knowledge, these are the first computationally efficient, nearly minimax optimal algorithms for RL with linear function approximation.

59 pages, 1 figure

References in corpus (24)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Empirical Bernstein Bounds and Sample Variance Penalization
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• 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
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions
• Improved Optimistic Algorithms for Logistic Bandits
• On Oracle-Efficient PAC RL with Rich Observations
• $Q$-learning with Logarithmic Regret
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity
• Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalities
• Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs
• Tight Regret Bounds for Infinite-armed Linear Contextual Bandits
• Regret Bounds for Discounted MDPs
• DBNET: DOA-driven beamforming network for end-to-end farfield sound source separation

Cited by in corpus (7)

• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
• Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation
• Near-optimal Representation Learning for Linear Bandits and Linear RL
• Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints
• Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solver
• Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation