强化学习基础

基本概念

强化学习（reinforcementlearning, RL）是近年来机器学习和智能控制领域的主要方法之一。强化学习关注的是智能体如何在环境中采取一系列行为，从而获得最大的累计回报
通过强化学习，一个智能体知道在什么状态下应该采取什么行为。RL是从环境状态到动作的映射学习，我们把这个映射称为策略（Policy）
强化学习和监督学习的区别

增强学习是试错学习(Trail-and-error)，由于没有直接的指导信息，智能体要以不断与环境进行交互，通过试错的方式来获得最佳策略。
延迟回报，增强学习的指导信息很少，而且往往是在事后（最后一个状态）才给出的，这就导致了一个问题，就是获得正回报或者负回报以后，如何将回报分配给前面的状态。

马尔科夫决策过程

马尔科夫链是指，从一个状态到另一个状态的转换的随机过程。该过程要求具备“无记忆”的性质：下一状态的概率分布只能由当前状态决定，在时间序列中它前面的事件均与之无关。这种特定类型的“无记忆性”称作马尔可夫性质。
马尔可夫决策过程(Markov Decision Process,MDP)也具有马尔可夫性，与上面不同的是MDP考虑了动作，即系统下个状态不仅和当前的状态有关，也和当前采取的动作有关

马尔科夫决策过程推导

一个马尔科夫决策过程由一个四元组构成 $M=(S, A, P_{sa}, R)$

$S$ ：表示状态集(states), 有 $s \in S$ , $s_i$ 表示第 $i$ 步的状态
$A$ : 表示一组动作(actions)，有 $a \in A$ ， $a_i$ 表示第 $i$ 步的动作
$P_sa$ ：表示状态转移概率。 $P_{sa}$ 表示的是在当前 $s \in S$ 状态下，经过 $a \in A$ 作用后，会转移到的其他状态的概率分布情况。比如，在状态 $s$ 下执行动作 $a$ ，转移到 $s'$ 的概率可以表示为 $p(s'|s,a)$
$R$ : R是回报函数(reward function)。如果一组 $(s,a)$ 转移到了下个状态 $s'$ ，那么回报函数可记为 $r(s'|s, a)$ 。如果 $(s,a)$ 对应的下个状态 $s'$ 是唯一的，那么回报函数也可以记为 $r(s,a)$

MDP的动态过程如下：某个智能体(agent)的初始状态为 $s_0$ ，然后从 $A$ 中挑选一个动作 $a_0$ 执行，执行后，agent 按 $P_{sa}$ 概率随机转移到了下一个 $s_1$ 状态， $s_1 \in P_{s_0a_0}$ 。然后再执行一个动作 $a_1$ ，就转移到了 $s_2$ ，接下来再执行 $a_2$ …，我们可以用下面的图表示状态转移的过程。
强化学习基础
如果回报r是根据状态s和动作a得到的，则MDP还可以表示成下图：

值函数

强化学习学到的是一个从环境状态到动作的映射（即行为策略），记为策略 $π: S→A$ 。而强化学习往往又具有延迟回报的特点:因而需要定义值函数(value function，又叫效用函数)来表明当前状态下策略 $π$ 的长期影响。

用 $V^{\pi}(s)$ 表示策略 $\pi$ 下，状态 $s$ 的值函数。 $r_i$ 表示未来第 $i$ 步的立即回报，常见的值函数有一下三种

未来有限h步的期望立即回报总和： $V^{\pi}(s)=E_{\pi}[\sum_{i=0}^hr_i|s_0=s]$
采用策略π的情况下期望的平均回报： $V^{\pi}(s)=E_{\pi}[\frac{1}{h}\sum_{i=0}^hr_i|s_0=s]$
值函数最常见的形式: $V^{\pi}(s)=E_{\pi}[\sum_{i=0}^\infty \gamma ^ir_i|s_0=s]$

