PaperlayerView exact revision on arXiv

Source-linked AI summary

Provably Efficient Q-Learning with Low Switching Cost

Yu Bai, Tengyang Xie, Nan Jiang, Yu-Xiang Wang

arXiv:1905.12849v3cs.LGcs.AIstat.ML

TL;DR

Limited adaptivity is important when reinforcement-learning policies are costly to change, but its theoretical treatment in RL is limited. The paper defines local switching cost and develops model-free Q-Learning with UCB2 exploration, achieving sublinear regret with logarithmic switching, plus concurrent extensions and a lower bound. The paper leaves tighter regret and switching guarantees, especially for model-based approaches and global switching cost, as future directions.

  • Problem

    The paper addresses how to obtain low-regret reinforcement learning while changing exploration policies infrequently in applications where policy deployment is costly.

    Source: §1 · pp. 1–2

  • Method

    It defines local switching cost and develops model-free Q-Learning algorithms using UCB2 exploration with delayed policy updates.

    Source: §1 · p. 2, §6 · p. 9

  • Results

    The algorithms achieve eO(H^{4,3}SAT) regret with O(H^3SA log(K/A)) local switching cost, while concurrent versions provide nearly linear speedup and favorable sample complexity.

    Source: §1 · p. 2, §8 · p. 10

  • Takeaways & Limitations

    UCB2-style delayed exploration can extend low-switching, low-regret learning from bandits to model-free episodic RL and concurrent execution.

    Source: §3 · p. 4, §8 · p. 10

    The paper leaves tighter global switching-cost bounds and tighter regret or switching guarantees, potentially via model-based methods, for future work.

    Source: §2.1 · p. 4, §8 · p. 10

Abstract

from arXiv · show

We take initial steps in studying PAC-MDP algorithms with limited adaptivity, that is, algorithms that change its exploration policy as infrequently as possible during regret minimization. This is motivated by the difficulty of running fully adaptive algorithms in real-world applications (such as medical domains), and we propose to quantify adaptivity using the notion of local switching cost. Our main contribution, Q-Learning with UCB2 exploration, is a model-free algorithm for H-step episodic MDP that achieves sublinear regret whose local switching cost in K episodes is $O(H^3SA\log K)$, and we provide a lower bound of $Ω(HSA)$ on the local switching cost for any no-regret algorithm. Our algorithm can be naturally adapted to the concurrent setting, which yields nontrivial results that improve upon prior work in certain aspects.

1 Introduction

The paper studies reinforcement learning with limited adaptivity, motivated by costly policy changes, and develops low-switching Q-Learning methods with regret guarantees. It also introduces local switching cost, derives a lower bound, and extends the approach to concurrent RL.

1 Introduction

  • Limited adaptivity matters in medical treatment, recommendation, compiler optimization, hardware placement, database optimization, and materials discovery because changing deployed policies can require costly approvals or reconfiguration.The paper also connects limited adaptivity to parallelization, off-policy RL, and constrained MDPs [9] [26].Source: §1 · pp. 1–2

1.1 Prior work

  • Prior work established low-adaptivity guarantees in bandits, online learning, and optimization, while this paper extends the agenda to model-free episodic RL.Q-Learning had already achieved eO(poly(H)·SAT) regret with UCB exploration and careful stepsizes.Source: §1 · p. 2, §1.1 · p. 3

1 Introduction

  • The paper proposes local switching cost to quantify how many state-time policy decisions change between deployed policies.Lower local switching cost corresponds to fewer changes in deployed policies.Source: §1 · pp. 1–2
  • O(H^3SA log(K/A)) local switching cost accompanies regret matching vanilla Q-Learning counterparts, while switching grows only logarithmically with episodes.The algorithms are Q-Learning with UCB2-Hoeffding and UCB2-Bernstein exploration.Source: §1 · p. 2
  • Concurrent versions let multiple agents act in parallel, achieving nearly linear execution-time speedup and favorable exploration sample complexity relative to existing concurrent algorithms [13].Source: §1 · p. 2
  • An Ω(HSA) lower bound applies to the switching cost of any sublinear-regret algorithm, leaving at most an O(H^2 log(K/A)) gap from the upper bound.Source: §1 · p. 2

2 Problem setup

The paper formalizes tabular undiscounted episodic MDPs and measures adaptivity through local policy changes across episodes. It focuses on local rather than global switching cost, leaving tighter global bounds for future work.

