【强化学习】相关基本概念
【强化学习】 Q-Learning
【强化学习】 Q-Learning 案例分析
【强化学习】 Sarsa
【强化学习】 Sarsa（lambda）

强化学习

强化学习（Reinforcement Learning，RL），也叫增强学习，是指一类从（与环境）交互中不断学习的问题以及解决这类问题的方法．是和监督学习，无监督学习并列的第三种机器学习方法

例如：(这个解释来自于：DQN（Deep Q-learning）入门教程（一）之强化学习介绍)

你现在在家，有两个动作选择：打游戏和读书。如果选择打游戏的话，你就跑到了网吧，选择读书的话，就坐在了书桌面前。你爸妈下班回家，如果发现你在网吧，就会给你一套社会主义的铁拳，如果你在书桌面前的话，就会买根棒棒糖给你吃。

首先，你在家的时候并不知道选择哪一个动作，因此你可能会选择study或者game。但是，当你接受了多次社会主义的毒打和奖励棒棒糖之后，你会发现选择game会得到惩罚，选择study你会得到奖励。因此当你再次处于”home“状态时，你就会偏向于选择“study”。（这便是强化学习！！）

可以描述为：一个智能体从与环境的交互中不断学习以完成特定目标（比如取得最大奖励值）

强化学习也是机器学习中的一个重要分支．强化学习和监督学习的不同在于，强化学习问题不需要给出“正确”策略作为监督信息，只需要给出策略的（延迟）回报，并通过调整策略来取得最大化的期望回报．

强化模型可以建模如下：

交互对象

在强化学习中，有两个可以进行交互的对象：智能体和环境．

（1） 智能体（Agent）：可以感知外界环境的状态（State）和反馈的奖励（Reward），并进行学习和决策．智能体的决策功能是指根据外界环境的状态来做出不同的动作（Action），而学习功能是指根据外界环境的奖励来调整策略．（有的地方也称Agent为代理）

（2） 环境（Environment）是智能体外部的所有事物，并受智能体动作的影响而改变其状态，并反馈给智能体相应的奖励．

Agent：Agent也就是执行个体，我们可以操作执行个体做出不同的选择（也就是动作Action），即：你自己
Environment：我们研究的环境，它有一个一个的状态（State）。即：网吧or书桌
Action：当Agent做出动作（Action）的时候，环境会发生改变也就是State会发生改变。即：选择study或game后你会处于书桌或者网吧的状态
Reward：当State发生改变时，环境会给予一定的奖励（奖励可为正负）。即：拳头or棒棒糖

建立情景-动作映射：智能体通过不断的尝试去发现环境能最大奖励的动作。动作不仅影响瞬时报酬，还会影响下一个场景，并由此影响后续的奖励。

基本要素

（1） 状态𝑠：是对环境的描述，可以是离散的或连续的，其状态空间为𝒮．
（2） 动作𝑎 ：是对智能体行为的描述，可以是离散的或连续的，其动作空间为𝒜．
（3） 策略𝜋(𝑎|𝑠) ：是智能体根据环境状态𝑠 来决定下一步动作𝑎 的函数．
（4） 状态转移概率𝑝(𝑠′|𝑠, 𝑎) ：是在智能体根据当前状态𝑠 做出一个动作𝑎 之后，环境在下一个时刻转变为状态𝑠′ 的概率．
（5） 即时奖励𝑟(𝑠, 𝑎, 𝑠′)：是一个标量函数，即智能体根据当前状态𝑠 做出动作𝑎 之后，环境会反馈给智能体一个奖励，这个奖励也经常和下一个时刻的状态𝑠′ 有关

策略(Policy)𝜋

当Agent处于某一个state的时候，它做的Action是不确定的，例如你可以选择study也可以选择game，也就是说你在某一个状态是以一定的概率去选择某一个action。也就是说，策略的选择是一个条件概率𝜋(a|s)，这里的𝜋与数序中的𝜋没有任何关系，他只是代表一个函数而已。

$\pi (a|s)=P(A_{t}=a|S_{t}=s)$
此函数代表：在状态s时采取动作a的概率分布。

价值(value)

前面我们说到过奖励，当Agent在t时刻执行某个动作时，会得到一个 $R_{t+1}$ 。我们可以想一下蝴蝶效应，这个Action会影响 $R_{t+1}$ ，那么他会不会影响 $R_{t+2}$ ， $R_{t+3}$ ……， $R_{t+n}$ 呢？很可能会的，比如说在电游中，你所做的某个选择肯定会对接下来的游戏产生影响，这个影响可以深远，也可以没那么深渊，因此状态价值函数可以表示为：

