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\}\big(H^2dlog T\sqrt\{T\}\big)\) 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\}\big(H^2\widetilde\{d\}log T\sqrt\{T\}\big)\), whe

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyyang2019reinforcement

Related papers

• An \(L^2\) Analysis Of Reinforcement Learning In High Dimensions With Kernel And Neural Network Approximation (2021)0.00
• Nearly Minimax Optimal Reinforcement Learning For Linear Markov Decision Processes (2022)0.00
• Model-based Reinforcement Learning For Continuous Control With Posterior Sampling (2020)0.00
• Value Function Approximations Via Kernel Embeddings For No-regret Reinforcement Learning (2020)0.00
• First-order Regret In Reinforcement Learning With Linear Function Approximation: A Robust Estimation Approach (2021)0.00
• Online Sparse Reinforcement Learning (2020)0.00
• Asymptotically Optimal Reinforcement Learning In Block Markov Decision Processes (2025)0.00
• Model-based Reinforcement Learning With Multinomial Logistic Function Approximation (2022)2.26