提出高效强化学习算法，解决确定性转移的线性贝尔曼完备MDP问题。
End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions
- 基于线性函数逼近与贝尔曼完备性设计新算法
- 样本与计算复杂度对时长远、特征维数和精度均多项式增长
- 适用于大或无限动作空间，仅需标准argmax查询
我们研究在满足线性贝尔曼完备性的马尔可夫决策过程（MDPs）中使用线性函数逼近的强化学习。该设定下任意线性值函数的贝尔曼备份仍为线性，虽统计上可处理，但以往高效算法受限于小动作空间或强特征空间假设。本文针对确定性转移、随机初始状态与随机奖励的场景，提出一种计算高效的算法。对于有限动作空间，算法为端到端高效；对于大或无限动作空间，仅需标准argmax oracle。算法可在多项式于时长远、特征维度及1/ε的样本与计算复杂度下，学习出ε-最优策略。
原文摘要 · Abstract (English)
We study reinforcement learning (RL) with linear function approximation in Markov Decision Processes (MDPs) satisfying \emph{linear Bellman completeness} -- a fundamental setting where the Bellman backup of any linear value function remains linear. While statistically tractable, prior computationally efficient algorithms are either limited to small action spaces or require strong oracle assumptions over the feature space. We provide a computationally efficient algorithm for linear Bellman complete MDPs with \emph{deterministic transitions}, stochastic initial states, and stochastic rewards. For finite action spaces, our algorithm is end-to-end efficient; for large or infinite action spaces, we require only a standard argmax oracle over actions. Our algorithm learns an $\varepsilon$-optimal policy with sample and computational complexity polynomial in the horizon, feature dimension, and $1/\varepsilon$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。