接下来我们只讨论第三种形式，式中 $\gamma$ 称为折合因子，表明了未来的回报相对于当前回报的重要程度。特别的， $\gamma =0$ 时，相当于只考虑立即不考虑长期回报， $\gamma = 1$ 时，将长期回报和立即回报看得同等重要。

现在将值函数的第三种形式展开，其中 $r_i$ 表示未来第 $i$ 步回报， $s'$ 表示下一步状态，则有：

$V^{\pi}(s)=E_{\pi}[r_0+\gamma r_1 + \gamma^2r_2 + \gamma^3r_3+...|s_0=s]$
$=E_{\pi}[r_0+\gamma E[r_1 + \gamma r_2 + \gamma^2 r_3+...]|s_0=s]$
$=E_{\pi}[r(s'|s,a)+\gamma V^{\pi}(s')|s=s_0]$

给定策略 $\pi$ 和初始状态 $s$ ，则动作 $a=\pi(s)$ ，下个时刻将以概率 $p(s'|s,a)$ 转向下个状态 $s'$ ，那么上式的期望可以拆开，可以重写为：
$V^{\pi}(s)=\sum_{s'\in S}p(s'|s,a)[r(s'|s,a)+\gamma V^{\pi}(s')]$

上面提到的值函数称为状态值函数(state value function)，需要注意的是， $V^{\pi}(s)$ 中， $\pi$ 和初始状态 $s$ 是我们给定的，而初始动作 $a$ 是由策略 $\pi$ 和状态 $s$ 决定的，即 $a=\pi(s)$ 。

定义**动作值函数（action value function）**如下:

$Q^{\pi}(s,a)=E_{\pi}[\sum_{i=0}^\infty \gamma ^ir_i|s_0=s,a_0=a]$

给定当前状态 $s$ 和当前动作 $a$ ，在未来遵循策略 $\pi$ ，那么系统将以概率 $p(s'|s,a)$ 转向下个状态 $s'$ ，上式可以重写为：

$Q^{\pi}(s,a)=\sum_{s'\in S}p(s'|s,a)[r(s'|s,a)+\gamma V^{\pi}(s')]$

在 $Q^{\pi}(s,a)$ ,不仅策略 $\pi$ 和初始状态 $s$ 是我们给定的，当前的动作a也是我们给定的，这是 $Q^{\pi}(s,a)$ 和 $V^{\pi}(a)$ 的主要区别。

一个MDP的最优策略表示如下
$\pi^{\ast} = arg max_{\pi}V^{\pi}(s), (\bigvee s)$

即我们寻找的是在任意初始条件 $s$ 下，能够最大化值函数的策略 ${\pi}^{\ast}$ 。

Temporal-Difference learning

在介绍时间差分学习(TD learning)之前，先引入蒙特卡罗算法，称为constant-α MC，它的状态值函数更新公式如下：

$V(s_t){\leftarrow}V(s_t)+\alpha[R_t-V(s_t)]$

其中 $R_t$ 是每个episode结束后获得的实际累积回报， $\alpha$ 是学习率，这个式子的直观的理解就是用实际累积回报 $R_t$ 作为状态值函数 $V(s_t)$ 的估计值。具体做法是对每个episode，考察实验中 $s_t$ 的实际累积回报 $R_t$ 和当前估计 $V(s_t)$ 的偏差值，并用该偏差值乘以学习率来更新得到 $V(S_t)$ 的新估值。

现在我们将公式修改如下，把 $R_t$ 换成 $r_{t+1}+\gamma V(s_t+1)$ ,就得到了TD(0)的状态函数更新公式：

$V(s_t){\leftarrow}V(s_t)+\alpha[r_{t+1}+\gamma V(s_{t+1})-V(s_t)]$

回忆下状态值函数的定义：

$V^{\pi}(s) = E_{\pi}[r(s'|s,a)+\gamma V^{\pi}(s')]$

利用真实的立即回报 $r_{t+1}$ 和下个状态的值函数 $V(s_{t+1})$ 来更新 $V(s_t)$ ，这种就方式就称为时间差分(temporal difference)。

Sarsa

强化学习算法可以分为在线策略(on-policy)和离线策略(off-policy)两类。sarsa算法属于on-policy算法。sarsa算法估计的是动作值函数而非状态值函数。也就是说，我们估计的是策略 $\pi$ 下，任意状态 $s$ 上所有可执行的动作 $a$ 的动作值函数 $Q^{π}(s,a)$ 。

sarsa的动作值函数更新公式如下：

$Q(s_t,a_t)\leftarrow Q(s_t,a_t) + \alpha [r_{t+1}+\lambda Q(s_{t+1},a_{t+1}) - Q(s_t,a_t)]$

由于动作值函数的每次更新都与 $(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})$ 相关，因此算法被命名为sarsa算法。sarsa算法的完整流程图如下：
强化学习基础

Q-learning

在sarsa算法中，选择动作时遵循的策略和更新动作值函数时遵循的策略是相同的，即 $ϵ−greedy$ 的策略，而在接下来介绍的Q-learning中，动作值函数更新则不同于选取动作时遵循的策略，这种方式称为离线策略(Off-Policy)。Q-learning的动作值函数更新公式如下：

$Q(s_t,a_t)\leftarrow Q(s_t,a_t) + \alpha [r_{t+1}+\lambda max_{\alpha}Q(s_{t+1},a_{t}) - Q(s_t,a_t)]$

可以看到，Q-learning与sarsa算法最大的不同在于更新Q值的时候，直接使用了最大的Q(st+1,a)值——相当于采用了Q(st+1,a)值最大的动作，并且与当前执行的策略，即选取动作at时采用的策略无关
强化学习基础

Q-learning和Sarsa算法对比
强化学习基础
从算法来看, 这就是他们两最大的不同之处了. 因为 Sarsa 是说到做到型, 所以我们也叫他 on-policy, 在线学习, 学着自己在做的事情. 而 Q learning 是说到但并不一定做到, 所以它也叫作 Off-policy, 离线学习. 而因为有了 maxQ, Q-learning 也是一个特别勇敢的算法。

Deep Q Network

我们使用表格来存储每一个状态 state, 和在这个 state 每个行为 action 所拥有的 Q 值. 而当状态很多的时候，使用表格存储效率就很低了.DQN利用神经网络，将状态和动作当成神经网络的输入,然后经过神经网络分析后得到动作的 Q 值, 这样我们就没必要在表格中记录 Q 值, 而是直接使用神经网络生成 Q 值. 还有一种形式的是这样, 我们也能只输入状态值, 输出所有的动作值, 然后按照 Q learning的原则,直接选择拥有最大值的动作当做下一步要做的动作. 我们可以想象, 神经网络接受外部的信息, 相当于眼睛鼻子耳朵收集信息, 然后通过大脑加工输出每种动作的值, 最后通过强化学习的方式选择动作.

算法流程如下所示：
强化学习基础

Policy Gradient

简介

强化学习是一个通过奖惩来学习正确行为的机制. 家族中有很多种不一样的成员, 有学习奖惩值, 根据自己认为的高价值选行为, 比如 Q learning, Deep Q Network, 也有不通过分析奖励值, 直接输出行为的方法, 这就是今天要说的 Policy Gradients 了. 甚至我们可以为 Policy Gradients 加上一个神经网络来输出预测的动作. 对比起以值为基础的方法, Policy Gradients 直接输出动作的最大好处就是, 它能在一个连续区间内挑选动作, 而基于值的, 比如 Q-learning, 它如果在无穷多的动作中计算价值, 从而选择行为, 这, 它可吃不消.

核心思想

举个简单的例子来说明policy gradient的核心思想。假设一个智能体有左右两个可选动作。假如这次的观测信息让神经网络选择了右边的行为, 右边的行为随之想要进行反向传递, 使右边的行为下次被多选一点, 这时, 获得了一个正的奖励。告诉我们这是好行为, 那我们就在这次反向传递的时候加大力度, 让它下次被多选的幅度更猛烈! 这就是 Policy Gradients 的核心思想了。

算法流程