Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs

1.3 Problem Setting, Notation, and Organization

• The setting is tabular episodic MDP regret, with policies selected across K episodes of horizon H and total rounds T = KH; optimism uses upper-estimated Q-functions.StrongEuler uses adaptive model-based bonuses, while the clipped decomposition is broader than the subsequent model-based analysis and may not straightforwardly extend to Q-learning.Source: §1 · p. 1, §1.3 · pp. 4–5, §1.4 · pp. 5–6

1.2 Related Work

• Unlike earlier asymptotic or diameter-dependent analyses, the paper targets finite-time favorable-instance guarantees without difficult-to-verify ergodicity or hitting-time quantities.Prior logarithmic bounds could require large numbers of rounds and conservative problem-dependent quantities, whereas the proposed results depend on H rather than diameter D.Source: §1 · pp. 1–2, §1.2 · p. 4

1.1 Contributions

• StrongEuler achieves high-probability regret C_M log(1/δ) for every T ≥ 1, with gap- and horizon-dependent C_M plus an almost-gap-independent additive term.Choosing δ = 1/T yields a non-asymptotic expected regret bound, though the stated guarantee is for each fixed T rather than anytime regret.Source: §1.1 · p. 2
• The regret smoothly interpolates between instance-dependent C_M log T and minimax e O(H|S||A|T), which can be sharper for smaller T.The bound can also refine horizon dependence on benign instances, and the gap-dependent coefficient avoids worst-case mixing-time, hitting-time, and ergodicity dependencies.Source: §1.1 · p. 2, §1.2 · p. 4
• A clipped regret decomposition applies to a broad family of optimistic algorithms and yields analogous gap-dependent log T bounds beyond StrongEuler.The decomposition covers algorithms analyzed in Zanette and Brunskill [2019], Dann et al. [2018, 2017], Jin et al. [2018], and Azar et al. [2017].Source: §1.1 · p. 2

2 Main Results

• StrongEuler achieves a high-probability logarithmic gap-dependent bound, with H^3 factors reducible to H under contextual-bandit or sufficiently bounded-reward conditions and to 1 for contextual-bandit suboptimal terms.The expected regret scales as log T, while the suboptimal-pair term is generally unimprovable; the second term reflects additional dependence on gapmin.Source: §2 · pp. 6–7
• The gap-clipping analysis extends beyond StrongEuler to other recent optimistic algorithms, although some require confidence-interval modifications to obtain log T rather than log^2 T regret.The cited algorithms include those of Azar et al. [2017], Dann et al. [2017], Zanette and Brunskill [2019], and Dann et al. [2018].Source: §2 · p. 7, §2.1 · p. 7

2.1 Sub-optimality Gap Lower Bound

• For every prescribed set of gaps, an MDP exists whose regret matches the first term of Corollary 2.1 when T is large, showing that term is unavoidable.The construction applies for S ≥ 2, A ≥ 2, and arbitrary H ≥ 1 under the stated gap constraints.Source: §2.1 · pp. 7–8

2.2 Why the dependence on gapmin?

• A two-stage MDP with one gapmin = ϵ state and all other gaps at least 1/2 forces existing δ-correct optimistic algorithms to incur at least S/gapmin log(1/δ) regret.The instance demonstrates over-exploration caused by optimism and establishes the unavoidable gapmin dependence for the considered optimistic algorithms.Source: §2.2 · p. 8

2.3 Interpolating with Minimax Regret for Small T

• StrongEuler’s general bound interpolates between gap-dependent log T regret and worst-case sqrt(HSAT) regret, with improved H factors for contextual bandits and bounded rewards.The guarantee holds with probability at least 1 − δ, and its expected-regret version follows by setting δ = 1/T.Source: §2.3 · p. 9

3 Gap-Dependent bounds via ‘clipping’

