基于 Thompson Sampling 的未知线性系统学习控制
本文提出了一种基于贝叶斯的 Thompson Sampling 加持的动态时段算法 (TSDE),尝试在无限的时间尺度内解决了一个学习未知 MDP 的问题,实现了很好的性能并达到了理论界限。
Sep, 2017
我们提出了一种近似的 Thompson 采样算法,用于学习具有改进贝叶斯后悔界限为 O (√T) 的线性二次调节器(LQR)。我们的方法利用了经过细致设计的 Langevin 动力学和简单的激励机制。我们展示了激励信号随时间增长引起预条件器的最小特征值增长,从而加速近似后验采样过程。此外,我们识别出由我们的算法生成的近似后验的非平凡的浓度特性。这些特性使我们能够在不依赖于文献中常用的对参数集的不切实际的限制假设的情况下,束缚系统状态的矩,并获得 O (√T) 的后悔界限。
May, 2024
本文研究了在未知奖励分布下使用 Thompson 采样算法来解决不断变化的赌博机问题,证明了一种子线性的,O (sqrt (T) log T) 的遗憾上限,并将算法测试在了一个动态信道接入问题的模拟中,实证结果与理论上限一致。
Oct, 2019
本研究提出了一种基于 Thompson 取样的强化学习算法,针对参数化的 Markov 决策过程,通过贝叶斯方法进行训练,在一般参数空间的先验分布中可以获得频率挽回上限。结果显示,选择次优动作的时间段的数量随时间对数成比例增长,这取决于参数空间的 Kullback-Leibler 几何信息复杂度。
Jun, 2014
在随机线性赌博机问题中,我们为 Thompson 采样的后悔证明提供了一种替代证明方法。我们展示了后悔与目标函数的敏感性有关,并且选取与乐观参数相关的最优臂可以控制后悔,在具有固定概率为乐观的采样分布下来看,Thompson 采样可以作为一种通用的随机化算法。我们还证明了这个理论可以轻松应用到正则化线性优化和广义线性模型问题中。
Nov, 2016
我们研究了基于 Thompson Sampling 的有界奖励随机赌博算法。为了解决现有的与高斯先验的 Thompson Sampling 相关的问题相关后悔界限在 T≤288e^64 时是虚无的问题,我们导出了一个更实用的界限,将主要项的系数从 288e^64 缩小到 1270。此外,我们提出了两种参数化的 Thompson Sampling 算法:带有模型聚合的 TS-MA-α 和带有时间战斗的 TS-TD-α,其中 α∈[0,1] 控制效用与计算之间的权衡。这两种算法都可以实现 O (Kln^(α+1)(T)/Δ) 的后悔界限,其中 K 是臂数量,T 是有限学习时段,Δ 表示拉动次优臂时的单轮性能损失。
May, 2024
我们通过建立一个马尔可夫决策过程模型,研究一种名为汤普森采样的采样算法的渐近行为。我们展示了标准(期望)遗憾可能呈超线性增长,并且不能很好地捕捉到在具有非平凡状态演进的现实情况下的学习概念。通过分解标准(期望)遗憾,我们提出了一种新的指标,称为期望剩余遗憾,它忽略了过去动作的不可变后果,而是测量了当前时期后的最优奖励的遗憾。我们表明,汤普森采样算法的期望剩余遗憾上界由一个指数级快速收敛于 0 的项给定。我们给出了汤普森采样的后验采样误差收敛于 0 的条件,并且引入了期望剩余遗憾的概率版本并给出了其收敛于 0 的条件。因此,我们提供了一个适用于采样算法的学习概念,在比以前考虑的更广泛的情况下将非常有用。
May, 2024
这篇论文提出了一个算法框架,结合了不同的近似抽样方法和最近提出的 Feel-Good Thompson Sampling (FGTS) 方法,在线性 MDPs 中应用时,我们的遗憾分析得到了关于维度的最好依赖关系,超过了现有的随机算法。在一些需要进行深度探索的任务中,我们提出的将 FGTS 和近似抽样相结合的算法与其他强基准相比表现显著地更好。在 Atari 57 套件的几个具有挑战性的游戏中,我们的算法在性能上要么优于,要么与深度 RL 文献中的其他强基准相当。
Jun, 2024
本研究证明了在多种环境设置下,Thompson 采样在强化学习中的贝叶斯后悔限与性能上界,通过使用一组离散的替代环境简化学习问题,并使用后验一致性对信息比例进行了精细分析,从而导出了时间不均匀强化学习问题中的上界,其中 $H$ 是回合长度,$d_{l_1}$ 是环境空间的 Kolmogorov $l_1$ 维度。接着,我们在各种设置中找到了 $d_{l_1}$ 的具体限制,并讨论了我们的结果是首次出现还是改进了现有技术。
Oct, 2023