提出高效算法解决大规模推荐中的多物品选择问题，兼顾低延迟与高收益。
Efficient Algorithms for Logistic Contextual Slate Bandits with Bandit Feedback
- 通过局部规划实现每轮仅需多项式时间复杂度
- 在多样性假设下理论证明后悔值仅为亚线性增长（√T）
- 适用于大模型提示词优化，实测效果优于现有方法
我们研究了逻辑上下文滑板强化学习问题：每轮从指数级候选滑板集合（大小为2^Ω(N)）中选择一个包含N个物品的滑板，仅观察到由逻辑模型决定的单个二值奖励。目标是在T轮内最大化累积奖励，同时保持每轮计算成本较低。本文提出两种算法Slate-GLM-OFU和Slate-GLM-TS，通过独立槽位选择实现每轮时间复杂度N^{O(1)}，并通过联合参数估计实现低后悔。在广泛合成实验中，算法始终优于现有基线，达到最低后悔值与最快运行速度。进一步应用于语言模型提示词中上下文示例的选择，在情感分析等二分类任务上取得具有竞争力的测试准确率，具备实际应用潜力。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。