• The section motivates clipping by showing that identifying suboptimal actions requires accurate future value estimates, explaining why prior gap-dependent analyses imposed diameter or ergodicity assumptions.It defines optimistic surplus and introduces strong optimism, a novel condition that facilitates sharper H-dependence in contextual bandits.Source: §3 · pp. 9–10

3.1 The Clipping Trick

• The clipping trick controls suboptimality by clipping small surpluses, combining minimax surplus analysis with gap-dependent control without requiring suboptimal actions to stop being selected.Suboptimal selections are attributed either to large current surpluses or insufficient exploration of future state-action pairs; recursive clipping avoids exponential dependence on H, while half-clipping introduces an unavoidable S/gapmin term for existing optimistic algorithms.Source: §3.1 · p. 11

3.2 Analysis of StrongEuler

• StrongEuler satisfies the strong-optimism criterion through a surplus bound, and the resulting analysis recovers the leading gap-dependent terms while improving H-dependence in benign instances and contextual bandits.The analysis extends beyond the particular confidence intervals by requiring an analogous surplus bound for other model-based optimistic algorithms; interpolation with the minimax rate is detailed in Appendix B.4.Source: §3.2 · pp. 12–13

4 Conclusion

• The approach provides logarithmic, gap-dependent bounds for episodic tabular MDPs and extends to model-based optimistic algorithms, while Q-learning extensions and optimal horizon dependence remain open.The authors also identify extensions to model-free approaches based on Q-learning as future work.Source: §4 · p. 13
• Existing optimistic algorithms incur an additional S/gapmin dependence on worst-case instances, despite the models nearly matching analogous information-theoretic lower bounds.The paper leaves open whether new algorithmic ideas can circumvent this limitation.Source: §4 · p. 13
• Future directions include logarithmic bounds for infinite-arm settings, adaptive discretization in metric state-action spaces, and function approximation.The infinite-arm example considers countably many actions drawn from an unknown reservoir distribution.Source: §4 · p. 13

A Notation and Organization

• Part I gives detailed StrongEuler regret bounds, proves their refinements, strengthens the clipped regret decomposition, and establishes optimism and surplus bounds.Its technical lemmas are deferred to Section C, while the main refinements concern Corollary B.1, Theorem B.2, and Theorem B.3.Source: A Notation and Organization · p. 18

Precise Results and Analysis

• Precise Results and Analysis consolidates the refined regret statements, StrongEuler guarantees, clipped-decomposition analysis, surplus control, and lower-bound arguments developed across the appendix.These components collectively provide the technical form of the paper’s main results.Source: A Notation and Organization · p. 18

A Notation and Organization

• Part II presents StrongEuler, specifies its confidence bonuses in pseudocode, connects it to model-based optimistic algorithms, and verifies its strong optimism and surplus guarantee.Section E describes the algorithmic instantiation, and Section F proves Proposition B.4.Source: A Notation and Organization · p. 18
• Part III proves the lower bounds, including the Ω(S/gapmin) bound for a specified algorithm class and the information-theoretic lower bound.These results are established in Sections G and H through Theorem 2.3 and Proposition 2.2.Source: A Notation and Organization · p. 18
• The notation distinguishes optimal, optimistic, lower-bound, and clipped quantities, while tracking gaps, variances, surpluses, visitation frequencies, observations, concentration events, and sampling thresholds.Worst-case-over-horizon gap notation, clipped gaps, surplus bounds, and the sampling scale Hsample ≲H log M support the appendix analysis.Source: A Notation and Organization · pp. 18–19

