Thompson Sampling for Multi-Objective Linear Contextual Bandit¶

会议: NeurIPS 2025
arXiv: 2512.00930
代码: 无
领域: 强化学习
关键词: Thompson采样, 多目标优化, 上下文Bandit, Pareto最优, 有效Pareto前沿

一句话总结¶

提出MOL-TS——首个具有worst-case Pareto regret理论保证的多目标线性上下文Bandit Thompson Sampling算法，通过定义"有效Pareto最优臂"概念和乐观采样策略，实现\(\widetilde{O}(d^{3/2}\sqrt{T})\)的regret上界，目标数\(L\)仅增加\(O(\log L)\)因子。

研究背景与动机¶

多目标Bandit的实际需求：在推荐系统、在线广告、资源分配等实际场景中，决策者常常需要同时优化多个可能冲突的目标（如点击率、用户满意度、收入等）。多目标多臂Bandit（MOMAB）通过Pareto最优框架处理这种多目标权衡——拉动一个臂获得的是一个奖励向量而非单一标量值，不存在单一的"最佳"臂。

UCB主导的理论格局：现有所有带Pareto regret保证的MOMAB算法均基于UCB策略（如ParetoUCB、MOGLM-UCB等），理论分析相对直接因为UCB的确定性上界天然保证乐观性。然而在单目标Bandit中，Thompson Sampling（TS）凭借其随机探索的优雅性和实证上的优越性能（往往超过UCB），已成为最受欢迎的算法之一。将TS扩展到多目标设定一直是一个公认的理论难题。

多目标TS的核心技术困难：TS的worst-case regret分析依赖于"采样参数以至少常数概率是乐观的"这一性质。在单目标中，单次采样的乐观概率为常数\(\tilde{p}\)。但在多目标设定中，需要所有\(L\)个目标同时乐观，朴素TS（每目标采样一次，\(M=1\)）的联合乐观概率为\(\tilde{p}^L\)——随目标数指数下降，导致regret随\(L\)指数增长，完全失去理论意义。

标准Pareto最优的局限：作者还发现了Pareto regret定义本身的缺陷——一个仅从标准Pareto前沿随机选择臂的策略可以获得零Pareto regret，但其累积奖励可能远劣于另一个同样零regret的策略。这是因为标准Pareto最优只比较单个臂之间的支配关系，忽略了通过混合选择（凸组合）可能获得的更优累积表现。这一缺陷在长期运行中会越来越严重。

方法详解¶

整体框架¶

MOL-TS是一个基于正则化最大似然估计的多目标线性Thompson Sampling算法。每轮\(t\)：(1) 对每个目标\(\ell\)独立采样\(M\)个参数向量；(2) 对每个目标用最大值进行乐观评估；(3) 构建有效Pareto前沿并均匀随机选择一个臂；(4) 观测奖励向量并更新参数估计。

关键设计¶

