Many deployed learning systems cannot change their decision whenever they like. A retailer can re-price or re-shelve a limited number of times, and a clinic can revise a protocol only occasionally. The theory of hard switching constraints studies this case. A bandit algorithm (a learner that repeatedly picks one of $K$ options and sees only that option's reward) may change its choice at most $B$ times over $T$ rounds, and once the budget is gone it is stuck with its last choice. The theory is detailed. Regret does not fall smoothly as $B$ grows but in a "staircase" of discrete steps (Simchi-Levi and Xu), and in the full-information expert setting it has a sharp phase transition near $B \approx \sqrt{T}$ (Altschuler and Talwar). The algorithms that attain these rates schedule their switches on a fixed grid of epochs chosen in advance for the worst case. None of them has been run on real interaction data. The papers themselves state this: BwSC reports no datasets, and the limited-switch revenue-management and assortment work is synthetic only (Simchi-Levi, Xu, and Zhao; Zhang et al.).
This proposal treats hard switching as the object of study and the missing empirical validation as the method. It asks one question that a benchmark alone would not answer: on real reward data, does when you spend a switch matter more than how many you have? The worst-case grids assume every instance is as hard as the lower-bound construction. Real logs have uneven gaps between arms, a few clearly bad arms, and reward drift. That suggests a learner that times its switches by the data, while still respecting the hard cap, could beat the grid at the same $B$. It also suggests that the staircase, a worst-case phenomenon, may simply not appear.
Core Claim
We claim two things that can each be falsified. First, on replayed real logs, the regret-versus-budget curve of the theoretically optimal limited-switch algorithms will be smooth. The predicted staircase steps, which the theory spaces roughly by the number of arms, will be undetectable, even though they are detectable at the same $T$ and $K$ on the worst-case synthetic instances the theory is built on. Second, a budget-aware adaptive trigger will dominate the fixed epoch grid of LS-SE (Simchi-Levi and Xu) at every budget below the unconstrained switch count. This trigger switches when the set of plausibly-best arms actually changes, but it holds a reserve of switches so it can never be locked in early. It will not dominate uniform batching with Thompson sampling everywhere. We expect the gain to concentrate at small $B$, where timing matters most.
The closest existing work is Beyond Information Gain. It benchmarked switching criteria for low-switching-cost deep reinforcement learning and found that provable information-gain triggers switch too often. There, a heuristic based on feature similarity reached an average reward-threshold switching improvement (RSI) of 3.60 on Atari, against 2.33 for information-gain rules and 3.22 for policy-based rules. That study motivates our question but differs from it in three ways. It concerns deep RL training rather than regret under a hard budget. It imposes no cap $B$ with lock-in. It never tests the bandit theory's staircase predictions. We import its lesson, that theoretical switch rules are miscalibrated in practice, into the setting where the theory is sharpest and has never been checked.
Research Program
The first component is an evaluation harness for hard switching on logged data. We use two uniformly-random logging sources, which permit unbiased replay. A round is accepted when the logged action matches the action the learner is holding, and accepted rounds count as time steps. The sources are the Random-policy campaigns of the Open Bandit Dataset (Large-scale Open Dataset, Pipeline, and Benchmark for Bandit Algorithms), with roughly 26M ZOZOTOWN impressions, and the Yahoo! Today News click logs used by Online Interactive Collaborative Filtering. MovieLens ratings, binarized as in Simulated Contextual Bandits for Personalization Tasks, give a third, simulator-style environment in which we can also expose full information and test the $\sqrt{T}$ expert threshold.
Replay under a hard cap has a subtlety. Holding one arm for an epoch consumes only the events for that arm, so events are not in true wall-clock order. We report results both under stationary shuffling and in original timestamp order. The ordered version keeps the article churn in Yahoo, which is exactly where lock-in after budget exhaustion should hurt. Every method runs through the same harness, and switch counts are checked as a hard invariant.
The second component is the adaptive trigger. It runs successive elimination, and it switches arms only when the elimination set changes or the active arm's confidence interval stops overlapping the leader's. A reserve rule forbids spending a switch if doing so would leave fewer than the number needed to finish a coarsened LS-SE grid on the remaining horizon. This reserve is the key ingredient. Because the rule always keeps a feasible fallback schedule, a simple argument should bound its worst-case regret within a constant factor of LS-SE run with a proportionally smaller budget. We will state this bound, but it is secondary to the empirical question.
The third component is cost accounting. We measure wall-clock time and memory for AdaLS, LS-2SLP, and the adaptive trigger. The file notes that such overheads are unquantified (Sherman and Koren). It also records that one compact reformulation cut assortment solves from over 10 hours to a few minutes (Zhang et al.).
Baselines
The naive reference point is predict-then-deploy. We fit arm means on an initial slice of replayed data and then commit to the best arm with zero further switches, which uses a budget of one. We also run uniform random play as a floor. The ceiling is unconstrained Thompson sampling and UCB, reported together with their realized switch counts so the budget scale is anchored.
The strongest simple competitor is uniform fixed-interval batching (FIX-$B$). It splits the horizon into $B$ equal epochs and runs Thompson sampling or UCB on the accumulated data at each epoch boundary. It is dangerous because equal mini-batching is exactly minimax-optimal in switching-constrained convex optimization (Chen et al.), and it was stable though not best in the RL benchmark. The strongest theory-derived methods are LS-SE and AdaLS (Simchi-Levi and Xu). The adaptive trigger has to beat these to show that the theoretical grid is miscalibrated rather than merely that adaptivity helps.
We also include a soft-penalty baseline: Thompson sampling with a switching penalty $\lambda$, with $\lambda$ tuned per budget so realized switches meet $B$ and a hard stop when the cap is hit. An ablation removes the reserve rule from our trigger, so it switches whenever the evidence changes until the budget is exhausted. This isolates the reserve rule's contribution.
Fairness rules apply to every method. All methods see identical replay streams and random seeds, 50 or more per configuration. Every tunable method gets the same hyperparameter budget, 20 configurations tuned on a held-out campaign or time slice and frozen before test. Beating a baseline means lower mean cumulative regret, relative to the best fixed arm in hindsight, at matched realized switches, with non-overlapping 95% bootstrap intervals over seeds, on at least two of the three data sources.
There is no reported result on Lacuna for any hard-switching bandit algorithm on real logs, so no published number exists to beat. The nearest reported figures are the Atari RSI values above (3.60 vs. 3.22 vs. 2.33). They come from a different problem and serve only as context. The one reported limited-switch number, a revenue-to-optimum ratio of up to 0.84 on synthetic configuration $\Gamma_4$ (Zhang et al.), will be reproduced as a sanity check of the harness.
Why not just…?
Why not just batch uniformly and skip the theory altogether? This is the real threat. If FIX-$B$ with Thompson sampling matches the adaptive trigger at every budget, then the claim that timing matters is false for these data, and the right conclusion is that practitioners should batch uniformly. The experiments are built to show that outcome if it holds. What would contradict it is a gap concentrated at small $B$ and on the time-ordered Yahoo stream, where uniform epochs waste switches during stretches when nothing changes. We will report the result honestly either way.
Why not just learn offline and deploy one policy? Theory says a budget that stays constant as $T$ grows gives linear regret, and roughly $K \log\log T$ switches are needed for near-optimal regret (Simchi-Levi and Xu). Naive offline maximum likelihood is also known to overrate rarely seen actions (PASTA). Still, real logs may be easy enough that one or two switches suffice. The predict-then-deploy baseline measures exactly how much of the budget curve collapses to $B \le 2$.
Why not just use a soft switching penalty? A tuned $\lambda$ controls switches only on average. It can cluster switches in noisy periods and then hit the cap and lock in (Zhang et al.). We test this directly. We record how often the soft-penalty learner exhausts its budget before the horizon's midpoint, and what regret it incurs afterwards, compared with the reserve-based trigger.
Proposed Experiments
The first decisive check targets the staircase. For each source we sweep $B$ at unit resolution across several predicted step locations for a fixed $K$, drawn from 10 to 80 arms of OBD or Yahoo, and a fixed $T$. We then compare the regret drop for budget increments that cross a predicted step with increments that stay inside one. We run the same sweep on the worst-case synthetic instances from the lower-bound construction, which calibrates statistical power. If the steps are visible in synthetic data but absent in real data, the staircase is a worst-case artifact. If they appear in both, the theory's structure is a practical guide to choosing $B$. On MovieLens with full information we run the analogous test for the $\sqrt{T}$ transition in the expert setting.
The second check is the budget-efficiency curve. It plots regret against realized switches for every method, and our claim holds only if the adaptive trigger's curve lies below both LS-SE and FIX-$B$ over the small-budget range. The no-reserve ablation must show more early lock-in on time-ordered data. Otherwise the reserve rule is unnecessary.
The third check measures wall-clock time per decision and total runtime for AdaLS, LS-2SLP (on an OBD pricing-style reformulation with a small price grid), and our trigger, all on identical hardware. We release the harness, replay code, and all seeds so later limited-switch algorithms face real logs by default.
References
- Phase Transitions in Bandits with Switching Constraints
- Online Learning over a Finite Action Set with Limited Switching
- Blind Network Revenue Management and Bandits with Knapsacks Under Limited Switches
- Dynamic Assortment Selection Under Inventory and Limited Switches Constraints
- Beyond Information Gain: An Empirical Benchmark for Low-Switching-Cost Reinforcement Learning
- Large-scale Open Dataset, Pipeline, and Benchmark for Bandit Algorithms
- Online Interactive Collaborative Filtering Using Multi-Armed Bandit with Dependent Arms
- Simulated Contextual Bandits for Personalization Tasks from Recommendation Datasets
- Lazy OCO: Online Convex Optimization on a Switching Budget
- Minimax Regret of Switching-Constrained Online Convex Optimization: No Phase Transition
- PASTA: Pessimistic Assortment Optimization
- Revisiting Smoothed Online Learning