Stochastic Linear Bandits with Parameter Noise

Technical Summary: Stochastic Linear Bandits with Parameter Noise

Problem Definition
This work investigates the stochastic linear bandits with parameter noise model. In this setting, a learner interacts with an environment over a time horizon $T$ by selecting actions $a_t$ from an action set $\mathcal{A} \subseteq \mathbb{R}^d$. Unlike the standard additive noise model where the reward is $X_t = a_t^\top \theta^\star + \eta_t$ (with fixed $\theta^\star$ and noise $\eta_t$), the parameter noise model assumes the reward is given by $X_t = a_t^\top \theta_t$, where $\theta_t$ is sampled i.i.d. from a fixed, unknown distribution $\nu$ with mean $\theta^\star$ and covariance matrix $\Sigma$.

The paper highlights a key distinction: in the parameter noise model, the learner can influence the variance of the reward. Specifically, $\text{Var}(X_t) = a_t^\top \Sigma a_t$, whereas in the additive noise model, the variance is determined solely by the environment. The authors note that while the parameter noise model is a relaxation of the adversarial linear bandit model (where $\theta_t$ is chosen by an adversary), it presents unique structural properties that allow for potentially tighter regret bounds than the additive noise model in certain geometric settings.

Methodology and Algorithms
The authors propose two algorithms tailored to different action set geometries:

1. VASE (Variance Aware Optimal Design Successive Elimination):

   • Target: General finite action sets (and infinite sets via covering arguments).
   • Mechanism: A successive elimination algorithm that leverages variance information. In each phase, it computes a G-optimal design $\pi_\ell$ to select actions. It explicitly estimates the variance of actions in the support of the design using a stopping rule algorithm (SR).
   • Key Innovation: The algorithm uses estimated variances in two ways: to reduce the number of samples required for exploration and as weights in a weighted least squares estimator. This weighting ensures the covariance of the estimator remains controlled even with fewer samples, leading to variance-dependent regret bounds.

2. VALEE (Variance Aware Linear Explore-Exploit):

   • Target: $\ell_p$ unit balls where $p \in (1, 2]$ (and their dual norms $q \ge 2$).
   • Mechanism: A simple explore-exploit algorithm.
     • Exploration: The algorithm plays standard basis vectors $e_i$. It estimates the mean vector $\theta^\star$ coordinate-wise using the Median-of-Means (MoM) technique. If the covariance matrix $\Sigma$ is unknown, it first estimates the variances of the basis vectors.
     • Exploitation: Once the estimation error is sufficiently small relative to the variance and time horizon, the algorithm commits to an action $\hat{a}$ derived from the estimated mean $\hat{\theta}$, specifically $\hat{a}_i = \text{sign}(\hat{\theta}_i)|\hat{\theta}_i|^{q-1} / \|\hat{\theta}\|_q^{q-1}$.
   • Key Innovation: The analysis exploits the geometry of the $\ell_p$ ball and the parameter noise structure. The authors show that exploring basis vectors yields an estimation error proportional to $\sqrt{\sigma^2(e_i)}$, which is tighter than the standard $\epsilon$ bound in additive noise models. This allows the algorithm to achieve optimal regret bounds that depend on the variance structure of the reward distribution.

Key Results
The paper establishes both upper and lower bounds, demonstrating that the proposed algorithms are minimax optimal (up to logarithmic factors) for specific settings.

• General Finite Action Sets ($K$ actions):

  • Upper Bound: VASE achieves a regret of $\tilde{O}(d^2 + \sqrt{dT \log(K/\delta) M_\sigma})$, where $M_\sigma$ is a variance-dependent quantity bounded by $\max_a \sigma^2(a)$.
  • Lower Bound: A lower bound of $\tilde{\Omega}(d\sqrt{T \sigma^2_{\max}})$ is proven, showing the upper bound is tight up to logarithmic factors when $\log(K) \approx d$.

• $\ell_p$ Unit Balls ($p \le 2$):

  • Known Covariance: VALEE achieves a regret of $\tilde{O}(d + \sqrt{dT \sigma^2_q})$, where $\sigma^2_q = (\sum \Sigma_{ii}^{q/2})^{2/q}$. This is shown to be optimal via a matching lower bound of $\tilde{\Omega}(\sqrt{dT \sigma^2_q})$.
  • Unknown Covariance: VALEE incurs an additional additive term, resulting in a regret of $\tilde{O}(\sqrt{dT \sigma^2_q} + d^{2/3 + 2/3q} T^{1/3})$. The authors note this additive term arises from the variance estimation phase.

• $\ell_p$ Unit Balls ($p > 2$):

  • The paper provides a lower bound of $\tilde{\Omega}(d\sqrt{T \sigma^2_{\max}})$, matching the known lower bounds for the adversarial setting in these geometries.

Significance and Claims
The paper claims to resolve a "curious case" regarding linear bandits where the additive noise model often yields worse regret bounds ($d\sqrt{T}$) than the adversarial model ($\sqrt{dT}$) for specific action sets like the $\ell_2$ unit ball. The authors demonstrate that the parameter noise model aligns more closely with the intuition that stochastic models should be easier than adversarial ones.

• Tighter Bounds: For $\ell_p$ balls with $p \le 2$, the parameter noise model allows for regret bounds of order $\sqrt{dT \sigma^2_q}$, which can be significantly smaller than the $d\sqrt{T}$ bound typical of additive noise models when the variance is small.
• Structural Advantage: The results highlight that the linearity of the realization (not just the expectation) and the ability of the learner to influence variance are crucial for achieving these improved bounds.
• Simplicity: Surprisingly, the optimal regret for $\ell_p$ balls ($p \le 2$) is attainable using a very simple explore-exploit algorithm (VALEE), contrasting with the complex optimal design algorithms often required in additive noise settings.

The authors conclude that while their results for $p \le 2$ are optimal (up to logs) when the covariance is known, the unknown covariance case leaves an open gap (the $T^{1/3}$ term) that future work may address. They also leave the design of an algorithm matching the lower bound for $p > 2$ as an open question.