基本概念

强化学习（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_{s}a$：表示状态转移概率。$P_{sa}$表示的是在当前$s\in S$状态下，经过$a\in A$作用后，会转移到的其他状态的概率分布情况。比如，在状态$s$下执行动作$a$，转移到$s^{\prime }$的概率可以表示为$p(s^{\prime }|s,a)$
• $R$: R是回报函数(reward function)。如果一组$(s,a)$转移到了下个状态$s^{\prime }$，那么回报函数可记为$r(s^{\prime }|s,a)$。如果$(s,a)$对应的下个状态$s^{\prime }$是唯一的，那么回报函数也可以记为$r(s,a)$

MDP的动态过程如下：某个智能体(agent)的初始状态为$s_0$，然后从 $A$ 中挑选一个动作$a_0$执行，执行后，agent 按$P_{sa}$概率随机转移到了下一个$s_1$状态，$s_1\in P_{s_0{a}_0}$。然后再执行一个动作$a_1$，就转移到了$s_2$，接下来再执行$a_2$…，我们可以用下面的图表示状态转移的过程。

如果回报r是根据状态s和动作a得到的，则MDP还可以表示成下图：

值函数

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

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

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

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

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

$V^{\pi }(s)=E_{\pi }[r_0+\gamma r_1+{\gamma }^2{r}_2+{\gamma }^3{r}_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^{\prime }|s,a)+\gamma V^{\pi }(s^{\prime })|s=s_0]$

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

上面提到的值函数称为状态值函数(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 }^i{r}_i|s_0=s,a_0=a]$

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

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

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

一个MDP的最优策略表示如下
${\pi }^{\ast }=argma{x}_{\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^{\prime }|s,a)+\gamma V^{\pi }(s^{\prime })]$

利用真实的立即回报$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^{\pi }(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 ma{x}_{\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 的核心思想了。

算法流程

参考文献

1. https://morvanzhou.github.io/tutorials/machine-learning/reinforcement-learning/5-1-policy-gradient-softmax1/
2. http://www.cnblogs.com/jinxulin/tag/增强学习/