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 (9)

• Playing Atari with Deep Reinforcement Learning
• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving
• What Doubling Tricks Can and Can't Do for Multi-Armed Bandits
• On Lower Bounds for Regret in Reinforcement Learning
• Minimax Regret Bounds for Reinforcement Learning
• Sample-Optimal Parametric Q-Learning Using Linearly Additive Features
• Policy Certificates: Towards Accountable Reinforcement Learning
• No-regret Exploration in Contextual Reinforcement Learning

Cited by in corpus (21)

• 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
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization
• Neural Thompson Sampling
• Adaptive Discretization for Episodic Reinforcement Learning in Metric Spaces
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• Corruption-robust exploration in episodic reinforcement learning
• 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
• Robust Policy Gradient against Strong Data Corruption
• Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles
• Conservative Exploration in Reinforcement Learning
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
• Efficient Learning in Non-Stationary Linear Markov Decision Processes
• Generative Adversarial Imitation Learning with Neural Networks: Global Optimality and Convergence Rate
• $\sqrt{n}$-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank
• Randomized Value Functions via Posterior State-Abstraction Sampling
• Can Agents Learn by Analogy? An Inferable Model for PAC Reinforcement Learning
• A maximum-entropy approach to off-policy evaluation in average-reward MDPs