Generalized Linear Bandits with Limited Adaptivity

Many real-world applications of contextual bandits, such as clinical trials and online advertising, face the challenge of limited adaptivity, where frequent policy updates are infeasible. Existing algorithms often struggle with this constraint or fail to provide strong theoretical guarantees. This paper addresses this limitation by studying the contextual bandit problem with generalized linear reward models. The problem is particularly challenging due to instance-dependent non-linearity parameters that can significantly affect the performance of algorithms.

The researchers propose two novel algorithms, B-GLinCB and RS-GLinCB, to tackle the problem. B-GLinCB is designed for a setting where the update rounds must be decided upfront. RS-GLinCB addresses a more general setting where the algorithm can adaptively choose when to update its policy. Both algorithms achieve optimal regret guarantees (Õ(√T)), notably eliminating the dependence on the instance-dependent non-linearity parameter. This is a significant improvement over previous algorithms, which often have sub-optimal regret bounds. The algorithms also demonstrate computational efficiency, making them practically feasible for various real-world applications.