Linear Reinforcement Learning with Ball Structure Action Space
This addresses sample efficiency in RL for settings with linear function approximation, but it is incremental as it relies on a specific action space assumption.
The paper tackles the problem of reinforcement learning with linear function approximation, where worst-case sample complexity is exponential, by assuming a 'ball structure' action space that allows free exploration of the feature space, resulting in an algorithm (BallRL) that learns an ε-optimal policy with Õ(H⁵d³/ε³) trajectories.
We study the problem of Reinforcement Learning (RL) with linear function approximation, i.e. assuming the optimal action-value function is linear in a known $d$-dimensional feature mapping. Unfortunately, however, based on only this assumption, the worst case sample complexity has been shown to be exponential, even under a generative model. Instead of making further assumptions on the MDP or value functions, we assume that our action space is such that there always exist playable actions to explore any direction of the feature space. We formalize this assumption as a ``ball structure'' action space, and show that being able to freely explore the feature space allows for efficient RL. In particular, we propose a sample-efficient RL algorithm (BallRL) that learns an $ε$-optimal policy using only $\tilde{O}\left(\frac{H^5d^3}{ε^3}\right)$ number of trajectories.