具有量化目标的随机博弈价值迭代的停止准则
研究了在零和Markov博弈中的价值函数逼近问题,提出了适用于Markov博弈的强化学习算法,并针对在两人同时进行移动的特殊问题,给出了LSTD和时间差分学习的线性价值函数逼近的收敛保障,通过LSPI算法,将该算法应用于足球领域和流量控制问题中,并证明了价值函数逼近在Markov博弈中的可行性。
Dec, 2012
本研究提出了一种基于平均报酬MDPs的学习和规划算法,其中包括第一种无参考状态的普遍证明收敛的无模型控制算法、第一个证明收敛的无政策自由预测算法,以及第一个离线学习算法,其收敛于实际值函数而不是值函数增加一个偏移量。在使用时间差错错误而不是常规错误更新平均报酬估计时,我们的所有算法都基于此。
Jun, 2020
研究了时间变动折扣率的无限时间段马尔可夫决策过程,以一个博弈论的视角看待每一个时间步骤为一个独立决策者,研究了所得到博弈的次游戏最佳均衡点(SPE)以及相关的算法问题。提出了SPE的存在性的构造性证明,证明了计算SPE的EXPTIME难度,同时证明了在较弱的假设条件下存在一个近似SPE(ε-SPE)。提供了计算ε-SPE的算法,并提供了时间复杂度上界,该上界是基于时间变动折扣率的收敛特性的函数。
Jul, 2023
马尔可夫决策过程在强化学习中起着关键作用,本研究探讨了多种与强化学习相关的'成本',研究了策略评估的样本复杂度,并开发了一种具有实例特定误差界限的新估计器;在在线遗憾最小化设置下,通过引入基于奖励的常量和基于潜力的奖励塑形技术,提供了理论上的解释;提出了一种安全强化学习研究方法,建立了重置效率的量化概念;针对具有多个奖励函数的决策过程,开发了一个能够计算出帕累托最优随机策略的规划算法。
Aug, 2023
马尔科夫决策过程(MDPs)为不确定性下的顺序决策制定了标准框架,但是MDPs中的转移概率通常是从数据中估计的,并且MDPs不考虑数据的不确定性。鲁棒马尔科夫决策过程(RMDPs)通过为每个转移分配不确定性集合而不是单个概率值来解决了MDPs的这个缺点。解决RMDPs的目标是找到一种策略,使得在不确定性集合上最大化最坏情况的性能。本文考虑多面体RMDPs,在其中所有的不确定性集合都是多面体,并研究解决长期平均回报的多面体RMDPs的问题。我们关注计算复杂性方面和高效算法。我们提出了这个问题的一个新视角,并且证明它可以简化为解决具有有限状态和动作空间的长期平均回报的轮流随机游戏。这个简化使我们能够得出几个重要的结论,这些结论以前是未知的。首先,我们为解决长期平均回报的多面体RMDPs推导出新的计算复杂性界限,首次证明它们的阈值决策问题属于NP coNP,并且它们具有具有亚指数期望运行时间的随机算法。其次,我们提出了鲁棒多面体策略迭代(RPPI),一种用于解决长期平均回报的多面体RMDPs的新型策略迭代算法。我们的实验评估表明,相比基于值迭代的现有方法,RPPI在解决长期平均回报的多面体RMDPs方面更加高效。
Dec, 2023
研究马尔可夫潜势博弈在无限时间平均回报准则下,证明基于独立策略梯度和独立自然策略梯度的算法都能在全局收敛到纳什均衡点,同时提出了渐进性和底座条件,通过梯度和微分值函数的灵敏度边界为梯度方法奠定了基础,并证明了三种算法的收敛性以及具体的时间复杂度,当需要估计策略梯度时,我们提出了一个算法并给出了样本复杂度分析,最后通过模拟研究来验证结果。
Mar, 2024
该研究报告首次提出了有限时间全局收敛分析方法,针对无限时间平均奖励马尔可夫决策过程中的策略梯度方法。具体而言,我们关注的是具有有限状态和动作空间的遍历型表格型马尔可夫决策过程。我们的分析表明,策略梯度迭代以O(log(T))的子线性速率收敛到最优策略,并获得了O(log(T))的后悔度保证,其中T表示迭代次数。我们的研究工作主要贡献在于证明了策略梯度算法对于平均奖励马尔可夫决策过程的收敛性,以及得到了有限时间的性能保证。与现有的折扣奖励性能界限不同,我们的性能界限明确依赖于捕捉底层马尔可夫决策过程复杂性的常数。在此基础上,我们重新审视和改进了折扣奖励马尔可夫决策过程的性能界限,并通过模拟评估了平均奖励策略梯度算法的性能。
Mar, 2024
本研究针对传统马克ov决策过程在转移概率需要精确已知这一限制假设的缺陷,提出了强鲁棒马克ov决策过程(RMDPs),允许转移概率属于某个不确定性集合。文章提供了RMDPs的基本教学,探讨了其语义和解决方法,以及与其他模型的关系,展示了RMDPs在强化学习和抽象技术等多个领域的应用潜力。
Nov, 2024
本文解决了一种鲁棒马尔可夫决策过程(RMDP)中的不确定性问题,提出了一种通用、可靠且高效的求解框架。研究发现,该框架不仅能高效处理多种不确定性集合,还能在计算过程中提供精度保证,最显著的影响是它可以在短时间内解决具有上百万状态的RMDP。
Dec, 2024
本文解决了两人零和马尔可夫博弈(TZMGs)中由于状态数量增加导致均衡计算困难的问题。通过将多个不同状态视为一个状态的方式进行状态抽象,提出了一种新颖的方法,并通过推导对偶间隙界限来评估状态抽象游戏的均衡解。实验结果显示,该方法在马尔可夫足球游戏中有效计算了均衡策略,具有重要的应用潜力。
Dec, 2024