强化学习入门总结

目录

一、强化学习概述

1.强化学习简介

（1）

强化学习是机器学习

中的一个领域

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

。

（2）强化学习最早可以追溯到巴甫洛

夫的条件反射实验，它从动

物行为研究和优化控制两个领域独立发展

，最终经

Bellman

之手将其抽象为

马尔可夫决策过程

(Markov Decision Process

，

MDP

)

2.发展历程：

1956

年

Bellman

提出了动态规划方法。

1977

年

Werbos

提出只适应动态规划算法。

1988

年

sutton

提出时间差分算法。

1992

年

Watkins

提出

Q-learning

算法。

1994

年

rummery

提出

Saras

算法。

1996

年

Bersekas

提出解决随机过程中优化控制的神经动态规划方法。

2006

年

Kocsis

提出了置信上限树算法。

2009

年

kewis

提出反馈控制只适应动态规划算法。

2014

年

silver

提出确定性策略梯度（

Policy

Gradients

）算法。

2015

年

Google-

deepmind

提出

Deep-Q-Network

算法

。

可见，强化学习已经发展了几十年，并不是一门新的技术。在2016年，AlphaGo击败李世石之后，融合了深度学习的强化学习技术大放异彩，成为这两年最火的技术之一。总结来说，强化学习就是一个古老而又时尚的技术。

3.MDP（马儿可夫决策过程）

S:

表示状态集

(states)

，有

s∈S

，

si

表示第

i

步的状态。

A:

表示一组动作

(actions)

，有

a∈A

，

ai

表示第

i

步的动作。

?

sa

:

表示状态转移概率。?

s?

表示的是在当前

s ∈ S

状态下，经过

a ∈ A

作用后，会转移到的其他状态的概率分布情况。比如，在状态

s

下执行动作

a

，转移到

s'

的概率可以表示为

p(s'|

s,a

)

。

R: S×A⟼ℝ

，

R

是回报函数

(reward function)

。有些回报函数状态

S

的函数，可以简化为

R: S⟼ℝ

。如果一组

(

s,a

)

转移到了下个状态

s'

，那么回报函数可记为

r(

s’|s

, a)

。如果

(

s,a

)

对应的下个状态

s'

是唯一的，那么回报函数也可以记为

r(

s,a

)

。

γ

:折现因子

4.why RL？

强化学习所解决的问题的特点：

• 智能体和环境之间不断进行交互
• 搜索和试错
• 延迟奖励（当前所做的动作可能很多步之后才会产生相应的结果）

目标：

• 获取更多的累积奖励
• 获得更可靠的估计

强化学习

(Reinforcement Learning)

是一个机器学习大家族中的分支

,

由于近些年来的技术突破

,

和深度学习

(Deep Learning)

的整合

,

使得强化学习有了进一步的运用

。

比如让计算机学着玩游戏

,

AlphaGo

挑战世界围棋高手

,

都是强化学习在行的事

。

强化学习也是让你的程序从对当前环境完全陌生

,

成长为一个在环境中游刃有余的高手。

5.总结：

深度强化学习

全称是

Deep Reinforcement Learning

（

DRL

），其所带来的推理能力 是智能的一个关键特征衡量，真正的让机器有了自我学习、自我思考的能力。

深度强化学习

(Deep Reinforcement

Learning

，

DRL)

本质上属于采用神经网络作为值函数估计器的一类方法，其主要优势在于它能够利用深度神经网络对状态特征进行自动抽取，避免了人工 定义状态特征带来的不准确性，使得

Agent

能够在更原始的状态上进行学习。

二、强化学习求解方法

1.动态规划方法

基石：贝尔曼方程

（1）贝尔曼方程：

贝尔曼最优方程：

如何求解贝尔曼方程呢？

本质上就是个线性规划问题，多个方程，多个未知数，进行求解，如下，假设每一步的即使奖励是-0.2，有三个未知状态V(0,1),V(1,1),V(1,0),损失因子是1，则在如下的策略下，得到的贝尔曼方程如下：

但是当未知变量不断增大，线性规划则很难求解，这时需要使用动态规划进行不断迭代，让其状态值收敛。

（2）值迭代

In Value Iteration, you start with a

randon

value function and then find a new (improved) value function in a iterative process, until reaching the optimal value function. Notice that you can derive easily the optimal policy from the optimal value function. This process is based on the Optimality Bellman operator.

（3）策略迭代

