强化学习根底篇 [2]：SARSA、Q-learning 算法简介、利用举例、优缺点剖析
1.SARSA
SARSA（State-Action-Reward-State-Action）是一个学习马尔可夫决策过程策略的算法，通常利用于机器学习和强化学习学习畛域中。它由 Rummery 和 Niranjan 在技术论文“Modified Connectionist Q-Learning（MCQL）”中介绍了这个算法，并且由 Rich Sutton 在注脚处提到了 SARSA 这个别名。
State-Action-Reward-State-Action 这个名称分明地反馈了其学习更新函数依赖的 5 个值，别离是以后状态 S1，以后状态选中的动作 A1，取得的处分 Reward，S1 状态下执行 A1 后获得的状态 S2 及 S2 状态下将会执行的动作 A2。咱们取这 5 个值的首字母串起来能够得出一个词 SARSA。
1.1 根底概念
算法的核心思想能够简化为：
$$
Q(S_{t},A_{t})=Q(S_{t},A_{t})+\alpha[R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_{t},A_{t})]
$$
其中 $Q(S_{t+1},A_{t+1})$ 是下一时刻的状态和理论采取的口头对应的 Q 值，$Q(S_{t},A_{t})$ 是以后时刻的状态和理论采取的形同对应的 Q 值。折扣因子 $\gamma$ 的取值范畴是 [0 , 1]，其本质是一个衰减值，如果 gamma 更靠近 0，agent 趋向于只思考刹时处分值，反之如果更靠近 1，则 agent 为提早处分赋予更大的权重，更侧重于提早处分；处分值 $R_{t+1}$ 为 t + 1 时刻失去的处分值。$\alpha$ 为是学习率。
1.2 利用举例
将一个结冰的湖看成是一个 4×4 的方格，每个格子能够是起始块（S），指标块（G）、解冻块（F）或者危险块（H），指标是通过上下左右的挪动，找出能最快从起始块到指标块的最短门路来，同时防止走到危险块上，（走到危险块就意味着游戏完结）为了引入随机性的影响，还能够假如有风吹过，会随机的让你向一个方向漂移。
图 1: 初始化
左图是每个地位对应的 Q value 的表，最后都是 0，一开始的策略就是随机生成的，假设第一步是向右，那依据上文公式，假设学习率是 $\alpha$ 是 0.1，折现率 $\gamma$ 是 0.5，而每走一步，会带来 -0.4 的处分，那么（1.2）的 Q value 就是 0 + 0.1 ×[-0.4 + 0.5× (0)-0] = -0.04，为了简化问题，此处这里没有假如湖面有风。
图 2: 走一步
假如之后又接着往右走了一步，用相似的办法更新（1，3）的 Q value 了，失去（1.3）的 Q value 还为 -0.04
图 3: 走一步
等到了下个时刻，骰子通知咱们要往左走，此时就须要更新（1，2）的 Q -value，计算式为：V(s) = 0 +0.1× [-0.4 + 0.5× (-0.04)-0) ]
图 4: 走一步
从这里，智能体就能学到先向右在向左不是一个好的策略，会浪费时间，顺次类推，一直依据之前的状态更新右边的 Q table，直到指标达成或游戏完结。
图 5: 走一步
假如当初智能体达到了如图 5 所示的地位，当初要做的是依据公式，更新（3，2）这里的 Q value，因为向下走的 Q -value 最低，假设学习率是 0.1，折现率是 0.5，那么（3，2）这个点向下走这个策略的更新后的 Q value 就是，Sarsa 会随机选一个 action, 比方这里抉择的是 (Q(4,2),down)：
$$ Q((3,2) down) = Q((3,2) down ) + 0.1× (-0.4 + 0.5 × (Q( (4,2) down) )- Q((3,2), down））$$
$$ Q((3,2), down) = 0.6 + 0.1× (-0.4 + 0.5 × 0.4 – 0.6)=0.52 $$
1.3 优缺点
SARSA 算法常常与 Q -learning 算法作比拟，以便摸索出两种算法别离实用的状况。它们互有利弊。
与 SARSA 相比，Q-learning 具备以下长处和毛病：
- Q-learning 间接学习最优策略，而 SARSA 在摸索时学会了近乎最优的策略。
- Q-learning 具备比 SARSA 更高的每样本方差，并且可能因而产生收敛问题。当通过 Q -learning 训练神经网络时，这会成为一个问题。
- SARSA 在靠近收敛时，容许对探索性的口头进行可能的惩办，而 Q -learning 会间接疏忽，这使得 SARSA 算法更加激进。如果存在靠近最佳门路的大量负面报酬的危险，Q-learning 将偏向于在摸索时触发处分，而 SARSA 将偏向于防止危险的最佳门路并且仅在摸索参数缩小时缓缓学会应用它。
如果是在模仿中或在低成本和疾速迭代的环境中训练代理，那么因为第一点（间接学习最优策略），Q-learning 是一个不错的抉择。如果代理是在线学习，并且重视学习期间取得的处分，那么 SARSA 算法更加实用。
2.Q-learning
首先咱们看一下上图 Q -learning 在整个强化学习的地位，Q-Learning 是属于值函数近似算法中，蒙特卡洛办法和工夫差分法相结合的算法。它在 1989 年被 Watkins 提出，能够说一出世就给强化学习带来了重要的冲破。
Q-Learning 假如可能呈现的动作 a 和状态 S 是无限多，这时 a 和 S 的全副组合也是无限多个，并且引入价值量 Q 示意智能体认为做出某个 a 时所可能取得的利益。在这种假如下，智能体收到 S，应该做出怎么的 a，取决于抉择哪一个 a 能够产生最大的 Q。上面的表格显示了动物在面对环境的不同状态时做出的 a 对应着怎么的 Q，这里为了简略阐明只别离列举了 2 种 S 和 a：
显然，如果此时 S =” 后方有食物 ”，抉择 a =” 向前走 1 米 ”，失去的利益 Q =”1″ 显然比抉择 a =” 向后走 1 米 ” 的 q =”0″ 要大，所以这时应该抉择向前走；绝对的后方如果有天敌，往前走显然没有任何利益，这时抉择最大的利益就要向后走。这种表格在 Q -Learning 中被称为 Q 表，表中的 S 和 a 须要当时确定，表格主体的数据——q 在初始化的时候被随机设置，在后续通过训练失去改正。
2.1 根底概念
Q-Learning 的训练过程是 Q 表的 Q 值逐步调整的过程，其外围是依据曾经晓得的 Q 值，以后抉择的口头 a 作用于环境取得的回报 R 和下一轮 $S_{t+1}$ 对应能够取得的最大利益 Q，总共三个量进行加权求和算出新的 Q 值，来更新 Q 表：
$$
Q(S_{t},A_{t})=Q(S_{t},A_{t})+\alpha[R_{t+1}+\gamma \mathop{max}_{a} Q(S_{t+1},a)-Q(S_{t},A_{t})]
$$
其中 $Q(S_{t+1}, a)$ 是在 $t+1$ 时刻的状态和采取的口头（并不是实际行动，所以公式采纳了所有可能采取行动的 Q 的最大值）对应的 Q 值，$Q(S_{t},A_{t})$ 是以后时刻的状态和理论采取的形同对应的 Q 值。折扣因子 $\gamma$ 的取值范畴是 [0 , 1]，其本质是一个衰减值，如果 gamma 更靠近 0，agent 趋向于只思考刹时处分值，反之如果更靠近 1，则 agent 为提早处分赋予更大的权重，更侧重于提早处分；处分值 $R_{t+1}$ 为 t + 1 时刻失去的处分值。$\alpha$ 为是学习率。
这里动作价值 Q 函数的指标就是迫近最优的 $q*$ $q*=R_{t+1}+\gamma \mathop{max}_{a} Q(S_{t+1},a)$，并且轨迹的口头策略与最终的 $q*$ 是无关的。前面中括号的加和式示意的是 $q*$ 的贝尔曼最优方程近似模式。
2.2 利用举例
将一个结冰的湖看成是一个 4×4 的方格，每个格子能够是起始块（S），指标块（G）、解冻块（F）或者危险块（H），指标是通过上下左右的挪动，找出能最快从起始块到指标块的最短门路来，同时防止走到危险块上，（走到危险块就意味着游戏完结）为了引入随机性的影响，还能够假如有风吹过，会随机的让你向一个方向漂移。
图 1: 初始化
左图是每个地位对应的 Q value 的表，最后都是 0，一开始的策略就是随机生成的，假设第一步是向右，那依据上文公式，假设学习率是 $\alpha$ 是 0.1，折现率 $\gamma$ 是 0.5，而每走一步，会带来 -0.4 的处分，那么（1.2）的 Q value 就是 0 + 0.1 ×[-0.4 + 0.5× (0)-0] = -0.04，为了简化问题，此处这里没有假如湖面有风。
图 2: 走一步
假如之后又接着往右走了一步，用相似的办法更新（1，3）的 Q value 了，失去（1.3）的 Q value 还为 -0.04
图 3: 走一步
等到了下个时刻，骰子通知咱们要往左走，此时就须要更新（1，2）的 Q -value，计算式为：V(s) = 0 +0.1× [-0.4 + 0.5× (-0.04)-0) ]
图 4: 走一步
从这里，智能体就能学到先向右在向左不是一个好的策略，会浪费时间，顺次类推，一直依据之前的状态更新右边的 Q table，直到指标达成或游戏完结。
图 5: 走一步
假如当初智能体达到了如图 5 所示的地位，当初要做的是依据公式，更新（3，2）这里的 Q value，因为向下走的 Q -value 最低，假设学习率是 0.1，折现率是 0.5，那么（3，2）这个点向下走这个策略的更新后的 Q value 就是：
$$ Q((3,2) down) = Q((3,2) down ) + 0.1× (-0.4 + 0.5 × max [Q( (4,2) action) ]- Q((3,2), down））$$
$$ Q((3,2), down) = 0.6 + 0.1× (-0.4 + 0.5 × max [0.2, 0.4, 0.6] – 0.6)=0.53 $$
2.3 优缺点
Q-Learning 算法有一些毛病，比方状态和动作都假如是离散且无限的，对于简单的状况解决起来会很麻烦；智能体的决策只依赖以后环境的状态，所以如果状态之间存在时序关联那么学习的成果就不佳。
更多文章请关注公重号：汀丶人工智能