关于POMDP中随机控制器优化的计算复杂性
本文研究部分可观察马尔可夫决策过程(POMDPs)的解决方案,探讨如何从有限状态自动机的限制集合中找到最佳策略,进而展示了通过分支定界法和梯度上升法寻找全局最优确定性策略和局部最优随机策略的优越实验结果。
Jan, 2013
本文介绍了使用有限状态自动机表示具有有限记忆的策略学习算法,具体探讨在部分可观测的MDP问题中,基于随机梯度下降的VAPS算法进行本地优化的通用有限状态自动机控制器的问题。并进一步讨论了在何种条件下随机梯度下降将优于精确梯度下降的问题,通过实证研究验证了该算法在补偿每个时间步上的不可观测性方面发挥了良好的效果。
Jan, 2013
本文研究部分可观察马尔可夫决策过程 (POMDPs),带有一组目标状态并且每个转移都有一个整数成本。研究的最优化目标是在确保(概率为1)几乎达到目标集时最小化预期总成本。我们证明,对于整数成本,近似最优成本是不可判定的。对于正成本,我们的结果有:(i)我们建立了最优成本的匹配下限和上限,上限是双指数;(ii)我们表明,近似最优成本的问题是可判定的,并且提出了建立在具有有限时间段目标的 POMDP 算法上的近似算法。虽然这个算法的最坏运行时间是双指数的,但我们还介绍了算法的有效停止标准,并实验性地表明它在许多有意义的示例中表现良好。
Nov, 2014
本研究旨在解决部分可观测的马尔科夫决策过程中最大化期望奖励的问题,将其转化为线性规划问题,并研究了用于减少搜索空间的有限随机性的最优无记忆策略的几何框架,进而通过实验说明了该方法有助于更好更快地收敛到策略梯度。
Mar, 2015
本文提出基于有限状态控制器的有界策略迭代方法,通过标准的凸优化算法设计出完全风险规避的POMDP最优策略,并针对给定的记忆预算和优化指标对控制器进行修改以减小一致风险。
Sep, 2019
本研究提出了一种基于POMDPs的任意时间算法,通过在线性时态逻辑(LTL)清单约束条件下最大化满足概率来合成次优随机有限状态控制器(sFSCs),并通过机器人导航案例研究表明了该方法的有效性。
Jan, 2020
本研究考虑了有限状态和动作空间的无穷时部分观察到的马尔可夫决策问题中,根据折扣或平均收益准则找到最佳的无记忆随机策略并描述了优化问题作为可行状态-动作频率空间中的线性优化问题并使用了多项式优化的最大化奖励来解决导航问题。
Oct, 2021
研究如何解决具有不确定转移内核的折现,有限状态,有限行动空间MDP的强鲁棒性问题,旨在寻找一个抵抗传递不确定性的最佳策略。与标准MDP规划相比,本文提出了一个名为RPMD的策略型一阶方法,并对于两种递增步长的情形,建立了寻找ε-最优策略的O(log(1/ε))和O(1/ε)迭代复杂度。本文还提出了一种名为SRPMD的随机变量。
Sep, 2022
本文研究部分可观察马尔科夫决策过程(POMDP),发现除非我们拥有完整的后见状态信息,否则需要指数级的样本复杂度才能实现对POMDP的一个ε-最优策略解,但有部分POMDP分类情况下,其状态信息是足够的,本文提出了新的算法并证实这些算法是近似最优解。
Jun, 2023
通过引入新的限制性、历史依赖成本约束的递归约束部分可观察马尔可夫决策问题 (RC-POMDP),本文解决了常规约束部分可观察马尔可夫决策问题 (C-POMDP) 中存在的问题,并提出了一个基于点的动态规划算法来寻找 RC-POMDP 的最优策略。实验证明,相比于 C-POMDP 的策略,RC-POMDP 的策略具有更好的行为,并展示了算法在一组基准问题上的有效性。
Oct, 2023