mlsanityData to 7 Oct 2026

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

arXiv 2602.00781 ↗First posted 31 Jan 2026cs.LG stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

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 O(max((K-1),CK-1)√SATlog(T)) regret for any K ≥ 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 hrefhttps://github.com/jamie01713/K-Step-Lookaheadgithub.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 29 of its 49 references that are in the map. First posted on arXiv 31 Jan 2026.

Builds on

29 of 49 references.

References · 29

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
  3. 2015Trust Region Policy Optimizationcited by 2,503
  4. 2019When to Trust Your Model: Model-Based Policy Optimizationcited by 753
  5. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  6. 2019Model-Based Reinforcement Learning for Ataricited by 495
  7. 2018Is Q-learning Provably Efficient?cited by 485
  8. 2018Time-uniform, nonparametric, nonasymptotic confidence sequencescited by 220
  9. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  10. 2020Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizabilitycited by 114
  11. 2021Recent Advances in Reinforcement Learning in Financecited by 102
  12. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 81
17 more
  1. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  2. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 41
  3. 2019Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policiescited by 38
  4. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 28
  5. 2020Improved Analysis of UCRL2 with Empirical Bernstein Inequalitycited by 18
  6. 2021Near-Optimal Randomized Exploration for Tabular Markov Decision Processescited by 14
  7. 2024Achieving Tractable Minimax Optimal Regret in Average Reward MDPscited by 13
  8. 2024A Deployed Online Reinforcement Learning Algorithm In An Oral Health Clinical Trialcited by 11
  9. 2024Reinforcement Learning with Lookahead Informationcited by 8
  10. 2021FinRL-Meta: A Universe of Near-Real Market Environments for Data-Driven Deep Reinforcement Learning in Quantitative Financecited by 6
  11. 2024reBandit: Random Effects based Online RL algorithm for Reducing Cannabis Usecited by 6
  12. 2024The Value of Reward Lookahead in Reinforcement Learningcited by 6
  13. 2024Policy Mirror Descent with Lookaheadcited by 6
  14. 2018Guaranteed satisficing and finite regret: Analysis of a cognitive satisficing value functioncited by 4
  15. 2025On the Hardness of Reinforcement Learning with Transition Look-Aheadcited by 4
  16. 2023Mastering the exploration-exploitation trade-off in Bayesian Optimizationcited by 3
  17. 2024Satisficing Regret Minimization in Bandits: Constant Rate and Light-Tailed Distributioncited by 3

Built on by

Not cited yet.