Mar, 2020

绕开怪物：一种更快、更简单的实现环境下上下文二项式算法

PDF
TL;DR该论文考虑了具有普适性假设的（随机性）上下文赌博问题，设计了一种快速、简单的算法，在所有 $T$ 回合中通过对离线回归神谕的 $logT$ 次调用实现了统计优化遗憾。我们的结果提供了第一个从上下文赌徒到离线回归的通用和最优化简化，解决了上下文赌徒文献中的一个重要开放问题。我们的结果表明，离线回归中的任何进展都将立即在上下文赌客中进行统计和计算翻译。
contextual banditstochastic processregressionalgorithmreward
发现论文，激发创造
  • 驯服怪兽：一种快速简单的上下文赌博算法

    本文提出了一种在线学习算法，具有上下文匹配学习问题中的统计最优保证，并通过少量的机器学习调用来完成，而且在性能方面非常优秀。

    Feb, 2014

  • 通过离线神谕在具有多个类别的情境下选择最优模型的方法

    本研究提出了一种新的算法，用于解决上下文 Bandit 问题中的模型选择问题，该算法通过离线模型选择预言机的方式平衡偏差 - 方差交换和探索 - 利用交换，并具有与回归模型选择相同的计算要求。

    Jun, 2021

  • 超越 ucb: 具有回归预测器的最优和高效上下文臂算法

    本文提出了一种将上下文强化学习转化为在线回归问题的算法；该算法可以在泛型函数类上实现最小化风险，并且与以前的结果相比，它不需要任何分布假设，即使在敌对性上下文的情况下也可以工作。

    Feb, 2020

  • 基于 oracle 的对抗性情境赌博算法的改进遗憾界

    提出了一种基于 oracle 的算法来应对敌对情境下的赌博问题，该算法在访问离线优化 Oracle 并且享有 $O ((KT)^{\frac {2}{3}}(\log N)^{\frac {1}{3}})$ 的遗憾度的情况下是计算有效的，其中 K 是操作的数量，T 是迭代次数，N 是基线策略的数量。

    Jun, 2016

  • 具备回归神谕的实用上下文强化学习

    本研究提出了一种新的技术，将可实现性方法的经验和计算优势与不可知方法的灵活性相结合，借助回归预测器的可用性来进行算法优化，实现了任何分布假设下出色的表现。

    Mar, 2018

  • 利用离线回归预测器适应上下文 Bandit 中的错误规格化

    提出了一种简单的上下文 Bandit 算法族，该算法族可以通过当有证据表明错配错误导致遗憾增加时返回良好的安全策略来适应错配误差，而不需要像在线或约束回归神谕一样更健壮的神谕。

    Feb, 2021

  • 上下文臂针对高效优化学习

    本文介绍了一种在线学习算法，它使用了一种基于代价敏感分类器的方法，并实现了最优遗憾率，与之前的算法相比，具有指数级别的运行速度优势，并且在反馈延迟方面实现了加性遗憾而非乘性遗憾。

    Jun, 2011

  • 一种改进的用于 Oracle-Efficient Adversarial Contextual Bandits 的松弛方法

    我们提出了一种对抗情境下上下文弛豫的方法，其中上下文是从已知分布中顺序独立抽取的，并且成本序列由在线对手选择。我们的算法在每一轮最多对离线优化预言机进行 O (K) 次调用，有一个遗憾界限为 O (T^（2/3）(Klog (|Pi|))^（1/3）)，这是首次改进了 Syrgkanis 等人在 2016 年 NeurIPS 会议上获得的 O ((TK)^（2/3）(log (|Pi|))^（1/3）) 最佳界限，也是第一次与 Langford 和 Zhang 在 2007 年 NeurIPS 会议上为随机情况获得的原始界限相匹配。

    Oct, 2023

  • 可预测奖励的情境决策学习

    本研究探讨了一种基于可实现性假设下的上下文强化学习问题，并提出了一种新算法 —— 回归器消除，证明了其在保证可实现性前提下，也具有与不可实现性假设情况相似的遗憾率；同时在任意一组策略的情况下，我们证明了本算法具有恒定遗憾，相对于之前的方法而言。

    Feb, 2012

  • 绕过模拟器：近似最优的对抗线性情境赌博机

    通过实现无需模拟器的多项式时间算法，我们在拥有线性上界误差的情况下，提高了对抗性线性上下文赌博问题的表现，实现了近乎优化的后悔度，同时保持了计算效率。

    Sep, 2023