$v_{\pi }(s)=E_{\pi }(R_{t+1}+\gamma R_{t+2}+\gamma ^{2}R_{t+3}+...|S_{t}=s)$
$v_{\pi }(s)$ 与策略函数𝜋有关，可以理解为当Agent以策略𝜋运行时，状态s的价值是多少。也就是在此状态下，我能够得到多少回报。

$\gamma$ 奖励衰减因子

在上面的价值函数中，有一个变量 $\gamma$ ，即奖励衰减因子，在[0，1]之间。
如果为0，则是贪婪法，即价值只由当前的奖励决定；
如果是1，则所有的后续状态奖励和当前奖励一视同仁。一般来说取0到1之间的数。

环境的状态转化模型(状态转移概率)

由于在某个状态下，执行一定的action，能够达到新的一个状态 $state_{t+1}$ ，但是 $state_{t+1}$ 不一定是唯一的。环境的状态转化模型，可以理解为一个概率状态机，它是一个概率模型，即在状态s下采取动作a，转到下一个状态s′的概率，表示为 $P_{ss{}'}^{a}$ 或 𝑝(𝑠′|𝑠, 𝑎)

探索率ϵ

它主要是为了防止陷入局部最优。比如说目前在s1状态下有两个a1,a2。我们通过计算出，发现执行a1的动作比较好，但是为了防止陷入局部最优，我们会选择以 ϵ 的概率来执行a2，以1−ϵ 的概率来执行a1。一般来说，ϵ 随着训练次数的增加而逐渐减小。

马尔可夫决策过程(Markov Decision Process，MDP)

为简单起见，我们将智能体与环境的交互看作离散的时间序列．具体步骤如下：

Step1：智能体感知到的初始环境𝑠0 ，做一个相应的动作𝑎0，
Step2：环境相应地发生改变到新的状态𝑠1，并反馈给智能体一个即时奖励𝑟1，
Step3：然后智能体又根据状态𝑠1 做一个动作𝑎1，环境相应改变为𝑠2，并反馈奖励𝑟2，
Step...：这样的交互可以一直进行下去：𝑠0, 𝑎0, 𝑠1, 𝑟1, 𝑎1, ⋯ , $s_{T-1}$ , $a_{T-1}$ , $s_{T}$ , $r_{T}$

其中 $r_{t}=r(s_{t}-1,a_{t}-1,s_{t})$ 是第𝑡 时刻的即时奖励，与上一个状态、上一个行为、这个状态有关．如下图给出了智能体与环境的交互．

智能体与环境的交互过程可以看作一个马尔可夫决策过程（Markov Decision Process，MDP）．

问：为什么要把Agent与Environment的交互过程看作是MDP呢？
答：其实就是想表达一个思想，即：下一个状态 𝑠′ 只和当前状态 𝑠 与做出的动作 𝑎 相关，而马尔可夫过程中的思想是：下一个状态𝑠′ 只和当前状态 𝑠 相关
（如果没有理解，就继续往下看MP与MDP具体都是什么意思）

前面我们说过某个状态执行action可以转换成另外一个state，可以用概率表示为： $P_{ss{}'}^{a}$ 。那么这个概率与什么有关呢？认真的考虑下，毋庸置疑，与目前的状态 $s_{t}$ 和a有关，但是同样，它可能也与上一个状态 $s_{t-1}$ ，上上个状态 $s_{t-2}$ ……有关，但是如果真的这样考虑，就复杂了。

因此我们将问题进行一定的简化，简化的方法就是假设状态转化的马尔科夫性质

马尔可夫过程（Markov Process，MP）是一组具有马尔可夫性质的随机变量序列𝑠0, 𝑠1, ⋯， $s_{t}$ ∈ 𝒮，其中下一个时刻的状态 $s_{t+1}$ 只取决于当前状态 $s_{t}$ ，

$p(s_{t+1}|s_{t}...s_{0})=p(s_{t+1}|s_{t})$

其中 $p(s_{t+1}|s_{t})$ 称为状态转移概率，

马尔可夫决策过程(MDP)在马尔可夫过程(MP)中加入一个额外的变量：动作𝑎，下一个时刻的状态 $s_{t+1}$ 不但和当前时刻的状态 $s_{t}$ 相关，而且和动作 $a_{t}$ 相关，

其中 $p(s_{t+1}|s_{t},a_{t})$ 称为状态转移概率.

马尔可夫决策过程的图模型表示如下：

给定策略𝜋(𝑎|𝑠)，马尔可夫决策过程的一个轨迹（Trajectory）

𝜏 = 𝑠0, 𝑎0, 𝑠1, 𝑟1, 𝑎1, ⋯ , $s_{T}-1$ , $r_{T}-1$ , $a_{T}-1$ , $s_{T}$

的概率为：

也就是假设状态转化到下一个状态 s′ 的概率仅与当前状态 s 有关，与之前的状态无关（也就是说未来与当前有关，与过去无关）。用公式表示就是：

$P_{ss{}'}^{a}=\mathbb{P}(S_{t+1}=s{}'|S_{t}=s,A_{t}=a)$

同时对于策略 π 我们也做MDP假设，也就是说，当前Agent所作的策略仅仅与当前状态有关，与以前的状态都没有关系，因此:

$\pi (a|s)=P(A_{t}=a|S_{t}=s)$

同样针对于价值函数v，有：

$v_{\pi }(s)=E_{\pi }(R_{t+1}+\gamma R_{t+2}+\gamma ^{2}R_{t+3}+...|S_{t}=s)$

目标函数

总回报：给定策略𝜋(𝑎|𝑠)，智能体和环境一次交互过程的轨迹𝜏 所收到的累积奖励为总回报（Return）．表达如下：

假设环境中有一个或多个特殊的终止状态（Terminal State），当到达终止状态时，一个智能体和环境的交互过程就结束了
这一轮交互的过程称为一个回合（Episode）或试验（Trial）
如果环境中没有终止状态（比如终身学习的机器人），即𝑇 = ∞，称为持续式任务（Continuing Task），其总回报也可能是无穷大．为了解决这个问题，我们可以引入一个折扣率（衰减率）来降低远期回报的权重．折扣回报（Discounted Return）定义为

其中𝛾 ∈ [0, 1] 是折扣率．当𝛾 接近于0 时，智能体更在意短期回报
而当𝛾 接近于1 时，长期回报变得更重要

目标函数：

因为策略和状态转移都有一定的随机性，所以每次试验得到的轨迹是一个随机序列，其收获的总回报也不一样
强化学习的目标是学习到一个策略 $\pi _{\theta}$ (𝑎|𝑠)来最大化期望回报（Expected Return），即希望智能体执行一系列的动作来获得尽可能多的平均回报

其中𝜃 为策略函数的参数
在持续式任务中，强化学习的优化目标也可以定义为MDP 到达平稳分布时“即时奖励”的期望．

价值函数与贝尔曼方程（Bellman）

为了评估策略𝜋 的期望回报，我们定义两个值函数：状态价值函数和动作价值函数．

状态值函数：

之所以我们来分析这个价值函数，是因为它是强化学习的核心，为什么Agent能够自动学习，自动选择某一个Action，其中一个量化标准就是它：

其中𝑉𝜋(𝑠) 称为状态值函数（State Value Function），表示从状态𝑠 开始，执行策略𝜋 得到的期望总回报

令：

Gt代表Return，代表Agent从某一个状态St开始直到终止状态时所有奖励的有衰减的之和。

则有：

因此：

上述方程称为贝尔曼方程（Bellman Equation），表示当前状态的值函数可以通过下个状态的值函数来计算．

这个式子告诉我们，一个状态的价值由该状态的奖励以及后续状态价值按一定的衰减比例联合组成。

贝尔曼方程因其提出者、美国国家科学院院士、动态规划创始人理查德·贝尔曼（Richard Bellman，1920～1984）而得名，也叫作“动态规划方程”

上述贝尔曼方程用更全面的表达可以如下：

𝑉𝜋(𝑠)

其中𝑎~策略𝜋(𝑎|𝑠)，𝑠′~状态转移概率(𝑠′|𝑠, 𝑎)，即时奖励𝑟(𝑠, 𝑎, 𝑠′)与状态𝑠、行为𝑎、下一个状态𝑠′

因此：

如果给定策略𝜋(𝑎|𝑠)，状态转移概率𝑝(𝑠′|𝑠, 𝑎) 和奖励𝑟(𝑠, 𝑎, 𝑠′)，我们就可以通过迭代的方式来计算状态价值函数𝑉𝜋(𝑠)．由于存在衰减比例，迭代一定步数后，每个状态的价值函数就会固定不变．