增强学习 Reinforcement learning part 2 - Markov Decision Process

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

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

1、Markov Processes

在RL中，MDP是用来描述environment的，并且假设environment是full observable的

i.e. The current state completely characterizes the process

许多RL问题可以用MDP来表示：

Optimal control primarily deals with continuous MDPs
Partially observable problems can be converted into MDPs
Bandits are MDPs with one state

先介绍两个基本知识

Markov Property：The future is independent of the past given the present

未来只与现在有关，与过去无关。这一点性质相当于是简化了模型。

State Transition Matrix：从状态s转换到状态s’的概率

把所有的状态转换概率写成矩阵P PS：矩阵每一行和为1

Markov Process：具有马尔可夫性的随机过程，用<S, P>来表示

S is a (finite) set of states
P is a state transition probability matrix

example：

2、Markov Reward Processes

MRP是在MP的基础上增加了一个值——reward。MRP用<S, P, R, gamma>来表示

其中S和P的定义与MP中的一样，R代表的是到达状态s后（或者说在状态s时）会得到的奖励（或者说是收益），gamma是折现因子，用于表示未来的收益折算到现在的比例，范围是0~1

example：

Return：从第t步开始，未来N步的总收益，未来的部分是有折扣的。return只是针对某个sequence而言

The return Gt is the total discounted reward from time-step t.

gamma越接近于0表示越看重眼前的收益，越接近于1表示越看重未来的收益。

为什么要用gamma这个discounted factor？

example：

假如MRP中某个sequence是C1 C2 C3 Pass Sleep，那么在C1时的return G1 = - 2 - 2 0.5 - 2 0.25 + 10 * 0.125 = -2.25

注意这里R2就表示在C1（S1）处的reward，之所以下标不一样，是因为在建模时，对于t的界定是新的t+1是从agent的action结束后，environment反馈reward和observation时开始算，所以状态St = s的reward用Rt+1来表示

Value Function：MRP中只有state value function——v(s)，状态s的value function。表示的是从状态s开始对未来的期望收益。（从状态s开始往后所有的sequence的收益的期望）

The state value function v(s) of an MRP is the expected return starting from state s

example：

计算方法见Bellman Equation部分

Bellman Equation：我们将v(s)进行一些数学变换，会发现v(s)可以分解成两部分，一部分是状态s的immediate reward Rt+1，另一部分是折扣过的下一state的v(St+1)

假设下一个state有两个，那么结构类似与下面这种树状图，将下一个的所有state都average起来求期望。就相当于树下面的加起来给上面的根节点

所以最终v(s)可以表示为

所以上面那个例子中每个state的v(s)计算过程如下：

可能会注意到计算class3的时候用到了pub，而如果计算pub的时候又会用到class3，有种循环递归的问题，但是实际上v(s)的计算表达式可以用矩阵的形式来表示

由于这是个线性方程，所以可以直接解出。那么上面说的循环递归的问题就不存在了，因为所有state的value function是同时求出来的

但是直接解的复杂度为O(n3)，n为state的个数，所以如果要用直接解法那么只能用于很小的MRP，对于很大的MRP，有很多迭代的方法可以用：

Dynamic programming（动态规划）
Monte-Carlo evaluation（蒙特卡罗强化学习）
Temporal-Difference learning（时序差分学习）

3、Markov Decision Processes

MDP是在MRP的基础上再加一个元素——action。MDP用<S, A, P, R, gamma>来表示

MDP是agent在自己的大脑中用来描述environment模型的，MDP中每个state都具有马尔可夫性

example：与MRP的example相比，概率变成了action，pub的state消失了，在这里如果在class3选择了pub这个action，直接会有0.2概率去class1，而不会有个pub这种state来停留

Policy：在一个state处，agent接下来会采取各种action的概率分布。实质上policy就是定义了agent的行为，在这个state会怎么选，在下一个state会怎么选等等

MDP的policy具有马尔可夫性，只与当前state有关。所以policy也是time-independent的

加入了policy后，P和R的计算方式

Value Function：在MDP中有两种value function

state-value function——vπ(s)，状态s的value function。在遵循policy的前提下，从状态s算起的未来期望收益

The state-value function vπ(s) of an MDP is the expected return starting from state s, and then following policy pi

action-value function——qπ(s, a)，在状态s处执行action a的value function。在遵循policy的前提下，在状态s处执行action a后算起的未来期望收益

The action-value function qπ(s, a) is the expected return starting from state s, taking action a, and then following policy pi

v是针对state而言，q是针对action而言

example：

计算方法见Bellman Expectation Equation部分

Bellman Expectation Equation：类似于MRP中的Bellman Equation，vpi(s)和qpi(s, a)也可以写成类似的表达式

类似的，也可以用树状图来表示其计算过程

在state s处，有两种action的选择，每种action有自己的value function，所以state s的value function就等于两种action的value function的加权和。

而选好一种action后，可能会跳转到的下一state有两种，所以action a的value function就等于两个下一state的value function的加权和。

把上面的树形结构链接起来后就是下面这个样子，如果要求state s的value function（也就是根结点是白点），那么如图左；如果要求action a的value function（也就是根结点是黑点），那么如图右。

example：

在MDP中vpi(s)的计算过程如下，假设选取每种action的概率相同

当然vpi(s)的计算还是可以用矩阵来表示的

direct solution：

当然，在实际中我们的目标是寻求一个最优解，在state处选择哪个action收益最好，所以就有了以下的内容

Optimal Value Function：

optimal state-value function——v* (s)，在所有的policy中，选出最大的vpi(s)
The optimal state-value function v*(s) is the maximum value function over all policies

optimal action-value function——q* (s, a)，在所有的policy中，选出最大的qpi(s, a)
The optimal action-value function q*(s, a) is the maximum action-value function over all policies

OVF代表着MDP中最优的表现（收益）。如果我们知道了OVF，也就意味着这个MDP是solved

example：

右边那个图pub的q* 应该是9.4 = 1 + (0.2 x 6 + 0.4 x 8 + 0.4 x 10)