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

2026-01-31 · Jiamin Xu, Kyra Gan 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 $\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}.

📄 PDF Abstract BibTeX arXiv:2602.00781

Code (0)

등록된 구현이 없습니다.

Tasks

Reinforcement Learning

Recursive Two-Step Lookahead Expected Payoff for Time-Dependent Bayesian Optimization

2020-06-14 · S. Ashwin Renganathan, Jeffrey Larson, Stefan Wild

We propose a novel Bayesian method to solve the maximization of a time-dependent expensive-to-evaluate oracle. We are interested in the decision that maximizes the oracle at a finite time horizon, when relatively few noi…

Bayesian Optimization Vocal Bursts Valence Prediction

Policy Mirror Descent with Lookahead

2024-03-21 · Kimon Protopapas, Anas Barakat

Policy Mirror Descent (PMD) stands as a versatile algorithmic framework encompassing several seminal policy gradient algorithms such as natural policy gradient, with connections with state-of-the-art reinforcement learni…

Reinforcement Learning (RL)

Theoretical Guarantees of Fictitious Discount Algorithms for Episodic Reinforcement Learning and Global Convergence of Policy Gradient Methods

2021-09-13 · Xin Guo, Anran Hu, Junzi Zhang

When designing algorithms for finite-time-horizon episodic reinforcement learning problems, a common approach is to introduce a fictitious discount factor and use stationary policies for approximations. Empirically, it h…

Policy Gradient Methods reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

On the Convergence of Monte Carlo UCB for Random-Length Episodic MDPs

2022-09-07 · Zixuan Dong, Che Wang, Keith Ross

In reinforcement learning, Monte Carlo algorithms update the Q function by averaging the episodic returns. In the Monte Carlo UCB (MC-UCB) algorithm, the action taken in each state is the action that maximizes the Q func…

Open-Ended Question Answering Q-Learning

Logarithmic regret for episodic continuous-time linear-quadratic reinforcement learning over a finite-time horizon

2020-06-27 · Matteo Basei, Xin Guo, Anran Hu, Yufei Zhang

We study finite-time horizon continuous-time linear-quadratic reinforcement learning problems in an episodic setting, where both the state and control coefficients are unknown to the controller. We first propose a least-…

parameter estimation Reinforcement Learning (RL)