强化学习读书笔记 - 06~07 - 时序差分学习(Temporal-Difference Learning)

强化学习读书笔记 - 06~07 - 时序差分学习(Temporal-Difference Learning)

学习笔记: Reinforcement Learning: An Introduction, Richard S. Sutton and Andrew G. Barto c 2014, 2015, 2016

数学符号看不懂的,先看看这里:

时序差分学习简话

时序差分学习结合了动态规划和蒙特卡洛方法,是强化学习的核心思想。

时序差分这个词不好理解。改为当时差分学习比较形象一些 - 表示通过当前的差分数据来学习。

蒙特卡洛的方法是模拟(或者经历)一段情节,在情节结束后,根据情节上各个状态的价值,来估计状态价值。 时序差分学习是模拟(或者经历)一段情节,每行动一步(或者几步),根据新状态的价值,然后估计执行前的状态价值。 可以认为蒙特卡洛的方法是最大步数的时序差分学习。 本章只考虑单步的时序差分学习。多步的时序差分学习在下一章讲解。

数学表示 根据我们已经知道的知识:如果可以计算出策略价值(\pi状态价值v_{\pi}(s),或者行动价值q_{\pi(s, a)}),就可以优化策略。 在蒙特卡洛方法中,计算策略的价值,需要完成一个情节(episode),通过情节的目标价值G_t来计算状态的价值。其公式: Formula MonteCarlo V(S_t) \gets V(S_t) + \alpha \delta_t \\ \delta_t = [G_t - V(S_t)] \\ where \\ \delta_t \text{ - Monte Carlo error} \\ \alpha \text{ - learning step size}

