Fast Non-Episodic Finite-Horizon RL with K-Step Lookahead Thresholding
For researchers in reinforcement learning, this provides a novel algorithm for finite-horizon non-episodic settings that is both theoretically sound and empirically effective.
The paper tackles online reinforcement learning in non-episodic, finite-horizon MDPs by introducing a K-step lookahead Q-function with thresholding, achieving minimax optimal constant regret for K=1 and O(max((K-1),C_{K-1})√(SAT log(T))) regret for K≥2, with superior cumulative rewards over state-of-the-art methods in synthetic and RL environments.
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}.