Apr, 2017

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

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

    提出了一种采用采样技术的快速算法来解决折扣马尔可夫决策过程的近似求解，并证明了算法的收敛性和复杂度。同时，结合经典的价值迭代与方差约减技术，改进了该算法的性能，使其具有线性收敛性和渐进最优性。

    Oct, 2017

  • 通过线性规划对偶解决大规模马尔可夫决策问题

    本文提出了一种针对状态空间较大的 MDP 问题进行优化的方法，该方法基于一小组策略的占用度量的低维度逼近，并提出了一个有效的算法，可用于在该类策略中找到低过度损失相对于最佳策略的策略。作者限定了平均成本和折扣成本情况下的过量损失，并在队列应用中展示了该方法的有效性。

    Jan, 2019

  • 大规模马尔可夫决策问题的线性规划

    本文考虑了控制具有大状态空间的马尔可夫决策过程以最小化平均成本的问题，并使用线性规划和两种方法，即基于随机凸优化和基于约束采样的方法，将性能提高到与在低维策略类中的任何策略相比的最佳水平。

    Feb, 2014

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

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

    Oct, 2017

  • 线性马尔可夫决策过程低切换成本可证效率算法

    本文着重于线性马尔可夫决策过程（MDP）问题中的低转换成本，并提出了第一个具有低转换成本的线性 MDP 算法，同时通过低转换成本较小而达到了大体积的泛化。

    Jan, 2021

  • 线性马尔科夫决策过程的近最小值最大化强化学习

    本文介绍了一种基于加权线性回归方案的计算有效算法，用于处理线性马尔可夫决策过程的强化学习问题。该算法实现了近似最小化最优遗憾，具有较好的效率，对参数化转换动态有良好的适应性，可以对研究领域进行更细致的探讨。

    Dec, 2022

  • 合作多智能体马尔可夫决策过程中的近似线性规划和分散策略改进

    我们提出了适用于合作多智能体有限和无限时域折扣马尔可夫决策过程的逼近策略迭代算法，其中使用近似线性规划计算近似值函数并实施分散策略改进。

    Nov, 2023

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

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

    Jun, 2018

  • 随机算法与 PAC 界限在连续空间逆向强化学习中的应用

    该研究探讨了具有连续状态和动作空间的离散时间贴现马尔可夫决策过程，并解决了从观察到的最优行为中推断成本函数的逆问题。研究首先考虑了完全掌握专家策略的情况，并通过使用职业度量、线性对偶和互补松弛条件来刻画逆问题的解集。为避免平凡解和不适当性，引入了自然线性标准化约束。这导致了一个无限维的线性可行性问题，并对其性质进行了深入分析。其次，采用线性函数逼近器和随机化方法，即场景方法和相关的概率可行性保证，为逆问题提供了 ε- 最优解。对于所需的近似精度，进一步讨论了样本复杂度。最后，针对只有有限一组专家示范和生成模型可供使用的更加现实的情况，给出了使用样本时产生的误差界限。

    May, 2024

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

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

    Jun, 2020