• The section formally proves Corollary 2.1 and Theorem 2.4 through refined counterparts that exploit benign instances and other favorable instance-specific quantities.Corollary B.1 refines the logarithmic-regret bound, while Theorem B.2 refines the interpolation between log T and T regimes.Source: B Precise Statement and Rigorous Proof… · p. 20
• The proof framework combines granular clipping, StrongEuler surplus bounds, and an integration-based argument into the refined regret guarantees.Theorem B.3 strengthens Proposition 3.1, Proposition B.4 bounds StrongEuler surpluses E_k,h(x, a), and Lemma B.6 combines these ingredients.Source: B Precise Statement and Rigorous Proof… · p. 20
• The rigorous argument proves Corollary B.1 first and then modifies the analysis to obtain the interpolation in Theorem B.2.Supporting technical results are distributed across Sections C, D, and F.Source: B Precise Statement and Rigorous Proof… · p. 20
• The section presents these tools as a modular recipe for establishing and potentially automating similar regret proofs for existing model-based optimistic algorithms.The authors explicitly intend the tools to be reusable in related settings.Source: B Precise Statement and Rigorous Proof… · p. 20

Effective horizon

• The effective horizon HT replaces H with a potentially smaller problem-dependent quantity and satisfies HT ≲1 for contextual bandits and for G ≲1 bounded rewards.The section notes that contextual-bandit variance can also be bounded by 1, while general horizon-H MDPs retain HT ≤ min-type bounds.Source: §B.1 · pp. 20–21

Transition suboptimality

• α-transition suboptimality requires the transition distributions of an action and an optimal action to be pointwise multiplicatively close; contextual bandits satisfy α = 0, while arbitrary MDPs satisfy α ≤1.The condition can be relaxed to hold only on a high-probability subset of next states, although the section uses the unrelaxed definition.Source: §B.1 · p. 21

Logarithmic bound

• Corollary B.1 provides a more precise logarithmic regret bound for StrongEuler, parameterized by variance, effective horizon, optimal-pair count, and minimum gaps.The result holds with probability at least 1 −δ for all K ≥2, with M = (SAH)^2 and confidence parameter δ.Source: §B.1 · p. 21

Main regret theorem

• Theorem B.2 gives StrongEuler a high-probability regret bound for all K ≥2 under effective horizon HT and α-transition suboptimality, interpolating between logarithmic and √T regimes.The theorem defines Zsub(ϵ) to control suboptimal pairs with gaps below ϵ, and Theorem 2.4 and Corollary 2.1 follow as direct consequences.Source: §B.1 · pp. 21–22

Instance structure

• The bounds depend on the number of optimal state-action pairs, which is at most H|S| under unique optimal actions and can be as small as |S| when the optimal action is stage-independent.The section notes that |Zopt| is often approximately |S| in environments with steady-state behavior.Source: §B.1 · p. 22

Variance-gap refinement

• A sharper coupling of variance and gaps is possible by binning gaps into intervals, but the required manipulations are deferred to later work.The stated bounds use maximal variance and minimal gap for each state-action pair, which can be refined by coupling stagewise quantities.Source: §B.1 · p. 22

Clipping framework

• The proof combines a generalized surplus-clipping theorem with a technical lemma distributing clipping across sums to obtain StrongEuler’s regret decomposition.The clipping threshold is based on transition suboptimality, with a simpler form for optimistic algorithms lacking strong optimism.Source: §B.2 · pp. 22, 24

Variance quantities

• Policy-dependent variance quantities are introduced to preserve the optimal H-dependence when interpolating with nearly gap-free regret bounds.The analysis uses variance terms associated with the optimal value function and rollouts of the current policy.Source: §B.2 · p. 23

Surplus bound

• With probability at least 1 −δ/2, Proposition B.4 bounds StrongEuler’s surpluses uniformly over states, actions, stages, and episodes while verifying strong optimism.The bound contains lead and future terms; the lead term drives the dominant regret factors, while future terms arise from rollouts of πk.Source: §B.2 · p. 23
• The lead term decays more slowly than the future terms and therefore governs the nearly gap-free component of regret.Its dependence on the minimum variance of the optimal value function is crucial for obtaining the correct minimax rate.Source: §B.2 · p. 23

Clipped regret decomposition

• Lemma B.6 combines the surplus bound and clipping theorem into a decomposition of StrongEuler’s regret into clipped lead and future terms on the concentration event.The decomposition uses the minimum clipped gap as a global threshold and bounds the resulting contribution with a universal constant.Source: §B.2 · p. 24