有效Pareto最优臂（Effective Pareto Optimal Arm）:
- 功能：定义一种比标准Pareto最优更严格的最优性概念，确保重复选择某臂的累积奖励也是Pareto最优的
- 核心思路：标准Pareto最优要求臂\(a^*\)的奖励向量\(\boldsymbol{\mu}_{a^*}\)不被任何单个臂支配；有效Pareto最优要求\(\boldsymbol{\mu}_{a^*}\)不被其他臂的任意凸组合支配："\(\forall \beta \in \mathcal{S}^{|\mathcal{A}|-1}: \boldsymbol{\mu}_{a^*} \not\prec \sum_{a \neq a^*} \beta_a \boldsymbol{\mu}_a\)"。因此有效Pareto前沿\(\mathcal{C}^*\)是标准Pareto前沿\(\mathcal{P}^*\)的子集。关键定理建立了对偶关系：有效Pareto最优臂\(\Leftrightarrow\)存在权重向量\(\boldsymbol{w}\)使其为线性标量化最优
- 设计动机：论文通过具体反例展示了标准Pareto regret的不足——两个策略都只选Pareto最优臂获得零regret，但累积奖励相差显著（如[1.3,1.3] vs [1.6,1.7]）。有效Pareto最优保证了长期运行中不会被"混合策略"支配
乐观采样策略（Optimistic Sampling）:
- 功能：通过每目标多次采样并取最大值，解决多目标TS中联合乐观概率指数衰减的核心难题
- 核心思路：对每个目标\(\ell\)从高斯后验\(\mathcal{N}(\hat{\theta}_t^{(\ell)}, c^2 V_t^{-1})\)独立采样\(M\)个参数\(\tilde{\theta}_{t,1}^{(\ell)}, \ldots, \tilde{\theta}_{t,M}^{(\ell)}\)，用最大值评估奖励\(\tilde{\mu}_{t,a}^{(\ell)} = \max_{m} x_{t,a}^\top \tilde{\theta}_{t,m}^{(\ell)}\)。当\(M \geq 1 - \frac{\log L}{\log(1-\tilde{p})}\)时（即\(M = O(\log L)\)），所有目标同时乐观的概率保持常数\(p \geq 0.15\)
- 设计动机：\(M=1\)时乐观概率为\(\tilde{p}^L\)（指数衰减），\(M=O(\log L)\)时概率为\((1-(1-\tilde{p})^M)^L\)（常数）。这是因为每目标\(M\)次独立采样中至少有一次乐观的概率为\(1-(1-\tilde{p})^M\)，当\(M\)足够大时该值趋近1，\(L\)次方后仍保持常数。这个设计以\(O(M \cdot L) = O(L \log L)\)的采样代价换取了指数改善的理论保证
有效Pareto前沿的估计与臂选择:
- 功能：基于乐观评估的奖励向量构建经验有效Pareto前沿，并从中均匀随机选择一个臂
- 核心思路：用乐观评估奖励\(\tilde{\boldsymbol{\mu}}_{t,a}\)替代真实奖励，构建估计的有效Pareto前沿\(\tilde{\mathcal{C}}_t = \{a \in \mathcal{A} \mid \tilde{\boldsymbol{\mu}}_{t,a} \not\prec \sum_{a'} \beta_{a'} \tilde{\boldsymbol{\mu}}_{t,a'}, \forall \beta \in \mathcal{S}^{|\mathcal{A}|}\}\)。不同于UCB方法需要显式计算经验Pareto前沿，MOL-TS只需从前沿中随机选择一个臂，计算效率更高
- 设计动机：通过Theorem 1的对偶性，从有效Pareto前沿选择等价于对某个随机权重向量\(\boldsymbol{w}_t\)取线性标量化最优，无需穷举所有权重方向

损失函数 / 训练策略¶

参数估计使用正则化最小二乘（RLS）：\(V_t = \sum_{s=1}^{t-1} x_{s,a_s} x_{s,a_s}^\top + \lambda I\)，\(\hat{\theta}_t^{(\ell)} = V_t^{-1} \sum_{s=1}^{t-1} x_{s,a_s} r_{s,a_s}^{(\ell)}\)。每轮所有目标共享同一gram矩阵\(V_t\)（因为观测到的是同一臂的context），但分别维护奖励累积和\(Z_t^{(\ell)}\)。超参数\(\lambda\)为正则化系数，\(c\)控制采样方差、通常设为与置信区间宽度\(c_{1,t}(\delta)\)一致。关键理论参数设定：置信区间宽度\(c_{1,t}(\delta) = R\sqrt{d\log\frac{1+(t-1)/(\lambda d)}{\delta/L}} + \lambda^{1/2}\)，其中\(O(\sqrt{\log L})\)依赖不可避免（需在所有目标上联合成立）；采样次数\(M = \lceil 1 - \frac{\log L}{\log(1-p)}\rceil\)（\(p=0.15\)时常数量级），确保乐观概率不随\(L\)指数衰减。

实验关键数据¶

主实验¶

设定：\(K=50\)臂，\(d=5\)维，\(L=4\)目标，\(T=10000\)轮，10个独立实例

算法	Pareto Regret	Effective Pareto Regret	Obj1累积奖励	Obj2累积奖励
MOL-TS (\(M=O(\log L)\))	最低	最低	最高	最高
MOL-UCB	中等	中等	中等	中等
MOL-\(\epsilon\)-Greedy	最高	最高	混合（部分目标偏高但不一致）	混合
MOL-TS (\(M=1\))	略高于\(M=O(\log L)\)	略高	略低	略低

消融实验¶

配置	Pareto Regret	说明
MOL-TS, \(M=1\)	较高	朴素TS，乐观概率指数衰减
MOL-TS, \(M=O(\log L)\)	最低	乐观采样恢复常数概率
MOL-UCB	高于MOL-TS	UCB确定性但不如TS灵活

关键发现¶

MOL-TS在Pareto regret和Effective Pareto Regret上均优于MOL-UCB和\(\epsilon\)-Greedy
有效Pareto前沿选择确实带来更高累积奖励——MOL-TS在所有4个目标上的累积奖励均最高
\(M = O(\log L)\)的乐观采样策略在实验中确实必要——\(M=1\)的性能明显劣于\(M=O(\log L)\)
MOL-\(\epsilon\)-Greedy出现反直觉现象：Pareto regret最高但某些目标的即时奖励可能偏高，这是因为它不区分有效Pareto前沿，随机选择导致累积奖励被"平均化"稀释

亮点与洞察¶

有效Pareto最优的概念解决了一个长期被忽视的问题：标准Pareto regret为零并不保证累积表现最优。这一新定义通过凸组合支配关系，精确描述了"重复选择也不会被混合策略打败"的严格最优性。直观理解为：有效Pareto前沿就是Pareto前沿的"凸包边界"，只有在边界上的点才值得长期选择
乐观采样的优雅解法：用\(O(\log L)\)次额外采样将指数衰减的联合乐观概率恢复为常数，以极低的计算代价（采样复杂度仅从\(O(L)\)增至\(O(L \log L)\)）获得了指数级的理论改善。这种"以对数代价换取指数收益"的技巧在计算机科学中反复出现（如union bound的\(\log\)因子），作者在Bandit context中的具体实现非常漂亮
对偶性定理的优雅：Theorem 1建立了有效Pareto最优臂与线性标量化最优臂的完美对应关系（来自多目标优化的经典结论），不仅简化了算法设计（从有效Pareto前沿选臂 ↔ 对某个权重向量取标量化最优），也为regret分析提供了关键的分解工具——将多目标regret降解为单目标regret的加权形式

局限与展望¶

计算有效Pareto前沿需要求解凸包相关问题，当臂数\(|\mathcal{A}|\)或目标数\(L\)很大时计算开销增加，影响实时性
实验设定相对简单（\(K=50, d=5, L=4\)），缺乏大规模或高维的经验验证，也没有在真实推荐系统等场景中测试
Regret bound中\(d^{3/2}\)依赖可能不是最优的——单目标TS的某些变体（如OFUL-TS）可以达到\(d\sqrt{T}\)，改进\(d^{3/2}\)因子是开放问题
假设各目标噪声独立且有界（sub-Gaussian），在实际中目标间往往存在正或负相关性，如何利用相关结构改进bound是自然延伸
有效Pareto前沿的概念依赖于均值奖励向量，对风险敏感的场景（关心方差或尾部风险）需要进一步扩展

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首个多目标TS的worst-case regret分析 + 有效Pareto最优这一新概念，双重理论贡献填补了重要空白
实验充分度: ⭐⭐⭐ 实验验证了理论主张但设定较简单，缺乏大规模验证和真实推荐系统等应用场景
写作质量: ⭐⭐⭐⭐ 理论推导严谨，反例和直觉解释到位，但符号系统略显繁重
价值: ⭐⭐⭐⭐ 填补了多目标Bandit理论的重要空白，对偶性定理和乐观采样技巧有广泛启发价值