在线线性 $ q^π $ 可实现 MDPs 中的 RL 与线性 MDPs 一样简单，只要你学会忽略什么

Oct, 2023

在线线性 $ q^π $ 可实现 MDPs 中的 RL 与线性 MDPs 一样简单，只要你学会忽略什么

Online RL in Linearly $q^π$-Realizable MDPs Is as Easy as in Linear MDPs If You Learn What to Ignore

Gellért Weisz, András György, Csaba Szepesvári

TL;DR在线强化学习中的线性可实现的马尔可夫决策过程 (MDP)，提出了一种计算效率较低的学习算法，通过跳过特定状态转化为线性 MDP，并证明了该算法在这种情况下具有多项式样本复杂度。

Abstract

We consider online reinforcement learning (RL) in episodic Markov decision processes (MDPs) under the linear $q^\pi$-realizability assumption, where it is assumed that the action-values of all policies can be expressed as linear functions of state-action features. This class is known t

online reinforcement learning markov decision processes linear mdps computationally inefficient learning algorithm misspecified case

发现论文，激发创造

线性可行最优状态价值函数下的 MDP 查询效率规划

本文考虑了使用生成模型进行有限轮次的 MDP 本地规划，并提出了一种名为 TensorPlan 算法的方法，在最优价值函数符合线性可实现性的情况下，能够以 poly ((dH/δ) 的复杂度找到相对于任何线性可实现性且存在界限参数的确定性策略的 δ 最优策略；此外，本文还将上限拓展到了近可实现性情况和无限时域折扣设置。

Feb, 2021

自信自然策略梯度用于 $q_π$ 可实现受限 MDP 中的本地规划

这篇研究论文提出了一个新的基于受约束的马尔可夫决策过程（CMDP）框架的强化学习算法，通过离线数据评估和策略梯度更新来在线学习，实现了 CMDP 在线性设置中的多项式样本复杂度。

Jun, 2024

具有恒定子最优性差异的可线性实现 MDPs 的指数下界

本研究讨论在线强化学习问题，探讨了是否能够通过加入一个常数子优性差值的假设来实现有效学习，结果发现即使假设线性实现了最优 Q 函数，仍然需要指数级别的样本量，进一步证明在线学习和生成模型学习之间存在指数差距。

Mar, 2021

强化学习中的计算统计差距

本文针对强化学习中的大状态空间问题，研究使用函数逼近的强化学习方法，并提出了寻找高效率算法的方案，同时探讨了计算难度与统计问题之间的关系。

Feb, 2022

在线稀疏强化学习

在稀疏线性马尔可夫决策过程中，通过引入一种新的算法 - Lasso fitted Q-iteration，通过一个具有一定条件的数据策略，以几乎无维度代价实现对在线强化学习的降低，但线性后悔在常用政策情况下仍然无法避免。

Nov, 2020

稀疏线性 MDP 中的探索和学习，无需计算难解的预测器

线性马尔科夫决策过程（MDP）中的特征选择和零稀疏线性 MDP，以及通过凸规划有效计算的模拟器、低深度决策树上的区块 MDP 的学习算法。

Sep, 2023

几乎没有视野限制的离线强化学习

本文利用离线强化学习技术研究了时域同质马尔可夫决策过程上的策略评估和优化问题，并提出了一种递归方法来限制离线场景下的 “总方差” 项，得到了近似无视野远的样本复杂度上限。

Mar, 2021

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

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

Oct, 2017

连续状态空间中的样本高效强化学习：超越线性的视角

提出了 Effective Planning Window（EPW）条件，并提供一种算法来证明满足该条件的 MDPs 具有有效的样本使用率，该条件是在 RL 中不需要假设线性结构的一种结构性条件。

Jun, 2021

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

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

May, 2023