Nonlinear Bandit

Research Overview

This paper addresses the challenge of sequential decision-making in environments where reward distributions are heavy-tailed and relationships between context and reward are nonlinear. Traditional methods, such as those relying on maximum likelihood estimation (MLE), are often sensitive to noise, leading to biased parameter estimates and poor performance. To overcome this, the authors propose the Extended Huber loss Method (EHM), which combines the robustness of Huber loss with the efficiency of online mirror descent.

The core of the proposed solution is the EHM algorithm, which replaces standard loss functions with an extended Huber loss. This modification allows the algorithm to maintain robustness against heavy-tailed noise without requiring the computational overhead of traditional kernel-based or neural bandit methods. The authors extend this framework to three scenarios:

1. Generalized Linear Bandits (GLB): Achieving near-optimal regret bounds while eliminating the need for certain sensitive parameters.
2. Piecewise GLB: Handling contexts where the underlying parameter is piecewise constant by maintaining separate estimations for different regions.
3. Nonlinear Bandits (NB): Utilizing a bisection method and affine lifting to extend the robust estimation framework to more general nonlinear reward structures.

Balancing statistical robustness with computational efficiency is a central problem in online learning. By providing an algorithm that achieves sublinear regret in noisy, heavy-tailed environments with O(1) per-round complexity, this work offers a scalable alternative to existing methods that often suffer from high computational costs or restrictive structural assumptions. The approach is particularly relevant for real-world applications like personalized recommendation systems and financial modeling, where data is frequently noisy and non-Gaussian.