策略梯度搜索：不使用搜索树的在线规划和专家迭代 | 技术头条
作者 | Thomas Anthony、Robert Nishihara、Philipp Moritz、
Tim Salimans、John Schulman
译者 | 李倩
编辑 | Rachel、Jane
出品 | AI科技大本营（ID：rgznai100）
蒙特卡罗树搜索（MCTS）算法执行基于模拟的搜索以改进在线策略。在搜索过程中，模拟策略适用于探索最有希望的游戏策略。MCTS已被用于处理许多最新的程序问题，但MCTS的一个缺点是需要评估状态值并存储其结果，这在分支树非常多的游戏场景中并不适用。
作者提出了一种替代性的基于模拟的搜索方法，即策略梯度搜索（PGS），该方法通过策略梯度更新在线调整神经网络模拟策略，避免了对搜索树的需求。在Hex中，PGS实现了与MCTS相当的性能，并且使用专家迭代算法（Expert Iteration）和 PGS训练的模型击败了MoHex 2.0，这是目前最强的开源Hex代理。
蒙特卡罗树搜索（MCTS）在Go和Hex等游戏中实现最大测试时间性能的价值早已为人所知。最近的研究表明，在许多经典的棋盘类游戏中，通过专家迭代算法将规划方法纳入强化学习智能体的训练，可以使用纯RL方法实现最好的性能。
但是，MCTS构建一个显式搜索树，每个节点会存储其访问数和估计值。所以在MCTS中需要多次访问搜索树中的节点。这种方法适用许多经典的棋盘游戏，但在许多现实世界的问题中，分支树都会非常大，这使得MCTS难以使用。大量的分支树可能由非常大的动作空间或偶然节点引起。在动作空间很大时，可以使用先前策略来降低弱动作的影响，从而减少有效分支树。随机转换更难以处理，因为先前的策略不能用于减少偶然节点处的分支因子。
相比之下，蒙特卡罗搜索（MCS）算法没有这样的要求。MCTS使用每个节点中的值估计来调整模拟策略，而MCS算法在整个搜索过程中都有固定的模拟策略。但是，由于MCS在搜索过程中不能提高模拟质量，因此它的效果会明显弱于MCTS。
基础理论：
1）Markov Decision Processes（MDP）：马尔可夫决策过程在每个时间间隔t中，代理观察状态并选择要采取的动作。对于终止状态，需要最大化阶段性奖励R。
2）Hex：Hex 是一个基于双人的基于连接的游戏，在n×n六边形网格上进行。游戏双方分别用黑色和白色棋子表示，双方轮流在空的位置上放置自己的棋子。如果白棋从左到右连续成线则白棋赢，若黑色棋子从上到下连成线则黑棋赢，下图是白棋赢的示意图。
3）Monte Carlo Tree Search（MCTS）：蒙特卡罗树搜索是一种随时可用的最佳树搜索算法。它使用重复的游戏模拟来估计状态值，并使用更优的游戏策略进一步扩展搜索树。当所有分支都模拟完成后，采取reward值最高的action。
4）Monte Carlo Search（MCS）：蒙特卡罗搜索是一种比MCTS更简单的搜索算法。给定状态和策略，通过迭代的模拟选择评估值最高的策略。
5）Expert Iteration：搜索算法基于单个状态s0的规划模型动作，但不学习推广到不同位置的信息。相比之下，深度神经网络能够在状态空间中推广知识。专家迭代算法将基于搜索的规划方法和深度学习进行了结合，其中规划算法作为专家，用于发现对当前策略的改进内容。神经网络算法作为学员，其模仿专家的策略并计算值函数。
Policy Gradient Search
策略梯度搜索通过应用无模型的强化学习算法来适应蒙特卡罗搜索中的模拟过程。作者假设提供先验策略π和先验值函数V，并在完整MDP上训练。
该算法必须对它通过非表格函数逼近器学习的所有内容进行表示，否则它将遇到与MCTS相同的问题。MCTS已经是一种自我对弈强化学习方法，但不能直接使其适应函数逼近，因为UCT公式依赖于基于访问量的探索规则。
作者使用策略梯度强化学习方法来训练模拟策略。模拟策略由具有与全局策略网络相同的体系结构的神经网络表示。在每个游戏开始时，策略网络的参数被设置为全局策略网络的参数。
由于评估模拟策略代价很大，所以该算法不会模拟到终止状态，而是使用截断的蒙特卡罗算法模拟。选择何时截断模拟并不简单，最佳选择策略可能取决于MDP本身。如果模拟太短，可能无法包含新的信息，或者没有给出足够长的时间范围搜索。太长的模拟则会导致恨到的时间开销。
对于Hex，作者使用与MCTS算法相同的策略：运行每个模拟过程，直到模拟的动作序列是唯一的。一旦我们在t步之后达到模拟的终止状态sL，使用全局值网络V估计该状态的值，并使用该估计更新模拟策略参数θ，其中α是学习率，其值在-1和1之间，对于其他问题，可能需要非零基线。可以将这些更新视为微调当前子游戏的全局策略。
因为在每次模拟中都要访问根节点，与 MCS 一样，可以使用基于单状态的强化学习方法来选择每个模拟的第一个动作。采用PUCT公式，选择令下式的值的动作：
Parameter Freezing during Online Adaptation
在测试期间，在线搜索算法通常受在时间约束的情况下使用，因此，与标准RL问题相比，其使用数量级更少的模拟。还需要注意的是，要确保该算法在每个模拟步骤中不需要太多计算。当在专家迭代中用于离线训练时，搜索方法的效率仍然至关重要。
Note on Batch Normalisation
神经网络使用批量标准化。在所有情况下，全局神经网络已经在来自许多独立采样的Hex游戏的状态数据集上进行了训练。
实验
Policy Gradient Search as an Online Planner
作者在Hex游戏中评估PGS。Hex具有中等数量的分支因子和确定性转换，这意味着MCTS在该领域中非常有效，这使作者能够直接比较PGS与MCTS的强度。作者在原始神经网络和四个搜索算法MCS，MCTS，PGS和PGS-UF之间进行了循环对弈，其中参数可变。为了克服Hex中第一个玩家具有的优势，每对智能体互相打了2*n*n场比赛。
每个智能体在每次移动使用800次搜索迭代，不会在移动之间思考。实验结果见下表。
如果策略搜索的能力已经饱和，那么PGS的扩展可能不如MCTS，但是并没有发现在游戏中会出现这种情况。但是，在每次移动中进行1600次迭代仍然是一个相当短的搜索，这样的情况可能会发生在较长时间的搜索过程中。
Policy Gradient Search Expert Iteration
作者使用PGS作为专家迭代算法中的专家进行实验，并与MCS和MCTS进行比较。
结果表明，PGS的性能优于MCS，但不如MCTS。在训练过程中，在反复应用更好或更差的专家时，智能体的差异更加复杂多变。
结论
作者提出了PGS算法，这是一种在线规划的搜索算法，不需要显式搜索树。PGS是一种有效的规划算法。实验结果证明，在9x9和13x13 的Hex游戏中，它的性能略微弱于MCTS，但与MCTS相比具有竞争力，同时其决策时间显著性能优于MCS。
在专家迭代算法的框架中使用PGS时，PGS在训练期间也很有效，该算法在不使用搜索树的情况下，训练了第一个有竞争力的Hex代理tabula rasa。相比之下，该算法比类似的强化学习算法和使用MCTS专家的专家迭代算法性能要好。
实验结果显示PGS-EXIT在专家迭代算法框架中性能明显优于MCS，并且还提供了第一个经验数据，表明MCTS-EXIT算法优于传统的策略迭代方法。
这项工作中提出的结果主要关注Hex的确定性和离散动作空间域。这使得模型的效果可以与MCTS直接比较，但PGS最激动人心的潜在应用是MCTS不易使用的问题，例如随机状态转换或连续动作空间的问题。
论文地址：
https://arxiv.org/abs/1904.03646
◆
CTA核心技术及应用峰会
◆
5月25-27日，由中国IT社区CSDN与数字经济人才发展中心联合主办的第一届CTA核心技术及应用峰会将在杭州国际博览中心隆重召开，峰会将围绕人工智能领域，邀请技术领航者，与开发者共同探讨机器学习和知识图谱的前沿研究及应用。
目前，确认出席的演讲嘉宾有漆桂林（东南大学教授、博士生导师）、李涓子（清华大学长聘教授、博士生导师，藏经阁计划学术负责人）、肖仰华（复旦大学教授、博士生导师）、谢殿侠（海知智能创始人&CEO）、谢晓辉（Hulu首席研究主管）、刘杉（腾讯音视频实验室负责人）、王昊奋（深圳狗尾草智能科技有限公司（Gowild）CTO）、朱其立（上海交通大学电子信息与电气工程学院教授）等。
目前会议早鸟票发售中（原票价1099元），点击阅读原文即刻抢购。扫码添加小助手微信 15101014297，备注CTA，了解大会详情。
推荐阅读
写代码这条路，能走多远？阿里算法专家告诉你
深度解析：特斯拉「最强」自动驾驶芯片？
我去面试Python岗位了，和你分享一些经验
Python、Java、C#、Perl 创始人聚首，编程语言要变天？
最强编程语言 Java 和最受欢迎之 Python 的巅峰对决
开发者如何写好技术简历？
回报率29%! 大神用情感分析创建一个比特币交易算法, 原来交易玩的是心理战
和 996 对着干的百亿巨头：不打卡，不设 KPI，福利好到爆，却称霸行业 20 年！
她说：为啥程序员都特想要机械键盘？这答案我服！
❤点击阅读原文，了解「CTA核心技术及应用峰会」
相关文章：
【FFmpeg】解码时refcounted_frames标志的使用
1、refcounted_frames说明 在接口 avcodec_decode_video2 的注释中，有关于 refcounted_frames 的详细说明： （1）当 AVCodecContext.refcounted_frames 被设置为1，该 AVFrame 被引用计数，返回的引用属于调用者。当不再需要 AVFrame 时，调用者必须使用 av_frame_unref() 来…
python-selenum3 第五天定位——不常用定位与css定位详
使用tag来定位tag定位的是标签，不常用例如：百度的输入框标签是input最终会报错，因为百度首页input标签太多了 driver webdriver.Firefox(executable_path"d:\\geckodriver") driver.get("https://www.baidu.com")driver…
nagios监控三部曲之——为什么nagios不能发送报警邮件(2)
最近我写了关于naigos监控的安装与配置的技术文档，公司运维按照我的文档部署naigos，发现不能发送报警邮件，经过我的检查，发现问题如下： 1、hosts里的配置 [rootnagios ~]# cat /etc/hosts # Do not remove the follow…
小样，加张图你就不认识我了？“补丁”模型骗你没商量！| 技术头条
作者 | Simen Thys, Wiebe Van Ranst(共同一作)译者 | 刘畅编辑 | Rachel、Jane出品 | AI科技大本营（id：agznai100）【导语】本文介绍了一个可以生成欺骗性补丁的系统模型，通过将该补丁放置在固定位置，人们能够使自己在…
【经验】如何查看gcc、g++不加-std时的默认版本
一、测试gcc 1、测试代码:c.c #include <stdio.h>int main(void) { #ifdef __STDC_VERSION__printf("__STDC_VERSION__ %ld \n", __STDC_VERSION__); #endif #ifdef __STRICT_ANSI__printf("__STRICT_ANSI__ %d \n", __STRICT_ANSI__); #endifre…
发布开源框架到CocoaPods入坑指南
个人原文博客地址: 发布开源框架到CocoaPods入坑指南在开发过程中一定会用到一些第三方框架, 只要安装了CocoaPods, 然后通过pod install命令, 就可以集成框架到项目中了可是如果想要把自己的框架或者组件也开源出去, 让别人也可以使用, 那该如何入手 ?对于CocoaPods还不是很了…
linux下打印机共享及监控
操作系统:centos6.0 主要软件：cups，samba，ghostpostscript 打印机：richo 3025 主要功能：通过samba将打印机共享给局域网用户，并实现对打印内容的监控 主要有三大步：本机安装打印机，通…
【H.264】x264命令详解：x264 --fullhelp
1、简述 宏区块： macroblock：。是一种图像压缩的术语。 宏区块是运动预测的基本单位，一张完整的图像（frame）通常会被切割成几个宏区块。h.264 的宏区块大小是可变的，常用 16x16 pixels。 帧类型 “帧”基础知识： 影片可以看作是由一张张连续的图片组成的，每幅图片就…
东大漆桂林、清华李涓子、复旦肖仰华等大牛确认出席CTA峰会！5月一起打卡杭州...
5月26日-27日，由中国IT社区CSDN与数字经济人才发展中心联合主办的第一届CTA核心技术及应用峰会将在杭州国际博览中心召开。首届CTA核心技术及应用峰会将聚焦人工智能，邀请技术领航者，与开发者共同探讨机器学习和知识图谱的前沿研究及应用。20…
【Oracle Database】数据库用户管理
创建用户 SQL> create user soe identified by soe default tablespace soe temporary tablespace temp; User created.查询用户的默认表空间 SQL> set line 200 SQL> col username for a30 SQL> col account_status for a20 SQL> select username,account_stat…
MySQL两主多从，且故障转移配置
一、角色划分1、MySQL数据库规划主机名 IP地址 角色 mysql_server_idweiliaodb1 192.168.1.233 master1 1weiliaodb2 192.168.1.234 master2 2weiliaodb3 192.168.1.235 slave1 3monitor 192.168.1.240 mmm_mon -2、虚拟IP规划IP地址 角色192.168.1.10 writer192.168.1.20 read…
Go开发者路线图2019，请收下这份指南
整理 | Rachel责编 | 阿司匹林出品 | AI科技大本营（ID: rgznai100）Go是Google开发的一种静态、强类型、编译型、并发型，并具有垃圾回收功能的类C编程语言。2009以开源项目的形式发布，2012年发布1.0稳定版本，距今已经十…
【Ubuntu】在Ubuntu中设置永久的DNS
1、问题描述 ping不通域名，比如“ping www.baidu.com”时，报错“ping: unknown host www.baidu.com”。这是因为ubuntu默认情况下没有设置DNS。 在ubuntu上设置DNS的方法，修改“/etc/resolv.conf”，添加“nameserver 8.8.8.8”&a…
实习期间问题总结
主要针对实习期间，接触的部分问题进行总结，后续会不间断的补充，作为实习期间的回顾。 1，git ,github和gitlab的关系 git 是一个版本控制工具，github是一个用git做版本控制的项目托管平台，他是一个网站&…
在windows sever 2008系统中如何添加桌面体验功能
1.开启THEMES服务：运行－services.msc －找到Themes服务项，默认是禁用，改为自动。 2.运行服务器管理器：左窗口选择功能－右边点“添加功能”在弹出的“添加功能向导”窗口中拖到最下面，…
17篇论文入选CVPR 2019，百度AI都在关注什么？（附论文地址）
整理 | 阿司匹林出品 | AI科技大本营（公众号id：rgznai100）计算机视觉和模式识别大会CVPR 2019即将于6月在美国长滩召开，作为人工智能领域计算机视觉方向的重要学术会议，CVPR每年都会吸引全球最顶尖的学术机构和公司的研…
【GStreamer】在x264enc中设置profile级别
1、问题描述 在使用GStreamer生成h.264的rtmp流时，不知道怎么设置h.264的profile级别。默认一直是“high”： video/x-h264, ... profile=(string)high, ...2、解决方法 查看官网手册中，有如下解释 The H264 profile that is eventually used depends on a few settings. …
js 使用a标签 下载资源
文档 let data new Blob([hello ajanuw], {type: application/text})let src window.URL.createObjectURL(data)let dl document.createElement(a)dl.href src;dl.download hello.txtdl.click() 切片下载 let data new Blob([hello ajanuw], {type: application/text }) …
linux 新增swap分区
由于用vmware 物理机转换成虚拟机时 忘记把swap 分区转过来了，只能手动在系统里添加了 1建立1G 大小的交换分区 # dd if/dev/zore of/opt/swapfile bs1M count1024 2,设置交换分区文件 # mkswap /opt/swapfile 3.立即启用交换分区文件 # swapon /opt/swapfile 4.使系…
通过cookies跳过验证码登陆页面，直接访问网站的其它URL
我每次手动访问去NN网的一家酒店，就不需要登陆，一旦我用脚本打开就会让我登陆，而登陆页面又有验证码，不想识别验证码，所以就想：“通过cookies跳过验证码登陆页面，直接访问网站的其它URL”转载虫…
可视化深入理解损失函数与梯度下降 | 技术头条
作者 | Hugegene译者 | 刘畅责编 | Rachel出品 | AI科技大本营（id：rgznai100）【导语】本文对梯度函数和损失函数间的关系进行了介绍，并通过可视化方式进行了详细展示。另外，作者对三种常见的损失函数和两种常用的激活函…
【Qt】Linux上设置自启动后qApp-＞applicationDirPath()的返回值问题
1、问题描述 开发程序过程中，使用qApp->applicationDirPath()返回程序所在目录，一直没问题。但是在设置自启动后，qApp->applicationDirPath()返回的目录不是程序所在目录。 2、原因分析 查看qApp->applicationDirPath()官方手册&…
sqlserver 行转列
还写了一篇Linq 实现 DataTable 行转列有时间大家可以看一下 sqlserver把行转成列在我们编码中是经常遇到的我做一个小例子大家看一下 1 --创建一个表 2 create table PayPhoneMoney 3 ( 4 id int identity(1,1), 5 userName Nvarchar(20), 6 payType nvarchar(20)…
Javascript闭包和闭包的几种写法及用途
好久没有写博客了，过了一个十一长假都变懒了，今天总算是恢复状态了。好了，进入正题，今天来说一说javascript里面的闭包吧！本篇博客主要讲一些实用的东西，主要将闭包的写法、用法和用途。 一、什么是闭包和闭…
【GStreamer】使用capsfilter设置x264enc中的profile级别
1、问题描述 在【GStreamer】在x264enc中设置profile级别中，通过设置x264enc的属性，只将profile由high级别切换到main，但是在切换到baseline时，失败了。 2、解决方法 这里使用capsfilter，直接指定x264enc的profile。相关代码如下： // 创建元素 GstElement *h264enc =…
一文帮你梳理清楚：奇异值分解和矩阵分解 | 技术头条
作者 | K. Delphino译者 | Linstancy编辑 | Rachel出品 | AI科技大本营（id：rgznai100）【导读】在推荐系统的相关研究中，我们常常用到两个相关概念：矩阵分解和奇异值分解。这两个概念是同一种算法吗？两者到底…
[转]程序员技术练级攻略
2019独角兽企业重金招聘Python工程师标准>>> 月光博客6月12日发表了《写给新手程序员的一封信》，翻译自《An open letter to those who want to start programming》，我的朋友（他在本站的id是Mailper）告诉我࿰…
聊天机器人落地及进阶实战 | 公开课速记
嘉宾 | 邵浩编辑 | suiling来源 | AI科技大本营在线公开课近年来，聊天机器人技术及产品得到了快速的发展。聊天机器人作为人工智能技术的杀手级应用，发展得如火如荼，各种智能硬件层出不穷。本次公开课中，AI科技大本营联合电子工业…
【GStreamer】官网基本教程学习（basic-tutorial）
目录 下载和编译basic-tutorial-1.c 直接创建管道播放视频basic-tutorial-2.c 创建元件-->装入管道-->连接元件0、gstreamer 函数调用顺序1、元素 videotestsrc 的 pattern 属性详解2、GST_BIN 将其它类型指针转换成 GstBin*basic-tutorial-3.c 信号触发后再连接元件0、g…
IdentityServer4关于多客户端和API的最佳实践【含多类型客户端和API资源，以及客户端分组实践】【中】...
上一篇文章中，我们已经完成了服务端数据库的搭建，本篇主要处理多【传统HTTP】【依赖CORE环境】客户端之间协同在线【SSO】以及不需要SSO的场景处理。 目标： 1）实现多类型客户端接入IdentityServer 后文简称【IDSV】 2）…