在弱通信马尔可夫决策过程中平均奖励Q学习的收敛性
本文提供了一种算法,用于在未知的弱交流Markov决策过程(MDP)中实现最佳的后悔率。该算法通过利用最优偏差向量跨度的正则化,在每个周期中选择一个策略。对于具有S个状态和A个动作的MDP,其最优偏差向量的跨度受到H的限制,我们显示出~O(HSpAT)的后悔界限。我们还将其跨度与MDP相关的各种直径类似的量联系起来,证明了我们的结果如何改善先前的后悔限制。
May, 2012
提出了一种基于EE-QL,结合浓度逼近和无模型弱交流 MDPs 的无模型学习算法,实现了与最佳已知基于模型算法相似的学习速度。
Jun, 2020
本研究提出了一种政策优化算法,用于处理成本约束下的无限时间跨度平均奖励马尔可夫决策过程中的后悔最小化问题,该算法在符合一定条件的MDP下具有较低的后悔度和约束违反率,并将其推广到弱通信MDP领域,为该领域提供了复杂度可行的算法。
Jan, 2022
我们提出了多种经过证明有效的无模型强化学习算法,包括基于参考优势分解的在线无模型强化学习算法以及适用于模拟器环境的无模型强化学习算法,在平均报酬马尔科夫决策过程中实现更好的折扣估计和置信区间的高效构建。
Jun, 2023
该研究证明了自然策略梯度算法在无限状态的平均奖励马尔可夫决策过程中的收敛速度,如果采用良好的初始策略进行初始化,则收敛速度为O(1/√T)。此外,针对大类排队马尔可夫决策过程,最大权重策略足以满足我们的初始策略要求并实现O(1/√T)的收敛速度。关键是根据NPG算法的迭代策略所达到的相对值函数,我们得出了这一结果。
Feb, 2024
该研究报告首次提出了有限时间全局收敛分析方法,针对无限时间平均奖励马尔可夫决策过程中的策略梯度方法。具体而言,我们关注的是具有有限状态和动作空间的遍历型表格型马尔可夫决策过程。我们的分析表明,策略梯度迭代以O(log(T))的子线性速率收敛到最优策略,并获得了O(log(T))的后悔度保证,其中T表示迭代次数。我们的研究工作主要贡献在于证明了策略梯度算法对于平均奖励马尔可夫决策过程的收敛性,以及得到了有限时间的性能保证。与现有的折扣奖励性能界限不同,我们的性能界限明确依赖于捕捉底层马尔可夫决策过程复杂性的常数。在此基础上,我们重新审视和改进了折扣奖励马尔可夫决策过程的性能界限,并通过模拟评估了平均奖励策略梯度算法的性能。
Mar, 2024
我们研究了具有非线性函数逼近的基于模型的强化学习,其中底层马尔可夫决策过程(MDP)的转移函数由一个多项式逻辑模型给出。本文针对无限时间平均奖励设定,提出了两种算法。第一个算法UCRL2-MNL适用于通信MDP类,并实现了一种具有(近似)Ο(dD√T)的遗憾保证,其中d是特征映射的维数,D是底层MDP的直径,T是时间界。第二个算法OVIFH-MNL在计算上更有效,并适用于更一般的弱通信MDP类,我们展示了其具有(近似)Ο(d^(2/5)sp(v^*)T^(4/5))的遗憾保证,其中sp(v^*)是相关最优偏差函数的散度。我们还证明了对于最大直径为D的可通信MDP,学习具有MNL转移的复杂度的Ω(d√(DT))的下界。此外,我们对于具有MNL函数逼近的H-时间界的情况,展示了Ω(dH^(3/2)√K)的遗憾下界,在这里K是序列的数量,该下界优于有限时间界设定的已知最佳下界。
Jun, 2024
我们提出了一种新颖的层次强化学习方法,针对无限时域平均奖励设置中的线性可解决的马尔可夫决策过程(LMDPs)。与以往的工作不同,我们的方法允许同时学习低级和高级任务,而不对低级任务施加限制。我们的方法依赖于创造较小子任务的状态空间分割,并利用这种分割的等价性以实现更高效的学习。然后,我们利用低级任务的组合性来准确表示高级任务的价值函数。实验表明,我们的方法可以比平坦的平均奖励强化学习高出一到几个数量级。
Jul, 2024
本文研究了异步随机逼近算法及其在半马克ov决策过程中的应用,重点在于平均奖励标准。通过扩展Borkar和Meyn的稳定性证明方法,我们为异步SA算法提供了更广泛的收敛保证,并发展了RVI Q学习算法的收敛性,这将扩展目前的算法框架,对强化学习领域产生重要影响。
Sep, 2024