厘清强化学习中最小必要预言机，揭示不同假设对算法复杂度的影响。
Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning
- 提出两上下文回归为块马尔可夫决策过程的最小预言机
- 在重置模型下，一上下文回归接近最优，证明重置有计算优势
- 在低秩马尔可夫决策过程中，原预言机不充分，具密码学证据
强化学习在大规模状态空间中的算法严重依赖监督学习子程序来估计价值函数或转移概率。由于仅有最简单的监督学习问题能被高效且可证明地求解，实际性能取决于所假设的监督学习‘预言机’及其实现方式。但哪些预言机更优？是否存在最小预言机？本文阐明了预言机选择对强化学习计算复杂度的影响，以预言机强度量化。首先，在标准回合访问模型下的奖励无关探索（块马尔可夫决策过程），我们识别出两上下文回归为最小预言机，即在温和正则性假设下既必要又充分。其次，在更强的重置访问模型中，我们发现一上下文回归为近似最小预言机，证明了重置带来的可证明计算优势。第三，将研究拓展至低秩马尔可夫决策过程，给出密码学证据表明块马尔可夫决策过程中的对应预言机不足。
原文摘要 · Abstract (English)
Algorithms for reinforcement learning (RL) in large state spaces crucially rely on supervised learning subroutines to estimate objects such as value functions or transition probabilities. Since only the simplest supervised learning problems can be solved provably and efficiently, practical performance of an RL algorithm depends on which of these supervised learning "oracles" it assumes access to (and how they are implemented). But which oracles are better or worse? Is there a minimal oracle? In this work, we clarify the impact of the choice of supervised learning oracle on the computational complexity of RL, as quantified by the oracle strength. First, for the task of reward-free exploration in Block MDPs in the standard episodic access model -- a ubiquitous setting for RL with function approximation -- we identify two-context regression as a minimal oracle, i.e. an oracle that is both necessary and sufficient (under a mild regularity assumption). Second, we identify one-context regression as a near-minimal oracle in the stronger reset access model, establishing a provable computational benefit of resets in the process. Third, we broaden our focus to Low-Rank MDPs, where we give cryptographic evidence that the analogous oracle from the Block MDP setting is insufficient.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。