In Policy Iteration algorithms, you start with a random policy, then find the value function of that policy (policy evaluation step), then find an new (improved) policy based on the previous value function, and so on. In this process, each policy is guaranteed to be a strict improvement over the previous one (unless it is already optimal). Given a policy, its value function can be obtained using the Bellman operator.

（4）算法详细对比：

• 根据策略迭代算法，每一次迭代都要进行策略评估和策略提升，直到二者都收敛。可我们的目标是选出最优的策略，那么有没有可能在策略评估值没有收敛的情况下，最优策略已经收敛了呢？答案是有这个可能
• 策略迭代的收敛速度更快一些，在状态空间较小时，最好选用策略迭代方法。当状态空间较大时，值迭代的计算量更小一些

（5）GridWorld举例（分别用策略迭代和值迭代进行求解）

策略迭代过程：

值迭代过程：

2.蒙特卡洛方法

上面的动态规划方法，是一种较为理想的状态，即所有的参数都提前知道，比如状态转移概率，及奖励等等。然而显示情况是未知的，这时候有一种手段是采用蒙特卡洛采样，基于大数定律，基于统计计算出转移概率值；比如当你抛硬币的次数足够多，那么正面和反面的概率将会越来越接近真实情况。

3.时间差分方法

基于动态规划和蒙特卡洛

三、强化学习算法分类

1.分类一：

基于理不理解所处环境来进行分类：

Model-free:环境给了我们什么就是什么

.

我们就把这种方法叫做

model-free,

这里的

model

就是用模型来表示环境

M

odel

-based:

那理解了环境也就是学会了用一个模型来代表环境

,

所以这种就是

model-based

方法

2.分类二：

一类是直接输出各个动作概率，另一个是输出每个动作的价值；前者适用于连续动作情况，后者无法表示连续动作的价值。

3.分类三：

4.分类四：

判断

on-policy

和

off-

policy

的

关键

在于

，你所估计的

policy或者value-

function

和你生成样本时所采用的

policy

是不是一样

。

如果一样

，那就是

on-policy

的，否则是

off-policy

的。

总结各常用算法的分类：

四、代表性算法

1.Q-learning

（1）四个基本组成成分：

• Q表：Q(s,a),状态s下执行动作a的累积价值
• 定义动作：选择动作
• 环境反馈： 做出行为后，环境的反馈
• 环境更新

（2）算法公式：

（3）算法决策：

（4）算法更新：

（5）代码实现框架：

2.Sarsa:

与

Q-learning

基本类似，唯一的区别是更新方式不一样

（1）算法公式：

（2）与Q-learning的区别：Sarsa是on-policy的，Q-learning是off-policy的

（3）更新过程：

前者是Sarsa，后者是Q-learning

（4）代码中展现不同：

Sarsa:

Q-learning:

（5）代码实现框架：

3.大名鼎鼎的DQN

Deepmind就是因为DQN这篇论文，被谷歌收购

（1）由来：

• DQN

  （

  Deep

  Q

  Network

  ）是一种融合了神经网络和

  Q

  learning

  的方法

  .

• 有些问题太复杂，

  Q

  表无法存储，即使可以存储，搜索也很麻烦。故而，将

  Q

  表用神经网络进行替代。

（2）增加了两个新特性：

Experience

replay

：每次

DQN

更新的时候，随机抽取一些之前的经历进行学习。随机抽取这种打乱了经历之间的相关性，使得神经网络更新更有效率。

Fixed Q-

targets

：使用两个结构相同但参数不同的神经网络，预测

Q

估计的神经网络具备最新的参数，而预测Q

现实的神经网络使用的参数则是很久以前的。

（3）算法公式：

paper地址：

（4）DQN代码实现框架：

可以看到基本上Q-learning一模一样，只是有一处不一样，就是多了存储记忆，并且批量进行学习。

4.Policy Gradients算法

（1）由来：

强化学习是一个通过奖惩来学习正确行为的机制

.

家族中有很多种不一样的成员

,

有学习奖惩值

,

根据自己认为的高价值选行为

,

比如

Q learning, Deep Q Network,

也有不通过分析奖励值

,

直接输出行为的方法

,

这就是今天要说的

Policy Gradients

了

.

甚至我们可以为

Policy Gradients

加上一个神经网络来输出预测的动作

.

对比起以值为基础的方法

, Policy Gradients

直接输出动作的最大好处就是

,

它能在一个连续区间内挑选动作

,

而基于值的

,

比如

Q-learning,

