首发于AI打怪路
强化学习之超系统的多臂老虎机应用综述

强化学习之超系统的多臂老虎机应用综述

在研究机器学习/深度学习/强化学习+组合优化的小伙伴欢迎加我微信jjnuxjp5x呀,这条路好艰难,一起逼逼防抑郁嘿嘿嘿~


(好想研究ml/rl+组合优化的小伙伴赶紧冒出来,把积极的拉个群好好讨论呀,这块要做出新意和效果来太难了哈哈哈,如果过期了就加我微信jjnuxjp5x,我拉您入群哈~目前群里聊得火热呀。btw,欢迎大家帮忙宣传,感激不尽我会尽力为社区做贡献的!


(不好意思吖,大噶看到多臂强盗/多武装土匪,默认为多臂老虎机就好哈。本憨憨修改此文码到眼冒金星,先去ICU转一圈yoxi(●'◡'●)~)

摘要

近年来,多臂老虎机(multi-armed bandit,简称MAB)框架因优异的性能和较少的反馈学习等优点,在从推荐系统、信息检索到医疗保健和金融等诸多应用领域受到广泛关注。随着各种实际应用所激发的新型问题设置和算法的引入,多臂强盗问题在经典强盗问题的基础上蓬勃发展。这篇文章的目的是提供一个全面的最新发展,在多个现实生活中的应用多武装土匪。具体来说,我们将介绍常见的基于mab的应用分类,并总结每个领域的最新进展。此外,我们确定了重要的当前趋势,并提供了与这个令人兴奋和快速增长的领域的未来相关的新视角

满200的话拉您进2群,加我微信 jjnuxjp5x

1介绍

序列决策问题在各种实际应用中经常遇到,从临床试验[Durand et al., 2018]到推荐系统[Mary et al., 2015]和异常检测[Ding et al., 2019]。通常,每个操作都有一个附加信息或上下文(如用户画像),而反馈或奖励仅限于所选择的动作。例如,在临床试验中[Durand等,2018;上下文是患者的医疗记录(如:健康状况、家族史等),动作对应于正在被权衡的治疗方案,奖励代表所给建议的治疗结果(如:成功或失败)。在这种情况下,为取得较大的长期累积回报,我们需在探索(例如,尝试一种新药)和开发(选择已知药物)之间找到一个好的平衡。
这种固有的探索与利用之间的权衡存在于许多顺序决策问题中,传统上被表述为多武装强盗(MAB)问题:给定K个可能的行动(或”老虎机手臂“),每个都与一个固定但未知的奖励概率分布相关[Lai和Robbins, 1985;Auer等人,2002],在每次迭代(时间点)中,代理选择一个手臂进行游戏并获得奖励,该奖励从各个手臂的概率分布中采样,与之前的操作无关。代理的任务是学习如何选择它的行为,以随时间的推移最大化累积回报。在这种随机设定的基础上,不同研究者提出了不同的解决方案[Lai和Robbins, 1985;奥尔等人,2002;Bouneffouf和F’eraud, 2016]和相应的Bayesian formulation[Agrawal和Goyal, 2012];但是,这些方法没有考虑上下文或代理可用的side information。
一个特别有用的MAB版本是上下文多臂强盗(CMAB),或者简单的上下文强盗问题,在每个迭代中,在选择一个arm之前,代理观察一个n维上下文,或者特征向量。代理使用这个上下文,以及在过去使用的手臂的回报,来选择在当前迭代中使用哪个手臂。随着时间的推移,代理的目标是收集足够多的关于环境向量和奖励之间关系的信息,以便通过观察当前的环境来预测下一个最好的手臂[Langford和Zhang, 2008;Agrawal和Goyal, 2013]。针对一般情况,不同研究者提出了不同算法,包括LINUCB [Li et al., 2010]、Neural Bandit [Allesiardo et al., 2014]和上下文Thompson Sampling (Thompson Sampling, CTS) [Agrawal and Goyal, 2013],在这些算法中,一个行为的预期回报与其上下文之间通常假定存在线性依赖关系。
我们现在将提供一个bandit框架各种应用的广泛概述,包括在多领域(医疗、计算机网络路由、金融等)中解决的实际问题,以及在计算机科学和机器学习中的应用(在这些领域中,bandit方法可以帮助改进监督学习、主动学习和强化学习中的超参数调优和其他重要算法的选择。)

2多臂老虎机的现实应用

随机多臂强盗环境作为一种通用的数学框架,克服了不确定性条件下序列决策的主要困难,即探索与利用exploitation-exploration的两难困境,为现实生活中大多数在线决策问题提供了一种自然的形式。

2.1医疗

临床试验
使用常规的随机治疗分配程序时,很难收集数据来评估动物模型在整个疾病阶段的治疗效果,因为治疗不当可能会导致受试者的健康恶化。[Durand et al., 2018]的作者旨在设计一种自适应分配策略,通过分配更多的样本来探索有前途的治疗方法,从而提高数据收集的效率。他们把这个应用描述为一个上下文强盗问题,并在这个框架中介绍了一种实用的探索和利用算法。这项工作依赖于使用相同数量的信息对治疗方案进行比较。通过在高斯过程回归中应用子采样,并将子采样策略扩展到上下文环境强盗设置。
Warfarin是世界上应用最广泛的口服抗凝剂;然而,正确地给药仍然是一个重大的挑战,因为由于各种临床、人口统计学和遗传因素,适当的剂量在个体之间可能是高度可变的。目前,医生采用的是固定剂量策略:他们每天给病人5毫克(大多数病人的适当剂量),然后通过跟踪病人的抗凝血水平,在几周内慢慢调整剂量。然而,不正确的初始剂量可能导致严重的不良后果,如中风(如果初始剂量过低)或内出血(如果初始剂量过高)。因此,[Bastani and Bayati, 2015]的作者通过将问题建模为一个具有高维协变量的多臂强盗来解决患者学习和分配适当初始剂量的问题,并提出了一种基于LASSO估计器的新型高效强盗算法

大脑和行为建模
[Bouneffouf et al., 2017a]的作者从健康对照组和不同精神障碍患者的人类决策行为研究中获得灵感,提出了多臂强盗问题的一般参数框架,该框架扩展了标准的汤普森抽样方法,将与包括帕金森病、注意缺陷多动障碍(ADHD)、上瘾、慢性疼痛和阿尔茨海默病在内的多种神经和精神疾病相关的奖赏处理偏差纳入其中。他们从行为建模的角度实证地证明,他们的参数化框架可以被看作是一个统一的计算模型的第一步,该模型捕获了跨越多种精神状态的奖赏处理异常。

2.2金融
近年来,在机器学习和定量金融的交叉领域,顺序投资组合选择已经成为人们越来越感兴趣的焦点。以累积报酬最大化为目标的勘探和开发之间的权衡是投资组合选择问题的自然公式。在[Shen et al., 2015]中,作者提出了一个强盗算法,通过利用多个武器之间的相关性来进行在线投资组合选择。摘要通过构造多资产的正交投资组合,并将其方法与上限置信约束的强盗框架相结合,根据风险调整后的收益函数,推导出代表被动投资和主动投资组合的最优投资组合策略。在[霍和傅,2017]中,作者将风险意识融入到经典的多臂强盗设置中,并引入了一种新的投资组合构建算法。通过根据金融市场的拓扑结构对资产进行过滤,将最优的多臂强盗策略与一致的风险度量最小化相结合,实现了风险与收益的平衡。

2.3动态定价
在线零售商公司经常面临动态定价问题:公司必须决定其多种产品的实时价格。公司可以进行价格实验(经常改变价格)来了解需求并最大化长期利润。[Misra et al., 2018]的作者提出了一个动态的价格实验政策,其中公司只有不完整的需求信息。在这种一般情况下,作者推导出一种定价算法,该算法平衡了即时利润和未来利润的学习。该方法从经济理论出发,将多臂老虎机与消费者需求的部分识别相结合。与[Misra et al., 2018]类似,[Mueller et al., 2018]的作者考虑采用演化的低维线性需求模型的多维动态多产品定价。结果表明,收益最大化问题可归结为一个带side infomation的在线强盗凸优化问题。该方法将bandit凸优化算法应用于由潜在产品特征所张成(span)的低维投影空间中,同时通过对包含着所观察需求的精心制作的矩阵进行在线奇异值分解来学习该span。

2.4推荐系统
推荐系统常被用来预测用户偏好。然而,项目实施者们常常面临探索-利用exploitation-exploration的困境,因为他们既需利用之前用户选择的感兴趣的item的知识,同时探索用户可能喜欢的新item。[Zhou等人,2017]的作者使用了多武器强盗设置来解决这一挑战,这对具有非常大或无限数量item的大型推荐系统尤其适用(???really?)。他们提出了两种缺乏事先信息时的大规模强盗方法。通过对这些方法的不断探索,我们可以解决推荐系统的冷启动问题。在上下文感知(context-aware)的推荐系统中,大多数现有方法侧重于考虑上下文信息(如时间、位置或社会因素)向用户推荐相关item。然而,这些方法都没有考虑到用户内容演变的问题。在[Bouneffouf等人,2012]中,作者介绍了一种考虑到这种动态演变的算法。它建立在动态勘探/开发的基础上,且能够自适应地平衡E-E,决定哪种情况最适合勘探、哪种最适合开发。在这个意义上,[Bouneffouf, 2014]提出通过强盗问题来研究用户内容的“新鲜度”。他们在本文中介绍了一种基于新鲜度感知的汤普森抽样算法,该算法根据用户的情况风险( according to the user’s risk of the situation)来管理对新文档的推荐。

2.5影响最大化
[Vaswani et al., 2017]中的Autors考虑了社交网络中的影响最大化(influence maximization, IM),这是一个通过选择一组种子用户并将产品暴露给这些种子用户来最大化用户数量的问题。他们提出了一种新的参数化方法,这种方法不仅使框架不受底层扩散模型的影响,而且还提高了从数据中学习的统计效率。研究者给出了一个相应的单调次模代函数(a corresponding monotone, submodular surrogate function),并证明了它是一个很好的逼近原IM目标的方法。
他们还考虑了一种”新晋营销人员希望exploit现有社交网络、同时学习控制信息传播的因素“的情况。为此,他们开发了一个基于LinUCB的强盗算法。[Wen et al., 2017]的作者也研究了社交网络中独立级联模型下的网络影响力最大化问题。具体来说,他们试图在线学习社交网络中最好的种子或影响者,同时反复与之互动。它们解决了组合行动空间的挑战(因为可行影响集的数量随着影响集的最大数量呈指数增长,而反馈有限(仅有被影响部分能被观察到)),他出并分析了IMLinUCB,这是一种计算效率很高的基于ucb的算法。

2.6信息检索
[Losada等,2017]的作者认为,信息检索的迭代选择过程可以自然地建模为上下文强盗问题。Casting document judging作为一种MAB问题,有着非常高效的裁判方法。在这个bandit分配框架下,Losada考虑了固定和非固定模型,并提出了7种新的文件判决方法(5种固定方法和2种非固定变体)。这项比较研究包括现有的基于池的评估方法和现有的元搜索方法。在移动信息检索领域,[Bouneffouf等人,2013]的作者介绍了一种算法,解决了基于上下文的信息检索(CBIR)领域的这一难题。它以动态exploitation和exploration为基础,通过确定 which users situation is most relevant for exploration or exploitation,自适应地平衡exploitation和exploration。在一个精心设计的在线框架内,他们对移动用户进行了评估。

2.7对话系统

对话响应选择
对话响应选择是会话主体自然响应生成的重要步骤。现有的会话模型研究主要关注离线监督学习,使用大量的上下文响应对。在[Liu et al., 2018]中,作者关注对话系统中响应选择的在线学习。他们提出了一个具有非线性回报函数的上下文多武装强盗模型,该模型使用文本的分布式表示进行在线响应选择。双向LSTM用于生成对话上下文和响应的分布式表示,作为上下文强盗的输入。他们提出了一种定制化(customized)的汤普森抽样方法,该方法应用于多项式特征空间来逼近奖励。

积极主动对话系统
在对话系统中,主动性的一个目标是增强会话代理的可用性,使它们能够自己发起会话。虽然对话系统在过去几年变得越来越流行,但是当前的面向任务的对话系统仍然主要是被动的,因为倾向于发起对话的仍然是用户。[Silander and others, 2018] 的作者建议引入上下文老虎机的范式作为主动对话系统的框架。上下文老虎机已经成为仅收到部分反馈的奖励最大化问题的模型选择,因为它非常适合任务描述。该作者还探索了上下文老虎机中记忆的概念,他们提出了两个可微分的记忆模型,作为参数奖励估计函数的一部分。第一个是卷积选择性记忆网络,它使用对过去交互的选择作为决策支持的一部分。第二个模型称为上下文注意记忆网络,它实现了一种可区分的注意机制。目标是将经典的上下文老虎机模型推广到需要以可学习的方式合并和利用时态信息的环境中。

多域对话系统
构建多域对话代理是现代人工智能领域的一个具有挑战性的课题和开放性问题。在对话领域中,编排多个独立训练的对话代理的能力或技能对于创建统一的系统具有特殊的意义。在[Upadhyay et al., 2018]作者研究了在线后验对话编排的任务,他们将后验编排定义为选择技能子集的任务,该技能子集使用从用户输入和个人技能中提取的特征最恰当地回答用户输入。为了考虑与提取技能特征相关的各种成本,他们考虑在skill execution 预算下的在线后验编排。该设置被形式化为Context-Attentive Bandit with Observations(Context-Attentive Bandit的一种变体),并在模拟的非会话和专用会话数据集上对其进行评估。

2.8异常检测
对属性化网络进行异常检测需要找到行为与大多数节点明显偏离的节点。[Ding et al., 2019]的作者通过允许系统主动与人类专家进行交流,对真实异常进行有限数量的查询,来研究交互式环境中的异常检测问题。他们的目标是在给定的预算用完后,最大限度地向人类专家呈现真实的异常。与此同时,他们通过有原则的多武装强盗框架来阐明问题,并开发了一种新的协同上下文强盗算法,该算法在联合框架中明确、无缝建模出节点属性和节点的依赖关系,并处理查询不同类型异常时的探索-利用困境。由自动检测系统预测为欺诈的信用卡交易通常会交给人类专家进行确证。为限制成本,标准做法是只选择最可疑的交易进行调查。[Soemers et al., 2018]的作者声称,为了适应行为的变化,exploration和exploitation之间的权衡是必要的。exploration包括以改进预测模型为目的的事务选择和调查,而exploitation包括调查发现可疑事务。他们将欺诈交易的成功检测建模为奖励,使用增量回归树学习器创建具有类似预期奖励的交易集群。这使上下文多臂老虎机(CMAB)在exploration-exploitation权衡中得以发挥作用。

2.9电信
在[Boldrini et al., 2018]中,作者用多武装强盗模型描述多无线电接入技术(multi-Radio Access Technology, multi-RAT)设备的最佳无线网络选择问题,其目标是最大化最终用户感知的质量。该模型从两个方面对经典的MAB进行了扩展。首先,它预见了两种不同的行为:to measure and to use;其次,它允许动作跨越多个时间步长。此外,论文还介绍了利用MAB模型的较高灵活性而设计的两种新算法。第一个是Measure -use-UCB1,它来自于UCB1算法,第二个是Measure with logicinterval,它是为新模型设计的,以便在利用new measure action的同时,积极使用当前最好的arm。[Kerkouche等人,2018]的作者论证了优化远程广域网技术性能的可能性。作者建议节点采用多武装强盗算法来选择通信参数(扩展因子和发射功率)。实验结果表明,这种学习方法比基于信噪比和干扰比的自适应数据率算法能更好地处理能量消耗和丢包之间的权衡。

2.10老虎机在现实生活中的应用:总结和未来展望

Table 1: Bandit for Real Life Application

由上图可知,非平稳bandit并没有在医疗应用中使用,因为在做出治疗决策的过程中,环境中可能没有发生显著的变化,即患者的状态没有变化;如果真发生了明显转换,最好使用强化学习而不是非平稳bandit来建模显然,在其他领域,非平稳强盗是一个更合适的设置(但似乎这种设置在医疗保健领域还没有太多的研究):例如,异常检测是一个可以使用非平稳上下文bandit的领域,因为在这种情况下,异常可能是对抗性的,这意味着应用到这种设置的任何bandit都应该具有某种漂移条件,以适应新的攻击类型。另一个观察是,在现有研究中,没有一项工作尝试开发出可以同时解决这些不同任务的算法,或者将一个领域中获得的知识应用到另一个领域,从而开辟在bandit环境中进行多任务和迁移学习的研究方向。此外,考虑到bandit问题的在线性质,continuous learning或lifelong learning将是一个自然的future work,它们将之前所学模型应用到新任务中,同时仍记得如何执行之前的任务,从而避免“灾难性遗忘”的问题。

3 Bandit for Better Machine Learning

3.1算法选择

Algorithm selection is typically based on models of algorithm performance,这些模型是在单独的离线训练序列中学习的,代价可能非常昂贵。在最近的工作中,研究者们采用了一种在线方法,其中performance model被迭代更新,并用于指导对一系列问题实例的选择。由此产生的exploration-exploitation权衡被表示为一个有专家建议的bandit问题,我们可以使用现有的解决方案来解决这个问题,但这需要使用算法运行次数的任意bounds( this required using an arbitrary bound on algorithm runtimes),这将使解决方案的最优后悔变得无效。[Gagliolo和Schmidhuber, 2010]则提出了一个更简单的框架,它将算法选择表示为一个仅使用部分信息和未知的损失边界的bandit问题。

3.2 超参数优化

机器学习算法的性能在很大程度上取决于确定一组好的超参数。虽然最近的方法使用贝叶斯优化自适应地选择最优的超参数配置,但它们更侧重于通过适应性资源配置和提前停止加速随机搜索 。[Li et al., 2016]将超参数优化定义为纯粹exploration的非随机无限多臂老虎机问题,其中,作者们将预定义的资源(如迭代、数据样本或特征)分配给随机采样配置。论文针对该框架提出了一种新的算法——超频带算法,并对其理论性质进行了分析,给出了若干理想的regret bound。在此基础上,利用流行的贝叶斯优化方法对一组超参数优化问题进行了超带优化;目前已有研究者注意到,在各种深度学习和基于内核的学习问题上,超频带可以提供比竞争对手多一个数量级的加速。

3.3特征选择

经典的在线监督学习总是向分类器揭示样本的真实标签,与bandit设置不同的是,任何错误的分类结果都是零奖励,只有单个正确的分类产生奖励1。[Wang et al., 2014]的作者研究了在线特征选择问题,其目的是使用epsilon贪心算法仅使用少量的活动特征就能进行准确预测。[Bouneffouf et al., 2017b]的作者利用汤普森抽样算法,通过解决随机bandit环境下带bandit反馈的组合优化问题,进而处理在线特征选择问题。

3.4主动学习的老虎机

在监督分类设置中,给所有训练示例都贴上标签的代价可能很高。主动学习策略通过选择最有用的未标记的实例来获得标记并训练一个预测模型,从而解决了这个问题。待标记实例的选择可以看作输入空间上的exploration-exploitation两难问题。[Bouneffouf et al., 2014]提出的新型主动学习策略则通过将主动学习问题建模为上下文bandit问题来管理这种tradeoff。他们提出了一个名为Active Thompson Sampling (ATS)的顺序算法,在每一轮中,该算法在池中分配一个抽样分布,从这个分布中抽取一个点,并查询oracle(先知)以获得这个抽样点标签。[Ganti和Gray, 2013]的作者还提出了一种基于多臂老虎机且基于池的主动学习算法以解决二进制分类问题。他们利用低可信界、多臂老虎机文献中的自和谐正则化等思想来设计算法。在每一轮中,该算法在池中分配一个抽样分布,从这个分布中抽取一个点,并查询oracle中这个抽样点的标签。

3.5聚类

[Sublime和Lefebvre, 2018]考虑了协作集群,这是一种机器学习范式,涉及使用多种算法一起工作的复杂多视图数据的无监督分析。协同聚类的著名应用包括多视图聚类和分布式数据聚类,其中多种算法交换信息以相互改进。多视图和协作集群的一个关键问题是评估哪些协作是有益/有害的。针对这个问题已经提出了许多解决方案,所有的解决方案都得出结论:除非两个模型非常接近,否则很难提前预测协作结果。为解决这个问题,[Sublime and Lefebvre, 2018]的作者提出了一种基于非随机多臂老虎机原理的协作对等聚类算法,实时评估哪些算法或视图能够带来有用的信息。

3.6强化学习

自主的网络物理系统在我们的生活中扮演着重要的角色。为了确保agents的行为与其所处社会的价值观相一致,我们必须发展技术,使这些agents不仅能在一个环境中获得最大回报,还能够学习和遵循社会假定的隐含约束。在[Noothigattu et al., 2018]中,作者研究了一种环境,在该环境中,agents可以观察到社会成员的行为轨迹,但无法访问导致观察到的行为的明确约束集。相反,反向强化学习用于学习这些约束,然后在采取行动时,通过使用基于上下文的协调器在两种策略(基于约束和基于环境奖励)之间挑一个contextually-appropriate的选择,并将这些约束与可能的正交值函数结合起来。上下文bandit协调器以新颖的方式使agents混合使用各种策略,从报酬最大化策略或受约束策略中采取最佳操作。The [Laroche and F ' eraud, 2017]解决了在线RL算法选择的问题。论文给出了一个元算法,它由多个非策略RL算法组成,用于在每条新轨迹的起点确定下一条轨迹的行为由投资组合中的哪种算法控制,以使最大化累积回报。另外,现在还有一种新的元算法—— Epochal Stochastic Bandit Algorithm Selection,它的原则是:在每个epoch中,冻结住策略的更新,并让重启动的随机bandit负责算法的选择。

3.7用于机器学习的bandit

表2总结了用于解决上述机器学习问题的bandit问题的类型。我们可以看到上下文bandit并没有用于特征选择或超参数优化。这一发现为今后的工作指明了方向,我们可以尝试将side infomation用于特征选择。此外,在这些问题设置中研究者很少考虑非稳态bandit,这也暗示了当前工作的可能扩展。例如,当环境不断变化时,非平稳的上下文bandit可能在非平稳的特征选择设置中很有用,在这种情况下,找到正确的特征是依赖于时间和上下文的。我们的其他主要观察是,每种技术一次只能解决一个机器学习问题;因此,是否可以考虑开发一个bandit设置和算法来同时解决多个机器学习问题以及在这个设置中是否可以实现迁移和连续学习?一种解决方案是在一个组合bandit框架中对所有这些问题进行建模,其中bandit算法将在每次迭代中为每个问题找到最优解决方案;因此,组合bandit可以进一步用作推进自动化机器学习的工具。

Table 2: Bandit in Machine Learning

4结论

在这篇文章中,我们回顾了最近关于多臂强盗和上下文强盗在现实生活领域和自动机器学习中的应用的一些最著名的工作。我们有条理地(表1和表2)总结了各种现有的应用,按强盗设置的类型分类,并讨论了在每个领域中使用强盗技术的优点。我们简要概述了几个重要的开放问题和有前景的未来扩展。 综上所述,目前,bandit框架(包括multi-arm和context bandit)是非常活跃和有前途的研究领域,每年都会出现多种新的技术和应用。我们希望这些调查能帮助读者更好地理解这个令人兴奋的领域,并更好地了解它的显著进步和未来前景。

参考文献:

Bouneffouf, Djallel, and Irina Rish. "A survey on practical applications of multi-armed and contextual bandits."arXiv preprint arXiv:1904.10040(2019).
Chen, Wei, Yajun Wang, and Yang Yuan. "Combinatorial multi-armed bandit: General framework and applications."International Conference on Machine Learning. 2013.
Mahajan, Aditya, and Demosthenis Teneketzis. "Multi-armed bandit problems."Foundations and applications of sensor management. Springer, Boston, MA, 2008. 121-151.
Qin, Lijing, Shouyuan Chen, and Xiaoyan Zhu. "Contextual combinatorial bandit and its application on diversified online recommendation."Proceedings of the 2014 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics, 2014.

编辑于 2021-03-06 17:02