CONTEXTUAL SLATE GLM BANDITS WITH LIMITED ADAPTIVITY

In online slate bandit problems, a learner must select a slate of items across multiple slots to maximize a cumulative reward. While fully adaptive algorithms exist, they are often impractical for web-scale applications due to the high frequency of parameter updates. This paper addresses the challenge of designing computationally efficient algorithms for contextual slate bandits with generalized linear model (GLM) rewards that operate under limited adaptivity, specifically in batched and rarely-switching settings.

The authors introduce two primary algorithms:

• B-SlateGLinCB: A batched algorithm that partitions the time horizon into O(log log T) batches, where the policy is updated only between batches. This design enables parallelization of rounds within each batch.
• RS-SlateGLinCB: A rarely-switching algorithm that adaptively triggers parameter updates only when the determinant of the design matrix grows significantly, resulting in O(Nd log T) total updates.

Both algorithms utilize a slot-level decomposition to maintain computational efficiency, requiring only poly(N) time per round, which avoids the exponential complexity of iterating over all possible slates. They also employ a scaling technique using a 'scaling-slate' to ensure the regret bounds are independent of the non-linearity parameter κ, a common bottleneck in GLM bandit analysis.

Under a diversity assumption on the item sequences, the authors prove that B-SlateGLinCB and RS-SlateGLinCB achieve regret bounds of O(Nd^3/2 sqrt(T)) and O(Nd sqrt(T)), respectively. These bounds are optimal in terms of the time horizon T and notably avoid the κ-dependency typically found in GLM bandit regret. Empirically, the algorithms outperform existing limited-adaptivity baselines. The authors also propose a heuristic modification, B-SlateGLinCB+, which performs competitively with the state-of-the-art fully adaptive algorithm (Slate-GLM-OFU) and demonstrates strong performance in practical prompt-tuning tasks for language models.