Introduction
Reinforcement learning (RL) in environments with massive or infinite state and action spaces often relies on function approximation. A prominent theoretical framework for this is the linear kernel Markov Decision Process (MDP), where transition probabilities are represented using linear function approximation. While episodic RL has seen extensive theoretical development, infinite-horizon discounted MDPs—where an agent interacts with the environment indefinitely and future rewards are discounted by a factor $\gamma \in (0, 1)$—present unique challenges.
This paper addresses a critical gap in the theoretical guarantees for such settings, introducing UPAC-UCLK, the first algorithm to achieve a "uniform-PAC" (Probably Approximately Correct) sample complexity bound for infinite-horizon discounted MDPs using linear function approximation.
The Shortcoming of Regret Bounds
Historically, state-of-the-art algorithms for linear kernel MDPs, such as UCLK, have provided guarantees strictly in terms of regret bounds. While regret is a highly useful metric in episodic RL where the agent periodically resets, it falls short in infinite-horizon settings. Specifically, an algorithm can achieve a sublinear regret bound but still make $\epsilon$-sized errors infinitely often. This means the agent might never truly converge to the optimal policy.
To resolve this, the authors target a uniform-PAC guarantee. A uniform-PAC bound strictly limits the total number of times an agent can ever take a highly suboptimal action, ensuring true convergence. Prior to this work, no algorithm had achieved a polynomial sample complexity bound for this specific setting without relying on a generative model.
Methodology: UPAC-UCLK and Discounted Data Inheritance
The authors propose the Uniform-PAC Upper-Confidence Linear Kernel (UPAC-UCLK) algorithm. Building upon the existing UCLK framework, UPAC-UCLK introduces a multi-level partition scheme to secure the uniform-PAC guarantee.
A major technical hurdle in infinite-horizon RL is that the value function changes at every single time step. To manage this, the algorithm separates time steps and their corresponding data into different "levels" based on the uncertainty of the model's predictions. However, in an infinite horizon, this theoretically requires infinite levels. When a new level is activated, it starts with no data, leading to a "cold start" problem characterized by massive uncertainty, huge confidence intervals, and wildly inaccurate value estimates.
To solve this, the authors introduce a novel technique called Discounted Data Inheritance. UPAC-UCLK allows newly activated levels to inherit data from lower levels. To prevent old data from overwhelming the new levels and breaking the theoretical bounds, the inherited data is exponentially discounted. This mathematical bridge "warm-starts" new levels with just enough information to keep confidence sets small, allowing the algorithm to smoothly update its value functions step after step. Furthermore, the authors introduce a novel mathematical method to decompose the difference between consecutive value functions and express it using changes in their confidence ellipsoids.
Key Theoretical Results
The primary contribution of this paper is the first $O(1/\epsilon^2)$ sample complexity bound for infinite-horizon discounted RL with linear function approximation. Specifically, UPAC-UCLK achieves a uniform-PAC sample complexity of:
$$ \tilde{O}\left(\frac{d^2}{(1-\gamma)^4 \epsilon^2} + \frac{1}{(1-\gamma)^6 \epsilon^2}\right) $$
where $d$ is the feature dimension, $\gamma$ is the discount factor, and $\epsilon$ is the target accuracy. Crucially, these bounds depend on the feature dimension $d$ rather than the raw number of states $|S|$ or actions $|A|$, proving the algorithm is theoretically efficient even for massive environments.
Because uniform-PAC is a strictly stronger guarantee than regret, this result automatically implies a high-probability regret bound of $\tilde{O}\left(\frac{d\sqrt{T}}{(1-\gamma)^2} + \frac{\sqrt{T}}{(1-\gamma)^3}\right)$ for the first $T$ steps.
Limitations and Future Work
While the sample complexity bound is polynomial and groundbreaking for this setting, the authors acknowledge it is likely not perfectly tight. The sample complexity contains an extra $\tilde{O}(1/((1-\gamma)^6 \epsilon^2))$ term stemming from their Multi-Level Extended Value Iteration (ML-EVI) analysis. Consequently, the implied regret bound suffers from an extra $\tilde{O}(\sqrt{T}/(1-\gamma)^3)$ term compared to previous regret-only algorithms.
The primary direction for future work is to tighten these bounds to achieve minimax optimal sample complexity, effectively removing these extra terms while preserving the strong uniform-PAC guarantee.
Summary updated