When and why randomised exploration works (in linear bandits)

Technical Summary: When and why randomised exploration works (in linear bandits)

Problem Setting
The paper addresses the linear bandit problem, a sequential decision-making setting where an agent selects actions $X_t$ from a closed subset $\mathcal{X}$ of the unit Euclidean ball in $\mathbb{R}^d$. The agent receives a reward $Y_t$ with mean $\langle X_t, \theta^\star \rangle$, where $\theta^\star$ is an unknown parameter vector. The objective is to minimize the $n$-step regret, defined as the cumulative difference between the reward of the optimal action and the actions taken.

While optimistic algorithms (e.g., Upper Confidence Bound) have established frequentist regret bounds of $O(d\sqrt{n} \log n)$ for linear bandits, randomised exploration algorithms like Thompson sampling have historically been harder to analyze in this setting. Previous frequentist analyses of randomised methods often relied on "forced optimism" or "posterior inflation"—modifying the algorithm to artificially inflate the variance of the posterior distribution to ensure optimism with high probability. These modifications typically resulted in suboptimal regret bounds, such as $O((d \log n)^{3/2}\sqrt{n})$, introducing an extra $\sqrt{d}$ factor compared to optimistic algorithms. Furthermore, recent lower bounds (Hamidi and Bayati, 2023; Zhang, 2022) demonstrated that unmodified Thompson sampling can incur linear regret in specific pathological settings, suggesting that randomised exploration is not universally optimal without structural assumptions.

Methodology and Assumptions
The authors propose a new analysis framework that avoids modifying the randomised algorithm (i.e., no forced optimism or posterior inflation). Instead, the analysis relies on specific geometric properties of the action set $\mathcal{X}$.

1. Algorithmic Framework: The paper considers a class of randomised algorithms where, at each step $t$, a parameter $\theta_t$ is sampled as $\theta_t = \hat{\theta}_{t-1} + V_{t-1}^{-1/2}\eta_t$, where $\hat{\theta}_{t-1}$ is the regularised least-squares estimate, $V_{t-1}$ is the design matrix, and $\eta_t$ is a rotationally invariant perturbation. The action is selected as $X_t = \arg\max_{x \in \mathcal{X}} \langle x, \theta_t \rangle$.
2. Perturbation Assumptions: The perturbations $\eta_t$ are assumed to be independent, rotationally invariant random variables with bounded second and fourth moments (e.g., Gaussian or uniform on a sphere).
3. Action Set Assumptions (Smoothness and Strong Convexity): The core theoretical contribution rests on Assumption 4.2, which requires the action set $\mathcal{X}$ to be a closed, absorbing subset of the unit ball such that the square of its support function, $J_{\mathcal{X}}^2$, is both $m$-strongly convex and $M$-smooth with respect to a specific norm $\|\cdot\|_*$.
   • Strong Convexity: Ensures that the support function does not have "flat" regions, guaranteeing that small changes in the parameter space translate to meaningful changes in the action space.
   • Smoothness: Ensures that the gradient of the support function (which maps parameters to actions) is Lipschitz, preventing large jumps in regret due to small parameter perturbations.
   • Examples: This class includes rescaled $\ell_q$-balls for $q \in (1, \infty)$.

Key Contributions and Analysis
The paper provides a frequentist regret analysis that does not rely on the "optimism in the face of uncertainty" framework. Instead, it directly analyzes the dynamics of the exploration process and the evolution of the confidence sets.

• Regret Decomposition: The authors decompose the expected regret into two components: steps where the algorithm is "optimistic" (the sampled parameter yields a value higher than the true optimum) and steps where it is not.
• Non-Optimistic Exploration: A critical insight is that even when a sample is not optimistic, it still provides valuable information that shrinks the confidence set. The authors utilize a Bregman divergence formulation of the per-step regret, $r_t = D_{J_{\mathcal{X}}}(\theta^\star, \theta_t)$, and leverage the strong convexity and smoothness of $J_{\mathcal{X}}^2$ to bound this divergence.
• Information Growth: The proof establishes a lower bound on the growth of the design matrix $V_t$ by relating the expected information gain $\mathbb{E}_{t-1}[X_t X_t^\top]$ to the geometry of the confidence ellipsoids. This connects the "size" of the parameter space (measured by $V_t^{-1/2}$) to the actual exploration performed.
• Avoiding Inflation: Unlike previous works, this analysis does not require inflating the variance of the sampling distribution. It demonstrates that the natural randomness of the algorithm, combined with the geometric properties of $\mathcal{X}$, is sufficient to drive exploration and control regret.

Main Results
Under the stated assumptions, the authors prove that any randomised algorithm satisfying the perturbation conditions achieves a frequentist regret bound of:
$$R_n \lesssim O(d\sqrt{n} \log n)$$
Specifically, Theorem 4.1 provides a bound of the order $O(d\sqrt{n} \log n)$ (ignoring logarithmic factors in $n$ and $\delta$). This matches the known lower bound for linear bandits (Rusmevichientong and Tsitsiklis, 2010) up to logarithmic factors.

Significance and Claims
The paper claims to resolve an important open question regarding the dimension dependence of Thompson sampling in linear bandits.

• Optimal Dimension Dependence: It demonstrates for the first time that unmodified (non-inflated) Thompson sampling can achieve optimal dimension dependence ($O(d)$) in structured linear bandit settings, specifically when the action space is smooth and strongly convex.
• Mechanism of Success: The work elucidates why randomised exploration works in these settings: the geometric properties of the action set ensure that perturbations in the parameter space effectively explore the action space without requiring artificial optimism.
• Limitations and Scope: The authors acknowledge that their results do not contradict existing lower bounds showing linear regret for Thompson sampling in non-smooth or non-absorbing action spaces (e.g., those with "trap" arms). The success of the method is contingent on the action set satisfying the smoothness and strong convexity assumptions. The paper does not claim that these conditions are necessary, but rather that they are sufficient to achieve optimal rates without algorithmic modifications.

In summary, the paper establishes that for a broad class of well-behaved action sets (including $\ell_q$-balls), randomised exploration algorithms naturally achieve optimal regret rates, removing the need for the ad-hoc variance inflation techniques previously thought necessary for theoretical guarantees.