Reinforcement Learning 1

终于要开始了，有些激动，同时也有些担忧，激动自然是因为我将要把我所学习的知识记录下来并且有机会分享给其他的人，担忧则是由于我预计这项工作对我来说将会是一项巨大挑战（想想上一篇文章累计写了10多个小时就瑟瑟发抖），所以能否做好，能否平衡好日常工作和写博客（毕竟写博客相对于做研究还是要容易很多的，虽然会花很多时间，但简单的事就会容易让人陷进去，大部分人都有畏难心理，我也不例外）都要打个问号。但是不管怎么样，先迈第一步再说。

首先放上学习资料，我接触强化学习是从KDD Cup的比赛开始，然后入门是学习了周博磊老师《强化学习纲要》这门课（目前仍然处于入门阶段），感兴趣的小伙伴们可以在B站上看到，在后面的文章中还会出现更多的学习资料，但是这门课作为我首个系统性学习强化学习的课程，而且我的写作思路也基本上是按照周老师的课程走的（至少前面几篇文章会是的），所以必须有排面。

什么是强化学习

提到强化学习，就必须要提到Sutton和Barto这两个人，他俩可以说是强化学习的开山鼻祖，写了目前最经典的一本书Reinforcement Learning: An Introduction。我目前还没有读过，但是迟早是要拜读的。

下面就以上面这张图来解释一下，什么是强化学习，强化学习的应用场景可以抽象成Agent和Environment两个部分，我解释一个循环大家应该就明白了，在$t=0$时刻，$R_t=0$，Agent观测到Environment的状态$S_0$，于是决定采取一个动作$A_0$，Environment根据$A_0$会进入到一个新的状态$S_1$，并且给Agent一个反馈，用$R_1$来表示，然后又开始新的交互过程，这个过程中有几点需要注意一下：

1. 交互过程可能有结束的时候也可以一直交互下去
2. Environment的反馈并不一定是即时的，可能会存在滞后

而强化学习的目标就是要让Agent在交互的过程中能够最大化它的累积收益（cumulated rewards）。

Markov Decision Process

这样一个交互过程在强化学习中通常或者可以说基本上就是建模成一个马尔可夫决策过程，要介绍MDP，可以先从马尔可夫过程（MP）开始，再到马尔科夫奖励过程（MRP），最后到MDP。

马尔科夫过程（MP）

也是我们通常说的“马氏链”，它是由状态S和转移概率P构成的。马尔科夫过程需要满足一个性质：给定现在状态，未来的状态与过去是独立的，用公式表示就是：

历史的状态：$h_t={s_1, s_2, \ldots, s_t}$

称状态 $S_t$ 是 $Markovian$ 当且仅当：$p(s_{t+1}| h_t)=p(s_{t+1}| s_t)$

下图就是一个马尔科夫过程的例子：

马尔科夫奖励过程（MRP）

MRP就是MP + reward

定义：

1. S 是（有限）状态的集合（$s \in S$）
2. P 是动态／转移模型，$P(s_{t+1}=s’ | s_t=s)$
3. R 是reward 函数，$R(s_t=s)=\mathbb{E}[r_t | s_t=s]$，注意这里$r_t$是一个随机变量，随机性由环境带来
4. 折现因子 $\gamma \in [0, 1]$，用于对未来收益的折现

接下来就要介绍一些强化学习中很重要的概念了，我就不翻译了，直接用原始的英文以免产生理解偏差。

Horizon

1. 一个episode中最大的time steps数，episode是指一个完整的交互过程
2. Horizon可以是无穷大

Return

从时刻t开始之后的折现rewards的总和

这里的记号不同的资料可能会不一样，比如有些下标会从t开始，大家不必太在意，明白意思就行了。

state value function $V_t(s)$ for a MRP

Expected return from t in state s

这里再提一下为什么要使用折现因子：

1. 可以避免cyclic的MRP产生无穷大的return，因为如果MRP是周期性没有终止状态的，那么可能造成returns趋向无穷大，而折现因子的存在可以近似忽略足够远未来的rewards，从而规避这个问题
2. 由于未来无法被观测到，所以具有一定的不确定性，用折现因子来表示未来无法被完整表示
3. 人们往往是更看重即时收益而忽视未来收益

计算MRP的value function

强化学习第一个非常重要的知识点，敲黑板！！！

$V(s)=R(s)+\gamma \sum_{s’ \in S}P(s’ |s)V(s’)$称为Bellman equation，它想表达的意思就是，当前状态的value function，是等于当前状态的reward加上下一个状态value function的期望，这个公式可以说是强化学习的基石，许多方法的逻辑都是它，后面还会有许多它的变种。

如果状态是有限个，其实我们可以把Bellman equation写成矩阵版本：

$V=R+\gamma PV$，因此可以直接把V解出来：$V=(I-\gamma P)^{-1}R$，不过这只适用于状态比较少的情况，太多的话矩阵求逆计算复杂度太高（$O(N^3)$）。

MDP

终于又回到MDP了，MDP就是MRP + decisions

定义：

1. S 是一个有限状态集合
2. A 是一个有限的动作集合
3. $P^a$ 是动态／转移模型，$P(s_{t+1}=s’ | s_t=s, a_t=t)$
4. R 是reward function，$R(s_t=s, a_t=a)=\mathbb{E}[r_t | s_t=s,a_t=a]$
5. Discount factor $\gamma \in [0,1]$

