首个具备帕累托最优保证的多目标线性上下文算法，有效平衡多个冲突目标。
Thompson Sampling for Multi-Objective Linear Contextual Bandit
- 通过采样参数构建动态有效帕累托前沿，避免每轮重算帕累托前沿。
- 理论证明最坏情况帕累托累计损失为 $ ilde{O}(d^{3/2} oot{T})$，与单目标最优阶一致。
- 适合需同时优化多个冲突目标的推荐系统、个性化医疗等场景。
我们研究多目标线性上下文老虎机问题，即需同时优化多个相互冲突的目标。提出 exttt{MOL-TS}，这是首个在该问题上具备帕累托后悔保证的汤普森采样算法。不同于传统方法每轮计算经验帕累托前沿， exttt{MOL-TS} 在各目标参数上采样，并从一个新颖的「有效帕累托前沿」中高效选择臂，该前沿考虑了历史重复选择的影响。分析表明， exttt{MOL-TS} 的最坏情况帕累托后悔界为 $ ilde{O}(d^{3/2} oot{T})$，其中 $d$ 为特征向量维度，$T$ 为总轮数，与单目标随机线性老虎机算法的最佳已知阶数相同。实验验证了该方法的优势，展示了更优的后悔最小化和强劲的多目标性能。
原文摘要 · Abstract (English)
We study the multi-objective linear contextual bandit problem, where multiple possible conflicting objectives must be optimized simultaneously. We propose \texttt{MOL-TS}, the \textit{first} Thompson Sampling algorithm with Pareto regret guarantees for this problem. Unlike standard approaches that compute an empirical Pareto front each round, \texttt{MOL-TS} samples parameters across objectives and efficiently selects an arm from a novel \emph{effective Pareto front}, which accounts for repeated selections over time. Our analysis shows that \texttt{MOL-TS} achieves a worst-case Pareto regret bound of $\widetilde{O}(d^{3/2}\sqrt{T})$, where $d$ is the dimension of the feature vectors, $T$ is the total number of rounds, matching the best known order for randomized linear bandit algorithms for single objective. Empirical results confirm the benefits of our proposed approach, demonstrating improved regret minimization and strong multi-objective performance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。