提出高效算法求解无限时域平均奖励的线性MDP问题，实现最优后悔上界。
Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation
- 基于贝尔曼最优性条件设计可计算高效的算法
- 在线性MDP下达到新最优后悔界 $\widetilde{O}(d^{3/2}\mathrm{sp}(v^*)\sqrt{T})$
- 技术可推广至线性混合MDP，适合强化学习理论研究者
本文提出一种在贝尔曼最优性条件下，针对无限时域平均奖励线性马尔可夫决策过程（MDP）和线性混合MDP的可计算高效算法。该算法在保证计算效率的同时，对线性MDP实现了迄今为止最优的后悔上界 $\widetilde{\mathcal{O}}(d^{3/2}\mathrm{sp}(v^*)\sqrt{T})$，其中 $\mathrm{sp}(v^*)$ 为最优偏差函数 $v^*$ 的跨度，$d$ 为特征映射维度；对线性混合MDP则达到 $\widetilde{\mathcal{O}}(d\cdot\mathrm{sp}(v^*)\sqrt{T})$。算法通过新颖技术控制值函数类的覆盖数及乐观估计值函数的跨度，相关技术本身具有独立研究价值。
原文摘要 · Abstract (English)
This paper proposes a computationally tractable algorithm for learning infinite-horizon average-reward linear Markov decision processes (MDPs) and linear mixture MDPs under the Bellman optimality condition. While guaranteeing computational efficiency, our algorithm for linear MDPs achieves the best-known regret upper bound of $\widetilde{\mathcal{O}}(d^{3/2}\mathrm{sp}(v^*)\sqrt{T})$ over $T$ time steps where $\mathrm{sp}(v^*)$ is the span of the optimal bias function $v^*$ and $d$ is the dimension of the feature mapping. For linear mixture MDPs, our algorithm attains a regret bound of $\widetilde{\mathcal{O}}(d\cdot\mathrm{sp}(v^*)\sqrt{T})$. The algorithm applies novel techniques to control the covering number of the value function class and the span of optimistic estimators of the value function, which is of independent interest.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。