原始 - 对偶 π 学习：对遍历式马尔可夫决策问题的样本复杂度和亚线性运行时间

Oct, 2017

原始 - 对偶 π 学习：对遍历式马尔可夫决策问题的样本复杂度和亚线性运行时间

Primal-Dual $π$ Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems

Mengdi Wang

TL;DR本文提出了一种基于 Primal-Dual π Learning 的方法，利用线性对偶性更新价值与策略向量以逼近无穷时间和折扣因子为 1 的马尔可夫决策过程的最优策略，并给出了复杂度上界，并且这种方法还能应用于有限状态、有限动作空间以及随机转移概率模型下的计算问题，当情况许可下，此方法可以在次线性时间内解决平均奖励最大化的问题。

Abstract

Consider the problem of approximating the optimal policy of a Markov decision process (MDP) by sampling state transitions. In contrast to existing reinforcement learning methods that are based on successive approximations to the nonlinear Bellman equation, we propose a Primal-Dual $\pi$ Learning method in light of the linear duality between the value and pol

markov decision process primal-dual π learning policy approximation model-free sublinear-time algorithm

发现论文，激发创造

随机原始对偶方法和强化学习样本复杂性

本文研究了马尔可夫决策过程 (MDP) 的最优策略在线估计问题，并提出了一类基于随机原始对偶法的方法，利用 Bellman 方程的内在极小极大对偶性进行优化。这些方法具有小的存储空间和低的计算复杂度，通过观察新的状态转移更新值和策略估计的少数坐标。对于无限时间折扣奖励 MDP，这些 SPD 方法使用 O (|S|^4 |A|^2σ^2/(1-γ)^6ε^2) 的迭代 / 样本数可以高概率地找到绝对 ε- 最优策略，对于有限时间 MDP，迭代次数为 O (|S|^4 |A|^2H^6σ^2/ε^2)。

Dec, 2016

无模型强化学习：从剪切伪懊恼到样本复杂度

本文提出了一种无模型的算法来学习具有折扣因子的马尔可夫决策过程中的政策，该算法的成功概率为 (1-p)，且具有样本复杂度 O (SALn (1/p)/(ε^2 (1-γ)^3))，其中 S 是状态数，A 是行动数，γ 是折扣因子，ε 是一个近似阈值

Jun, 2020

随机线性规划以几乎线性（有时是亚线性）的运行时间解决折扣马尔科夫决策问题

提出一种新的随机线性规划算法，利用价值 - 策略对偶和二叉树数据结构，自适应地采样状态 - 动作 - 状态转移，并进行指数原始 - 对偶更新，从而以几乎线性的运行时间在最坏情况下找到一个 ε- 最优策略。当马尔可夫决策过程是遍历的并且以某些特殊的数据格式指定时，该算法使用线性的运行时间，在状态 - 动作对的总数中是次线性的，为解决随机动态规划问题提供了新的途径和复杂性基准。

Apr, 2017

卷积投影：连续空间马尔可夫决策过程中强化学习的最佳样本复杂度

学习连续空间马尔可夫决策过程中的 ε- 最优策略问题，在具有光滑 Bellman 算子的一般类别中，通过使用正交三角多项式特征的简单的扰动最小二乘值迭代，并结合基于谐波分析的新型投影技术，实现了速率最优的样本复杂性。

May, 2024

用生成模型解决折扣马尔可夫决策过程的最优时间和样本复杂度

通过生成采样模型计算马尔可夫决策过程问题的最优策略及其样本复杂度分析。

Jun, 2018

线性 MDP 的离线原始 - 对偶强化学习

本文提出了一种基于线性规划的原对偶优化方法，该方法针对有限时间或使用表格的强 RL 范式有较强的理论保证，采用函数近似和最小数据集假设解决了无限时间范式的算法问题，并在更具挑战性的平均回报设置下进行了分析。

May, 2023

在约束马尔可夫决策过程中实现 $\tilde {O}(1/ε)$ 的样本复杂性

我们研究了强化学习问题中的约束马尔可夫决策过程（CMDP），并通过优化算法对 CMDP 问题的样本复杂度提出了改进，实现了优化的问题相关保证。

Feb, 2024

深度原始 - 对偶强化学习：利用贝尔曼对偶加速演员 - 评论家算法

基于深度神经网络的参数 Primal-Dual pi 学习方法，旨在解决马尔可夫决策过程中状态空间大和策略离线学习问题，通过基本线性 Bellman 方法对价值和策略函数进行原始对偶更新，从而更加有效地进行价值和策略更新，在与同类方法比较的测试中表现明显优于最相关的基准方法

Dec, 2017

离线约束强化学习的低秩 MDP 原始 - 对偶算法

该论文提出了一种用于解决低秩 Markov 决策过程的离线强化学习算法，该算法在折扣无限时间段设置中具有较低的样本复杂度，且支持离线约束强化学习设置。

Feb, 2024

平均回报马尔可夫决策过程的最佳样本复杂度

我们在具有均匀遍历的马尔可夫决策过程（MDP）中，通过建立一个估计器来实现平均奖励 MDP 的最优策略，其样本复杂度达到文献中的下界，并借鉴了 Jin 和 Sidford（2021）以及 Li 等人（2020）的算法思想。

Oct, 2023