Abstract
We investigate the hardness of online reinforcement learning in fixed horizon, sparse linear Markov decision process (MDP), with a special focus on the high-dimensional regime where the ambient dimension is larger than the number of episodes. Our contribution is two-fold. First, we provide a lower bound showing that linear regret is generally unavoidable in this case, even if there exists a policy that collects well-conditioned data. The lower bound construction uses an MDP with a fixed number of states while the number of actions scales with the ambient dimension. Note that when the horizon is fixed to one, the case of linear stochastic bandits, the linear regret can be avoided. Second, we show that if the learner has oracle access to a policy that collects well-conditioned data then a variant of Lasso fitted Q-iteration enjoys a nearly dimension-free regret of $\tilde{O}( s^{2/3} N^{2/3})$ where $N$ is the number of episodes and $s$ is the sparsity level. This shows that in the large-action setting, the difficulty of learning can be attributed to the difficulty of finding a good exploratory policy.
Introduction
In modern Reinforcement Learning (RL), linear models are frequently employed to represent complex environments, assuming that transition dynamics and rewards can be explained by a set of features. However, in the "high-dimensional regime," the number of features ($d$) can significantly exceed the number of episodes ($N$) available for learning.
In classical statistics, this challenge is addressed through sparsity: the assumption that only a small subset ($s$) of the $d$ features are relevant. While sparsity is highly effective for static regression (e.g., the Lasso) and multi-armed bandits, its role in online RL has remained less understood. This research investigates whether sparsity alone is sufficient to overcome the "curse of dimensionality" when an agent must simultaneously explore an environment and maximize rewards.
The Hardness of Exploration
The study first establishes a fundamental lower bound on regret. The authors demonstrate that in the high-dimensional regime, linear regret—essentially a failure to learn efficiently—is often unavoidable.
The core of this hardness result lies in the difficulty of exploration. The authors construct a "hard-to-learn" Markov Decision Process (MDP) where the agent starts in a neutral state and must select exactly the right action from a large set to reach an "informative" state.
As shown in Figure 1, the agent at state $x_0$ faces $d$ possible actions. Only one specific action leads to the informative state $x_i$, while the remaining $d-1$ actions lead to an uninformative state $x_u$. Because the transitions are sparse but the "needle" is hidden in a high-dimensional haystack of actions, any algorithm is likely to fail to find the informative state within a reasonable timeframe, leading to a regret of $\Omega(Hd)$. This highlights a fundamental gap between contextual bandits and RL: in RL, the "context" (state) is determined by the transition kernel, creating a "chicken-and-egg" problem where one must learn the transitions to explore, but must explore to learn the transitions.
Lasso Fitted-Q-Iteration (Lasso-FQI)
To determine if the difficulty lies in estimation or exploration, the authors propose an "Explore-then-Commit" framework using a variant of Lasso Fitted-Q-Iteration. This approach assumes the learner has oracle access to an exploratory policy that collects well-conditioned data.
The algorithm operates in three phases:
- Exploration: The agent follows the oracle's exploratory policy to collect diverse data.
- Learning: The agent applies a Lasso-based Fitted-Q-Iteration to identify the $s$ relevant features from the data.
- Exploitation: The agent commits to the best policy identified.
Under this oracle assumption, the algorithm achieves a regret of $\tilde{O}(s^{2/3}N^{2/3})$. Crucially, this regret is nearly independent of the total number of features $d$, scaling primarily with the sparsity level $s$. This result proves that sparsity can lead to efficient, dimension-free learning, provided the exploration bottleneck is bypassed.
Conclusion
This research clarifies the boundaries of sparse reinforcement learning. The primary obstacle in high-dimensional RL is not the estimation of feature values, but the initial discovery of informative states. While sparsity allows for efficient learning given a good exploratory policy, finding such a policy in a large action space remains a significant theoretical and practical challenge. Future work may focus on identifying conditions weaker than an oracle that still permit sub-linear regret in sparse environments.
Summary updated