Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
This provides a theoretical improvement for RL practitioners dealing with large-scale problems by offering the first near-optimal regret bounds for feature- or kernel-based methods, though it is incremental in advancing existing bandit techniques.
The paper tackles the problem of exploration in reinforcement learning with high-dimensional state-action spaces by proposing MatrixRL, an online algorithm that learns a low-dimensional representation of the transition model, achieving a regret bound of O(H^2d log T √T) with features and O(H^2d̃ log T √T) with kernels, which are near-optimal in time and dimension and polynomial in horizon.
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^2d\log 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)$, where $\widetilde{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 $\widetilde{d}$) and polynomial in the planning horizon $H$.