Geometric Regret Scaling in Linear Bandits

This direction is split into other directions: action set geometry constraints. Its last version stays readable and citable here.

Version 1 of 147 papers65 conceptsfrozen 2026-10-04

In the standard multi-armed bandit problem, a learner chooses between $K$ discrete actions. However, in many real-world scenarios—like routing packets through a network or recommending a slate of movies—the number of possible actions is exponentially large or even infinite. To handle this, we often model actions as vectors in a $d$-dimensional space, where the reward is a linear function of the chosen vector.

While it might seem that the number of dimensions $d$ is the primary factor determining learning difficulty, a growing body of research shows that the geometry of the action set—its "roundness," its "sharpness," and its orientation—is the true driver of performance.

The Roundness Advantage

The fundamental challenge in bandit learning is the exploration-exploitation trade-off. To learn the best action, you must try many different ones. The efficiency of this exploration depends on how much information a single choice provides about other possible choices.

Nicolò Cesa-Bianchi and Gábor Lugosi demonstrated in Combinatorial Bandits that the rate of improvement is limited by the "geometric diversity" of the action set. If your actions are all clustered in one direction, you learn very little about the rewards in other directions.

Intuition suggests that "round" action sets, like a Euclidean ball, are easier to navigate than "pointy" ones, like a hypercube or a simplex. This is because smooth, curved boundaries allow for gradual adjustments. As Ofer Dekel and colleagues point out in Online Learning with a Hint, the strong convexity (curvature) of an action set allows a learner to convert even slight "hints" about the future into significant regret reduction. In a round set, a small move in the right direction consistently brings you closer to the optimum. In a flat-sided polyhedral set, you might have to move a long way along a face before your distance to the optimal vertex actually decreases.

Regret at the Boundary

The relationship between geometry and regret is most visible at the boundaries of the action set. Hedi Hadiji and Sébastien Gerchinovitz show in Diversity-Preserving K-Armed Bandits, Revisited that the scaling of regret changes fundamentally based on where the optimal action lies:

  • Interior: If the optimal action is in the interior of the set, regret can be constant.
  • Flat Boundaries: If the optimum is on a flat face (like the side of a cube), regret typically scales logarithmically with time ($\log T$).
  • Curved Boundaries: If the optimum is on a curved boundary (like the surface of a sphere), regret can scale with $(\log T)^2$.

This happens because the "sharpness" of the boundary dictates how much a small error in estimating the reward vector penalizes the learner. On a sphere, a small estimation error leads to a small suboptimality gap. On a cube, a tiny change in the estimated reward vector can cause the learner to jump from one vertex to a completely different one, leading to a large "instability" penalty.

The High Price of Sharp Corners

The difficulty of "pointy" geometries isn't just theoretical; it impacts computational efficiency. The hypercube is a notorious example. While the number of vertices is $2^d$, Abhishek Shetty and Sudeep Raja Putta showed in Exponential Weights on the Hypercube in Polynomial Time that we can achieve minimax optimal regret in polynomial time by exploiting the fact that the exponential weights distribution factorizes over the cube's dimensions.

However, even "simple" geometric changes can drastically increase complexity. Ohad Shamir proved in On the Complexity of Bandit Linear Optimization that shifting a unit ball away from the origin—a seemingly trivial change—can increase the "price of bandit information" from $\sqrt{d}$ to $d$. This sensitivity suggests that many of our standard regret bounds are fragile artifacts of perfectly centered, symmetric geometries.

Measuring Complexity via Gaussian Width

To unify these observations, researchers have turned to tools from high-dimensional geometry. Julian Katz-Samuels and Kevin Jamieson use the concept of Gaussian width in An Empirical Process Approach to the Union Bound to provide a more nuanced measure of an action set's complexity.

Gaussian width captures how "spread out" a set is in different directions. By replacing simple dimension counts ($d$) with geometric measures like Gaussian width or the statistical "succinctness" framework proposed by Guo Zeng and Jean Honorio, we can derive lower bounds that are much tighter and more reflective of the actual difficulty of the learning task.

Ultimately, this research direction suggests that an algorithm's success depends less on how many choices it has, and more on the topological spread and local curvature of the space those choices inhabit. As Daniel Ezer and Yishay Mansour demonstrate in their work on parameter noise, exploiting the curvature of smooth action sets is often the key to breaking through the dimensionality barriers that plague traditional bandit theory.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_geometric_regret_scaling_in_linear_bandi_2ee8b01b,
  title = {Geometric Regret Scaling in Linear Bandits},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/geometric-regret-scaling-in-linear-bandits/rdr_2ee8b01b3e084f67bac8555f8614ebfe},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_geometric_regret_scaling_in_linear_bandi_2ee8b01b_v1,
  title = {Geometric Regret Scaling in Linear Bandits},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/geometric-regret-scaling-in-linear-bandits/rdr_2ee8b01b3e084f67bac8555f8614ebfe/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}