当下样本独立时，瑕疵无关的增强学习何时具有统计追踪性？

Oct, 2023

当下样本独立时，瑕疵无关的增强学习何时具有统计追踪性？

When is Agnostic Reinforcement Learning Statistically Tractable?

Zeyu Jia, Gene Li, Alexander Rakhlin, Ayush Sekhari, Nathan Srebro

TL;DR我们研究了对所有政策类 Pi 进行不可知 PAC 强化学习问题：在与一个未知的具有潜在庞大状态和动作空间的 MDP 交互的情况下，需要多少轮才能学习到相对于 Pi 的 epsilon - 次优政策？为此，我们引入了一种新的复杂性度量，称为生成能力，它仅依赖于政策类 Pi 而与 MDP 动力学无关。通过一个生成模型，我们证明了对于任何政策类 Pi，有界的生成能力表征了 PAC 可学习性。然而，对于在线 RL 来说，情况要复杂些。我们展示了存在一个具有有界生成能力的政策类 Pi，需要超多项式数量的样本来进行学习。这揭示了在生成访问和在线访问模型之间（以及在线访问下的确定性 / 随机 MDPs 之间）对于不可知学习能力的令人惊讶的区别。在积极方面，我们确定了一种额外的向日葵结构，它与有界生成能力一起，通过一种名为 POPLER 的新算法实现了统计高效的在线 RL，该算法借鉴了经典的重要性采样方法以及无奖励探索中可达状态识别和政策评估技术。

Abstract

We study the problem of agnostic pac reinforcement learning (RL): given a policy class $\Pi$, how many rounds of interaction with an unknown MDP (with a potentially large state and action space) are required to l

agnostic pac reinforcement learning spanning capacity policy class online rl popler

发现论文，激发创造

强化学习中高效的偏差 - 跨度 - 约束探索 - 利用

SCAL 是一种用于解决未知弱通信马尔可夫决策过程中的有效探索和开发问题的算法，通过对 REGAL.C 的优化问题进行了放松和分析，提供了第一个可计算的有效算法，并表明 SCAL 在具有大直径和小偏差跨度的 MDP 中显著优于 UCRL。

Feb, 2018

基于区间的平均奖励 MDP 的最优样本复杂度

我们研究了一个基于生成模型的平均回报马尔科夫决策过程（MDP）中学习一个 ε- 最优策略的样本复杂度，建立了复杂度界限 Ω(SA (H/ε^2))。我们的结果在参数 S、A、H 和 ε 上是极小极大最优的（最多有对数系数），进一步改进了现有工作，其中要么假定所有策略的混合时间均匀有界，要么对参数有次优的依赖。我们的结果基于将平均回报 MDP 简化为折扣 MDP。为了证明这种简化的最优性，我们对 γ 折扣 MDP 进行了改进的界限，显示了在 γ≥1-1/H 的情况下，采样 Ω(SA (H/((1-γ)^2ε^2))) 足以在弱通信 MDP 中学习 ε- 最优策略，从而规避了适用于一般 γ 折扣 MDP 的 Ω(SA/(1-γ)^3ε^2) 的已知下限。我们的分析以跨度参数为基础，对某些实例相关方差参数进行了上界估计，这些上界比基于 MDP 的混合时间或直径的估计更紧凑，可能具有更广泛的应用。

Nov, 2023

多组别不可知的 PAC 可学习性

通过对多个带敏感性群体的个体进行损失度量，本文提出了用于处理公平性关切的多组无知 PAC 可学习性算法，该算法可以保证在涵盖多个不同的群体时仍能保证所学分类器表现一致，通过联合和扩展以前针对特定损失函数的多组公平性文献中的研究，为包含敏感性群体的学习提供了一个统一的视角。

May, 2021

固定视界强化学习的样本复杂度

本文研究了固定时间段内交互式学习智能体的表现，并从样本复杂度的角度提出了上下 PAC 确定性保证边界，为固定时间段内 MDP 的研究提供了理论上的支持。

Oct, 2015

通过生成模型在模型为基础的强化学习中突破样本量限制

研究强化学习的样本效率，证明了两种算法的最小最优性，同时实现了目标准确率的最小最优样本复杂度，这是目前首次提供涵盖整个样本范围的最小最优保证。

May, 2020

非参数通用强化学习

本文提出了在非 Markovian、非 ergodic 且只部分可观察的环境下进行强化学习的问题。作者建立了贝叶斯强化学习代理的负面结果，并证明 Thompson 采样在随机环境中是渐进最优的。此外，作者构建了一个大但可计算的类，展示了基于 Thompson 采样的代理在这个类中收敛于任意未知可计算多智能体环境中的纳什均衡。

Nov, 2016

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

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

May, 2024

当简单探索具有样本效率：确定随机探索达到 PAC RL 算法的充分条件

本研究提出了基于随机游走探索的 Q 学习的问题特定样本复杂度界限，该界限依赖于多个结构性质，并将理论结果与某些经验基准领域相关联，以说明我们的界限在这些领域中是否具有多项式样本复杂度并与经验绩效相关。

May, 2018

分布无关可靠学习

研究可靠的不可知学习框架中的问题，使用单边多项式逼近可学习可靠分类器和构建适当的单边多项式逼近来学习大多数时完全可靠，这些算法还满足强属性效率属性并提供样本复杂度和运行时间之间的平滑折衷。

Feb, 2014

一种适用于情节式 POMDP 的 PAC RL 算法

本文研究了部分可观的强化学习问题，并提出了首个具有多项式边界的算法，用于处理一类重要的 POMDP 问题，该算法基于最近的方法学方法来估计潜在变量模型。

May, 2016