强化学习课程学习系列笔记，RL Course by David Silve，按照课程顺序，每节课一篇博客笔记，主要记录课程内容和个人理解。
1. Markov Processes
Markov决策过程形式化地描述了RL Agent所处的环境，这里的环境假定是完全可观测的，即当前的state可以完整得描述整个过程。之所以要介绍Markov决策过程 (MDP) 是因为几乎所有的RL问题都可以形式化的定义成Markov决策过程，比如最优化控制是连续的MDPs，任何部分可观测问题也可以转换成MDPs，Bandits也是特殊的MDP（所谓Bandits指的是只给定一组可选的Action，你无法估计每个action可以带来的收益，你需要选择一个action，然后会返回你一个reward[1]）
1.1 Markov Property
Markov 性质用一言以蔽之就是：“The future is independent of the past given the present”，数学一点的表述是，A state $S_t$ is Markov if and only if：
\mathbb{P}\left[S_{t+1} \mid S_{t}\right]=\mathbb{P}\left[S_{t+1} \mid S_{1}, \ldots, S_{t}\right]
$$
这其实在上一篇笔记中提到过，简单来说就是当前的状态 $S_t$ 可以等价于历史的所有状态 $S_{1}, \ldots, S_{t}$，所以一旦确定了 $S_t$，就可以舍弃所有的历史信息 $S_{1}, \ldots, S_{t-1}$，因为当前的状态 $S_t$ 足以用于预测未来。
也就是说，对于一个Markov的状态 $s$ ，我们可以仅依靠 $s$ 的信息，获得从 $s$ 转移到某个后继状态 $s^\prime$ 的概率 ，定义为：
\mathcal{P}_{s s^{\prime}}=\mathbb{P}\left[S_{t+1}=s^{\prime} \mid S_{t}=s\right]
$$
以此类推，我们可以获得一个概率矩阵，表示从所有状态 $s$ 转移到所有可能的后继状态的概率：
\mathcal{P}=\left[\begin{array}{ccc}
\mathcal{P}_{11} & \ldots & \mathcal{P}_{1 n} \\
\vdots & & \\
\mathcal{P}_{n 1} & \ldots & \mathcal{P}_{n n}
\end{array}\right]
$$
由概率的定义不难得出，矩阵的每一行之和为1.
1.2 Markov Process
Markov Process（又称为Markov Chain）是一个完全基于概率的随机过程，即一个随机状态的序列，每个状态满足Markov 性质，数学定义为：
以课堂中学生的状态转移为例，初始状态为上第一节课（Class1），其中有0.5的概率对课程不感兴趣，转而刷Facebook，并以0.9的概率一直沦陷在Facebook的世界中；同时有0.5的概率进入第二节课，在第二节课中可能会疲惫，因此有0.2的概率睡着了，有0.8的概率继续去上第三节课，并有0.6的概率通过最终的课程；通过课程后就能安心睡觉，在这个例子中睡觉是终止状态，不会转移到任何其他状态；此外，在第三节课，学术还有0.4的概率去酒吧，并有不同的概率前往三节课程（喝醉了，走错教室了？）。上述的过程就是一个Markov Process转移，可以建立一个Markov Chain Transition Matrix（下图右）。
在Markov Process中还有一个定义Sample，指的是一条从初始状态到最终状态的随机采样得到的序列，例如：
- C1 C2 C3 Pass Sleep
- C1 FB FB C1 C2 Sleep
- C1 FB FB C1 C2 C3 Pub C1 FB FB FB C1 C2 C3 Pub C2 Sleep
都是一种可能的Sample episode.
2. Markov Reward Processes
2.1 Definition of MRP
在Markov Process的基础上引入reward的概念，则称之为Markov Reward Processes，其形式化定义如下：
这里的 $\mathcal{S}$ 和 $\mathcal{P}$ 在上一节的Markov Process已经提到过了。 $\mathcal{R}$ 指的是奖励函数，注意这里指的是即时奖励，也就是说它衡量的是当前状态为 $S_t = s$ 时，接下来的一次状态转移所能获得的reward的期望是多少。$\gamma$ 是衰减系数，控制较远的未来Reward的影响，在下一节Return会涉及。
2.2 Return
Return $G_t$ 表示的是从 $t$ 时间步开始的某个Markov Process采样的reward累计和（因此这里不是一个期望，而是直接累加，因为$G_t$本身就是通过一个随机采样序列得到的），这里的reward是经过discounted的：
G_{t}=R_{t+1}+\gamma R_{t+2}+\ldots=\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1}
$$
$\gamma$ 就是discounted factor，衡量更关心即时reward还是延迟reward：
- $\gamma$接近0， 表示更关心短期的收益。
- $\gamma$接近1， 表示更关心长远的收益。
在大多数Markov Reward中都会使用discounted factor，基于以下几点原因：
- 在数学计算中，使用折扣可以简化很多推导和公式，使得理论分析和算法实现更加便利。特别是在计算累积奖励时，折扣使得无穷和（infinite sum）收敛。
- 在某些循环的马尔可夫决策过程中，如果没有折扣因子，累积回报可能会变得无限大，这是不可取的。折扣因子的引入可以防止这种无限回报的出现，使得累积回报保持有限。
- 未来的情况往往是不确定的，折扣因子可以自然地反映出这种不确定性。未来的奖励越远，它们的价值就越不确定，因此我们会对未来的奖励打折扣，体现出它们的重要性降低。
- 在财务或经济情境中，立即获得的奖励可能比延迟获得的奖励更有价值，因为立即获得的资金可以用于投资或生息，从而获得更多的收益。因此，折扣因子可以用来反映资金的时间价值。
- 在行为心理学中，研究表明动物和人类通常更偏好立即获得的奖励，而不是延迟的奖励。折扣因子可以模拟这一偏好，帮助智能体在决策过程中更符合自然行为的特点。
当然，有时候我们也可以不使用折扣因子（$\gamma = 1$），比如当所有序列都必然终止（例如在一个有限步数的过程或终止条件明确的任务中）。这意味着未来的奖励不会被打折，所有的奖励都被视为同等重要。
继续以学生上课举例，假设折扣因子$\gamma = 0.5$，我们可以计算每个sample的return：
2.3 Value Function
value function衡量的是状态 $s$ 的一个长期价值，换句话说就是从某个状态$S_t$开始的期望 Return $G_t$：
v(s)=\mathbb{E}\left[G_{t} \mid S_{t}=s\right]
$$
就是从状态 $s$ 开始所有可能的state sample对应的return的期望（某个sample的概率乘以Return值）。下图为学生上课例子在不同折扣因子下的Value指。
2.4 Bellman Equation
Value Function可以递归得被分解成两个部分：即时奖励 $R_{t+1}$ 和经过折扣因子计算后的后续状态的value $\gamma v(S_{t+1})$，因此value function可以以递归的形式表示：
\begin{aligned}
v(s) & =\mathbb{E}\left[G_{t} \mid S_{t}=s\right] \\
& =\mathbb{E}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\ldots \mid S_{t}=s\right] \\
& =\mathbb{E}\left[R_{t+1}+\gamma\left(R_{t+2}+\gamma R_{t+3}+\ldots\right) \mid S_{t}=s\right] \\
& =\mathbb{E}\left[R_{t+1}+\gamma G_{t+1} \mid S_{t}=s\right] \\
& =\mathbb{E}\left[R_{t+1}+\gamma v\left(S_{t+1}\right) \mid S_{t}=s\right]\\
&=\mathcal{R}_{s}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}} v\left(s^{\prime}\right)
\end{aligned}
$$
上式被称为Bellman Equation，其中$\mathcal{P}_{s s^{\prime}}$ 表述从状态 $s$ 到状态 $s^{\prime}$ 转移的概率。由此可以通过递归的方式从终止状态递归推得所有的value function值，举例：
此外，Bellman Function还可以表示成矩阵的形式 $v = \mathcal{R} + \gamma \mathcal{P}v$：
\left[\begin{array}{c}
v(1) \\
\vdots \\
v(n)
\end{array}\right]=\left[\begin{array}{c}
\mathcal{R}_{1} \\
\vdots \\
\mathcal{R}_{n}
\end{array}\right]+\gamma\left[\begin{array}{ccc}
\mathcal{P}_{11} & \ldots & \mathcal{P}_{1 n} \\
\vdots & & \\
\mathcal{P}_{11} & \ldots & \mathcal{P}_{n n}
\end{array}\right]\left[\begin{array}{c}
v(1) \\
\vdots \\
v(n)
\end{array}\right]
$$
由此我们可以得到Bellman Equation是一个线性等式，如果矩阵不大，可以直接通过求逆得到 $v$ 的解：
\begin{align*}
\mathbf{v} &= \mathcal{R} + \gamma \mathcal{P} \mathbf{v} \\
(I – \gamma \mathcal{P}) \mathbf{v} &= \mathcal{R} \\
\mathbf{v} &= (I – \gamma \mathcal{P})^{-1} \mathcal{R}
\end{align*}
$$
这一计算的复杂度为 $O(n^3)$ ，所以只适合较小的MRP问题，除此之外还有其他迭代式的方法用于解决复杂的MRP问题，比如Dynamic programming，Monte-Carlo evaluation，Temporal-Difference learning.
3. Markov Decision Processes
3.1 MDP Definition
目前为止，我们已经引入了四个元素了，完整的Markov Decision Process（MDP）还包含一个元素 Action，用 $\mathcal{A}$ 表示，MDP可以看成一种所有state都是Markov的environment，形式化定义为：
在之前我们介绍的Markov过程中，状态转移概率只取决于状态本身，而在MDP中，状态转移是依赖于状态State和动作Action，同时Reward也受Action影响，这样我们就把整个系统变成了一个Agency，可以通过采取Action来影响state之间的转移概率，从而影响整个系统。
3.2 Policy
MDP中引入了Action，Action是一个有限的集合，那么我们在每个状态下应该采取什么样的Action呢？这就需要引入Policy的概念了，Policy是一个概率分布，表示在给定State下采取某个Action的概率：
\pi(a \mid s) = \mathbb{P}[A_t = a \mid S_t = s]
$$
因此一个Policy就完全定义了一个Agent的所有行为，MDP Policy只依赖于当前state，与历史记录和时间无关。
给定一个MDP $\mathcal{M} = \langle \mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma \rangle$ 以及一个policy $\pi$，状态序列 $S_1, S_2, …$ 就是一个Markov过程，即$\langle \mathcal{S}, \mathcal{P^{\pi}}\rangle$ ，状态和奖励序列 $S_1,R_2,S_2…$ 就是一个MRP，即 $\langle \mathcal{S}, \mathcal{P^{\pi}}, \mathcal{R^{\pi}}, \gamma \rangle$ ，其中：
\mathcal{P}^{\pi}_{s,s'} = \sum_{a \in \mathcal{A}} \pi(a \mid s) \mathcal{P}^{a}_{ss'} \\
\mathcal{R}^{\pi}_{s} = \sum_{a \in \mathcal{A}} \pi(a \mid s) \mathcal{R}^{a}_{s}
$$
3.3 Value Function
以下是MDP中涉及的两种value function，其中state-value function表述的是基于某一个policy，状态$s$的期望Return，action-value function表述的是基于某一个policy，状态$s$下执行动作$a$的期望Return. 理解要点：value表述的是return的期望，也就是对于整个未来（直到终止状态）收益的预测。注意与MRP中value function的区别。
3.4 Bellman Expectation Equation
同理，state-value function和action-value function也可以递归得求解，称为Bellman Expectation Equation，具体为：
- state-value function：
\begin{align*}
v_{\pi}(s) &= \mathbb{E}_{\pi} \left[ R_{t+1} + \gamma v_{\pi}(S_{t+1}) \mid S_{t} = s \right]
\\
& = \sum_{a \in \mathcal{A}} \pi(a \mid s) q_{\pi}(s, a)
\\
& = \sum_{a \in \mathcal{A}} \pi(a \mid s) \left( \mathcal{R}_{s}^{a} + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'}^{a} v_{\pi}(s') \right)
\end{align*}
$$
- action-value function:
\begin{align*}
q_{\pi}(s, a) &= \mathbb{E}_{\pi} \left[ R_{t+1} + \gamma q_{\pi}(S_{t+1}, A_{t+1}) \mid S_{t} = s, A_{t} = a \right]\\
&= \mathcal{R}_{s}^{a} + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'}^{a} v_{\pi}(s')\\
&= \mathcal{R}_{s}^{a} + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'}^{a} \sum_{a' \in \mathcal{A}} \pi(a' \mid s') q_{\pi}(s', a')
\end{align*}
$$
举例计算action-value function，假定policy是一个正态分布，即每个action的概率相同，在图中7.4的状态中，我们有两个Action可以选择（Study 学习 or Pub 去酒吧），其中去酒吧这一行动会转移到三种可能的状态，对应三个不同的概率（0.2，0.4，0.4），Study行为只会转移到一个结束状态，即终止状态：
同样Bellman Expectation Equation 也有矩阵形式，以及可以通过求逆得解：
v_{\pi} = \mathcal{R}^{\pi} + \gamma \mathcal{P}^{\pi} v_{\pi}\\
v_{\pi} = \left(I – \gamma \mathcal{P}^{\pi}\right)^{-1} \mathcal{R}^{\pi}
$$
3.5 Optimal Value Function
Optimal Value Function也有两种，$v_*$ 和 $q_*$ 表示的是，所有潜在的Policy中，最优的 state-value 和 action-value function是什么，如果我们知道了Optimal Value Function，我们就可以说我们解决了一个MDP问题。
还是以学生MDP的为例，展示最优的Value Function：
3.6 Optimal Policy
要定义什么是最优的Policy，首先我们需要定义Policy的一个偏序关系（即两个Policy的比较方式）：
\pi \geq \pi' \text{ if } v_{\pi}(s) \geq v_{\pi'}(s), \forall s
$$
对于MDP，有以下几个理论，都是很直观的：
因此我们可以通过获取每一个最大的 $q_*(s,a)$ 得到一个最优的Policy：
\pi_{*}(a \mid s) =
\begin{cases}
1 & \text{if } a = \arg\max\limits_{a \in \mathcal{A}} q_{*}(s, a) \\
0 & \text{otherwise}
\end{cases}
$$
因此，对于任何一个MDP问题，都有一个确定的最优Policy，基于这个Policy下，在每个state下采取的action都是100%确定的。在学生MDP的例子中，依据最优的value function q，可以获得最优的Policy（图中红线）：
3.7 Bellman Optimality Equation
那么如何求解最优的value function呢？思想其实是很直观的：
- 对于state-value function（下图左），它表示的是当前状态可以获得的最大价值，所以我们去寻找在当前状态下，选取一个最优的action，通过执行该action，我们可以获得最大的action-value $q_*(s,a)$，这就是当前状态的最优value $v_*(s)$.
- 对于action-value function（下图右），它表示的是当前状态下执行一个确定的action后可以获得的最大价值，由于action已经确定了，我们首先可以获得执行这一行动的即时reward，即$\mathcal{R}^a_s$，然后我们求一下执行这一动作可能转移到的所有state的最大期望value之和（通过状态转移概率乘以对应状态的最优state-value获得期望），就是最优的action-value.
可以发现state-value function可以由action-value function确定（这一步主要是选择max action），然后action-value function又可以由state-value function确定（这一步主要是在确定的action下预测state-value期望）。首先，我们需要弄清的要点是：在MDP中，RL Agent是通过各种Action来参与到environment的state转移中的。因此，MDP可以看成两个步骤，1. Agent基于当前State选择一个Action执行。2. environment根据Action和当前的State给出转移到后继State的概率。所以，我们在求解 optimal value function时也可以分两步走（黑点表示一个Action，白圈表示一个State）：
- 对于optimal state-value function，我们先选择一个Action，然后environment根据这个Action按照一定的概率转移到若干state. 所以我们要保证state-value function是最优的，只能去寻找最优的Action，使得收获的即时reward $\mathcal{R}^a_s$ 加上所有执行该action后可能转移到的后继state对应的optimal state-value期望之和是最优的（下图左）。
- 对于optimal action-value function，我们已经选好了一个action，所以$\mathcal{R}^a_s$是确定的一个值，同时我们也知道我们会以多少概率转移到若干个可能的后继状态 $s^{\prime}$，那么我们需要确保的是每个后继状态执行的后继action是最优的，这样才能使得我们可以得到最大的后继value，然后将后继value乘以转移到该后继state的概率，作为期望，将期望求和，代表在状态s下，执行动作a的期望最大value，即optimal action-value function.
文字可能表述的有点晦涩，看图容易理解，当你理解了就会发现这就是左脚踩右脚，螺旋飞升。由于需要求max，所以Bellman Optimality Equation是非线性的，不能用矩阵求逆来求解，也没有一个确定的求解公式，常用迭代法处理，例如：Value Iteration，Policy Iteration， Q-learning，Sarsa.
4. Extensions to MDPs
下面是一些复杂MDP的例子，算是对上述MDP的拓展，简单介绍，本人也暂时没深入了解，之后如果用到了可以回过来深入理解！
4.1 Infinite MDPs
-
可数无限的状态和/或动作空间：即使状态或动作空间是可数无限的（可以列出一个序列的无穷状态或动作），MDP框架仍然可以直接应用，而无需大幅修改。
-
连续的状态和/或动作空间：在状态和动作空间是连续的情况下，MDP框架可以扩展。LQR（linear quadratic model）是一个在连续空间中有封闭解的控制问题的例子。
-
连续时间：
- 需要偏微分方程：在连续时间设置下，系统的动态由偏微分方程描述，而非差分方程。
- 哈密顿-雅可比-贝尔曼（HJB）方程：用于描述连续时间控制问题中的最优值函数。
- 贝尔曼方程的极限情况，当时间步长趋于0：HJB方程可以看作是当时间步趋近于零时贝尔曼方程的极限情况，实际上是从离散时间转变为连续时间的过程。
4.2 POMDP
部分可观测马尔科夫决策过程 Partially Observable Markov Decision Process （POMDP）是一种包含隐藏状态的MDP，定义如下：
由于POMDP中状态的不可完全观测性，即Agent无法直接观察到系统的确切状态，而只能通过某些观测（观察到的迹象、信号等）间接推测状态，所以Agent需要自己构建一套State的转移方式，称为Belief States ，定义如下，简单来说就是一种概率分布，表示在给定历史（即所有过去的动作、观测和奖励序列）的情况下，系统可能处于不同状态的概率。：
由于上述的历史 H 是Markov的，belief state 也是Markov的，所以：
- 历史树（History Tree）：图中左侧显示了一个历史树的结构。历史树中的每个节点代表一个时间点的历史记录，该记录包括了所有过去的动作和观测。历史树是无限的，因为理论上可以有无限多的动作和观测序列。POMDP 可以归约为一个（无限）历史树。
- 信念树（Belief Tree）：图中右侧显示了一个信念树的结构。信念树中的每个节点表示一个信念状态，即一个关于系统当前状态的概率分布。信念树也是无限的，因为信念状态会随着每一次动作和观测不断更新。POMDP 可以归约为一个（无限）信念状态树。
4.3 Average Reward MDPs
4.3.1 Definition
遍历马尔科夫过程（ergodic Markov process）是指这样一种马尔科夫过程，它满足以下两个性质：
- 重现性（Recurrent）：每个状态都会被无限次数地访问。这意味着在无限的时间范围内，系统总会再次进入到任何一个特定的状态。这种性质确保了系统不会“丢失”某些状态。
- 无周期性（Aperiodic）：每个状态被访问时没有固定的周期。也就是说，系统返回到某个状态的时间间隔不是固定的，而是随机的。这意味着系统不会在一种固定的循环模式下运行。
遍历马尔科夫过程具有一个极限平稳分布（limiting stationary distribution），表示系统在长时间运行后，进入某个状态 s 的概率分布。这种分布不会随着时间的进一步推移而改变，表示系统达到了某种平衡状态。下面的公式表示的是在平稳状态下，系统在状态 $s$ 的概率 $d^{\pi}(s)$ 是所有可能前一状态 $s^′$ 的平稳概率 $d^{\pi}(s’)$ 与从$s^′ $转移到 $s$ 的转移概率 $P_{s’s}$ 的加权和。
遍历马尔科夫过程（ergodic Markov process）定义：一个马尔科夫决策过程（MDP）是遍历的，如果由任意策略（policy）诱导的马尔科夫链是遍历的。也就是说，不论选择什么策略，系统的状态都会遍历到所有可能的状态，并且这些状态之间的转移没有固定的周期。
4.3.2 average reward
对于任何策略$\pi$，一个遍历的MDP具有每时间步的平均奖励 average reward per time-step，记作 $\rho^{\pi}$，并且该平均奖励与起始状态无关：
\rho^{\pi} = \lim_{T \to \infty} \frac{1}{T} \mathbb{E}\left[\sum_{t=1}^{T} R_t\right]
$$
这个公式描述了在长期运行中，每一个时间步的期望平均奖励$\rho^{\pi}$ 是如何计算的：
- $\sum_{t=1}^{T} R_t$ 表示在前 (T) 个时间步中获得的累计奖励。
- $\frac{1}{T}$ 是计算平均奖励的除数，表示每个时间步的奖励。
- $lim_{T \to \infty}$ 表示当时间 (T) 趋近于无穷时，这个平均奖励的极限值。
4.3.3 value function
未折扣的遍历MDP的价值函数可以用平均奖励来表示，用：$\tilde{v}_{\pi}(s)$ 表示从状态 $s$ 开始所得到的额外奖励：
\tilde{v}_{\pi}(s) = \mathbb{E}_{\pi} \left[ \sum_{k=1}^{\infty} \left( R_{t+k} – \rho^{\pi} \right) \mid S_t = s \right]
$$
这意味着 $\tilde{v}_{\pi}(s)$ 是从状态 $s$ 开始，扣除平均奖励 $\rho^{\pi}$ 后累积的额外奖励的期望值。
4.3.4 Bellman function
$$ \tilde{v}_{\pi}(s) = \mathbb{E}_{\pi} \left[ \left( R_{t+1} – \rho^{\pi} \right) + \sum_{k=1}^{\infty} \left( R_{t+k+1} – \rho^{\pi} \right) \mid S_t = s \right] $$
$$ \tilde{v}_{\pi}(s) = \mathbb{E}_{\pi} \left[ \left( R_{t+1} – \rho^{\pi} \right) + \tilde{v}_{\pi}(S_{t+1}) \mid S_t = s \right] $$
这个贝尔曼方程表示，在状态 $s$ 时的额外奖励 $\tilde{v}_{\pi}(s)$ 是下一个时间步的即时奖励减去平均奖励 $\rho^{\pi}$ 以及从下一个状态 $S_{t+1}$ 开始的未来额外奖励的和。这为在未折扣的遍历MDP中计算最优策略提供了基础。
