Technical Summary: A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions

1. Problem Setting

The paper addresses the problem of Heteroskedastic Generalized Linear Bandits (GLBs) in the presence of adversarial corruptions. This setting unifies three challenging aspects of sequential decision-making:

1. Generalized Linear Models (GLMs): The expected reward for an arm $x_t \in \mathbb{R}^d$ follows a GLM, $E[r_t|x_t; \theta^\star] = \mu(\langle x_t, \theta^\star \rangle)$, where $\mu$ is a known inverse link function and $\theta^\star$ is an unknown parameter. This framework encompasses logistic, Poisson, and Gaussian linear bandits.
2. Heteroskedasticity: The reward variance is not constant but varies across arms and time steps. Specifically, $\text{Var}[r_t|x_t, \tau_t; \theta^\star] = g(\tau_t) \dot{\mu}(\langle x_t, \theta^\star \rangle)$, where $g(\tau_t)$ is a dispersion parameter that can be exogenously time-varying (e.g., in Gaussian bandits) or endogenously determined by the arm choice (e.g., in logistic/Poisson bandits).
3. Adversarial Corruptions: An adaptive adversary manipulates the observed reward at each step $t$ by adding a corruption $c_t$, such that the learner observes $\tilde{r}_t = r_t + c_t$. The adversary operates under a total budget constraint $\sum_{t=1}^T |c_t| \le C$.

The goal is to minimize cumulative pseudo-regret, defined as the difference between the expected reward of the optimal arm and the chosen arm over $T$ rounds.

2. Methodology: HCW-GLB-OMD

The authors propose HCW-GLB-OMD (Hessian-Confidence Weighted GLB-OMD), an algorithm designed to be both computationally efficient and statistically optimal. The algorithm integrates two primary components:

A. Online Mirror Descent (OMD) Estimator

Unlike previous approaches that rely on batched Maximum Likelihood Estimation (MLE), which creates a time-index mismatch between local weights and global estimates, HCW-GLB-OMD utilizes an online OMD estimator. The parameter update at step $t$ is defined as:
$$\theta_{t+1} \leftarrow \arg \min_{\theta \in \Theta} \left[ \langle \nabla \tilde{\ell}_t(\theta_t), \theta - \theta_t \rangle + \frac{1}{2} \|\theta - \theta_t\|^2_{\nabla^2 \tilde{\ell}_t(\theta_t)} + \frac{1}{2\eta} \|\theta - \theta_t\|^2_{H_t} \right]$$
where $\tilde{\ell}_t$ is a weighted negative log-likelihood. This online approach ensures that the estimator, the arm, and the weights are aligned at the same local time step, facilitating rigorous analysis of corruption impacts.

B. Hessian-Based Confidence Weights

To achieve robustness against corruptions, the algorithm assigns a confidence weight $w_t$ to each observation based on the local Hessian (curvature) of the link function and the dispersion parameter:
$$w_t = \min \left\{ 1, \frac{\alpha g(\tau_t)}{\|x_t\|_{H_t^{-1}}} \right\}$$
Here, $\|x_t\|_{H_t^{-1}}$ quantifies the uncertainty along the direction of $x_t$.

• Mechanism: If an arm direction is highly uncertain (large norm in the inverse Hessian) relative to the dispersion, the weight $w_t$ is reduced ($<1$). This downweights observations from directions vulnerable to adversarial manipulation.
• Curvature Awareness: Unlike linear bandit methods that use a design matrix, this method uses the Hessian $\nabla^2 \tilde{\ell}_t$, which incorporates the local slope $\dot{\mu}$. This allows the algorithm to adapt to the specific geometry of the GLM (e.g., the saturation in logistic bandits).

C. Corruption-Robust Confidence Sequences

The authors construct a confidence set $C_t(\delta)$ that accounts for both estimation error and adversarial corruption. The radius of this set includes an additive term proportional to the corruption budget $C$:
$$C_t(\delta) \equiv \{ \theta \in \Theta : \|\theta - \theta_t\|_{H_t} \le \beta_t(\delta) + 2\eta\alpha C \}$$
The proof of this sequence relies on a supermartingale argument applied to a weighted likelihood ratio, utilizing the concavity of the mapping $x \mapsto x^{w_t}$ to handle cases where $w_t < 1$.

