【无限流浅谈】从《迷域行者》到双臂赌博机
最近在B站刷到一档神奇的综艺节目——《十天之后回归现实》，该节目的安排基本照搬自日本智斗/无限流漫画《弥留之国的爱丽丝》，大概是一群人被投放到一个“异世界”中，需要完成各种各样的游戏来获取“签证”（在异世界中的生存时间）。其中的一个游戏来自一部被尘封的国产无限流漫画——《迷域行者》，我们现在来聊聊这个游戏中有趣的设定和可能的解法。
问题描述
综艺节目中给出的原始问题是这样的：
玩家面前有一列苹果，每个苹果的质量是$m_i$。玩家只能依次看到第$i=1,2,3,\cdots,n$个苹果的重量。在玩家获知第$i$苹果的重量后，玩家可以选择拿取这个苹果，或者继续向前走；玩家一旦获知第$i$个苹果的重量，就不能拿取编号小于$i$的苹果。每个玩家在拿取两个苹果后游戏结束，两个苹果中质量最大的那个是玩家的最终得分，而玩家需要最大化一得分。
“最优停止”问题的定义
上面的“取苹果”问题是可以被归类到最优停止问题中，这里我们先给出最优停止问题的定义：
我们有一列随机变量${X_i}$和一列函数${y_i}$。你可以在随机变量序列 $X_1,X_2,\cdots,X_T$ 中观测任意长度的序列，在观测到$X_i = x_i$后，你可以选择继续向下观测$X_{i+1}$，也可以选择停止以获得奖励$y_i = y(x_1,x_2,\cdots,x_i)$。记观测到$X_i$后选择停止的概率为$\phi_i$，停在第$i$步的概率为$\psi_i$，则$\psi_0 = \phi_0$，$\psi_1 = (1 - \phi_0) \cdot \phi_1$，等等。我们的目标是合理地选择$\phi_i$，以最大化收益期望$R(\phi) = \mathbb{E} (\sum_i \psi_i y_i)$。换言之，一个更简单的定义是：我们有离散随机过程${Y_i}$，$\mathcal{F}_i$是由$Y_1,Y_2,\cdots,Y_i$定义的滤流（Filtration）。我们定义随机变量$N$是一个停时，如果事件${N \le i}$是$\mathcal{F}_i$可测的。我们要找到一个停时$N$，最大化$R = \mathbb{E}(Y_N)$。
经典最优停止问题：离散有限视野的情况
如果问题中的随机变量序列是有限的，我们就称问题是Finite Horizon（如同最优控制中一样）。这样的问题可以通过逆向归纳法（实际上是一种动态规划方法）求解。
一般的套路：逆向归纳法
定义状态价值函数$V_i(x_1,x_2,\cdots,x_i)$，代表从第$i$阶段开始（此阶段的状态为$x_1,x_2,\cdots,x_i$）使用最优停止策略直到终点所能获取的最大期望收益。设决策阶段的总数为$T$，显然边界条件是$V_T = y_T (x_1,x_2,\cdots,x_T)$，$V_i$满足的递推公式是：
\[V_i(x_1,\cdots,x_i) = \max[ y_i(x_1,\cdots,x_i) , \mathbb{E} [ V_{i+1}(x_1,\cdots,x_i,X_{i+1}) | X_1 = x_1,\cdots,X_i = x_i]]\]在第$i$步选择停止的条件是$y_i(x_1,x_2,\cdots,x_i) = V_{i}(x_1,x_2,\cdots,x_i)$。只要从$V_T$开始倒推，一路计算到$V_0$，我们也就求出了问题的解。
(a)经典秘书问题
首先介绍一种最经典的问题。
一位公司领导要选择秘书，领导必须依次面试每个秘书，并在每场面试结束后立刻决定是否录用。假设领导可以清晰地比较任意两个秘书之间的能力强弱，那么领导应该采取何种策略，才能最大化选到能力最佳的秘书的概率？
设$X_i$代表第$i$位秘书在已经面试过的$i$个秘书中的能力排名，则$X_i$是在$1,2,\cdots,i$中等概率取值的。我们首先计算每个阶段的即时奖励，假设秘书共有$n$位，我们将每个阶段时已经面试过的人中能力最强者称为“候选人”，那么即时奖励$y_i$应当是第$i$阶段选出能力最佳者的概率： \(y_i(x_i) = \begin{cases} \dfrac{i}{n} \quad X_i = 1 \\ 0 \quad X_i \not = 1 \end{cases}\)
根据$V_i$的定义和$x_i$之间的独立性，不难知道$V_i(x_1,x_2,\cdots,x_i)$只与$x_i$有关。考虑在第$i$阶段停止的条件：$y_i \ge \mathbb{E}V_{i+1}(X_{i+1})$，根据$V_i$的递推式：
\[V_{i+1}(x_{i+1}) = \max[y(x_1,x_2,\cdots,x_{i+1}),\mathbb{E}[V_{i+2}(X_{i+2})]]\]可以得到$\mathbb{E}(V_{i+1}) \ge \mathbb{E}(V_{i+2})$。那么，如果我们在第$i$阶段和第$i+1$阶段面试的均是“候选人”，就有$y_{i+1} > y_{i} \ge \mathbb{E}(V_{i+1}) \ge \mathbb{E}(V_{i+2})$这使得我们得到重要结论：假如第$i$阶段和第$i+1$阶段面试的秘书均是“候选人”，且第$i$阶段的最优策略是录取当前的秘书，那么第$i+1$阶段的最优策略也应是录取当前的秘书。因此，我们可以构造参数化的最优策略：选择一个阈值$r$，拒绝第$1$个到第$r-1$个秘书，接受从$r$开始出现的第一个“候选人”。
记$P_r$为选取阈值为$r$时，选择到最优秘书的概率，现在只需优化$P_r$。直接计算： \(\begin{align*}P_r &= \sum_{i=r}^n P(\text{第}i\text{位秘书能力最佳且被选择}) \\ &= \sum_{i=r}^n P(\text{第}i\text{位秘书能力最佳}) \cdot P(\text{第}i\text{位秘书被选择}|\text{第}i\text{位秘书能力最佳}) \\ &= P(\text{第}i\text{位秘书能力最佳}) \cdot \sum_{i=r}^n P(\text{前}i-1\text{位中能力最佳的秘书出现在前}r-1\text{位中}) \\ &= \sum_{i=r}^n \dfrac{1}{n} \cdot \dfrac{r-1}{i-1} = \dfrac{r-1}{n} \sum_{i=r}^n \dfrac{1}{i-1}\end{align*}\)
通过检查$P_{r+1} \le P_r$的点可以得到：
\[r = \min(r \ge 1, \sum_{i=r+1}^n \dfrac{1}{i-1} \ge 1)\]在$n$很大时，可以得到$\dfrac{r}{n} \rightarrow \dfrac{1}{e}$。
(b)效用单调的秘书问题
在上面的经典问题中，只有选中能力最佳的秘书才有收益。现在，我们给$n$个人的能力赋予从$1$到$n$的排名，排名为$i$的人被选择时带来效用$U(i)$，$U(i)$满足$U(1) \ge U(2) \cdots \ge U(n)$，这个性质被称为效用单调。上面的经典问题可以写为$U(1)=1 ,U(2) = \cdots = U(n) = 0$。为了研究这类问题的性质，我们仍然先计算$y_i$。一位秘书在前$j$个秘书中排名为$x$，但是在总体$n$个秘书中排名为$b$的概率为：
\[f(b|i,x) = \dfrac{C_{b-1}^{x-1}C_{n-b}^{i-x}}{C_n^i}\]那么：
\[y_i(x_1,x_2,\cdots,x_i) = \sum_{b=x}^{n-i+x} U(b) f(b|i,x)\]其中$x = x_i$，显然$y_i$只与$x_i$有关。由于$f$满足下列递推关系：
\[f(b|i-1,x) = \dfrac{x}{i} f(b|i,x+1) + \dfrac{i-x}{i} f(b|i,x)\]这导致$y_i$满足同样的递推关系：
\[y_{i-1}(x) = \dfrac{x}{i} y_i(x+1) + \dfrac{i-x}{i} y_i(x)\]递推边界条件是：$y_n(x_n) = U(x_n)$。此外有$V_n(x_n) = U(x_n)$。这里$V_i$的递推公式是：
\[V_i(x_i) = \max [y_i(x_i) , \mathbb{E} V_{i+1}(X_{i+1})] = \max [y_i(x_i) , \dfrac{1}{i+1}\sum_{i=1}^{i+1} V_{i+1}(x)]\]在第$i$阶段停止的条件就是：$y_i(x_i) = \dfrac{1}{i+1}\sum_{i=1}^{i+1} V_{i+1}(x)$。
接下来我们给出该问题重要性质：如果第$i$阶段录取排名$x$的秘书是最优策略，那么
- 在第$i$阶段录取排名第$x-1$的秘书也是最优策略
- 在第$i+1$阶段录取排名第$x$的秘书也是最优策略
第一条结论的证明是平凡的，我们主要关注第二条。首先根据$V_i$递推式，可以知道$V_i(x) \ge \mathbb{E} (V_{i+1}(x))$，从而有$\mathbb{E} (V_{i}(x)) \ge \mathbb{E} (V_{i+1}(x))$。另外，根据$y_i$的递推式有：
\[\begin{align*} y_i(x) &= \dfrac{x}{i+1} y_{i+1}(x+1) + \dfrac{i+1-x}{i+1}y_{i+1}(x) \\ &\le \dfrac{x}{i+1} y_{i+1}(x) + \dfrac{i+1-x}{i+1}(x) = y_{i+1}(x) \end{align*}\]这导致我们获得不等式$y_{i+1}(x) > y_i(x) \ge \mathbb{E} (V_{i}(x)) \ge \mathbb{E} (V_{i+1}(x))$，也就证明了上面两条重要性质。这两条性质给出了效应单调秘书问题的一种参数化策略：选择$n$个阈值使得$1 \le r_1 \le r_2 \cdots \le r_n \le n$，设在第$i$阶段面试者的排名为$x$，则$i \ge r_x$时即停止。针对特定问题，具体的阈值计算可能是困难的。
(c)停车场问题
最后再介绍一个简单小问题，正如我们一开始所说，这些类似的问题都可以在类似的框架下解决：
你开车沿着一列无限长的编号为$0,1,2,\cdots$的停车位行走，你的目标是将车停在离车位$T$尽可能近的地方；假如你停在了位置$i$，那么你受到损失$|T-i|$。每个车位都有$p$的概率已经被占据，一旦向前走就不能再回头。最优的停车策略是什么？
首先，我们将问题重新表述成有限视野问题。我们可以只考虑$[0,T]$这些车位，车位的状态$X_1,X_2,\cdots,X_T$是一列独立同分布的两点随机变量。考虑即时损失：对于位置$T$有：
\[y_T = \begin{cases} 0 \quad X_T = 0 \\ \dfrac{1}{1-p} \quad X_T = 1 \end{cases}\]这里$T$位置被占满后的损失是在$T$之后位置停车的期望损失。对于其他位置则有：
\[y_T = \begin{cases} T-j \quad X_T = 0 \\ +\infty \quad X_T = 1 \end{cases}\]很容易证明这里也有$T - (j+1) < T-j \le \mathbb{E}(V_{j+1}) \le \mathbb{E}(V_{j+2})$（注意此时$V$的递推式中的取最大变成了取最小，$V$的意义不再是最大奖励，而是最小损失）。因此，使用$r$代表当前停车位离开$T$位置的距离，那么我们只需在$r$之内的某个位置停车即可。这种策略下的期望损失$L_r$满足递推公式：
\[L_r = (1-p)r + p L_{r-1} \Rightarrow L_r = r+1 + \dfrac{2 p^{r+1} - 1}{1-p}\]不难看出最优的$r$的取值为$r = \min(r\ge 0, p^{r+1} \le \dfrac{1}{2})$。
从最优停止到强化学习：双臂赌博机的研究
分析最优停止问题的思想还可以被用于求解强化学习中的重要问题——多臂赌博机问题。在这篇简单的科普文章中，我们只分析问题的最简单形式——双臂赌博机问题。
假定我们有一台有两个摇臂的老虎机，摇臂1每次摇动后的奖励是一列联合分布已知的随机变量$X_1,X_2,\cdots$，而摇臂2在每次摇动后固定给出奖励$\lambda$。设我们的动作序列是$a_1,a_2,\cdots$，观测到的奖励序列是$r_1,r_2,\cdots$，我们需要找到策略$a_n = \pi(a_1,r_1,\cdots,a_{n-1},r_{n-1})$以最大化折扣奖励$V(\pi)= \mathbb{E}(\sum_{i=1}^\infty \beta^{i-1} r_i | \pi)$。
为什么我们说这个问题可以与最优停止问题联系起来？这是因为我们将证明这一问题的重要性质：如果在第$i$阶段发现使用摇臂2是最优的，那么最优策略就应当是在第$i$阶段后一直使用摇臂2。也就是说，我们需要确定一个从摇臂1切换到摇臂2的时间点。
不失一般性，我们设$i=1$，那么在“第1阶段发现摇臂2是最优的”这一条件下的最优策略是$\pi = \arg \sup_{\pi} [V(\pi) : \text{所有}\pi \text{满足} a_1=2]$。假设上面的性质成立，那么最优折扣奖励$V^\star = \dfrac{\lambda}{1 - \beta}$。现在假设我们可以找到策略$\pi$，使得$V(\pi) \ge V^\star - \epsilon\ ,\ \epsilon > 0$，那么我们有：
\[\begin{align*} V(\pi) &= \lambda + \beta \mathbb{E} \left( \sum_{i=2}^\infty \beta^{i-2} r_i | \pi \right) \\ &= \lambda + \beta \mathbb{E} \left( \sum_{i=1}^\infty \beta^{i-1} r_i | \pi \right) \\ &= \lambda + \beta \mathbb{E} \left( \sum_{i=1}^\infty \beta^{i-1} r_i' | \pi \ \text{(shifted 1 slot)} \right) \\ & \le \lambda + \beta V^\star \end{align*}\]于是我们有$V^\star - \epsilon \le \lambda + \beta V^\star$，从而：
\(V^\star \le \dfrac{\lambda + \epsilon}{1 - \beta} \Rightarrow V^\star \le \dfrac{\lambda}{1 - \beta}\)。
这就证明了性质。此外，还容易证明从$i=1$阶段开始，使用摇臂2为最优策略的条件是$\lambda \ge \Lambda$，其中：
\[\Lambda = \sup_{N \ge 1} \dfrac{\mathbb{E} \sum_{i=1}^N \beta^{i-1} X_i}{\sum_{i=1}^N \beta^{i-1}}\]结语
在本文中，我们从《迷域行者》中的游戏出发，给出了离散型最优停止问题的一般定义和有限视野离散型最优停止问题的一般求解方法。我们求解了经典秘书问题、效应单调秘书问题和停车场问题作为例子，同时使用一个简单的双臂赌博机模型介绍了最优停止问题和强化学习中部分问题的联系。然而，本文只是科普，最优停止问题的种类多种多样，足够写十篇这么长的文章。
另外，出乎意料的是，《迷域行者》中提出的游戏是不平凡的，不难看出本文中求解的问题都类似强化学习中的马尔可夫决策过程，$y_i$和$V_i$仅依赖于$x_i$，而原问题中的要求“选择两个苹果”破坏了这个良好性质。因此原问题的求解可能非常复杂。