去年下半年我被借调到某算法小组支援一个代号为模拟项目X的专项项目全称就叫价值引导的结构化采样优化。名字绕口说白了就是一件事候选方案多到搜索空间完全爆炸时不要用均匀随机采样去大海捞针而是先用一个价值评估器把候选按预期价值排排队再在业务约束下按分值概率去抽样。项目上线前的双通道对比测试里同样的候选池、同样的硬约束我们的采样方法比原来的均匀随机采样提升了接近四成的有效命中率资源开销反而更低。我想把这套方案的起因、算法骨架、约束工程和几个实测踩坑记录完整整理出来给同样被超大搜索空间折磨的人一份可复用的参考。1. 项目起因组合空间爆炸后的三个常规选择1.1 业务场景与为什么不能穷举我们的业务抽象下来其实不复杂有一批候选方案每个方案可以理解为一个动作组合比如“给哪类用户发哪个权益、发放顺序怎么排、叠加哪个附属选项”。候选方案本身已经经过一层粗筛数量级仍然在千万上下而实际投放只需要从中挑出几百个组合成一批计划。问题就出在这里。假设候选池有 N 个方案最终要挑出 n 个组合数量是 C(N, n)。当 N 到千万、n 到几百时这个组合空间已经大到不可能做任何形式的全局遍历。一次全量枚举的复杂度是天文数字再快的机器也扛不住。团队一开始尝试过最自然的办法把候选按某个单点指标排序从高到低直接取前几百个。这个办法看起来没什么问题但在实际业务里很快就暴露出两个缺陷。第一单点指标高并不代表放进组合后整体价值高。方案之间存在资源竞争、曝光拥挤、用户疲劳等交互效应单独看每个都很好合在一起可能互相干扰。第二业务里存在大量硬性约束比如不同方案之间有互斥关系、某些类型有配额上限直接按排序截断很容易把后续约束全部打乱最后还要人工调。1.2 贪心不行均匀随机也不行在枚举不可行、贪心排序不靠谱的背景下最常见的替代方案就是均匀随机采样从千万个候选里随机抽几百个期望靠“公平”来覆盖不同区域。均匀随机采样确实能保证无偏但它的问题同样致命。海量候选中真正高价值的区域通常只占很小比例均匀抽样等于把所有区域一视同仁结果就是大量采样样本落在低价值区域。我们当时做过一次离线统计均匀随机抽样产出的样本里真正达到预期收益阈值的比例不到 5%。这意味着每一次实验要跑很多组才能看到有效结果浪费流量和计算资源。还有一个被低估的问题均匀随机采样完全不考虑结构化约束。它天然假设各个候选之间相互独立、可以任意组合但真实业务约束恰恰把这种独立性彻底打破。抽出来的几百个方案很可能超过预算上限、违反互斥规则、或者集中把某一类资源全部抽完最后只能靠后处理强行删改采样分布又被扭曲了。1.3 把问题重新定义成采样问题经过几轮失败尝试我们意识到真正要解决的不是“如何把组合搜索做完”而是“如何在约束条件下分配抽样概率”。换句话说我们并不需要找到全局最优解只需要让采样器以更高概率落在高价值区域同时保留一定随机性去探索未知区域。这就像钓鱼不是把整个鱼塘的水抽干而是先大致判断哪里鱼多把鱼钩往那些位置多甩几次但也不能永远只在一个点下竿。这个思路最终催生了项目名里的三个关键词价值引导、结构化、采样优化。价值引导负责提供“哪里鱼多”的判断结构化负责保证“鱼钩不会甩到岸上”采样优化负责在两者之间找到一个可调、可解释、可上线的平衡点。2. 核心算法骨架价值打分加上温度化加权采样2.1 价值网络怎么训练整个方案的第一步是得到一个能给候选方案打分的价值评估器。我们并没有一开始就上复杂的强化学习框架而是先用离线历史日志训练了一个打分模型。特征主要分三类候选方案自身的属性、上下文特征、历史上同类方案的表现统计。标签用的是真实价值回执比如单元转化率、单位成本、最终收益等。模型结构可以选择梯度提升树或者简单的多层神经网络核心并不在于网络有多深而在于它能不能提供一个相对可靠的 p(value | feature) 近似。这里有个特别容易犯的错直接拿全量历史数据训练价值网络而不做样本分布修正。因为历史数据本身就是旧策略产生的旧策略偏爱高分样本训练集里高分样本会过多模型学出来的价值判断会偏。我们第一次就是这么踩坑的后文会详细复盘。2.2 为什么是加权采样而不是贪心或均匀拿到价值分数之后下一步就是把它转成采样概率。很多人第一反应是“既然已经有分数了直接取分数最高的几个不就行了”。这正是贪心策略我们前面已经验证过不可行。贪心的问题在于它把探索空间砍到了零。一旦分数估计有一点偏差所有决策都会沿着这个偏差走最后采样器只会在同一片小区域打转而且硬约束的存在会让贪心排序出来的组合频繁触碰边界必须不断后处理。均匀随机又太极端等于完全不利用价值信息。两个极端之间需要一个连续调节的中间地带这就是温度化加权采样做的事情。公式看起来很简单。设候选 i 的价值分数为 score_i温度参数为 tau那么候选 i 被抽中的概率为prob_i exp(score_i / tau) / sum_j(exp(score_j / tau))温度参数 tau 控制了价值信号对采样概率的影响程度。tau 趋近于 0 时概率分布趋向于只在最高分候选处取 1退化成贪心tau 趋近于无穷大时所有候选的概率趋近相等退化成均匀随机。实际使用中我们取中间值既保留价值信息的引导又保留一定随机性去探索。这个设计的理论基础也很直接如果价值分数与真实价值正相关那么把抽样概率从均匀分布切换成按价值加权的分布后采样集合的期望真实价值会上升。因为更高的概率被分配给了更高价值的候选平均下来自然比均匀采样更优。当然这个结论依赖价值模型的准确性模型偏差越大这个增益就越小所以价值网络的迭代质量直接决定整体上限。2.3 采样器的核心伪代码价值引导加权采样的核心逻辑并不长难点全在约束处理上。先放一个最基础版本import torch def value_guided_structured_sample( value_scores, # 每个候选的价值分数 feasible_mask, # 当前可行的候选掩码 tau, # 温度系数 n_samples # 需要采样的个数 ): chosen [] for _ in range(n_samples): # 只有可行候选参与概率计算 logits value_scores / tau logits logits.masked_fill(~feasible_mask, float(-inf)) probs torch.softmax(logits, dim0) idx torch.multinomial(probs, 1).item() chosen.append(idx) # 根据已抽中的候选更新可行掩码 feasible_mask update_mask_with_state(feasible_mask, idx) return chosen注意每一轮抽样完成后都要重新做一次 softmax而不是在一开始算好概率后重复采样。这样做是因为无放回采样过程中抽走一个候选之后剩余候选的可行掩码可能发生变化比如互斥项被禁掉、配额剩余量变小等等。如果不重新归一化后面几轮的采样分布就和当前可行集完全脱节。3. 结构化约束从一个自由采样器变成一个能上线的采样器3.1 业务里真正会遇到的约束类型纯价值加权采样在实验室里跑得很好但离上线还差一大步。这一步就是结构化约束。我们当时梳理下来业务里有四类约束直接影响采样过程。第一是总量约束。最终抽出的候选组合总成本、总曝光量、总预算不能超过某个上限。这类约束是全局性的抽样进行到后半段会越来越紧。第二是配额约束。某些类型或某些来源的候选方案有数量上限比如同一个权益类型最多出现 20 次同一个供应商的方案最多出现 5 个。这类约束是对“某一类样本占比”的限制。第三是互斥与依赖约束。有的方案和另一个方案不能同时出现有的方案一旦出现就必须配套某个辅助方案。这类约束决定了个体之间的关联关系无法用简单的“每类最多几个”表达。第四是多样性约束。虽然不需要硬性要求每个簇都必须出现但如果抽样结果全部集中在同一簇线上体验会明显恶化用户容易产生审美疲劳。多样性约束更像一个软目标而不是硬边界。3.2 三种实现策略的取舍面对这些约束我当时梳理了三种实现方案这里直接做一张对比表方便大家参考。实现策略优点缺点适用场景拒绝采样实现最简单逻辑清晰几乎无实现偏差约束多时拒绝率高可能反复空转约束很少、可行集很大的场景掩码加归一化确定性强不会空转见效快只适合表达“行/不行”的硬约束硬约束明确、数量较少时状态感知序列采样能处理连续变化的约束状态实现复杂需要维护状态机预算、配额、依赖关系同时存在时拒绝采样是最容易想到的方法先按价值权重抽一个样本再检查它是否满足所有约束不满足就重抽。这个方案在候选池大、约束稀疏时很好用但我们的场景里候选池已经被粗筛过一轮可行集本身不大加上多个约束叠加拒绝率经常高达 90% 以上每次采样都要跑大量无效循环。掩码加归一化比拒绝采样稳定因为它不是在抽样后判断而是在抽样前就把不可行候选排除掉。做法很简单把不可行候选的 logits 设为负无穷softmax 之后概率自然变成 0。这个方法适合处理“某候选能否出现”这类瞬间可判定的硬约束。麻烦的是预算约束这种连续状态。预算不是“能不能选”的问题而是“选到什么时候会超”。单纯用掩码表达不了“还剩 30% 预算时必须偏好低成本候选”这类动态变化。3.3 我们最后选择的方案状态感知序列采样最终我们采用的是第三种状态感知序列采样。它的核心思想是每一轮抽样都维护一个当前状态状态里包含剩余预算、剩余配额、已经选中的候选集合等信息。每一步根据这个状态重新计算可行掩码再做一次价值加权抽样。举个互斥约束的例子。候选集里有 A 和 B两者互斥。随机抽样抽中 A 之后状态更新时就把 B 的掩码置为 False下一轮 softmax 自动把 B 排除。预算约束也类似每抽中一个候选就从剩余预算里扣掉它的成本如果剩余预算不够支撑某个候选的最低成本就把该候选从可行掩码中暂时移除。这个方案比单纯掩码灵活的地方在于状态是有记忆的。前面抽了什么后面就知道哪些不能再选哪些配额快满了哪些预算要省着用。它本质上把“结构化”从静态规则升级成动态决策过程。3.4 硬约束和软约束怎么平衡状态感知序列采样处理硬约束很顺手但多样性这类软约束直接上硬掩码会出问题。我们把所有约束分成两类硬约束必须 100% 满足任何一条不满足都是事故软约束则转换成惩罚项或额外分数叠加到价值分数上。比如多样性约束我们的做法不是“同一聚类最多出现 3 个”而是“某个候选所在聚类的已出现次数越多它的实际采样分数越低”。用公式表达就是effective_score_i value_score_i - alpha * count_in_cluster_i其中 alpha 是多样性惩罚系数count_in_cluster_i 是当前已抽样本中与候选 i 同一聚类的数量。这个设计保留了采样的灵活性当某个聚类的候选真实价值高得惊人时算法仍然有机会突破多样性限制去选择它而硬掩码会把这个可能性完全抹掉。4. 绕不开的三个运行细节温度、评估和冷启动4.1 温度系数怎么调温度参数 tau 是整个采样器里最直观、也最需要仔细调的旋钮。tau 太大价值引导形同虚设tau 太小探索能力被抑制价值模型的误差会被无限放大。我们一开始尝试固定 tau1效果一般。后来参照模拟退火的思路把 tau 设计成随迭代衰减的曲线冷启动阶段用 1.2 到 1.5保留充分探索平稳运行阶段降到 0.6 到 0.8后期如果要收敛到更稳定的高价值区域可以压到 0.3 左右。tau 取值采样行为建议使用阶段1.0 ~ 1.5接近均匀随机但保留价值偏置冷启动、新流量探索0.5 ~ 0.8价值主导保留适当随机常规稳定运行0.1 ~ 0.3接近贪心探索极少后期收敛、重点场景这里有一个重要提示不要企图在不同业务场景中共享同一个固定温度值。不同场景的目标分布形态差异很大价值分数分布窄的场景需要更小的 tau 来拉开差距价值分数分布宽的场景用同样 tau 会导致概率几乎全部集中在极少数高分候选上。我们最后是每个场景单独扫一组 tau 候选值来做离线选参。4.2 离线评估怎么更贴近线上离线评估是整个项目最容易被做得失真的一环。最常见的错误是只看价值模型平均分价值模型说这批样本平均分高就认为采样器表现好但价值模型本身的偏差被完整继承了。我们后来建立了一套指标组合。首先是采样命中率也就是采到的样本里真实反馈达到预设阈值的比例这个是核心业务指标。其次是相对均匀采样的真实价值提升率用同一批候选池分别跑均匀随机和我们的采样器比较真实回执的平均水平。第三是覆盖率统计采样集合覆盖了多少个聚类或者多少个方案来源。第四是约束满足率硬约束必须达到 100%。离线评估还有个容易忽略的点应该用小流量日志重建评测集而不是使用几个月前的历史日志。因为采样器上线后会改变候选的分布旧日志里的分布已经代表不了未来的线上环境。我们就是在这一点上栽了个跟头后面详细说。4.3 冷启动阶段的价值探索价值网络刚上线时对没见过的候选区域基本没有判断力。如果直接按价值分数引导采样器会只在训练数据覆盖较好的少数区域打转未开发的区域永远得不到曝光价值网络也无法学习它们。我们用了两个办法来缓解冷启动问题。第一个是 UCB 式的探索加权给价值分数加一个不确定性上界候选 i 被采样的分数变成 value_pred_i c * uncertainty_i。不确定性的常见口径是 sqrt(log(total_count) / count_i)count_i 越大意味着该候选被采到的次数越多、估计越稳定不确定性自然下降。这样冷启动阶段高不确定性候选会自动获得更高的被采样机会。第二个方法更简单粗暴以一定概率切换到均匀随机采样。比如 20% 的流量走均匀随机80% 走价值引导。等价值网络见过足够多样本、不确定性降到阈值以下再把随机比例降下来。个人更推荐 UCB 方式因为它的探索是自适应的对某个候选越不确定越发愿意给它机会而固定概率的随机切换在整个生命周期中都保持同样的探索强度不够聪明。5. 实测踩坑三个翻车现场的完整复盘5.1 案例一价值网络被“高分样本”带偏第一轮迭代进行到第三周时我们看到一个诡异的现象离线命中率还在涨但线上真实转化率反而开始下滑。团队第一反应是数据回传链路出了问题排查了半天没有发现异常。后来我们把采样分布拉出来看发现采样器越来越集中在同一小簇候选上价值网络打分排名前列的候选大量共享相同属性。再往深挖根因出在训练集分布上。历史日志数据来自旧策略而旧策略本身偏爱少数高价值簇导致训练集里这些簇的样本严重过采样。价值网络学到的不是“什么是高价值”而是“哪些样本在训练集里大量出现”模型自然会把高分集中到旧策略已经偏爱的那一小片区域。这个坑的本质是训练分布与采样分布之间的循环放大采样器按价值网络选高分高分样本继续进入日志继续强化模型对同一区域的偏爱。修复分两步走一是在训练集中对低分样本和低覆盖率区域的样本做上采样让价值网络看到更多“非高分”候选二是把离线命中率指标改成按聚类分层统计避免少数高分簇掩盖整体退化。5.2 案例二硬 mask 把探索空间锁死第二个问题出现在多样性约束改成硬掩码之后。我们曾经为了提升覆盖率把“每个聚类最多出现 3 个候选”直接写成了 mask 逻辑。结果覆盖率指标确实涨了但线上用户时长反而下降。排查链路先是检查约束满足率全部 100% 通过再检查采样集合的真实价值发现平均价值下降。原因其实不复杂当我们把高分候选所在聚类硬性 mask 掉之后采样器只能在次优集合里打转。多样性被人为拔高同时牺牲了太多价值信号。这个案例给我们最大的教训是多样性不是越高越好硬约束会压制价值引导的发挥空间。最终我们把它从硬 mask 改成软惩罚项让价值信号和多样性约束在同一个维度上互相权衡覆盖率从峰值略降了一点但真实价值大幅回升。5.3 案例三离线提升和线上效果对不上第三个案例最让人头疼。我们在离线评测集上跑出的相对提升接近 10%上线小流量之后几乎没有变化甚至少数实验桶里还出现了负向波动。逐层排查之后发现两个问题。第一离线评测集用的是三个月前的历史日志而这三个月里候选池结构已经发生变化旧评测集不能代表线上分布。第二线上请求带有很多实时上下文特征比如当下用户所处场景、近期实时反馈热度这些特征完全没有进入价值网络模型的判断力在真实环境里打了折扣。修复方案是把价值网络的特征体系补全加入三个最重要的实时上下文特征同时建立小流量日志回流机制每隔一段时间用最近一周的线上日志重建评测集离线评估和线上环境保持同步。改完再跑离线提升和线上效果就对上了。6. 这套方法还能迁移到哪些地方6.1 搜索结果打散与内容多样性控制第一个可以迁移的场景是搜索结果打散。搜索场景的候选通常由召回模型给出按相关性预估分数排序但直接按分数排序会让结果页高度同质化。把本文的框架套进去价值网络换成相关性预估模型结构化约束换成“同一作者最多出现几次”“同一类型最多几个”这类规则采样器就可以在保持相关性的同时控制结果多样性。这一套在很多内容业务里可以直接复用。6.2 测试用例组合选择第二个方向是软件测试中的用例组合优化。回归测试往往有成千上万条用例执行成本高不能全量跑。我们可以把每条用例的历史失败率当成价值分数把执行时长预算、环境依赖关系、模块覆盖率上限当成结构化约束。价值引导加结构化采样可以自动选出一组“历史失败率高、执行总时长可控、覆盖足够广”的用例子集比经验式的手工圈定要客观得多。6.3 强化学习仿真的候选生成第三个方向是强化学习仿真环境里的经验回放采样。训练过程中产生的 transition 数量巨大随机从经验池取样会导致价值网络反复学到同质化的转移经验。按时间差分误差或者预测不确定性作为价值分数再结合 batch 内部多样性约束做加权采样可以显著提高训练样本的利用效率。这个方向我们只在内部仿真环境里验证过效果不错但还需要更多场景打磨。6.4 价值网与采样器解耦的工程经验最后分享一个工程层面的经验从第一天起就把价值网络和采样器设计成两个独立模块中间只通过一份快照传递分数。我们最初把价值网络内嵌到采样服务里每次模型迭代都要重启整个服务线上抖动严重。后来改成价值网络离线训练、定期导出全量候选分数采样器每隔一段时间拉取一次快照模型更新完全不影响线上采样过程。异步更新的代价是分数可能滞后几分钟但在大多数场景里远不至于影响效果而迭代效率的收益非常明显。如果要在自己的项目里落地这套思路我建议不要一上来就搭完整的状态感知序列采样器。先从均匀随机采样开始持续记录真实反馈数据训练一个最简单的价值打分模型再用温度 1.0 的加权采样替换均匀随机最后才逐步加入结构化约束。这条路径每一步都能单独评估、单独回滚风险最小。我在这次项目里最大的体会是算法复杂不等于有效价值引导提供的方向性、结构化约束提供的可行性、温度参数提供的灵活性三者平衡才是真正决定效果的东西。