折扣马尔可夫决策过程的 PAC 上界
本文提出简单算法来解决在短期内实现理论驱动的探索方法和实际需求之间的纠葛,并通过理论分析和数字示例展示所提出的放宽条件的好处,同时维持任何时候的误差边界和平均损失边界,并且适用于贝叶斯和非贝叶斯方法。
Apr, 2016
本文使用生成模型证明了在马尔可夫决策过程中,基于值迭代算法的样本复杂度 PAC 上限为 O (Nlog (N/δ)/((1-γ)³ε²)),其中 N 为状态 - 动作对的数量,γ 为折扣因子,ε 表示动作价值函数的 ε- 最优估计,δ 为概率。同时证明了在任何强化学习算法中,基于每个状态 - 动作对估计最优动作值函数的样本复杂度下限为 Θ(Nlog (N/δ)/((1-γ)³ε²)),该上限和下限在 N,ε、δ、1/(1-γ) 方面匹配。
Jun, 2012
此篇论文探讨了在未知、随机环境中,通过建立模型、构造符合某些临时逻辑规则要求的 MDP,并通过 PAC-MDP 的方法,利用数据、空间和时间进行迭代更新,得到了一个在一定条件下接近最优的策略,从而达到在给定规则下最大化概率的目的。
Apr, 2014
该研究提出了一种基于贝叶斯思想和汤普森抽样的算法来解决优化数量可数的马尔可夫决策过程的控制问题,在未知参数和固定先验分布的情况下,能够稳定地获得近似最优解,适用于诸如通信网络和计算系统等不确定动力系统以及一些数量可数的排队模型。
Jun, 2023
针对有限时间表格 MDPs 的后悔最小化问题,我们推导了一个新颖的渐近问题相关下限。尽管与先前的工作类似(例如针对遍历 MDPs 的工作),这个下限是一个优化问题的解,但我们的推导表明需要在状态 - 动作对的访问分布上附加一个额外的约束条件,以明确考虑 MDP 的动态性。通过一系列示例,我们提供了我们下界的表征,说明不同的 MDP 可能具有显着不同的复杂性。
Jun, 2021
这篇文章提出了第一个关于任何表格化情节型马尔可夫决策过程(MDP)中需要样本复杂性的 PAC 识别近似最优策略的实例相关下界,并证明了 PEDEL 算法的样本复杂度接近这个下界。鉴于 PEDEL 计算的复杂性,我们提出了一个关于能否使用计算高效的算法达到我们的下界的开放性问题。
Oct, 2023
设计控制策略时,我们考虑在只有近似模型的情况下对无限时域折扣成本马尔可夫决策过程进行控制。对于在原始模型中使用近似模型的最优策略的性能如何,在原始模型中使用的近似模型的价值函数与原始模型的最优价值函数之间的差异的加权范数提供了上界的边界。通过考虑每步成本的仿射变换,我们进一步提供了可能更紧密的上界,并且上界明确取决于原始模型和近似模型之间成本函数和状态转移核之间的加权距离。我们提供示例以说明我们的结果。
Feb, 2024
本文针对局限于有限状态下的马尔可夫决策过程,对于包括折扣和平均成本标准在内的情况进行了研究,获得了近似最优策略,使用预处理步骤将操作空间有限近似,可以使用众所周知的算法计算近似最优政策。
Mar, 2015