在动态组合优化问题中，传统的方法是使用基于采样的库存无关策略。这类策略在每个时间段从固定分布中采样产品组合，以提供给不同类型的顾客。这种策略被称为库存无关，因为所采样的组合可能包含没有剩余库存的产品，顾客如果选择了这种产品，则无法完成购买。
虽然库存无关的特性通常不被视为问题，但采样本身带来了性能的不确定性。
本文提出了一种算法，可以去随机化任何基于采样的库存无关策略，使得去随机化后的策略提供一个确定性的产品组合序列，而不会降低性能。此外，我们还给出了去随机化算法的变体，旨在寻找超出原始策略支持的确定性产品组合序列。
我们证明，只要能解决顾客选择过程中的静态组合优化问题，就可以有效实现这个变体。
作为我们的主要技术贡献，我们研究了局部最优的确定性策略，即更改策略中任一组合都不会提高总期望收入的策略。我们表明，任何局部最优策略与最佳的基于采样的策略相比，具有1/2 - ε的性能保证。
博主点评： 本文在动态组合优化领域提出了重要的进展，通过去随机化策略，显著减少了性能的不确定性，提升了策略的可预测性。这一方法为库存管理和客户选择过程的优化提供了新的思路，值得深入研究和应用。