Abstract
We study time-inhomogeneous episodic reinforcement learning (RL) under general function approximation and sparse rewards. We design a new algorithm, Variance-weighted Optimistic $Q$-Learning (VO$Q$L), based on $Q$-learning and bound its regret assuming completeness and bounded Eluder dimension for the regression function class. As a special case, VO$Q$L achieves $\tilde{O}(d\sqrt{HT}+d^6H^{5})$ regret over $T$ episodes for a horizon $H$ MDP under ($d$-dimensional) linear function approximation, which is asymptotically optimal. Our algorithm incorporates weighted regression-based upper and lower bounds on the optimal value function to obtain this improved regret. The algorithm is computationally efficient given a regression oracle over the function class, making this the first computationally tractable and statistically optimal approach for linear MDPs.
Introduction
In Reinforcement Learning (RL), the primary objective is to minimize regret—the cumulative difference between the rewards obtained by an agent and those of an optimal policy. While the field has established optimal algorithms for tabular settings, real-world applications involve massive state spaces that necessitate the use of function approximation, such as neural networks, to generalize across states.
However, existing algorithms for function approximation frequently encounter a "triple threat" of challenges:
- Statistical Inefficiency: Regret often scales poorly with the task's horizon ($H$), leading to slow learning.
- Computational Intractability: Many theoretically sound algorithms require solving complex, often NP-hard, constrained optimization problems.
- Model-Based Constraints: Many optimal results are restricted to model-based RL, which requires learning the full transition dynamics of the environment, whereas model-free approaches are often more practical.
This paper introduces VOQL (Variance-weighted Optimistic Q-Learning), the first model-free algorithm to achieve asymptotically optimal regret for linear MDPs while supporting general nonlinear function approximation.
Methodology: Variance-weighted Optimistic Q-Learning
VOQL bridges the gap between theoretical optimality and computational tractability through several key technical innovations.
Variance-Weighted Regression
Standard Q-learning typically treats all observed transitions with equal importance. VOQL, however, weights data points by their estimated variance. This variance-weighting technique, which has been successful in tabular RL, acts as a "de-noising" mechanism. By prioritizing more certain information, the algorithm achieves a significantly improved dependence on the horizon $H$, scaling with $\sqrt{H}$ instead of $H$ or $H^2$.
The "Sandwich" of Value Estimates
A significant challenge in model-free RL is that the regression target changes as the agent updates its Q-values. To maintain stable variance estimates, VOQL employs a novel "sandwich" approach. It maintains two auxiliary value function estimates: one that is overly optimistic and one that is overly pessimistic. These bounds are used to construct a monotone variance upper bound that remains valid even as the underlying Q-function evolves during exploration.
Bonus Oracles and Eluder Dimension
To handle exploration in nonlinear settings, VOQL utilizes a refined bonus construction based on the generalized Eluder dimension. This complexity measure allows the algorithm to provide tight regret bounds for a broad class of functions. Crucially, the analysis ensures that the complexity of the exploration bonus does not dominate the overall regret, which instead depends primarily on the complexity of the value function class itself.
Computational Tractability
Unlike previous "gold standard" theoretical algorithms that required solving complex constrained optimizations, VOQL only requires access to a regression oracle. This means the algorithm can be implemented using standard model-fitting tools common in deep learning, making it the first computationally tractable approach that is also statistically optimal for linear MDPs.
Key Results
The theoretical analysis of VOQL provides rigorous regret bounds for two primary settings: linear MDPs and general function classes.
Linear MDPs
In the benchmark setting of linear MDPs, where transitions and rewards are linear functions of state-action features, VOQL achieves a regret of $\tilde{O}(d\sqrt{HT} + d^6H^5)$. The leading term, $d\sqrt{HT}$, matches the known theoretical lower bound, establishing VOQL as asymptotically optimal in terms of the number of episodes $T$.
General Function Classes
For more complex, nonlinear models, VOQL's regret scales with $\sqrt{\text{dim}(\mathcal{F}) \log \mathcal{N} \cdot HT}$, where $\text{dim}(\mathcal{F})$ represents the generalized Eluder dimension and $\mathcal{N}$ is the covering number of the function class.
As shown in the table above, VOQL matches or improves upon the regret bounds of previous state-of-the-art methods like GOLF and ELEANOR, particularly in its dependence on the horizon $H$ and total time $T$.
Discussion and Future Work
While VOQL represents a significant step forward, several avenues for future research remain. The "lower-order" terms in the regret bound, such as $d^6H^5$, are currently quite large; reducing these constants would improve the algorithm's practical performance in shorter-term learning scenarios.
Furthermore, the current analysis assumes a time-inhomogeneous environment where dynamics can change at each step of the horizon. In stable, time-homogeneous environments, it may be possible to achieve "horizon-free" regret. Finally, while the algorithm assumes a perfect regression oracle, investigating the impact of optimization errors in practical deep learning implementations is a vital next step for deploying VOQL in real-world systems.
Summary updated