强化学习笔记

1. 介绍

强化学习强调如何基于环境而行动，以取得最大化的预期利益。其灵感来源于心理学中的行为主义理论，即有机体如何在环境给予的奖励或惩罚的刺激下，逐步形成对刺激的预期，产生能获得最大利益的习惯性行为。在运筹学和控制理论下称之为“近似动态规划”。

在机器学习中，环境通常被规范为马尔科夫决策过程（MDP）。传统技术（动态规划）不需要MDP知识，而且不乏找到确切方法。强化学习和监督学习区别又有，它不需要出现正确的输入/输出对。也不需要精确校正次优化的行为。强化学习更加专注于在线规划，需要在探索（在未知的领域）和遵从（现有知识）之间找到平衡。

模型包括：

1. 环境状态的集合 $S$;
2. 动作的集合 $A$;
3. 在状态之间转换的规则；
4. 规定转换后“即时奖励”的规则；
5. 描述主体能够观察到什么的规则。

每一个时间$t$，主体接收到一个观测$o_t$，通常其中包含奖励$r_t$。然后，它从允许的集合中选择一个动作 $a_{t} $，然后送出到环境中去。环境则变化到一个新的状态 $s_{t+1}$，然后决定了和这个变化 $ (s_t,a_t,s_{t+1})$相关联的奖励 $ r_{t+1}$。强化学习主体的目标，是得到尽可能多的奖励。主体选择的动作是其历史的函数，它也可以选择随机的动作。

强化学习有效在两个方面：使用样本优化行为，以及使用函数来逼近复杂的环境。

1.1 强化学习和监督学习区别

1. 强化学习是试错学习，因为没有直接信息，所以是与环境不断进行交互，来获取环境的最佳模型。
2. 延迟回报强化学习是在事后反馈。也就是获得正反馈或者负反馈之后才能修改参数。

1.2 仿真环境

OpenAI Gym。

2. 马尔科夫决策过程 MDP

2.1 推导过程

马尔科夫决策由五元组组成$(S,A,{P_{sa}},\gamma, R)$。

• $S$表示状态集。
• $A$表示一组动作。
• $P_{sa}$是状态转移概率。表示当前状态$s\in S$状态下，经过$a \in A$作用下，会转移到其他状态的概率分布情况。这里主要讨论的是stochastic policy，还有一个叫做Deterministic Policy的也就是$a = \pi(s)$
• $\gamma \in [0,1)$是阻尼系数(discount factor)。
• $R: S \times A \to R$，$R$是回报函数(reward function)，回报函数经常写作只和$S$的函数。

整个过程相当于HMM：

$$s\_0, a\_0 \to s\_1, a\_1 \to \cdots$$

回报函数之和就是：

$$R(s\_0, a\_0) + \gamma R(s\_1, a\_1) + \gamma^2 R(s\_2, a\_2) + \cdots$$

如果回报函数之和$S$有关，那么：

$$R(s\_0) + \gamma R(s\_1) + \gamma^2 R(s\_2) + \cdots$$

这样我们希望全部的回报加权和期望最大：

$$E\left[ R(s\_0) + \gamma R(s\_1) + \gamma^2 R(s\_2) + \cdots \right]$$

这样可以发现$t$时刻的回报函数变成$\gamma^t R(s_t)$，意思也就是要将回报函数大的放到决策的前面。也就是距离越近，状态对方案的影响越大。

一个策略（policy）就是一个动作选择过程。也就是一个状态到动作的映射函数$\pi: S \to A$。我们求出$\pi$也就是知道每步执行的动作。

值函数（value function）也叫做折算累计回报（discounted cumulateive reward），如果考虑了action也叫做Q-function：

$$V^\pi(s) = E\left[ R(s\_0) + \gamma R(s\_1) + \gamma^2 R(s\_2) + \cdots \vert s\_0 = s,\pi \right]$$

在其他讲解中都是把$V(s)$代替成$Q(s,a)$的，然后相应的学习方法也就称之为Q-learning。

当前状态和下一个状态$s’$可以进行递推：

