Abstract
Recently, there has been remarkable progress in reinforcement learning (RL) with general function approximation. However, all these works only provide regret or sample complexity guarantees. It is still an open question if one can achieve stronger performance guarantees, i.e., the uniform probably approximate correctness (Uniform-PAC) guarantee that can imply both a sub-linear regret bound and a polynomial sample complexity for any target learning accuracy. We study this problem by proposing algorithms for both nonlinear bandits and model-based episodic RL using the general function class with a bounded eluder dimension. The key idea of the proposed algorithms is to assign each action to different levels according to its width with respect to the confidence set. The achieved Uniform-PAC sample complexity is tight in the sense that it matches the state-of-the-art regret bounds or sample complexity guarantees when reduced to the linear case. To the best of our knowledge, this is the first work for Uniform-PAC guarantees on bandit and RL that goes beyond linear cases.
Introduction
In the field of reinforcement learning (RL), performance is typically measured using either Regret Bounds (the cumulative reward loss during learning) or PAC Bounds (the number of samples required to reach a specific accuracy $\epsilon$). While both are valuable, they have inherent limitations. A low-regret algorithm does not necessarily converge to an optimal policy, and standard PAC bounds are often tied to a pre-selected, fixed $\epsilon$.
The "gold standard" for performance guarantees is Uniform-PAC. A Uniform-PAC guarantee provides an upper bound on the number of $\epsilon$-suboptimal episodes for any accuracy level $\epsilon > 0$ simultaneously. This implies both sub-linear regret and polynomial sample complexity. While Uniform-PAC results have been established for tabular and linear RL, achieving them for general function approximation—where complex nonlinear models are used—has remained an open challenge.
Methodology: Multi-Level Partitioning
The authors propose two novel algorithms: $\mathcal{F}$-UPAC-OFUL for nonlinear bandits and $\mathcal{F}$-UPAC-VTR for model-based episodic RL.
The central innovation is a multi-level partition scheme. Conventional algorithms often maintain a single confidence set. In contrast, these new algorithms categorize actions (or state-action pairs) into different "levels" based on their width, which represents the uncertainty relative to the current confidence set.
- Actions with high uncertainty remain at lower levels.
- As more data is collected and uncertainty decreases, actions are promoted to higher levels (e.g., level $l$ corresponds to uncertainty scales around $2^{-l}$).
To quantify the complexity of nonlinear models, the work utilizes the eluder dimension ($d_E$) and metric entropy ($d_K$). The eluder dimension generalizes linear independence to nonlinear spaces, capturing how many samples are needed to uniquely determine a function.
Key Results
The proposed algorithms achieve state-of-the-art performance while providing the first Uniform-PAC guarantees for general function classes.
Nonlinear Bandits
The $\mathcal{F}$-UPAC-OFUL algorithm achieves a Uniform-PAC sample complexity of $\tilde{O}(d_K d_E / \epsilon^2)$. As shown in the comparison below, this matches the regret performance of existing linear and general bandit algorithms while being the first to offer Uniform-PAC guarantees for general reward functions.
Model-Based RL
For episodic RL, the $\mathcal{F}$-UPAC-VTR algorithm achieves a complexity of $\tilde{O}(H^3 d_K d_E / \epsilon^2)$, where $H$ is the horizon length. This result implies a regret bound of $\tilde{O}(\sqrt{H^3 d_K d_E K})$, matching the best-known results in the literature for model-based RL with general function approximation.
Discussion and Future Work
While these algorithms are sample-efficient, they face challenges in computational efficiency. Finding the most optimistic function within a general nonlinear confidence set is typically an NP-hard optimization problem.
Furthermore, the current work relies on the eluder dimension. Extending these Uniform-PAC guarantees to even broader complexity measures, such as the Bellman eluder dimension or bilinear classes, is a significant future hurdle because these measures do not easily support "instance-wise" error estimation. Finally, extending these strong guarantees to model-free RL settings remains a promising direction for future research.
Summary updated