时序差分的思想是通过下一个状态的价值计算状态的价值,形成一个迭代公式(又): Formula TD(0) V(S_t) \gets V(S_t) + \alpha \delta_t \\ \delta_t = [R_{t+1} + \gamma\ V(S_{t+1} - V(S_t)] \\ where \\ \delta_t \text{ - TD error} \\ \alpha \text{ - learning step size} \\ \gamma \text{ - reward discount rate}

注:书上提出TD error并不精确,而Monte Carlo error是精确地。需要了解,在此并不拗述。

时序差分学习方法

本章介绍的是时序差分学习的单步学习方法。多步学习方法在下一章介绍。

  • 策略状态价值\(v_{\pi}\)的时序差分学习方法(单步\多步)
  • 策略行动价值\(q_{\pi}\)的on-policy时序差分学习方法: Sarsa(单步\多步)
  • 策略行动价值\(q_{\pi}\)的off-policy时序差分学习方法: Q-learning(单步)
  • Double Q-learning(单步)
  • 策略行动价值\(q_{\pi}\)的off-policy时序差分学习方法(带importance sampling): Sarsa(多步)
  • 策略行动价值\(q_{\pi}\)的off-policy时序差分学习方法(不带importance sampling): Tree Backup Algorithm(多步)
  • 策略行动价值\(q_{\pi}\)的off-policy时序差分学习方法: \(Q(\sigma)\)(多步)

策略状态价值v_{\pi}的时序差分学习方法

单步时序差分学习方法TD(0)

  • 流程图
  • 算法描述

多步时序差分学习方法

  • 流程图
  • 算法描述

策略行动价值\(q_{\pi}\)的on-policy时序差分学习方法: Sarsa

单步时序差分学习方法

  • 流程图

  • 算法描述

多步时序差分学习方法

  • 流程图

  • 算法描述

策略行动价值q_{\pi}的off-policy时序差分学习方法: Q-learning

Q-learning 算法(Watkins, 1989)是一个突破性的算法。这里利用了这个公式进行off-policy学习。 Q(S_t, A_t) \gets Q(S_t, A_t) + \alpha [R_{t+1} + \gamma \underset{a}{max} \ Q(S_{t+1}, a) - Q(S_t, A_t)]

单步时序差分学习方法

  • 算法描述
  • Q-learning使用了max,会引起一个最大化偏差(Maximization Bias)问题。 具体说明,请看书上的Example 6.7。** 使用Double Q-learning可以消除这个问题。

Double Q-learning

单步时序差分学习方法

策略行动价值q_{\pi}的off-policy时序差分学习方法(by importance sampling): Sarsa

考虑到重要样本,把\(\rho\)带入到Sarsa算法中,形成一个off-policy的方法。 \rho - 重要样本比率(importance sampling ratio) \rho \gets \prod_{i = \tau + 1}^{min(\tau + n - 1, T -1 )} \frac{\pi(A_t|S_t)}{\mu(A_t|S_t)} \qquad \qquad (\rho_{\tau+n}^{(\tau+1)})

多步时序差分学习方法

  • 算法描述

Expected Sarsa

  • 流程图
  • 算法描述 略。

策略行动价值q_{\pi}的off-policy时序差分学习方法(不带importance sampling): Tree Backup Algorithm

Tree Backup Algorithm的思想是每步都求行动价值的期望值。 求行动价值的期望值意味着对所有可能的行动\(a\)都评估一次。

多步时序差分学习方法

  • 流程图

  • 算法描述

策略行动价值q_{\pi}的off-policy时序差分学习方法: Q(\sigma)

  • 算法描述

总结

时序差分学习方法的限制:学习步数内,可获得奖赏信息。 比如,国际象棋的每一步,是否可以计算出一个奖赏信息?如果使用蒙特卡洛方法,模拟到游戏结束,肯定是可以获得一个奖赏结果的。

参照

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏奇点大数据

福利赠书!《图解深度学习与神经网络:从张量到TensorFlow实现》

作为一个三观奇正,有志于分享的公众号,奇点在每周五都有“赠书福利”环节,把更多的好书介绍给读者。关注并转发本篇文章,然后将截图发至后台就可以参与抽奖,每周一奇点...

67630
来自专栏华章科技

大神Hinton的Capsule论文终于公开,神经网络迎来新探索

今年9月的一次大会上,大神Geoffrey Hinton再次号召展开一次AI革命。

9730
来自专栏AI科技评论

学界 | 腾讯AI Lab解读多篇ACL 2018入选长文

本文转载自腾讯 AI Lab,微信号 tencent_ailab。本文将详解 2018 年 NLP 领域顶级学术会议 ACL 上,腾讯AI Lab入选 5 篇文...

14520
来自专栏量子位

实录 | 旷视研究院解读COCO2017物体检测夺冠论文(PPT+视频)

主讲人:彭超 | 旷视研究院研究员 屈鑫 整理编辑 量子位 出品 | 公众号 QbitAI 12月6日晚,量子位·吃瓜社联合Face++论文解读系列第一期开讲,...

441160
来自专栏人工智能头条

微软资深研究员详解基于交错组卷积的高效DNN | 公开课笔记

15910
来自专栏新智元

榜单 | Github 深度学习项目排行榜

【新智元导读】GitHub上根据星级(stra)列出了最常用的53个深度学习项目。其中,最受欢迎的是TensorFlow。表格的整理人ID分别是aymericd...

509100
来自专栏决胜机器学习

机器学习(二十四) ——从图像处理谈机器学习项目流程

机器学习(二十四)——从图像处理谈机器学习项目流程 (原创内容,转载请注明来源,谢谢) 一、概述 这里简单讨论图像处理的机器学习过程,主要讨论的是机器学习的项...

43450
来自专栏机器学习算法与Python学习

干货 | 8个方法解决90%的NLP问题

15030
来自专栏WeaponZhi

机器学习一:线性回归

视频及 PPT 原教程:https://pan.baidu.com/s/1geFro9H 密码:50sc 线性回归中维基百科的定义如下:

16650
来自专栏机器之心

从大间隔分类器到核函数:全面理解支持向量机

319100

扫码关注云+社区

领取腾讯云代金券