小红书广告交易算法实习面试：KKT 条件与博弈论连环拷打

《面试题目》

1. 你了解安全强化学习算法吗？
2. 为什么用 SAC，而不用别的算法？
3. 拉格朗日对偶是个什么原理？
4. 对偶形式是什么？
5. KKT 条件背一下。
6. Slater 条件背一下。
7. 介绍一下 Stackelberg 博弈。
8. Stackelberg 博弈和 Nash 博弈有什么区别？
9. 八股：PPO、DPO、GRPO 分别是什么？
10. 手撕：求从网格左上角到右下角的路径数量。

《参考解析》

安全强化学习在解决什么

普通 RL 只最大化期望回报，容易学出「收益高但风险大」的策略。安全强化学习把约束显式写进目标，典型建模是 CMDP：在最大化回报的同时要求若干代价指标的期望不超过阈值。主流做法三类——拉格朗日法把约束乘上乘子并入奖励，再对乘子做梯度更新与策略交替优化；把约束直接塞进策略更新的置信域（CPO 用信赖域控制代价增量）；或者用独立的恢复策略/安全层过滤动作。广告出价、推荐这类场景要的正是「收益不塌但风险可控」，这也是这个岗位会问它的原因：约束不是事后过滤，而是训练目标的一部分。

为什么常用 SAC

SAC 是 off-policy 的最大熵算法：目标里除 Q 值还带策略熵，鼓励探索、对超参不敏感；双 Q 取最小值抑制高估；重参数化得到低方差梯度；熵系数可以自动调节。相对 PPO，它的样本效率更高、能反复利用 replay buffer 里的旧数据，适合真实环境采样昂贵的业务；相对 DDPG/TD3 这类确定性策略算法，随机策略天然带探索、在连续动作空间更稳。答「为什么不用别的」时给出对比轴才有说服力：样本效率、稳定性、动作空间类型、以及在线采样成本，最后落到自己项目里的具体观测。

拉格朗日对偶与对偶形式

原始约束优化的标准形式是最小化 f(x)，满足 g_i(x)≤0 与 h_j(x)=0。构造拉格朗日函数 L(x,λ,ν)=f(x)+Σλ_i·g_i(x)+Σν_j·h_j(x)，对 x 取下确界得到对偶函数，对偶问题就是在 λ≥0 上最大化它。弱对偶（对偶最优不超过原始最优）恒成立；凸性加约束规范满足时强对偶成立、两者相等，最优解由 KKT 条件刻画。落到强化学习上，这套东西的用途是把带安全约束的优化拆成「内层对策略做无约束优化、外层对乘子做梯度更新」的交替过程——乘子本质上是约束的「影子价格」，超限越多惩罚越大。

KKT 条件与 Slater 条件

KKT 在强对偶时是必要条件（凸问题下也充分），包含四块：平稳性（∇f + Σλ_i∇g_i + Σν_j∇h_j = 0）、原始可行性（g≤0、h=0）、对偶可行性（λ≥0）、互补松弛（λ_i·g_i(x)=0）。互补松弛的直觉最值得讲：约束没顶到边界时乘子必须为零，只有起作用的约束才带乘子，这正好解释了安全 RL 里「没超线的约束不参与惩罚」。Slater 条件是保证强对偶成立的一种约束规范：问题凸，且存在严格满足所有不等式约束的内点。面试里连着问是为了确认你不是只会背式子——把「它们各自用来保证什么」说出来比默写公式更容易拿分。

Stackelberg 博弈与 Nash 博弈的区别

Nash 均衡描述同时决策、互为最优反应的一组策略：给定别人的策略，没有人能单方面改变而变好。Stackelberg 是主从博弈，有明确的行动顺序：领导者先决策并预判跟随者的最优反应，跟随者观察到领导者的选择后再优化自己，均衡是子博弈完美的。核心差别在顺序与信息——Stackelberg 下领导者有先动优势，可以把跟随者的反应函数代进自己的目标再优化。广告竞价、定价、平台与商家的关系都是典型主从结构：平台（或广告主）设定机制/出价策略，其他参与方在其后响应，所以广告交易方向特别爱问这个。

PPO、DPO、GRPO 的差别

三者的目标都是把模型输出往「更好的回答」上调，差别在数据与奖励来源。PPO 是在线策略梯度：采样 rollout，用奖励模型或规则打分，再用裁剪的代理目标限制单次更新幅度；需要维护 actor 与 critic（可能还有奖励模型），显存与工程复杂度高。DPO 把带 KL 约束的 RLHF 目标在偏好数据上重参数化，直接对「胜出回答相对落败回答的对数概率差」做类交叉熵优化，省掉采样与奖励模型，但依赖离线偏好数据、用不上在线反馈。GRPO 是 PPO 的轻量化变体：去掉 critic，对同一 prompt 采样一组回答，用组内奖励的均值与标准差作基线算优势，显存占用大幅下降，在数学、代码这类可验证奖励场景效果好。

手撕：网格路径计数

m×n 网格从左上走到右下、每步只向右或向下，本质是组合计数：总步数为 (m-1)+(n-1)，从中挑 (m-1) 步向右，答案是 C(m+n-2, m-1)；实现时用乘法递推求组合数，避免阶乘溢出。DP 版本是 dp[i][j] = dp[i-1][j] + dp[i][j-1]，空间可压成一维。面试官通常会在基础上加码：带障碍物（障碍格 dp 置 0）、允许向右/向下/斜向走、或者要求结果取模时改用 DP 而不是组合数；如果问「任意方向都能走，问路径是否存在」那就退化成图上的可达性/计数问题，别直接套组合数。