阿里在KDD 2020《Maximizing Cumulative User Engagement in Sequential Recommendation: An Online Optimization Perspective》提出了MDP-SSP。
摘要
为了在序列推荐（sequential recommendation）中最大化累积用户参与度(cumulative user engagement 例如：cumulative clicks)，通常需要对潜在的两个冲突目标进行tradeoff，也就是说：追求更高的即时用户参与度（immediate user engagement，例如：click-through rate）和鼓励用户浏览（例如：更多的items曝光）。现存的工作通常分开考虑这两个任务。因而会导致次优的结果。在本paper中，我们从在线最优化的视角，研究了该问题，并提出了一个灵活并且实际的框架来对更长的用户浏览长度和更高的即时用户参与度间进行tradeoff。特别的，我们将：
- items：看成是actions
- 用户请求（user requests）：看成是states
- 用户离开(user leaving)：看成是一个吸收态（absorbing state）
- 每个用户的序列行为：看成是一个个性化的马尔可夫决策过程Markov decision process（MDP）
因此，最大化cumulative user engagement的问题可以转化成一个随机最短路径（SSP：stochastic shortest path）问题。同时，有了immediate user engegement和退出概率估计，可以看到：SSP问题可以通过动态规划（DP）进行有效求解。在实际数据集上的实验表明了该方法的有效性。另外，该方法被部署到大型电商平台上，达到了7%的cumulative clicks的提升。
1.介绍
最近些年，sequential recommendation在许多场景在使用。比如：头条，tiktok等。
不同于传统的推荐系统（通常推荐items的数目的固定的），sequential recommendation的最重要特性是：它会迭代式推荐items，直到用户退出（如图1）。这意味着，用户可以浏览无尽的items。我们针对此的目标是：最大化在每个session内的累积用户参与度（cumulative user engagement)，比如：累积点击（cumulative clicks）、累积停留时间（cumulative dwell time）等。为了该目的，推荐系统需要同时达成两个目标：
- a) 吸引用户具有一个更长的session，比如：浏览更多items
- b) 捕获user interests，比如：达到更高的immediate user engagement
图1
在传统的推荐系统中，由于推荐item的数目是固定的，大多数努力都花在提升immediaite user engagement上，它通常通过CTR进行衡量，等。然而，当这样的一个策略被用到sequential recommendation中时，会趋向于产生次优的cumulative user engagement，这是因为浏览items的数目有限。另外，由于它们间的内在冲突，想要同时达到一个更长session和更高immediate user engagement是一个trivial任务（可以通过实验进行演示）。例如，为了达到一个更长的session，它通常需要探索更多样的推荐结果；这会牺牲immediate user engagement。因此，如何对一个一个更长的session和更高的immediate user engagement进行tradeoff变得非常重要，可以达到一个更高的cumulative user engagement，这对于sequential recommendation来说是个非常重要的问题。
通常来说，在sequential recommendation中存在的工作划成两派。派系1尝试利用sequential information（例如：用户的交互行为）来更准地估计user engagement（例如：CTR）的概率【8，11，12，16，22】。例如，通过使用RNN或它的变种【8，11，25】。通过利用sequential行为模式，这些方法关注于更准地捕获用户兴趣，但没有考虑扩展session length，因而会导致次优结果。基于多样结果的观查，趋向于吸引用户浏览更多的items，第二派的方法显式考虑推荐结果多样性【7，9，23】。然而，在多样性和用户浏览长度间的关系是非常经验性的；因而，直接优化多样性并没有充分理由，特别是存在这样的事实：目前不存在被广泛接受的meartures。因此，在sequential recommendation中最优化cumulative user engagement仍是个挑战。
在本paper中，我们从在线最优化（online optimization）的角度，考虑在sequential recommendation中最大化cumulative user engagement的问题，并提出了一个灵活和实际的框架来解决它。特别的，当将不同的items看成是不同的actions时，用户不同的请求看成是states，用户离开看成是一个absorbing state，在MDP框架中的用户浏览过程，是一个最大化cumulative user engagement的问题，可以看成是一个随机最短路径问题（SSP）问题。为了让该框架可行，在每个state（除了absorbing state），我们需要知道对于每个可能action的两个概率，例如：达到user engagement（例如：click）的概率以及转换成absorbing state的概率（这意味着用户退出浏览过程）。很明显，估计user engagement的概率已经被广泛研究，许多已经存在的机器学习方法可以被采用。同时，我们提出了一个multi-instance learning方法来估计将absorbing state的转移概率（例如：用户退出）。有了该框架以及相应的概率被有效估计，SSP问题可以通过动态规划（DP）进行有效求解。在真实datasets中的实验表明了该方法的有效性。
2.相关工作
2.1 Sequential Recommendation
在最近几年，常规推荐方法，例如：RNN models，使用attention的memory network，被广泛应用于Sequential Recommendation场景。为了找到应推荐的next item，RNN models会通过使用历史序列信息捕获用户的sequence模式。可以训练一个memory network并引入attention机制来加权某些sequential elements。【11，22】表明：这些方法可以极大胜过经典方法（它们会忽略sequential信息）。本质上，他们仍会估计next item的immediate user engagement（），不会考虑上quit probability。因此，进一步的提升必须最大化cumulative user engagement。
2.2 MDP and SSP
随机最短路径（SSP）是一个关于经典最短路径问题的随机版本：对于一个graph的每个node，我们必须选择一个关于在后继节点集合上的概率分布，以便达到一个特定目标节点具有最小的期望开销【4，21】。SSP问题通常是一个MDP问题，具有以下假设：存在一个absorbing state和一个合适的策略。一些动态规划的变种可以被用来求解该问题。RTDP是一个算法，用来求解non-deterministic planning问题，它可以看成是一个启发式搜索或者一个动态规划过程。Labeled RTDP是RTDP的一个变种，关键思想是：如果它的后继节点已经收全省，将一个state标记为sloved，sloved states不会进一步更新。
2.3 Multi-Instance Learning
在MIL任务中，每个样本可以通过一个实例包进行表示【10】。如果它包含了至少一个正实例，则该包（bag）是正向（positive）；否则为负。根据[1] 该方法可以分成三个范式：
- instance-space paradigm
- bag-space paradigm
- embedded-space paradigm
对于我们的sequential recommendation设定，建模转移概率与instance-space paradigm一致。在instance-level MIL任务上，一些SVM-based的方法被提出来。MI-SVM是一个SVM-like MIL方法的变种，主要思想是：在每次迭代中，它会强制远离决策超平面（decision hyperplane，它具有最大间隔）的instance为postive。
3.问题声明
我们将每个浏览过程建模成一个个性化的MDP过程，它包括：一个absorbing state，我们将最大化cumulative user engagement的问题看成是一个SSP问题。
3.1 个性化MDP模型
MDP包含了4个元素的tuple （S, A, R, P)：
- State space S： \(S = \lbrace s_1, s_2, s_3, \cdots, s_t, \cdots, s_T, s_A \rbrace\)。这里我们将推荐序列中的每个step看成是一个单独的state，并定义\(s_t = t\)，其中t是step index。由于每个step中只有一个item会被展示给用户，t也是浏览items的顺序数（sequence number）。T是浏览session length的上限，它对于推荐场景来说是足够大的。\(s_A\)被定义成absorb state，意味着用户离开。
- Action space A：\(A = \lbrace 1,2,3,\cdots, K\rbrace\)。Action space A包含了所有candidates，它可以在当前session中被推荐
- Reward R：\(R \in R^{(T+1) \times K}\)。将S中的state表示成s，将在A中的action表示a，那么\(R_{s,a}\)表示在state s上采用action a的reward。特别的，\(R_{s_t, a_t}\)是在第t个step的immediate user engagement（例如：CTR）。
- 转移概率（Transition probability） P： \(P \in R^{(T+1) \times K \times (T+1)}\)，并且\(P_{s,a,s'} \in [0, 1]\)是在采用action a后，从state s转移到state \(s'\)的概率。
由于在S中的states是顺序的，我们在P上引入一个regulation，它来自所有states（除了\(s_T, s_A\)），用户可以转移到下一个state（继续浏览），或者跳到absorbing state（退出）。另外，从最后的浏览step来看，用户只会进到absorbing state。正式的，我们有：
\[\begin{cases} P_{s_i, a_i, s_{i+1}} + P_{s_i, a_i, s_A} = 1, i < T \\[2ex] P_{s_T, a_t, s_A} = 1, i=T \end{cases}\]…(1)
该过程的有限状态机如图2所示。再者，强调的是，提出的MDP模型是个性化的，我们需要为每个online session来infer一个新的MDP模型。生成MDP models的一个有效算法会在后面呈现。
图2
3.2 SSP问题
基于MDP模型，在sequantial recommendation中的累积回报（cumulative rewards）可以公式化为一个SSP问题：给定一个MDP，目标是寻找一个policy \(\pi^*: S \rightarrow A\)，它可以帮助我们规划一个具有最大累计回报的path：
\[\pi^* = argmax_{\pi} E(\sum\limits_{t=1}^{\tau} R_{s_t, a_t})\]…(2)
其中，\(\tau\)是实际浏览长度。\(\tau\)的分布可以被导出：
\[P(\tau \geq t) = \prod_{i < t} P_{s_i, a_i, s_{i+1}}\]…(3)
因而，等式(2)的expected cumulative reward可以被表示为：
\[E(\sum\limits_{t=1}^{\tau} R_{s_t, a_t}) = \sum_{t \leq T} R_{s_t, a_t} P(\tau \geq t)\]…(4)
最终，通过将等式(1)引入到等式(4)中，我们有：
\[E(\sum\limits_{t=1}^{\tau} R_{s_t, a_t}) = \sum\limits_{t=1}^T R_{s_t, a_t} \times \prod\limits_{i < t} (1 - P_{s_i, a_i, s_A})\]…(5)
3.2.1 Remark 1
最大化等式（5）的目标是共同最优化以下两个点：
- 1）用户浏览长度（\(\tau\)）
- 2）immediate user engagement （例如：\(R_{s_t, a_t}\)）
根据该公式，我们应首先估计等式（5）中的\(R_{s_t, a_t}\)和\(P_{s_i, a_i, s_A}\)，它本质上会生成一个个性化的MDP模型。接着我们通过最大化等式(5)来最优化一个policy，它可以用来为相应用户规划一个推荐序列\([a_1, \cdots, a_T]\)（或者称为 在SSP中的Path）。
4.提出的方法
为了最大化expected cumulative rewards，我们会从personlized MDP model中学习一个MDP generator，它可以在线生成，接着使用personized MDP模型来规划推荐序列。因此，提出的MDP-SSP框架包含了两部分：一个离线MDP Generator和一个在线SSP Planer，它如图3所示。
图3 MDP-SSP框架
4.1.1 MDP Generator
它被设计成用来为每个online session生成personalized MDPs。在该部分中存在两个子模块：Model Worker和Calibration Worker。Model Worker被用来从离线历史数据中生成一个模型，目标是提供个性化MDP的必要元素。特别的，等式（5）中需要的reward function \(R_{s_t, a_t}\)和退出概率（quit probability） \(P_{s_i, a_i, s_A}\)。这里：
- \(R_{s_t, a_t}\)可以是一个immediate user engagement，例如：immediate click，因而，Model Worker包含了相应的estimation model，例如：click model。
- \(P_{s_i, a_i, s_A}\)与一个quit model相关，它决定着浏览session长度，是一个关于Model Worker的重要组件。
再者，由于SSP planing的效率依赖于生成的MDP model的accuracy，我们引入一个额外的Calibration Worker来对从学到的模型中获得的ranking scores进行calibrate到real value【14， 18， 20】。
4.1.2 SSP Planer
它会规划一个最短路径（具有最大cumulative rewards），它包含了顺序的推荐items。它也包含了两个submodules：MDP Producer和SSP Solver。基于通过离线MDP Generator算法学到的该generator，MDP Producer 会为用户的当前session生成一个个性化的MDP。接着SSP Solver会计算一个基于个性化MDP的最优路径给该用户。
4.2 Offline MDP Generator算法
在本节中，我们描述了一个离线算法来学习reward function \(R_{s_t, a_t}\)以及quit probability \(P_{s_i, a_i, s_A}\)，它对生成online个性化MDPs是必需的。我们将看到建模\(P_{s_i, a_i, s_A}\)的问题会更严格和困难。实际上，我们获得的历史数据通常是一个item set，它包含了该用户看到过的items，直到session结束（它会做出用户退出或者继续浏览）。然而，很难知道item set中的哪个item是准确的主因。为了估计每个item的退出概率，我们会采用MIL框架，通过采用item set作为bag，将item作为instance。详细的，如果该item set会造成一个quit，那么该用户会不喜欢在该set中的所有items；如果该item set会造成一个持续的浏览，那么在item set中至少有一个item会被该用户接受，它与MIL setting是一致的。
4.2.1 Remark 2
标准的MIL猜想声明：所有negative bags只包含negative instances，positive bags包含至少一个postive instance。
通过使用一些经典的MIL技术，我们可以获得如下user quit model。
4.2.2 User Quit Model
基于用户的浏览历史，我们可以获得包含了bags \(B_i\)的序列，你可以验证在浏览session中只有最后的bag不会让users继续浏览。我们假设：该bag会继续保持该用户是一个postive bag，写成\(B_i^+\)，并且最后一个是negative bag，写成“\(B_{leave}^-\)”，因此，一个浏览session 为：\(B=(B_1^+, \cdots, B_i^+, \cdots, B_{leave}^-)\)。我们的任务是构建一个模型来预测每个new instance \(B_{*,j}\)的quit probability。然而，存在一个gap，我们的training labels是bag level，而predictions是instance level。为了处理该问题，我们引入MI-SVM【2】来帮助我们训练一个instance level model，它具有bag level data，据我们所知，它对推荐来说是一个MIL的新应用。quit model的训练过程如算法1所示。
4.2.3 Model Calibration
在工业界推荐系统中，由click model和quit model提供的ranking scores，并不等于MDPs中的reward \(R_{s_t, a_t}\)以及转移概率\(P_{s_i, a_i, s_A}\)。因而，它必须对模型的output进行calibrate到真实概率上。对该话题感兴趣的读者可以去【14，18，20】进行详细阅读。在本paper中，我们将predicted score表示成\(f(B_{i,j})\)，真实概率值可以如下进行表示：
\[P(y=1 | B_{i,j}) = \frac{1}{1 + exp(A * f(B_{i,j}) + B)}\]…(6)
其中，A和B是两个scalar参数，可以从历史数据中学习到.
4.3 Online SSP Planner算法
基于最近子节中提到的MDP Generator，我们会正式介绍SSP Planer，它包含了MDP Producer和SSP Slover。
4.3.1 MDP Producer
当一个新的session来的时候，MDP Producer接受来自server的关于user和items的在线信息，接着feeds它们到从MDP Generator中genreators中。接着，可以获得reward和转移概率并实时生成一个个性化MDP。值得注意的是，关于以下的信息：用户已经浏览了多少items，有多少item的类目已经被展示给用户，该用户点击了多少次等，都应该被考虑。这些交互features会扮演着重要的角色，造成用户继续浏览或退出。
4.3.2 SSP Solver
从MDP Producer中，我们可以为当前session获得一个个性化MDP，下一个工作是，寻找一个路径\([a_1, \cdots, a_T]\)，它具有最大cumulative rewards。除了absorbing state外，相应的MDP具有T个states，接着最优的state value function可以使用在T-steps交互的动态规划进行求解。接着，很容易验证，我们特定设计的MDP的transition matrix会保持一个上三角结构，如等式(7)所示。
(7)
基于特殊的结构化转移矩阵，很容易发现：当我们更新当前的state value function，后者的state value function不会变化。因此，向后归纳（backwards induction）会被采纳。我们可以从absorbing state开始，迭代式获取最优的policy以及相关的最优state value function。我们正式地将该过程归纳如下：
\[V^*(s_A) = 0\]…(8)
再者，当i = T时，我们有：
\[\pi^*(s_T) = argmax_{a_T} \lbrace R_{s_T, a_T} + P_{s_T, a_T, s_A} V^*(s_A) \rbrace \\ = argmax_{a_T} \lbrace R_{s_T, a_T} \rbrace, \\ V^*(s_T) = max_{a_T} \lbrace R_{s_T, a_T} \rbrace\]…(8)(9)(10)
当 i < T时，我们有：
\[\pi^*(s_t) = argmax_{a_t} \lbrace R_{s_t, a_t} + P_{s_t, a_t, s_{t+1}} V^*(s_{t+1}) + P_{s_t, a_t, s_A} V^*(s_A)\ rbrace \\ = argmax_{a_t} \lbrace R_{s_t, a_t} + P_{s_t,a_t,s_{t+1}} V^*(s_{t+1})\rbrace \\ V^*(s_t) = max_{a_t} \lbrace R_{s_t, a_t} + P_{s_t,a_t,s_{t+1}} V^*(s_{t+1}) \rbrace\]…(11)(12)
基于等式(8)(12），我们可以计算一个最优的路径 \([a_1, \cdots, a_T]\)。最优化过程如算法2所示。我们可以看到：整个planing过程相当简单和清晰，它有利于提出方法的在线应用。特别的，假设存在K个候选，SSP的复杂度为O(TK)个。
5.实验
我们在一个大型电商平台上开展实验。首先分析了数据特性：表明使用SSP的必要性，接着在离线和在线评估SSP。
5.1 数据集
Dataset 1: MDP Generator的数据集。它包含了15天关于user item交互的历史数据，基于此，我们可以学习模型来预测ctr以及任意user item pair的退出概率（quit probability）
Dataset 2: 该dataset用于SSP offline evaluation。我们收集活跃用户以及它们相应的浏览sessions，并丢弃掉那么不活跃用户或过度活跃用户。根据规则：是否浏览session length在50个items到100个items间进行采样。最终，我们得到1000个users以及相应的浏览sessions。浏览sessions的平均长度是57.
Dataset 3: 该dataset用于SSP online evaluation。它实际上是线上环境，每天具有1000w用户和1亿items。
许多策略（包括SSP）将被部署，会对Dataset 2和Dataset 3中的每个用户进行rerank个性化的候选items，来验证它们在最大化cumulative user engagement上的效果。在那之前，我们应首先验证：该datasets会与如下特性一致：
- 歧视（Discrimination）: 不同的items会提供不同的quit概率，他们会具有一个明显的歧视。否则，当做出推荐时没必要考虑quit概率。
- 弱相关（Weakly related）： 对于一个用户来说，一个item的退出概率会与CTR弱相关。否则SSP和Greedy会是相同的。
5.2 Evaluation Measures
在该实验中，我们会考虑cumulative clicks作为cumulative user engagement。更者，我们将cumulative clicks命名为IPV，这意味着Item Page View，常用于工业界。浏览深度（Browse length：BL）也是一个measurement，因为IPV可以通过让用户浏览更多的items来进行最大化。
在离线评估中，假设：推荐的sequence length是T，根据等式(1)-(5)，我们有：
\[IPV = \sum\limits_{t=1}^T R_{s_t, a_t} \times \prod\limits_{i<t} (1 - P_{s_i, a_i, s_A}) \\ BL = \sum\limits_{t=1}^T \prod_{i < t} (1 - P_{s_i, a_i, A})\]…(13)(14)
再者，推荐序列的CTR的定义如下：
\[CTR = \frac{IPV}{BL}\]…(15)
在每个evaluation中，IPV可以根据实际在线情况进行统计，根据：
\[IPV = \sum\limits_{t=1}^{\tau} c_t\]…(16)
其中：\(c_t \in \lbrace 0, 1\rbrace\)表示在t step上的click行为，而\(\tau\)是浏览深度，例如：\(BL=\tau\)。
5.3 对比策略
- Greedy：在我们的方法与传统方法间的关键不同点是：我们会考虑user的退出概率，并计划着一个可以直接最大化IPV的path，而大多数其它方法尝试尽可能准地估计每个step的reward \(R_{s_t, a_t}\)。然而，当计划着根据\(R_{s_t, a_t}\)贪婪地对items进行排序时，会忽略掉\(P_{s_i, a_i, s_A}\)对于IPV来说很关键。Greedy是第一个对比策略，它的quit概率\(P_{s_i, a_i, s_A}\)不涉及。假设：存在K个侯选，planning path的长度为T，则复杂度是\(O(TK)\)。
- Beam Search：这是一个search算法，可以对效果（performance）和消耗（consumption）进行平衡。它的目的是：将相对最优的路径以序列方式解码。它会被选择作为对比策略，因为退出概率\(P_{s_i, a_i, s_A}\)会被涉及。我们会根据等式（13）计算beam search score，因此，Beam Search会直接应用到这来最优化IPV。假设：存在K个候选，planning path的长度是T，复杂度是O(STK)，其中S是beam size。
5.4 MDP Generator Learning
我们首先会描述MDP Generator learning如第5.4节所示。
5.4.1 Model Learning
在模型学习中，我们会充分利用user属性和item属性。再者，我们会添加interactive features，例如：该item的类目已经被展示给该user多少次、被给user点击多少次，它直觉上对于用户是否做继续浏览动作扮演着一个很重要的角色。AUC，是一个频繁使用的metric，被用来measure 学到的模型，结果如表1所示。
这里我们简短声明下：关于Quit Model的测试方法。由于我们确实不知道哪个item使得用户做出继续浏览行为，因而AUC不能在instance level被直接计算。在bag level中使用instance prediction来计算AUC更合理，因为我们可以假设：如果该bag包含了至少一个postive instance，该bag是positive的；如果所有instance是negative的，则该bag是negative的。
再者，我们会在Quit Model上开展一个对比实验来表明：采用MIL的必要性。由于bag labels是已知的，最直觉的想法是：使用bag的label来表示 instance的label。基于此想法，我们获取了一个\(QuitModel_{no\_MIL}\)，并且AUC也在bag level进行计算。结果如表2所示，从中我们看到，采用MIL对于Quit Model learning来说可以给出一个提升。
5.4.2 Model Calibration
Calibration尝试将从models的ranking scores映mtdf到real value中。这里非常重要，error会累积，见等式(11)(12)。我们会使用普拉特扩展(platt scaling)，并采用RMSE（Root Mean Square Error）作为measurement。结果如表3所示。
从表3中，可以看到，在Calibration后可以达到极大提升，接着real value和calibrated value的曲线在图4和图5中。横坐标是通过predicted scores进行排序的items，纵坐标是calibrated score和real score。real score可以从items bin中获得。
图4
图5
5.4.3 Discrimination
在dataset 2中，对于每个user我们会从MDP Generator（，例如：items的用户浏览session）中获得相应候选的quit probability。接着，可以获取一个user的quit probability list \(l_u = (q_1, \cdots, q_i, \cdots, q_n)\)，其中\(q_i\)是当推荐item i给user u的quit probability。每个list会计算标准差（STD）和MEAN，接着dataset的统计数据如表4所示。从表中，它可以表明：对每个user，不同的candidates会做出不同的贡献来保持用户浏览（user browsing），接着他们具有一个极大的discrimination。
表4
5.4.4 弱相关
我们进一步研究：在quit probability和immediate user engagement（例如：每个step的reward）间的相关性。对于每个user，我们会获得两个item lists \(l_{u1}\)和\(l_{u2}\)，它具有长度L=20. 其中，\(l_{u1}\)和\(l_{u2}\)会根据\(R_{s_t, a_t}\)以及\((1- P_{s_i, a_i, s_A}\)分别被贪婪生成。如果\((1- P_{s_i, a_i, s_A}\)和\(R_{s_t, a_t}\)完全正相关，\(l_{u1}\)和\(l_{u2}\)会是相同的，它会导致SSP和Greedy的equality。我们会使用Jaccard Index和NDCG来measure \(l_{u1}\)和\(l_{u2}\)间的相似度，dataset的平均结果如表5所示。从表中可知，我们会发现：在dataset中，quit probability和immediate user engagement会被弱相关。
表5
5.5 SSP Planner: 离线评估
5.5.1 SSP Plan。
我们会根据上面的每个策略，计算一个具有T step的序列list：\(L_{T} = (a_1, a_2, \cdots, a_T)\)。\(L_T\)的收益可以根据等式(13)-(15)进行计算。
详情如表6所示，我们可以发现：
- Greedy会达到最佳的CTR，而SSP会达到最佳的IPV和BL。这会展示我们的思想：IPV可以通过使得用户浏览更多内容来进行提升。SSP不会最优化每一step的效率（effectiveness），它的目的是提升累积点击（cumulative clicks）的总数。
- step数越长，IPV和BL的优化越大。见：T=20和T=50，当T乘以2.5时，从20到50，IPV和BL两者的提升会超过2.5倍（1347.57 vs. 392.97, 4045.47 vs. 1066.08）。这会产生与我们期望一致的结果：计算越多的step会导致在users中的quit probability越大。
表6
5.5.2 SSP Plan具有Duplicate Removal
在一些实践场景中，items会禁止重复展示。我们需要在三个策略上做出一个折中：
- Greedy：在前t steps中选中的items会被移除出step t+1中的candidate set。
- Beam Search：在前t steps中选中的items会在第step t+1中的candidate set中移除
- SSP：当planing时，我们会根据每步\(V^*(s_t)\)的上界，从step T到step 1进行计划（plan），并在每一step保持最优的T个items作为step的候选。当进行选择时，我们会从step 1到step N做出选择。特别的，我们会选择最优的一个item并从剩余step的候选中同步移除它
从表7的详细结果看出，我们可以发现：尽管折中会伤害理想效果，但SSP仍要胜过Greedy和Beam Search。
表7
5.5.3 SSP plan with Noise
由于存在一些在offline environment和online enviroment间的一个gap，它会做出predicted ctr以及quit probability 在离线不会绝对等价于real value online，我们会在部署MDP-SSP online之前，引入一个noise 实验的集合。
实验会以如下方式开展：我们会在CTR上添加随机噪声（random noises），通过离线环境给出quit probability。假设：noise \(e \sim U(a, b)\)，其中U(a, b)是一个均匀分布，我们会定义 \(a = -0.02m, b = 0.02m\)，其中m是一个从0到10的整数范围。我们会根据具有noise的value进行计划，并计算具有real value的最终收益。结果如图6所示，水平轴表示noise，例如：U(a, b)中的b，竖直轴是revenue，例如：cumulative clicks。
图6
从图6中，我们可以发现，尽管SSP会对noise更敏感，它的效果会好于Greedy和Beam Search。它表明：考虑上quit probability会在IPV问题上扮演着一个十分重要的角色。
SSP Planner：在线评估
对于在线评估，我们会在真实电商APP中部署SSP和Greedy策略。对于进一步对比，我们会做一个实验，它具有quit model，它不会引入MIL，该策略命名为\(SSP_{no \_ MIL}\)。三种策略会在线运行相同的流量各一周，表8展示了结果：
- 对于cumulative clicks，quit brobability在sequential recommendations中不会被忽略，详见SSP和Greedy
- quit probability的accuracy会直接影响着结果，详见：SSP和\(SSP_{no\_MIL}\)
表8
6.结论
略