Sample-Optimal Parametric Q-Learning Using Linearly Additive Features

Abstract

Consider a Markov decision process (MDP) that admits a set of state-action features, which can linearly express the process's probabilistic transition model. We propose a parametric Q-learning algorithm that finds an approximate-optimal policy using a sample size proportional to the feature dimension $K$ and invariant with respect to the size of the state space. To further improve its sample efficiency, we exploit the monotonicity property and intrinsic noise structure of the Bellman operator, provided the existence of anchor state-actions that imply implicit non-negativity in the feature space. We augment the algorithm using techniques of variance reduction, monotonicity preservation, and confidence bounds. It is proved to find a policy which is $\epsilon$-optimal from any initial state with high probability using $\tilde{O}(K/{\epsilon }^2(1-\gamma {)}^3)$ sample transitions for arbitrarily large-scale MDP with a discount factor $\gamma \in (0,1)$. A matching information-theoretical lower bound is proved, confirming the sample optimality of the proposed method with respect to all parameters (up to polylog factors).

Accepted to ICML, 2019

References in corpus (3)

• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Scalable Bilinear $\pi$ Learning Using State and Action Features
• Reinforcement Learning in Rich-Observation MDPs using Spectral Methods

Cited by in corpus (9)

• Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
• Frequentist Regret Bounds for Randomized Least-Squares Value Iteration
• Corruption-Robust Offline Reinforcement Learning
• Near-optimal Representation Learning for Linear Bandits and Linear RL
• Breaking the Deadly Triad with a Target Network
• Minimax Regret for Stochastic Shortest Path
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
• On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function
• Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL