提出K步前瞻阈值法,加速非回合制有限时域强化学习。
Fast Non-Episodic Finite-Horizon RL with K-Step Lookahead Thresholding
- 用K步前瞻Q函数替代全时域目标,简化规划。
- 实现最小化常数级后悔率(K=1)和√(SAT log T)级后悔率(K≥2)。
- 适合需快速收敛的实时决策场景,如金融交易、游戏控制。
非回合制、有限时域马尔可夫决策过程中的在线强化学习仍研究不足,主要因需对固定终止时间估计回报。现有无限时域方法多依赖折扣收缩,难以适配固定时域结构。本文提出一种改进的Q函数:不追求全时域目标,而是学习仅前瞻未来K步的Q函数,将规划限制在最近K步内。为进一步提升样本效率,引入动态阈值机制:仅当动作的估计K步前瞻值超过随时间变化的阈值时才被选择。我们设计了一种高效的表格型学习算法,证明其可实现快速有限样本收敛:当K=1时达到最小化常数后悔率;当K≥2时,后悔率为O(max(K−1, C_{K−1})√(SAT log T))。我们在合成MDP及真实环境(JumpRiverswim、FrozenLake、AnyTrading)中评估了算法性能,结果表明其累积奖励显著优于当前最优的表格型强化学习方法。代码已公开于github。
原文摘要 · Abstract (English)
Online reinforcement learning in non-episodic, finite-horizon MDPs remains underexplored and is challenged by the need to estimate returns to a fixed terminal time. Existing infinite-horizon methods, which often rely on discounted contraction, do not naturally account for this fixed-horizon structure. We introduce a modified Q-function: rather than targeting the full-horizon, we learn a K-step lookahead Q-function that truncates planning to the next K steps. To further improve sample efficiency, we introduce a thresholding mechanism: actions are selected only when their estimated K-step lookahead value exceeds a time-varying threshold. We provide an efficient tabular learning algorithm for this novel objective, proving it achieves fast finite-sample convergence: it achieves minimax optimal constant regret for $K=1$ and $\mathcal{O}(\max((K-1),C_{K-1})\sqrt{SAT\log(T)})$ regret for any $K \geq 2$. We numerically evaluate the performance of our algorithm under the objective of maximizing reward. Our implementation adaptively increases K over time, balancing lookahead depth against estimation variance. Empirical results demonstrate superior cumulative rewards over state-of-the-art tabular RL methods across synthetic MDPs and RL environments: JumpRiverswim, FrozenLake and AnyTrading. Code is provided on \href{https://github.com/jamie01713/K-Step-Lookahead}{github}.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。