# A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 51 of its 65 references that are in the map.
- First posted on arXiv 26 Nov 2023.

## Builds on (most cited first, 30 of 51)

- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Neural Architecture Search with Reinforcement Learning](https://mlsanity.com/paper/1611.01578/) (2016)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Reinforcement learning based recommender systems: A survey](https://mlsanity.com/paper/2101.06286/) (2021)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Deployment-Efficient Reinforcement Learning via Model-Based Offline Optimization](https://mlsanity.com/paper/2006.03647/) (2020)
- [Optimism in Reinforcement Learning with Generalized Linear Function Approximation](https://mlsanity.com/paper/1912.04136/) (2019)
- [Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/1905.03814/) (2019)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [Frequentist Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/1911.00567/) (2019)
- [Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles](https://mlsanity.com/paper/1910.10597/) (2019)
- [Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon](https://mlsanity.com/paper/2009.13503/) (2020)
- [Logarithmic Regret for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2011.11566/) (2020)
- [Provably Efficient Q-Learning with Low Switching Cost](https://mlsanity.com/paper/1905.12849/) (2019)
- [On Oracle-Efficient PAC RL with Rich Observations](https://mlsanity.com/paper/1803.00606/) (2018)
- [Sequential Batch Learning in Finite-Action Linear Contextual Bandits](https://mlsanity.com/paper/2004.06321/) (2020)

## Built on by (most cited first, 14 of 14)

- [Sharp Analysis for KL-Regularized Contextual Bandits and RLHF](https://mlsanity.com/paper/2411.04625/) (2024)
- [Logarithmic Regret for Online KL-Regularized Reinforcement Learning](https://mlsanity.com/paper/2502.07460/) (2025)
- [Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruption](https://mlsanity.com/paper/2402.08991/) (2024)
- [Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds](https://mlsanity.com/paper/2408.08994/) (2024)
- [Uncertainty-Aware Reward-Free Exploration with General Function Approximation](https://mlsanity.com/paper/2406.16255/) (2024)
- [Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints](https://mlsanity.com/paper/2402.01111/) (2024)
- [Catoni Contextual Bandits are Robust to Heavy-tailed Rewards](https://mlsanity.com/paper/2502.02486/) (2025)
- [Sample and Computationally Efficient Continuous-Time Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2505.14821/) (2025)
- [Beyond-Expert Performance with Limited Demonstrations: Efficient Imitation Learning with Double Exploration](https://mlsanity.com/paper/2506.20307/) (2025)
- [A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theory](https://mlsanity.com/paper/2508.07746/) (2025)
- [The Horizon Threshold in Cooperative Multi-Agent Reward-Free Exploration](https://mlsanity.com/paper/2602.01453/) (2026)
- [Provably Efficient Offline-to-Online Value Adaptation with General Function Approximation](https://mlsanity.com/paper/2604.13966/) (2026)
- [Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set](https://mlsanity.com/paper/2607.23679/) (2026)
- [Provable Benefits of Regularization: Fast Rates for Adversarial Imitation Learning](https://mlsanity.com/paper/2609.35698/) (2026)

## Abstract (arXiv)

The exploration-exploitation dilemma has been a central challenge in reinforcement learning (RL) with complex model classes. In this paper, we propose a new algorithm, Monotonic Q-Learning with Upper Confidence Bound (MQL-UCB) for RL with general function approximation. Our key algorithmic design includes (1) a general deterministic policy-switching strategy that achieves low switching cost, (2) a monotonic value function structure with carefully controlled function class complexity, and (3) a variance-weighted regression scheme that exploits historical trajectories with high data efficiency. MQL-UCB achieves minimax optimal regret of tildeO(d√HK) when K is sufficiently large and near-optimal policy switching cost of tildeO(dH), with d being the eluder dimension of the function class, H being the planning horizon, and K being the number of episodes. Our work sheds light on designing provably sample-efficient and deployment-efficient Q-learning with nonlinear function approximation.