贝尔曼方程

与在确定的搜索问题中寻找一个通往目标状态的最优“计划”不同，解决一个马尔可夫决策过程意味着寻找一个最优策略 (Optimal Policy)。

策略 $\pi$ 是一个从状态 $s \in S$ 到动作 $a \in A$ 的映射，即 $\pi: S \to A$ 。它定义了一个“反射式”智能体：给定一个状态 $s$ ，智能体会立即选择动作 $a = \pi(s)$ ，而不考虑其未来的长期后果。

一个最优策略 $\pi^*$ 是指，如果智能体遵循该策略，它将获得最大的期望总回报。

为了求解MDP，我们需要引入贝尔曼方程，但首先要定义两个关键的价值函数。

状态的最优价值 $V^*(s)$ (Optimal Value of a State)：一个从状态 $s$ 出发、并且始终采取最优行动的智能体，在其未来生命周期中所能获得的期望总效用。
Q-状态的最优价值 $Q^*(s, a)$ (Optimal Value of a Q-State)：一个智能体从状态 $s$ 开始，执行动作 $a$ ，然后从那以后始终采取最优行动所能获得的期望总效用。

可以这么理解： $V^*(s)$ 是 “当前状态的前景有多好”，表示的是当前这个状态的潜力；而 $Q^*(s, a)$ 是 “决定执行动作 $a$ 后得到的结果有多好”，表示的是一个具体选择的价值。

利用这两个新概念，贝尔曼方程被定义为：

V^*(s) = \max_{a} \sum_{s'} T(s, a, s')[R(s, a, s') + \gamma V^*(s')]

其中， $T(s, a, s')$ 是转移概率， $R(s, a, s')$ 是奖励， $\gamma$ 是折扣因子。

我们先定义Q-值的计算公式：

Q^*(s, a) = \sum_{s'} T(s, a, s')[R(s, a, s') + \gamma V^*(s')]

这个公式可以理解为：一个选择的价值等于在执行这个选择遇到的各种情况（到达的各种 $s'$ 状态）的期望总回报，而这个回报包含两个方面：即时奖励和未来价值，也就是奖励函数和 $s'$ 的状态最优价值。这个在后面有详细讲解

通过Q-值的定义，贝尔曼方程可以被重写为：

V^*(s) = \max_{a} Q^*(s, a)

这个公式清晰地揭示了三者之间的关系：

\pi^*(s) = \arg\max _{a} Q^*(s, a)

贝尔曼方程是一个动态规划方程，它通过其内在的递归结构将复杂问题分解为更小的子问题。

递归子问题: 核心在于 $[R(s, a, s') + \gamma V^*(s')]$ $[R (s, a, s^{'}) + γ V^{*} (s^{'})]$ 这一项。
- 它代表了从状态 $s$ 执行动作 $a$ 到达后继状态 $s'$ ，然后从 $s'$ 开始一直采取最优行动所能获得的总效用。
- 它由两部分组成：即时奖励 $R(s, a, s')$ 和后继状态的未来最优价值 $V^*(s')$ 。
- $V^*(s')$ 被折扣因子 $\gamma$ 折扣，因为从 $s$ 到 $s'$ 经过了一个时间步。 $V^*(s')$ 本身封装了从 $s'$ 出发所有可能的复杂路径，并将其抽象为一个单一的递归值。
期望的计算: 完整的Q-值公式 $Q^*(s, a) = \sum_{s'} T(s, a, s') [R(s, a, s') + \gamma V^*(s')]$ $Q^{*} (s, a) = \sum_{s^{'}} T (s, a, s^{'}) [R (s, a, s^{'}) + γ V^{*} (s^{'})]$ 是一个加权和。
- 它计算了所有可能的后继状态 $s'$ 所能带来的总效用，并用其出现的概率 $T(s, a, s')$ 进行加权。
- 这正是从Q-状态 $(s, a)$ 出发所能获得的期望效用。
最大化选择: 最终，贝尔曼方程 $V^*(s) = \max _a Q*(s, a)$ 指出，一个状态的价值是所有可能动作中能产生的最大期望效用。这与Minimax算法中的Maximizer节点非常相似：我们先计算每个分支（动作 a）的期望值（Chance节点），然后选择其中最大的一个。

贝尔曼方程的实际用途是作为最优性的检验条件。如果我们能找到一组价值 $V(s)$ ，使得这组价值在所有状态 $s \in S$ 上都满足贝尔曼方程，那么我们就可以断定，这组价值就是该MDP的最优价值函数，即 $\forall s \in S, V(s) = V^*(s)$ 。