3. Key Contributions and Results

A. Regret Upper Bound

The paper establishes a regret upper bound for HCW-GLB-OMD under the assumption that the link function $\mu$ is self-concordant (Assumption 3). With probability at least $1-\delta$, the regret is bounded by:
$$\text{Reg}(T) \lesssim \log d \left( \sqrt{\sum_{t=1}^T g(\tau_t) \dot{\mu}_{t,\star}} + d^2 g_{\max} \kappa + d(g_{\max} + \kappa)C \right)$$
Where:

• $\dot{\mu}_{t,\star} = \dot{\mu}(\langle x_{t,\star}, \theta^\star \rangle)$ is the slope of the link function at the optimal arm.
• $g_{\max} = \max_t g(\tau_t)$ is the maximum dispersion.
• $\kappa = (\min_{x,\theta} \dot{\mu}(\langle x, \theta \rangle))^{-1}$ is the curvature parameter.
• $C$ is the total corruption budget.

Significance of the Bound:

• Instance-Wise Optimality: The leading term $\sqrt{\sum g(\tau_t) \dot{\mu}_{t,\star}}$ depends on the actual slope at the optimal arm, rather than the worst-case curvature $\kappa$. This matches the minimax lower bound for corruption-free GLBs.
• Corruption Robustness: The corruption term scales linearly with $C$ (specifically $d(g_{\max} + \kappa)C$), which is minimax optimal up to a curvature factor $\kappa$.
• Unification: The bound simultaneously recovers state-of-the-art results for heteroskedastic linear bandits, logistic bandits, and Poisson bandits.

B. Unified Regret Lower Bound

The authors prove a unified lower bound for any self-concordant heteroskedastic GLB with adversarial corruptions:
$$\Omega \left( d \sqrt{\sum_{t=1}^T g(\tau_t) \dot{\mu}_{t,\star}} + dC \right)$$
This lower bound:

• Subsumes existing problem-specific lower bounds for logistic bandits, heteroskedastic linear bandits, and corrupted linear bandits.
• Confirms that the algorithm's leading term is instance-wise minimax optimal.
• Demonstrates that the corruption term $dC$ is unavoidable, though the upper bound currently includes an extra $\kappa$ factor in the corruption term ($d\kappa C$).

C. Computational Efficiency

A critical contribution is the algorithm's efficiency. By using the online OMD update and recursive Hessian updates, HCW-GLB-OMD achieves $O(1)$ space and time complexity per iteration. This contrasts with prior corruption-robust algorithms for GLMs (e.g., CR-Eluder-UCB, GAdaOFUL) which often require $O(t)$ complexity due to batch processing or complex confidence set constructions.

4. Significance and Claims

The paper claims to provide the first jointly efficient and optimal algorithm for heteroskedastic GLBs under adversarial corruptions. Its primary significance lies in:

1. Bridging the Gap: It resolves the trade-off between computational efficiency and statistical optimality in corrupted GLBs. Previous works either achieved optimality with high computational cost or efficiency with suboptimal regret bounds (often scaling with worst-case curvature $\kappa$).
2. Instance-Wise Optimality: The algorithm achieves regret bounds that adapt to the specific difficulty of the instance (via $\dot{\mu}_{t,\star}$) rather than relying on worst-case assumptions, even in the presence of corruptions.
3. Unified Framework: It offers a single theoretical framework that covers a broad spectrum of bandit problems (linear, logistic, Poisson, heteroskedastic) without requiring problem-specific algorithmic modifications.

The authors note a remaining gap: the corruption term in the upper bound scales with $d\kappa C$, whereas the lower bound is $dC$. They conjecture that the $\kappa$ factor in the corruption term is an artifact of the analysis and that an $O(dC)$ bound is achievable, but this remains an open problem. Additionally, the current analysis assumes the dispersion parameter $\tau_t$ is known to the learner; handling unknown $\tau_t$ is identified as a future direction.