2.4 时序差分算法

category
type
status
slug
date
summary
tags
password
icon
本系列为学习赵世钰老师的《强化学习的数学原理》所作的学习笔记.
课程视频网址：https://space.bilibili.com/2044042934
本节我们将介绍强化学习中的蒙特卡洛方法.

2.4.1 Robbins-Monro算法

Robbins-Monro算法是一种随机近似方法，通过迭代的方式求解非线性方程。
假设我们要求解: , 但是我们没有的具体函数形式, 只有它的观测数据:
其中是观测误差, 那么我们可以利用观测数据, 迭代式的逼近的根:
其中是一个大于0的参数, 迭代过程如下图, 这种方法就是Robbins-Monro算法. 它的收敛性证明可以前往书中查看.
notion image

2.4.2 TD learning 时序差分算法

2.4.2.1 推导

时序差分算法用来计算给定策略和其状态的状态值期望, 即贝尔曼公式:
因为的discounted return实际上就是其状态值的期望:
因此贝尔曼公式也可以写作, 也叫做贝尔曼期望公式:
TD算法就是利用RM算法迭代求解贝尔曼公式, 首先我们定义求解目标:
接着我们写出它的采样:
然后根据RM算法, 写出更新方程:
实际上, 上式就是TD learning算法更新公式

2.4.2.2 定义

假设我们基于一个策略, 按时间步顺序生成了一组状态和奖励: , 用下式更新, 就是时序差分算法:
  • 是TD target, 代表更新的目标
  • 是TD error, 代表更新的目标与之间的误差
我们可以简写成如下形式, 显然这符合Robbins-Monro算法的形式:

2.4.2.3 TD target 和 TD error

为了理解为什么是更新的目标, 并做推导:
因为是一个小的正数, 因此, 所以:
这说明了: 比离更近, 代表这算法是在朝着目标迭代更新.
那么代表误差就很容易理解了, 当时, 代表已经达到了目标.
 

2.4.3 TD learning 和 MC learning对比

2.4.3.1 在线/离线

  • TD learning: 是在线算法, 每迭代一步(从到)就可以在线更新;
  • MC learning: 是离线算法, 也就是它必须等到episode采样结束, 才能更新

2.4.3.2 持续任务/片段任务

  • TD learning: 可以处理持续和片段任务, 因为它是在线更新的, 所以不需要等到采样完整结束;
  • MC learning: 只能处理持续和片段任务,因为它必须要等到此案有完整结束才能更新

2.4.3.3 Bootstrapping

  • TD learning: Bootstrapping, 它在初始猜测策略的基础上, 不需要完整的episode就能更新策略; 但是相应的, 差的初始猜测会让他更难接近最优解.
  • MC learning: none Bootstrapping, 它不需要初始猜测, 可以直接估计状态/动作值.

2.4.3.4 估计方差

  • TD learning: 估计方差小, 因为它涉及的随机变量较少, 只需要一步的数据;
  • MC learning: 估计方差大, 因为涉及许多随机变量。例如，要估计，我们需要的样本。假设每个片段的长度是。假设每个状态有相同数量的动作，即。那么，按照软策略，一共有种可能的片段。但是MC只使用部分片段来估计整体，所以估计方差较高.
 
上一篇
动手学控制理论
下一篇
端到端-理论与实战视频课程
Loading...