B.3 Proof of Corollary B.1: A proof via integration

• The regret bound is decomposed into local terms depending only on state-action sample counts, which are represented by lead and future functions.This isolates the dependence on empirical counts n_k(x, a) before relating them to visitation probabilities.Source: §B.3 · p. 24
• A martingale concentration argument establishes a sampling event under which empirical counts lower-bound their visitation-based counterparts, jointly with the concentration event with probability 1−δ.The event is obtained from the conditional expected count increments and Lemma B.7, proved using Dann et al. [2018, Lemma 6].Source: §B.3 · p. 25
• The resulting regret sums become discrete integrals of non-increasing lead and future functions, formalized by the integral-conversion Lemma B.8 after discarding initial samples.The conversion uses the relation between visitation probabilities and scaled counts n_k(x, a)/4.Source: §B.3 · p. 25
• Applying Lemma B.9 to the lead and future terms and substituting both resulting bounds into equation (6) completes the proof of Corollary B.1.The integral computations cover clipped non-increasing functions and remain valid under constant rescaling of the integration argument.Source: §B.3 · pp. 26–27
• Naive confidence intervals formed by union bounds over all times incur a log T · log log T dependence, so they do not yield strictly O(log T) regret.This motivates using anytime estimates in the integration-based analysis.Source: §B.3 · p. 26

• Theorem B.2’s regret bound interpolates between T and log T regimes.Source: §B.4 · p. 27
• The proof reduces the argument to establishing two inequalities after retracing Corollary B.1.Source: §B.4 · p. 27

Bound with Var

• The variance-based bound uses integration, Cauchy–Schwarz, and a bound on cumulative visitation counts.Source: §B.4 · p. 28

Bound with H_T

• The H_T bound instead uses f(u) = 1/max{u, 1}, Proposition B.4, and a deferred Cauchy–Schwarz integration lemma for G-bounds.Source: §B.4 · p. 28
• The H_T argument shows that the auxiliary |Z0|Hsamplefmax term is absorbed into terms already present in the final bound.Source: §B.4 · p. 28

C.1 Proof of clipping with future bounds, Lemma B.6

• Strong optimism allows Theorem B.3 to establish the clipping inequality, with future terms controlled through transition probabilities and Lemma B.5.The proof also uses clip[αx|ϵ] ≤ α clip[x|ϵ] for α ≤ 1 and sums the resulting inequality over episodes.Source: §C.1 · pp. 29–30

C.2 Proof of sampling lemma (Lemma B.7)

• The sampling lemma shows that the event (Esamp)′ implies Esamp(Hsample) for Hsample = 4H log 2HSA/δ, with probability at least 1 − δ/2.For k ≥ τ(x, a), the proof obtains the required lower bound on nk(x, a).Source: §C.2 · p. 30

C.3 Proof of integral conversion, Lemma B.8

• Lemma B.8 converts sums involving ωk(x, a) into integrals by representing counts with a nondecreasing function G and applying monotonicity and the Fundamental Theorem of Calculus.The conversion begins at τ(x, a), where nτ−1(x, a) is bounded by Hsample and f is non-increasing.Source: §C.3 · p. 31

C.4 Proof of interal conversion for G-bounds, Lemma B.10

• Lemma B.10 applies the integral conversion to G-bounds, separately bounding the first product term and the second term with Lemma C.1.The resulting expression includes an eL(nk(x, a))Vx,a,k,h contribution and an |Zopt|Hsamplefmax term.Source: §C.4 · p. 32

C.5 General Integral computations (Lemma B.9)

