增强学习 Reinforcement learning part 3 - Planning by Dynamic Programming

本文是在学习David Silver所教授的Reinforcement learning课程过程中所记录的笔记。因为个人知识的不足以及全程啃生肉，难免会有理解偏差的地方，欢迎一起交流。

课程资料：http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Teaching.html

1、Introduction

这一部分是用动态规划来解决MDP问题，所以先介绍下什么是动态规划

Dynamic Programming（动态规划），是用来解决一些复杂的问题，将复杂的问题分解为一些子问题，然后分别解决这些子问题，最后再把解决方案合并得到复杂问题的解

Dynamic：代表这个问题是连续的或者是跟时间相关的
Programming：不是编程的意思，而指的是优化一个程序

想要使用DP来解决一个问题，那么这个问题需要具有以下两种性质：

Optimal substructure：满足最优化原理，最优解分解后针对子问题也是最优解
Overlapping subproblems：子问题重复出现，对每一种子问题只计算一次，然后将结果存起来，下次直接使用

而MDP刚好满足这两条性质，bellman equation具有递归分解性，说明可以分解为子问题并且会重复出现（类似于斐波那契数列）；value function就相当于能够存储并且重复利用的解

要使用DP来解决MDP问题，假设条件是对MDP是充分认知（full knowledge）的

对于MDP来说，还是从两个方面来说，prediction and control

prediction的目的是给你policy，然后去预测使用这个policy的话各个state的value function，也就是预测使用这个policy的话未来的收益

control的目的是不给你policy，自己去寻找最优的policy以及未来最优的收益

扩展：动态规划还可以解决其他许多问题

Scheduling algorithms
String algorithms (e.g. sequence alignment)
Graph algorithms (e.g. shortest path algorithms)
Graphical models (e.g. Viterbi algorithm)
Bioinformatics (e.g. lattice models)

2、Policy Evaluation

策略评估

需要解决的问题：评估一个给定的policy

解决方案：以迭代次数为维度（或者理解成时间，一次迭代相当于过去了一个时刻，agent执行了一次action）不断去迭代Bellman Expectation Equation

可以证明，最终value function会收敛到vpi

采用同步更新的方式，在新的时刻所有的state同时更新

计算方法如下：

套用Bellman Expectation Equation，加上迭代次数维度，依据马尔可夫性，未来只与现在有关，所以求state s的k+1时刻的value function，就要使用k时刻state s’的value function，其中s’是s的后续state

上面的是RL part2中的计算方程，相当于是下面的计算方程迭代到最后已经收敛的形式

下面举个例子gridworld

这是个4x4的方格，那两个灰色的方格是特殊的state，可以看作是终点，其他14个白色的方格是普通的state，在白色方格时有四种action选择，向上下左右移动，各自的概率为0.25。每移动一步reward减1，直到灰色的方格

所以这个例子可以看作你随机出现在某个方格上，然后用最少的步数走到灰色方格。

下面是进行policy evaluation的迭代过程，k代表第几次迭代

先说左边的，选择的policy是random policy，就是在任何一个state，选择四个方向的概率都为0.25。初始v0的时候所有state的value都是0。然后v1时，利用上面vk+1(s)的公式进行计算（0.25x(-1+0)x4）。下面以v2中两个state来说明具体的计算过程

先计算state6（就是第二行第三个，这里对应公式的话就是s）在这次迭代中（对应公式的话就是k+1）的state value：如果向上走的话会移动到state2（对应公式的话就是s’），那这个action value就是reward(-1)加上state2上一时刻（对应公式的话就是k）的state value(-1)，所以向上移动是0.25x(-1-1)。向其他三个方向移动的计算方式和向上移动类似，结果也都是0.25x(-1-1)。所以state6在v2时的state value就是0.25x(-1-1)x4=-2

再计算state1（第一行第二个）的state value：如果选择向上走的话，因为上面没有格子了，所以会停在原地，那这次action value就是移动的reward(-1)加上state1上一时刻的state value(-1)，所以向上移动是0.25x(-1-1)。向下向右类似。向左移动的话是reward(-1)加上灰色格子上一时刻的state value(0)，所以向左移动就是0.25x(-1+0)。所以state1在v2时的state value就是0.25x(-1-1)x3+0.25x(-1+0)=-1.75。图中显示是-1.7，那是因为只能显示两位数。

