Abstract: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^{\Omega(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.
| Comments: | Accepted to UAI 2025 |
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2506.13163 [cs.LG] |
| (or arXiv:2506.13163v3 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2506.13163 arXiv-issued DOI via DataCite |
From: Tanmay Goyal [view email]
[v1]
Mon, 16 Jun 2025 07:19:02 UTC (5,162 KB)
[v2]
Sat, 7 Mar 2026 08:27:28 UTC (5,163 KB)
[v3]
Tue, 12 May 2026 14:00:40 UTC (10,327 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。