mlsanityData to 14 Oct 2026

Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPs

arXiv 2302.12456 ↗First posted 24 Feb 2023cs.LG cs.AI stat.MLcited by 9

Not on the map. Why?

Abstract (arXiv)

In many real-life reinforcement learning (RL) problems, deploying new policies is costly. In those scenarios, algorithms must solve exploration (which requires adaptivity) while switching the deployed policy sparsely (which limits adaptivity). In this paper, we go beyond the existing state-of-the-art on this problem that focused on linear Markov Decision Processes (MDPs) by considering linear Bellman-complete MDPs with low inherent Bellman error. We propose the ELEANOR-LowSwitching algorithm that achieves the near-optimal regret with a switching cost logarithmic in the number of episodes and linear in the time-horizon H and feature dimension d. We also prove a lower bound proportional to dH among all algorithms with sublinear regret. In addition, we show the ``doubling trick'' used in ELEANOR-LowSwitching can be further leveraged for the generalized linear function approximation, under which we design a sample-efficient algorithm with near-optimal switching cost.

Key facts. Cited by 9 papers in the map (data through 14 Oct 2026). Builds on 21 of its 35 references that are in the map. First posted on arXiv 24 Feb 2023.

Builds on

21 of 35 references.

References · 21

  1. 2019Reinforcement Learning in Healthcare: A Surveycited by 310
  2. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  3. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  4. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  5. 2018Optimization of Molecules via Deep Reinforcement Learningcited by 200
  6. 2021Reinforcement learning based recommender systems: A surveycited by 188
  7. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  8. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  9. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  10. 2020Deployment-Efficient Reinforcement Learning via Model-Based Offline Optimizationcited by 120
  11. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  12. 2019Batched Multi-armed Bandits Problemcited by 98
9 more
  1. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  2. 2019Provably Efficient Q-Learning with Low Switching Costcited by 78
  3. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 40
  4. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  5. 2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
  6. 2022Off-Policy Fitted Q-Evaluation with Differentiable Function Approximators: Z-Estimation and Inference Theorycited by 18
  7. 2022Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximationcited by 13
  8. 2022Near-Optimal Regret Bounds for Multi-batch Reinforcement Learningcited by 13
  9. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 4; 2024: 3; 2025: 1; 2026: 1.

9 papers.

  1. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
  2. 2024Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizescited by 12
  3. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  4. 2023A General Framework for Sequential Decision-Making under Adaptivity Constraintscited by 6
  5. 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 4
  6. 2023Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivitycited by 2
  7. 2024Differentially Private Reinforcement Learning with Self-Playcited by 1
  8. 2025A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theorycited by 1
  9. 2026Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimationcited by 0