提出新算法，高效解决无限时域强化学习难题。
Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learning
- 融合奖励加成与虚拟吸收态，实现乐观探索
- 达到最优后悔率，误差随样本数平方根增长
- 适用于对抗性奖励与模仿学习，效果领先
研究无限时域折扣线性马尔可夫决策过程中的强化学习问题，提出首个计算高效且具备率最优后悔保证的算法。核心思想是结合两种经典乐观探索技术：对奖励函数添加增量奖励项，以及向最大回报的吸收态引入人工转移。结合正则化近似动态规划方案后，该算法在总样本转移数为T、折扣因子γ∈(0,1)、特征维度d的情况下，实现了$ ilde{ ext{O}}( ext{sqrt}{d^3 (1 - γ)^{-7/2} T})$的后悔率。该结果在对抗性奖励序列下依然成立，从而可用于线性MDP中的模仿学习，并取得当前最佳性能。
原文摘要 · Abstract (English)
We study the problem of reinforcement learning in infinite-horizon discounted linear Markov decision processes (MDPs), and propose the first computationally efficient algorithm achieving rate-optimal regret guarantees in this setting. Our main idea is to combine two classic techniques for optimistic exploration: additive exploration bonuses applied to the reward function, and artificial transitions made to an absorbing state with maximal return. We show that, combined with a regularized approximate dynamic-programming scheme, the resulting algorithm achieves a regret of order $\tilde{\mathcal{O}} (\sqrt{d^3 (1 - γ)^{- 7 / 2} T})$, where $T$ is the total number of sample transitions, $γ\in (0,1)$ is the discount factor, and $d$ is the feature dimensionality. The results continue to hold against adversarial reward sequences, enabling application of our method to the problem of imitation learning in linear MDPs, where we achieve state-of-the-art results.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。