$$V^\pi(s) = R(s\_0) + \gamma (E\left[ R(s\_1) + \gamma R(s\_2) + \gamma^2 R(s\_3) + \cdots \vert s\_0 = s,\pi \right]) = R(s\_0) + \gamma V^\pi(s')$$

当然我们给定了策略$\pi$，尽管在$s$状态肯定选择$a$动作。但是$s’$却不是唯一的。

$$V^\pi(s) = R(s) + \gamma \sum\_{s' \in S} P\_{s\pi(s)}(s') V^\pi(s')$$

也就是$R(s)$是当前状态立即回报。第二项$E_{s’ \sim P_{s\pi(s)}}[V^\pi(s’)]$时下一个状态的期望值，$s’$也符合$P_{s\pi(s)}$分布。

我们要求的也就是在目前状态$s$下，最优行动策略$\pi$，最优的$V^{*}$也就是：

$$V^{\*}(s) = \max\_\pi V^\pi(s)$$

带入也就是：

$$V^{\*}(s) = R(s) + \max\_{a \in A} \gamma \sum\_{s' \in S} P\_{sa}(s') V^{\*}(s')$$

$R(s)$是已知的，当然我们要求的是最优策略$\pi^{*}$：

$$\pi^{\*}(s) = \arg \max\_{a \in A} \sum\_{s' \in S} P\_{sa}(s') V^{\*}(s')$$

这个也就是知道在$s$的动作$a$。

2.2 值迭代和策略迭代法

这里只考虑MDP是有限状态、有限动作的情况。
值迭代法（Value Iteration）

1. 初始化$V(s)=0$
2. 重复直到收敛，对于每个状态s，更新$V(s) = R(s) + \max_{a \in A} \gamma \sum_{s’ \in S} P_{sa}(s’) V(s’)$

同步迭代法：首先初始化完了，然后对所有的$s$都计算新的$V(s) = R(s) + 0 = R(s)$。在计算每个状态都会得到一个新的$V(s)$但是不更新。待所有的$s$的新值都计算完毕，再统一更新。

异步迭代法：每次得到新的$V(s)$就立即更新。

策略迭代法：

1. 随机指定一个$\pi$
2. 重复直到收敛，
   2.a $V=V^\pi$。
   2.b 对于每个状态s，更新$\pi(s) = \arg \max_{a \in A} \sum_{s’ \in S} P_{sa}(s’) V(s’)$

首先通过a求得所有状态的$V^\pi(s)$，然后通过b求得当前状态下的最优值。

两种方法，在MDP比较小的情况下，策略容易收敛。比较大则相反。实际上Value Iteration根本无法使用，因为非常有限的状态/动作，不能产生未观测的状态。

2.3 MDP 中的参数估计

如上是知道转移概率矩阵$P$和回报函数$R(s)$，但是实际上这两个参数不能得到。
实际上我们使用：

$$P\_{sa}(s') = \frac{\text{number of times we took action a in state s and got to s'}}{\text{number of times we took action a in state s}}$$

然后如果出现分母为0，也就是没有出现过在$s$执行$a$，那么直接设置为$P_{sa}(s’)=1/\vert S\vert$。同样在线更新也是可以做的，也就是更改那个count值。

当然也可以求回报函数，认为$R(s)$为在$s$状态下已经观测得到的回报均值。

如果把参数估计假如之前的值迭代或者策略迭代算法中，也就是在第二个步骤同时算出转移概率和回报函数。

2.4 连续状态MDP

也就是说每个状态之间是有无穷可能的位置的。比如汽车在行驶的状态$(x,y,\theta, x’,y’,\theta’)$。

一种解决思路就是离散化(Discretization)。也就是把状态在$a_i\le x \le a_{i+1}$，这个设置为状态$s_i$，然后依次类推。这样一个连续状态就变成了离散状态。

问题就是这只是一个naive的表示，根本无法代表$V$的真实情况。另外会出现维度诅咒（Curse of Dimension），如果状态的维度很大$S \in R^n$，那么如果每个状态分成$k$份，那么最终状态数目就变成了$k^n$。

2.5 Value Function Approximation

当然除了离散化还有另外一种方法解决连续状态的MDP。

我们假设一个模型：

当输入$s_t$和$a_t$之后，进入我们的模型，得到一个$s_{t+1}$并且这个是服从$P_{sa}$的概率分布。

最简单的就是训练一个线性模型：

$$s\_{t+1} = A s\_t + B a\_t$$

假设我们进行$m$次路线(trails)，那么我们就是想最小化noise，$\epsilon \sim N(0,\Sigma) $。

$$\arg \min\_{A,B} \sum\_{i=1}^{m} \sum\_{t=0}^{T-1} \Vert s\_{t+1}^{(i)} - (A s\_t^{(i)} + B a\_t^{(i)}) \Vert^2$$

当然如果是非线性的，那么就把$s_t$和$a_t$替换成：

$$s\_{t+1} = A \phi\_s( s\_t) + B \phi\_a(a\_t)$$

2.6 连续状态求出Value(Q)函数

Fitted Value(Q) iteration算法。

原本的值迭代算法（连续状态）如下：
$V(s) = R(s) + \max_{a \in A} \gamma E_{s’ \sim P_{sa}}[V(s’)]$
注意对比前面的值迭代算法。

$$V(s) = \theta^T \phi(s)$$

这里$\phi$是一个appropriate feature mapping对这些状态而言。在每一个时间t的状态s下。我们都进行了m次sample得到m个相应的状态。也就是下面算法的i过程$i=1,\cdots,m$，会算出一个量$y^{(i)}$，这个值用来估计$R(s) + \max_{a \in A} \gamma E_{s’ \sim P_{sa}}[V(s’)]$。然后我们再用监督学习来得到一个$V(s)$是最接近$y^{(i)}$的。算法过程如下：

这里$(x,y)$分别是$s$和$y$。在sample $s_1’,\cdots, s_k’ \sim P_{sa}$的过程中，这里是为了逼近那个期望。

实际操作中也有按照上一节逼近的方法$s_{t+1} = f(s_t, a_t) + \epsilon_t$，这里可以设置$f(s_t, a_t)=As_t + B a_t$，$\epsilon \sim N(0,\Sigma) $。这样就是求解：

$$\arg \max\_a V(f(s,a))$$

当然也可以直接sample一次，然后假设noise也非常小。

这里Deep Q-learning方法感觉是把supervisor learning那块改成了CNN。

3. 无模型的强化学习方法

MDP过程是可以采用无模型的强化学习方法的，这里包括了蒙特卡洛方法和时间差分方法（TD方法）。上面第二节都是讲的基于模型的动态规划方法。

3.1 蒙特卡洛方法

我们先从蒙特卡洛方法讲起。与前面方法相比，主要不同在值函数的估计上面。首先在动态规划方法的值函数这样计算：

$$V(s) = R(s) + \gamma \sum\_{a \in A} \pi(a \vert s) \sum\_{s'} P\_{sa}V(s')$$

但是再无模型强化学习中，模型$P_{sa}$是未知的。再次给出以下第二节的$V$和$Q$的表达式：

$$V\_\pi(s) = E\_{\pi}[G\_t \vert S\_t = s] = E\_\pi \left[ \sum\_{k=0}^\infty \gamma^k R\_{t+k+1} \vert S\_t = s \right]$$ $$Q\_\pi(s,a) = E\_\pi \left[\sum\_{k=0}^\infty \gamma^k R\_{t+k+1} \vert S\_t = s, A\_t = a \right]$$

状态值函数和行为值函数，计算的其实是返回值的期望。在计算值函数的时候，蒙特卡洛方法是利用经验平均代替随机变量的期望。也就是2.3节的参数估计方法。

当然还有比较常用的叫做温和策略。也就是$\pi(a \vert s) > 0$，也就是采用动作集合中每个动作的概率都大于0。$\epsilon-soft$ 策略：

$$\begin{aligned} \pi\left(a|s\right)\gets\left\\{ \begin{array}{cc} 1-\varepsilon +\frac{\varepsilon}{\left| A\left(s\right)\right|} & if\ a=arg\max\_aQ\left(s,a\right) \\\\ \frac{\varepsilon}{\left| A\left(s\right)\right|} & if\ a\ne arg\max\_aQ\left(s,a\right) \\\\ \end{array}\right. \end{aligned}$$

这里还分同策略（on-policy）和异策略（off-policy）。

同策略：行动策略和评估及改善的策略是同一个策略。比如改进的时候都是用$\epsilon-soft$ 策略

异策略：假设使用$\pi$表示评估和改进的策略，然后$\mu$表示产生样本数据的策略。这里使用重要性采样方法。

3.2 时间差分（TD）

进行稍微修改之前的值函数：

$$V(s) = E[R(s') + \gamma V(s')] = \sum\_{a}\pi(a \vert s) \sum\_{s'}P\_{sa}[R(s') + \gamma V(s')]$$

这里使用bootstapping，也就是自举，指当前值函数计算用到了后继状态的值函数。这里的$P_{sa} = p(s’, R(s’) \vert s, a)$。

蒙特卡洛需要做完一次实验，得到终止状态，然后才结束。

$$V(s\_t) \leftarrow V(s\_t) + \alpha (G\_t - V(s\_t))$$

时间差分也就是借鉴了两者。

$$V(s\_t) \leftarrow V(s\_t) + \alpha (R(s\_{t+1}) + \gamma V(s\_{t+1}) - V(s\_t))$$

$R(s_{t+1}) + \gamma V(s_{t+1})$ 位TD目标，与$G_t$对应。

从统计学的角度来看，蒙特卡罗方法（MC方法）和时间差分方法（TD方法）都是利用样本去估计值函数的方法。

蒙特卡洛是无偏估计，因为$G_t$就是值函数。时间差分法TD目标是$R(s_{t+1}) + \gamma V(s_{t+1})$，这里$V(s_{t+1})$采用的是估计，所以是有偏估计，但是因为只用了一部随机状态和动作。所以随机性要比蒙特卡洛要小，方差也小。

Q-learning也就是异策略时间差分方法。即行动策略采用 $\varepsilon $ 贪婪策略，而目标策略采用贪婪策略。

当时我们使用下一步的状态来表示TD目标，当然我们可以考虑更多步来进行：

$$G\_{t}^{(n)} = R(s\_{t+1}) + \gamma R(s\_{t+2}) + \cdots + \gamma^{n-1} R(s\_{t+n}) + \gamma^n V(s\_{t+n})$$

也就是说有n中估计方法，考虑使用多步的情况，融合就是加权融合，诚意加权因子$(1-\lambda)\lambda^{n-1}$：

$$\begin{aligned} G\_{t}^{\lambda} &= (1 - \lambda) G\_t^{(1)} + \cdots + (1-\lambda) \lambda^{n-1} G\_t^{(n)} \\\\ &\thickapprox [(1-\lambda) + (1-\lambda)\lambda +\cdots + (1-\lambda) \lambda^{n-1}] V(s\_t) \\\\ &= V(s\_t) \end{aligned}$$

4. Deep Learning with RL

主要参考。上面第二节主要是参考Andrew Ng的课程lecture。

4.1 Value-based Deep RL

DQN：增加一个$w$来表示。主要根据3.2的Q-learning改过来，利用深度卷积神经网络逼近值函数，利用经验回放对强化学习的过程进行训练，独立设置目标网络来处理时间差分算法的TD偏差。

$$Q(s,a,w) \thickapprox Q^{\*}(s,a)$$

第二节的Value Iteration过程$Q(s, a) = R(s) + \gamma\max_{a’} Q(s’,a’)^{*}$。
squared error就是：

$$L = E[(R(s) + \gamma\max\_{a'} Q(s',a',w) - Q(s,a,w))^2]$$

当然可以进行SGD求值。这里的值函数逼近和2.6里面的线性逼近是类似的。都是参数逼近。

这里是作为一个更新过程来的。

$$w\_{t+1} = w\_{t} + \alpha [R(s) + \gamma \max\_{a'} Q(s',a';w) - Q(s,a;w)] \nabla Q(s,a;w)$$

但是使用neural networks会无法converges.因为：

1. samples 之间是correlated
2. non-stationary targets

Experience Replay：为了消除correlations，可以从agent本身的experience获得数据，然后再进行sample，以及更新。因为神经网络训练时，假设数据是独立同分布的，但是强化学习得到的数据之间是相互关联的。然后把所有的数据放到数据库里，然后进行均匀随机采样抽取数据。

$$L = (R(s) + \gamma\max\_{a'} Q(s',a',w^-) - Q(s,a,w))^2$$

这里把$w^-$设置为固定的。在一个固定步数后进行更新而动作值函数逼近网络每一步都更新。避免non-stationarity。

例子：DQN in Atari
Input的状态就是最后4个frame的像素矩阵4x84x84
Output就是$Q(s,a)$表示18个joystick的位置
Rewar就是那个step的分数变化。

可以看：Gorila (General Reinforcement Learning Architecture)

3.2 Policy-based Deep RL

又称之为Deep Deterministic Policy Gradient。

Actor-Critic Algorithm（演员评判家），合并了以值为基础（Q-learning）和策略概率为基础的（Policy）两类全强化学习算法。Actor表示Policy Gradients能够在连续动作中选取合适的动作，而Q-learning无法做这件事。而Policy Gradients又无法满足单步更新。

加入一个新的weight $\mu$：

$$a = \pi(a \vert s, \mu) $$or$$

a = \pi(s, \mu)

$$仍然定义目标函数为total dicounted reward：$$

L(\mu) = E [r_1 + \gamma r_2 + \cdots \vert \pi(\cdot, \mu)]

$$

参考

课程

UCL Course on RL
Reinforcement Learning:
An Introduction

开源项目

DQN Flappy Bird
Deep Q Learning with Keras and Gym

Reference

1.强化学习-维基百科

2.OpenAI Gym

3.增强学习（Reinforcement Learning and Control）

4.CS229 Lecture Notes

5.DL-RL-Tutorial

6.DQN paper

7.DQN source code

8.dissecting-reinforcement-learning

9.pytorch-dqn-github

10.RL大讲堂-知乎专栏

11.RL大讲堂-DQN-知乎专栏

---

因为我们是朋友，所以你可以使用我的文字，但请注明出处：http://alwa.info