• Lemma B.9 provides general integral computations for clipped non-increasing functions f(u), covering two cases under problem-dependent constants and δ ∈ (0, 1/2).The bounds allow f(u/4) to be replaced by f(u/c) for any universal c > 0, and also cover the unclipped case by taking ϵ = 0.Source: §C.5 · pp. 32–33
• The proof of Lemma B.9 reduces clipped integrals to a finite endpoint nend, where f(u/4) vanishes beyond the threshold, and handles ϵ = 0 by taking nend = N.It then uses the inversion lemma to control logarithmic terms and determine the relevant endpoint scale.Source: §C.5 · pp. 33–34
• Lemma C.2 establishes inversion bounds for eL(u)/u, enabling the integral proof to control both threshold locations and logarithmic factors.For sufficiently large u, eL(u)/u ≤ b; for smaller scales, eL(u) is bounded by eL(1 + b−1).Source: §C.5 · p. 33
• For Part (b), the proof first derives a crude bound and then a refined bound by exploiting nend, before combining the resulting estimates.The argument defines n0 = 2 + log(M/δ), applies the inversion lemma, and combines the two pieces at the conclusion.Source: §C.5 · pp. 34–35

D Proof of ‘clipping’ bound: Proposition 3.1 / Theorem B.3

• The fundamental gap bound shows that for positive gap pairs, either the surplus is large or the expected next-stage value-function difference compensates for it.Under strong optimism and α-transition optimality, the bound applies with α; without strong optimism, it remains valid with α = 1.Source: D Proof of ‘clipping’ bound:… · p. 36
• Half-clipping sets the clipping threshold to ϵclip = gapmin/(2H) and constructs a modified MDP by adding half-clipped surpluses to rewards.Because clipping can destroy policy optimality, the proof instead establishes approximate optimism for the half-clipped value function.Source: D Proof of ‘clipping’ bound:… · p. 36

D.1 Proof of Lemma D.2

• Lemma D.2 lower-bounds the half-clipped surplus by comparing clipped and optimistic values through events where the policy selects suboptimal actions.The proof uses recursive decompositions over stages and exploits that suboptimal actions incur at least gapmin gap.Source: D Proof of ‘clipping’ bound:… · p. 36, §D.1 · p. 38

D.3 Proof of Lemma D.3

• Lemma D.3 further clips bonuses for suboptimal actions, showing that fully clipped surpluses satisfy the desired gap-based bound.The proof splits into cases according to whether the half-clipped surplus is already a fixed fraction of the gap, then chooses a constant c to close the bound.Source: D Proof of ‘clipping’ bound:… · pp. 36–37, §D.3 · pp. 40–41

D Proof of ‘clipping’ bound: Proposition 3.1 / Theorem B.3

• Combining the clipping lemmas bounds the policy’s suboptimality by an occupancy-weighted sum of fully clipped surpluses, thereby proving Theorem B.3.The argument also preserves nonnegativity of the clipped surplus when the algorithm is only optimistic.Source: D Proof of ‘clipping’ bound:… · p. 37

D.2 Proof of Lemma D.1

• Lemma D.1 derives the fundamental gap inequality by combining optimism, the maximizing definition of the optimistic action, and α-transition suboptimality.For algorithms that are not strongly optimistic, the resulting bound uses α = 1.Source: §D.2 · pp. 39–40

E The StrongEuler Algorithm

• StrongEuler makes two modifications to EULER: refined sample-count-dependent logarithmic bonuses and strong optimism.These changes target optimal log T regret and sharper bounds in settings with simple transition dynamics.Source: E The StrongEuler Algorithm · p. 42
• The bonuses use L(n_k(x, a)) proportional to log(Mn_k(x, a)/δ), replacing dependence on total time T and enabling log T asymptotic regret.Using log(MT/δ) confidence intervals may instead produce regret scaling as log^2 T.Source: E The StrongEuler Algorithm · p. 42
• Strong optimism is not required for gap-dependent bounds, but can sharpen them for simple transition dynamics such as contextual bandits.EULER and related algorithms would also obtain gap-dependent bounds, while refined logarithmic factors give log T asymptotic regret.Source: E The StrongEuler Algorithm · p. 42
• The algorithm performs optimistic value iteration with exploration bonuses and tracks reward, transition, count, and variance statistics across trajectories.RolloutAndUpdate executes each policy trajectory and records the data used to define the bonuses.Source: E The StrongEuler Algorithm · p. 42

