强化学习根底篇[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算法有一些毛病，比方状态和动作都假如是离散且无限的，对于简单的状况解决起来会很麻烦；智能体的决策只依赖以后环境的状态，所以如果状态之间存在时序关联那么学习的成果就不佳。

更多文章请关注公重号：汀丶人工智能