极小极大遗憾

极小极大遗憾（minimax regret）是在状态概率未给定时，选择最坏遗憾最小的决策准则。某个状态下的遗憾，是所选方案与“若事先知道该状态就能取得的最好结果”之间的差距。它衡量错失的机会，而不是收益本身的高低，也不是对人的后悔情绪作心理测量。

使用这一准则仍须给定可行方案、可能状态和每种组合的收益或损失。不指定概率，不能消除状态集合和模型数值带来的判断。^[1]

从收益表到遗憾表

设决策集合 $A$ 和状态集合 $S$ 都非空且有限，收益 $u (a, s) \in ℝ$ 越大越好。对每个状态先计算事后最好收益 $M_{s} = max_{b \in A} u (b, s) .$ 方案 a 在状态 s 下的遗憾定义为 $r (a, s) = M_{s} - u (a, s) \geq 0$ 。极小极大遗憾选择 $a^{*} \in * {a r g m i n}_{a \in A} max_{s \in S} r (a, s) .$ 由于两集合有限，最大值、最小值都能取得，但最优方案可能不唯一。M 是按列求出的基准，不能每一行用自己的最好状态当基准。

例如，下表是三个方案在三种状态下的教学收益，所有收益用同一个可加单位表示，不对应实际投资回报。

方案	状态一	状态二	状态三
A	8	7	1
B	4	6	6
C	0	4	10
各列最好收益	8	7	10

逐列用最好收益减去各项，再取每行最大值：

方案	状态一遗憾	状态二遗憾	状态三遗憾	最大遗憾
A	0	0	9	9
B	4	1	4	4
C	8	3	0	8

因此选择 B。它不在任何一列获得最高收益，却把最坏的机会损失限制在四；A 在两个状态下最好，但遇到第三种状态时会错失九。

三个方案在三种状态的遗憾柱图，A最大9，B最大4，C最大8，最小的行最大值属于B — 先按状态计算遗憾，再比较每个方案最坏的一项；不是比较所有柱子的平均高度。

与最坏收益和期望收益的区别

最大最小收益准则求的是 $max_{a} min_{s} u (a, s)$ ，直接保护最坏收益；极小极大遗憾保护的是相对同状态最好结果的差距。两者在某些表中恰好选择同一方案，在另一些表中不同。

考虑只有两种状态的变式：A 的收益为 $(2, 100)$ ，B 为 $(4, 90)$ 。最坏收益分别是二和四，最大最小收益选择 B。但事后最好收益为 $(4, 100)$ ，两行遗憾分别为 $(2, 0)$ 、 $(0, 10)$ ，故极小极大遗憾选择 A。前者更关注收益最低时拿到多少，后者更关注相对已知状态下最好方案少拿多少。

若状态概率 $p_{s}$ 已确定，最小化期望遗憾与最大化期望收益则完全等价，因为 $\sum_{s} p_{s} r (a, s) = \sum_{s} p_{s} M_{s} - \sum_{s} p_{s} u (a, s),$ 第一项与 a 无关。这个代数等价不适用于把期望换成最大值；不能把“最大遗憾最小”称为“平均收益最大”。^[1]

允许随机化的决策

若实际问题允许先抽签选方案，可令 $p_{a} \geq 0$ 、 $\sum_{a} p_{a} = 1$ ，在每个固定状态下比较期望遗憾。需要说明时间顺序：状态可以针对已知的抽签分布，但不能看完实际抽签结果再改变。此时优化为 $min_{p} max_{s} [M_{s} - \sum_{a} p_{a} u (a, s)] .$ 它等价于线性规划：引入变量 z，最小化 z，并对每个 s 加上约束 $z \geq M_{s} - \sum_{a} p_{a} u (a, s)$ ，再加概率非负和总和为一。每个状态给出一个仿射函数，取最大值形成凸的分段线性目标；有限数据与紧的概率单纯形保证最优值存在。

在刚才的两方案变式中，令以概率 p 选 A，其余选 B。两状态的期望遗憾为 $r_{1} (p) = 2 p, r_{2} (p) = 10 (1 - p) .$ 一条随 p 上升，一条随 p 下降。若 p 小于交点，降低最大项要增大 p；若大于交点，则要减小 p。故最小的上包络在交点取得： $2 p = 10 (1 - p), p = \frac{5}{6}, max (r_{1}, r_{2}) = \frac{5}{3} .$ 它小于最佳纯方案 A 的最大遗憾二。但 $5 / 3$ 只约束固定状态下对抽签取平均的遗憾，不保证每次实际抽签损失都不超过该值。若状态可以在看见抽签结果后选择，这一保证就不成立。

