学习未知马尔可夫决策过程:一种汤普森抽样方法
提出了一种基于后验采样的算法,应用于具有有限但未知直径的 Markov 决策过程中,证明了近最优的最坏情况遗憾上界。这种方法通过证明 Dirichlet 分布的反集中性,可能具有独立研究价值,并将总奖励与最优无限时维度折扣的平均奖励策略的总期望奖励在时间结构 $T$ 中呈现出紧密的匹配。
May, 2017
本研究提出了一种基于 Thompson 取样的强化学习算法,针对参数化的 Markov 决策过程,通过贝叶斯方法进行训练,在一般参数空间的先验分布中可以获得频率挽回上限。结果显示,选择次优动作的时间段的数量随时间对数成比例增长,这取决于参数空间的 Kullback-Leibler 几何信息复杂度。
Jun, 2014
该研究提出了一种基于贝叶斯思想和汤普森抽样的算法来解决优化数量可数的马尔可夫决策过程的控制问题,在未知参数和固定先验分布的情况下,能够稳定地获得近似最优解,适用于诸如通信网络和计算系统等不确定动力系统以及一些数量可数的排队模型。
Jun, 2023
我们通过建立一个马尔可夫决策过程模型,研究一种名为汤普森采样的采样算法的渐近行为。我们展示了标准(期望)遗憾可能呈超线性增长,并且不能很好地捕捉到在具有非平凡状态演进的现实情况下的学习概念。通过分解标准(期望)遗憾,我们提出了一种新的指标,称为期望剩余遗憾,它忽略了过去动作的不可变后果,而是测量了当前时期后的最优奖励的遗憾。我们表明,汤普森采样算法的期望剩余遗憾上界由一个指数级快速收敛于 0 的项给定。我们给出了汤普森采样的后验采样误差收敛于 0 的条件,并且引入了期望剩余遗憾的概率版本并给出了其收敛于 0 的条件。因此,我们提供了一个适用于采样算法的学习概念,在比以前考虑的更广泛的情况下将非常有用。
May, 2024
引入 Thompson 采样算法应对 LQ 控制问题的未知系统参数,该算法被称为具有动态阶段的 Thompson 采样(TSDE),其中包括两种停止准则来确定动态阶段的长度并呈现出具有 O (sqrt (T)) 的期望后悔值的性质,加入重启计划也展示了对于模型参数的时间变化具有稳健性。
Sep, 2017
本论文研究了参数化马尔可夫决策过程(Parameterized MDPs),使用贝叶斯推理学习其中的关键参数,提出了一组假设,对 Thompson 抽样算法保证了一个渐进最优的预期后悔边界(Asymptotically optimal expected regret bound)为 $O (T^{-1})$,并且可以轻松地验证在许多问题类别中,如排队、库存控制和动态定价中的应用。
May, 2023
本研究提出了一种政策优化算法,用于处理成本约束下的无限时间跨度平均奖励马尔可夫决策过程中的后悔最小化问题,该算法在符合一定条件的 MDP 下具有较低的后悔度和约束违反率,并将其推广到弱通信 MDP 领域,为该领域提供了复杂度可行的算法。
Jan, 2022
基于后验抽样的新算法在无限时间视野下的有约束马尔科夫决策过程学习中实现了几乎最优的悔恨界限,并在实践中相比现有算法具有优势。
May, 2024