马尔可夫决策过程

马尔可夫决策过程（Markov Decision Processes, MDP）为智能体在不确定性环境中进行决策提供了一个数学模型。其核心思想是，智能体的下一个状态只与当前状态和所选动作有关，而与之前的历史无关。

一个MDP由以下几个关键部分定义：

状态集合：一个包含所有可能状态的集合 $S$ 。
动作集合：一个包含智能体可以执行的所有动作的集合 $A$ 。
转移函数： $T(s, a, s')$ 是一个概率函数，表示在状态 $s$ 执行动作 $a$ 后，转移到状态 $s'$ 的概率。由于环境具有不确定性，一个动作可能导致多种结果。
奖励函数： $R(s, a, s')$ 表示在状态 $s$ 执行动作 $a$ 并转移到 $s'$ 后，智能体获得的即时奖励。奖励可以是正的或负的。智能体的目标是最大化累积奖励。
折扣因子：一个介于0和1之间的值 $\gamma$ ，用于平衡即时奖励和未来奖励的重要性。未来的奖励会被“打折”。
起始状态 和 终止状态：智能体从起始状态开始，当进入终止状态时，过程结束。

智能体的目标是选择一系列动作来最大化其长期收益，这个收益被称为效用 (Utility)。

智能体的决策过程可以看作一个序列：

s_0 \xrightarrow{a_0} s_1 \xrightarrow{a_1} s_2 \xrightarrow{a_2} s_3 \dots

最简单的效用是所有奖励的直接加和：

U([s_0, a_0, s_1, a_1, \dots]) = R(s_0, a_0, s_1) + R(s_1, a_1, s_2) + R(s_2, a_2, s_3) + \dots

如果没有时间限制或终止状态，智能体可能会永远选择安全但低奖励的动作来获得无限的奖励。为了解决这个问题，我们引入折扣因子 $\gamma$ 。

折扣因子 $\gamma$ (其中 $0 < \gamma < 1$ ) 体现了“未来的奖励不如眼前的奖励有价值”的思想。在 $t$ 时刻获得的奖励，其价值会被乘以 $\gamma^t$ 。

因此，智能体需要最大化的折扣效用 (Discounted Utility) 变为：

U([s_0, a_0, s_1, \dots]) = R(s_0, a_0, s_1) + \gamma R(s_1, a_1, s_2) + \gamma^2 R(s_2, a_2, s_3) + \dots = \sum_{t=0}^{\infty} \gamma^t R(s_t, a_t, s_{t+1})

这个无限序列的和是收敛的，只要奖励值有上限 $R_{max}$ ，其总效用不会超过 $\frac{R_{max}}{1-\gamma}$ 。这保证了即使在无限时间的任务中，总效用也是一个有限值，从而使比较不同策略成为可能。

MDP的核心是马尔可夫性质 (Markov Property)，也称为“无记忆性”。它指出，未来只取决于现在，而与过去无关。

换句话说，在给定当前状态 $s_t$ 和当前动作 $a_t$ 的情况下，下一个状态 $s_{t+1}$ 的概率分布与所有过去的状态和动作 $(s_0, a_0, \dots, s_{t-1}, a_{t-1})$ 是条件独立的。

数学上可以表示为：

P(S_{t+1}=s_{t+1} | S_t=s_t, A_t=a_t, S_{t-1}=s_{t-1}, \dots) = P(S_{t+1}=s_{t+1} | S_t=s_t, A_t=a_t)

这正是转移函数 $T$ 所编码的信息：

T(s, a, s') = P(s' | s, a)

这个性质极大地简化了决策问题，因为智能体在做决策时只需要考虑当前所处的状态，而不需要追溯完整的历史。