专栏首页arxiv.org翻译专栏可微分线性带状算法(CS LG)
原创

可微分线性带状算法(CS LG)

上置信界(Upper Confidence Bound,UCB)可以说是线性多臂强盗问题中最常用的方法。虽然概念和计算简单,但这种方法高度依赖置信界,如果这些界线设置不当,就无法得出最优的探索——开发。在文献中,置信界通常是基于对报酬分布的假设,如次高斯性,从集中不等式中得出。然而这些假设的有效性在实践中是未知的。在这项工作中,我们旨在以数据驱动的方式学习置信度边界,使其适应实际问题结构。具体来说,注意到现有的 UCB 类型的算法在置信度边界方面是不可分的,我们首先提出了一种新型的可分线性匪徒算法。然后,我们引入了一个梯度估计器,使得置信度边界可以通过梯度上升来学习。理论上,我们表明,所提出的算法实现了 T 轮的 \tilde{\mathcal{O}}(\hatβ\sqrt{dT}) 上界,其中 d 是手臂特征的维度,\hatβ 是学习到的置信度边界大小。实证结果表明,\hatβ 明显小于其理论上界,且提出的算法在模拟和真实世界数据集上都优于基线算法。

原文题目:Differentiable Linear Bandit Algorithm

原文:Upper Confidence Bound (UCB) is arguably the most commonly used method for linear multi-arm bandit problems. While conceptually and computationally simple, this method highly relies on the confidence bounds, failing to strike the optimal exploration-exploitation if these bounds are not properly set. In the literature, confidence bounds are typically derived from concentration inequalities based on assumptions on the reward distribution, e.g., sub-Gaussianity. The validity of these assumptions however is unknown in practice. In this work, we aim at learning the confidence bound in a data-driven fashion, making it adaptive to the actual problem structure. Specifically, noting that existing UCB-typed algorithms are not differentiable with respect to confidence bound, we first propose a novel differentiable linear bandit algorithm. Then, we introduce a gradient estimator, which allows the confidence bound to be learned via gradient ascent. Theoretically, we show that the proposed algorithm achieves a \tilde{\mathcal{O}}(\hatβ\sqrt{dT}) upper bound of T-round regret, where d is the dimension of arm features and \hatβ is the learned size of confidence bound. Empirical results show that \hatβ is significantly smaller than its theoretical upper bound and proposed algorithms outperforms baseline ones on both simulated and real-world datasets.

原文作者:Kaige Yang, Laura Toni

