有限时间 MDPs 的全局问题相关后悔下限

Jun, 2021

有限时间 MDPs 的全局问题相关后悔下限

A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs

Andrea Tirinzoni, Matteo Pirotta, Alessandro Lazaric

TL;DR针对有限时间表格 MDPs 的后悔最小化问题，我们推导了一个新颖的渐近问题相关下限。尽管与先前的工作类似（例如针对遍历 MDPs 的工作），这个下限是一个优化问题的解，但我们的推导表明需要在状态 - 动作对的访问分布上附加一个额外的约束条件，以明确考虑 MDP 的动态性。通过一系列示例，我们提供了我们下界的表征，说明不同的 MDP 可能具有显着不同的复杂性。

Abstract

We derive a novel asymptotic problem-dependent lower-bound for regret minimization in finite-horizon tabular markov decision processes (MDPs). While, similar to prior work (e.g., for ergodic MDPs), the

regret minimization markov decision processes visitation distribution lower-bound optimization problem

发现论文，激发创造

具有约束条件的无限时间平均奖励马尔可夫决策过程学习

本研究提出了一种政策优化算法，用于处理成本约束下的无限时间跨度平均奖励马尔可夫决策过程中的后悔最小化问题，该算法在符合一定条件的 MDP 下具有较低的后悔度和约束违反率，并将其推广到弱通信 MDP 领域，为该领域提供了复杂度可行的算法。

Jan, 2022

基于无界时间跨度和方差的隐含马尔可夫决策过程强化学习

本文研究基于后知的上下文中的潜在马尔可夫决策过程（LMDPs）的强化学习中的遗憾最小化问题，设计了一种新的基于模型的算法框架，证明了具有一定时间复杂度的遗憾上限。

Oct, 2022

线性马尔可夫决策过程的无界遗憾

近期一些研究工作展示了强化学习中降低后悔的边界可以（几乎）与计划周期无关，即所谓的无周期边界。然而，这些后悔边界仅适用于允许对转移模型大小多项式依赖的设置，例如表格型马尔科夫决策过程（MDP）和线性混合 MDP。我们给出了流行的线性 MDP 设置的首个无周期边界，其中转移模型的大小可以是指数级大甚至是不可数的。与先前的工作相比，该方法不需要明确估计转移模型并计算不同时间步的非齐次值函数，而是直接估计值函数和置信区间集合。通过保持多个加权最小二乘估计器，该方法获得了无周期边界，并且通过结构引理证明了非齐次值函数的最大总变差受特征维数的多项式因子限制。

Mar, 2024

潜在 MDPs 的强化学习：遗憾保证和下界

在本文中，我们考虑了隐式马尔科夫决策过程中强化学习的遗憾最小化问题，我们提出了一个具有局部保证的有效算法，以解决这个问题。

Feb, 2021

使用值函数界限在没有领域知识的情况下加强强化学习的问题相关遗憾范围

该研究针对有限时间段的离散马尔科夫决策问题，提出了一种算法并分析了其性能上限，得出了最先进的范围和如果环境规范小则更紧的限制，其不需要先前对应环境规范的知识，能解决经验学习中常常遇到的限制问题。

Jan, 2019

基于表格型 MDPs 的非渐进性依赖间隔遗憾上界

本文的关键是通过建立一种新的 “裁剪” 遗憾分解技术，证明了乐观算法能够在有限的步数内以对数遗憾实现相应动态规划问题的最优解，并适用于广泛的最优算法。

May, 2019

有限 MDP 中的情节式强化学习：Minimax 下界再思考

本文提出了基于问题的独立的新样本复杂度和后悔下限，重点放在了非固定转移核情况下的情况，我们提出了新的样本下限并证明了我们的发现。