Processing math: 90%
文章目录
  1. 1. 目录
  2. 2. 0.写在前面
  3. 3. 1. 策略评估
  4. 4. 2. 策略改进
  5. 5. 3. 策略迭代
  6. 6. 4. 值迭代
  • author: zhouyongsdzh@foxmail.com
  • date: 2017-11-04
  • weibo: @周永_52ML

目录

0.写在前面

上一节讲到马尔科夫决策过程,并把强化学习问题用MDP框架建模。并且介绍了强化学习的目标是寻找最优策略π使得累计回报Gt的期望最大,累计回报Gt是个随机变量,无法当成目标函数进行优化,因为把随机变量(Gt)的期望作为目标函数。

这一节介绍基于模型的强化学习问题求解的一种算法-动态规划算法。动态规划算法是解决复杂问题的一类方法,算法通过把复杂问题分解成若干个子问题,通过求解子问题进一步得到全局问题的解。

所谓基于模型的强化学习即马尔科夫决策过程已知(即状态转移概率已知)。如果MDP未知,称为无模型(model-free)的强化学习,仍有对应的求解算法(后面章节会详细介绍)。

使用动态规划求解问题 需要满足以下条件:

  • 最优化原理:问题的最优解是由所包含的子问题的解组成,且子问题的解也是最优的;
  • 子问题重叠:即子问题之间不是独立的,一个子问题在下一阶段决策中可能被重复用到。

马尔科夫决策过程满足上述两个条件,即贝尔曼方程把值函数的求解表示成递归地子问题求解过程,值函数相当于存储了一些子问题的解,可以复用。

在强化学习中,动态规划是基于模型的求解最优策略和最优值函数的算法,即在已知模型的基础上判断一个策略的价值函数(策略评估过程),并在此基础上寻求最优的策略和最优价值函数(策略改进过程)。或者直接寻求最优策略和最优价值函数(价值迭代算法)。

动态规划算法属于值表法(Tabular Methods)的一种(下一章的蒙特卡洛方法也属于这一类)。值表法即值函数用表格表示,值函数的参数为表格里的内容。

思考:如何用动态规划算法在MDP基础上求解最优策略?动态规划包括两个主要过程:预测(predict)和控制(control)。

  • 预测:给定一个MDP和当前策略π,要求基于当前策略π计算价值函数Vπ
  • 控制:给定一个MDP,要 求计算最优价值函数V和最优策略π

1. 策略评估

上一节提到,强化学习问题可以用MDP描述,并根据贝尔曼最优性原理得到贝尔曼最优化方程,即:

\begin{align} v_*(s) & = \max_{a \in \mathcal{A}} R(s,a) + \gamma \sum_{s’ \in \mathcal{S}} P(s’ |s,a) v__(s’) \\\ q__(s,a) & = R(s,a) + \sum_{s’ \in \mathcal{S}} P(s’|s,a) \max_{a’ \in \mathcal{A}} q_*(s’,a’) \end{align}  \qquad (rl.4.1)

贝尔曼方程符合动态规划中的条件,在这里动态规划的核心是寻找最优值函数。一个关键的问题摆在面前:如何计算策略π下的值函数? 在第03章部分已经给出了计算公式:

vπ(s)=aAπ(a|s)(R(s,a)+γsSP(s|s,a)vπ(s)) qπ(s,a)=R(s,a)+γsSP(s|s,a)aAπ(a|s)qπ(s,a)(rl.4.2)

可以看到状态s的值函数vπ(s)可以利用后继状态的值函数vπ(s)来表示。后继状态值函数vπ(s)又该如何求解呢?貌似是个没完没了的过程~~~

其实不然,对于模型已知的强化学习问题,公式(rl.4.2)中的P(s|s,a),γ以及R(s,a)都是已知的,π(a|s)为要评估的策略是指定的,也是已知值。公式(rl.4.2)中唯一的未知数是值函数,那么可以把(rl.4.2)理解为关于值函数的线性方程组,未知数的个数为状态总数,用|S|表示

考虑到状态值函数序列v0,v1,v2,,初始到值函数v0可以是任意的(除非为最终状状态值函数,值为0)。接下来的值函数都是根据贝尔曼方程得到,更新逻辑为:

vk+1(s)=Eπ[R(s,t)+γvk(St+1)|St=s] =aA(R(s,a)+γsSP(s|s,a)vk(s))(rl.4.3)

这里vk=vπ,序列{vk}最终将会收敛到vπ对应的值函数(稳定状态),这个算法称为迭代策略评估算法(Iterative Policy Evaluation)。下面给出策略评估算法的伪代码:

这部分参考教材的伪代码

$
\{ \;//\; \color{red} {迭代策略评估算法} \\\

  1. 输入
    \\\ \}
    $

[optional] 补充Gridworld示例。

策略评估算法用于根据当前策略计算每个状态的值函数的,计算值函数的目的是为了寻求最优策略。那么,如何利用状态值函数改进策略,进而得到最优策略呢

2. 策略改进

策略改进(policy improvement)采用了比较直接的做法:在已知当前策略的值函数时,在每个状态采用贪婪策略(greedy policy)对当前策略进行改进,形式化表示如下:

π(s)=argmax

这里\pi为当前策略,\pi’为改进后的策略。

至此,我们介绍了策略评估(依据当前策略预测值函数)和策略改进(依据贪婪策略选择最大值函数对应的策略),将二者合起来即为策略迭代算法。

3. 策略迭代

策略迭代算法包括策略评估和策略改进两个步骤。

  • 策略评估:给定策略,通过数值迭代算法不断计算该策略下的值函数,直至收敛
  • 策略改进:利用收敛的值函数和贪婪策略得到新的策略;

如此循环下去,最终得到最优策略和最优值函数,是一个策略收敛的过程。策略迭代算法伪代码如下:

这部分参考教材的伪代码

$
\{ \;//\; \color{red} {策略迭代算法} \\\

  1. 输入
    \\\ \}
    $

4. 值迭代

从策略迭代算法的伪代码可以看到,每一轮迭代中,在进行策略改进之前都要得到收敛的值函数,收敛的值函数需要很多次循环才能得到。问题:进行策略改进之前一定要得到当前策略对应的收敛值函数吗?

示例:网格,迭代10次。

我们发现,当前策略迭代10次与迭代无穷次所得到的贪婪策略都是一样的。因此,对于上面的问题,不一定非得等到策略评估算法完全收敛,才进行策略改进。如果在进行一次策略评估之后就进行策略改进,称之为值函数迭代算法。 值函数迭代算法的伪代码如下:

<伪代码>

可以看到,这里每次迭代过程在策略评估阶段只对状态空间扫描一次。

文章目录
  1. 1. 目录
  2. 2. 0.写在前面
  3. 3. 1. 策略评估
  4. 4. 2. 策略改进
  5. 5. 3. 策略迭代
  6. 6. 4. 值迭代