原文地址:https://arxiv.org/abs/2006.03000

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 微分私有可分解子模最大化(CS LG)

    我们研究可分解的子模函数的微分私有约束最大化问题。如果一个子模函数采取子模函数之和的形式,则该子模函数是可分解的。一个单调的、可分解的子模函数在基数约束下最大化...

    刘持诚
  • 使用可微分编程进行灵活的统计建模(CS LG)

    可微分编程作为一种便于利用计算机程序梯度的范式,最近受到许多关注。迄今为止,虽然相应的基于梯度的灵活优化方法主要用于深度学习或用建模组件丰富后者,但我们希望证明...

    毛艺漩8078803
  • 格林函数的协方差矩阵及其在机器学习中的应用(CS LG)

    本文提出并实现了一种基于格林函数理论的回归算法。本文首先研究了二阶线性常微分方程Dirichlet边值问题的Green函数,它是适合Hilbert空间的再生核。...

    Elva
  • Plan2Vec: 基于潜在计划的无监督表示学习(CS LG)

    在本文中,我们介绍了 Plan2Vec,一种无监督表示学习方法,它的灵感来自于强化学习。Plan2Vec 使用近邻距离在图像数据集上构建一个加权图,然后通过提炼...

    刘持诚
  • 5.29 VR扫描:索尼发布1600×1200分辨率OLED微型显示屏;DigiLens发布两层AR波导显示器

    VRPinea
  • 基于模型的强化学习中的Delta模式网络(CS LG)

    这项工作致力于解决人工智能的未解决问题-学习迁移的效率低下。在强化学习领域中用于解决此问题的机制之一是基于模型的方法。 在本文中,我们正在扩展模式网络方法,该方...

    小童
  • 深层神经网络输入输出层在对抗性防御中的作用探讨(CS LG)

    深层神经网络是一种在前景预测、计算机视觉、语言处理等领域都取得了最新成果的学习模型,然而,已有研究表明,存在某些特定输入不会误导人类,但可能会完全误导模型,这些...

    Elva
  • 音乐手势机器学习(CS lg)

    本文概述了应用于音乐手势分析和设计的交互式机器学习(IML)技术。我们通过探索IML技术的捕捉,分析,及其应用于人体手势的相关主要挑战和需求,以实现声音合成系统...

    木樾233
  • 因果关系和批量强化学习:未知领域中计划的补充方法(CS LG)

    强化学习算法在在线学习环境中取得了巨大的成功。但是,这些成功依赖于算法Agent与其环境之间的低风险交互。在许多可能使用RL的环境中,例如医疗保健和自动驾驶,大...

    小童
  • 使用预测的随机梯度上升学习优化环境(CS LG)

    在这项工作中,我们将直接策略搜索算法概括为一种称为“直接环境搜索”的算法,该算法具有(预测的随机)梯度上升(DESGA)。 后者可用于共同学习强化学习(RL)环...

    小童
  • 通过集成学习检测伪造评论(CS LG)

    客户通过使用在线评论来分享他们的经验来表示他们对消费产品的满意度。 几种基于机器学习的方法可以自动检测欺骗性和虚假评论。最近,有研究报告了集成学习方法与传统机器...

    小童
  • Android自定义View--自己撸一个柱状图也没那么难

    版权声明:本文为博主原创文章,转载请标明出处。 https://blog.csdn.net/lyhhj/article/details/53...

    Hankkin
  • 用一般值函数近似法进行高效的强化学习(CS LG)

    值函数近似已经在强化学习(RL)中取得了惊人的经验性成功。然而,尽管最近在发展线性函数近似的 RL 理论方面取得了一些进展,但我们对一般函数近似方案的理解仍有很...

    刘持诚
  • PHOTON——用于快速机器学习模型开发的Python API(CS-LG)

    本文介绍PHOTON的实现和使用,PHOTON是一个高级的Python API,旨在简化和加速机器学习模型的开发过程。它可以设计基本的和高级的机器学习流水线结构...

    Elva
  • GDC 2017完美收官,但星辰大海尚在远方

    VRPinea
  • 异步 Q-Learning 的样本复杂度:更敏锐的分析和方差减少技术(CS LG)

    异步 Q-learning 的目的是基于行为策略诱导的马尔科夫样本的单一轨迹,学习马尔科夫决策过程(MDP)的最优行动值函数(或Q-function)。专注于一...

    刘持诚
  • 形状变换在地震、风浪数据时间序列分类中的应用(CS LG)

    由于对大量工程结构(包括建筑物、桥梁、塔楼和海上平台等)的长期健康监测,使用时间序列分类法从大型数据库中自主检测所需事件,在土木工程中越来越重要。在这种情况下,...

    刘持诚
  • 基于多目标优化模型的不完全数据集机器学习(CS LG)

    机器学习技术已经发展到从完整的数据中学习。当数据集中存在缺失值时,应通过删除具有缺失值或插补的数据点来分别对不完整的数据进行预处理。在本文中,我们提出了一种在线...

    毛艺漩8078803
  • 一种不确定性量化的糖尿病视网膜病变分类的主动学习方法(CS LG)

    近年来,深度学习(DL)技术已在不同的医学成像任务上提供了最先进的性能。然而,由于所涉及的时间限制以及专家注释(例如放射线医生)的可用性,高质量注释医学数据的可...

    毛艺漩8078803

扫码关注云+社区

领取腾讯云代金券