ArchSummit全球架构师峰会门票9折倒计时中~ 了解详情
写点什么

强化学习:如何处理大规模离散动作空间

  • 2019 年 6 月 11 日
  • 本文字数:2313 字

    阅读完需:约 8 分钟

强化学习:如何处理大规模离散动作空间

在深度学习大潮之后,搜索推荐等领域模型该如何升级迭代呢?强化学习在游戏等领域大放异彩,那是否可将强化学习应用到搜索推荐领域呢?推荐搜索问题往往也可看作是序列决策的问题,引入强化学习的思想来实现长期回报最大的想法也是很自然的,事实上在工业界已有相关探索。因此后面将会写一个系列来介绍近期强化学习在搜索推荐业务上的应用。


本次将介绍两篇解决强化学习中大规模离散动作空间的论文。


第一篇是 DeepMind 在 2015 年发表的,题目为:


Deep Reinforcement Learning in Large Discrete Action Space


链接为:


https://arxiv.org/abs/1512.07679


适合精读;


第二篇是发表在 AAAI2019 上,题目为 :


Large-scale Interactive Recommendation with Tree-structured Policy Gradient


链接为:


https://arxiv.org/abs/1811.05869


适合泛读。


一、Introduction

传统的推荐模型在建模时只考虑单次推荐,那是否可以考虑连续推荐形成的序列来改善推荐策略呢?事实上已经有一些工作引入强化学习来对推荐过程进行建模。但有个问题就是推荐场景涉及的 item 数目往往非常高,大规模离散动作空间会使得一些 RL 方法无法有效应用。比如基于 DQN 的方法在学习策略时使用:



其中 A 表示 item 集合,对 A 中所有 item 均要计算一次 Q 函数。如果 |A| 非常大的话从时间开销上来讲无法接受。但这个方法有个优点就是 Q 函数往往在动作上有较好的泛化性。而基于 actor-critic 的方法中 actor 网络往往类似一个分类器,输出经过 softmax 后是动作上的概率分布,所以就避免了 DQN 类方法中的性能问题,但是这类方法缺点就是对未出现过的 action 泛化能力并不好。所以就需要寻找一种针对动作空间来说复杂度为次线性而且在动作空间上能较好泛化的方法。


二、Wolpertinger Architecture

该算法是第一篇论文提出来的,整体流程如下。



整个算法基于 actor-critic 框架,通过 DDPG 来训练参数,这里只介绍文章的重点部分即 action 的选择。算法先经过 得到 proto-action ,但 可能并不是一个有效的 action ,也就是说 。然后从 A 中找到 k 个和 最相似的 action ,表示为:



该步可在对数时间内得到近似解,属于次线性复杂度,避免了时间复杂度过高的问题。但是有些 Q 值低的 action 可能也恰好出现在 的周围,所以直接选择一个和 最接近的 action 并不是很理想的做法。为了避免选出异常的 action ,需要通过 action 对应的 Q 值再进行一次修正,表示为:



其中涉及的参数 包括 action 产生过程的 和 critic 网络的 。通过 Q 值的筛选可使得算法在 action 选择上更加鲁棒。


三、TPGR 模型

该算法是第二篇论文提出来的,主要思路是对 item 集合先预处理聚类从而解决效率问题,模型框架图如下。左半部分展示了一个平衡的树结构,整颗树对应着将 item 全集进行层次聚类的结果,每个根节点对应一个具体的 item 。右半部分展示了如何基于树结构进行决策,具体来说每个非叶节点对应一个策略网络,从根节点到叶子节点的路径中使用多个策略网络分别进行决策。TPGR 模型可使决策的复杂度从 降低到 ,其中 d 表示树的深度。下面分别介绍下左右两部分。



TPGR 模型框架图


  • 平衡的层次聚类


这步目的是将 item 全集进行层次聚类,聚类结果可通过树结构进行表示。文中强调这里是平衡的树结构,也就是说子树高度差小于等于 1,而且子树均符合平衡性质。设树的深度为 d ,除去叶子节点的父节点外其他中间节点的子树数均为 c ,可以得到 d 、c 和 item 数目 |A| 的关系如下:



涉及如何表示 item 和如何进行聚类两个问题。第一个问题,可以使用评分矩阵、基于矩阵分解方法得到的隐向量等方法作为 item 的表示。而第二个问题,文章提出了两种方法。篇幅有限,只介绍基于 Kmeans 改进的方法,具体来说:先进行正常的 Kmeans 聚类得到的簇中心 ( c 个 ) ,然后遍历所有簇,以欧几里得距离作为相似度指标将和簇中心最近的 item 加到当前簇中,遍历所有簇一遍后继续循环遍历所有簇,直到将所有 item 都进行了分配为止。通过这种分配的方式可使得最后每个簇的 item 数目基本一致,也就达到了平衡的要求。


  • 基于树结构的策略网络


