使用丰富观察的 Oracle 有效 PAC RL

Mar, 2018

On Oracle-Efficient PAC RL with Rich Observations

Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford...

TL;DR本文研究了 PAC 强化学习在富观察力下的计算复杂度，提出了基于确定性隐藏状态动态和随机富观察的可证明的样本有效算法，同时证明了在具有随机隐藏状态动态的情况下，已知样本有效算法 OLIVE 不能在 Oracle 模型中实现，通过几个示例表明了在这样一般的设置中可计算 PAC 强化学习的根本挑战。

Abstract

We study the computational tractability of pac reinforcement learning with rich observations. We present new provably sample-efficient algorithms

computational tractability pac reinforcement learning sample-efficient algorithms hidden state dynamics stochastic observations

发现论文，激发创造

基于丰富观测的 PAC 强化学习

本研究提出一种新的强化学习模型，将上下文逐步演化到顺序决策制定，通过分析最小二乘值淘汰算法表明，在某些特定情形，强化学习方法的范数较优行为可以在多项式时间内学习。

Feb, 2016

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

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

May, 2016

可观测 POMDP 中的学习，无需计算难以处理的预言机

该论文介绍了一种基于近似多项式时间算法的部分可观测马可夫决策过程无预言学习算法，该算法不是基于传统的探索 - 利用原则，而是采用几何拓扑中的重心跨度技术构建策略套接，并且通过对状态分布和观测分布的假设来保证合理性。

Jun, 2022

可证明高效的部分可观测动态系统强化学习

通过提出一种新的基于双线性 Actor-Critic 框架的学习算法，该算法可以对部分可观察的动态系统进行部分可观察的强化学习，并且在特定的情形下（如欠完备的可观察性模型）具有较高的性能表现。

Jun, 2022

PAC 强化学习用于预测状态表示

本文研究了在线强化学习在部分可观测动态系统中的应用，提出了一种基于模型的算法，通过可观测量学习了一个近似最优策略，其样本复杂度与系统的有关参数呈多项式关系。该算法自然地支持函数逼近，可处理具有潜在大状态和观测空间的系统，并且在一些特殊模型中也得到了有效应用。

Jul, 2022

具有潜在动态信息的可证明样本效率强化学习

本文研究了在观测结果高维的情况下，强化学习智能体如何使用对状态空间结构的抽象知识来学习目标领域中的任务。提出了一种名为 TASID 的算法，该算法学习目标任务的健壮策略，其采样复杂度是地平线次数的多项式，并且可以利用先前的知识独立于状态数。

May, 2022

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

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

May, 2024

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

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

May, 2018

通过潜在状态解码的丰富观测下可证明的高效强化学习

该论文研究了在具有大量从少量潜在状态生成的丰富观察结果的情节 MDPs 中的探索问题。在某些可辨识性假设下，研究人员通过一系列回归和聚类步骤归纳地估计了从观察到潜在状态的映射，并使用它构建了良好的探索策略。

Jan, 2019

有效的 PAC 学习与回应是 "是" 或者 "否" 的 Oracle 可能吗？

在本文中，我们探讨了在二分类的 PAC 学习中，是否有比经验风险最小化（ERM）更弱的预测力量仍然能够实现学习，结果表明只需多项式代价就可以使用我们的更弱预测力量来学习概念类，同时也满足了 Alon 等人提出的对于有效性学习的算法原则的要求。

Jun, 2024