Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound

Abstract

Exploration in reinforcement learning (RL) suffers from the curse of dimensionality when the state-action space is large. A common practice is to parameterize the high-dimensional value and policy functions using given features. However existing methods either have no theoretical guarantee or suffer a regret that is exponential in the planning horizon $H$. In this paper, we propose an online RL algorithm, namely the MatrixRL, that leverages ideas from linear bandit to learn a low-dimensional representation of the probability transition model while carefully balancing the exploitation-exploration tradeoff. We show that MatrixRL achieves a regret bound $O\left(H^{2}d\log T\sqrt{T}\right)$ where $d$ is the number of features. MatrixRL has an equivalent kernelized version, which is able to work with an arbitrary kernel Hilbert space without using explicit features. In this case, the kernelized MatrixRL satisfies a regret bound $O\left(H^2\tilde{d}\log T\sqrt{T}\right)$, where $\tilde{d}$ is the effective dimension of the kernel space. To our best knowledge, for RL using features or kernels, our results are the first regret bounds that are near-optimal in time $T$ and dimension $d$ (or $\tilde{d}$) and polynomial in the planning horizon $H$.

References in corpus (3)

• Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving
• On Lower Bounds for Regret in Reinforcement Learning
• Sample-Optimal Parametric Q-Learning Using Linearly Additive Features

Cited by in corpus (12)

• Model-Based Reinforcement Learning with Value-Targeted Regression
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• Adaptive Discretization for Episodic Reinforcement Learning in Metric Spaces
• Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation
• Provably Efficient Causal Reinforcement Learning with Confounded Observational Data
• Provably Efficient Reinforcement Learning with Aggregated States
• Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
• Can Agents Learn by Analogy? An Inferable Model for PAC Reinforcement Learning
• A maximum-entropy approach to off-policy evaluation in average-reward MDPs