决策制定（AIMA Part IV）
本笔记对应 AIMA（Artificial Intelligence: A Modern Approach）第16–17章的内容，涵盖简单决策和复杂决策。前面的概率推理笔记解决了"世界是什么样的"（推断），本章进一步回答"应该做什么"（决策）。
1. 效用理论
1.1 期望效用最大化
一个理性智能体应当选择最大化期望效用（Maximum Expected Utility, MEU）的行动：
其中 \(U(s)\) 是状态 \(s\) 的效用函数，\(P(s \mid a)\) 是采取行动 \(a\) 后到达状态 \(s\) 的概率。
MEU 原则是 AIMA 中理性智能体设计的核心准则——它将概率推理（信念）与效用理论（偏好）统一在一个决策框架中。
1.2 效用函数与风险态度
效用函数 \(U: S \to \mathbb{R}\) 将结果映射为实数值，反映智能体的偏好。不同的效用函数形状反映不同的风险态度：
| 风险态度 | 效用函数形状 | 特征 |
|---|---|---|
| 风险中性 | 线性：\(U(x) = x\) | 只关心期望值 |
| 风险厌恶 | 凹函数：\(U(x) = \sqrt{x}\) | 偏好确定性收益，\(U(\mathbb{E}[x]) > \mathbb{E}[U(x)]\) |
| 风险偏好 | 凸函数：\(U(x) = x^2\) | 偏好赌博，\(U(\mathbb{E}[x]) < \mathbb{E}[U(x)]\) |
风险态度示例
考虑两个选择：(A) 确定获得 $100；(B) 50% 概率获得 $200，50% 概率获得 \(0。两者的期望金额相同（\)100），但风险厌恶者会选 A，风险偏好者会选 B。
1.3 效用函数的公理化基础
冯·诺伊曼和摩根斯特恩（von Neumann & Morgenstern）证明，如果智能体的偏好满足以下公理，则必然存在一个效用函数使其行为等价于 MEU：
| 公理 | 含义 |
|---|---|
| 完备性（Completeness） | 对任意两个结果 \(A, B\)，智能体能判断 \(A \succ B\)、\(B \succ A\) 或 \(A \sim B\) |
| 传递性（Transitivity） | 如果 \(A \succ B\) 且 \(B \succ C\)，则 \(A \succ C\) |
| 连续性（Continuity） | 如果 \(A \succ B \succ C\)，则存在概率 \(p\) 使得 \(B \sim [p: A;\ (1-p): C]\) |
| 独立性（Independence） | 如果 \(A \succ B\)，则对任意 \(C\) 和 \(p\)，\([p: A;\ (1-p): C] \succ [p: B;\ (1-p): C]\) |
违反这些公理的行为（如 Allais 悖论）虽然在人类中常见，但被视为非理性。
2. 信息价值
2.1 完美信息价值（VPI）
在做决策之前，智能体可以选择先收集信息再行动。完美信息价值（Value of Perfect Information, VPI）量化了获得某个变量真实值的期望收益：
其中 \(\alpha_{e_j}\) 是在知道 \(E_j = e_j\) 后的最优行动，\(\alpha\) 是当前信息下的最优行动。
VPI 的关键性质：
- \(\text{VPI}(E_j) \ge 0\)：信息不会有负价值（在期望意义下）
- VPI 不具有可加性：\(\text{VPI}(E_1, E_2) \neq \text{VPI}(E_1) + \text{VPI}(E_2)\)（一般情况下）
- 如果当前最优决策在任何 \(E_j\) 取值下都不会改变，则 \(\text{VPI}(E_j) = 0\)
2.2 信息收集决策
基于 VPI，智能体可以理性地决定是否值得花费成本去获取信息：
- 如果 \(\text{VPI}(E_j) > \text{Cost}(E_j)\)，则应收集该信息
- 在多个可收集信息源中，选择净价值最高的那个
- 这是一个元推理（meta-reasoning）问题：关于如何推理的推理
3. 决策网络
决策网络（Decision Network），也称影响图（Influence Diagram），是贝叶斯网络的扩展，用于建模决策问题。它包含三种节点：
| 节点类型 | 形状 | 含义 |
|---|---|---|
| 机会节点（Chance） | 椭圆形 | 随机变量（与贝叶斯网络中的节点相同） |
| 决策节点（Decision） | 矩形 | 智能体可以选择的行动 |
| 效用节点（Utility） | 菱形 | 给定父节点取值时的效用值 |
求解决策网络的过程：
- 设置证据变量
- 对于每个可能的决策值，计算效用节点的期望效用
- 选择使期望效用最大的决策
决策网络将概率推理和决策优化统一在一个图模型中，使得复杂决策问题的建模和求解变得直观。
4. 序贯决策：马尔可夫决策过程
4.1 MDP 定义
当决策涉及多个时间步时，我们进入序贯决策的领域。马尔可夫决策过程（Markov Decision Process, MDP）是建模序贯决策的标准框架：
| 元素 | 含义 |
|---|---|
| \(S\) | 状态空间 |
| \(A\) | 动作空间 |
| \(T(s' \mid s, a)\) | 状态转移概率 |
| \(R(s, a, s')\) | 奖励函数 |
| \(\gamma \in [0, 1)\) | 折扣因子 |
4.2 贝尔曼方程
最优值函数满足贝尔曼最优方程：
最优策略 \(\pi^*(s) = \arg\max_{a} Q^*(s, a)\)。
4.3 求解算法
| 算法 | 思路 | 复杂度 |
|---|---|---|
| 值迭代（Value Iteration） | 反复应用贝尔曼更新直到收敛 | 每次迭代 \(O(\|S\|^2 \|A\|)\) |
| 策略迭代（Policy Iteration） | 交替进行策略评估和策略改进 | 通常更少迭代次数 |
与强化学习的关系
MDP 是强化学习的理论基础。值迭代和策略迭代假设已知转移概率 \(T\) 和奖励函数 \(R\)（即"模型已知"），而强化学习处理的是模型未知的情况——智能体必须通过与环境交互来学习。详细内容请参见本站的强化学习笔记。
5. POMDP：部分可观测环境下的决策
5.1 定义
部分可观测马尔可夫决策过程（POMDP）在 MDP 的基础上增加了观测模型：
其中 \(\Omega\) 是观测空间，\(O(o \mid s', a)\) 是在执行动作 \(a\) 后到达状态 \(s'\) 时观察到 \(o\) 的概率。
5.2 信念状态
在 POMDP 中，智能体无法直接观察状态，而是维护一个信念状态（belief state）\(b(s) = P(S_t = s \mid h_t)\)，即基于历史观测和动作的状态概率分布。
信念更新遵循贝叶斯规则：
POMDP 可以转化为信念空间上的连续状态 MDP，但求解通常是计算上非常困难的（PSPACE-complete）。实际中常用点基值迭代（PBVI）等近似方法。
6. 博弈论与多智能体决策
6.1 博弈论基础
当环境中存在多个理性智能体时，单个智能体的最优决策取决于其他智能体的行为。博弈论（Game Theory）提供了分析这类情况的框架。
正规形式博弈由以下元素定义：
- 参与者集合 \(\{1, 2, \dots, n\}\)
- 每个参与者的策略集 \(S_i\)
- 每个参与者的效用函数 \(u_i(s_1, \dots, s_n)\)
6.2 纳什均衡
纳什均衡（Nash Equilibrium）是一组策略 \((s_1^*, \dots, s_n^*)\)，使得没有任何参与者能通过单方面改变策略来提高自己的效用：
| 概念 | 说明 |
|---|---|
| 纯策略均衡 | 每个参与者选择一个确定的动作 |
| 混合策略均衡 | 参与者在动作上定义概率分布 |
| Nash 存在性定理 | 任何有限博弈至少存在一个混合策略纳什均衡 |
经典示例：囚徒困境
两个嫌疑人各自决定合作（沉默）或背叛（供出对方）。纳什均衡是双方都背叛——尽管双方合作的结果对双方都更好。这说明个体理性不一定导致集体最优。
6.3 机制设计
机制设计（Mechanism Design）是博弈论的"逆问题"：给定期望的社会结果，如何设计规则（机制）使得理性参与者的均衡行为恰好产生该结果？
典型应用包括拍卖设计（如 Vickrey 拍卖中的真实出价激励）和投票机制。
交叉引用
与本站其他笔记的关联
参考资料
- Russell & Norvig, Artificial Intelligence: A Modern Approach, Chapters 16–17
- Kaelbling, Littman & Cassandra, "Planning and Acting in Partially Observable Stochastic Domains", Artificial Intelligence, 1998
- Myerson, Game Theory: Analysis of Conflict