两状态期望遗憾2p与10乘以1减p的曲线相交于p等于六分之五，高度三分之五，最大值曲线在此最小 — 粗线为两条直线的上包络。横轴是选 A 的概率，纵轴是按固定状态计算的期望遗憾。

随机化是否可行由问题决定。对一次不可分割的设施建设，抽签并不等同于同时建设六分之五个 A；对可多次重复或能随机分配的任务，才可能有合适的实施解释。

单位变换与可行集

若给每个状态的全部方案都加同一个数 $b_{s}$ ，新基准也加上 $b_{s}$ ，遗憾保持不变。若所有收益统一乘以 $α > 0$ ，所有遗憾同乘该数，最优选择也不变。因此一致的货币换算不会改变结论；逐方案任意改变尺度则不具有这种性质。

可行方案集合却会改变基准。例如最初只有 A 的 $(5, 8)$ 、B 的 $(8, 4)$ ，最大遗憾分别为三和四，选择 A。加入 C 的 $(13, 0)$ 后，两状态基准变为 $(13, 8)$ ，A、B、C 的最大遗憾分别为八、五、八，选择变成 B，虽然新方案 C 本身没有被选择。原因是 C 提高了第一状态的事后基准。这个现象说明评估时须说明候选集，也不能把任意拼出的情景和备选项当成中性的背景。^[1]

若方案 B 在每个状态的收益都不低于 A，则 $r (B, s) \leq r (A, s)$ 对所有 s 成立，A 不可能在最大遗憾上严格优于 B；两者仍可能因最大项相同而并列。

精确计算纯方案

以下 Python 函数输入一个非空矩形收益表，元素为整数或 Fraction，返回遗憾表、每行最大遗憾以及全部最优行编号。不改写输入，采用有理数运算避免教学算例中的浮点比较误差；有小数时可先明确转换为 Fraction("0.1") 等精确值。

Python 3

from fractions import Fraction

def minimax_regret(payoffs):
    rows = [tuple(row) for row in payoffs]
    if not rows or not rows[0]:
        raise ValueError("payoff table must be nonempty")
    states = len(rows[0])
    if not all(len(row) == states for row in rows):
        raise ValueError("payoff table must be rectangular")
    if not all(type(x) is int or isinstance(x, Fraction)
               for row in rows for x in row):
        raise ValueError("use integer or Fraction payoffs")
    u = [tuple(Fraction(x) for x in row) for row in rows]
    best = [max(row[s] for row in u) for s in range(states)]
    regret = [tuple(best[s] - row[s] for s in range(states))
              for row in u]
    worst = [max(row) for row in regret]
    optimum = min(worst)
    choices = [i for i, value in enumerate(worst) if value == optimum]
    return regret, worst, choices

table = [(8, 7, 1), (4, 6, 6), (0, 4, 10)]
regret, worst, choices = minimax_regret(table)
print(regret)
print(worst, choices)

返回的最优编号为一，即从零编号的 B 行。算法先逐列求基准，再逐行求最大差，最后比较各行最大值，与定义逐步对应。若有 m 个方案、k 种状态，按有理数运算次数计，时间为 $O (m k)$ ，因保留表格而使用 $O (m k)$ 额外空间；位运算成本还与数值长度有关。一个方案时所有遗憾为零；一个状态时，这一准则恰好选择该状态下收益最大的方案。

若输入的是越小越好的损失 $L (a, s)$ ，应使用 $r (a, s) = L (a, s) - min_{b} L (b, s)$ ，也可先把收益设为 $u = - L$ 。直接对损失使用“列最大值减当前值”，会把比较方向颠倒。

一次分析应同时给出状态集合、收益或损失的单位、逐状态基准和最大遗憾。若未来能持续观察并调整选择，多臂老虎机问题等学习模型会进一步计算信息的价值；本篇准则本身没有描述这种学习过程。

参考文献

↑ ^1.0 ^1.1 ^1.2 Edward Anderson、Stan Zachary，2022，Minimax decision rules for planning under uncertainty，§1—3，arXiv:2203.01420，关于遗憾定义、与最坏成本准则的区别，以及对状态和方案集合的敏感性。

[anderson-1] 1.0 ^1.1 ^1.2 Edward Anderson、Stan Zachary，2022，Minimax decision rules for planning under uncertainty，§1—3，arXiv:2203.01420，关于遗憾定义、与最坏成本准则的区别，以及对状态和方案集合的敏感性。

[1]