Technical Summary: Nonlinear Bandit with Heavy-Tailed Noise

Problem Definition

This paper addresses the challenge of sequential decision-making in Generalized Linear Bandits (GLB) and Nonlinear Bandits (NB) under heavy-tailed noise conditions. Traditional bandit algorithms often assume light-tailed (e.g., sub-Gaussian) reward distributions, which fail in real-world scenarios like financial markets, personalized recommendations, and medical treatments where rewards exhibit heavy tails (e.g., Pareto or Student's t-distributions).

The core problem involves a learner selecting an action $X_t$ from a feasible set at each round $t$ to maximize cumulative expected reward. The reward model is defined as:
$$r_t = \mu(\langle X_t, \theta^* \rangle) + \varepsilon_t$$
where $\mu$ is a link function, $\theta^*$ is an unknown parameter, and $\varepsilon_t$ is noise with bounded $(1+\epsilon)$-th moments ($\epsilon \in (0, 1]$), rather than bounded variance. The goal is to minimize cumulative regret $R(T)$ while maintaining computational efficiency and robustness against outliers.

The paper extends this investigation to two more complex settings:

1. Piecewise GLB: Where the unknown parameter $\theta^*$ is piecewise constant across different regions of the action space.
2. General Nonlinear Bandits: Where the reward function $b(X)$ is a general nonlinear function, not restricted to a specific link function structure, potentially requiring "affine lifting" to map into a higher-dimensional linear space.

Methodology

The authors propose a series of algorithms based on the Online Mirror Descent (OMD) framework, utilizing an Extended Huber Loss to handle heavy-tailed noise.

1. GLB-EHM (Generalized Linear Bandit with Extended Huber Method)

• Core Mechanism: The algorithm replaces the standard Maximum Likelihood Estimation (MLE) with an extended Huber loss function. This loss combines the quadratic behavior of $L_2$ loss for small errors and linear behavior of $L_1$ loss for large errors, providing robustness against outliers.
• One-Pass Update: A key feature is the one-pass update mechanism. The algorithm updates parameters using the Sherman-Morrison formula and projection decomposition, achieving $O(1)$ computational complexity per round with respect to the time horizon $T$ (specifically $O(d^3)$ per step, independent of $T$).
• Parameter Elimination: The method introduces a specific parameter setting to eliminate the dependency on the sensitive parameter $\kappa$ (lower bound of the link function derivative) in the leading regret term, a dependency present in prior works.

2. PGLB-EHM (Piecewise GLB-EHM)

• Adaptation: For scenarios where the contextual characteristic $\theta^*$ is piecewise constant, the algorithm maintains separate estimations for each region $A_i$.
• Strategy: It employs a "distinguish and exploit" approach. By ensuring the optimal region yields a reward significantly higher (by a constant $a$) than suboptimal regions, the algorithm identifies the optimal area with a bounded time cost and focuses exploration there.

3. NB-EHM (Nonlinear Bandit with Extended Huber Method)

• Bisection Method: To handle general nonlinear reward functions $b(X)$, the algorithm employs a bisection method to recursively refine the feasible space (unit ball) into smaller subregions.
• Exploration Restriction: A critical component is the time limit $T(A) \propto 1/d(A)^2$ assigned to each region $A$, where $d(A)$ is the region's width. As regions become finer, the allowed exploration time increases, allowing estimation error to decrease automatically.
• Affine Lifting: For general nonlinear functions that do not naturally fit the piecewise structure, the paper utilizes an affine lifting approach. This transforms the problem into a higher-dimensional space where the function can be treated similarly to the special nonlinear case, allowing the NB-EHM framework to be applied.

Key Contributions

1. Robust GLB Algorithm (GLB-EHM): The paper introduces the first algorithm for GLB under heavy-tailed noise that achieves an almost optimal regret bound of $\tilde{O}(T^{\frac{1}{1+\epsilon}})$ while maintaining $O(1)$ computational complexity per round. It improves upon existing methods by removing the dependency on the parameter $\kappa$ in the leading coefficient.
2. Piecewise and Nonlinear Extensions: The authors successfully extend the robust framework to Piecewise GLB and a special class of Nonlinear Bandits. They prove that the regret order remains sublinear ($\tilde{O}(T^\alpha)$ with $\alpha < 1$) even when the underlying structure is piecewise constant or smooth nonlinear.
3. Theoretical Guarantees: The paper provides rigorous theoretical analysis, establishing high-probability confidence bounds for parameter estimation and deriving regret upper bounds that match known lower bounds (up to logarithmic factors) for the linear case.
4. Computational Efficiency: Unlike kernel-based or neural network approaches for nonlinear bandits which often suffer from $O(T^2)$ or $O(T^3)$ computational costs, the proposed methods maintain low computational complexity suitable for large-scale applications.

Results

• Theoretical Bounds:
  • For GLB-EHM, the regret is bounded by $\tilde{O}(d(1+KS)\nu T^{\frac{1}{1+\epsilon}})$, which is nearly optimal compared to the lower bound $\Omega(dT^{\frac{1}{1+\epsilon}})$.
  • For PGLB-EHM, the regret order remains $\tilde{O}(T^{\frac{1}{1+\epsilon}})$, with constants depending on the number of pieces $m$ and the gap $a$.
  • For NB-EHM, the regret is bounded by $\tilde{O}(T^\alpha)$, where $\alpha = \frac{\gamma+1}{\gamma+2} + \frac{(d+2)(1-\epsilon)}{2(\gamma+2)(1+\epsilon)}$ and $\gamma = (d+2)(C_2-1)+1$. Under specific conditions ($\epsilon > \frac{d}{d+4}$), this ensures a sublinear regret.
• Empirical Performance: Numerical simulations were conducted for all proposed algorithms.
  • GLB-EHM was tested on a logit model with Student's t-distributed noise, demonstrating robust performance with an average runtime of 11.25 seconds.
  • NB-EHM simulations showed convergence to the optimal point and sublinear regret growth, validating the theoretical analysis.

Significance and Claims

The paper claims that its primary significance lies in bridging the gap between statistical efficiency and computational complexity in the context of heavy-tailed nonlinear bandits.

• Robustness: It demonstrates that robustness to heavy-tailed noise can be achieved without sacrificing the sublinear regret guarantees typical of light-tailed settings.
• Generality: By moving beyond the restrictive assumptions of Generalized Linear Models (GLM), Reproducing Kernel Hilbert Spaces (RKHS), or Neural Tangent Kernels (NTK), the proposed NB-EHM offers a more general framework for nonlinear bandits.
• Scalability: The $O(1)$ per-round complexity (relative to $T$) makes these algorithms scalable for long time horizons, addressing a major bottleneck in existing nonlinear bandit methods.

The authors conclude that while they have established sublinear regret bounds, future work is needed to establish regret lower bounds for the general nonlinear case and to relax assumptions such as Lipschitz continuity to Hölder continuity.