摘要：假设你被邀请玩这样的一个游戏。如上图所示。在一条线段上，3号位置和6号位置上各有一个硬币。当你支付1元钱选择一个硬币后，如果其不在端点（2-5号位置）上，则其会以各一半的概率向左或者向右移动一个位置。如果其在端点（1、6号位置）上，则其会移动到其唯一一个相邻位
考虑这样的一个问题。
假设你被邀请玩这样的一个游戏。如上图所示。在一条线段上，3号位置和6号位置上各有一个硬币。当你支付1元钱选择一个硬币后，如果其不在端点（2-5号位置）上，则其会以各一半的概率向左或者向右移动一个位置。如果其在端点（1、6号位置）上，则其会移动到其唯一一个相邻位置（2、5号位置）上。当硬币到达4号位置上时，你就能够拿到这个位置上的礼物。现在，你希望以最小的代价拿到这个礼物。
我们先考虑一个简单的情况。假设你被要求只能选择一个固定的硬币进行移动，那么这个问题归结为比较3号位置和5号位置的击中时间（hitting time），也即，硬币从这两个位置移动到4号位置上的期望步数。一些基本的计算告诉我们，3号位置的击中时间为5，而6号位置的击中时间为4。所以我们应该选择移动6号位置的硬币。
然而，如果我们在每一步可以根据两个硬币当前所在的位置任意选择这一步所移动的硬币呢？我们可以注意到，先移动3号位置的硬币似乎是比较好的——如果它直接移动到4号位置上，就直接结束了。但如果它很不幸地移动到了2号位置上，好像我们就再也不应该移动它了，而是一直移动6号位置的硬币。这是因为，考虑到1号位置的存在，无论是5号位置还是6号位置，它和4号位置的距离看起来总是比2号位置和4号位置之间的距离要更近一点。再经过一些计算，我们知道这一策略的期望代价是3元。事实上，这一策略也确实是最优的。
上面的例子带给我们一个观察：第一个是，只能移动一个硬币的情况和可以任意移动两个硬币的情况下，最优策略所率先移动的硬币可以是不一样的。此外，我们会觉得解出第二个问题多少有些侥幸因素：如果问题的结构更复杂一些，上面的基于直觉的解法可能就会出错了。参照击中时间，我们的希望是，能不能为每个位置赋值，然后每一步中总是移动所在位置的值最小的硬币呢？这看起来是一个有些大胆甚至唐突的猜测，毕竟这个问题本身看起来还是很复杂的。
我们进一步将这个问题进行抽象化，称为多币游戏（multi-token game）。假设有n个 Markov 系统，每个系统i中有若干个状态，包含一个初始状态和一个终止状态。此外，系统i包含一个状态转移概率矩阵，这个系统从状态x转移到状态y的概率由(x,y)给出；每个状态x还有一个转移成本(x)。现在，每个系统都处在初始状态。每一步中，我们选择其中一个系统，支付其所在状态对应的成本使其进行转移。我们希望以最小的总成本支出使得其中的一个系统到达其终止状态，应该怎么做呢？
Dumitriu, Tetali, and Winkler (2003) 一工作（题名为 On Playing Golf with Two Balls）指出，这一问题的最优解异常地简洁且优美。最优解为每个系统中的每个状态赋予一个阶（grade）。在每一步中，我们只需要选择所有n个状态中阶最低的状态对应的那个 Markov 系统进行移动即可。这一结论也肯定了我们前面的大胆猜测。这一结论的证明也是非常优雅的，感兴趣的读者可以参考原论文。
如何理解这一“阶”的概念呢？对于一个 Markov 系统，我们假设一个玩家在每一步中可以选择移动这个系统，亦或支付一个价格g以直接结束这个游戏。假设 Markov 系统初始时处在状态u。可以证明，存在一个唯一的g，使得在最优策略中玩家在第一步中选择上面两个选项是没有区别的。这一g就是状态u的阶。可以观察到，一个状态的阶是不超过其击中时间的，也即其在这一 Markov 系统中转移到终止状态的期望成本。
事实上，这一阶的概念并不是第一次出现。其为 Gittins 指标（Gittins index）在这一 Markov 决策过程场景下的一个拓展，而 Gittins 指标由 John C. Gittins 在20世纪70年代至80年代的若干著作中给出。Gittins 指标的最初应用场景是经典的多臂老虎机（multi-armed bandit）问题。这一问题的背景是，一个老虎机有n个臂，每个臂为一个将状态支付替换为状态奖励的 Markov 系统。每一次决策可以选择拉动其中一个臂，已获得其所在状态的奖励，并使其进行一次状态转移。最终的目标是最大化将未来折损后累计的总奖励，也即，对一个折损因子(0,1)，最大化，其中为第t轮的奖励值。这一问题具有丰富的应用与历史，当然也是困难的，甚至一度被一些科学家认为是不可解决的。然而，其最优解仍然由 Gittins 指标定理给出：为每一个臂的每一个状态赋予一个指标，每次选择所在状态指标最大的臂拉动。
图源：网络
最后，我们探索Gittins指标的另一个巧妙应用：潘多拉魔盒问题（Pandora’s box problem）。这一问题由 Martin L. Weitzman 在1979年提出。感兴趣的读者可以参考之前的推送：「链接」。
为了更好地对应前文的内容，我们考虑其成本最小化的等价问题：潘多拉面前有n个盒子，每个盒子i里有一件物品，其价格独立服从某个已知的分布。潘多拉只有在打开盒子i时才能看到其中物品的真实价格，但这一动作需要额外花费的成本。在这一场景下，潘多拉可以依某种顺序打开这些盒子，并在某个时间停止。此时，潘多拉的总成本是已经打开的所有盒子中最低的物品真实价格与打开的所有盒子的成本之和。那么，潘多拉的最优策略是按照什么顺序打开盒子，并在什么时间停止呢？
John William Waterhouse: Pandora – 1896
图源：网络
我们将这一潘多拉魔盒问题规约到前面的多币游戏。将每个盒子i看成一个 Markov 系统，其有如下状态：起始状态，对应盒子尚未打开；对于每一个价格有一个中间状态，对应盒子打开后中物品的价格为；终止状态，对应停止并选择盒子中的物品。盒子i对应系统的起始状态转移成本为，其以概率分布转移到各中间状态；中间状态的转移成本为，并总是转移到终止状态。
在这一规约下，可以简单地计算出每个状态的“阶”。中间状态的阶显然就是自身。而对于初始状态而言，其阶由等式给出，称为盒子i的保留价（reservation price）。那么，根据 Dumitriu, Tetali, and Winkler (2003) 的结论，潘多拉魔盒的最优解是，按照保留价从小到大的顺序开盒，直到开出来的某一个物品价格不超过下一个要开的盒子的保留价，此时，停止并选择这一物品。
Dumitriu, Tetali, and Winkler (2003) 的结论能不能应用到别的形态的问题中呢？当然可以。我们在此抛砖引玉，希望读者进行进一步探索。
参考文献：
Dumitriu, I., Tetali, P., & Winkler, P. (2003). On Playing Golf with Two Balls. SIAM Journal on Discrete Mathematics, 16(4), 604-615.
Gittins, J. C. (1989). Multi-armed bandit Allocation Indices. Wiley-Interscience Series in Systems and Optimization. Chichester: John Wiley & Sons, Ltd.
Weitzman, M. L. (1979). Optimal Search for the Best Alternative. Econometrica: Journal of the Econometric Society, 641-654.
文 | 陈炤桦
来源：北京大学前沿计算研究中心一点号