没有合适的资源?快使用搜索试试~ 我知道了~
一种加速时间差分算法收敛的方法.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 115 浏览量
2023-02-23
20:18:39
上传
评论
收藏 1.02MB DOCX 举报
温馨提示
试读
15页
一种加速时间差分算法收敛的方法.docx
资源推荐
资源详情
资源评论
强化学习是机器学习领域中最接近人类和动物学习的方法
[1]
, 在机器人自主决策和学
习、复杂动态系统的优化控制和自动驾驶等领域中有着广泛的应用
[2-5]
. 强化学习算法分为
基于模型和无模型两种. 基于模型的算法需要一个精确且完整的环境模型, 而无模型算法没
有这个要求. 无模型的强化学习算法中基于值函数的算法较为常用. 该算法需要根据值函数
得出最优的策略. 如果值函数无法准确地被评估, 或者评估的效率过低, 那么将得不到最优
的策略, 或者耗时过长. 所以, 一个精确和高效的值函数评估方法对于基于值函数的强化学
习算法至关重要
[6-7]
.
对于值函数评估问题, 经典的解决方法是 TD (Temporal difference methods)算法和 MC
(Monte Carlo methods)算法. 其中, TD 算法可以像动态规划(Dynamic program)方法一样使用
自举(Bootstrap)的方式, 即利用已经评估过的状态值来进行新的评估. 这也使得 TD 算法可
以不需要等待情节结束, 就可以进行值函数的更新, 从而实现了在线学习的方式. MC 算法
必须等到情节结束后才能进行值函数的更新, 因而只能使用离线学习(Off-line)的方式
[1]
. 但
是如果 TD 算法所利用的评估过的状态值有偏差, 那么评估的结果往往在真实值附近. 另
外, TD 算法的收敛效率很大程度上取决于初值和步长参数的设定. 优秀的初值和恰当的步
长参数可以极大地缩小所需要策略迭代的次数, 但是初值的设定往往需要丰富的经验和相
关领域的专业知识. 对于步长参数设定的问题, 有许多自动设置步长参数的算法可以解决
[8-
9]
. 然而, 尽管这些算法有许多理论上的优势, 但是由于其自身的复杂性和进一步增加了 TD
算法的时间复杂度而得不到广泛的运用, 实际应用中更多地采用固定步长参数的方法
[10]
. 这
也就造成了加速一个特定 TD 算法收敛速率的方法的匮乏.
论文提出的 ATDMC 方法是利用 MC 算法的无偏的性质, 在 TD 算法完成一次值函数
评估后, 进行值函数改进. 即在广义策略迭代中加入减少值函数和真实值函数的之间距离的
步骤, 使得在不改变 TD 算法的在线学习的方式基础上, 加速算法的收敛.
文中第 1 节描述了强化学习的相关基本概念和所用到的符号的定义. 第 2 节给出 TD
算法的收敛速率的分析和 ATDMC 方法的详细推导过程. 第 3 节用实验分别展示在同策略
评估、异策略评估和控制三个方面的加速效果. 最后一节给出结论和后续的工作方向.
1. 强化学习相关基本概念
1.1 马尔科夫决策过程
马尔科夫决策过程(Markov decision process, MDP)是研究各种强化学习算法的理论基
础, 可以对大多数强化学习问题进行建模
[11]
. 这是因为 MDP 是在交互过程中学习以期达到
某种目标的问题的框架, 而强化学习问题是指如何在和环境交互过程中使得收到的累计奖
赏最大化的问题. 其中, 学习和决定动作的对象称为智能体(Agent), 智能体交互的对象为环
境.
MDP 是由一个 4 元组(S,(S, A,A, R,R, P)P)构成. 其中, SS 是指智能体在和环境进行交
互过程中, 环境的所有状态构成的集合. AA 是指智能体采取的动作构成的集合, 收到的奖
赏构成的集合为 R.R. PP 是由状态转移函数构成. 智能体和环境的一次交互是指智能体采取
一个动作(Action)后, 环境返回一个奖赏(Reward), 然后智能体对环境进行观测, 得到一个新
的状态(State). 为了表述简单, 将一次完整的交互定义在时间步 tt 发生, 智能体所处的状态
记为 St,St, 采取的动作记为 At,At, 获得的奖赏记为 Rt+1,Rt+1, 到达的下一个状态记为
St+1.St+1. 将由时间步 00 到终止时间步 TT 的整个过程称为一个情节(Episode). 可见, 一个
情节中智能体经过的状态、采取的动作和获得的奖赏构成了一个序列:
S0,A0,R1,S1,A1,R2,⋯S0,A0,R1,S1,A1,R2,⋯
将其中的奖赏的累计求和称为累计奖赏. 从状态 StSt 开始, 直至结束状态 STST 获得
的累计奖赏定义为:
Gt=∑i=t+1TRiGt=∑i=t+1TRi
(1)
在一些强化学习任务中, 最近获得的奖赏往往被赋予更大的权重值. 因为相比于过去
获得的奖赏, 新的奖赏更值得关注. 另外, 当情节的时间步较长时, GtGt 将会变为一个比较
大的值. 对此, 往往需要对获得的奖赏乘上一个折扣因子 γγ, 来控制 GtGt 的大小, 则:
Gt=∑i=t+1Tγi−t−1RiGt=∑i=t+1Tγi−t−1Ri
(2)
可见, 如何使 GtGt 最大化的问题即为强化学习在 MDP 框架下所要解决的问题.
1.2 广义策略迭代
广义策略迭代(Generalized policy iteration, GPI)是强化学习中最一般的思想, 几乎所有
的强化学习算法都可以描述成广义策略迭代的形式. 强化学习算法所要最大化的目标 GtGt
的值是由在各个状态下采取的动作决定的, 而在某个状态采取何种动作是由策略决定的. 强
化学习的目标即为寻找一个策略使得 GtGt 最大化, GPI 对此提供了具体思路.
GPI 可以分为策略评估(Policy evaluation)和策略改进(Policy improvement)两部分, 由这
两部分交替进行从而实现该思想. 其中, 策略评估是指在一个特定的状态下, 对遵循一个固
定策略的智能体将会收到的累计奖赏的期望进行估值. 对于一个给定的策略 π,π, 从 tt 时间
步开始, 获得的累计奖赏的期望记为:
vπ(St)=Eπ[Gt|St]vπ(St)=Eπ[Gt|St]
(3)
这个值被称为状态 StSt 的 vv 值, 也称为 StSt 在策略 ππ 的真实值. 相应地, 如果在时
间步采取的动作为 AtAt, 那么获得的累计奖赏的期望为:
qπ(St,At)=Eπ[Gt|St,At]qπ(St,At)=Eπ[Gt|St,At]
(4)
这个值也被称为状态动作对(St,At)(St,At)的 qq 值. 由 vv 值和 qq 值的定义可知:
vπ(St)=EAt[π(At|St)qπ(St,At)]vπ(St)=EAt[π(At|St)qπ(St,At)]
(5)
其中, π(At|St)π(At|St)是在状态 StSt 采取动作 AtAt 的概率.
策略评估后, 会根据评估出来的 qq 值函数进行策略改进. 策略改进一般采用 ϵϵ-greedy
算法, 即最大的 qq 值对应的动作被选取的概率为 1−ϵ1−ϵ, 另外有 ϵϵ 的概率任取一个动作.
一次策略评估和策略改进形成了一次完整的策略迭代. 下一轮迭代将根据新的策略继续评
估, 然后再改进策略. 经过多次策略迭代后, 策略达到了稳定的状态, 各个状态的值函数达
到最大值. 此时的策略称为最优策略, 对应的值函数称为最优值函数, 记为
v⋆(St)=maxπvπ(St)v⋆(St)=maxπvπ(St)
(6)
1.3 TD 算法
TD 算法是强化学习中最核心的算法, 可以用来评估 vv 值和 qq 值函数. 如果一些状态
的值函数已被评估过或是被赋予了初值(虽然初值可能是错误的, 但也可以视为被评估过),
则可以利用这些评估过的值来评估其他状态的值函数. TD 算法会对每一个 vv 值或者 qq 值
进行赋初值, 再利用这些初值进行新的评估, 然后进行策略改进, 不断循环进行从而实现
GPI.
TD 算法策略迭代的过程可以看作是值函数不断向 v⋆v⋆靠近的过程. 在具体的 TD 算
法中, v⋆v⋆是未知的值, 往往被替换成相应算法的目标 UTDUTD. 根据所利用的评估过的值
函数是一步还是多步之后的状态的值函数, 将 TD 算法分为一步或 nn 步 TD. 对于 nn 步
TD 算法而言, UTDUTD 为:
Gt:t+n=∑i=t+1t+nγi−t−1Ri+γnV(St+n)Gt:t+n=∑i=t+1t+nγi−t−1Ri+γnV(St+n)
(7)
其中,V(St+n)V(St+n)为 nn 步之后的状态的 vv 值的估计值, 而这个值可能是错误的.
如果该值为对应状态的真实值, 则显然 Gt:t+nGt:t+n 的期望也为真实值. 另外, nn = 1 的情况
即为一步 TD 的 UTDUTD. 利用 nn 步 TD 算法的目标, TD 算法的值函数的更新公式为:
V(St)=V(St)+α(Gt:t+n−V(St))V(St)=V(St)+α(Gt:t+n−V(St))
(8)
其中, αα 为步长参数.
强化学习在处理状态空间很大的问题时, 往往采用函数逼近的方法. 使用状态的特征
向量 x(St)x(St)和权重向量 ww 来表示状态的值函数. 在使用线性逼近方法的情况下, 值函
数记为:
V(St,w)=wTx(St)V(St,w)=wTx(St)
(9)
显然在函数逼近的条件下, 并不一定存在一个权重向量 ww 使得所有状态的值都能等
于对应的 vπ.vπ. 所以, 为了求出使得值函数和 vπvπ 之间的距离的平方和最小的 w,w, 将损
失函数定义为:
L(w)=∑i=t+1T(vπ(St)−V(St,w))2L(w)=∑i=t+1T(vπ(St)−V(St,w))2
(10)
由于 vπ(St)vπ(St)值未知, 将其替换为 UTD.UTD. 那么 TD 算法的权重向量的更新公式
定义为:
w=w+α(UTD−V(St,w))∇V(St,w)w=w+α(UTD−V(St,w))∇V(St,w)
(11)
1.4 MC 算法
MC 算法是另外一种强化学习中评估值函数的算法. MC 算法的值函数的更新公式为:
V(St)=V(St)+Gt−V(St)nV(St)=V(St)+Gt−V(St)n
(12)
剩余14页未读,继续阅读
资源评论
罗伯特之技术屋
- 粉丝: 3692
- 资源: 1万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功