Research map / Reinforcement learning / MDPs and planning
A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MQL-UCB, a Markov Q-learning algorithm for general function approximation with bounded eluder dimension that uses a deterministic uncertainty-based rare-switching rule to achieve O~(dH) switching cost and near-minimax regret.
Problem
Regret minimization and low policy-switching cost (deployment efficiency) for episodic RL with general nonlinear function approximation, where prior methods either had O~(d^2 H) switching cost, intractable planning, or were not statistically optimal.
Approach
A deterministic policy-switching rule based on cumulative generalized eluder-dimension (D_F^2) sensitivity of weighted historical data, combined with monotonic optimistic/pessimistic value functions and variance-weighted regression, yields Markov policies with O(dH) switches and near-minimax regret.
Key results
- MQL-UCB achieves regret O~(sqrt(dim(F) log N * H K)) for large K, matching minimax optimal rate for linear MDPs up to log factors.
- Switching cost of O(dim(F) H) (O~(dH) for linear MDPs), improving over prior O(d^2 H) for deterministic rare-switching.
- Proves a lower bound of Omega~(dH) switching cost for any algorithm (deterministic or stochastic) in linear MDPs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MQL-UCB's sensitivity-based deterministic policy-switching strategy instead of VOQL's switching approach | RL with bounded eluder dimension and completeness · Bounded eluder dimension + completeness | number of switches: \tilde O(\dim(\cF)^2H) -> \tilde O(\dim(\cF)H) | Helped |
| Use MQL-UCB instead of VOQL | RL with bounded eluder dimension and completeness · Bounded eluder dimension + completeness | regret: \sqrt{\dim(\cF) \log N \cdot H K} | No clear effect |
| Use MQL-UCB instead of LSVI-UCB++ | Linear MDPs · Linear MDPs | regret: d\sqrt{ H K} | No clear effect |
| Use MQL-UCB instead of LSVI-UCB++ | Linear MDPs · Linear MDPs | number of switches: \tilde{O}(dH) | No clear effect |
Surprising findings
- The paper notes a technical flaw in a prior remark relating generalized eluder dimension to standard eluder dimension (Remark 4 of Wang et al.).
Limitations
- Requires completeness assumption including second-moment Bellman operator and bonus oracle with bounded covering number.
- Lower-order regret term H^{2.5} d^5 sqrt(H+d^2) is large; minimax optimality holds only when K is sufficiently large.
Experimental setup
Metrics: regret switching cost
Baselines: VOQL LSVI-UCB++ LSVI-UCB LSVI-UCB-RareSwitch GOLF F-LSVI
Builds on: VOQL LSVI-UCB++ LSVI-UCB LSVI-UCB-RareSwitch generalized eluder dimension
Closest papers by meaning
- A General Framework for Sample-Efficient Function Approximation in Reinforcement Learning (ICLR 2023 · similarity 0.90)
- Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension (NeurIPS 2020 · similarity 0.89)
- Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation (NeurIPS 2024 · similarity 0.89)
- Regularized Q-Learning (NeurIPS 2024 · similarity 0.89)
- Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning (NeurIPS 2025 · similarity 0.88)
- Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge (AAAI 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.