原文：https://blog.csdn.net/v_JULY_v/article/details/128965854
目录强化学习极简入门：通俗理解MDP、DP MC TC和Q学习、策略梯度、PPO
第一部分 RL基础：什么是RL与MRP、MDP
1.1 入门强化学习所需掌握的基本概念
1.1.1 什么是强化学习：依据策略执行动作-感知状态-得到奖励
强化学习(Reinforcement Learning，简称RL)，是指基于智能体在复杂、不确定的环境中最大化它能获得的奖励，从而达到自主决策的目的。
经典的强化学习模型可以总结为下图的形式（可以理解为任何强化学习都包含这几个基本部分：智能体、行为、环境、状态、奖励）：
- Agent，一般译为智能体，就是我们要训练的模型，类似玩超级玛丽的时候操纵马里奥做出相应的动作，而这个马里奥就是Agent
- action(简记为(a))，玩超级玛丽的时候你会控制马里奥做三个动作，即向左走、向右走和向上跳，而马里奥做的这三个动作就是action
- Environment，即环境，它是提供reward的某个对象，它可以是AlphaGo中的人类棋手，也可以是自动驾驶中的人类驾驶员，甚至可以是某些游戏AI里的游戏规则
- reward(简记为(r))，这个奖赏可以类比为在明确目标的情况下，接近目标意味着做得好则奖，远离目标意味着做的不好则惩，最终达到收益/奖励最大化，且这个奖励是强化学习的核心
- State(简介为(s))，可以理解成环境的状态，简称状态
总的而言，Agent依据策略决策执行动作action，通过感知环境获取环境的状态state，进而得到奖励reward(以便下次再到相同状态时能采取更优的动作)，然后再继续按此流程“依据策略执行动作-感知状态--得到奖励”循环进行。
1.1.2 RL与监督学习的区别和RL方法的分类
RL和监督学习（supervised learning）的区别：
-
监督学习有标签告诉算法什么样的输入对应着什么样的输出（譬如分类、回归等问题）
所以对于监督学习，目标是找到一个最优的模型函数，使其在训练数据集上最小化一个给定的损失函数，相当于最小化预测误差
\(\text { 最优模型 }=\underset{E}{\arg \min }\{\mathcal{L}(y, f(x))\}\)
\(y\) 标签，\(x\) 特征, \(f\) 模型, \(\mathcal{L}\) 损失函数
-
RL没有标签告诉它在某种情况下应该做出什么样的行为，只有一个‘做出一系列行为后’最终反馈回来的reward，然后判断当前选择的行为是好是坏
相当于RL的目标是最大化智能体策略在和动态环境交互过程中的价值，而策略的价值可以等价转换成奖励函数的期望，即最大化累计下来的奖励期望
\(\text { 最优策略 }=\underset{\pi}{\arg \max }\left\{\mathbb{E}_{\pi}\left[\sum_{t-0}^{\infty} \gamma^{t} r\left(s_{t}, a_{t}\right)\right]\right\}\)
\(\pi\) 表示策略，即智能体在给定状态下选择动作的策略
\(\mathbb{E}_\pi\) 表示在策略 \(\pi\) 下的期望值
\(\gamma\) 是折扣因子，用于调整未来奖励的当前价值。
\(r\left(s_{t}, a_{t}\right)\) 是在时间 \(t\) 时，状态 \(s_t\) 和动作 \(a_t\) 对应的即时奖励。
\(\sum_{t-0}^{\infty} \gamma^{t} r\left(s_{t}, a_{t}\right)\) 表示从时间 \(t=0\) 开始到无穷大的累积奖励的总和。
-
监督学习如果做了比较坏的选择则会立刻反馈给算法
RL的结果反馈有延时，有时候可能需要走了很多步以后才知道之前某步的选择是好还是坏
-
监督学习中输入是独立分布的，即各项数据之间没有关联
RL面对的输入总是在变化，每当算法做出一个行为，它就影响了下一次决策的输入
进一步，RL为得到最优策略从而获取最大化奖励，有
-
基于值函数的方法，通过求解一个状态或者状态下某个动作的估值为手段，从而寻找最佳的价值函数，找到价值函数后，再提取最佳策略
比如Q-learning、DQN等，适合离散的环境下，比如围棋和某些游戏领域
-
基于策略的方法，一般先进行策略评估，即对当前已经搜索到的策略函数进行估值，得到估值后，进行策略改进，不断重复这两步直至策略收敛
① 比如策略梯度法(policy gradient，简称PG)，适合连续动作的场景，比如机器人控制领域
② 以及Actor-Criti(一般被翻译为演员-评论家算法)，Actor学习参数化的策略即策略函数，Criti学习值函数用来评估状态-动作对，不过，Actor-Criti本质上是属于基于策略的算法，毕竟算法的目标是优化一个带参数的策略，只是会额外学习价值函数，从而帮助策略函数更好的学习
③ 此外，还有对策略梯度算法的改进，比如TRPO算法、PPO算法，当然PPO算法也可称之为是一种Actor-Critic架构，下文会重点阐述
RL其实是一个马尔可夫决策过程(Markov decision process，MDP)，而为说清楚MDP，得先从随机过程、马尔可夫过程(Markov process，简称MP)开始讲起，
1.2 什么是马尔科夫决策过程
1.2.1 MDP的前置知识：随机过程、马尔可夫过程、马尔可夫奖励
如隐马尔可夫模型HMM学习最佳范例中所说：
-
有一类现象是确定性的现象，比如红绿灯系统，红灯之后一定是红黄、接着绿灯、黄灯，最后又红灯，每一个状态之间的变化是确定的
-
但还有一类现象则不是确定的，比如今天是晴天，谁也没法百分百确定明天一定是晴天还是雨天、阴天(即便有天气预报)
对于这种假设具有(M)个状态的模型
- 共有\(M^2\)个状态转移，因为任何一个状态都有可能是所有状态的下一个转移状态
- 每一个状态转移都有一个概率值，称为状态转移概率，相当于从一个状态转移到另一个状态的概率
- 所有的\(M^2\)个概率可以用一个状态转移矩阵表示
下面的状态转移矩阵显示的是天气例子中可能的状态转移概率：
也就是说，如果昨天是晴天，那么今天是晴天的概率为0.5，是多云的概率为0.375、是雨天的概率为0.125，且这三种天气状态的概率之和必为1
接下来，我们来抽象建模下。正如概率论的研究对象是静态的随机现象，而随机过程的研究对象是随时间演变的随机现象(比如天气随时间的变化)：
-
随机现象在某时刻t的取值是一个向量随机变量，用 \(S_t\) 表示
比如上述天气转移矩阵便如下图所示
\(\begin{bmatrix} s_1 \rightarrow s_1 & s_1 \rightarrow s_2 & s_1 \rightarrow s_3 \\ s_2 \rightarrow s_1 & s_2 \rightarrow s_2 & s_2 \rightarrow s_3 \\ s_3 \rightarrow s_1 & s_3 \rightarrow s_2 & s_3 \rightarrow s_3 \end{bmatrix}\)当然，这里是将数学表示替换为 LaTeX 格式的文本：
在某时刻 \(t\) 的状态 \(S_t\) 通常取决于 \(t\) 时刻之前的状态，我们将已知历史信息 \(\left(S_{1}, \ldots, S_{t}\right)\) 的下一个时刻的状态 \(S_{t+1}\) 的概率表示成 \(P\left(S_{t+1} \mid S_{1}, \ldots, S_{t}\right)\) 。
如此，便可以定义一个所有状态对之间的转移概率矩阵。
\(P = \begin{bmatrix} P(s_1|s_1) & P(s_2|s_1) & P(s_3|s_1) & \cdots & P(s_n|s_1) \\ P(s_1|s_2) & P(s_2|s_2) & P(s_3|s_2) & \cdots & P(s_n|s_2) \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ P(s_1|s_n) & P(s_2|s_n) & P(s_3|s_n) & \cdots & P(s_n|s_n) \end{bmatrix}\)
-
当且仅当某时刻的状态只取决于上一时刻的状态时，一个随机过程被称为具有马尔可夫性质，即 \(P(S_{t+1} \mid S_t) = P(S_{t+1} \mid S_1, \cdots, S_t)\)
当然了，虽说当前状态只看上一个状态，但上一个状态其实包含了更上一个状态的信息，所以不能说当下与历史是无关的
-
而具有马尔可夫性质的随机过程便是马尔可夫过程
在马尔可夫过程的基础上加入奖励函数 \(R\) 和折扣因子 \(\gamma\) ，就可以得到马尔可夫奖励过程(Markov reward process，MRP)。其中
-
奖励函数，某个状态 \(s\) 的奖励 \(R(s)\)，是指转移到该状态 \(s\) 时可以获得奖励的期望，有 \(R(s) = \mathbb{E}[R_{t+1} \mid S_t = s]\)
注意，有的书上奖励函数和下面回报公式中的 \(R_{t+1}\) 的下标 \(t+1\) 写为 \(t\)，其实严格来说，先有 \(t\) 时刻的状态动作之后才有 \(t+1\) 时刻的奖励，但应用中两种下标法又都存在，读者注意辨别
-
此外，实际中，因为一个状态可以得到的奖励是持久的，所有奖励的衰减之和称为回报，可用 \(G\) 表示当下即时奖励和所有持久奖励等一切奖励的加权和，考虑到一般越往后某个状态给的回报率越低，也即奖励因子或折扣因子越小，用 \(\gamma\) 表示，从而有
\(\begin{aligned} G_t &= R_{t+1} + \gamma \cdot R_{t+2} + \gamma^2 \cdot R_{t+3} + \gamma^3 \cdot R_{t+4} + \cdots \\ &= R_{t+1} + \gamma (R_{t+2} + \gamma \cdot R_{t+3} + \gamma^2 \cdot R_{t+4} + \cdots) \\ &= R_{t+1} + \gamma G_{t+1} \end{aligned}\)
举个例子，一个少年在面对“上大学、去打工、在家啃老”这三种状态，哪一种更能实现人生的价值呢？
相信很多人为长远发展都会选择上大学，因为身边有太多人因为上了大学，而好事连连，比如读研读博留学深造、进入大厂、娶个漂亮老婆、生个聪明孩子
当然了，上大学好处肯定多多，但上大学这个状态对上面4件好事所给予的贡献必然是逐级降低，毕竟越往后，越会有更多或更重要的因素成就更后面的好事，总不能所有好事都百分百归功于最开头选择了“上大学”这个状态/决策嘛
而一个状态的期望回报就称之为这个状态的价值，所有状态的价值则组成了所谓的价值函数，用公式表达为\(V(s) = \mathbb{E}[G_t \mid S_t = s]\)
展开为
\(\begin{aligned} V(s) &= E[G_t \mid S_t = s] \\ &= E[R_{t+1} + \gamma G_{t+1} \mid S_t = s] \\ &= E[R_{t+1} \mid S_t = s] + \gamma E[G_{t+1} \mid S_t = s] \\ &= E[R_{t+1} \mid S_t = s] + \gamma E[V(S_{t+1}) \mid S_t = s] \end{aligned}\)
在上式最后一个等式中
- 前半部分表示当前状态得到的即时奖励 \(E[R_{t+1} \mid S_t = s] = R(s)\)
- 后半部分表示当前状态得到的所有持久奖励 \(\gamma E[V(S_{t+1}) \mid S_t = s]\)，可以根据从状态 \(s\) 出发的转移概率得到
至于上述推导的最后一步，在于 \(E[G_{t+1} \mid S_t = s]\) 等于 \(E[V(S_{t+1}) \mid S_t = s]\)
推导过程
\(\begin{aligned} E[G_{t+1} \mid S_t = s] &= \sum G_{t+1} P\{ G_{t+1} \mid S_t = s \} \\ &= \sum G_{t+1} \sum_{s'} P\{ G_{t+1} \mid S_{t+1} = s', S_t = s \} P\{ S_{t+1} = s' \mid S_t = s \} \\ &= \sum_{s'} \sum G_{t+1} P\{ G_{t+1} \mid S_{t+1} = s', S_t = s \} P\{ S_{t+1} = s' \mid S_t = s \} \\ &= \sum_{s'} E[G_{t+1} \mid S_{t+1} = s', S_t = s] P\{ S_{t+1} = s' \mid S_t = s \} \\ &= \sum_{s'} V(S_{t+1}) P\{ S_{t+1} = s' \mid S_t = s \} \\ &= E[V(S_{t+1}) \mid S_t = s] \end{aligned}\)
对于上述第二个等式，只需推导出
\(P\{ G_{t+1} \mid S_t = s \} = \sum_{s'} P\{ G_{t+1} \mid S_{t+1} = s', S_t = s \} P\{ S_{t+1} = s' \mid S_t = s \}\)
推导过程如下
\(\begin{aligned} P\{ G_{t+1} \mid S_t = s \} &= \frac{P\{ G_{t+1}, S_t = s \}}{P(S_t = s)} \\ &= \frac{\sum_{s'} P\{ G_{t+1}, S_{t+1} = s', S_t = s \}}{P(S_t = s)} \\ &= \frac{\sum_{s'} P\{ G_{t+1} \mid S_{t+1} = s', S_t = s \} P(S_{t+1} = s', S_t = s)}{P(S_t = s)} \\ &= \frac{\sum_{s'} P\{ G_{t+1} \mid S_{t+1} = s', S_t = s \} P(S_{t+1} = s' \mid S_t = s) P(S_t = s)}{P(S_t = s)} \\ &= \sum_{s'} P\{ G_{t+1} \mid S_{t+1} = s', S_t = s \} P(S_{t+1} = s' \mid S_t = s) \end{aligned}\)
从而，综合前后两个部分可得 \(V(s) = R(s) + \gamma \sum_{s' \in S} P(s' \mid s) V(s')\)
而这就是所谓的贝尔曼方程(bellman equation)。该公式精准而简洁，其背后浓缩了很多信息，为形象起见，举个例子
比如状态 \(S_1\) 得到的即时奖励为 \(R(S_1)\)，然后接下来，有P_12的概率引发状态 \(S_2\)，此时状态\(S_2\)得到的即时奖励为\(R(S_2)\)，对于\(S_2\)，接下来有\(P_{24}\)的概率引发状态\(S_4\)，\(S_4\)得到的即时奖励为\(R(S_4)\)...
...
其中折扣因此为\(\gamma\)，那么因状态\(S_1\)而得到的一切奖励为
\(R_{s1} + \gamma (P_{12}R_{s2} + P_{13}R_{s3}) + \gamma^2(P_{24} R_{s4} + P_{25} R_{s5}) + \gamma^2(P_{36} R_{s6} + P_{37}R_{s7}) \\ = R_{s1} + \gamma (P_{12}R_{s2} + P_{13}R_{s3}) + \gamma^2(P_{24} R_{s4} + P_{25} R_{s5} + P_{36} R_{s6} + P_{37}R_{s7})\)
为更加形象起见，再举一个生活中最常见的“吃饭-抽烟/剔牙”例子
比如你吃完饭后你自己的心情愉悦值即奖励\(+5\)，然后下一个状态，有
\(0.6\)的概率是抽烟(抽烟带来的心情愉悦值即奖励\(+7\)
\(0.4\)的概率是剔牙(剔牙带来的奖励值\(+3\))
假设折扣因子\(\gamma\) 为\(0.5\)，且假定
吃饭的状态定义为\(s_1\)，则\(R_{s1} = 5\)
抽烟的状态定义为\(s_2\)，则\(R_{s2} = 7\)，且由于抽烟之后无后续状态，所以\(G_{s2}\)也是7
剔牙的状态定义为\(s_3\)，则\(R_{s3} = 3\)，且由于剔牙之后无后续状态，所以\(G_{s3}\)也是3
从而有：
当从\(s_1 \rightarrow s_2\)时，\(G_{s1} = R_{s1} + \gamma R_{s2} = 5 + 0.5 \times 7 = 8.5\)
当从\(s_1 \rightarrow s_3\)时，\(G'_{s1} = R_{s1} + \gamma R_{s3} = 5 + 0.5\times 3 = 6.5\)
由于状态\(s_2\)和状态\(s_3\)没有后续状态，
所以\(s_2\)和\(s_3\)对应的状态价值函数分别为 \(V_{s2} = R_{s2} = 7\)， \(V_{s3} = R_{s3} = 3\)
再根据贝尔曼方程\(V(s) = R(s) + \gamma \sum_{s'\in S}^{}P(s'|s)V(s')\)
可得状态\(s_1\)的状态价值函数为
\(\begin{aligned} V(s_1) &= R_{s1} + \gamma (P_{12}R_{s2} + P_{13}R_{s3}) \\ &= 5 + 0.5 \times (0.6 \times 7 + 0.4 \times 3) \\ &= 7.7 \end{aligned}\)
当然，你也可以如此计算（可以很明显的看出，计算量不如上述过程简洁，所以一般优先按上述方式计算）
\(\begin{aligned} V(s_1) &= E[G_t \mid S_t = s] \\ &= p_{12} \times G^{s2}_{s1} + p_{13} \times G^{s3}_{s1} \\ &= P_{12} (R_{s1} + \gamma R_{s2}) + P_{13} (R_{s1} + \gamma R_{s3}) \\ &= 0.6(5 + 0.5 \times 7) + 0.4(5 + 0.5 \times 3) \\ &= 7.7 \end{aligned}\)
上述例子的状态比较少所以计算量不大，但当状态一多，则贝尔曼方程的计算量还是比较大的，而求解较大规模的马尔可夫奖励过程中的价值函数时，可以用的方法包括：动态规划、蒙特卡洛方法、时序差分(temporal difference，简称TD)方法