解决推荐系统中组合选择的偏好反馈问题,实现高效学习与最优决策。
Combinatorial Reinforcement Learning with Preference Feedback
- 基于上下文MNL模型,用函数逼近物品价值,融合偏好反馈进行组合优化。
- 提出MNL-VQL算法,在线性MDP下达到近似极小最大遗憾,首次建立该框架下理论下界。
- 适用于长期用户互动场景,如推荐系统和在线广告,兼具计算与统计效率。
本文研究带有偏好反馈的组合强化学习,其中智能体逐轮向用户推荐多个物品组成的组合,用户的偏好遵循多项式逻辑(MNL)模型。该框架可建模真实世界中的长期用户参与场景,如推荐系统和在线广告。然而,该框架面临两大挑战:(1) 物品价值未知,不同于传统MNL老虎机仅处理单步偏好反馈;(2) 在物品价值未知的组合动作空间中,难以同时保证乐观性与可计算的组合选择。本文假设上下文MNL偏好模型,其均值效用为线性形式,物品价值由一般函数近似。我们提出算法MNL-VQL,有效应对上述挑战,具备计算与统计双重高效性。作为特例,对于线性MDP(带MNL偏好反馈),我们建立了该框架下的首个遗憾下界,并证明MNL-VQL达到近似极小最大遗憾。据我们所知,这是首个在组合强化学习与偏好反馈框架中提供统计保障的工作。
原文摘要 · Abstract (English)
In this paper, we consider combinatorial reinforcement learning with preference feedback, where a learning agent sequentially offers an action--an assortment of multiple items to--a user, whose preference feedback follows a multinomial logistic (MNL) model. This framework allows us to model real-world scenarios, particularly those involving long-term user engagement, such as in recommender systems and online advertising. However, this framework faces two main challenges: (1) the unknown value of each item, unlike traditional MNL bandits that only address single-step preference feedback, and (2) the difficulty of ensuring optimism while maintaining tractable assortment selection in the combinatorial action space with unknown values. In this paper, we assume a contextual MNL preference model, where the mean utilities are linear, and the value of each item is approximated by a general function. We propose an algorithm, MNL-VQL, that addresses these challenges, making it both computationally and statistically efficient. As a special case, for linear MDPs (with the MNL preference feedback), we establish the first regret lower bound in this framework and show that MNL-VQL achieves nearly minimax-optimal regret. To the best of our knowledge, this is the first work to provide statistical guarantees in combinatorial RL with preference feedback.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。