本系列是学习《动手学强化学习》 过程中做的摘抄。
2.1 状态和马尔科夫过程#
\(S_{t}\) 表示随机现象在某时刻 \(t\) 的取值，是一个向量随机变量，所有可能的状态组成状态集合 \(\mathcal{S}\)。 马尔科夫性质：当且仅当某时刻的状态只取决于上一时刻的状态，用公式表示为 \(P(S_{t+1} | S_t) = P(S_{t+1} | S_1, \cdots, S_t)\)。
虽然 \(t+1\) 时刻的状态只与 \(t\) 时刻的状态有关，但是 \(t\) 时刻的状态其实包含了 \(t-1\) 时刻的状态信息，通过这种链式的关系，历史的信息被传递到了现在。
马尔科夫过程是指具有马尔科夫性质的随机过程，也被称为马尔科夫链。通常用元组 \(<\mathcal{S}, \mathcal{P}>\) 描述一个马尔科夫过程，其中 \(\mathcal{S}\) 是有限数量的状态集合，\(\mathcal{P}\) 是状态转移矩阵，它定义了所有状态对之间的转移概率。
$$ \mathcal{P} = \left[ \begin{matrix} &P(s_1 | s_1) &\cdots &P(s_n | s_1) \\ &\vdots &\ddots &\vdots \\ &P(s_1 | s_n) &\cdots &P(s_n | s_n) \end{matrix} \right] $$终止状态不会再转移到其他状态，永远以概率 1 转移到自己。
2.2 马尔科夫奖励过程 MRP#
在马尔科夫过程的基础上加入奖励函数 \(r\) 和折扣因子 \(\gamma\)，就可以得到 MRP，即一个 MRP 由 \(<\mathcal{S}, \mathcal{P}, r, \gamma>\) 构成。
- \(r\) 是奖励函数，某个状态 \(s\) 的奖励 \(r(s)\) 指转移到该状态时可以获得的奖励的期望。
- \(0 \leq \gamma < 1\) 是折扣因子，引入折扣因子是因为远期利益具有一定的不确定性，有时更希望能够尽快获得一些奖励，所以需要对远期利益打一些折扣。\(\gamma\) 接近 0 更考虑短期奖励，\(\gamma\) 接近 1 更关注长期奖励。
回报：令 \(R_t\) 表示在时刻 \(t\) 获得的奖励，在一个 MRP 中，从 \(t\) 时刻状态 \(S_t\) 开始直到终止状态时，所有奖励的衰减之和称为回报，即 \(G_t = R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \cdots = \sum_{k=0}^{\infty} \gamma^k R_{t+k}\)。
价值函数：在 MRP 中，一个状态的期望回报被称为这个状态的价值，所有状态的价值就组成了价值函数。价值函数的输入为某个状态，输出为这个状态的价值，将其写成 \(V(s) = \text{E}[G_t | S_t = s]\)。
$$ \begin{equation*} \begin{aligned} V(s) &= \text{E} [G_t | S_t = s] = \text{E} [R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \cdots | S_t = s] \\ &=\text{E} [R_t + \gamma G_{t+1} | S_t = s] \\ &=\text{E} [R_t + \gamma V(S_{t+1}) | S_t=s] \end{aligned} \end{equation*} $$2.3 马尔科夫决策过程 MDP#
在 MRP 的基础上加入外界智能体的动作，就得到了马尔科夫决策过程。一个 MDP 由元组 \(<\mathcal{S}, \mathcal{A}, P, r, \gamma>\) 构成。
- \(\mathcal{A}\) 是动作的集合。
- \(r(s, a)\) 可以同时取决于状态和动作，在只取决于状态时，则退化为 \(r(s)\)。
- \(P(s' | s,a)\) 是状态转移函数，表示在状态 \(s\) 下执行动作 \(a\) 之后到达状态 \(s'\) 的概率。 注意，这里不再使用类似 MRP 定义中的状态转移矩阵，而是直接使用状态转移函数。
智能体根据当前状态从 \(\mathcal{A}\) 中选择一个动作的函数，被称为策略，通常用 \(\pi\) 表示。策略 \(\pi(a | s) = P(A_t = a | S_t = s)\) 表示在输入状态 \(s\) 的情况下采取动作 \(a\) 的概率。
在 MDP 中，由于马尔可夫性质的存在，策略 \(\pi\) 只需要与当前状态有关，不需要考虑历史状态。
动作价值函数 \(Q^{\pi} (s, a)\) 表示在 MDP 遵循策略 \(\pi\) 时，对当前状态 \(s\) 执行动作 \(a\) 得到的期望回报：
$$ Q^{\pi}(s,a)=\text{E}_{\pi} [G_t | S_t=s, A_t=a] = r(s, a) + \gamma \sum_{s' \in \mathcal{S}} P(s'|s, a) V^{\pi} (s') $$小结与贝尔曼方程#
- \(\mathcal{P}\) 状态转移矩阵，定义了所有状态对之间的转移概率；\(P(s'|s,a)\) 状态转移函数，表示在状态 \(s\) 下执行动作 \(a\) 之后到达状态 \(s'\) 的概率。状态转移函数与动作有关，并且状态转移函数更具有一般意义。
- \(\mathcal{A}\) 表示 Agent 动作的集合。
- \(R_t\) 表示在时刻 \(t\) 获得的奖励。
- \(r(s)\) 奖励函数，指转移到该状态时可以获得的奖励的期望，\(r(s) = \text{E} [R_t | S_t = s]\)；\(r(s, a)\) 可以同时取决于状态和动作。
- \(G_t\) 回报，指从 \(t\) 时刻状态 \(S_t\) 到终止状态时，所有奖励的衰减之和，\(G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k}\)。
- \(V(s)\) 状态价值函数，指一个状态的期望回报，\(V(s) = \text{E}[G_t | S_t = s]\)。
- 策略 \(\pi(a | s) = P(A_t = a | S_t = s)\) 表示在输入状态 \(s\) 的情况下采取动作 \(a\) 的概率
- \(Q^{\pi} (s, a)\) 动作价值函数，表示在 MDP 遵循策略 \(\pi\) 时，对当前状态 \(s\) 执行动作 \(a\) 得到的期望回报。
状态价值函数和动作价值函数之间的关系：
$$ \begin{equation*} \begin{aligned} & V^{\pi}(s) = \sum_{a \in \mathcal{A}} \pi(a | s) Q^{\pi}(s,a) \\ & Q^{\pi}(s,a)= r(s, a) + \gamma \sum_{s' \in \mathcal{S}} P(s'|s, a) V^{\pi} (s') \end{aligned} \end{equation*} $$贝尔曼方程#
马尔科夫奖励过程 MRP 中：
$$ V(s) = r(s) + \gamma \sum_{s' \in \mathcal{S}} P(s' | s) V(s') $$若一个 MRP 一共有 \(n\) 个状态，即 \(\mathcal{S} = \{s_1, s_2, \cdots, s_n\}\)，将所有状态的价值表示成一个列向量 \(\mathcal{V} = [V(s_1), V(s_2), \cdots, V(s_n)]^T\)；同理，将奖励函数表示成一个列向量 \(\mathcal{R} = [r(s_1), r(s_2), \cdots, r(s_n)]^T\)。于是可以将贝尔曼方程写成矩阵的形式：
$$ \mathcal{V}=\mathcal{R}+\gamma \mathcal{P} \mathcal{V} \Rightarrow \mathcal{V}=(\mathcal{I}-\gamma \mathcal{P})^{-1} \mathcal{R} $$上述解析解的计算复杂度是 \(O(n^3)\)，其中 \(n\) 是状态个数，因此这种方法只适用于很小的马尔可夫奖励过程。
贝尔曼期望方程#
马尔科夫决策过程 MDP 中：
$$ \begin{equation*} \begin{aligned} & V^{\pi}(s) = \sum_{a \in \mathcal{A}} \pi(a|s) \left( r(s,a)+\gamma \sum_{s' \in \mathcal{S}} P(s'|s, a) V^{\pi}(s') \right) \\ & Q^{\pi} (s,a) = r(s,a) + \gamma \sum_{s' \in \mathcal{S}} P(s'|s, a) \sum_{a' \in \mathcal{A}} \pi(a' | s') Q^{\pi}(s', a') \end{aligned} \end{equation*} $$贝尔曼最优方程#
最优策略 \(\pi^{*}(s)\) 下由相同的最优状态价值函数和最优动作价值函数：
$$ \begin{equation*} \begin{aligned} & V^{*}(s)=\max_{a \in \mathcal{A}} \{r(s,a)+\gamma \sum_{s' \in \mathcal{S}}P(s'|s,a)V^{*}(s') \} \\ & Q^{*}(s,a)=r(s,a) + \gamma \sum_{s' \in \mathcal{S}} P(s'|s,a) \max_{a' \in \mathcal{A}} Q^{*}(s',a') \end{aligned} \end{equation*} $$