Fast Non-Episodic Finite-Horizon RL with K-Step Lookahead Thresholding

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}.

Many real-world decision problems, such as medical treatment or financial trading, happen over one fixed period without repeated restarts. Standard reinforcement learning methods often learn too slowly in this setting because they try to estimate the value of each action all the way to the final time. This paper proposes a faster alternative. Instead of planning to the end, the algorithm only looks ahead for the next few steps and chooses actions whose estimated value is above a threshold. This makes learning easier and helps the agent quickly avoid clearly poor actions. The paper proves that this approach can learn much faster than standard methods in finite-horizon, non-repeating settings. Experiments on several reinforcement learning environments show that the proposed method achieves higher cumulative reward than existing tabular RL algorithms, especially when the learning horizon is limited. This shows that in finite-horizon problems where learning time is limited, quickly learning a good approximate policy can be more valuable than slowly trying to learn the exact optimal policy.