2 Problem setup

  • The setting is an undiscounted tabular episodic MDP with horizon H, S states, A actions, deterministic rewards in [0,1], and either adversarial or stochastic initial states.The transition kernel is Ph and the terminal state is absorbing and uninformative.Source: §2 · p. 3
  • A deterministic policy consists of H state-to-action sub-policies, and the analysis can focus on deterministic policies because an optimal deterministic policy exists.Source: §2 · p. 3
  • Regret is measured over K episodes, with total interaction length T := KH, by comparing each employed policy with the optimal episode value.The policy for episode k is selected before that episode begins.Source: §2 · p. 3

2.1 Measuring adaptivity through local switching cost

  • Local switching cost counts the (h,x) state-time pairs where consecutive policies choose different actions, and sums these changes across the K deployed policies.The cost is random in general, with trivial bounds nswitch(π,π′) ≤ HS and Nswitch(A) ≤ HS(K−1).Source: §2.1 · p. 4
  • The local measure reflects deployment costs that scale with the portion of a policy changed, whereas global switching cost counts whole-policy changes and can be substantially smaller.The paper focuses on bounding local switching cost and leaves tighter global bounds for future work.Source: §2.1 · p. 4

3 UCB2 for multi-armed bandits

The paper uses UCB2 as the bandit foundation for reducing policy switches without changing the regret target. UCB2 repeatedly executes an arm for scheduled blocks rather than switching after every upper-confidence-bound selection.

3 UCB2 for multi-armed bandits

  • UCB2 achieves the same regret bound as UCB while reducing switching cost to O(A log(T/A)).Its lower switching cost follows from grouping repeated arm selections into scheduled blocks.Source: §3 · pp. 4–5
  • The bandit problem is the H=1, S=1 special case of RL, with unknown reward distributions and a low-regret objective.Source: §3 · p. 4
  • UCB2 maintains upper confidence bounds but, when an arm maximizes the bound for the r-th time, plays it τ(r)−τ(r−1) times instead of once.Source: §3 · pp. 4–5
  • The algorithm initializes each arm, repeatedly selects the arm with the largest confidence score, and executes the scheduled block controlled by η.The full procedure uses parameter η∈(0,1) and updates time and arm counters after each block.Source: §3 · p. 5

4 Q-learning with UCB2 exploration

Q-Learning with UCB2 exploration combines optimistic running estimates with delayed policy updates, achieving sublinear regret and logarithmic local switching cost, plus PAC guarantees.

4.1 Algorithm description

  • The algorithm maintains an eagerly updated estimate and a delayed estimate used for action selection, keeping the policy fixed between scheduled updates.UCB2 triggers every update initially, then only at exponentially spaced visitation counts after the threshold τ(r⋆).Source: §4.1 · pp. 5–6
  • The method uses Hoeffding- or Bernstein-type optimistic exploration bonuses while updating running Q estimates after each episode.The Hoeffding implementation initializes optimistic Q estimates and updates them using a bonus term and stepsize-weighted target.Source: §4.1 · p. 6

4.2 Regret and switching cost guarantee

  • Q-Learning with UCB2-Hoeffding achieves eO(H^4SAT) regret and O(H^3SA log(K/A)) local switching cost, matching UCB regret while reducing policy switches.The switching cost is logarithmic in K, whereas vanilla UCB can incur HS(K−1) switches in the worst case.Source: §4.2 · pp. 6–7
  • The Bernstein variant achieves eO(H^3SAT) regret with the same O(H^3SA log(K/A)) switching-cost bound as the Hoeffding variant.It replaces the Hoeffding exploration bonus with a Bernstein-type bonus.Source: §4.2 · p. 7

4.3 PAC guarantee

  • Q-Learning with UCB2 yields a PAC policy after eO(H^{5,4}SA/ε^2) episodes for the Hoeffding and Bernstein variants, respectively.The PAC guarantee follows by converting the regret bounds through an online-to-batch argument.Source: §4.3 · p. 7

5 Application: Concurrent Q-Learning

The low-switching Q-Learning algorithms extend to concurrent reinforcement learning by parallelizing execution between policy switches, achieving nearly linear speedup and favorable comparisons with CMBIE.

Setting

  • The concurrent setting uses M independent MDP copies whose machines act synchronously, communicate only after episodes, and measure performance in completed rounds.The setting is more stringent than prior work allowing communication after each timestep.Source: §5 · p. 7

Concurrent Q-Learning

  • The parallelized algorithms achieve a nearly linear execution-time speedup and compare favorably with existing concurrent algorithms in exploration sample complexity.The concurrent construction follows because low-switching execution can be parallelized between consecutive policy switches.Source: §5 · pp. 7–8
  • Concurrent Q-Learning achieves linear speedup while M = eO(H^{2,1}/ε^2), with the H^3SA overhead negligible in high-accuracy settings.The result applies to concurrent versions using UCB2H or UCB2B exploration.Source: §5 · p. 8

