本文利用离线强化学习技术研究了时域同质马尔可夫决策过程上的策略评估和优化问题,并提出了一种递归方法来限制离线场景下的 “总方差” 项,得到了近似无视野远的样本复杂度上限。
Mar, 2021
本文使用生成模型证明了在马尔可夫决策过程中,基于值迭代算法的样本复杂度 PAC 上限为 O (Nlog (N/δ)/((1-γ)³ε²)),其中 N 为状态 - 动作对的数量,γ 为折扣因子,ε 表示动作价值函数的 ε- 最优估计,δ 为概率。同时证明了在任何强化学习算法中,基于每个状态 - 动作对估计最优动作值函数的样本复杂度下限为 Θ(Nlog (N/δ)/((1-γ)³ε²)),该上限和下限在 N,ε、δ、1/(1-γ) 方面匹配。
Jun, 2012
本文研究了约束马尔可夫决策过程,并提出了一种在线算法,该算法利用了有限时间视角下的线性规划公式来进行乐观规划,以提供概率上正确的 γ 优化策略,该算法逐渐逼近最佳结果,并且保证结果最多只是 γ 深度有损失的结果,并且在指定公差范围内具有概率保证。
Sep, 2020
本文提出了一种无模型的算法来学习具有折扣因子的马尔可夫决策过程中的政策,该算法的成功概率为 (1-p),且具有样本复杂度 O (SALn (1/p)/(ε^2 (1-γ)^3)),其中 S 是状态数,A 是行动数,γ 是折扣因子,ε 是一个近似阈值
Jun, 2020
本文提出了基于问题的独立的新样本复杂度和后悔下限,重点放在了非固定转移核情况下的情况,我们提出了新的样本下限并证明了我们的发现。
Oct, 2020
我们研究了强化学习问题中的约束马尔可夫决策过程(CMDP),并通过优化算法对 CMDP 问题的样本复杂度提出了改进,实现了优化的问题相关保证。
Feb, 2024
本文提出了一种无需进一步探索的离线强化学习方法,通过精心设计的模型实现了最优的样本复杂度,适合处理数据分布转移和数据覆盖范围受限的情况。
Apr, 2022
通过构建 ε- 网络和在线轨迹合成算法,证明纯表格的情况下,对于每个长度的规划时间,可以通过对数级的样本复杂度在多项式时间内发现适当规范化后的最佳策略,从而证明了一个假设,即规划时间的增加并不会增加学习长时序的 RW 的难度。
May, 2020
通过引入方差缩减策略,设计了一个记忆高效的算法来解决在线序列化强化学习中的勘探和开发之间的平衡问题,该算法的空间复杂度为 $ O (SAH)$,较以前的算法提高了 $S^5A^3$ 倍的效率。
Oct, 2021
我们在具有均匀遍历的马尔可夫决策过程(MDP)中,通过建立一个估计器来实现平均奖励 MDP 的最优策略,其样本复杂度达到文献中的下界,并借鉴了 Jin 和 Sidford(2021)以及 Li 等人(2020)的算法思想。
Oct, 2023