Reinforcement Learning with Low Switching Cost

This direction is merged into another direction: logarithmic update scheduling. Its last version stays readable and citable here.

Version 1 of 121 papers25 conceptsfrozen 2026-10-04

In standard reinforcement learning (RL) theory, an agent is usually depicted as a nimble learner that updates its strategy after every single interaction with the environment. However, in the real world, changing a policy is rarely free. In clinical trials, a doctor cannot change the treatment protocol for every new patient; in online advertising, updating a neural network every millisecond is computationally prohibitive; and in industrial systems, frequent strategy shifts can cause physical wear or operational instability.

This practical constraint has birthed a research direction focused on low switching cost or batched learning. The goal is to achieve near-optimal performance (low regret) while updating the deployed policy as infrequently as possible.

The Interactivity Gap

The fundamental tension in sequential decision-making is between adaptivity and efficiency. To minimize regret, an agent must use new data to correct its mistakes. Fully sequential algorithms like standard UCB (Upper Confidence Bound) are highly adaptive but have a "switching cost" that scales linearly with time ($T$).

As Vianney Perchet and colleagues noted in Batched Bandit Problems, there is often a significant gap between the theoretical ideal of continuous updates and the practical reality of limited intervention stages. The core challenge is determining how much efficiency is lost when we restrict the learner to a small number of batches.

The Doubling Trick for Information Gain

Why can we afford to wait before updating a policy? The intuition lies in the rate of information gain. Early in a task, every data point is precious and significantly shifts our understanding. As we collect more data, the marginal value of a single interaction decreases.

To exploit this, researchers use a doubling trick based on uncertainty. Instead of updating every step, the agent only updates its policy when its "knowledge" (often measured by the determinant of the covariance matrix of observed features) has doubled. Yu Bai and others demonstrated in Provably Efficient Q-Learning with Low Switching Cost that a logarithmic update schedule—updating only $O(\log T)$ times—is sufficient to maintain near-optimal regret. By using "stale" information until the next scheduled update, the agent saves on switching costs without significantly veering off the path to the optimal policy.

From Logarithmic to Doubly Logarithmic Updates

While $O(\log T)$ updates were a major milestone, recent work has pushed the boundaries of what is mathematically possible. In Sample-Efficient Reinforcement Learning with loglog(T) Switching Cost, Dan Qiao and Yu-Xiang Wang introduced the APEVE algorithm, which reduces the switching cost to a near-constant $O(\log \log T)$.

This "doubly logarithmic" bound represents a transition from updating based on time to updating based on a massive accumulation of evidence. Similarly, in the world of Thompson Sampling, Cem Kalkanli and Ayfer Ozgur showed in Batched Thompson Sampling that $O(\log \log T)$ batches are sufficient to achieve optimal regret. This suggests that for many problems, we only need to "check in" on our experiment a handful of times over its entire duration to remain competitive with a fully sequential learner.

Scaling to Complex Models

The intuition of low-frequency updates isn't limited to simple linear models. Researchers are now applying these principles to high-dimensional and non-linear settings:

The Theoretical Minimum

Is there a limit to how much we can compress these updates? Xuanfei Ren and Pan Xu explored this in Optimal Batched Linear Bandits, introducing the $E^4$ algorithm. They demonstrated that for certain linear bandit settings, asymptotic optimality can be reached with as few as 3 batches.

This line of research proves that the "cost of change" in RL is not a barrier to optimality. By carefully timing updates to coincide with significant shifts in information, we can build agents that are both statistically powerful and practically deployable in the rigid, batch-oriented systems of the real world.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_reinforcement_learning_with_low_switchin_2a9d8326,
  title = {Reinforcement Learning with Low Switching Cost},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/reinforcement-learning-with-low-switching-cost/rdr_2a9d8326615f49c59b3d2697119bfeeb},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_reinforcement_learning_with_low_switchin_2a9d8326_v1,
  title = {Reinforcement Learning with Low Switching Cost},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/reinforcement-learning-with-low-switching-cost/rdr_2a9d8326615f49c59b3d2697119bfeeb/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}