Comparison with existing concurrent algorithms

  • The concurrent algorithms also imply a PAC mistake bound for taking ε-near-optimal actions on all but a bounded number of actions with high probability.The bound is derived from Theorem 5.Source: §5 · p. 8
  • Against CMBIE, the comparison reports that CMBIE has higher H dependence and an S^2 term under the typical episodic-to-discounted correspondence.The dependence is not generally comparable without that correspondence.Source: §5 · p. 8

6 Proof overview of Theorem 2

The proof addresses delayed policy updates by controlling the mismatch between the Q-function used for exploration and the running estimate updated by learning.

Proof overview

  • Delayed UCB2 updates create a mismatch because the policy uses an older Q estimate while the algorithm updates the current running estimate.The proof must show that this mismatch does not destabilize propagation of error across steps.Source: §6 · p. 9
  • The proof first bounds h-step error by a maximum error whose policy-dependent term has no mismatch because the policy depends on the delayed estimate.The remaining perturbation term is related to stepsizes between episodes and the (h + 1)-regret.Source: §6 · p. 9
  • The analysis bounds the delayed-update perturbation and shows that its effect on successive-step regret is limited to a factor (1 + 1/H)(1 + O(ηH)).Choosing η = O(1/H^2) reduces this factor to 1 + O(1/H), allowing the propagation argument to proceed.Source: §6 · p. 9

Broader implications

  • The propagation analysis may extend to exploration problems with delayed updates or asynchronous parallelization.This is presented as a broader potential application of the perturbation analysis.Source: §6 · p. 9

7 Lower bound on switching cost

The paper proves an Ω(HSA) lower bound on switching cost for no-regret algorithms, while its O(H^3SA log K) upper bound is within an H^2 log K factor.

Lower bound

  • Ω(HSA) switching cost is necessary for any no-regret algorithm; otherwise, an algorithm with N_switch ≤ HSA/2 has regret linear in K.The lower bound applies to the stated class of episodic MDPs and algorithms satisfying the switching restriction.Source: §7 · pp. 9–10
  • The achieved O(H^3SA log K) switching cost is at most O(H^2 log K) above the lower bound.The paper leaves tightening the H^2 factor as future work and conjectures that log K may be reducible.Source: §7 · p. 10

8 Conclusion

The paper develops low-switching-cost Q-Learning by combining delayed policy updates with optimistic running estimates. Its analysis establishes optimism, accuracy, and perturbation bounds that support the regret guarantee.

8 Conclusion

  • Q-Learning maintains a running estimate updated every episode and a delayed estimate used for action selection, so policy switches occur only when the delayed estimate is updated.The delayed-update analysis controls the resulting perturbation and propagation of error.Source: §8 · p. 10
  • The conclusion reports sublinear regret with at most O(log T) policy switches, alongside nearly linear concurrent speedup and favorable sample complexity.The proof uses a perturbation analysis for exploration with delayed updates, which the paper identifies as potentially broader than this algorithm.Source: §8 · p. 10
  • The paper leaves tighter regret bounds, still lower switching costs, and connections to off-policy RL as future directions.These directions define the main scope boundaries stated in the conclusion.Source: §8 · p. 10

A.2 Basics

  • The proof establishes that the running Q estimates are optimistic and accurate, providing the properties needed for regret analysis.The argument treats the estimates as aggregated Q-functions and separates their optimism from the exploration policy and bonus.Source: §A.2 · p. 13

A.3 Perturbation bound under delayed Q updates

  • The delayed-policy analysis bounds max error and isolates a perturbation term caused by updates that lag behind the policy.When no delayed update intervenes, the bound reduces to the corresponding current-estimate expression.Source: §A.3 · pp. 13–14

A.4 Proof of Theorem 2

The proof of Theorem 2 combines perturbation and propagation-of-error bounds to control regret under delayed Q updates. It separately bounds the local switching cost by analyzing the UCB2 triggering stages.

A.4 Proof of Theorem 2

  • The main proof combines a perturbation bound with the main regret term and shows that propagation of error remains controlled under delayed updates.The proof explicitly separates regret and local-switching-cost arguments.Source: §A.4 · pp. 15–16
  • The regret proof bounds the accumulated delayed-update error and then applies a propagation-of-error inequality to obtain O(H^4SATℓ).The accumulated contribution is controlled by a factor bounded by 1 + 3/H before summing over episodes.Source: §A.4 · pp. 15, 17
  • With probability at least 1 − p, Algorithm 2 has regret O(H^4SATℓ) and local switching cost O(H^3SA log(K/A)).Here ℓ := log(SAT/p).Source: §A.4 · p. 16
  • The switching-cost proof analyzes each (h, x) and action through the two UCB2 stages, then multiplies the resulting bound by HS.The stage-triggering sequence determines the number of switches contributed by each action.Source: §A.4 · p. 18

