Regret Scaling in High Dimensional Online Learning

681 concepts472 papers2 proposals

In online learning and multi-armed bandits, the standard measure of success is regret—the difference between the total reward collected by an omniscient oracle and that accumulated by the learning algorithm. Traditionally, the primary focus of bandit theory has been optimizing how regret scales with time $T$. We celebrate algorithms that achieve sublinear regret like $O(\sqrt{T})$ or $O(\log T)$, which guarantee that the learner will eventually converge to an optimal policy.

However, this time-centric view masks a critical bottleneck: how regret scales with the dimensionality ($d$) of the problem's features, contexts, or actions. In modern applications like personalized recommendation engines, dynamic pricing, and clinical trials, an agent must process high-dimensional context vectors (e.g., thousands of user demographics or product attributes). If an algorithm's regret scales poorly with $d$, its theoretical time-optimality becomes practically irrelevant because the "burn-in" period required to achieve acceptable performance grows too large to survive.

The Mathematical Reality of the Curse

Why does dimensionality degrade performance so drastically? The answer depends heavily on the structural assumptions we make about the environment's reward function.

Non-Parametric Settings: The Exponential Explosion

In non-parametric settings, where the reward function is merely assumed to be smooth (e.g., Lipschitz), the problem is fundamentally geometric. To learn the reward landscape without a strict formula, an algorithm must effectively partition the context space into localized sub-regions. As Suk et al. and Chen et al. demonstrate, the number of required sub-regions grows exponentially with the number of features ($O(2^d)$).

This exponential scaling means that as more contextual variables are added, the time required to achieve a target performance level explodes. Consequently, non-parametric pricing or recommendation models face severe performance degradation in feature-rich environments, making them highly sensitive to the curse of dimensionality (Bachoc et al.; Gollapudi et al.).

Linear and Parametric Settings: The Polynomial Burden

To escape exponential scaling, researchers often assume a linear structure. In standard linear bandits, regret typically scales linearly with the total number of dimensions (Carpentier et al.). As Brunskill notes, the number of samples required to learn an optimal policy scales linearly with the feature dimension, creating a massive resource burden when the dimensionality is larger than the number of rounds.

Furthermore, when we add real-world complexities—such as tracking non-stationary environments, handling adversarial attacks, or estimating system variance—the dimensional dependence often degrades into high-degree polynomials. For example:

  • Variance-Aware Bounds: Current variance-aware regret bounds can exhibit a polynomial dependency as high as the ninth power of the feature dimension, largely due to loose mathematical generalizations of quadratic potentials (Zhang et al.).
  • Robustness and Control: Algorithms designed to be robust against adversarial attacks or time-varying control dynamics suffer significant performance penalties, scaling with the dimension to the power of 1.5, 2, or higher (Bogunovic et al.; Yuwei Luo et al.).

Why Errors Compound in High Dimensions

To build intuition for why dimensionality degrades regret, consider how a linear bandit algorithm constructs its confidence intervals. The algorithm uses past observations to estimate a $d$-dimensional parameter vector $\theta^*$. The uncertainty around this estimate forms an ellipsoid in $d$-dimensional space.

When choosing an action, the algorithm projects this uncertainty ellipsoid along the action's feature vector to apply the principle of "optimism in the face of uncertainty." In high dimensions, the volume of this uncertainty ellipsoid explodes.

Low Dimension (d=2)                 High Dimension (d=Many)
     ┌───────┐                            ┌───────────────────┐
  ───│   •   │───                      ───│         •         │───
     └───────┘                            └───────────────────┘
Small uncertainty volume;             Massive uncertainty volume;
Tight upper confidence bounds.        Loose bounds lead to excessive,
                                      suboptimal exploration.

If the model is even slightly misspecified (meaning the true reward function isn't perfectly linear), Dong et al. demonstrate that the approximation error scales with the square root of the total feature dimension, rapidly rendering the linear approximation unreliable. Additionally, if the action space itself is high-dimensional, algorithms can suffer from quadratic regret growth or square-root dependencies on the action space size, slowing down convergence significantly (Chiang et al.; Schuurmans).

Escaping the Curse: Structural and Statistical Remedies

To make high-dimensional online learning practical, recent literature focuses on identifying structural properties or advanced statistical estimators that can neutralize or tame dimension-dependent scaling.

1. Exploiting Hidden Low-Rank and Sparse Structures

If the true reward function depends only on a small subspace or a sparse subset of the high-dimensional features, we can bypass scaling with the full dimension $d$. For instance, Hamidi et al. introduce a row-enhancement technique for personalization tasks that leverages hidden low-rank structures to achieve a regret bound that scales linearly rather than cubically with the problem's dimensions.

2. Advanced Estimators and Dimension-Free Tail Bounds

Instead of relying on standard least-squares estimators—which suffer from loose tail bounds in high dimensions—algorithms can use more sophisticated statistical designs. Wonyoung Kim et al. demonstrate that "doubly robust" estimators can maintain stable regret even as the feature space expands by effectively learning from unselected actions. Furthermore, by employing novel "dimension-free" concentration inequalities that account for the underlying geometry of the feature space, Wonyoung Kim et al. successfully shave a factor of $\sqrt{d}$ off the standard regret bound for Linear Thompson Sampling.

3. Alternative Feedback Mechanisms

Sometimes, changing how the algorithm collects feedback can fundamentally alter the statistical speed limits of learning. Jourdan et al. show that leveraging preference feedback (pairwise comparisons) rather than absolute noisy rewards can accelerate parameter estimation from the standard $O(1/\sqrt{n})$ rate to a faster $O(1/n)$ rate, though the overall complexity remains bounded by the dimensionality of the target distribution.

Ultimately, mapping out the precise boundaries of how context space size, feature dimensionality, and time interact remains a vibrant frontier in online learning theory (Ito; Tullii et al.).

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_high_dimensional_regret_scaling_64baeaf3,
  title = {high-dimensional regret scaling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/high-dimensional-regret-scaling/rdr_64baeaf332cc43f4a8356fe474d2ec39},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_high_dimensional_regret_scaling_64baeaf3_v1,
  title = {high-dimensional regret scaling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/high-dimensional-regret-scaling/rdr_64baeaf332cc43f4a8356fe474d2ec39/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake