高效学习具有普适函数逼近的无限视野平均奖励马尔可夫决策问题

ICLRApr, 2024

高效学习具有普适函数逼近的无限视野平均奖励马尔可夫决策问题

Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation

Jianliang He, Han Zhong, Zhuoran Yang

TL;DR我们提出了一种名为 LOOP 的新算法框架，它结合了基于模型和基于值的方法，用于研究无限时域平均奖励马尔可夫决策过程（AMDPs）。此外，我们提出了一个新的复杂度度量并证明了框架在几乎所有 AMDPs 中的有效性。

Abstract

We study infinite-horizon average-reward markov decision processes (AMDPs) in the context of general function approximation. Specifically, we propose a novel algorithmic framework named Local-fitted Optimization

infinite-horizon average-reward markov decision processes model-based and value-based incarnations average-reward generalized eluder coefficient loop algorithm function approximation

发现论文，激发创造

使用线性函数逼近学习无限时间平均回报马尔可夫决策过程

开发多种学习用于 Markov Decision Processes 的无限时间平均奖励设置和线性函数逼近的算法，使用乐观原则和假设 MDP 具有线性结构，提出具有优化的计算效率的算法，并展开了详细的分析，改进了现有最佳结果。

Jul, 2020

可证明高效的无限时间平均回报线性 MDP 的强化学习

设计了一个计算有效的算法，通过将平均奖励设定近似为折扣设定，并且在适当调整贴现因子时，通过运行基于乐观值迭代的算法来实现无限时段平均奖励线性马尔可夫决策过程 (MDP) 的 O (sqrt (T)) 的遗憾。

May, 2024

基于规约的平均回报 MDP 的近似最优策略学习

本研究考虑采用生成模型（模拟器）以获取平均奖励 MDP 中的 eps 策略最优性的样本复杂度。

Dec, 2022

无模型强化学习中的无限时域平均奖赏马尔可夫决策过程

本文提出两种基于无模型的强化学习算法，用于学习无限时间持续的平均回报 MDP 问题，第一种算法在弱相互通信的 MDPs 中，将问题简化为折扣回报问题，在 T 步之后的遗憾为 O (T^(2/3)), 该算法是解决该问题的第一种无模型的算法；第二种算法利用了对抗多臂老虎机自适应算法的最新进展，将遗憾进一步改进至 O (sqrt (T))，但需要更强的符合人类定义的遍历条件。这个结果取代了 Abbasi-Yadkori 等人 2019 年只有在符合人类定义的遍历条件下的 ergodic MDP 才能达到 O (T^(3/4)) 的遗憾。

Oct, 2019

强化学习中样本高效函数逼近的通用框架

本文提出了一个能够统一模型驱动和无模型驱动强化学习的通用框架，本框架中提出了一个可见证贝尔曼算法（ABC）类别，能够涵盖几乎所有文献中的马尔可夫决策过程（MDP）模型。结合该框架，本文提出了一个新的算法 OPtimization-based ExploRation with Approximation（OPERA），能够在多种 MDP 模型中达到最小遗憾的上限。

Sep, 2022

鲁棒平均奖励马尔科夫决策过程

本篇论文研究鲁棒平均回报 MDP 问题，旨在找到一种策略，使其在不确定性的 MDP 集合中的最坏平均回报最优化。作者探讨了利用折扣 MDP 实现这个问题，证明了当折扣因子趋近于 1 时，鲁棒折扣价值函数收敛于鲁棒平均回报，并设计了鲁棒动态规划方法。同时，也考虑了直接处理鲁棒平均回报 MDP 问题的情况，并导出了其鲁棒 Bellman 方程，设计了一种鲁棒相对价值迭代算法来求解其策略。

Jan, 2023

基于平均奖励的马尔可夫决策过程更为精确的无模型强化学习

我们提出了多种经过证明有效的无模型强化学习算法，包括基于参考优势分解的在线无模型强化学习算法以及适用于模拟器环境的无模型强化学习算法，在平均报酬马尔科夫决策过程中实现更好的折扣估计和置信区间的高效构建。

Jun, 2023

全局收敛性：在平均奖励马尔可夫决策过程中的策略梯度

该研究报告首次提出了有限时间全局收敛分析方法，针对无限时间平均奖励马尔可夫决策过程中的策略梯度方法。具体而言，我们关注的是具有有限状态和动作空间的遍历型表格型马尔可夫决策过程。我们的分析表明，策略梯度迭代以 O (log (T)) 的子线性速率收敛到最优策略，并获得了 O (log (T)) 的后悔度保证，其中 T 表示迭代次数。我们的研究工作主要贡献在于证明了策略梯度算法对于平均奖励马尔可夫决策过程的收敛性，以及得到了有限时间的性能保证。与现有的折扣奖励性能界限不同，我们的性能界限明确依赖于捕捉底层马尔可夫决策过程复杂性的常数。在此基础上，我们重新审视和改进了折扣奖励马尔可夫决策过程的性能界限，并通过模拟评估了平均奖励策略梯度算法的性能。

Mar, 2024

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

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

Jan, 2022

无限时间平均回报马尔科夫决策过程的强化学习与多项式逻辑函数逼近

我们研究了具有非线性函数逼近的基于模型的强化学习，其中底层马尔可夫决策过程（MDP）的转移函数由一个多项式逻辑模型给出。本文针对无限时间平均奖励设定，提出了两种算法。第一个算法 UCRL2-MNL 适用于通信 MDP 类，并实现了一种具有 (近似)Ο(dD√T) 的遗憾保证，其中 d 是特征映射的维数，D 是底层 MDP 的直径，T 是时间界。第二个算法 OVIFH-MNL 在计算上更有效，并适用于更一般的弱通信 MDP 类，我们展示了其具有 (近似)Ο(d^(2/5) sp (v^*) T^(4/5)) 的遗憾保证，其中 sp (v^*) 是相关最优偏差函数的散度。我们还证明了对于最大直径为 D 的可通信 MDP，学习具有 MNL 转移的复杂度的 Ω(d√(DT)) 的下界。此外，我们对于具有 MNL 函数逼近的 H - 时间界的情况，展示了 Ω(dH^(3/2)√K) 的遗憾下界，在这里 K 是序列的数量，该下界优于有限时间界设定的已知最佳下界。

Jun, 2024