解决只有终点反馈时的强化学习信用分配难题,实现高效学习。
Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits
- 设计可证明高效的算法,适用于大规模状态空间。
- 样本复杂度达$\widetilde{O}(C_{\rm cov} H^3/ε^2)$,理论最优。
- 揭示终点反馈与每步奖励间存在指数级差距,适合理论研究者。
基于结果的强化学习面临根本挑战:当仅在轨迹终点观测奖励时,如何准确为具体动作分配信用?本文首次对具有通用函数逼近能力的在线强化学习中的该问题进行系统分析。我们提出一个可证明样本高效的算法,达到$\widetilde{O}(C_{\rm cov} H^3/ε^2)$的样本复杂度,其中$C_{\rm cov}$为底层马尔可夫决策过程的覆盖系数。通过利用通用函数逼近,该方法在大规模或无限状态空间中仍有效,只需值函数和奖励函数能被相应函数类表示。结果还揭示了结果反馈在统计上与每步奖励之间的分离性,某些马尔可夫决策过程存在不可避免的指数级差异。对于确定性马尔可夫决策过程,我们消除了完备性假设,显著简化了算法。此外,我们将方法扩展至偏好反馈场景,证明即使信息更受限,也能实现等效的统计效率。这些成果共同构成了理解基于结果强化学习统计性质的理论基础。
原文摘要 · Abstract (English)
Reinforcement learning with outcome-based feedback faces a fundamental challenge: when rewards are only observed at trajectory endpoints, how do we assign credit to the right actions? This paper provides the first comprehensive analysis of this problem in online RL with general function approximation. We develop a provably sample-efficient algorithm achieving $\widetilde{O}({C_{\rm cov} H^3}/{ε^2})$ sample complexity, where $C_{\rm cov}$ is the coverability coefficient of the underlying MDP. By leveraging general function approximation, our approach works effectively in large or infinite state spaces where tabular methods fail, requiring only that value functions and reward functions can be represented by appropriate function classes. Our results also characterize when outcome-based feedback is statistically separated from per-step rewards, revealing an unavoidable exponential separation for certain MDPs. For deterministic MDPs, we show how to eliminate the completeness assumption, dramatically simplifying the algorithm. We further extend our approach to preference-based feedback settings, proving that equivalent statistical efficiency can be achieved even under more limited information. Together, these results constitute a theoretical foundation for understanding the statistical properties of outcome-based reinforcement learning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。