1. 个性化多目标决策与偏好学习的核心挑战在现实世界的决策场景中我们很少只追求单一目标。无论是设计一个推荐系统需要在准确性、新颖性、多样性之间权衡规划机器人路径需要平衡时间、能耗和安全性还是进行医疗资源分配需兼顾效率、公平性和成本我们面对的都是典型的多目标决策问题。每个用户在这些目标上的权重——即他们的“偏好向量”——往往是未知且高度个性化的。传统方法要么假设一个统一的偏好要么要求用户明确指定复杂的权重这在实际中既困难又不自然。基于比较反馈的偏好学习其核心思想是绕开直接量化偏好的难题转而通过更符合人类直觉的“二选一”方式来探知用户偏好。例如不是问用户“你对响应速度和准确性的权重分别是多少”而是展示两个策略A和B的结果询问“你更喜欢哪一个”。这种反馈形式更自然噪声容忍度也更高。算法的任务就是利用一系列这样的二元比较高效地推断出用户的隐含偏好向量并据此找到最能满足其个性化需求的策略。这引出了几个核心挑战首先策略空间可能极其庞大甚至是连续的我们无法枚举所有策略供用户比较。其次用户的比较反馈可能存在噪声或不一致。最后我们希望在尽可能少的比较次数内以高概率找到接近最优的策略。本文将要深入剖析的算法正是针对这些挑战提供了一个具有理论保证的解决方案。它通过精心设计的交互协议将高维的偏好学习问题转化为在策略价值向量空间中的搜索问题并证明了其查询复杂度和策略性能的优越性。2. 算法框架与核心思想解析2.1 问题形式化从决策到几何我们首先将问题置于一个严格的数学框架中。假设我们有 $k$ 个需要优化的目标。每一个策略 $\pi$可以是一个推荐列表、一条机器人路径等在执行后会在这 $k$ 个目标上产生一个价值向量 $V_\pi \in \mathbb{R}^k$。例如$V_\pi[1]$ 代表策略 $\pi$ 在“准确性”上的得分$V_\pi[2]$ 代表“多样性”得分以此类推。用户的个性化偏好由一个未知的偏好向量 $w^* \in \mathbb{R}^k_$各分量非负来刻画。用户对策略 $\pi$ 的总体满意度由该策略的价值向量在其偏好方向上的投影即内积 $\langle w^, V_\pi \rangle$ 来决定。这个值越高说明策略越符合用户偏好。最优的个性化策略 $\pi^$ 就是最大化这个内积的策略 $$\pi^* \arg\max_{\pi \in \Pi} \langle w^, V_\pi \rangle.$$ 我们记最优价值为 $v^ \langle w^, V_{\pi^} \rangle$。算法的目标是在不知道 $w^$ 的情况下通过与用户的交互比较查询找到一个策略 $\hat{\pi}$使得其价值 $\langle w^, V_{\hat{\pi}} \rangle$ 尽可能接近 $v^*$。关键视角转换这个形式化过程完成了一次关键的视角转换。我们将寻找“最优策略”的问题转化为在价值向量空间 ${V_\pi: \pi \in \Pi}$ 中寻找在方向 $w^$ 上投影最大的点。偏好学习本质上就是估计这个方向 $w^$ 的过程。2.2 比较反馈作为查询 oracle算法与用户交互的基本单元是比较查询。给定两个策略 $\pi_A$ 和 $\pi_B$或其混合算法向用户呈现它们的结果或描述用户返回一个偏好 $\pi_A \succ \pi_B$喜欢A、$\pi_A \prec \pi_B$喜欢B或者“无法区分”。这个反馈模型非常实用因为它认知负担低用户只需做相对判断无需绝对评分。抗噪声能力强即使反馈有随机错误只要正确概率大于1/2算法依然可以工作。便于获取在许多场景如A/B测试、用户调研中这种数据天然存在。算法需要利用一系列这样的二元比较逐步逼近 $w^$。一个朴素的想法是直接估计 $w^$ 的每个分量但这需要用户对每个目标进行独立评估违背了“整体比较”的初衷。本文的算法采用了一种更巧妙的思路它不去直接估计 $w^$而是去估计一个能产生与 $w^$ 相同最优策略的替代权重向量 $\hat{w}$。2.3 算法核心构建与求解线性系统算法的核心步骤可以概括为以下三步步骤一探索价值空间的基础Algorithm 10为了理解策略价值向量的分布范围算法首先需要找到一组“基础策略” $\pi_1, \pi_2, ..., \pi_d$使得它们的价值向量 ${V_{\pi_1}, ..., V_{\pi_d}}$ 能够张成或近似张成整个价值空间 $\text{span}({V_\pi: \pi \in \Pi})$。这里的 $d$ 是该空间的维度$d \le k$。如何找到这些基础策略算法采用了一种迭代的、基于比较的探索方法。它从一组标准正交基向量 ${e_1, ..., e_k}$对应 $k$ 个纯目标方向出发。对于每个方向 $e_i$算法通过与用户交互找到一个在该方向上表现近似最优的策略 $\tilde{\pi}i$即 $\tilde{\pi}i \approx \arg\max{\pi} \langle e_i, V\pi \rangle$。这个过程本身可以通过带噪声的二分搜索或锦标赛式的比较来完成。最终我们从这 $k$ 个策略中选取价值向量线性无关的一个子集 ${\pi_1, ..., \pi_d}$ 作为基础。实操心得在实际部署中寻找“纯目标最优”策略 $\tilde{\pi}_i$ 可能本身就是一个优化问题。我们可以使用现有的、针对单目标的优化器来获得近似解。关键在于这些基础策略不需要是全局最优的只要它们能提供足够“分散”的价值向量来撑开整个空间即可。维度 $d$ 通常远小于 $k$这反映了目标之间往往存在相关性。步骤二估计基础比率Algorithm 26这是算法最精妙的部分。我们已经有了基础策略 $\pi_1, ..., \pi_d$。根据线性代数的知识如果 $w^$ 已知那么对于任意 $i \in [d-1]$存在一个标量 $\alpha_i$使得混合策略 $\alpha_i \pi_1 (1-\alpha_i)\pi_0$这里 $\pi_0$ 可以是一个零价值策略或某个参考策略与策略 $\pi_{i1}$ 在用户 $w^$ 看来是无差异的indifferent。即 $$\langle w^, V_{\pi_1} \rangle \alpha_i \langle w^, V_{\pi_{i1}} \rangle.$$ 然而我们不知道 $w^*$ 和 $\alpha_i$。算法的巧妙之处在于它通过比较查询来直接估计这些 $\alpha_i$。对于每个 $i$它构造一系列介于 $\pi_1$ 和 $\pi_{i1}$ 之间的混合策略通过调整系数并询问用户该混合策略与 $\pi_1$ 孰优孰劣。通过二分搜索算法可以找到一个估计值 $\hat{\alpha}_i$使得用户对混合策略 $\frac{1}{\hat{\alpha}i}\pi{i1} (1-\frac{1}{\hat{\alpha}_i})\pi_0$ 和 $\pi_1$ 感到“无法区分”。这个过程如图1所示。步骤三求解偏好向量并输出策略一旦我们获得了估计的基础比率 $\hat{\alpha}1, ..., \hat{\alpha}{d-1}$我们就可以构建一个线性方程组。定义矩阵 $\hat{A} \in \mathbb{R}^{d \times k}$其第一行为 $V_{\pi_1}^\top$第 $i1$ 行为 $(\hat{\alpha}i V{\pi_1} - V_{\pi_{i1}})^\top$。理想情况下真实的 $w^$经过缩放后满足 $A w e_1$其中 $e_1 (1,0,...,0)^\top$$w w^/ \langle w^*, V_{\pi_1} \rangle$。现在我们用 $\hat{A}$ 代替 $A$求解线性系统 $\hat{A} \hat{w} e_1$。由于 $\hat{A}$ 是 $d \times k$ 的“扁”矩阵$d \le k$这个系统通常有无穷多解。我们选择最小范数解$\hat{w} \arg\min_{\hat{A}xe_1} |x|_2$。这个选择具有很好的稳定性对估计误差 $\hat{\alpha}_i - \alpha_i$ 不敏感。最后算法输出基于估计偏好 $\hat{w}$ 的最优策略$\pi_{\hat{w}} \arg\max_{\pi \in \Pi} \langle \hat{w}, V_\pi \rangle$。3. 理论保证与误差分析算法的理论核心在于证明尽管我们通过有噪声的比较查询得到的 $\hat{\alpha}i$ 存在误差尽管我们用 $\hat{A}$ 近似 $A$但最终输出的策略 $\pi{\hat{w}}$ 的价值 $\langle w^, V_{\pi_{\hat{w}}} \rangle$ 仍然非常接近最优价值 $v^$。3.1 关键引理与定理引理 8.1基础策略的质量保证该引理保证了算法找到的第一个基础策略 $\pi_1$ 不是太差。它证明在比较误差 $\epsilon$ 满足 $\epsilon \le v^/(2k)$ 的条件下有 $$\langle w^, V_{\pi_1} \rangle \ge \frac{v^}{2k}.$$ 这意味着 $\pi_1$ 的价值至少是最优价值的 $1/(2k)$。这个保证是后续所有分析的基石。同时该引理还将基础比率的估计误差 $|\hat{\alpha}_i - \alpha_i|$ 与比较误差 $\epsilon$ 联系了起来$|\hat{\alpha}_i - \alpha_i| \le \frac{4k^2 \epsilon}{v^}$。定理 8.1主定理一般误差上界这是算法最主要的理论结果。它表明使用 $\mathcal{O}(k \log(k/\epsilon))$ 次比较查询算法输出的策略 $\pi_{\hat{w}}$ 的遗憾Regret上界为 $$v^* - \langle w^*, V_{\pi_{\hat{w}}} \rangle \le \mathcal{O}\left( (\sqrt{k}1)d^{\frac{1}{4}} \epsilon^{\frac{1}{3}} \right).$$ 我们来拆解这个上界依赖维度 $k$ 和 $d$遗憾随目标数量 $k$ 和有效维度 $d$ 的增长而增长这是高维问题复杂性的体现。依赖比较误差 $\epsilon$遗憾以 $\epsilon^{1/3}$ 的速度衰减。这意味着即使比较反馈有一定噪声算法性能的衰减速度也比误差本身的线性速度要慢立方根展现了算法对噪声的鲁棒性。查询复杂度仅需 $\mathcal{O}(k \log(k/\epsilon))$ 次比较。这是一个非常高效的结果因为它与策略空间大小、状态空间大小都无关仅与目标数量 $k$ 呈线性关系与精度要求呈对数关系。定理 8.2改进的误差上界通过一个技术性的改进——使用截断矩阵 $\hat{A}^{(\delta)}$只保留前 $d_\delta$ 行对应价值向量投影较大的方向并求解 $\hat{A}^{(\delta)} x e_1$ 得到 $\hat{w}^{(\delta)}$可以进一步将遗憾上界优化为 $$v^* - \langle w^*, V_{\pi_{\hat{w}^{(\delta)}}} \rangle \le \mathcal{O}(k^{\frac{13}{6}} \epsilon^{\frac{1}{3}}).$$ 这个上界消除了对维度 $d$ 的依赖仅与 $k$ 有关。当 $d$ 较大时这个改进尤为有意义。其中 $\delta k^{\frac{5}{3}} \epsilon^{\frac{1}{3}}$ 是一个截断阈值参数。3.2 误差来源与传播分析理解误差如何从比较反馈一步步传递到最终策略性能对于应用和调试至关重要。误差传播链如下比较误差 ($\epsilon$): 用户反馈并非完全可靠存在一个误差概率或偏差 $\epsilon$。这是所有误差的源头。基础比率估计误差 ($\epsilon_\alpha$): 如引理 8.1 所示比较误差会导致我们对基础比率 $\alpha_i$ 的估计产生误差$\epsilon_\alpha |\hat{\alpha}_i - \alpha_i| \mathcal{O}(k^2 \epsilon / v^*)$。矩阵近似误差: 用 $\hat{A}$ 代替 $A$导致我们求解的线性系统发生了扰动。解向量误差 ($|\hat{w} - w|$): 矩阵的扰动最终导致我们求解出的偏好向量估计 $\hat{w}$ 与真实的缩放向量 $w$ 产生偏差。策略价值误差 (Regret): 偏好向量的误差导致我们选择的最优策略 $\pi_{\hat{w}}$ 在真实偏好 $w^$ 下的价值低于最优策略 $\pi^$。算法的分析引理 8.2 和引理 8.3的核心就是严格控制第3步和第4步的误差放大效应。它证明了即使 $\hat{A}$ 的条件数Condition Number可能很大但由于算法探索过程Algorithm 10所隐含的结构信息所有策略价值向量都位于一个“扁平的”集合中最终的价值误差 $\sup_\pi |\langle \hat{w}, V_\pi \rangle - \langle w^*, V_\pi \rangle|$ 仍然可以很小。这是该算法理论深度的体现。注意事项定理中的大O常数隐含地依赖于价值向量的范数上界 $C_V$ 和偏好向量的范数 $|w^|_2$。在实际问题中如果价值向量的尺度差异巨大例如一个目标的值在0-1之间另一个在0-1000之间需要对数据进行归一化预处理否则 $|w^|_2$ 可能会很大影响实际性能。4. 算法实现与工程细节4.1 基础策略探索的实现细节Algorithm 10 是算法的探索阶段其目标是找到 $d$ 个线性无关的基础策略价值向量。其伪代码逻辑如下输入: 策略集合 Π, 比较查询Oracle, 精度参数 ε 初始化: U {e_1, ..., e_k} (标准正交基) for i 1 to k do 在方向 u_i ∈ U 上通过二分搜索/锦标赛找到策略 π̃_i 使得 ⟨u_i, V_{π̃_i}⟩ 近似最大。 计算 V_{π̃_i}。 从 U 中移除 u_i。 对 U 中剩余的每个向量 u将其投影到与 V_{π̃_1}, ..., V_{π̃_i} 所张成空间正交的方向上并重新归一化。 end for 从 {π̃_1, ..., π̃_k} 中选取一组线性无关的向量对应的策略作为 {π_1, ..., π_d} 输出。关键操作二分搜索/锦标赛对于给定的方向 $u$如何找到使 $\langle u, V_\pi \rangle$ 最大的策略由于我们只能通过比较查询来评估策略这本身就是一个单目标优化问题。可以采用以下方法随机采样与锦标赛从策略空间 $\Pi$ 中随机采样一批候选策略。通过两两比较采用淘汰赛制选出这批样本中在方向 $u$ 上最优的策略。可以多轮迭代逐步缩小搜索范围。基于梯度的策略优化如果策略空间是参数化的如神经网络策略并且我们可以估计 $V_\pi$ 关于参数 $\theta$ 的梯度那么可以结合比较反馈来设计偏好优化梯度进行迭代优化。此时比较查询用于评估两个参数点 $\theta_A$ 和 $\theta_B$ 的优劣从而指导搜索方向。关键操作Gram-Schmidt 正交化在每轮找到一个新的基础策略价值向量 $V_{\tilde{\pi}_i}$ 后我们需要更新剩余搜索方向 $U$确保它们与已找到的基础向量张成的空间正交。这是标准的 Gram-Schmidt 过程对于 $U$ 中的每个向量 $u$计算 $u \leftarrow u - \sum_{j1}^{i} \frac{\langle u, V_{\tilde{\pi}j} \rangle}{|V{\tilde{\pi}j}|^2} V{\tilde{\pi}_j}$。如果 $u$ 的范数小于某个阈值 $\delta$即与已有空间几乎平行则将其从 $U$ 中移除。否则将 $u$ 归一化。当 $U$ 为空集时循环终止。此时得到的 ${\tilde{\pi}_1, ..., \tilde{\pi}_i}$ 对应的价值向量是线性无关的其个数 $d$ 即为价值空间的维度。4.2 基础比率估计的二分搜索实现Algorithm 26 是算法的利用阶段用于估计基础比率 $\alpha_i$。其核心是一个二分搜索。对于每个 $i$我们需要找到 $\hat{\alpha}_i$使得用户对混合策略 $M_1 \frac{1}{\hat{\alpha}i}\pi{i1} (1-\frac{1}{\hat{\alpha}_i})\pi_0$ 和 $M_2 \pi_1$ 感到无差异。实现步骤初始化搜索区间我们知道 $\alpha_i \in (0, C_\alpha]$其中 $C_\alpha$ 是一个上界引理8.1中为 $2k$。设置初始下界 $l0$上界 $h C_\alpha$当前估计 $\hat{\alpha}i C\alpha/2$。二分迭代如果 $\hat{\alpha}_i 1$构造混合策略 $M_1 \frac{1}{\hat{\alpha}i}\pi{i1} (1-\frac{1}{\hat{\alpha}_i})\pi_0$与 $\pi_1$ 进行比较。如果用户反馈 $\pi_1 \succ M_1$说明混合策略中 $\pi_{i1}$ 的权重太高即 $\hat{\alpha}_i$ 太小用户更偏好纯的 $\pi_1$。因此我们应该增大$\hat{\alpha}_i$将上界 $h$ 设为当前 $\hat{\alpha}_i$。如果用户反馈 $\pi_1 \prec M_1$说明 $\hat{\alpha}_i$ 太大应该减小将下界 $l$ 设为当前 $\hat{\alpha}_i$。如果 $\hat{\alpha}_i \le 1$构造混合策略 $M_2 \hat{\alpha}_i \pi_1 (1-\hat{\alpha}i)\pi_0$与 $\pi{i1}$ 进行比较。逻辑与上类似。更新与终止更新 $\hat{\alpha}_i (lh)/2$。重复步骤2直到用户反馈为“无法区分”或者搜索区间长度 $h-l$ 小于预设精度阈值。输出最终的 $\hat{\alpha}_i$ 即为估计值。实操心得这里的“无法区分”反馈在实际中需要仔细设计。可以设定一个“ indifference zone ”当两个策略的估计价值差 $|\langle \hat{w}, V_{\pi_A} \rangle - \langle \hat{w}, V_{\pi_B} \rangle|$ 小于某个阈值 $\tau$ 时即返回“无法区分”。阈值 $\tau$ 的选择需要与比较误差 $\epsilon$ 相匹配。4.3 策略表示压缩与高效计算在强化学习等场景中一个策略 $\pi$ 可能对应着海量的轨迹Trajectory。直接存储和计算 $V_\pi \mathbb{E}_\tau[\Phi(\tau)]$其中 $\Phi(\tau)$ 是轨迹 $\tau$ 的累积奖励向量是低效的。附录G.9-G.12 提出了两种方法将策略的价值函数压缩成少量加权轨迹的表示。方法一基于流分解的方法 (Algorithm 28)将策略执行过程视为一个层状图上的流Flow。每个节点代表特定时间步的状态每条边 $(s, s)$ 上的流量 $f(s, s)$ 代表策略 $\pi$ 导致该转移的概率。通过动态规划可以高效计算所有 $f(s, s)$。然后算法通过不断从源点到汇点抽取路径即轨迹并分配流量将流分解为若干条轨迹及其权重的组合。最后利用 Carathéodory 定理Algorithm 27, C4可以将这组加权轨迹进一步压缩到最多 $k1$ 条。这样任何策略 $\pi$ 都可以用最多 $k1$ 条加权轨迹 ${(\tau_j, \beta_j)}$ 来表示使得 $V_\pi \sum_j \beta_j \Phi(\tau_j)$。时间复杂度为 $\mathcal{O}(H^2 |\mathcal{S}|^2 k^3 H |\mathcal{S}|^2)$。方法二扩展与压缩方法 (Algorithm 11)这是一种更高效的动态规划方法。核心思想是递归地构建轨迹集合。在时间步 $t$我们维护一个小的轨迹前缀集合 $F^{(t)}$ 及其权重 $\beta^{(t)}$。从 $t$ 到 $t1$我们将每个前缀 $\tau \in F^{(t)}$ 扩展一步得到新的轨迹集合 ${\tau \circ s}$其权重为 $\beta^{(t)}(\tau) \cdot P(s|s_{\tau}^t, \pi(s_{\tau}^t))$。这个新集合的大小最多是 $|F^{(t)}| \cdot |\mathcal{S}|$。然后我们立即调用 C4 算法将其压缩回最多 $k1$ 条轨迹。通过这种“扩展-压缩”的循环最终在 $tH$ 时我们得到最多 $k1$ 条完整轨迹及其权重精确表示 $V_\pi$。时间复杂度为 $\mathcal{O}(k^4 H |\mathcal{S}| k H |\mathcal{S}|^2)$当状态空间 $|\mathcal{S}|$ 很大时通常比流分解方法更优。方法核心思想时间复杂度适用场景流分解将策略执行视为网络流进行路径分解$\mathcal{O}(H^2 |mathcal{S}|^2 k^3 H |mathcal{S}|^2)$状态转移图相对简单$H$ 不大时扩展-压缩动态规划中每步扩展后立即进行 Carathéodory 压缩$\mathcal{O}(k^4 H |mathcal{S}| k H |mathcal{S}|^2)$状态空间大但目标维度 $k$ 较小时注意事项策略压缩是工程实现中的关键一步它使得存储、传输和计算策略价值 $V_\pi$ 变得可行。尤其是在需要频繁计算内积 $\langle w, V_\pi \rangle$ 的算法步骤中使用压缩表示可以极大提升效率。选择哪种压缩方法需根据具体问题的 $H$, $|\mathcal{S}|$, $k$ 的相对大小来决定。5. 实战考量、常见问题与扩展5.1 参数选择与调优建议算法中有几个关键参数需要根据实际问题进行调整比较误差 $\epsilon$这反映了用户反馈的噪声水平或算法在单目标优化中的精度。可以通过小规模预实验来估计。例如随机选取一些策略对让用户比较统计其反馈与真实偏好若可知不一致的比例。$\epsilon$ 的设置直接影响理论上的查询次数上界和遗憾上界。截断参数 $\delta$在定理8.2的改进算法中需要设置 $\delta (C_V^4 k^5 |w^|_2^2 \epsilon / {v^}^2)^{1/3}$。其中 $C_V$价值向量上界、$|w^|_2$、$v^$ 通常是未知的。实践中可以采用以下启发式方法在算法运行初期使用完整的 $\hat{A}$ 矩阵。当估计的 $\hat{w}$ 稳定后计算 $\hat{A}$ 的奇异值。将奇异值小于某个阈值例如最大奇异值的 $1%$的行对应的方向视为“不重要方向”进行截断。这个阈值起到了 $\delta$ 的作用。二分搜索精度在估计基础比率 $\alpha_i$ 时二分搜索的停止条件区间长度或“无法区分”的阈值需要设置。通常该精度应与最终希望达到的策略价值精度相匹配。5.2 常见问题与排查问题算法找到的基础策略 $\pi_1$ 价值很低导致后续估计误差放大。原因在探索阶段Algorithm 10为每个方向 $e_i$ 寻找最优策略 $\tilde{\pi}_i$ 时优化精度不足或采样策略不够有代表性。排查检查单目标优化模块的性能。可以尝试增加优化算法的迭代次数或使用更强大的优化器。确保用于比较的策略对覆盖了足够广的价值范围。解决引入“预热”阶段使用更精细的搜索如多轮锦标赛、贝叶斯优化来寻找每个方向上的高质量策略。也可以考虑使用一些先验知识来初始化搜索方向。问题求解 $\hat{A} \hat{w} e_1$ 时数值不稳定解 $\hat{w}$ 波动大。原因矩阵 $\hat{A}$ 条件数过大即其行向量价值向量接近线性相关。这通常发生在不同策略的价值向量差异不大或者基础比率估计误差 $\hat{\alpha}_i$ 不准确时。排查计算 $\hat{A}$ 的奇异值。如果存在非常小的奇异值则说明矩阵是病态的。解决正则化求解 $\min_w |\hat{A}w - e_1|_2^2 \lambda |w|_2^2$岭回归其中 $\lambda$ 是一个小的正正则化系数。使用截断解直接采用定理8.2的建议使用截断SVD只保留前 $r$ 个大的奇异值及其对应的奇异向量来求解即 $\hat{w} \hat{A}_r^ e_1$其中 $\hat{A}_r^$ 是秩 $r$ 近似矩阵的伪逆。重新探索回到探索阶段尝试寻找价值向量更具区分度更“正交”的基础策略。问题用户反馈存在系统性偏差例如总是更倾向于选择第一个展示的策略。原因比较查询的界面或顺序引入了偏差。排查在实验中随机化策略对的展示顺序并收集大量反馈数据检验是否存在顺序效应。解决随机化始终随机决定两个策略中哪一个作为“选项A”或“选项B”呈现。模型偏差在算法中显式地对这种偏差进行建模。例如假设观测到的偏好概率为 $P(\pi_A \succ \pi_B) \sigma(\eta \cdot (\langle w^, V_{\pi_A} \rangle - \langle w^, V_{\pi_B} \rangle) b)$其中 $b$ 是顺序偏差项$\sigma$ 是sigmoid函数。然后使用最大似然估计同时学习 $w^*$ 和 $b$。问题查询次数仍然太多用户感到疲劳。原因理论上的 $\mathcal{O}(k \log(k/\epsilon))$ 是上界实际常数可能较大。解决主动学习在选择下一个要比较的策略对时不随机选择而是选择能最大程度减少 $w^*$ 估计不确定性的对如基于信息增益或方差减少。批量查询一次性向用户展示多个策略对如以排行榜形式收集批量反馈。虽然这可能会增加单次查询的认知负担但可以大幅减少交互轮次。利用先验如果对用户的偏好有一定先验知识如来自群体数据可以将其作为贝叶斯先验从后验分布中采样 $w^*$ 的估计从而加速收敛。5.3 扩展与变体处理非线性和上下文偏好本文算法假设偏好是价值向量的线性函数。对于非线性偏好例如用户对某个目标有饱和效应可以考虑使用核方法将价值向量映射到高维特征空间再在该空间中学习线性偏好。对于上下文Context相关的偏好可以将上下文特征与价值向量拼接学习一个参数化的偏好函数 $w^*(x)$。与深度强化学习结合在机器人控制等场景中策略 $\pi$ 通常由深度神经网络表示。可以将本算法作为外层循环用于指导内层RL训练的方向。具体来说内层RL负责为给定的偏好向量 $w$ 优化策略 $\pi_w$外层本算法负责通过与用户交互迭代更新 $w$ 的估计 $\hat{w}$并调用内层RL来求解 $\pi_{\hat{w}}$ 和用于比较的新策略。应用于推荐系统在推荐中一个物品可以看作一个策略决定展示什么其价值向量可以是点击率、观看时长、点赞、分享等多个指标。用户每次反馈点击、跳过、点赞可以视为一种比较点击的物品优于未点击的。算法可以在线学习用户的个性化权重用于调整推荐排序模型的多目标融合分数。这个基于比较反馈的偏好学习框架其强大之处在于将复杂的多目标个性化问题分解为一系列可操作的、符合人类认知的二元查询并提供了坚实的理论收敛保证。尽管在实现细节和参数调优上需要根据具体领域进行精心设计但它为解决“不知道用户想要什么但可以问他们更喜欢哪个”这类问题提供了一个系统性的、数据高效的解决方案。在实际应用中结合领域知识对算法模块如单目标优化器、策略表示、偏差处理进行定制化是取得成功的关键。
基于比较反馈的多目标偏好学习：从几何视角到高效算法实现
发布时间：2026/5/24 8:02:28
1. 个性化多目标决策与偏好学习的核心挑战在现实世界的决策场景中我们很少只追求单一目标。无论是设计一个推荐系统需要在准确性、新颖性、多样性之间权衡规划机器人路径需要平衡时间、能耗和安全性还是进行医疗资源分配需兼顾效率、公平性和成本我们面对的都是典型的多目标决策问题。每个用户在这些目标上的权重——即他们的“偏好向量”——往往是未知且高度个性化的。传统方法要么假设一个统一的偏好要么要求用户明确指定复杂的权重这在实际中既困难又不自然。基于比较反馈的偏好学习其核心思想是绕开直接量化偏好的难题转而通过更符合人类直觉的“二选一”方式来探知用户偏好。例如不是问用户“你对响应速度和准确性的权重分别是多少”而是展示两个策略A和B的结果询问“你更喜欢哪一个”。这种反馈形式更自然噪声容忍度也更高。算法的任务就是利用一系列这样的二元比较高效地推断出用户的隐含偏好向量并据此找到最能满足其个性化需求的策略。这引出了几个核心挑战首先策略空间可能极其庞大甚至是连续的我们无法枚举所有策略供用户比较。其次用户的比较反馈可能存在噪声或不一致。最后我们希望在尽可能少的比较次数内以高概率找到接近最优的策略。本文将要深入剖析的算法正是针对这些挑战提供了一个具有理论保证的解决方案。它通过精心设计的交互协议将高维的偏好学习问题转化为在策略价值向量空间中的搜索问题并证明了其查询复杂度和策略性能的优越性。2. 算法框架与核心思想解析2.1 问题形式化从决策到几何我们首先将问题置于一个严格的数学框架中。假设我们有 $k$ 个需要优化的目标。每一个策略 $\pi$可以是一个推荐列表、一条机器人路径等在执行后会在这 $k$ 个目标上产生一个价值向量 $V_\pi \in \mathbb{R}^k$。例如$V_\pi[1]$ 代表策略 $\pi$ 在“准确性”上的得分$V_\pi[2]$ 代表“多样性”得分以此类推。用户的个性化偏好由一个未知的偏好向量 $w^* \in \mathbb{R}^k_$各分量非负来刻画。用户对策略 $\pi$ 的总体满意度由该策略的价值向量在其偏好方向上的投影即内积 $\langle w^, V_\pi \rangle$ 来决定。这个值越高说明策略越符合用户偏好。最优的个性化策略 $\pi^$ 就是最大化这个内积的策略 $$\pi^* \arg\max_{\pi \in \Pi} \langle w^, V_\pi \rangle.$$ 我们记最优价值为 $v^ \langle w^, V_{\pi^} \rangle$。算法的目标是在不知道 $w^$ 的情况下通过与用户的交互比较查询找到一个策略 $\hat{\pi}$使得其价值 $\langle w^, V_{\hat{\pi}} \rangle$ 尽可能接近 $v^*$。关键视角转换这个形式化过程完成了一次关键的视角转换。我们将寻找“最优策略”的问题转化为在价值向量空间 ${V_\pi: \pi \in \Pi}$ 中寻找在方向 $w^$ 上投影最大的点。偏好学习本质上就是估计这个方向 $w^$ 的过程。2.2 比较反馈作为查询 oracle算法与用户交互的基本单元是比较查询。给定两个策略 $\pi_A$ 和 $\pi_B$或其混合算法向用户呈现它们的结果或描述用户返回一个偏好 $\pi_A \succ \pi_B$喜欢A、$\pi_A \prec \pi_B$喜欢B或者“无法区分”。这个反馈模型非常实用因为它认知负担低用户只需做相对判断无需绝对评分。抗噪声能力强即使反馈有随机错误只要正确概率大于1/2算法依然可以工作。便于获取在许多场景如A/B测试、用户调研中这种数据天然存在。算法需要利用一系列这样的二元比较逐步逼近 $w^$。一个朴素的想法是直接估计 $w^$ 的每个分量但这需要用户对每个目标进行独立评估违背了“整体比较”的初衷。本文的算法采用了一种更巧妙的思路它不去直接估计 $w^$而是去估计一个能产生与 $w^$ 相同最优策略的替代权重向量 $\hat{w}$。2.3 算法核心构建与求解线性系统算法的核心步骤可以概括为以下三步步骤一探索价值空间的基础Algorithm 10为了理解策略价值向量的分布范围算法首先需要找到一组“基础策略” $\pi_1, \pi_2, ..., \pi_d$使得它们的价值向量 ${V_{\pi_1}, ..., V_{\pi_d}}$ 能够张成或近似张成整个价值空间 $\text{span}({V_\pi: \pi \in \Pi})$。这里的 $d$ 是该空间的维度$d \le k$。如何找到这些基础策略算法采用了一种迭代的、基于比较的探索方法。它从一组标准正交基向量 ${e_1, ..., e_k}$对应 $k$ 个纯目标方向出发。对于每个方向 $e_i$算法通过与用户交互找到一个在该方向上表现近似最优的策略 $\tilde{\pi}i$即 $\tilde{\pi}i \approx \arg\max{\pi} \langle e_i, V\pi \rangle$。这个过程本身可以通过带噪声的二分搜索或锦标赛式的比较来完成。最终我们从这 $k$ 个策略中选取价值向量线性无关的一个子集 ${\pi_1, ..., \pi_d}$ 作为基础。实操心得在实际部署中寻找“纯目标最优”策略 $\tilde{\pi}_i$ 可能本身就是一个优化问题。我们可以使用现有的、针对单目标的优化器来获得近似解。关键在于这些基础策略不需要是全局最优的只要它们能提供足够“分散”的价值向量来撑开整个空间即可。维度 $d$ 通常远小于 $k$这反映了目标之间往往存在相关性。步骤二估计基础比率Algorithm 26这是算法最精妙的部分。我们已经有了基础策略 $\pi_1, ..., \pi_d$。根据线性代数的知识如果 $w^$ 已知那么对于任意 $i \in [d-1]$存在一个标量 $\alpha_i$使得混合策略 $\alpha_i \pi_1 (1-\alpha_i)\pi_0$这里 $\pi_0$ 可以是一个零价值策略或某个参考策略与策略 $\pi_{i1}$ 在用户 $w^$ 看来是无差异的indifferent。即 $$\langle w^, V_{\pi_1} \rangle \alpha_i \langle w^, V_{\pi_{i1}} \rangle.$$ 然而我们不知道 $w^*$ 和 $\alpha_i$。算法的巧妙之处在于它通过比较查询来直接估计这些 $\alpha_i$。对于每个 $i$它构造一系列介于 $\pi_1$ 和 $\pi_{i1}$ 之间的混合策略通过调整系数并询问用户该混合策略与 $\pi_1$ 孰优孰劣。通过二分搜索算法可以找到一个估计值 $\hat{\alpha}_i$使得用户对混合策略 $\frac{1}{\hat{\alpha}i}\pi{i1} (1-\frac{1}{\hat{\alpha}_i})\pi_0$ 和 $\pi_1$ 感到“无法区分”。这个过程如图1所示。步骤三求解偏好向量并输出策略一旦我们获得了估计的基础比率 $\hat{\alpha}1, ..., \hat{\alpha}{d-1}$我们就可以构建一个线性方程组。定义矩阵 $\hat{A} \in \mathbb{R}^{d \times k}$其第一行为 $V_{\pi_1}^\top$第 $i1$ 行为 $(\hat{\alpha}i V{\pi_1} - V_{\pi_{i1}})^\top$。理想情况下真实的 $w^$经过缩放后满足 $A w e_1$其中 $e_1 (1,0,...,0)^\top$$w w^/ \langle w^*, V_{\pi_1} \rangle$。现在我们用 $\hat{A}$ 代替 $A$求解线性系统 $\hat{A} \hat{w} e_1$。由于 $\hat{A}$ 是 $d \times k$ 的“扁”矩阵$d \le k$这个系统通常有无穷多解。我们选择最小范数解$\hat{w} \arg\min_{\hat{A}xe_1} |x|_2$。这个选择具有很好的稳定性对估计误差 $\hat{\alpha}_i - \alpha_i$ 不敏感。最后算法输出基于估计偏好 $\hat{w}$ 的最优策略$\pi_{\hat{w}} \arg\max_{\pi \in \Pi} \langle \hat{w}, V_\pi \rangle$。3. 理论保证与误差分析算法的理论核心在于证明尽管我们通过有噪声的比较查询得到的 $\hat{\alpha}i$ 存在误差尽管我们用 $\hat{A}$ 近似 $A$但最终输出的策略 $\pi{\hat{w}}$ 的价值 $\langle w^, V_{\pi_{\hat{w}}} \rangle$ 仍然非常接近最优价值 $v^$。3.1 关键引理与定理引理 8.1基础策略的质量保证该引理保证了算法找到的第一个基础策略 $\pi_1$ 不是太差。它证明在比较误差 $\epsilon$ 满足 $\epsilon \le v^/(2k)$ 的条件下有 $$\langle w^, V_{\pi_1} \rangle \ge \frac{v^}{2k}.$$ 这意味着 $\pi_1$ 的价值至少是最优价值的 $1/(2k)$。这个保证是后续所有分析的基石。同时该引理还将基础比率的估计误差 $|\hat{\alpha}_i - \alpha_i|$ 与比较误差 $\epsilon$ 联系了起来$|\hat{\alpha}_i - \alpha_i| \le \frac{4k^2 \epsilon}{v^}$。定理 8.1主定理一般误差上界这是算法最主要的理论结果。它表明使用 $\mathcal{O}(k \log(k/\epsilon))$ 次比较查询算法输出的策略 $\pi_{\hat{w}}$ 的遗憾Regret上界为 $$v^* - \langle w^*, V_{\pi_{\hat{w}}} \rangle \le \mathcal{O}\left( (\sqrt{k}1)d^{\frac{1}{4}} \epsilon^{\frac{1}{3}} \right).$$ 我们来拆解这个上界依赖维度 $k$ 和 $d$遗憾随目标数量 $k$ 和有效维度 $d$ 的增长而增长这是高维问题复杂性的体现。依赖比较误差 $\epsilon$遗憾以 $\epsilon^{1/3}$ 的速度衰减。这意味着即使比较反馈有一定噪声算法性能的衰减速度也比误差本身的线性速度要慢立方根展现了算法对噪声的鲁棒性。查询复杂度仅需 $\mathcal{O}(k \log(k/\epsilon))$ 次比较。这是一个非常高效的结果因为它与策略空间大小、状态空间大小都无关仅与目标数量 $k$ 呈线性关系与精度要求呈对数关系。定理 8.2改进的误差上界通过一个技术性的改进——使用截断矩阵 $\hat{A}^{(\delta)}$只保留前 $d_\delta$ 行对应价值向量投影较大的方向并求解 $\hat{A}^{(\delta)} x e_1$ 得到 $\hat{w}^{(\delta)}$可以进一步将遗憾上界优化为 $$v^* - \langle w^*, V_{\pi_{\hat{w}^{(\delta)}}} \rangle \le \mathcal{O}(k^{\frac{13}{6}} \epsilon^{\frac{1}{3}}).$$ 这个上界消除了对维度 $d$ 的依赖仅与 $k$ 有关。当 $d$ 较大时这个改进尤为有意义。其中 $\delta k^{\frac{5}{3}} \epsilon^{\frac{1}{3}}$ 是一个截断阈值参数。3.2 误差来源与传播分析理解误差如何从比较反馈一步步传递到最终策略性能对于应用和调试至关重要。误差传播链如下比较误差 ($\epsilon$): 用户反馈并非完全可靠存在一个误差概率或偏差 $\epsilon$。这是所有误差的源头。基础比率估计误差 ($\epsilon_\alpha$): 如引理 8.1 所示比较误差会导致我们对基础比率 $\alpha_i$ 的估计产生误差$\epsilon_\alpha |\hat{\alpha}_i - \alpha_i| \mathcal{O}(k^2 \epsilon / v^*)$。矩阵近似误差: 用 $\hat{A}$ 代替 $A$导致我们求解的线性系统发生了扰动。解向量误差 ($|\hat{w} - w|$): 矩阵的扰动最终导致我们求解出的偏好向量估计 $\hat{w}$ 与真实的缩放向量 $w$ 产生偏差。策略价值误差 (Regret): 偏好向量的误差导致我们选择的最优策略 $\pi_{\hat{w}}$ 在真实偏好 $w^$ 下的价值低于最优策略 $\pi^$。算法的分析引理 8.2 和引理 8.3的核心就是严格控制第3步和第4步的误差放大效应。它证明了即使 $\hat{A}$ 的条件数Condition Number可能很大但由于算法探索过程Algorithm 10所隐含的结构信息所有策略价值向量都位于一个“扁平的”集合中最终的价值误差 $\sup_\pi |\langle \hat{w}, V_\pi \rangle - \langle w^*, V_\pi \rangle|$ 仍然可以很小。这是该算法理论深度的体现。注意事项定理中的大O常数隐含地依赖于价值向量的范数上界 $C_V$ 和偏好向量的范数 $|w^|_2$。在实际问题中如果价值向量的尺度差异巨大例如一个目标的值在0-1之间另一个在0-1000之间需要对数据进行归一化预处理否则 $|w^|_2$ 可能会很大影响实际性能。4. 算法实现与工程细节4.1 基础策略探索的实现细节Algorithm 10 是算法的探索阶段其目标是找到 $d$ 个线性无关的基础策略价值向量。其伪代码逻辑如下输入: 策略集合 Π, 比较查询Oracle, 精度参数 ε 初始化: U {e_1, ..., e_k} (标准正交基) for i 1 to k do 在方向 u_i ∈ U 上通过二分搜索/锦标赛找到策略 π̃_i 使得 ⟨u_i, V_{π̃_i}⟩ 近似最大。 计算 V_{π̃_i}。 从 U 中移除 u_i。 对 U 中剩余的每个向量 u将其投影到与 V_{π̃_1}, ..., V_{π̃_i} 所张成空间正交的方向上并重新归一化。 end for 从 {π̃_1, ..., π̃_k} 中选取一组线性无关的向量对应的策略作为 {π_1, ..., π_d} 输出。关键操作二分搜索/锦标赛对于给定的方向 $u$如何找到使 $\langle u, V_\pi \rangle$ 最大的策略由于我们只能通过比较查询来评估策略这本身就是一个单目标优化问题。可以采用以下方法随机采样与锦标赛从策略空间 $\Pi$ 中随机采样一批候选策略。通过两两比较采用淘汰赛制选出这批样本中在方向 $u$ 上最优的策略。可以多轮迭代逐步缩小搜索范围。基于梯度的策略优化如果策略空间是参数化的如神经网络策略并且我们可以估计 $V_\pi$ 关于参数 $\theta$ 的梯度那么可以结合比较反馈来设计偏好优化梯度进行迭代优化。此时比较查询用于评估两个参数点 $\theta_A$ 和 $\theta_B$ 的优劣从而指导搜索方向。关键操作Gram-Schmidt 正交化在每轮找到一个新的基础策略价值向量 $V_{\tilde{\pi}_i}$ 后我们需要更新剩余搜索方向 $U$确保它们与已找到的基础向量张成的空间正交。这是标准的 Gram-Schmidt 过程对于 $U$ 中的每个向量 $u$计算 $u \leftarrow u - \sum_{j1}^{i} \frac{\langle u, V_{\tilde{\pi}j} \rangle}{|V{\tilde{\pi}j}|^2} V{\tilde{\pi}_j}$。如果 $u$ 的范数小于某个阈值 $\delta$即与已有空间几乎平行则将其从 $U$ 中移除。否则将 $u$ 归一化。当 $U$ 为空集时循环终止。此时得到的 ${\tilde{\pi}_1, ..., \tilde{\pi}_i}$ 对应的价值向量是线性无关的其个数 $d$ 即为价值空间的维度。4.2 基础比率估计的二分搜索实现Algorithm 26 是算法的利用阶段用于估计基础比率 $\alpha_i$。其核心是一个二分搜索。对于每个 $i$我们需要找到 $\hat{\alpha}_i$使得用户对混合策略 $M_1 \frac{1}{\hat{\alpha}i}\pi{i1} (1-\frac{1}{\hat{\alpha}_i})\pi_0$ 和 $M_2 \pi_1$ 感到无差异。实现步骤初始化搜索区间我们知道 $\alpha_i \in (0, C_\alpha]$其中 $C_\alpha$ 是一个上界引理8.1中为 $2k$。设置初始下界 $l0$上界 $h C_\alpha$当前估计 $\hat{\alpha}i C\alpha/2$。二分迭代如果 $\hat{\alpha}_i 1$构造混合策略 $M_1 \frac{1}{\hat{\alpha}i}\pi{i1} (1-\frac{1}{\hat{\alpha}_i})\pi_0$与 $\pi_1$ 进行比较。如果用户反馈 $\pi_1 \succ M_1$说明混合策略中 $\pi_{i1}$ 的权重太高即 $\hat{\alpha}_i$ 太小用户更偏好纯的 $\pi_1$。因此我们应该增大$\hat{\alpha}_i$将上界 $h$ 设为当前 $\hat{\alpha}_i$。如果用户反馈 $\pi_1 \prec M_1$说明 $\hat{\alpha}_i$ 太大应该减小将下界 $l$ 设为当前 $\hat{\alpha}_i$。如果 $\hat{\alpha}_i \le 1$构造混合策略 $M_2 \hat{\alpha}_i \pi_1 (1-\hat{\alpha}i)\pi_0$与 $\pi{i1}$ 进行比较。逻辑与上类似。更新与终止更新 $\hat{\alpha}_i (lh)/2$。重复步骤2直到用户反馈为“无法区分”或者搜索区间长度 $h-l$ 小于预设精度阈值。输出最终的 $\hat{\alpha}_i$ 即为估计值。实操心得这里的“无法区分”反馈在实际中需要仔细设计。可以设定一个“ indifference zone ”当两个策略的估计价值差 $|\langle \hat{w}, V_{\pi_A} \rangle - \langle \hat{w}, V_{\pi_B} \rangle|$ 小于某个阈值 $\tau$ 时即返回“无法区分”。阈值 $\tau$ 的选择需要与比较误差 $\epsilon$ 相匹配。4.3 策略表示压缩与高效计算在强化学习等场景中一个策略 $\pi$ 可能对应着海量的轨迹Trajectory。直接存储和计算 $V_\pi \mathbb{E}_\tau[\Phi(\tau)]$其中 $\Phi(\tau)$ 是轨迹 $\tau$ 的累积奖励向量是低效的。附录G.9-G.12 提出了两种方法将策略的价值函数压缩成少量加权轨迹的表示。方法一基于流分解的方法 (Algorithm 28)将策略执行过程视为一个层状图上的流Flow。每个节点代表特定时间步的状态每条边 $(s, s)$ 上的流量 $f(s, s)$ 代表策略 $\pi$ 导致该转移的概率。通过动态规划可以高效计算所有 $f(s, s)$。然后算法通过不断从源点到汇点抽取路径即轨迹并分配流量将流分解为若干条轨迹及其权重的组合。最后利用 Carathéodory 定理Algorithm 27, C4可以将这组加权轨迹进一步压缩到最多 $k1$ 条。这样任何策略 $\pi$ 都可以用最多 $k1$ 条加权轨迹 ${(\tau_j, \beta_j)}$ 来表示使得 $V_\pi \sum_j \beta_j \Phi(\tau_j)$。时间复杂度为 $\mathcal{O}(H^2 |\mathcal{S}|^2 k^3 H |\mathcal{S}|^2)$。方法二扩展与压缩方法 (Algorithm 11)这是一种更高效的动态规划方法。核心思想是递归地构建轨迹集合。在时间步 $t$我们维护一个小的轨迹前缀集合 $F^{(t)}$ 及其权重 $\beta^{(t)}$。从 $t$ 到 $t1$我们将每个前缀 $\tau \in F^{(t)}$ 扩展一步得到新的轨迹集合 ${\tau \circ s}$其权重为 $\beta^{(t)}(\tau) \cdot P(s|s_{\tau}^t, \pi(s_{\tau}^t))$。这个新集合的大小最多是 $|F^{(t)}| \cdot |\mathcal{S}|$。然后我们立即调用 C4 算法将其压缩回最多 $k1$ 条轨迹。通过这种“扩展-压缩”的循环最终在 $tH$ 时我们得到最多 $k1$ 条完整轨迹及其权重精确表示 $V_\pi$。时间复杂度为 $\mathcal{O}(k^4 H |\mathcal{S}| k H |\mathcal{S}|^2)$当状态空间 $|\mathcal{S}|$ 很大时通常比流分解方法更优。方法核心思想时间复杂度适用场景流分解将策略执行视为网络流进行路径分解$\mathcal{O}(H^2 |mathcal{S}|^2 k^3 H |mathcal{S}|^2)$状态转移图相对简单$H$ 不大时扩展-压缩动态规划中每步扩展后立即进行 Carathéodory 压缩$\mathcal{O}(k^4 H |mathcal{S}| k H |mathcal{S}|^2)$状态空间大但目标维度 $k$ 较小时注意事项策略压缩是工程实现中的关键一步它使得存储、传输和计算策略价值 $V_\pi$ 变得可行。尤其是在需要频繁计算内积 $\langle w, V_\pi \rangle$ 的算法步骤中使用压缩表示可以极大提升效率。选择哪种压缩方法需根据具体问题的 $H$, $|\mathcal{S}|$, $k$ 的相对大小来决定。5. 实战考量、常见问题与扩展5.1 参数选择与调优建议算法中有几个关键参数需要根据实际问题进行调整比较误差 $\epsilon$这反映了用户反馈的噪声水平或算法在单目标优化中的精度。可以通过小规模预实验来估计。例如随机选取一些策略对让用户比较统计其反馈与真实偏好若可知不一致的比例。$\epsilon$ 的设置直接影响理论上的查询次数上界和遗憾上界。截断参数 $\delta$在定理8.2的改进算法中需要设置 $\delta (C_V^4 k^5 |w^|_2^2 \epsilon / {v^}^2)^{1/3}$。其中 $C_V$价值向量上界、$|w^|_2$、$v^$ 通常是未知的。实践中可以采用以下启发式方法在算法运行初期使用完整的 $\hat{A}$ 矩阵。当估计的 $\hat{w}$ 稳定后计算 $\hat{A}$ 的奇异值。将奇异值小于某个阈值例如最大奇异值的 $1%$的行对应的方向视为“不重要方向”进行截断。这个阈值起到了 $\delta$ 的作用。二分搜索精度在估计基础比率 $\alpha_i$ 时二分搜索的停止条件区间长度或“无法区分”的阈值需要设置。通常该精度应与最终希望达到的策略价值精度相匹配。5.2 常见问题与排查问题算法找到的基础策略 $\pi_1$ 价值很低导致后续估计误差放大。原因在探索阶段Algorithm 10为每个方向 $e_i$ 寻找最优策略 $\tilde{\pi}_i$ 时优化精度不足或采样策略不够有代表性。排查检查单目标优化模块的性能。可以尝试增加优化算法的迭代次数或使用更强大的优化器。确保用于比较的策略对覆盖了足够广的价值范围。解决引入“预热”阶段使用更精细的搜索如多轮锦标赛、贝叶斯优化来寻找每个方向上的高质量策略。也可以考虑使用一些先验知识来初始化搜索方向。问题求解 $\hat{A} \hat{w} e_1$ 时数值不稳定解 $\hat{w}$ 波动大。原因矩阵 $\hat{A}$ 条件数过大即其行向量价值向量接近线性相关。这通常发生在不同策略的价值向量差异不大或者基础比率估计误差 $\hat{\alpha}_i$ 不准确时。排查计算 $\hat{A}$ 的奇异值。如果存在非常小的奇异值则说明矩阵是病态的。解决正则化求解 $\min_w |\hat{A}w - e_1|_2^2 \lambda |w|_2^2$岭回归其中 $\lambda$ 是一个小的正正则化系数。使用截断解直接采用定理8.2的建议使用截断SVD只保留前 $r$ 个大的奇异值及其对应的奇异向量来求解即 $\hat{w} \hat{A}_r^ e_1$其中 $\hat{A}_r^$ 是秩 $r$ 近似矩阵的伪逆。重新探索回到探索阶段尝试寻找价值向量更具区分度更“正交”的基础策略。问题用户反馈存在系统性偏差例如总是更倾向于选择第一个展示的策略。原因比较查询的界面或顺序引入了偏差。排查在实验中随机化策略对的展示顺序并收集大量反馈数据检验是否存在顺序效应。解决随机化始终随机决定两个策略中哪一个作为“选项A”或“选项B”呈现。模型偏差在算法中显式地对这种偏差进行建模。例如假设观测到的偏好概率为 $P(\pi_A \succ \pi_B) \sigma(\eta \cdot (\langle w^, V_{\pi_A} \rangle - \langle w^, V_{\pi_B} \rangle) b)$其中 $b$ 是顺序偏差项$\sigma$ 是sigmoid函数。然后使用最大似然估计同时学习 $w^*$ 和 $b$。问题查询次数仍然太多用户感到疲劳。原因理论上的 $\mathcal{O}(k \log(k/\epsilon))$ 是上界实际常数可能较大。解决主动学习在选择下一个要比较的策略对时不随机选择而是选择能最大程度减少 $w^*$ 估计不确定性的对如基于信息增益或方差减少。批量查询一次性向用户展示多个策略对如以排行榜形式收集批量反馈。虽然这可能会增加单次查询的认知负担但可以大幅减少交互轮次。利用先验如果对用户的偏好有一定先验知识如来自群体数据可以将其作为贝叶斯先验从后验分布中采样 $w^*$ 的估计从而加速收敛。5.3 扩展与变体处理非线性和上下文偏好本文算法假设偏好是价值向量的线性函数。对于非线性偏好例如用户对某个目标有饱和效应可以考虑使用核方法将价值向量映射到高维特征空间再在该空间中学习线性偏好。对于上下文Context相关的偏好可以将上下文特征与价值向量拼接学习一个参数化的偏好函数 $w^*(x)$。与深度强化学习结合在机器人控制等场景中策略 $\pi$ 通常由深度神经网络表示。可以将本算法作为外层循环用于指导内层RL训练的方向。具体来说内层RL负责为给定的偏好向量 $w$ 优化策略 $\pi_w$外层本算法负责通过与用户交互迭代更新 $w$ 的估计 $\hat{w}$并调用内层RL来求解 $\pi_{\hat{w}}$ 和用于比较的新策略。应用于推荐系统在推荐中一个物品可以看作一个策略决定展示什么其价值向量可以是点击率、观看时长、点赞、分享等多个指标。用户每次反馈点击、跳过、点赞可以视为一种比较点击的物品优于未点击的。算法可以在线学习用户的个性化权重用于调整推荐排序模型的多目标融合分数。这个基于比较反馈的偏好学习框架其强大之处在于将复杂的多目标个性化问题分解为一系列可操作的、符合人类认知的二元查询并提供了坚实的理论收敛保证。尽管在实现细节和参数调优上需要根据具体领域进行精心设计但它为解决“不知道用户想要什么但可以问他们更喜欢哪个”这类问题提供了一个系统性的、数据高效的解决方案。在实际应用中结合领域知识对算法模块如单目标优化器、策略表示、偏差处理进行定制化是取得成功的关键。