它如果在无穷多的动作中计算价值

,

从而选择行为

,

这

,

它可吃不消

.

（2）区别：

Q-learning

、

DQN

：学习奖惩值

,

根据自己认为

的高价值选行为。

Policy

Gradients

：不通过分析奖励值

,

直接输出行为的

方法

。

Policy Gradients

直接输出动作的最大好处就是

,

它能在一个连续区间内挑选动作

,

而基于值的

,

比如

Q-learning,

它如果在无穷多的动作中计算价值

,

从而选择行为

,

这

,

它可吃不消

.

（3）更新：

（4）REINFORCE算法公式：

推到步骤的博客：

5.Actor-critic

（1）由来：

结合了

Policy Gradient (Actor)

和

Function Approximation (Critic)

的方法

. Actor

基于概率选行为

, Critic

基于

Actor

的行为评判行为的得分

, Actor

根据

Critic

的评分修改选行为的概率

.

（2）特点：

Policy

Gradients

Q

-learning

：既可以在连续动作中取合适的动作，又可以进行单步更新。

（3）与Policy Gradients的区别：

Policy

gradient

是回合后进行奖惩计算，前期没有值函数，需要后向推算；

Actor

critic

多了一个

critic

方法，可以用来每一步进行一个好坏判断；

（4）更新

Actor Critic

方法的劣势

:

取决于

Critic

的价值

判断

,

但是

Critic

难收敛

,

再加上

Actor

的更新

,

就更难收敛

.

为了解决收敛问题

, Google

Deepmind

提出

了

Actor

Critic

升级版

Deep Deterministic Policy Gradient.

后者融合了

DQN

的优势

,

解决了收敛难的问题

.

（5）代码实现框架：

五、强化学习应用：

（1）各领域应用：

（2）对话

TaskBot

阿里小蜜的任务型问答技术：

State.

我们主要考虑了

intent network

出来的

user question

embeddings

，当前抽 取的

slot

状态，和历史的

slot

信息，之后接入一个全连接的神经网络，最后连

softmax

到各个

actions

。

Action.

在订机票场景，

action

空间是离散的，主要包括对各个

slot

的反问和

Order(

下单

):

反问时间，反问出发地，反问目的地，和

Order

。这里的

action

空间可以扩展，加入一些新的信息比方询问说多少个人同行，用户偏好等。

对比了不同的

DRL

配置下的效果。在测试的时候发现，如果用户退出会话

(Quit)

给一个比较大的惩罚

-1

，模型很难学好。这个主要原因 是，用户退出的原因比较多样化，有些不是因为系统回复的不好而退出的，如 果这个时候给比较大的惩罚，会对正确的

actions

有影响。

（3）淘宝电商搜索：

用户搜索商品是一个连续的过程。这一连续过程的不同阶段之间不是孤立的，而是有着紧密的联系。换句话说，用户最终选择购买 或不够买商品，不是由某一次排序所决定，而是一连串搜索排序的结果。

搜索引擎（智能体）、用户（环境）、用户行为（

reward

）

当状态空间

S

和动作空间

A

确定好之后

(

动作空间即

Agent

能够选择排序策略的 空间

)

，状态转移函数

T

也随即确定

;

另一个重要的步骤是把我们 要达到的目标

(

如

:

提高点击率、提高

GMV

等

)

转化为具体的奖赏函数

R

（4）FlappyBird:

（5）组合优化问题（TSP）：

六、总结：

1.如何设计算法：

Step

1

：将实际问题建模成马尔可夫决策过程，抽象出五元组，

其中

reward

与实际目标相关联

Step

2

：根据动作是否连续选择对应的算法

动作离散：

DQN

动作连续：

Policy

Gradients

，

Actor-

Critic

，

DDPG

Step

3

：根据算法写代码

参考资料：

1

、

莫烦强化学习系列教程

2

、

DQN

系列教程

3

、

Policy

gradients

推导：

4

、

2017

年

ICLR

论文：

NEURAL

COMBINATORIAL OPTIMIZATION WITH REINFORCEMENT LEARNING

5

、

sutton

《

Reinforcement

Learning:An

I

ntroduction

》

：

6

、

Exercises and Solutions to accompany

Sutton‘s

Book and David

Silver’s course

：

7

、

Andrew

Ng

机器学习视频

16-20

章

8

、

David Silver

视频

9

、

Reinforcement

Learning

Beyond

Games:To

M

ake

a

Difference

in

Alibaba