Contextual Slate GLM Bandits with Limited Adaptivity

We investigate the contextual slate bandit problem with generalized linear rewards under limited adaptivity. At each round, the learner is presented with $N$ sets of items, where each item is represented by a $d$-dimensional feature vector. The learner then constructs a slate by selecting one item per set; the resulting slate yields a scalar reward sampled from a Generalized Linear Model (GLM). We propose algorithms under two limited-adaptivity settings: (a) Batched and (b) Rarely-Switching. For the batched setting, we introduce B-SlateGLinCB, which partitions the time horizon into $\mathcal{O}(\log\log T)$ batches such that each batch's policy relies only on data from previous batches. For the rarely-switching setting, we propose RS-SlateGLinCB, which adaptively performs only $\mathcal{O}(Nd\log T)$ parameter updates. Under a diversity assumption on the item sequences, we prove that B-SlateGLinCB and RS-SlateGLinCB achieve regret bounds of $\mathcal{O}(Nd^{3/2}\sqrt{T})$ and $\mathcal{O}(Nd\sqrt{T})$, respectively. Notably, both bounds are independent of the non-linearity parameter $\kappa$ that is typically found to scale the regret of GLM bandit algorithms. Our algorithms are computationally efficient, requiring only $\text{poly}(N)$ time per round despite $2^{\Omega(N)}$ possible slates. Simulations show our algorithms outperform existing baselines with limited adaptivity and remain competitive with Slate-GLM-OFU, a fully adaptive state-of-the-art algorithm. Notably, a slightly modified B-SlateGLinCB empirically matches this baseline. Finally, we demonstrate strong performance in a practical in-context example selection task for language models.

In this work, we study the Contextual GLM Slate Bandit problem, where at each round, the learner receives $N$ different item-sets, and is required to choose an item from each of the $N$ sets, resulting in an $N-$tuple, referred to as a slate. After selecting a slate, the learner receives a single feedback, sampled from a Generalized Linear Model with unknown parameters. The learner is required to minimize her regret at the end of $T$ rounds. However, the learner is constrained by limited adaptivity, i.e, the learner can only make $M$ updates to their policy, resulting in two different limited adaptivity settings: (a) Batched, where the learner has to fix the $M$ time rounds for making updates beforehand, and (b) Rarely-Switching, where the learner can choose when to update on-the-fly. Thus, for each of the settings, we develop efficient algorithms that do not iterate over the exponentially large set of arms (slates), while achieving optimal sublinear regret bounds of $O(\sqrt{T})$. Further, we empirically demonstrate that our algorithms significantly outperform existing baselines that accommodate limited adaptivity, and remain competitive with fully-adaptive algorithms (i.e, algorithms that can update their policy at each round). Finally, we apply our algorithms to the task of choosing in-context examples for prompt tuning for binary classification tasks, and show that they achieve strong performance.