提出无需投影的推荐算法，效率更高且更鲁棒。
Simple Projection-Free Algorithm for Contextual Recommendation with Logarithmic Regret and Robustness
- 利用推荐任务的非正规性，避免复杂投影计算。
- 达到与已有方法相当的 $O(d\ log T)$ regret 界。
- 天然抗次优反馈，适合实际应用中不完美数据场景。
上下文推荐是上下文线性老虎机的一种变体，学习者观测到的是（最优）动作而非标量奖励。近期 Sakaue 等人（2025）提出了高效的在线牛顿步（ONS）方法，实现了 $O(d\log T)$ 的后悔界，其中 $d$ 为动作空间维度，$T$ 为时间范围。本文提出一种更简单的算法，比基于 ONS 的方法更高效，同时保持相同的后悔界。核心思想是利用上下文推荐中固有的非正规性，得到类似在线分类中二阶感知机的更新规则，从而消除 ONS 所需的马氏距离投影步骤，该步骤常为计算瓶颈。更重要的是，同一算法在面对可能次优的动作反馈时仍具鲁棒性，而此前基于 ONS 的方法需运行多个不同学习率的 ONS 学习器才能实现此扩展。我们还描述了该方法在一般希尔伯特空间（例如通过核化）中的适用性，此时消除马氏投影更具优势。
原文摘要 · Abstract (English)
Contextual recommendation is a variant of contextual linear bandits in which the learner observes an (optimal) action rather than a reward scalar. Recently, Sakaue et al. (2025) developed an efficient Online Newton Step (ONS) approach with an $O(d\log T)$ regret bound, where $d$ is the dimension of the action space and $T$ is the time horizon. In this paper, we present a simple algorithm that is more efficient than the ONS-based method while achieving the same regret guarantee. Our core idea is to exploit the improperness inherent in contextual recommendation, leading to an update rule akin to the second-order perceptron from online classification. This removes the Mahalanobis projection step required by ONS, which is often a major computational bottleneck. More importantly, the same algorithm remains robust to possibly suboptimal action feedback, whereas the prior ONS-based method required running multiple ONS learners with different learning rates for this extension. We describe how our method works in general Hilbert spaces (e.g., via kernelization), where eliminating Mahalanobis projections becomes even more beneficial.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。