B.1 Algorithm description

  • The appendix introduces UCB2-Bernstein exploration as an additional algorithmic variant.Its full algorithm is presented separately from the Hoeffding-style proof.Source: §B.1 · p. 18

B.2 Proof of Theorem 3

The Bernstein proof adapts the delayed-update analysis with variance-sensitive optimism and perturbation bounds. It derives the regret guarantee and carries over the local switching-cost argument from Theorem 2.

B.2 Proof of Theorem 3

  • The Bernstein analysis establishes optimism, accuracy, and bounded variance for the running estimates and variance terms.These properties are the Bernstein-case analogues of the Hoeffding proof lemmas.Source: §B.2 · pp. 18, 20
  • The algorithm updates the running estimate with a Bernstein-type bonus and periodically copies it into the action-selection Q estimate.The displayed update sequence includes action selection, observation accumulation, and a policy update.Source: §B.2 · p. 19
  • The proof uses a Bernstein-specific perturbation bound for delayed policy updates and a max-error lemma indexed by the last update episode.The perturbation term is nonzero only after the policy update has been delayed.Source: §B.2 · p. 19
  • With probability at least 1 − p, Algorithm 3 has regret bounded by O(S3A3H9ℓ4), while its local switching-cost bound can be adapted from the proof of Theorem 2.The proof obtains a propagation of error inequality for the remaining terms.Source: §B.2 · pp. 20, 23
  • The Bernstein proof sums several error terms using concentration inequalities, Cauchy–Schwarz, and the balanced-visit condition to obtain the final regret bound.The remaining propagation argument is adapted from Theorem 2 in.Source: §B.2 · pp. 21, 23

C Proof of Corollary 4

The corollary translates the regret guarantees into episode requirements for finding an ε near-optimal policy. The concurrent construction parallelizes unchanged-policy episodes while preserving the non-parallel execution path in distribution.

C Proof of Corollary 4

  • Q-Learning with UCB2B requires K = eO(H^4SA/ε^2) episodes to guarantee an ε near-optimal policy with high probability.The corresponding Hoeffding-style result uses K = eO(H^5SA/ε^2).Source: C Proof of Corollary 4 · p. 24

D Proof of Theorem 5

  • The concurrent algorithm executes the current policy on all M machines until the UCB2 schedule requires a switch, retaining only the trajectories needed for that switch point.Unused trajectories may be discarded to preserve the vanilla algorithm's execution path.Source: Algorithm description · p. 24

Algorithm description

  • The concurrent procedure aggregates trajectories sequentially through UCB2 scheduling, then updates the policy from the retained trajectories using either Hoeffding or Bernstein bonuses.This construction applies to both low-switching-cost Q-Learning variants.Source: Algorithm description · p. 24

D.1 Proof of Theorem 5

The concurrent algorithm preserves the execution distribution of non-parallel Q-Learning with UCB2 exploration while reducing episodes between switches across machines. The section also establishes a mistake-bound conversion and develops a prior-based linear-regret lower bound.

D.1 Proof of Theorem 5

  • Algorithm 4 has an execution path equal in distribution to vanilla non-parallel Q-Learning with UCB2 exploration, while discarding some data and playing each switch interval in ⌈L_t/M⌉ rounds.This equivalence holds because the concurrent algorithm does not fully use data from all M machines.Source: §D.1 · p. 25

D.2 Concurrent algorithm with mistake bound

  • The concurrent algorithm yields an ε near-optimal policy with high probability after the exploration rounds specified by Theorem 5, then runs that policy indefinitely without mistakes.The resulting mistake bound counts exploration-round actions across at most M machines and H steps per machine.Source: §D.2 · p. 25

E Proof of Theorem 6

  • The lower-bound argument considers algorithms over H-step MDPs with S states, A actions, deterministic rewards in [0, 1], and K episodes.The proof starts from an algorithmic condition and aims to establish a worst-case regret statement.Source: E Proof of Theorem 6 · p. 26

E.1 Construction of prior

  • The constructed prior uses uniformly random transitions and a policy-dependent optimal action a⋆(h, x), making each MDP equivalent to H parallel A-armed bandits replicated across S states.Rewards are 1 for selecting a⋆(h, x) and 0 otherwise.Source: §E.1 · p. 26

E.2 Minimax lower bound

  • The minimax lower-bound proof relates value loss to local switching cost by tracking visited actions and recursively analyzing algorithms that switch only to previously unseen actions.For A ≥ 4, the resulting regret is lower bounded as stated in the proof.Source: §E.2 · pp. 26–28
Loading 1905.12849v3…