mlsanityData to 14 Oct 2026

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

arXiv 2212.06069 ↗First posted 12 Dec 2022cs.LG stat.MLcited by 44

Not on the map. Why?

Cited by 23 in Deep reinforcement learning methods, but placed by its own abstract, which didn’t fit.

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.

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

Builds on

0 of 0 references.

No references here yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 12; 2024: 22; 2025: 7; 2026: 3.

44 papers.

Sort:

By area:

  1. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 350
  2. 2024Building Math Agents with Multi-Turn Iterative Preference Learningcited by 66
  3. 2024Online Iterative Reinforcement Learning from Human Feedback with General Preference Modelcited by 52
  4. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 40
  5. 2024Sharp Analysis for KL-Regularized Contextual Bandits and RLHFcited by 33
  6. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 29
  7. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 26
  8. 2025Logarithmic Regret for Online KL-Regularized Reinforcement Learningcited by 22
  9. 2023Efficient Model-Free Exploration in Low-Rank MDPscited by 16
  10. 2023Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Boundscited by 14
  11. 2023Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedbackcited by 14
  12. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
32 more
  1. 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processescited by 14
  2. 2023Optimistic Natural Policy Gradient: a Simple Efficient Policy Optimization Framework for Online RLcited by 13
  3. 2024Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruptioncited by 12
  4. 2023Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximationcited by 9
  5. 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learningcited by 9
  6. 2023Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPscited by 7
  7. 2023Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learningcited by 7
  8. 2024Q-Star Meets Scalable Posterior Sampling: Bridging Theory and Practice via HyperAgentcited by 6
  9. 2024Horizon-Free Regret for Linear Markov Decision Processescited by 6
  10. 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximationcited by 6
  11. 2024Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPscited by 6
  12. 2024Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamicscited by 5
  13. 2024Uncertainty-Aware Reward-Free Exploration with General Function Approximationcited by 5
  14. 2024Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processescited by 5
  15. 2024Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actionscited by 4
  16. 2024Provable Risk-Sensitive Distributional Reinforcement Learning with General Function Approximationcited by 3
  17. 2024Achieving Constant Regret in Linear Markov Decision Processescited by 3
  18. 2025Catoni Contextual Bandits are Robust to Heavy-tailed Rewardscited by 3
  19. 2025Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Gamescited by 3
  20. 2026Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrabilitycited by 3
  21. 2024Prior-dependent analysis of posterior sampling reinforcement learning with function approximationcited by 2
  22. 2025Minimax Optimal Reinforcement Learning with Quasi-Optimismcited by 2
  23. 2025Near-Optimal Second-Order Guarantees for Model-Based Adversarial Imitation Learningcited by 2
  24. 2025Variance-Aware Feel-Good Thompson Sampling for Contextual Banditscited by 2
  25. 2024Policy Zooming: Adaptive Discretization-based Infinite-Horizon Average-Reward Reinforcement Learningcited by 1
  26. 2024Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Spancited by 1
  27. 2024Near-Optimal Reinforcement Learning with Shuffle Differential Privacycited by 1
  28. 2025Beyond-Expert Performance with Limited Demonstrations: Efficient Imitation Learning with Double Explorationcited by 1
  29. 2024Building Socially-Equitable Public Modelscited by 0
  30. 2024Bellman Unbiasedness: Toward Provably Efficient Distributional Reinforcement Learning with General Value Function Approximationcited by 0
  31. 2026Provably Efficient Offline-to-Online Value Adaptation with General Function Approximationcited by 0
  32. 2026Improved Model-based Reinforcement Learning with Smooth Kernelscited by 0