Abstract
This work studies linear bandits under a new notion of gap-adjusted misspecification and is an extension of Liu et al. (2023). When the underlying reward function is not linear, existing linear bandits work usually relies on a uniform misspecification parameter ε that measures the sup-norm error of the best linear approximation. This results in an unavoidable linear regret whenever ε > 0. We propose a more natural model of misspecification which only requires the approximation error at each input x to be proportional to the suboptimality gap at x. It captures the intuition that, for optimization problems, near-optimal regions should matter more and we can tolerate larger approximation errors in suboptimal regions. Quite surprisingly, we show that the classical LinUCB algorithm -- designed for the realizable case -- is automatically robust against such ρ-gap-adjusted misspecification with parameter ρ diminishing at O(1/(d √log T)). It achieves a near-optimal O(√T) regret for problems that the best-known regret is almost linear in time horizon T. We further advance this frontier by presenting a novel phased elimination-based algorithm whose gap-adjusted misspecification parameter ρ = O(1/√d) does not scale with T. This algorithm attains optimal O(√T) regret and is deployment-efficient, requiring only log T batches of exploration. It also enjoys an adaptive O(log T) regret when a constant suboptimality gap exists. Technically, our proof relies on a novel self-bounding argument that bounds the part of the regret due to misspecification by the regret itself, and a new inductive lemma that limits the misspecification error within the suboptimality gap for all valid actions in each batch selected by G-optimal design.