# VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation

arXiv: https://arxiv.org/abs/2212.06069 · HTML: https://mlsanity.com/paper/2212.06069/

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Dec 2022.

## Built on by (most cited first, 30 of 44)

- [Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint](https://mlsanity.com/paper/2312.11456/) (2023)
- [Building Math Agents with Multi-Turn Iterative Preference Learning](https://mlsanity.com/paper/2409.02392/) (2024)
- [Online Iterative Reinforcement Learning from Human Feedback with General Preference Model](https://mlsanity.com/paper/2402.07314/) (2024)
- [Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency](https://mlsanity.com/paper/2302.10371/) (2023)
- [Sharp Analysis for KL-Regularized Contextual Bandits and RLHF](https://mlsanity.com/paper/2411.04625/) (2024)
- [A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes](https://mlsanity.com/paper/2305.08841/) (2023)
- [Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms](https://mlsanity.com/paper/2404.03578/) (2024)
- [Logarithmic Regret for Online KL-Regularized Reinforcement Learning](https://mlsanity.com/paper/2502.07460/) (2025)
- [Efficient Model-Free Exploration in Low-Rank MDPs](https://mlsanity.com/paper/2307.03997/) (2023)
- [Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Bounds](https://mlsanity.com/paper/2306.06836/) (2023)
- [Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedback](https://mlsanity.com/paper/2307.02842/) (2023)
- [A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2311.15238/) (2023)
- [Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processes](https://mlsanity.com/paper/2403.12946/) (2024)
- [Optimistic Natural Policy Gradient: a Simple Efficient Policy Optimization Framework for Online RL](https://mlsanity.com/paper/2305.11032/) (2023)
- [Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruption](https://mlsanity.com/paper/2402.08991/) (2024)
- [Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation](https://mlsanity.com/paper/2305.06446/) (2023)
- [Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning](https://mlsanity.com/paper/2310.01380/) (2023)
- [Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs](https://mlsanity.com/paper/2303.10165/) (2023)
- [Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learning](https://mlsanity.com/paper/2310.20007/) (2023)
- [Q-Star Meets Scalable Posterior Sampling: Bridging Theory and Practice via HyperAgent](https://mlsanity.com/paper/2402.10228/) (2024)
- [Horizon-Free Regret for Linear Markov Decision Processes](https://mlsanity.com/paper/2403.10738/) (2024)
- [Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation](https://mlsanity.com/paper/2404.12648/) (2024)
- [Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPs](https://mlsanity.com/paper/2408.04526/) (2024)
- [Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamics](https://mlsanity.com/paper/2406.11810/) (2024)
- [Uncertainty-Aware Reward-Free Exploration with General Function Approximation](https://mlsanity.com/paper/2406.16255/) (2024)
- [Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processes](https://mlsanity.com/paper/2407.03065/) (2024)
- [Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actions](https://mlsanity.com/paper/2406.11640/) (2024)
- [Provable Risk-Sensitive Distributional Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2402.18159/) (2024)
- [Achieving Constant Regret in Linear Markov Decision Processes](https://mlsanity.com/paper/2404.10745/) (2024)
- [Catoni Contextual Bandits are Robust to Heavy-tailed Rewards](https://mlsanity.com/paper/2502.02486/) (2025)

## Abstract (arXiv)

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 (VOQL), based on Q-learning and bound its regret assuming completeness and bounded Eluder dimension for the regression function class. As a special case, VOQL achieves tildeO(d√HT+d6H5) 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.