Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning

📄 arXiv: 2404.03774v1 📥 PDF

作者: Noah Golowich, Ankur Moitra, Dhruv Rohatgi

分类: cs.LG, cs.CC, cs.CR, cs.DS

发布日期: 2024-04-04

备注: 112 pages, 3 figures

💡 一句话要点

提出区分强化学习与监督学习的加密方法

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

关键词: 强化学习 监督学习 计算复杂性 区块MDP 加密分离 回归问题 LPN假设 探索策略

📋 核心要点

  1. 现有方法未能有效区分强化学习与监督学习的计算复杂性，导致对强化学习的理解不足。
  2. 论文通过构造特定的区块MDP和解码函数，展示了无奖励探索在计算上比回归问题更为困难的现象。
  3. 研究结果表明，即使有回归问题的预言机，针对奖励导向的强化学习也无法实现有效的计算，揭示了新的复杂性界限。

📝 摘要（中文）

监督学习在实践中通常计算上较为简单，但这是否意味着强化学习（RL）也应当如此？本文首次展示了强化学习与监督学习之间的加密分离，构造了一类区块马尔可夫决策过程（MDP）及相关解码函数，证明了无奖励探索在计算上比相关回归问题更为困难。我们还展示了即使在区块MDP中，针对奖励导向的强化学习也不存在计算上有效的算法，即使有回归问题的预言机可用。我们的结果表明，能够在区块MDP中进行回归并不足以找到良好的策略。分离下界利用了学习带噪声的平衡（LPN）难度假设的新鲁棒性特性，这对于处理RL数据的依赖性至关重要。

🔬 方法详解

问题定义：本文旨在解决强化学习与监督学习之间的计算复杂性分离问题。现有方法未能充分揭示强化学习的计算瓶颈，导致对其复杂性的理解不足。

核心思路：论文提出通过构造特定的区块MDP和解码函数，证明无奖励探索的计算复杂性高于相关回归问题，从而实现强化学习与监督学习的加密分离。

技术框架：整体架构包括构造区块MDP、定义解码函数以及分析其计算复杂性。主要模块包括区块MDP的设计、回归问题的定义及其与RL的关系分析。

关键创新：最重要的技术创新在于首次展示了强化学习与监督学习之间的加密分离，利用LPN难度假设的新鲁棒性特性，处理了RL数据的依赖性问题。

关键设计：关键设计包括对区块MDP的具体构造、解码函数的定义，以及在分析中使用的LPN难度假设的鲁棒性特性。

📊 实验亮点

实验结果表明，在区块MDP中，无奖励探索的计算复杂性显著高于相关回归问题，且即使有回归问题的预言机，奖励导向的强化学习仍无法实现有效计算。这一发现为理解强化学习的计算瓶颈提供了新的视角。

🎯 应用场景

该研究的潜在应用领域包括强化学习算法的设计与优化，尤其是在需要高效探索的复杂环境中。通过明确强化学习与监督学习的计算复杂性差异，可以为算法开发提供更清晰的理论基础，推动智能体在实际应用中的表现提升。

📄 摘要（原文）

Supervised learning is often computationally easy in practice. But to what extent does this mean that other modes of learning, such as reinforcement learning (RL), ought to be computationally easy by extension? In this work we show the first cryptographic separation between RL and supervised learning, by exhibiting a class of block MDPs and associated decoding functions where reward-free exploration is provably computationally harder than the associated regression problem. We also show that there is no computationally efficient algorithm for reward-directed RL in block MDPs, even when given access to an oracle for this regression problem. It is known that being able to perform regression in block MDPs is necessary for finding a good policy; our results suggest that it is not sufficient. Our separation lower bound uses a new robustness property of the Learning Parities with Noise (LPN) hardness assumption, which is crucial in handling the dependent nature of RL data. We argue that separations and oracle lower bounds, such as ours, are a more meaningful way to prove hardness of learning because the constructions better reflect the practical reality that supervised learning by itself is often not the computational bottleneck.