提出高效算法学习无限时域平均奖励线性混合MDP，实现近最优后悔上界。
Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Span
- 基于折扣奖励近似与跨度剪裁的值迭代方法
- 达到$ ilde{ m O}(d oot d m{sp}(v^*)T)$的近极小极大后悔上界
- 适用于高维特征下在线强化学习，适合研究者参考
本文提出一种计算上可行的算法，用于在贝尔曼最优条件下学习无限时域平均奖励线性混合马尔可夫决策过程（MDP）。该算法对线性混合MDP实现了近乎极小极大的后悔上界 $ ilde{ m O}(d oot d m{sp}(v^*)T)$，其中 $ m{sp}(v^*)$ 为最优偏置函数 $v^*$ 的跨度，$d$ 为特征映射的维度。算法采用近期发展的技术：在折扣奖励近似上运行值迭代，并通过跨度进行剪裁。我们证明即使存在剪裁操作，值迭代仍能收敛；且在随机转移下相关方差项依然可被控制。结合基于加权岭回归的参数估计方案，最终获得近乎极小极大的后悔保证。
原文摘要 · Abstract (English)
This paper proposes a computationally tractable algorithm for learning infinite-horizon average-reward linear mixture Markov decision processes (MDPs) under the Bellman optimality condition. Our algorithm for linear mixture MDPs achieves a nearly minimax optimal regret upper bound of $\widetilde{\mathcal{O}}(d\sqrt{\mathrm{sp}(v^*)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. Our algorithm applies the recently developed technique of running value iteration on a discounted-reward MDP approximation with clipping by the span. We prove that the value iteration procedure, even with the clipping operation, converges. Moreover, we show that the associated variance term due to random transitions can be bounded even under clipping. Combined with the weighted ridge regression-based parameter estimation scheme, this leads to the nearly minimax optimal regret guarantee.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。