【强基固本】Reinforcement learning入门：从马尔可夫，动态规划到强化学习

“强基固本，行稳致远”，科学研究离不开理论基础，人工智能学科更是需要数学、物理、神经科学等基础学科提供有力支撑，为了紧扣时代脉搏，我们推出“强基固本”专栏，讲解AI领域的基础知识，为你的科研学习提供助力，夯实理论基础，提升原始创新能力，敬请关注。

作者：知乎—弃之

地址：https://www.zhihu.com/people/qi-zhi-24-55-95

本文从RL的基本知识讲起，参考了open ai的RL introduction；然后讲了一部分RL的渊源，如早期MDP，POMDP，以及用dynamic programming的方法进行解的方案，参考了UCL的RL课程。后续还会继续跟踪这门课程，讲RL的一些方法。

先讲讲RL的基本概念。

01

Key concepts in RL[1]

1.1 states and observations

states：complete description of the state of the world

observation：partial description of a state, which may omit information.

在RL中，action应该是取决与state的，但是由于agent不能完全观察到state，所以实际上是取决与observation  的

1.2 action spaces

取决于具体的环境，有discrete action spaces，也有continuous action spaces

1.3 policies

a rule used by an agent to decide what actions to take。policy是agent的大脑，agent可以直接用policy来替代。同时我们的policy是带参数可训练的，一般用  来表示

可以是derministic的，写作

也可以是stocastic的，写作

从这两种policy的命名上就能大概猜出他们的不同，一个是决定性的，只与之前的状态有关；另一个则是带有随机的，有一个sample的步骤。deterministic往往要求有full observation。

1.3.1 derministic policy

policy的设计就可以直接用神经网络来做就行，输入一个observation  ，输出一个policy。如

pi_net = nn.Sequential(
              nn.Linear(obs_dim, 64),
              nn.Tanh(),
              nn.Linear(64, 64),
              nn.Tanh(),
              nn.Linear(64, act_dim)
            )

1.3.2 Stocastic policy

关键在于两个步骤

1.从policy中sample actions

2.计算action的对数似然 

分类上可以分为

• Categorical policies：discrete action spaces

sample的过程直接利用tf.multinomial函数就可以（多项式概率），按照每个action的概率进行sample。求似然的过程可以直接利用一个classifier神经网络。

• diagonal Gaussian policies ：continuous action spaces.

多元高斯分布的特殊形式，即协方差矩阵只有对角线有值（意味着相互独立？）。多元高斯分布的核心在哪儿呢？自然是均值和方差，所以接下来讨论均值和方差如何得到。

1. 我们需要一个神经网络先将observation映射到一个mean action 

2. 对于协方差矩阵  ，一个自然的想法也是利用神经网络来映射一个，当然着神经网络可以和上述均值那个有一定layer的重合。

3. 有了均值和方差，接下来就是如何sample出action了。我们可以先随机冲球形高斯分布中sample出一个noise  ，然后action的sample就直接利用均值方差和随机向量  得到

然后对sample出的action算他们的对数似然

1.4.trajectories

用来代替states和actions的sequence

其中  是sample自初始状态分布。状态在下一个时刻有多种决定方法，如上述讲的policy，可以是deterministic的，也可以是stocastic的。

1.5 Reward & return

reward的完整形式可以表述为

但是在实际运用中，我们会考虑更加简单更加独立的形式，如只与当前状态  有关，或者只与  有关。一条路径  所带来的cumulative reward可以用  进行表示。计算这条行动路径的reward可以有两种方式，一种就是在固定的window size长度为T下直接求和，

另一种则是算无限长度下的discounted return。

这种衰减是十分有用的，直觉上十分相符，我们更加关注当前信息；同时也容易计算。

1.6 the RL optimization problem

从上述问题建模，RL的目标就是最大化expected return。以状态和环境都是stocastic为例，即环境我们也是无法完全预料的（如王者荣耀，不知道后面敌人会干嘛），只有一个概率。即从当前状态开始，利用policy后决定的所有可能的行动路径trajectory  所得到的return。

以接下来T个时间步为例，那么走某条行动路径  的概率为

那么expected return就可以加权求和了

所以问题就变成了最优化这个policy

1.7 value functions

value function其实就是用来计算上述提到的expected return的，定义也是一样的。

其中又分为

其实本质都是一样的，Q和V两个的区别只是在于当前state是否有相应的action，V就是所有当前所有action导致的Q的加权。

这个联系方式也是和1.6节中定义的optimization problem一致，即以当前状态为起点，所有action的expected return，只是换了一种写法，表示所有的路径  换成了随时间的V-Q关系。可以看出着形成了一个递推关系，V由Q决定，Q又由下一个时间步的V决定....

1.8 Bellman equation

在1.7中我们已经可以隐隐看到点随时间递推的痕迹了，而bellman equation就是这种formal的defination。可以推导一下：

