Online Sparse Reinforcement Learning

Botao Hao, Tor Lattimore, Csaba Szepesvári, Mengdi Wang

Authors: Botao Hao (DeepMind), Tor Lattimore (DeepMind), Csaba Szepesvári (University of Alberta/DeepMind), Mengdi Wang (Princeton University)

Abstract

We investigate the hardness of online reinforcement learning in 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, even if there exists a policy that collects well-conditioned data. 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 regret of $O(N^{2/3})$ where $N$ is the number of episodes.

Introduction

In classical statistics, sparsity is a powerful tool. When dealing with high-dimensional data where the number of features $d$ exceeds the number of samples, algorithms like the Lasso can successfully identify the few relevant features ($s \ll d$). This principle has been effectively applied to static regression and multi-armed bandits. However, Reinforcement Learning (RL) introduces a fundamental challenge: the data distribution is controlled by the agent's actions. To learn which features are relevant, an agent must first explore the environment. This research explores whether sparsity can overcome the "curse of dimensionality" in online RL or if the necessity of exploration creates an insurmountable barrier.

The Exploration-Estimation Dilemma

The core difficulty in sparse RL is a "chicken-and-egg" problem involving exploration and estimation:

  1. Estimation requires exploration: To identify the $s$ important features, the agent needs "well-conditioned" data that covers the feature space.
  2. Exploration requires knowledge: To navigate to informative states in a complex environment, the agent must already know which features and transitions are important.

Without prior knowledge of the relevant features, an agent may spend an impractical amount of time performing random actions that fail to yield informative data.

Hardness of Exploration: A Minimax Lower Bound

The authors establish a minimax lower bound by constructing a specific "hard" MDP. In this environment, the agent starts at a state $x_0$ and must choose from $d$ possible actions. Only one specific action leads to an "informative" state ($x_i$), while the remaining $d-1$ actions lead to an "uninformative" state ($x_u$).

Figure 1: A hard MDP construction where only one specific action out of $d$ leads to an informative state, illustrating the exploration bottleneck in high-dimensional sparse RL.

Using information-theoretic arguments, the paper proves that any algorithm will struggle to find this "needle in a haystack." The resulting regret scales linearly with the total dimension $d$. In the high-dimensional regime ($d > N$), this implies that the learner performs no better than random guessing for a significant duration, regardless of the underlying sparsity.

Lasso Fitted Q-Iteration (Lasso-FQI)

To isolate the estimation problem from the exploration problem, the authors analyze Lasso-FQI. This algorithm employs an "explore-then-commit" strategy, integrating a Lasso penalty into the standard Fitted Q-Iteration update to perform on-the-fly feature selection.

Crucially, the analysis assumes the learner has Oracle Access to an exploratory policy—a pre-existing mechanism to gather well-conditioned data. Under this assumption, the algorithm achieves a regret of $\tilde{O}(s^{2/3}N^{2/3})$. In this scenario, the ambient dimension $d$ only appears logarithmically, making the regret effectively "dimension-free" and dependent primarily on the sparsity level $s$.

Key Insights

  • The RL-Bandit Gap: Unlike linear bandits, where exploratory distributions can eventually be found, RL transitions can "hide" informative states behind specific action sequences, making them exponentially harder to locate.
  • Sparsity's Limits: Sparsity aids in estimation (calculating feature weights) but does not inherently simplify exploration (finding where those features manifest).
  • Localization of Hardness: The "hardness" of high-dimensional RL is concentrated in the exploration phase. If exploration is solved (via an oracle), the estimation phase scales efficiently with sparsity.

Conclusion and Future Work

This work demonstrates that sparsity alone is insufficient for efficient online RL in high dimensions. The linear regret lower bound suggests that without additional structural assumptions or exploratory guidance, the curse of dimensionality persists. Future research may focus on identifying specific MDP classes where exploratory policies are easier to discover or leveraging structural sparsity to bridge the gap between theoretical bounds and practical performance.

Summary updated

Abstract

We investigate the hardness of online reinforcement learning in 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, even if there exists a policy that collects well-conditioned data. 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 regret of $O(N^{2/3})$ where $N$ is the number of episodes.
BibTeX
@inproceedings{hao2021online,
  author = {Botao Hao and Tor Lattimore and Csaba Szepesvári and Mengdi Wang},
  title = {{Online Sparse Reinforcement Learning}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=p5qCtJMG8-4},
}
Figure