MDP is a tuple: ($S,A,P,R,\gamma$)，这里有几个点我一开始没有理解清楚，导致后面看一些方法产生了疑惑，这里我说明一下，如果已经弄清楚这部分的小伙伴可以快速扫过：MDP的环境转移模型和reward function都是既依赖于当前的状态也依赖于当前的action的，也就是说 在给定当前状态和动作的情况下，下一时刻的状态是与策略（马上会介绍）无关的，是由环境来决定的。

接下来的内容都会假设状态和动作都是离散且有限的，这是为了说明的方便，但是实际上它们也可以是连续的。

policy in MDP

所谓策略就是在每一个state应该采取什么样的动作，也就是给定一个state，要确定一个actions的分布，policy：$\pi(a | s)=P(a_t=a | s_t=t)$，并且我们假设这个策略是不随时间变化的，这种策略的写法是叫做stochastic policy，还有一种叫做deterministic policy，意思是给定一个状态，我的action是唯一确定的，而不是一个关于actions的分布。（其实我是觉得deterministic的策略在现实中是更常见的，个人看法）

如果给定MDP（$S,A,P,R,\gamma$）和policy $\pi$，其实我们是可以退回MP和MRP的，

下面两张图是MP／MRP和MDP的比较，我就不解释了。

同样的也可以定义MDP的value function：$v^{\pi}(s)=\mathbb{E}_{\pi}[G_t | s_t=s]$,

这里又有几个点我觉得要理解透彻，一个就是这个式子表示的意思是：从当前状态$s_t=s$开始，之后策略$\pi$得到的value function；另一个就是这个$\mathbb{E}_{\pi}$，这个期望不仅包括环境的随机性，还包括策略的随机性（如果是stochastic policy的话）。

MDP还有一个其特有的函数，就是state-action value function（教科书里写的是action value function，动作值函数，我觉得还是写全称更能表示它的意思，当然这不影响理解）:

它表示的是：在状态s采取动作a，之后采取策略$\pi$得到的value function。

它们两者有如下关系：

第一个式子比较好理解，不过第二的式子可能稍微需要理解一下，其实可以从变量的角度来理解，$q(s,a)$的变量是状态s和动作a这两个，reward function和转移概率也是这两个，那么我只需要关注通过这个转移概率转移到的状态$s’$的value function就可以了，如果你要用Q function，就还需要把下一个状态的action $a’$用$\pi$给求期望求掉（这在之后的公式里会展示出来）。

Bellman Expectation Equation

在MDP下，Bellman equation就换了一种称呼（虽然我觉得之前也可以叫expectation，而且跟MRP相比就是多加了一个给定的policy $\pi$），并且多了一个公式：

把这两个公式的期望写开，或者把上面$v(s)$和$q(s,a)$的关系相互带入，就得到了$v(s)$和$q(s,a)$各自的当前时刻和下一时刻值的关系：

这两个式子一定要理解透彻，cornerstone of RL ！！！

OpenAI Gym Library

最后介绍一个强化学习必用的library，这是OpenAI公司开发的专门针对强化学习的库，里面集成了非常多的环境，比如Atari游戏、Box2d、classic control等 ，能让学习者能很方便的进行RL算法的训练。 官方网址

结下来就以一个简单的游戏CartPole-v0来说明一下这个库的基本使用方法。 这个游戏的目的就是让杆子（pole）能立在方块（cart）上尽可能维持它不倒，支点就是杆子与方块的连接处。你可以施加的动作就是向左或者向右移动这个cart。它的observation是一个4维的向量：cart的位置、速度、杆的角度和杆顶点的速度。每一步的reward都是1，因为它的目的就是尽可能的活更长的时间。游戏结束的条件有3个：杆的角度超过12度、cart的位置超出边界、游戏已经进行了200步（也就是说这个游戏的最大return就是200（不考虑折现））。想看它的源码可以查看 https://github.com/openai/gym/blob/master/gym/envs/classic_control/cartpole.py

import gym
env = gym.make("CartPole-v0")
observation = env.reset()
for _ in range(1000):
  env.render() # display the rendered scene
  action = env.action_space.sample() # your agent here (this takes random actions)
  observation, reward, done, info = env.step(action)

  if done:
    observation = env.reset()
env.close()

这是一个标准的与环境交互的过程，导入gym过后，首先创建环境，使用gym.make(name)，然后用env.reset()来初始化环境（一定要先初始化再交互，每玩完一次游戏要初始化），会生成一个4维的初始状态变量，然后就可以开始进行交互了，接下来的循环展示的是玩游戏的过程，首先env.render()是用来把上一步的状态给图形化显示出来，你可以每交互一次就显示一次，这样就看起来像一个动画了（当然你不显示也是完全没有问题的，而且如果是在训练算法时一般都不显示的，因为会费时间），然后你需要给定一个动作，这个动作可以是你的算法基于当前观测到的observation作出的，也可以像代码中一样随机sample一个，接下来就用env.step(action)来交互，它会输出4个东西，首先是一下个状态，然后是reward，done表示这个游戏是否结束（一开始一直都是False，当达到终止条件时就变成True）和一些其他的相关信息（这个不是很重要，一般也用不到），每交互完一次后判断，是不是当前episode已经结束，是的话就初始化环境，开始下一轮游戏，全部结束之后env.close()关闭环境。

好了，第一篇文章就先写到这，下一篇文章就介绍MDP中需要做的两类问题：prediction和control。

• Previous
  我做KDD比赛时学习KM算法的心路历程
• Next
  Reinforcement Learning 2