0%

强化学习笔记

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$有关,那么:

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

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

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

值函数(value function)也叫做折算累计回报(discounted cumulateive reward),如果考虑了action也叫做Q-function:

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

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

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

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

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

带入也就是:

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

这个也就是知道在$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)$,但是实际上这两个参数不能得到。
实际上我们使用:

然后如果出现分母为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}$的概率分布。

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

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

当然如果是非线性的,那么就把$s_t$和$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’)]$
注意对比前面的值迭代算法。

这里$\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) $。这样就是求解:

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

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

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

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

3.1 蒙特卡洛方法

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

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

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

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

这里还分同策略(on-policy)和异策略(off-policy)。

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

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

3.2 时间差分(TD)

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

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

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

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

$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目标,当然我们可以考虑更多步来进行:

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

4. Deep Learning with RL

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

4.1 Value-based Deep RL

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

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

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

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

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

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

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

这里把$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(s, \mu)

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