May, 2023

参数化马尔可夫决策过程下的汤普森采样

PDF
TL;DR本论文研究了参数化马尔可夫决策过程（Parameterized MDPs），使用贝叶斯推理学习其中的关键参数，提出了一组假设，对 Thompson 抽样算法保证了一个渐进最优的预期后悔边界（Asymptotically optimal expected regret bound）为 $O (T^{-1})$，并且可以轻松地验证在许多问题类别中，如排队、库存控制和动态定价中的应用。
parameterized mdpsbayesian inferencethompson samplingregret bounddynamic pricing
发现论文，激发创造
  • 用 Thompson 取样算法学习参数化的马尔可夫决策过程

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

    Jun, 2014

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

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

    Sep, 2017

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

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

    May, 2024

  • 计数无限状态空间马尔可夫决策过程的贝叶斯学习最优策略

    该研究提出了一种基于贝叶斯思想和汤普森抽样的算法来解决优化数量可数的马尔可夫决策过程的控制问题，在未知参数和固定先验分布的情况下，能够稳定地获得近似最优解，适用于诸如通信网络和计算系统等不确定动力系统以及一些数量可数的排队模型。

    Jun, 2023

  • 广义汤普森抽样用于顺序决策和因果推断

    该论文讨论了 Thompson 采样如何是贝叶斯策略不确定性建模的自然后果、如何用于多个自适应智能体之间的交互研究和如何应用于推断环境中的因果关系等，在自适应顺序决策和因果推断问题中可能不仅是有用的启发式方法，而且也是一个原则性的方法。

    Mar, 2013

  • 基于信息论的噪声上下文随机赌博机的汤普森抽样算法的遗憾分析

    我们研究了一种随机情境线性赌博机问题，代理人通过一个未知噪声参数的噪声信道观察到真实情境的有噪声、损坏的版本。我们的目标是设计一种行动策略，可以近似一个能够获取奖励模型、信道参数以及根据观察到的有噪声情境从真实情境得到预测分布的神谕的行动策略。我们在贝叶斯框架下引入了一种基于高斯情境噪声的汤普森采样算法。采用信息论分析，对于神谕的行动策略，我们证明了该算法的贝叶斯遗憾。我们还将这个问题扩展到当代理人在接收到奖励之后，以一定延迟观察到真实情境的情景，并展示了延迟真实情境会导致更低的贝叶斯遗憾。最后，我们通过与基准算法进行实证研究，展示了所提出算法的性能。

    Jan, 2024

  • 汤普森抽样的信息论分析

    本文提供一种信息论分析 Thompson 采样的方式，适用于许多在线优化问题，其中决策者必须从部分反馈中学习，分析继承信息论的简单性和优雅性，并导致与最优行动分布熵成比例的后悔界限，这加强了现有的成果并揭示了信息如何提高性能。

    Mar, 2014

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

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

    Feb, 2024

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

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

    May, 2017

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

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

    Aug, 2022