精读笔记

Problem Setting

这篇论文实际解决的是 dynamic assortment optimization 中 sampling-based inventory-agnostic approximation policy 的执行层随机化问题。已有工作为了避开高维库存状态，通常先用 LP 或 relaxation 得到每个 customer type 下 assortment 的混合分布，再在线随机抽 assortment。困难不在于定义动态 assortment，而在于库存耗尽造成跨时间耦合，使得一个时刻的 assortment 改动会改变未来库存可用性和 revenue。

过去方法卡在两个地方：一是 guarantee 往往绑定在 randomized policy 上，无法直接给 deterministic execution；二是去随机化如果靠 simulation，会留下 sampling error，本质上没有消除随机性。本文抓住的矛盾是：随机化对分析和 convexification 有用，但对执行未必必要；平台真正想要的是确定性、稳定、可解释的 assortment 序列，同时保留原 guarantee。

Motivation

已有路线不够的地方不是没有近似保证，而是保证的对象不够干净。sampling-based policy 把算法内部的不确定性直接暴露到执行端，导致同样状态、同样时间、同样用户类型可能看到不同 assortment；这在 revenue variance、平台一致性和商业解释上都很差。

作者的核心观察是：inventory-agnostic policy 的 expected revenue 可以被压缩到产品-时间层面的 purchase probability，而不是依赖完整 assortment distribution 的所有细节。如果随机 distribution 只是为了生成这些 probabilities，那么它可能只是一个中间表征，不应被保留为执行策略。关键缺口就是：能否在不损 guarantee 的情况下，把 LP/randomized policy 转成 deterministic sequence，并进一步证明 deterministic local search 本身已有 guarantee。

Core Idea

论文真正的核心不是“枚举 support 选最好 assortment”这个表面步骤，而是把动态 assortment 的随机策略空间重新投影到 purchase probability 空间。对每个产品 i 和时间 t，策略只通过 demand probability phi_it 影响 expected sales E[min(c_i, sum_t Bernoulli(phi_it))]。这使得动态库存耦合被分解为每个产品的一维截断 Bernoulli 和问题，而不是完整 n 维库存 DP。

这个视角改变了建模方式：随机 assortment 不再是必须执行的 policy，而是生成可达 purchase probability 的 convex representation。去随机化用 conditional expectation 保证 support 内存在不差 deterministic replacement；超出 support 时，利用边际库存可用概率 H_it^- 把动态替换问题变成静态 assortment optimization。和 prior 的本质区别是：prior 用 LP solution 指导随机执行，本文把随机执行本身消掉，并把 policy improvement 变成 coordinate-wise deterministic search。

Method

第一层机制是 support 内去随机化。对一个类型-时间坐标 (j,t)，原随机 assortment 的 revenue 等于条件在每个 support assortment 下 deterministic replacement revenue 的加权平均，因此选 support 中最好的 assortment 不会降低 revenue。它解决的是“随机化是否必要执行”的问题，核心变化是把随机抽样替换成确定性条件期望选择。

第二层机制是 revenue 的可计算表达。因为策略 inventory-agnostic 且各期随机独立，产品 i 的 expected sales 可写成 E[min(c_i, sum_t B_it)]，其中 B_it 是 Bernoulli demand。这样每个产品只需一维 DP，而不是跟踪全库存向量。它解决的是去随机化过程中频繁评估 policy 的计算瓶颈。

第三层机制是 beyond-support replacement。固定其他坐标后，替换 (j,t) 的 assortment 对 revenue 的影响只通过 sum_i r_i H_it^- phi_ij(S) 体现，其中 H_it^- 是不含 t 期时产品 i 仍有库存空间的概率。因此最优替换等价于一个带 adjusted revenues 的静态 assortment problem。它解决的是原 support 太窄导致 improvement 空间不足的问题。

第四层机制是 local optimality guarantee。若任意单坐标 assortment 替换都不能显著提升 revenue，则对应 purchase probability 点是近似 stationary point；由于 revenue 函数是 monotone continuous DR-submodular，stationary point 给出 1/2 近似。它解决的是“从任意 deterministic policy 做局部交换是否有理论意义”的问题。

Key Insight / Why It Works

最关键 insight 是 revenue 对 purchase probabilities 的结构，而不是具体的 de-randomization algorithm。函数 F_i(u_1,...,u_T)=E[min(c_i, sum_t Bernoulli(u_t))] 同时具备三个性质：单调、每个坐标线性、DR-submodular。直觉上，增加某期 demand probability 的边际收益等于其他期需求没有耗尽库存的概率；其他期 demand 越高，这个边际收益越低，所以自然出现 diminishing returns。这正是库存约束带来的 latent submodular structure。

去随机化本身用的是 conditional expectation，技术上不神秘，甚至接近 folklore；真正强的是把这个 replacement 操作和 purchase probability space 的 stationarity 联系起来。local optimality 不是局部启发式，而是在 DR-submodular maximization 意义下的近似一阶最优，因此有 1/2 guarantee。这是论文最值得迁移的部分。

