May, 2024

无限时间段折现决策过程的汤普森抽样

PDF
TL;DR我们通过建立一个马尔可夫决策过程模型，研究一种名为汤普森采样的采样算法的渐近行为。我们展示了标准（期望）遗憾可能呈超线性增长，并且不能很好地捕捉到在具有非平凡状态演进的现实情况下的学习概念。通过分解标准（期望）遗憾，我们提出了一种新的指标，称为期望剩余遗憾，它忽略了过去动作的不可变后果，而是测量了当前时期后的最优奖励的遗憾。我们表明，汤普森采样算法的期望剩余遗憾上界由一个指数级快速收敛于 0 的项给定。我们给出了汤普森采样的后验采样误差收敛于 0 的条件，并且引入了期望剩余遗憾的概率版本并给出了其收敛于 0 的条件。因此，我们提供了一个适用于采样算法的学习概念，在比以前考虑的更广泛的情况下将非常有用。
markov decision processthompson samplingregretlearningsampling algorithms
发现论文，激发创造
  • 进一步优化 Thompson Sampling 算法的后悔上界

    使用贝叶斯方法的随机算法 Thompson Sampling 在多臂赌博问题中表现显著，本文提供了一种新的悔恨分析方法，同时证明了该算法在期望后悔上的问题特定界限和问题独立界限，方法简单且可适用于更广泛的 contestual bandits 设置。

    Sep, 2012

  • 用 Thompson 取样算法学习参数化的马尔可夫决策过程

    本研究提出了一种基于 Thompson 取样的强化学习算法，针对参数化的 Markov 决策过程，通过贝叶斯方法进行训练，在一般参数空间的先验分布中可以获得频率挽回上限。结果显示，选择次优动作的时间段的数量随时间对数成比例增长，这取决于参数空间的 Kullback-Leibler 几何信息复杂度。

    Jun, 2014

  • 学习未知马尔可夫决策过程：一种汤普森抽样方法

    本文提出了一种基于贝叶斯的 Thompson Sampling 加持的动态时段算法 (TSDE)，尝试在无限的时间尺度内解决了一个学习未知 MDP 的问题，实现了很好的性能并达到了理论界限。

    Sep, 2017

  • 强化学习的后验采样：最坏情况的遗憾界

    提出了一种基于后验采样的算法，应用于具有有限但未知直径的 Markov 决策过程中，证明了近最优的最坏情况遗憾上界。这种方法通过证明 Dirichlet 分布的反集中性，可能具有独立研究价值，并将总奖励与最优无限时维度折扣的平均奖励策略的总期望奖励在时间结构 $T$ 中呈现出紧密的匹配。

    May, 2017

  • Thompson 抽样的无先验和有先验依赖的遗憾界

    研究具有奖励分布先验分布的随机多臂赌博问题，证明 Thompson Sampling 算法在没有先验分布时具有最优的贝叶斯遗憾上界，并在 Bubeck 等人的先验设置下证明了算法的一致界限，并与 Audibert 和 Bubeck [2009] 和 Russo 和 Roy [2013] 的技术方法有关。

    Apr, 2013

  • 时间敏感型贝叶斯优化多臂赌博机学习

    该文研究了在具有时间偏好的情况下的强化学习中，使用折扣累计损失代替累计损失，使用改进的 Thompson 抽样算法得到较强的解决方案。

    Apr, 2017

  • 汤普森采样高效学习控制扩散过程

    通过 Thompson 采样算法学习漂移矩阵严重不确定的扩散过程的最优控制策略，并在实际应用中验证了其优势，这是相关研究的首次尝试。

    Jun, 2022

  • 一种可证明有效的无模型后验采样方法，用于情节强化学习

    本文提出了一种新的模型无关后验采样的公式，适用于更广泛的周期性强化学习问题，并通过新颖的证明技术，展示了在适当条件下，我们的后验采样方法的最坏后果可以与基于优化的方法的最优结果相匹配，尤其是在线性 MDP 设置中，我们的算法产生的遗憾与现有基于后验采样的探索算法相比，随着维度线性增长而非二次依赖。

    Aug, 2022

  • 未知游戏中的无遗憾学习的乐观汤普森抽样

    我们开发了一种基于 Thompson 抽样的算法，利用关于对手行动和奖励结构的信息来应对部分信息和多机构的挑战。在交通路由和雷达感知等实际应用中，我们的方法显著减少了实验预算，与基准算法相比，实现了超过十倍的减少。此外，本研究还引入了乐观 - 无悔框架，将我们提出的方法和领域中现有算法相结合。

    Feb, 2024

  • 多臂赌博问题中汤普森采样的分析

    本文介绍了使用贝叶斯算法的 Thompson Sampling 原则，旨在在序贯决策问题中研究探索 / 开发权衡。该算法在实验证明接近最优，并展现了一些理想的特性，但对该算法的理论认识相当有限。本文第一次展示了 Thompson Sampling 算法在多臂赌博机问题中实现了对数级别的预期遗憾。

    Nov, 2011