F Analysis of StrongEuler: Proof of Proposition B.4

• The analysis of Proposition B.4 establishes both lower and upper bounds on the surplus E_k,h(x, a), using the lower bound to prove strong optimism.The upper bound is then used to analyze the corresponding complexity.Source: F Analysis of StrongEuler: Proof of… · p. 43
• The proof assumes a good event A_conc, defines it through six constituent events, and establishes P[A_conc] ≥ 1 − δ.Supporting lemmas in Sections F.1 and F.2 use the event assumption, which is formally specified in Section F.3.Source: F Analysis of StrongEuler: Proof of… · p. 43

F.1 Proof of Optimism

• StrongEuler is optimistic under Aconc: Qk,h(x, a) ≥ Q⋆h(x) and Ek,h(x, a) ≥ 0.The proof proceeds by backward induction on h, using bonus bounds and the inductive ordering of value functions.Source: §F.1 · p. 43, §11 · pp. 44–45

11 end

• The optimism proof reduces to controlling reward and transition deviations through bonus terms on Aconc, including a comparison lemma for bounded value functions.Lemma F.2 controls concentration deviations, while Lemma F.3 applies when Vk,h+1 ≤ V1 ≤ V2 ≤ Vk,h+1.Source: §11 · pp. 44–45

F.2 Proof of Surplus Bound Upper Bound

• The surplus-bound proof combines reward, transition, and strong bonuses while replacing empirical variance and empirical transitions with true-variance and true-transition controls.It uses Lemma F.4, the variance comparison Lemma F.5, Fact F.6, and a further transition bound to derive the stated upper-bound framework.Source: §F.2 · pp. 46, 48

F.3 Definition of Aconc, and proofs of supporting lemmas

• Aconc occurs with probability 1 −δ/2 because its constituent reward, transition, value, and variance events each hold with probability at least 1 −δ/12.The supporting proofs use Bernstein’s, Hoeffding’s, and Maurer–Pontil concentration inequalities with filtrations yielding logarithms depending on nk(x, a), rather than T.Source: §F.3 · pp. 49–50
• The supporting proofs define concentration events and combine reward, transition, variance, and bonus controls to establish the required optimistic-value inequalities.The derivations use variance events, Cauchy–Schwarz, and the ordering of optimistic value functions under the concentration event Aconc.Source: §F.3 · pp. 51–53

G.1 Formal Statement

• Theorem G.1 gives a high-probability regret lower bound for algorithms in the specified optimistic class on H = 2, |A| = 2, |S| = 2S + 1 instances with one gapmin = ϵ state and all other minimum gaps at least 1/2.The bound applies for ϵ ≤ 1/⌈c1S log(S/δ))⌉ and sufficiently large K, with probability at least 1 − c2Sϵ−2 log(1/δ)e−c3S −3δ; in particular, it holds with probability 1 − O(δ) when log(ϵ−1/δ) ≲ S ≲ ϵ−1/log(ϵ−1/δ).Source: §G.1 · p. 54

G.2 Algorithm Class

• The class considers optimistic Q-functions constructed from empirical reward and transition estimates, a reward bonus, and an additional nonnegative stage-dependent bonus, using a model-based formulation.Source: §G.2 · pp. 54–55

G.3 Formal Lower Bound Instance

• The lower-bound instance starts at state 0, uses two actions over H = 2, and routes actions to uniformly sampled positive or negative states whose reward distributions differ by ϵ on the designated state.The optimal action is always a = 1; gap1(0, −1) = gapmin = ϵ, while gap2(x, −1) ≥ 1/2 for x ≠ 0.Source: §G.3 · pp. 55–56

