Efficient Algorithms for Logistic Contextual Slate Bandits with Bandit Feedback
This work provides efficient algorithms for contextual slate bandit problems, which are relevant for applications like recommendation systems and in-context learning for large language models, offering improved regret and runtime performance.
This paper addresses the Logistic Contextual Slate Bandit problem, where an agent selects a slate of N items from an exponentially large set and observes a single binary reward based on a logistic model. The proposed algorithms, Slate-GLM-OFU and Slate-GLM-TS, achieve N^O(1) per-round time complexity and, under a diversity assumption, Slate-GLM-OFU incurs O(sqrt(T)) regret, consistently outperforming state-of-the-art baselines in synthetic experiments.
We study the Logistic Contextual Slate Bandit problem, where, at each round, an agent selects a slate of $N$ items from an exponentially large set (of size $2^{Ω(N)}$) of candidate slates provided by the environment. A single binary reward, determined by a logistic model, is observed for the chosen slate. Our objective is to develop algorithms that maximize cumulative reward over $T$ rounds while maintaining low per-round computational costs. We propose two algorithms, Slate-GLM-OFU and Slate-GLM-TS, that accomplish this goal. These algorithms achieve $N^{O(1)}$ per-round time complexity via local planning (independent slot selections), and low regret through global learning (joint parameter estimation). We provide theoretical and empirical evidence supporting these claims. Under a well-studied diversity assumption, we prove that Slate-GLM-OFU incurs only $\tilde{O}(\sqrt{T})$ regret. Extensive experiments across a wide range of synthetic settings demonstrate that our algorithms consistently outperform state-of-the-art baselines, achieving both the lowest regret and the fastest runtime. Furthermore, we apply our algorithm to select in-context examples in prompts of Language Models for solving binary classification tasks such as sentiment analysis. Our approach achieves competitive test accuracy, making it a viable alternative in practical scenarios.