潜在 MDPs 的强化学习:遗憾保证和下界
本文研究基于后知的上下文中的潜在马尔可夫决策过程(LMDPs)的强化学习中的遗憾最小化问题,设计了一种新的基于模型的算法框架,证明了具有一定时间复杂度的遗憾上限。
Oct, 2022
针对有限时间表格 MDPs 的后悔最小化问题,我们推导了一个新颖的渐近问题相关下限。尽管与先前的工作类似(例如针对遍历 MDPs 的工作),这个下限是一个优化问题的解,但我们的推导表明需要在状态 - 动作对的访问分布上附加一个额外的约束条件,以明确考虑 MDP 的动态性。通过一系列示例,我们提供了我们下界的表征,说明不同的 MDP 可能具有显着不同的复杂性。
Jun, 2021
研究有限时段表格马尔可夫决策过程(MDPs)中的遗憾最小化问题,在差分隐私(DP)约束条件下,提出两种 DP 变体的通用框架 -- 集中式 DP(JDP)和本地 DP(LDP)-- 以设计带有隐私机制的强化学习算法,其中 JDP 的隐私代价仅为下限加项,而 LDP 的代价则是乘法项。同时获得次线性的遗憾保证,并提出了该分析的统一方法。
Dec, 2021
我们介绍了没有任何附加结构假设的 Latent Markov Decision Processes (LMDPs) 的第一个样本高效算法,并建立了新的离线评估引理和 LMDPs 的新覆盖系数,通过这些结果可以推导出一种乐观探索算法的近似最优保证。我们相信这些结果对于广泛的交互式学习问题,特别是部分观测环境中,具有重要价值。
Jun, 2024
为了解决在连续状态和 / 或动作空间中得到强化学习(RL)无后悔保证仍然是该领域的主要挑战之一,本论文引入了一种新的结构性假设,即 $ u-$ 平滑性,它概括了迄今已提出的大多数设置(如线性 MDPs 和 Lipschitz MDPs),我们提出了两种算法,在 $ u-$ 平滑 MDPs 中对后悔进行最小化,这两种算法都建立在利用基于 Legendre 多项式的正交特征映射来构建 MDP 表示的思想上,第一种算法 extsc {Legendre-Eleanor} 在较弱的假设下实现无后悔属性,但计算效率低,而第二种算法 extsc {Legendre-LSVI} 虽然运行时间是多项式级别,但适用于较小的问题类别,经分析它们的后悔性能,我们将结果与 RL 理论的最新成果进行了比较,表明我们的算法达到了最佳保证。
Feb, 2024
本文探讨了如何用线性优化的方法解决在对抗环境下的马尔科夫决策过程问题,通过将特征映射设置到线性优化的赌臂中,得到了不需要访问转移模拟器的新技术,并在探索性的假设下,将线性对手马尔科夫决策问题的最优结果从 $ ilde {O}(K^{6/7})$ 提高到了 $ ilde {O}(K^{4/5})$。
Feb, 2023
本文研究了在损失函数任意的情况下,对于线性近似的 Q 函数,提出了两种算法,可以在拥有模拟器的情况下使得损失最小值达到 $\tilde {\mathcal O}(\sqrt K)$,并在无模拟器情况下实现了 $ ilde {\mathcal O}(K^{8/9})$ 的表现,改进了之前的表现
Jan, 2023
近期一些研究工作展示了强化学习中降低后悔的边界可以(几乎)与计划周期无关,即所谓的无周期边界。然而,这些后悔边界仅适用于允许对转移模型大小多项式依赖的设置,例如表格型马尔科夫决策过程(MDP)和线性混合 MDP。我们给出了流行的线性 MDP 设置的首个无周期边界,其中转移模型的大小可以是指数级大甚至是不可数的。与先前的工作相比,该方法不需要明确估计转移模型并计算不同时间步的非齐次值函数,而是直接估计值函数和置信区间集合。通过保持多个加权最小二乘估计器,该方法获得了无周期边界,并且通过结构引理证明了非齐次值函数的最大总变差受特征维数的多项式因子限制。
Mar, 2024
本文研究了具有未知转换和拥有无限制延迟反馈的分集式马尔可夫决策过程的在线学习,表现出基于策略优化的新算法,在完全信息反馈下实现了接近最优的高概率后悔情况,同时也是第一个考虑具有延迟反馈的 MDP 的后悔最小化设置。
Dec, 2020
该研究针对马尔可夫决策过程中的无折扣强化学习问题提出了一种算法,并提供了针对最优非静态策略的性能保证。给出了在 MDP 总变差方面的差错的上限,这是一般强化学习设置的第一个变分差错界限。
May, 2019