只要第一次初始化后，每次更新都有一个链式法则的东西在做这样一个discount的事情。注意对每个  的更新时都是基于前一个状态步的state信息，需要等当前状态步  所有state全部更新完成后再统一关系状态图中的信息。所以我们可以得到：

 就是服从policy给每个action的概率，  就是服从采取action后环境给出的下一个状态概率。显而易见，在环境和policy都不定的情况下这个期望公式是完美服从的。

同理，  也是如此

自然optimal value也能容易推导出来，这两个方程揭示了一个重要的道理：如果我们要获得最大的expected return，那么我们每一步都选择当下最优的就行。同时，这个方程优化的是在average水平上最优的action选择，而不是绝对意义上最优的。

02

数学渊源：MDP与POMDP

2.1 与Markov Decision Processer的联系[2]

MDP可以说是RL的基础。从之前RL的value function也可以看出，RL考虑state的时候，下一个state只与当前的state有关，而不会考虑prior states。这就是MDP的思想。

Markov Property: the effects of an action taken in a state depend only on that state and not on the prior history

其余的理论MDP基本都体现在RL的value function和和Bellman Equation中了。

如上图所示，就是Markov Chain和Transition Matrix的代表。

实际上，bellman方程是可以直接解的，先用matrix形式写出表达式

写成matrix的形式是比较巧妙的，而且非常方便进行解。

其中  矩阵为转移矩阵，那么数值解value向量就可以直接解出，但是复杂度是  (  个states)。而我们要求的policy，就是在所有的policy中找到使得  最大的那个。

整个过程可以看到是一个非线性不断迭代的过程，无法得出一个closed-form的解析解，只能通过迭代得到数值解。

closed-form solution:通常我们把解析解analytic solution称为这个，即可以利用显示的数学表达式表达出结果的。
numerical solution：数值解，即在数值分析中可以通过迭代等方法求出的解。

迭代方法就很多了，如

• Value Iteration

• Policy Iteration

• Q-learning

• Sarsa

2.2 与Partially Observable Markov Decision Process联系

定义：A Partially Observable Markov Decision Process is an MDP with hidden states. It is a hidden Markov model with actions.

上述讲到的MDP是fully observation情况下的，现实情况下更多是无法完全观测到环境的，所以有一个新的观测变量  。这其实和隐马尔可夫HMDP很像，都有hidden states，但是加入了action。

左边是根据action和observation得到的历史状态树，右边是根据action和observation得到的belief state树

A belief state b(h) is a probability distribution over states, conditioned on the history h

03

Planning by dynamic programming[3]

动态规划最主要的需要两个key idea

• optimal substructure:最优子结构

• overlapping subproblem:重叠子问题

而我们再bellman方程中看到的递归方程式恰好满足这两个条件，所以可以用dp解决。当然，我们有policy和value这两个东西，解决的问题当然就是知道其中一个然后求出另外一个，如知道policy要求出value，就称为policy evaluation。

3.1 policy evaluation

• Problem: evaluate a given policy π

• Solution: iterative application of Bellman expectation backup

一个简单的例子如上图，用一个greedy的方法每次根据新的value确定新的policy，然后不断迭代的过程。不过一个好的policy不需要迭代到收敛因为会耗费太多时间，实际中我们可以提前截断迭代过程，但是不影响它是优的policy。

一个迭代的policy iteration的过程可以再下图中展现，policy和value的不断迭代。

3.2 value iteration

• Problem: find optimal policy π

• Solution: iterative application of Bellman optimality backup

但是和policy iteration不同的是，并没有显示的policy。并不像policy iteration那样，有value和policy的不断相互迭代和改进，value iteration是直接迭代value的。

因为都是用的最优的参数，一个简单的例子如下

每次我们挑选最大的  ，然后不断iterate这value。

3.3 Asynchronous DP

同步的DP来做就是之前讨论的，需要同时更新所有的state，每次都是等所有的state的状态都更新了然后统一更新。这意味着我们需要backup上一次所有的state状态。

在实际操作中，可以不用backup，称为In-place DP，不保留上一次的状态，利用实时更新后的state状态进行更新。

但是上述更新的一个缺点就每一轮迭代我们需要更新所有state的状态。因此还有一种称为Real-Time DP，只更新与阿根廷相关的state。

当然，在传统DP中，只适合处理问题规模不大的问题。state过多的话，需要的backup成本太高了，可以利用sample backup的方法，即只sample一部分。

我们可以看到，像sample这种MDP的东西是如何演化为RL的一部分并进行发展的。

参考

1. open ai rl introduction 

https://spinningup.openai.com/en/latest/spinningup/rl_intro.html

2. An Introduction to Markov Decision Processes 

https://www.cs.rice.edu/~vardi/dag01/givan1.pdf

3. UCL RL course 

https://www.davidsilver.uk/teaching/

本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。

直播预告

“强基固本”历史文章

分享、点赞、在看，给个三连击呗！