如果一直迭代下去，当k为无穷的时候，各个state的value就已经收敛不会变了。

再说下右边的，显示的是每次迭代根据左边计算出来的state value选择出来的greedy policy。greedy policy指的是选出各个action value中最高的所对应的action。比如在v2时，state1的四个action value中，向左移动的action value是最高的，所以greedy policy在state1处只选择向左移动

当random policy经过许多步迭代后state value收敛到vpi时，这时候选出的greedy policy就是random policy的optimal policy

注意：evaluate任何一个policy（这里是random policy）都能得到greedy policy

总结：进行策略评估的实质就是计算在使用policy pi时各个state的value function，但是因为reword和action的存在，随着时间的推移（action次数的增加），每个state的value function会变化，但是最终会收敛到一个固定值vpi，然后使用greedy policy选出policy pi的optimal policy

3、Policy Iteration

策略迭代

在策略评估中，讲的是在给定一个policy pi后，先对其进行evaluate得到vpi，然后使用greedy policy来improve policy，得到新的policy pi’

在上面gridworld的例子中，因为这个例子很简单，所以经过一次improve后得到的pi’就已经是optimal policy pi*

但是通常说来，一般需要经过多次evaluation/improvement的过程才能得到pi*

这种不断evaluation/improvement的过程就称作策略迭代

注意：类似于policy evaluation中state value会收敛到vpi，在policy iteration中policy肯定会收敛到pi*

evaluation和improvement过程中的算法可以是任意的

example：

下面是具体讲一下improve过程，证明了为什么improve后vpi’(s)>=vpi(s)

modified：在evaluation部分，一定要等state value达到vpi吗？

事实上，这并不是必须的，就好比上面的gridworld例子，在第三次迭代的时候其实就已经是optimal policy了，所以没必要继续迭代下去

所以我们可以通过一些方法提前停止evaluation，比如在state value收敛的过程中设置epsilon，小于则停止迭代；或者是设置迭代k次就停止

如果设置evaluation只迭代一次，即k=1，那么这就是下面要讲的value iteration

总结：policy iteration相比于policy evaluation而言，后者是一次evaluation/improvement过程，只能得到比policy pi更好的policy pi’，而前者是多次evaluation/improvement过程，最终能得到该MDP的optimal policy pi*

4、Value Iteration

值迭代

上面说过能用DP解决的问题需要具有一个特点，满足最优化原理（Principle of Optimality），就是最优解分解之后针对每个子问题也是最优解，对于MDP来说，就是optimal policy可以分为两部分，当前state的optimal action A*，后续state的policy也是optimal policy
Any optimal policy can be subdivided into two components:

An optimal first action A*
Followed by an optimal policy from successor state S0

所以，若要满足一个policy pi使的state s的value为optimal value，当且仅当policy pi使得s的后续state s’的value为optimal value

所以知道了s’的optimal value便可以倒推出来s的optimal value

所以这便是value iteration的思想所在，迭代重复上面这个公式

直观上看来，是从最后一个state开始，倒推到第一个state，下面以一个例子来说明下

这个例子的目的是每个state找出到达左上角的最短路径（步数），其他方面类似于之前gridworld的例子，action是向四个方向移动，每移动一步reward减1

V1初始时所有的state的value都是0，然后在V2时，每个state从四个action value中选出最高的那个作为自己的state value（在policy iteration中是将四个action value求期望作为自己的state value），以第二行第二个为例，它在V1V2V3的时候四个action value都是一样的，所以没有相对的optimal，但是从V4开始，向上和向左比向下向右好，所以它的state value就一直为-2，拿V6来说，它的state value = max(-2, -2, -4, -4) = -2

在这个例子中需要注意这么几个问题：

每一次迭代中所有的state都要计算value，只不过有些state每次max的时候都是那些值（先达到了optimal value）所以看起来就不变了
在开始的时候不像policy iteration那样有个明确的policy，而且在迭代过程中state value并不对应于哪个policy，只有在最终迭代完成后（在例子中是V7）才对应于一个policy，而且还是optimal policy
如果以右下角那个state为开始的话，那路径就是-6 -5 -4 -3 -2 -1 0，而计算过程是-1 -2 -3 -4 -5 -6，所以符合上面说的Principle of Optimality的倒推性

所以对于value iteration来说

需要解决的问题：找到optimal policy pi*

解决方案：不断去迭代Bellman optimality Equation