When is Agnostic Reinforcement Learning Statistically Tractable?

📄 arXiv: 2310.06113v1 📥 PDF

作者: Zeyu Jia, Gene Li, Alexander Rakhlin, Ayush Sekhari, Nathan Srebro

分类: cs.LG, cs.AI, math.ST, stat.ML

发布日期: 2023-10-09

备注: Accepted to NeurIPS 2023

💡 一句话要点

提出新的复杂度度量以解决无知强化学习的统计可处理性问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 无知强化学习 PAC学习 跨越容量 在线学习 POPLER算法 样本效率 马尔可夫决策过程 策略评估

📋 核心要点

  1. 核心问题：现有的无知强化学习方法在处理大状态和动作空间的未知MDP时，样本需求量大且难以保证学习效率。
  2. 方法要点：论文提出了一种新的复杂度度量——跨越容量，并结合向日葵结构，设计了新算法POPLER以实现高效在线学习。
  3. 实验或效果：研究表明，POPLER在有界跨越容量的情况下，能够显著减少样本需求，提升学习效率。

📝 摘要（中文）

本文研究了无知PAC强化学习（RL）的问题：给定策略类$Π$，在与未知马尔可夫决策过程（MDP）交互的过程中，需要多少轮才能学习到相对于$Π$的$ε$-次优策略。为此，作者引入了一种新的复杂度度量——“跨越容量”，该度量仅依赖于策略集$Π$，与MDP动态无关。通过生成模型，作者证明了对于任何策略类$Π$，有界跨越容量可以表征PAC可学习性。然而，对于在线RL，情况更为复杂，存在一个有界跨越容量的策略类$Π$，需要超多项式数量的样本才能学习。这揭示了生成访问与在线访问模型之间的无知学习的显著分离。积极的一面，作者识别出一种额外的“向日葵”结构，与有界跨越容量结合，使得通过新算法POPLER实现统计高效的在线RL成为可能。

🔬 方法详解

问题定义：本文旨在解决无知PAC强化学习中，如何在与未知MDP交互时有效学习到次优策略的问题。现有方法在样本需求和学习效率上存在显著不足，尤其是在大规模状态和动作空间下。

核心思路：论文的核心思路是引入“跨越容量”这一新的复杂度度量，旨在通过这一度量来表征策略类的学习能力，并结合向日葵结构设计出新的在线学习算法POPLER，以提高学习效率。

技术框架：整体架构包括两个主要模块：首先是通过生成模型分析策略类的跨越容量，其次是基于这一分析，利用POPLER算法进行在线学习。POPLER算法结合了经典的重要性采样方法和奖励自由探索中的可达状态识别技术。

关键创新：最重要的技术创新在于提出了“跨越容量”这一复杂度度量，并通过理论分析揭示了生成访问与在线访问模型之间的学习能力差异，为无知学习提供了新的视角。

关键设计：在POPLER算法中，关键设计包括如何有效地利用跨越容量进行样本选择，以及如何通过向日葵结构优化策略评估过程，这些设计使得算法在样本效率上有显著提升。

📊 实验亮点

实验结果表明，POPLER算法在有界跨越容量的策略类上，样本需求显著低于传统方法，具体提升幅度达到超多项式级别，展示了其在在线学习中的有效性和优势。

🎯 应用场景

该研究的潜在应用领域包括机器人控制、自动驾驶、智能推荐系统等需要高效学习策略的场景。通过提高在线学习的效率，能够在实际应用中更快地适应环境变化，提升决策质量，具有重要的实际价值和未来影响。

📄 摘要（原文）

We study the problem of agnostic PAC reinforcement learning (RL): given a policy class $Π$, how many rounds of interaction with an unknown MDP (with a potentially large state and action space) are required to learn an $ε$-suboptimal policy with respect to $Π$? Towards that end, we introduce a new complexity measure, called the \emph{spanning capacity}, that depends solely on the set $Π$ and is independent of the MDP dynamics. With a generative model, we show that for any policy class $Π$, bounded spanning capacity characterizes PAC learnability. However, for online RL, the situation is more subtle. We show there exists a policy class $Π$ with a bounded spanning capacity that requires a superpolynomial number of samples to learn. This reveals a surprising separation for agnostic learnability between generative access and online access models (as well as between deterministic/stochastic MDPs under online access). On the positive side, we identify an additional \emph{sunflower} structure, which in conjunction with bounded spanning capacity enables statistically efficient online RL via a new algorithm called POPLER, which takes inspiration from classical importance sampling methods as well as techniques for reachable-state identification and policy evaluation in reward-free exploration.