之前提到,每个非叶节点均对应一个策略网络。其输入是当前节点对应的状态,输出则是每个子节点上的概率分布,也就是移动到每个子节点的概率。在上面的框架图中,根节点为 ,根据其策略网络输出的概率移动到 ,以此类推,最后到 ,将 推荐给 user 。策略网络具体采用 REINFORCE 算法,梯度更新公式为:



其中 表示 策略下状态 s 采取动作 a 的期望累积回报,可通过采用抽样来进行估计。


四、总结

一般推荐系统中会有召回步骤将候选的 item 范围缩小到几十到几百量级,所以从这个角度来看处理大规模离散动作的必要性就不那么大了。


TPGR 模型中平衡树和子树数目限制只是为了使时间复杂度保证是对数量级,也就是解决大规模离散动作空间的前提。而 item 分布都会有倾斜的情况,所以实际情况下将所有 item 集合聚类成数目基本一致的多个簇在实际情况下并不合理。这点肯定会影响到模型效果,所以树的构建可能还需要更多的探索和尝试。


作者介绍

杨镒铭,滴滴出行高级算法工程师,硕士毕业于中国科学技术大学,知乎「记录广告、推荐等方面的模型积累」专栏作者。


本文来自 DataFun 社区


原文链接


https://mp.weixin.qq.com/s/tX8l94v6bnBJB9uhDL25XA


2019 年 6 月 11 日 08:0012187

评论

发布
暂无评论
发现更多内容

【死磕JVM】什么是JVM调优?

牧小农

JVM jvm调优 JVM基础

聪明人的训练(二十六)

Changing Lin

4月日更

【TcaplusDB小知识】TcaplusDB的技术原理

数据人er

数据库 nosql TcaplusDB 国产数据库

JVM类加载机制笔记

六维

4月日更 JVM类加载

近期值得关注的四款工具

彭宏豪95

效率 工具 Mac 4月日更

linux高性能服务器编程--高性能服务器程序框架

赖猫

Linux 服务器开发 高性能服务器 C/C++后端

chia奇亚挖矿软件开发|chia奇亚挖矿APP系统开发

系统开发

Substrate 合约书之合约语言框架

Patract

rust Substrate polkadot Patract Wasm

贝壳基于 Flink 的实时计算演进之路

Apache Flink

flink

网络协议学习笔记 Day5

穿过生命散发芬芳

网络协议 4月日更

腾讯云TcaplusDB数据库联合盛趣游戏打造《上古卷轴:刀锋》传奇

TcaplusDB

数据库 nosql 技术 后端

容器 & 服务: 扩容(二)

程序员架构进阶

容器 k8s 28天写作 弹性扩容 4月日更

xch挖矿APP开发|xch挖矿系统软件开发

系统开发

2021团体程序设计天梯赛-部分题解

玄兴梦影

算法 比赛 算法解析

刹车失灵,数据的刹车是否也会失灵?

CloudQuery社区

数据库 运维 dba 数据库管理工具

怎么理解组织?

石云升

团队建设 28天写作 职场经验 管理经验 4月日更

分布式消息中间件(2):Kafka系统学习—集群搭建与使用、副本机制和实时日志统计流程

北游学Java

Java kafka 分布式 中间件

聚力边缘计算 共建数字中国丨浪潮边缘云ICP Edge 2.0 全新发布

浪潮云

阿里P8独家揭秘:短期内升职加薪的方法,到底是什么?

Java架构师迁哥

腾讯云TcaplusDB数据库服务《上古卷轴:刀锋》 助力手游行业发展

数据人er

数据库 nosql TcaplusDB Tcaplus 国产数据库

2021金三银四最新拼多多 +蚂蚁金服 +头条(已拿offer),面试真题分享!

Java 编程 程序员 架构 面试

基于MySQL存储的自研消息队列架构设计文档

Geek_2e7dd7

MySQL 死锁套路:一次诡异的批量插入死锁问题分析

AI乔治

Java MySQL 架构

系统高可用之健康检查和健康度量那些事

vivo互联网技术

高可用 服务器

教育是限制吗?

箭上有毒

4月日更

IT 专业的高校大学生编程技能及就业问卷调研

Yano

问卷调查

金三银四 Java 架构面试指南上线, 1000 余道大厂面试真题,送你上岸

Java 编程 程序员 架构 面试

Linux字符截取命令-cut

进击的梦清

Linux 运维 xshell

分布式消息中间件(1):Rabbitmq入门到高可用实战!学会了这个还怕被B站面试官看不起?

北游学Java

Java 分布式 RabbitMQ 中间件

chia奇亚分币软件开发|chia奇亚分币APP系统开发

系统开发

AI在游戏反外挂中的应用与实践

AI在游戏反外挂中的应用与实践

强化学习:如何处理大规模离散动作空间_文化 & 方法_DataFunTalk_InfoQ精选文章