Nonlinear Bandit

2026-07-09 · Source: cs.LG updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Mathematics & Computational Sciences · Depth: Expert, extended

Summary

This paper introduces novel algorithms for generalized linear bandit (GLB) and nonlinear bandit (NB) problems, specifically addressing scenarios with heavy-tailed noise. The Generalized Linear Bandit with Extended Huber loss Method (GLB-EHM) is proposed, utilizing an adaptive Huber loss and online mirror descent for one-pass updates. It achieves a near-optimal regret of \"\u00d5(T^(1/(1+\u03b5)))\" with \u00d5(1) computational complexity, removing dependency on the \u03ba parameter. The PGLB-EHM algorithm extends this to piecewise constant contextual characteristics, maintaining the same regret order. For nonlinear bandits, the NB-EHM algorithm employs a bisection method and affine lifting to achieve a sublinear regret bound of \"\u00d5(T^\u03b1)\", where \u03b1 is a complex exponent dependent on d, C2, and \u03b5. Numerical simulations confirm the theoretical results for all algorithms.

Key takeaway

For research scientists and machine learning engineers developing online decision-making systems in noisy environments, these Huber loss-based bandit algorithms offer robust and efficient alternatives. You should consider GLB-EHM or NB-EHM when dealing with heavy-tailed reward distributions, as they provide strong theoretical regret guarantees with low computational overhead, potentially improving model stability and performance in real-world applications.

Key insights

Huber loss-based algorithms provide robust, computationally efficient solutions for heavy-tailed generalized linear and nonlinear bandits.

Principles

• Adaptive Huber loss enhances robustness against heavy-tailed noise.
• Online mirror descent enables \u00d5(1) one-pass updates.
• Affine lifting extends specific nonlinear bandit solutions to general cases.

Method

The EHM algorithm uses online mirror descent with adaptive Huber loss for one-pass updates. NB-EHM refines feasible space via bisection and applies affine lifting for general nonlinear problems.

In practice

• Applicable in personalized recommendation systems.
• Useful for financial market predictions.
• Relevant for medical treatment optimization.

Topics

• Generalized Linear Bandits
• Nonlinear Bandits
• Heavy-tailed Noise
• Huber Loss
• Online Mirror Descent
• Regret Minimization

Best for: AI Scientist, Research Scientist, Machine Learning Engineer

Related on AIssential

• Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards — Asymptotically optimal bandit algorithms can still exhibit heavy regret tails, necessitating tail behavior analysis.
• Bandit PCA with Minimax Optimal Regret — A novel algorithm achieves minimax optimal regret for Bandit PCA by combining online mirror descent with layered, epoch-based exploration.
• Online LLM Selection via Constrained Bandits with Time-Varying Demand — Online LLM selection under dynamic demand and hard/soft constraints can be optimized using constrained bandit learning.
• Deterministic Pareto-Optimal Policy Synthesis for Multi-Objective Reinforcement Learning — The new Bellman operator computes deterministic Pareto-optimal policies for MOMDPs, capturing complex trade-offs.
• Impatient Bandits: Optimizing for the Long-Term Without Delay — Progressive feedback enables long-term optimization in delayed reward bandit problems by leveraging incrementally revealed information.
• Constrained user-item allocation for e-commerce marketing campaigns — Constrained spectral biclustering effectively auto-targets e-commerce campaigns by jointly optimizing user-item allocation for quality and fairness.

See Counsel's argued verdicts on the open AI decisions leaders are weighing →

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.LG updates on arXiv.org.