哪些部分可能只是辅助：Caratheodory 用来压缩 support、DP 用来算 revenue、inventory-aware counterpart 用 substitutability 证明删除缺货品不差，这些都重要但不是思想核心。实验中的大幅增益，尤其 uniform-myopic 被救到接近 upper bound，更可能来自 global coordinate improvement 和合成实例结构，而不只是“去随机化”本身。对 CDLP support-only 的提升较小也说明：如果原 support 已经窄且 LP 解较好，单纯去掉随机性带来的均值提升有限；真正的大收益来自允许 beyond-support search。

Relation To Prior Work

最接近的是 Ma et al., Feng et al., Bai et al., Sun et al. 这类 LP-guided sampling policy：它们通过 relaxation 得到可保证的 randomized inventory-agnostic policy，再讨论如何处理缺货或库存 awareness。本文和它们的本质差异是把 randomized policy 当作待去随机化的中间对象，而不是最终 policy。

和 Ma et al. 的 de-randomization 相比，本文不是 simulation-based，不依赖 Monte Carlo 估计 policy value，因此理论上更干净。和 Bai et al. 的 inventory-aware dropping 结果相比，本文把“库存无感可无损修正”作为执行层补丁，而把主要创新放在去除 sampling randomness 和 local optimality guarantee 上。

看似新的部分中，support 内 conditional expectation 去随机化并不算深；真正新增的信息是 DR-submodularity 被用于 policy parameter optimization，以及 local deterministic coordinate optimum 相对最优 sampling policy 的 1/2 近似。这使论文属于 revenue management / online assortment 中“LP/randomized relaxation → deterministic local improvement → submodular continuous optimization certificate”的技术谱系。

Dataset / Evaluation

实验覆盖的是合成 MNL choice model，规模为 50 产品、20 类型、两种 horizon 长度，并通过到达峰值、no-purchase probability、库存紧张度生成不同场景。它验证了两个实践 claim：去随机化通常不只是不降均值，还会降低 revenue variance；global beyond-support search 对 CDLP 这类窄 support baseline 特别有用。

但 evaluation 的外推性有限。所有实例都是作者设计的随机 MNL，并且 arrival pattern 特意让大 consideration set 类型早到、小 consideration set 类型晚到，从而制造 inventory pressure。这是合理 stress test，但不是跨真实业务场景验证。没有真实平台数据，没有非 MNL choice，没有复杂 operational constraints。实验支持“在这种结构化 synthetic setting 下 deterministic local improvement 很强”，但不足以证明随机化在所有 dynamic assortment deployment 中都应被抛弃。

Limitation

核心前提之一是 inventory-agnostic policy 的可分析性：随机 assortment 在类型-时间坐标上独立，且 demand probability 可被干净聚合。如果存在 correlated arrivals、用户状态依赖、学习反馈、曝光疲劳、展示位置约束或跨产品 bundle/resource coupling，这个 purchase probability compression 可能失效。

第二个前提是 substitutability。inventory-aware counterpart 的无损性依赖删除缺货商品不会降低剩余商品选择概率；对某些非标准 choice behavior、互补品、诱饵效应或上下文效应，这个结论不成立。

第三，global method 把难度转移给静态 assortment oracle。对 MNL、nested logit、Markov chain choice 这类模型可行，但对真实大规模带业务规则的 assortment constraints，oracle 可能本身很难。文中“只要能解静态 assortment”是一个强抽象，工程上不一定轻。

第四，1/2 guarantee 的 comparison class 是 best sampling-based inventory-agnostic policy / deterministic inventory-agnostic sequence，而不是最优动态库存感知策略。标题里的 Killing the Case for Randomization 在这个 class 内成立，但不能理解成解决了完整动态 assortment 的随机化/适应性问题。

第五，实验增益归因不完全清楚。尤其 global 去随机化包含了超出原 policy support 的 coordinate optimization，收益可能主要来自 local search 扩大策略空间，而不是消除 randomization 本身。uniform-myopic 的巨大提升也可能反映初始 support 很丰富、实例结构适合 threshold-like MNL assortments，而不是一般弱策略都能被救活。

Takeaway

• 1. 随机化在这类 dynamic assortment policy 中更像分析和 convexification 工具，而不是执行层必要结构；能去掉就应该去掉。
• 2. 库存约束诱导的 diminishing returns 可以在 purchase probability 空间中显式化，DR-submodularity 是比 LP dual price 更结构化的解释工具。
• 3. 未来更值得做的是把这种“randomized relaxation → deterministic local optimum certificate”的套路推广到网络资源、多资源消耗和带约束 assortment，而不是继续设计更复杂的 randomized execution。
• 4. 实践上，beyond-support local improvement 可能比原始 LP sampling policy 更有价值；但需要认真区分 de-randomization gain 和 search-space expansion gain。

一句话总结

这篇论文把 dynamic assortment 中的 randomized inventory-agnostic policy 从最终执行策略降级为离线 convex representation，并用 conditional expectation 与 DR-submodular stationarity 证明确定性局部最优策略已具备可解释的近似保证。