G.4 The Lower Bound:

• Proposition G.3 shows that the optimistic Q-function gap at (0, 1) decays no faster than S log(1/δ)/nk(0, 1), producing regret of order S log(1/δ)/ϵ despite all but one Q-function gaps being Ω(1).The proposition is stated for ϵ ≤ 1/⌈c1S log(S/δ))⌉ and N = ⌊c2S log(1/δ)/ϵ2⌋.Source: §G.4 · p. 56

G.4.1 Proof of Proposition G.3

• The proof of Proposition G.3 combines the small-count and large-count regimes to show Δ0(k) ≥ 2ϵ through the prescribed range, with total failure probability controlled by δ.For large counts, the simplified game and visit-count concentration ensure every state receives enough samples for Claim G.5.Source: §G.4.1 · pp. 57–59
• Conditioned on state-visit counts, the proof decouples into independent two-arm bandit games, enabling a lower bound on optimistic values with constant probability.Each state x contributes n_k(x) rounds of a two-arm game, which supports Claim G.5 and the subsequent gap lower bound.Source: §G.4.1 · pp. 57–58

G.5 Proof of Claim G.5

• Claim G.5 establishes that, after C1 log(M/δ) visits, the relevant optimistic gap event holds with probability at least 1/4.The argument controls the suboptimal arm’s sampling count, handles adaptive sampling through a pre-sampled reward sequence, and intersects events with probabilities 1−δ, 1−δ, and 1/2.Source: §G.4.1 · p. 58, §G.5 · pp. 60–61

H Information Theoretic Lower Bound (Proposition 2.2)

• Section H proves the information-theoretic lower bound in Proposition 2.2 and also establishes a non-asymptotic bound for non-uniformly good algorithms.The construction uses specific, non-uniform gaps and follows the lower-bound approach of Dann and Brunskill [2015].Source: H Information Theoretic Lower Bound… · p. 62

H.1 Construction of the hard instance

• The hard MDP uses S+2 states, A actions, horizon H, and transition probabilities parameterized by Δx,a; its construction is modified for H=1.For both H≥2 and the H=1 modification, the resulting stage-1 gap satisfies gap1(x,a)=Δx,a.Source: §H.1 · p. 62

H.2 Regret Lower Bound Decomposition

• Expected regret is decomposed into expected state-action counts weighted by gap1(x,a), providing the basis for the lower-bound argument.The decomposition is combined with the relationship between the policy value and optimal Q-function.Source: §H.2 · p. 63
• For sufficiently large K≥K0(M), uniformly correct algorithms incur logarithmic lower bounds proportional to gap1(x,a) log K, with analogous bounds for all h∈[H−1].The displayed intermediate bound also contains gap1(x,a)^2 log K before the final gap-weighted conclusion.Source: §H.2 · p. 63

Information-theoretic reduction

• The argument invokes an MDP analogue of Garivier et al. [2018, Equation (6)] to relate observations under two episodic MDPs through KL divergences.The lemma applies to any filtration-measurable random variable bounded in [0, 1].Source: §H.3 · p. 64

Alternative MDP and KL control

• For a fixed state-action pair, the alternative MDP changes only its transition law, reducing the relevant divergence to Bernoulli KL between the two transition probabilities.A Taylor expansion bounds this divergence by a universal constant times ∆x,a^2 under the stated range conditions.Source: §H.3 · p. 64

Test statistic construction

• The proof constructs a bounded random variable ZK whose expectations under the original and alternative MDPs are controlled using state-visit probabilities and uniform goodness.Under the alternative MDP, uniform goodness gives 1 − E_M′[ZK] ≤ CM′η S K^(α−1).Source: §H.3 · p. 65

Conclusion

• Combining the two expectation controls with the change-of-measure inequality establishes the claimed lower bound for sufficiently large K.The final step also invokes Garivier et al. [2018, Inequality (11)].Source: §H.3 · p. 65