Q-Learning with Fine-Grained Gap-Dependent Regret
Authors: Haochen Zhang
Zhong Zheng
Lingzhou Xue
Venue: ICLR 2026 Poster (2026)
Keywords: Reinforcement Learning
Q-Learning
Regret
Suboptimality Gap.
Primary area: reinforcement learning
TL;DR: This work establishes the first fine-grained, gap-dependent regret upper bound for model-free RL algorithms, covering both UCB-based and non UCB-based algorithms.

Abstract: We study fine-grained gap-dependent regret bounds for model-free reinforcement learning in episodic tabular Markov Decision Processes. Existing model-free algorithms achieve minimax worst-case regret, but their gap-dependent bounds remain coarse and fail to fully capture the structure of suboptimality gaps. To address this limitation, we establish fine-grained gap-dependent regret guarantees for both UCB-based and non-UCB-based algorithms. In the UCB-based setting, we develop a novel analytical framework that explicitly separates the analysis of optimal and suboptimal state-action pairs, yielding the first fine-grained regret upper bound for UCB-Hoeffding (Jin et al., 2018). In the non-UCB-based setting, we revisit the only existing algorithm, AMB (Xu et al., 2021), and identify two issues in its design and analysis: improper truncation in the $Q$-updates and violation of the martingale difference condition in the concentration argument. To resolve these issues, we propose two refinements of AMB: the UCB-based ULCB-Hoeffding and the non-UCB-based Refined AMB. For ULCB-Hoeffding, we establish the same fine-grained regret bound as UCB-Hoeffding by applying our fine-grained framework, highlighting its broad applicability. For Refined AMB, we derive a rigorous fine-grained gap-dependent regret bound in the non-UCB setting and demonstrate consistent empirical improvements over the original AMB.

Published as a conference paper at ICLR 2026
Q- G-EANNNGNG WITH GININGRAINED GAP-DEPENDENT REGRET
Haochen Zhang, Zhong Zheng & Lingzhou Xue Department of Statistics, The Pennsylvania State University State College, PA, 16802, USA (haz5340,, 2v25337, zxxee eespspuuueeee edu
ABSTRACT
We study fine-grained gap-dependent regret bounds for model-free reinforcement learning in episodic tabular Markov Decision Processes. Existing model-free al- gorithms achieve minimax worst-case regret, but their gap-dependen bounds re- main coarse and fail to fully capture the structure of suboptimality gaps. To ad- dress this limitation, we establish fine-grained gap-dependent regret guarantees for both JCB-based and non-UCB -based algorithms. In the develop a novel analytical framework that explicitly separates the analysis of op- timal and suboptimal state-action pairs, yielding the first thneggrined regret upper bound for UCB- Coe--Hoffdiig (Jin et al., 2018). In the non-UCB- -CCB-based setting, we re- visit the only existing algorithm, AMB (Xu et al., 2021), and identify two issues in its design and analysis: improper truncation in the Q-updates and violation of the martingale difference condition in the concentration argument. To resolve these is- and
setting, we
sues, we propose two refinements of AMB: the UCB-based the non-UCB-based Refined AMB. For ULCB- ULCB-Hoeffing, we establish the same fine- une-grained regret bound as UCB- JCB-Hoeffding by applying our fine grained frame- work, highlighting its broad applicability. For Refined AMB, we derive rigorous fine- fine-grained gap-dependent regret bound in the non-UCB setting and demonstrate consistent empirical improvements over the original AMB.
INTRODUCTION
Reinforcement Learning (RL) (Sutton & Barto, 2018) is sequential decision-making framework where an agent maximizes cumulative rewards through repeated interactions with the environment. RL algorithms are typically categorized
model-based or model-free methods. Model-free ap- proaches directly learn value functions to optimize policies and are widely used in practice due to their simple implementation (Jin et al., 2018) and low memory requirements, which scale linearly with the number of states. In contrast, model-based methods require quadratic memory costs.
In this paper, we focus on model-free RL for episodic tabular Markov Decision Processes (MDPs) with inbomogeneous transition kernels. Specifically, we consider an episodic tabular MDP with S states, actions, and H steps per episode. For such MDPs, the minimax regret lower bound over K episodes is (((/H2SATT) where T K the total number of steps (Jin et al., 2018).
Many model-free algorithms achieve /T-type regret bounds (Jin et al., 2018; Zhang et al., 2020; Li et al., 2021; Xu et al., 2021; Zhang et al., 2025b), with two (Zhang et al., 2020; Li et al., 2021) matching the minimax bound up to logarithmic factors. Except for AMB (Xu et al., 2021), which uses novel multi-step bootstrapping technique, all these methods rely on the Upper Confidence Bound (UCB) approach to drive exploration via optimistic value estimates.
In practice, RL algorithms often outperform their worst-case guarantees when positive suboptimal- ity gaps exist, meaning the best action at each state is better than the others by some margin. In the model-free setting, for UCB-based algorithms, Yang et al. (2021) proved the first gap-dependent re- gret bound for UCB-Hoeffding (Jin et al., 2018), of order Ö(H Amin), where Ô hides logarith- mic factors and A Amin is the smallest positive suboptimality gap 4 (8, a) over all state-action-step
"Zhong Zheng and Lingzhou Xue are co-corresponding authors.

---

Published as a conference paper at ICLR 2026
triples (s, a. h). Later, Zheng al. (2025b) improved the dependence H for UCB- ICB-Advantage (Zhang et al., 2020) and Q-EarlySettled-ANwe Advantagg (Li et al., 2021). However, these results rely on coarse-grained term SA/Amin instead of the fine-grained (s limiting their tightness.
The only model-free. non-UCB-based algorithm, AMB, achieved the first fine-grained regret upper bound by incorporating two key components: Upper and Lower Confidence Bounds (ULCB) and multi-step bootstrapping. In particular, ULCB leverages both UCB and Lower Confidence Bound (LCB) techniques to select actions by maximizing the width of the confidence interval, and multi- step bootstrapping updates Q-estimates with rewards of multiple steps from settled optimal actions. However, as detailed in Section 4, the multi-step bootstrapping procedure encounters two issues in its algorithm design and analysis. Algorithmically, the improper truncation in the multi-step boot- strapping update (see lines 13-14 Algorithm of Xu et al. (2021)) breaks the key link between the Q-estimates and historical V-estimates (see their Equation (A.5)) that is essential for the analysis. Theoretically, the concentration inequalities are incorrectly applied by centering the estimators in- duced by multi-step bootstrapping their expectations rather than on their conditional expectations (see their Equation (4.2) and Lemma 4.1), violating the required martingale difference conditions. These issues cast doubt whether rigorous fine- fine-grained gap-dependent regret bound can be tablished for non-UCB- basdd AMB algorithms.
In contrast, recent model-basee works (Simchowitz & Jamieson, 2019; Dann al., 2021; Chen et al., 2025) have achieved fine-grained gap-dependent regret bounds of the following form:
H Σ Σ
1
Zoaal
+
SA poly(H))
(1)
an(s,a)
Amin
Aa(s,))
where Zzae denotes the number of optimal (s, a, h) triples. These results incorporate individual suboptimality gaps As(s,u a) and significantly reduce reliance on the global factor 1/Amin- This progress naturally leads to the following open question:
Can we establish rigorous lineggrinedd gap-dependent regret upper bounds for model-free RL with individual suboptimality gaps (8, a) and improved dependence on 1/ Aimi??
Answering this question is challenging. For UCB-based algorithms, establishing fine- fine-grained gap- dependent regret requires novel techniques, particularly in bounding the cumulative weighted esti- mation error of Q-estimates. Existing works (Yang et al., 2021; Zheng et al., 2025b) treat all state- action pairs uniformly in the analysis. However, it is insufficient for deriving fine-grained results, as optimal and suboptimal pairs exhibit significantly different visitation patterns: suboptimal pairs are typically visited only Ó(log times (Zhang et al., 2025a), where Ô captures only the depen- dence on T. Ignoring this imbalance leads to loose bounds and an overly conservative dependence on 1/ Ammn Regarding the non-UCB-based algorithm AMB, it remains unclear whether the two estimators induced by multi-step bootstrapping jointly form an unbiased estimate of the optimal Q-function due to the randomness of the bootstrapping step. This property is crucial for the concen- tration analysis used to establish the optimism of AMB, yet was not shown Xu et al. (2021).
In this paper, we give an affirmative answer to the open question above by establishing the first fine-grained gap-dependent regret upper bound for UCB-based algorithms, along with rigorous counterparts for non-UCB- -bsed algorithms. Our main contributions are summarized below:
Novel Fine-Grained Analytical Framework for UCB-Based Algorithms. We develop a novel framework that explicitly distinguishes the visitation frequencies of optimal and suboptimal state- action pairs. Using this framework, we establish the first fine-graine grained, gap-dependent regret bound for a popular UCB-based algorithm, namely UCB Hoeffding (Jin et al., 2018). As shown in Sec- tion 5, UCB- Hoeffding demonstrates improved empirical performance compared to AMB.
Two Refinements of the AMB Algorithm with Rigorous Fine-Grained Analysis. In Section 4, we revisit the AMB algorithm and identify both algorithmic and analytical issues that undermine its theoretical guarantees. We then propose two refinements of the AMB algorithm:
UCB-Based Refinement. ULCB-Hoeffding Hooffding in Section 4.1 simplifies AMB by removing its prob- lematic multi-stey bootstrapping and retaining only the ULCB mechanism. Using our UCB-based achieves fine-grained regret bound, demonstrating
framework, we show that
2

---

Published as a conference paper at ICLR 2026
that algorithms relying solely on the ULCB principle can also achieve fine- finengrained guarantees. This further underscores the generality of our UCB-based ane-grained analytical framework.
Non-UCB-Ban BCBB-Baeed Refinement. We also propose Refined AMB, a non-UCB-basse refinement that incorporates both ULCB and multi-step bootstrapping techniques. It has the following im- provement: (i) removes improper truncations in the Q-updates, (ii) rigorously proves that the esti- mators induced by multi-step bootstrapping form unbiased estimate of the optimal Q-function, (iii) ensures the martingale difference condition holds, which justifies applying concentration in- equalities to these estimators, and (iv) establishes tighter confidence bounds. These refinmments allow us to rigorously prove the fine-grained regret upper bound for non-UCB-based algorithm and yield enhanced empirical performance, as shown in Section 5.
Technical Novelty. Our work introduces the following key technical innovations: (a) We analyze each state-action pair separately at every step, enabling a fine fine-granne grained upper bound on the cumulative weighted estimation error of the Qeestimates (Lemmas 3.2 and 3.3). (b) We establish a recursive re- lationship for cumulative weighted visitation counts across steps, supporting an inductive argument to obtain a fine-grained upper bound (Lemma 3.4), from which the expected regret upper bound follows (Lemmaa 3.1). (c) We perform a state-specific decomposition of conditional expectations in the concentration analysis of Refined AMB, enabling a recursive argument and induction over steps to show that the sum of two multi-step bootstrapping estimators is unbiased (Theorem 4.3 and Appendix G.3). The first two innovations, (a) and (b), form the core of our fine- ane-grained analytical framework, extending its applicability to wider range of model-free RL algorithms, while (c) offers a general technique for analyzing algorithms with multi-step bootstrapping.
2 PRELIMINARIES
In this paper, for any C E N4. we denote by [C] the set (1.2.....C) C}. We write [[x] for the indicator function, which takes the value one if the event is true, and otherwise. We also set
4 = 1og(25AT/p) with failure probability E (0, 1) throughout this paper.
Tabular Episodic Markov Decision Process (MDP). A tabular episodic MDP is denoted as M (S, A, H, H,P, r). where S is the set of states with [ = S, A is the set of actions with |A| = A, H is the number of steps in each episode, F {Px { is the transition kernel so that Pa 8, characterizes the distribution over the next state given the state-action pair (s, at step h, and r : {ra) are the deterministic reward functions with T% (s, a) [0. 1].
In each episode, an initial state 81 is selected arbitrarily by an adversary. Then, at each step h E [M].
an agent observes a state 8 E S, picks an action a₁ E A, receives the reward rh = rh (sh (4.) and then transits to the next state $4+1- The episode ends when an absorbing state sH+1 is reached.
Policies and Value Functions. A policy π is a collection of H functions {ma : S + AA)" |
h=1 where A is the set of probability distributions over A. A policy is deterministic if for any action a A. In this case, we denote (s)s) = a. Let VIT S + I denote the state value function at step h under policy π. Formally, B( (Sw, az) |sa. s). We also use Q7, S x A- R to de- (s) = = D#
S, (s) concentrates all the probability mass
note the state-action value function at step h under policy π, defined as (7, a) (s, + E Σi= Bler (w) [rw ( 188. = 8, 4n = a). Azar et al. (2017) proved that there al- ways exists an optimal policy xt that achieves the optimal value (s) = sup, V (s) V, (s) and (s,a) a) sup, QR (s. a) = Q% (s, a) for all (s. h) Sx x [H]. For any (s. a,,aa)).. h), the following Bellman Equation and the Bellman Optimality Equation hold, with ( = = V (+) = 0:
{ (T)(s) E,, (x) (s) (T)(s,))) (8) = (x + s... V and { (s(s max. EA (s, @s( = rn (8, a) + P Ps,a, Vi+1-
(2)
For any algorithm over K episodes, let & be the policy used in the k-th episode, and sf be the corresponding initial state. The regret over T = HK steps is Regret(T) := Ek= (Vr - VT (TT) (sf))
Suboptimality Gap. For any given MDP, we can provide the following formal definition. Definition 2.1. For any (s, a, h), the suboptimality gap is defined as A a) VA ())
3

---

Published as a conference paper at ICLR 2026
Equation (2) ensures that A,. (s. a) 2 0 for any (s,a, Ax H Accordingly, we define the minimum gap at each step h as follows.
Definition 2.2. Define A inf (n 0, 8 A} the minimum gap at step h. If the set (Aa(s, a)= (s a) > 0, (8, E S x A] is emply, we sel Amin, oc.
Most gap-dependent works (Simchowitz & Jamieson, 2019; Xu al., 2020; Dann et al., 2021; Yang et al., 2021; Zhang et al., 2025a) define a minimum gap as Amia- = inf a) (s, > 0, (s, a. h) E S x A []]. By definition, obvious that Aminh 2 Amia for all [H].
KINE-GRAINED REGRET UPPER BOUND FOR UCB-BASED ALGORITTMS
In this section, present the first fine-grained, gap-dependent regret analysis for UCB Bcbdddeed (Jin et al., 2018), using our novel framework introduced in Section 3.2. To demonstrate the generality of our approach, introduce new UCB-based algorithm, ULCBB Hoeffding, in Section 4.1 and establish a fine-graie fine-grained regret bound for with the same framework.
3.1 THEORETICAL GUARANTEES FOR UCB-HORFFDING
We first review UCB- JCB-Hoeffding in Algorithm 1. At the start of any episode k. keeps an upper bound Q% on Q% for each (s, a. h), and selects actions greedily. The update of Qh uses the standard Bellman update with step size 7 = (H + 1)/ HH ++) and Hoeffding bonus b, For convenience, for
any N E 2 and 1 < i < N, we additionally define n = 1, no and 11," = = II (1-
A Algorithm UCB-Hoeffding
1: Initialize Q (s, a) < H and (7, a) < 0 for all (s, a, h).
2: for episode k 1,..,, K, after receiving of and setting V#+1 = 0, do
3: for step h = 1,..,, H do
4: Take action af = arg max, (s a'), and observe shit1-
5:
t= N (sk a <- ( a + 1; by 2/////l.
6:
( at) (1 n. @h a +mlrass ax) Vk ( be].
7:
(s = min H, max Q ( (st d'))
8:
QA (s, ()
= (x),
(8, ((s + (0h at).
9:
end for
10:
end for
Next, we present the fine-grate fine-grained gap-dependent regret upper bound for (CB-Hoeffding
Theorem 3.1. For UCB- Hoefffiing (Algorithm 1). the expected regret EE [[eegret(T) is bounded by
(
HD (og(SAT)
H 2 / Zop,, log(SAT)
+SAH*)
(3)
(ssaa)
Amin,A
An(s,))0
Here for any E [H], Zopu, = ((., () E AlAx(8,0) 0} with S S /Zop,Al SAA
In the ideal case where the MDP contains only a single suboptimal state-action-step triple (s, a, h) with h = H, our result exhibits a significantly improved dependence on the minimum gap, namely Õ(H3/ ((H))Amin) compared to the Ö(H S A/Amin) dependence in Yang et al. (2021). Even in the worst scenario where all suboptimality gaps satisfy (s,s, a) Amin: our result degrades gracefully to match the result in Yang et al. (2021). These findings demonstrate that our result outperforms that of Yang al. (2021) in all cases for the UCB- CCB-Hoeffding algorithm.
By applying the derive the following weaker but simpler upper bound on the expected regret from Equation (3):
inequality and noting that Amin.h 2 Amin for all fa E [M], we can
HD log(SAT) an(s,a)
HD Zopl (Sg(S)T)
Σ
+
+ SAH
Amin
A=
(8.a)20
where Zup ((8, E A (8, a) =0 is the set of optimal state-action-step trippe......
4

---

Published as a conference paper at ICLR 2026
Remark: The lower bound established in Simchowitz & Jamieson (2019) shows that any UCB- based algorithm, such as UCB- -CB-Hooffding, must incur gap-dependent expected regret of at least
E
Σ
H
S
(s.a)20 (n(s,a)
Aii
Our result matches this lower bound up to polynomial factors
the ideal scenario where /Zppl is independent of A, such in MDPs with constant number of optimal actions per state.
Xu et al. (2021) also provides lower bound (O( Zmal / Ammn) for all types of algorithms when HS -
1mmal _ HS4 Here, for any h [H]
Zmu a, h) E A [M] An a) 0, Zonp (8) 13,
where (s) fa A (s a) 0}. When HS S 1mmi I HSA it holds that |Zopl I
2
Zmmll and therefore the lower bound can be expressed as Z min). This demonstrates the tightness of the dependence on /Zppi/ /ii in the second term of our result.
3.2 A NOVEL GREAIGRANEE ANALYTICAL FRAMEWORK
In this subsection, we introduce the novel analytical framework used to derive fine-grained, gap- dependent regret upper bounds. Full proofs deferred to Appendix E. The key ideas of our fine- grained analytical framework are summarized below:
(I) We first establish Lemma 3.1, which upper-bounds the regret the expectation of the cumula- tive weighted visitation counts Σ E. (s N)N (s, a) and further relates this term the cumulative weighted estimation errors Σ w (Q) (s) af).
(2) We then bound the cumulative weighted estimation errors by establishing a recursive relationship between consecutive steps (Lemma 3.2) and propagating it to the final step H (Lemma 3.3).
(3) Using Lemmas 3.2 and 3.3, we derive a recursive relation for the cumulative weighted visitation counts Σ. s.a Au (s, a)
N K + (s, a) across steps, which enables an inductive argument to derive a fine-grained upper bound and subsequently bound the expected regret via Lemma 3.1.
3.2.1 BOUNDING EXPECTED REGRET WITH CUMULATIVE WEIGITED ESTIMATION ERROR
We begin with Lemma 3.1 that connects expected regret to suboptimality gaps: Lemma 3.1. For the UCB- (CB-Hoeffding algorithm with K episodes and total T = HK steps, we have:
E (Regret(T)) = E Σ Σ Nz (s.
8,a
Lemma 3.1 holds universally for any learning algorithm, shown in Lemma E.2. Therefore, bound- ing the expected regret reduces to controlling Σ E., a) +1 (s, a), which further
be bounded by the cumulative estimation error H ". (0) Q7) (s at). In particular, for any step h and episode k; with high probability, we have
(Qh: Qt) (s), at) 2 (s)) (s at) 2 VV Q1 att (n
(4)
Here, the first inequality follows from line 7 Algorithm 1, and the second holds due to the opti- mism property V 2 Vi and Q Q of UCB- HCB-Hoeffding (see Lemma E.I). With Equation (4), prior works (Yang et al., 2021; Zheng et al., 2025b) focused on bounding the cumulative weighted estimation error Ek (h2 (s) at) and established the following type of upper bound:
k=
K
Σ HASAlww 11) 1 + Σ ECn) (5)
"
Σ (Qt: 27) o < 0 K=1
KEW
where { is a non neg-tieeeive weight sequence and C(h') collects the remaining terms at step W. The norms [- 1i') loo and (wa(;;,)) at step h are defined in Equation (7) later.
5

---

Published as a conference paper at ICLR 2026
inequality to the cumulative weighted bonus Σx o N over all state-action pairs at any step h. However, as shown in Lemma 4.1 of Zhang et al. (2025a), in the gap-dependent setting, suboptimal state-action pairs (s, a) at any step h with Q7 (s. a)
Equation (5) is obtained by applying the
(s) are visited most Ó(log T) times, whereas optimal pairs can be visited infinitely often. Thus, uniform analysis of all state-action pairs leads to loose bounds.
3.2.2 SEPARATE ANALYSIS FOR EACH STATE-ACTION PAIR
To address the looseness of uniform analysis, we analyze the cumulative weighted estimation error for each state-action pair at every step, enabling tighter control.
For any given step h and non non-negatin negative weight sequence T we define the following weights for any k' E []], h & H < H:
NR++
wh (k', hb) = whth wh (K, +1): =
Σ
wh
H. ahr a 1'
(at (6)
N=
with the norms
|a (1,11))lox max (K,K)) (-)n,,'))ll ME[[]
Σ wn (K 1²).
Here, (8,8, a, h) denotes the episode index of the i-th visit to (8, h) and (s, denotes the
number of visits to (s, a, h) before episode k. The weight wn'k', h' + 1) captures the contribution of the term (Q%++ - (s +1) when recursively bounding the cumulative weighted estimation error from step h' to h' + 1 as shown in the second conclusion of Lemma 3.2 later.
For each state-action pair (s, a), we define the state- action specific weight at any step h S h/ < H as wi (K' h/ s, a) (h'k', h²). I[(s ) = (s,a)] with the corresponding norms given by
K
[| h1, s,,hh,... a,)))= == max wn (k', ,,,,,,)) s,,,, [|w h 8, a) KE[R]
W 8,a).
Additionally, for any state-action pair (x, a), we also define
(k' h' +1,,, = (k h + 1)][(sH a = a)].
The weight (W', h/ + 1, s,a) a) characterizes the weight of the term (Q% Qh (s 1 ) when bounding the cumulative weighted estimation error for each state-action pair (s, a) step h as shown in the first conclusion of Lemma 3.2 later.
We are now ready to present Lemma 3.2, which bounds the cumulative weighted estimation error for each state-action pair (s, a) at any subsequent steps h' E hh H]. It is derived by recursively using the Q-update (line 6 of Algorithm 1). The detailed statement is given in Lemma E.3, followed by its proof. Here, we use the shorthand (8, aai = (s%, a²))
Lemma 3.2. For UCB-Hoeefdiin algorithm, with probability least 1 1 p. for any non-negative weight sequence (w)) y at step h, the following two conclusions hold simultaneously for any (8, a) E A and subsequent step h' H):
K
K (n', + +1,8, ()(0 Qi+ (2,
Wh (kc, K., 8, (Q 2i (sh) ( S
k=1
k'=1
+ ||w h h1)llooot + / H (- 100 (,,',,,)))
and
K
K
wp (k, h1') (Qk @%:) (s/h ( S
Σ
wh wh('', , W + 1)(Q Qi W
==1
+ +Iwwn(, (.),)))))) S.ll
16 Σ
11 w/, (-, 1wh (,,, a)

---

Published as a conference paper at ICLR 2026
Iteratively applying recursions over steps h ...... H in the second conclusion of Lemma 3.2, and using the recursively defined weights wn wn(k, k'), we obtain the following Lemma 3.3:
Lemma 3.3. For UCB- CCB-Hoeffding, with probability least 1 - p. for any non-negative weights (wo he at step h, holds simultaneously for any (s, a) E S x and subsequent step h E [h, H):
(k, h6) (Qh -Kie) (she )
H Σ EVHs 1oollolllll h1, 8, a) An m/ 8,0
(w SAH + 16 hr
The formal statement is presented in Lemma E.4, followed by its proof. Unlike the upper bound derived from the uniform analysis in Equation (5), Lemma 3.3 retains the individual contributions / (I oloo | (,,/1, 8, a) [14. This allows tighter upper bound under the uneven visita- tions across different triples in the gap-dependent analysis.
3.2.3 INDUCTIVE ANALYSIS FOR CUMULATIVE WEIGHTED VISITATION COUNTS
We partition the state-action pairs at each step h into two subsets: Zopn containing optimal state- action pairs, where (s, a) and suu = {(s,, a) A)) (8, a) > 0} containing suboptimal state-action pairs. Then for any given step h, when Equation (4) holds, we set the weight as:
[ (s at) An (8% af), (s% (a)) E Zu
[[>h ax) E Z 1.
The second equality follows directly from Equation (4). Using this choice, applying the first conclu- sion in Lemma 3.2 with h' = h, the bound [[ ll S 1, and the fact that [[wn(' h, 8, a)llz S N +1 (s, a), we obtain the following inequalities for any state-action pair (8, a) E Zuibhi
(s, (s, & 1 (h - (sh aah.aaa)iii Is a = (s,
K
K s K==1 (K', h L,s wK + a) with (8,a) E Z and (s a) > 0, we reach:
1 :
o + 16y
K+1 H (8)
Solving this inequality for A (8, a) No
2 An(s,a)
2H + Σ Wn(k' h 1, a,) Qh+ (s 11))
Define Enub as the summation over all suboptimal state-action pairs (8.a) a) E Zubb. Summing the inequality above over all (s,a) a) E Zuhh, and noting that (s, 0 for (s,a) Zub
Σ sub Wn (K' h + 1, - Σnp Wn h 1, 8, wn (K' h h+11,
together with the optimism property Q 2h+1 by Lemma E.I, obtain:
2
K
Σ (o K+ - Σ
+2AHH (s)
Σ ( #=1
8.0
sub
Applying Lemma 3.3 with H = h + to the last term in the equation above and defining C'(h) = O(H2SA+ Emd H An (s, a)) to collect the remaining terms, we have
(s. An (s, - (' + Σ Σ EV
(111)) ( H1, 8,a))l.,
s,4
W=++1 8.a
To bound the last term in Equation (9), apply the Stuchy-Schward inequality by distinguishing between optimal and suboptimal state-action pairs. Specifically, we apply the inequality separately to the optimal state-action pairs in Zop for each step h²' and collectively to all suboptimal state- action pairs across steps h < h < H. This separation enables a sharper bound of
Σ W=
H Zap.
H3r
Σ AN sub,
Σ A K+ (s.a)
(10)
sub.
7

---

Published as a conference paper at ICLR 2026
where the shorthand Saa denotes the summation over all (s. Zub, for h < h' I H. This result also relies on the following three properties proved in Equations (27) to (29) of Lemma E.5:
[wn( (, S
> ( (,, < [[wa(s (,)l,, [|aa(, (', a,,)), S 0 (N +1 (s.u)).
Plugging the bound from Equation (10) into Equation (9) yields a recursive relation between (NN+++1ss. N a) step h and future steps. Applying induction from H down to 1, we obtain fine- mne-grained upper bound on the cumulative weighted visitation Σs, ( a) *
E.. (s,
Lemma 3.4. For UCB- Hoeffding algorithm and sufficiently large constant C1 0, with probabil- ity at least - p. holds simultaneousty for any h E [H] that:
a (K (s.. I SAH +
H Σ
H
H3 (Eih41 v Zugn.
+
C1
(s,
Amin,h
Wi Au(ss,))0
2
H² [EiN4a v Zope.el
miin,
M=++1
The full proof is provided in Lemma E.5. By combining this result with Lemma 3.1, we complete the proof of Theorem 3.1, establishing the desired fine-grained, gap-dependent regret upper bound.
4 GRNA-GRINNED GAP-DEPENDENT REGRET UPPER BOUND FOR AMB
The AMB algorithm (Xu et al., 2021) was proposed to establish a fine-grained, gap-dependent regret bound. However, we identify issues in both its algorithmic design and theoretical analysis that prevent it from achieving valid fine-grained guarantees. We first summarize these issues below.
Improper Truncation of Q-Estimates in Algorithm Design. AMB maintains upper and lower estimates on the optimal Q-value functions, denoted by Q and Q. respectively. However, during multi-step bootstrapping updates of these estimates, applies truncations 13-14 in Algorithm 3). This design breaks the recursive structure linking Q-estimates to historical Veestimates. In particular, it invalidates their Equation (A.5), which is essential for establishing the theoretical guarantee on the optimism and pessimism of Q-estimates Q and Q, respectively.
and 0 (see lines
Violation of Martingale Difference Conditions in Concentration Analysis. AMB uses multi-step bootstrapping and constructs Qeestimates by decomposing the Q-function into two parts: rewards accumulated along states with determined optimal actions, and those collected from the first state with undetermined optimal actions. When proving optimism and pessimism of the Q-estimates (see their Lemma 4.2), Xu et al. (2021) attempt to bound the deviation between the Q-estimates and Q" using Azema-Honfiding inequalities. However, when analyzing the two estimators arising from the Q-function decomposition (see their Equation (4.2) and Lemma 4.1), each term is improperly cen- tered around an incorrect expectation because the randomness of the bootstrapping step is ignored, thereby violating the martingale-differrneee condition required for the Azuma-Hoeffdiie inequality.
These issues compromise the claimed optimism and pessimism guarantees for the Q-estimates and invalidate the stated fine-grained gap-dependent regret upper bound in Xu et al. (2021). A detailed analysis is provided in Appendix G. To address these issues, we propose two refinements: UCB-based refinement, ULCB- B.CB-Hoeffding, and non-UCB-bast refinement, Refined AMB.
4.1 UCB-BASER REFINEMENT: LLCB-HOEFFDING
In this subsection, we introduce the UCB-based refinement of AMB, ULCB-Hoefdding It also achieves a fine-grained regret upper bound and demonstrates improved empirical performance over AMB. Importantly, our fine-grained analytical framework presented in Section 3.2 naturally extends to this variant, demonstrating the framework's 's flexibility and generality.
The ULCB- LLeB-Hooffiiig algorithm is presented in Algorithm At the start of each episode k ULCB- Hoeffding maintains upper and lower bounds, Φ (s, and 2¹ (s, a), of the optimal value func-
8

---

Published as a conference paper at ICLR 2026
tion (s. for any (s, a)). It then constructs candidate action set A by eliminating tions that are considered suboptimal (see line 14 in Algorithm 2). Specifically, if action a satisfies Qh k+1
(s,a) a) < (s), then by line in Algorithm 2, there exists another action a' such that @)(s, S x (s.a) (s) I <s,'' I (s, (', which confirms that the action is suboptimal. At the end of episode k. the new policy T. (s) is chosen to maximize the width of the confidence interval (Qh (hh+! - (s, a), which measures the uncertainty in the Qesttimates.
Algorithm 2 ULCB- B.eB-Hoofg
1: Initialize: Set the failure probability p E (0, 1), (s, = V1() + H. Q (v)()))((())))
(s, a) < and A (s) A for any (s, a, h) E A x (H].
2: for episode k 1, ....., K, after receiving of and setting V HH1 Vil KH+i(1) 0, do
3: for step h = 1..... H do
arg max AE (<) ( - 25 a).
IA
4:
Choose of
if (s))) = and get * h+11
the only clement in A/
5:
Sett = 1 ) + (s a + 1 and the bonus b, = 2/ H and update:
2n (sh: a = (1 m Q (s ) + (n o + Vh+ ( + bq
6:
7:
T (5% ) (1 me 2 (s ) + (n at) k (0/+1) - b
8:
whtt ( min { H, max 1
2 (sh
9:
1h++ (st) max (, A (s))
2 (o a)}
10:
end for
for
(s,a,)) h) E S Ax [H] {(5),, ) do
12: (Q Q++1 _N (s, a) (Qn, 2¹h Nz) (s. a). (v k+1 V
)s,
,b,t) (s) =(V (t).
13:
end for
14: v(s, S x [H] update (s) {a (s) t (s))
(s))
15:
end for
The main difference between ULCB- Hoeffding and AMB lies in the updates of Q-estimates. ULCB- Hoeffding uses the standard Bellman update (lines 6-7 of Algorithm 2), similar UCB-Hoeffding (line 6 of Algorithm 1), which is essential to prove fine-grained regret upper bound. In contrast, AMB uses multi-step bootstrapping update, which will be detailed Section and Appendix G.I.
We now present both worst-case and gap-dependent regret upper bounds for ULCB- CCBB-Hoffdiing. Theorem 4.1. For any p E (0, 1), let log(2S /p). Then with probability least p.
Hoeffdngg (Algorithm 2) satisfies Regret( s O O(
The proof of Theorem 4.1 is provided in Appendix F.2. The resulting bound matches the -ttyppe worst-case regret guarantee of HoeffHigg (Jin et al., 2018).
Theorem 4.2. For ULCB- ULCB-Hoeffile Hoeffding (Algorithm 2). the expected regret is upper bounded by (3).
The proof of Theorem 4.2 is given in Appendix F.3 using the fine-grained analytical framework developed in Section 3.2. ULCB-Hoeffdin attains the same fine-grained gap-dependent regret up- per bound as CCC--Hoffdiigg As discussed in Section 3.1. the guarantee in Equation (3) matches the lower bound established by Simchowitz & Jamieson (2019) for UCB- algorithms, with a tight dependence ZZp Amin that also aligns with the lower bound in Xu et al. (2021), up to polynomial factors in H.
4.2 NON-UCB-BAN BASED REFINEMENT: REFINED AMB
Since multi-step bootstrapping can improve the regret's dependence on 1/Amin, propose non- UCB-based refinement, Refined AMB, which incorporates both ULCB and multi-step bootstrap- ping. The following key modifications introduced to address the two issues of AMB:

---

Published as a conference paper at ICLR 2026
(a) Revising Update Rules. We remove the truncations in the updates of Q-estimates and instead apply them to the corresponding Vesstmattes. This preserves the crucial recursive structure linking Q-estimates to historical V -estimatees used in the theoretical analysis.
(b) Establishing Unbiasedness of Multi-Step Bootstrapping. We rigorously prove that the esti- mators from multi-step bootstrapping form an unbiased estimate of the optimal value function Q"
(c) Ensuring Martingale Difference Condition. We ensure the validity of Azuma Hoeffd-n in- equalities by centering the multi-step bootstrapping estimators around true conditional expectations.
(d) Tightening Confidence Bounds. By jointly analyzing the concentration of both estimators, we tighten the confidence interval and halve the bonus, leading to improved empirical performance.
These modifications not only ensure theoretical validity but also yield improved empirical perfor- mance. The refined algorithm is presented in Algorithms 4 and 5 of Appendix G.2. We further establish the following optimism and pessimism properties for its Q-estimates.
Theorem 4.3 (Informal). For the Refined AMB algoritlum, with high probability, @)(s,a) 2 (1, a) 2 (8, a) holds simultaneously for all (s, a,,a, h, k) E S A [H] [K].
The formal statement is given Theorem G.I, with its proof in Appendix G.3. Based on this result, can follow the remaining analysis of Xu al. (2021) to prove the following regret upper bound:
H log(SAT)
H 2mal log( S AT)
Σ Σ 1=11 An(s,))20
(11)
an(
A min
NUMERICAL EXPERIMENTS
In this section, we present numerical experiments' conducted in synthetic environments, evaluat- ing four algorithms: AMB, Refined AMB, UCB-Hoeffding, and ULCB-Hoeffing. We consider four experiment scales with (H. S, A, K) = (2, 3, 3, 109), (5, 5,5,6 6 x 10)). (7, 8, 6,5 x 109), and (10, 15, 10, 107). For each (s, a, h). rewards ra (s, a) are sampled independently from the uni- form distribution over [0, 1], and transition kernels P- s,a) are drawn uniformly from the S- dimensional probability simplex. The initial state of each episode is sampled uniformly random from the state space.
We also set + = and the bonus coefficient c == for UCB-Hoeffding, ULCB- Hoef-Hefd,ing. and Re- fined AMB, and = 2 for AMB. This is because AMB applies concentration inequalities separately to the two estimators induced by multi-step bootstrapping. In contrast, all other algorithms, includ- ing the Refined AMB that combines the concentration analysis for multi-step bootstrapping, apply the concentration inequality only once, resulting in bonus term with half the constant.
To report uncertainty, collect 10 sample trajectories per algorithm under the same MDP instance. In Figure 1 of Appendix B, we plot Regret(T)/ log( K + 1) versus the number of episodes K. Solid lines indicate the median regret, and shaded regions represent the 10th-90th percentile intervals.
The results show that UL.CB-Hofffde outperforming the original AMB, while UCB- CCB-Hoeffding performs the best overall. In all settings, the regret curves for all algorithms except AMB flatten as K increases, indicating logarithmic growth in regret, which consistent with the fine-grained theoretical guarantees.
and Refined AMB achieve comparable performance, both
6 CONCLUSION
This work establishes rigorous fine-grained gap-dependent regret bounds for model-free RL in episodic tabular MDPs. In the UCB-based setting, we introduce novel analytical framework that enables the first fine-grained regret analysis of UCB-Hoeffdingg For the non-UCB-based AMB algorithm, we propose two refinements. rithmic and analytical issues. In particular, for Refined AMB, we establish rigorous fine- -reegga regret bound in the non- OCB setting, while also demonstrating improved empirical performance.
and Refined AMB, that address its algo-
'll experiments were conducted desktop equipped with an Intel Core 17-14700F processor and com- pleted within 12 hours. The code included in the supplementary materials.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENT
The work of Haochen Zhang, Zhong Zheng, and Lingzhou Xue was supported by the U.S. National Science Foundation under the grants DMS-1953189 and CCF-2007823 and by the U.S. National Institutes of Health under the grant IR01GM152812.
ETHICS STATEMENT
This work is purely theoretical and does not involve human subjects, personal data, any exper- iments requiring ethical approval. We have followed all guidelines outlined in the ICLR Code of Ethics, ensuring transparency, integrity, and fairness throughout the research process. There foresceable ethical concerns or potential harms related to this study.
REPRODUCIBILITY STATEMENT
To ensure reproducibility, we provide detailed theoretical analyses, including a clearly defined tab- ular MDP framework and assumptions in Section 2, well as proof sketch outlines in Sections and 4. Full proofs are included in the appendix. For the empirical results included in Section 6, all experiments were conducted on a desktop equipped with an Intel Core 17-14700F processor over 12-hour period. The complete source code is provided in the supplementary materials to support independent verification.
USE OF LARGE LANGUAGE MODELS
In this work, the use of large language models was strictly limited to text polishing and language refinement. All core scientific ideas, problem formulation, methodology design, and experimental planning were independently developed by the authors.
REFERENCES
Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with gener- ative model minimax optimal. In Conference on Learning Theory, pp. 67-83. PMLR, 2020.
Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst- case regret bounds. Advances in Neural Information Processing Systems, 30, 2017.
Aymen Al Marjani and Alexandre Proutiere. Best policy identification in discounted mdps: Problem-specific sample complexity. arXiv preprint arXiv:2009. 13405, 2020.
Aymen Al Marjani, Aurélien Garivier, and Alexandre Proutiere. Navigating to the best policy in markov decision processes. In Advances in Neural Information Processing Systems, pp. 25852- 25864, 2021.
Peter Auer and Ronald Ortner. Logarithmic online regret bounds for undiscounted reinforcement learning, Advances in Neural Information Processing Systems, pp. 49-56. MIT Press, 2007.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in Neural Information Processing Systems, 21, 2008
Mohammad Gheshlaghi Azar, Ian Oshand, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International Conference on Machine Learning, pp. 263-272, PMLR, 2017.
Shulun Chen, Runlong Zhou, Zihan Zhang, Maryam Fazel, and Simon Du. Sharp gap-dependent variance-aware regret bounds for tabular mdps. arXiv preprint arXivv2506.0652/ 2025.
Christoph Dann, Lihong Li, Wei Wei. and Emma Brunskill. Policy certificates: Towards account- able reinforcement learning. In International Conference on Machine Learning, pp. 1507-1516. PMLR, 2019.
11

---

Published as a conference paper at ICLR 2026
Christoph Dann, Teodor Vanislavov Marinov, Mehryar Mohri, and Julian Zimmert. Beyond value- function gaps: Improved instance-dependent regret bounds for episodic reinforcement learning. In Advances in Neural Information Processing Systems, pp. 1-12,201 2021.
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient bias-span-constraineed exploration-exploottioon in reinforcement learning. In International Conference on Machine Learning. pp. 1578-1586. PMLR, 2018.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. In International Conference on Machine Learning, pp. 4171-4484. PMLR, 2021.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research,
2010.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably effi cient? Advances in Neural Information Processing Systems, 31, 2018.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward free exploration for reinforcement learning. In International Conference on Machine Learning, pp. 4870-4879. PMLR, 2020.
Anders Jonsson, Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Edouard Leurent, and Michal Valko. Planning in markov decision processes with gap-dependent sample complexity. In Advances in Neural Information Processing Systems, pp. 1253-12653 2020.
Sham Kakade, Mengdi Wang, and Lin F Yang. Variance reduction methods for sublinear reinforce- ment learning. arXiv preprini 18020080 04, 2018.
Safwan Labbi, Daniil Tiapkin, Lorenzo Mancini, Paul Mangold, and Eric Moulines. Federated ucbvi: Communication-efficeen federated regret minimization with heterogeneous agents. arXiv preprint arXiv:2410.22908 2024.
Gen Li, Laixi Shi, Yuxin Chen, Yuantao Gu, and Yuejie Chi. Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Advances Neural Information Processing Systems, 34:17722-17776, 2021.
Pierre Ménard, Omar Darwiche Domingues, Xuedong Shang, and Michal Valko. Ucb momen- tum q-learning: Correcting the bias without forgetting. In International Conference on Machine Learming, pp. 7609-7618. PMLR, 2021.
Thanh Nguyen-Tanne Ming Yin, Sunil Gupta, Svetha Venkatesh, and Raman Arora. On instance- dependent bounds for offline reinforeement learning with linear function approximation. In Pro- ceedings of the AAAI Conference on Artificial Intelligence, pp. 9310-9318. 2023.
Jungseul Ok, Alexandre Proutiere, and Damianos Tranos. Exploration in structured reinforcement
learning. Advances in Neural Information Processing Systems, 31, 2018
Matteo Papini, Andrea Tirinzoni, Aldo Pacchiano, Marcello Restelli, Alessandro Lazaric, and Mat- teo Pirotta. Reinforcement learning in linear mdps: Constant regret and representation selection. Advances in Neural Information Processing Systems, 34:16371-16388 2021.
Max Simchowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. In Advances in Neural Information Processing Systems, 2019.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, 2018.
Mohammad Sadegh Talebi and Odalrie-Ambrym Maillard. Variance-aware regret bounds for undis- counted reinforcement learning in mdps. In Algorithmic Learning Theory, pp. 770-805. PMLR, 2018.
Ambuj Tewari and Peter Bartlett. Optimistic linear programming gives logarithmic regret for irre- ducible mdps. In Advances in Neural Information Processing Systems, pp. 1505-1512, 2008.
12

---

Published as a conference paper at ICLR 2026
Andrea Tirinzoni, Aymen Al Marjani, and Emilie Kaufmann. Near Instance-optinen pac reinforce- ment learning for deterministic mdps. In Advances in Neural Information Processing Systems, pp. 3785-8798, 2022.
Andrea Tirinzoni, Aymen Al-Marjani, and Emilie Kaufmann. Optimistic pac reinforcement learn- ing: the instance-dependent view. In International Conference on Algorithmic Learning Theory, pp. 1460-1480. PMLR, 2023.
Andrew Wagenmaker and Kevin G Jamieson. Instance-dependent near-optimal policy identification in linear mdps via online experiment design. Advances in Neural Information Processing Systems, 35:5968-599 -9811 2022.
Andrew Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamicson. First- order regret in reinforcement learning with linear function approximation: A robust estimation approach. In International Conference on Machine Learning, pp. 22384-22422 PMLR, 2022a.
Andrew Wagenmaker, Max Simehowitz, and Kevin Jamieson. Beyond no regret: Instance- dependent pac reinforcement learning. In Conference on Learning Theory, pp. 358-418. PMLR, 2022b.
Xinqi Wang, Qiwen Cui, and Simon S Du. On gap-dependent bounds for offlin reinforcement learning. Advances Neural Information Processing Systems, 35: 15:14885-14877, 2022.
Haike Xu, Tengyu Ma, and Simon Du. Fine-grained gap-dependent bounds for tabular mdps via adaptive multi-step bootstrap. In Conference on Learning Theory, pp. 4438 4472. PMLR, 2021.
Tengyu Xu, Zhe Wang, Yi Zhou, and Yingbin Liang. Reanalysis of variance reduced temporal difference learning. In International Conference on Learning Representations, 2020.
Kunhe Yang, Lin Yang, and Simon Du. Q-learning with logarithmic regret. In International Con- ference on Artificial Intelligence and Statistics, pp. 1576-1584. PMLR, 2021.
Andrea Zanette and Emma Brunskill. Tighter problem-dependee regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pp. 7304-7312, PMLR, 2019.
Haochen Zhang, Zhong Zheng, and Lingzhou Xue. Gap-dependent bounds for federated SqS- learning. In Forty-second International Conference Machine Learning, 2025a.
Haochen Zhang, Zhong Zheng, and Lingzhou Xue. Regret-optimal q-learning with low cost for single-agent and federated reinforcement learning, arXiv preprint arXiv:2506.0466 2025b.
Haochen Zhang, Zhong Zheng, and Lingzhou Xue. Gap-dependent bounds for nearly minimax opti- mal reinforcement learning with linear function approximation. arXiv preprint arXiv:2602.20297, 2026.
Weitong Zhang, Zhiyuan Fan, Jiafan He, and Quanquan Gu. Achieving constant regret in linear markov decision processes. Advances Neural Information Processing Systems, 37:130 130738, 2024a.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference-advantage decomposition. Advances in Neural Information Processing Systems, 33: 15198-15207, 2020.
Zihan Zhang, Xiangyang Ji, and Simon Du. Is reinforcement learning more difficult than bandits? ncar-optimal algorithm escaping the curse of horizon. In Conference on Learning Theory, pp. 4528 4531. PMLR, 2021.
Zihan Zhang, Yuhang Jiang, Yuan Zhou, and Xiangyang Ji. Near-optimal regret bounds for multi- batch reinforcement learning. Advances in Neural Information Processing Systems, 35:24586- 24596, 2022.
Zihan Zhang. Yuxin Chen, Jason Lee, and Simon Du. Settling the sample complexity of online reinforcement learning. In Conference Learning Theory, pp. 5213-5219. PMLR, 2024b.
13

---

Published as a conference paper at ICLR 2026
Heyang Zhao, Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Variance-dependee regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency. In The Thirty Sixth Annual Conference Learning Theory, pp. 4977-5020. PMLR, 2023.
Zhong Zheng, Fengyu Gao, Lingzhou Xue, and Jing Yang. Federated q-learning: Linear regret speedup with low communication cost. In The Twelfth International Conference on Learning Representations, 2024.
Zhong Zheng, Haochen Zhang. and Lingzhou Xue. Federated q-learning with reference-advantage decomposition: Almost optimal regret and logarithmic communication cost. In The Thirteenth International Conference on Learning Representations, 2025a.
Zhong Zheng. Haochen Zhang, and Lingzhou Xue. Gap-dependent bounds for q-learning using reference-advantage decomposition. In The Thirteenth International Conference Learning Representations, 2025b.
Runlong Zhou, Zhang Zihan, and Simon Shaolei Du. Sharp variance-dependent bounds in reinforce- ment learning: Best of both worlds in stochastic and deterministic environments. In International Conference on Machine Learning, pp. 42878 42914. PMLR, 2023.
14

---

Published as a conference paper at ICLR 2026
In the appendix, Appendix A reviews related work, and Appendix B presents the experimental results. Appendix C presents a comparison of results and techniques with model-based works. Appendix D introduces several lemmas that support our proofs. Appendix E establishes the fine- grained gap-dependent regret upper bound for the UCB-Hoeffding algorithm, marking the first such result for UCB-based method. Appendix F provides proofs for both the worst-case and fine- grained gap-dependent regret bounds of the ELCB-Hoefiding algorithm. Finally, Appendix G offers a detailed analysis of both algorithmic and technical issues of the original AMB algorithm and presents proof of the fine- ine-grained regret bound for our Refined AMB algorithm.
A RELATED WORK
Online RL for Tabular Episodic MDPs with Worst-Case Regret. There are mainly two types of algorithms for reinforcement learning: model-based and model-free algorithms. Model- based algo- rithms learn a model from past experience and make decisions based on this model, while model-free algorithms only maintain a group of value functions and take the induced optimal actions. Due to these differences, model-free algorithms are usually more space-efficient and time-efficient com- pared to model-based algorithms. However, model-based algorithms may achieve better learning performance by leveraging the learned model.
Next, we discuss the literature on model- and model-free algorithms for finite-horizon tabular MDPs with worst-case regret. Auer et al. (2008), Agrawal & Jia (2017), Azar et al. (2017), Kakade et al. (2018), Agarwal et al. (2020), Dann et al. (2019), Zanette & Brunskill (2019),Zhang et al. (2021), Zhou et al. (2023) and Zhang al. (2024b) worked on model-based algorithms. Notably, Zhang al. (2024b) provided an algorithm that achieves regret of Ömiin V AHHT, T)), which matches the information lower bound. Jin et al. (2018), Zhang et al. (2025b), Zhang et al. (2020), Li et al. (2021) and Ménard et al. (2021) work on model-free algorithms. The latter three have introduced algorithms that achieve minimax regret of Ö(V AH2T). There are also several works focusing on online federated RL settings, such as Zheng et al. (2024), Labbi et al. (2024), Zheng et al. (2025a), and Zhang et al. (2025b). Notably, the last three works all achieve minimax regret bounds up to logarithmic factors.
Suboptimality Gap. When there exists a strictly positive suboptimality gap, logarithmic regret be- comes achievable. Early studies established asymptotic logarithmic regret bounds (Auer & Ortner, 2007: Tewari& & Bartlett, 2008). More recently, non-asymptotic bounds have been developed (Jaksch et al., 2010; Ok et al., 2018; Simchowitz & Jamieson, 2019; He et al., 2021). Specifically, Jaksch et al. (2010) designed a model-based algorithm whose regret bound depends on the policy gap in- stead of the action gap studied in this paper. Ok et al. (2018) derived problem-specifie logarithmic- type lower bounds for both structured and unstructured MDPs. Simchowitz & Jamieson (2019) extended the model-based algorithm proposed by Zanette & Brunskill (2019) and obtained logarith- mic regret bounds. More recently, Chen et al. (2025) further improved model-based gap-dependent results. Logarithmic regret bounds have also been established in the linear function approximation setting (He et al., 2021; Papini et al., 2021: ; Zhang et al., 2024a; 2026). Nguyen- Tang et al. (2023) provided gap-dependent guarantees for offline RL with linear function approximation.
Specifically, for model-free algorithms, Yang et al. (2021) demonstrated that the UCB-Hoeffding algorithm proposed in Jin et al. (2018) achieves gap-dependent regret bound of Ö(H* Amin.. This result was later improved by Xu et al. (2021), who introduced the Adaptive Multi-step Boot- strap (AMB) algorithm to achieve tighter bounds. Furthermore, Zheng et al. (2025b) provided gap- dependent analyses for algorithms with reference-advantage decomposition (Zhang et al., 2022: Li et al., 2021: Zheng et al., 2025a). More recently, Zhang et al. (2025a) and Zhang et al. (2025b) extended gap-dependent analysis to federated Q-learning settings.
There are also some other works focusing gap-dependent sample complexity bounds (Jonsson et al., 2020; Al Marjani& & Proutiere, 2020; Al Marjani et al., 2021: Tirinzoni et al., 2022; Wagen- maker al., 2022b; Wagenmaker & Jamieson, 2022; Wang et al., 2022: Tirinzoni et al., 2023).
Other Problem- -reeddemDependent Performance. In practice, RI. algorithms often outperform what their worst-case performance guarantees would suggest. This motivates recent line of works that in- vestigate optimal performance in various problem-dependent settings (Fruit et al., 2018; Jin et al., 2020; Talebi & Maillard, 2018; Wagenmaker et al., 2022a; Zhao et al., 2023; Zhou et al., 2023).
15

---

Published as a conference paper at ICLR 2026
B EXPERIMENTAL RESULTS
This section provides the four numerical plots for four experiment scales with (H, A, K) = (2,3, 3, 109), (5, 5, (7, 6, x 10%), and (10, 15, 10, x 10²) in Section 5. The al- gorithms evaluated are AMB, represented by the blue curve; ULCB- L.eB--Hoef,ing, shown in purple; Refined AMB, depicted in green; and UCB-Hoeffding, indicated by the red curve.
10000
15000
Regrot771 logh
Regreamh
3000
Tatal number of epiindes
Total number episodes
(a) Regret for (H, S, = (2, 3,
(b) Regret for (H, (5, 5,,5,33
LBCB Retined AMB UCB-ricuftling
ULCIB-Itewehiingg Paditadd AMB
UC25-Hoe lding
HegnorT logit 11
150000
122
10000
Total number of episades
Total numbee apanniss
(c) Regret for (H, A) = 17,800 6)
(d) Regret for (H, A) (10, 15, 10)
Figure 1: Regret Comparison of Different Algorithms.
Each plot displays the comparative performance of four distinct algorithms. In each plot, we col- lect 10 sample trajectories per algorithm under the same MDP instance and plot the results of Regret(T')/ log( + 1) versus the number of episodes K. Solid lines represent the median regret, while shaded regions show the range between the 10th and 90th percentiles.
C COMPARISON WITH MODEL-BASED WORKS
C.1 REGRET UPPER BOUND COMPARISON
We first compare our ane-grained gap-dependent regret upper bound with those obtained in model- based works. Among them, the state-of-the-as result Chen al. (2025) establishes the following regret upper bound:
H Σ
2
H Zoptl
Σ
+
+ SAH" max(S, H]
(p(s,a)
Amin
An(s,0)>0
where Ô hides variance-dependent and logarithmic factors.
Compared with our results in Equation (3) for UCB-Hoeffding and ULCB-Hoeffiee in Equation (11) for Refined AMB, this result achieves an improved H H-dependence in the gap- dependent terms, while maintaining comparable H-dependence in the last term. However, the final
well as
16

---

Published as a conference paper at ICLR 2026
term scales SAH* m H. which introduces additional S dependence when S > H. Such a quadratic dependence on the state space dimensions can be prohibitive in large-scale MDPs.
This improved H-dependence stems from the strong performance of the model-based algorithm MVP (Zhang et al., 2024b). MVP achieves sharper regret guarantees by incorporating variance- based bonuses and explicitly estimating the transition kernel, thereby enabling more accurate value function estimation. However, as is typical for model-based methods, maintaining transition-kemt estimates incurs memory of order 0 Af)), which is larger than the O(SAH) memory requirement of model-free methods.
Our fine-grained analytical framework developed in Section 3.2 can potentially further improve the regret upper bound when applied to more advanced model-free
H H-dependence in the RL algorithms, such as UCB-Bernstein (Jin al., 2018), UCB-Advantage (Zhang et al., 2020), and Q MarlySettled-Advanee
(Li et al., 2021).
C.2 TECHNICAL COMPARISON
All model-based works (Simchowitz Jamieson, 2019; Dann et al., 2021; Chen et al., 2025) estab- lish fine-grained gap-dependent regret upper bounds whose forms are similar to that in Equation (1). However, their analytical techniques cannot be directly applied to the model-free setting, particu- larly to the UCB-Hoefftie algorithm. To clarify this distinction, we next describe the common analytical approach underlying these model- works.
All three works begin by using the following relationship to upper bound the expected regret:
K
H
B(Regret(()) S E
Σ
(
Eh
where
(s, = (s, (rn a) + Be (1
(12)
denotes the surplus at (s, h, k) Sx A [H] [K]. The surplus is then bounded in terms of the suboptimality gap (s a) to derive fine-grained regret bound.
For all these model-based works, the Q-estimates updated as (s a) = (s, a) + E B (V (5') (s,,
where jol: s, a) is the empirical estimate of the transition kernel Px(- s, s,a) at the beginning of episode k. Substituting this update into Equation (12) gives
as, by (s, a) Ey (s') (V (+))))
The two conditional expectation terms share the same input VA and IP) ( 8, a) is unbiased estimator of the transition kernel PA (- 8, a). Therefore, their difference can be controlled using standard concentration inequalities and empirical process techniques.
The situation is fundamentally different for model-free methods, which do not maintain an empirical estimate the transition kernel. particular, for UCB-Hoeffding, the Q-estimates are updated as
N (st
Nttol, (eh (shtt) (Ntts))
a)(s,a)=
Th
h+l
where Sn denotes the cumulative bonus for all n N4 defined in Lemma E, later. Accordingly,
(s, = (1
Σ
Ny. T
(V (Vi (5 (E (V
key distinction is that the two terms inside the difference now involve different value function estimates: the empirical term uses historical estimates V whereas the conditional expectation term uses the current estimate V h4-1- This temporal mismatch introduces additional bias, which prevents the analytical framework developed for model-base based methods from being directly extended to the model-free setting.
17

---

Published as a conference paper at ICLR 2026
D GENERAL LEMMAS
Lemma D.1. Srruma-Hoeffding Inequality). Suppose { {
100 is a martingale and 3XXx-
Ck. Vk 14, almost surely. Then for any N 44 and 0, it holds that:
2
P (IXNN Xol 2 E) S 2exp
2 2
R= ck
Based on the definition of mh it can be easily verified that Σ following properties proved in Lemma 1 of Li et al. (2021).
The -
1[N > 0j. We also have the
Lemma D.2. For any integer N > O, the following properties hold: (a) For any N4,
nn
S 1 +
H
Nmn
(b) For any N E N4,
2H
Σ
N v
Tn
N
(c) For any t E N4 and a E (0,
jac
The following lemma summarizes basic but useful properties of the defined weights. When (s, o, h) is clear from context, we also write k² :s h) and N == N a) for simplicity.
Lemma D.3. For any given non-negative weight sequence [kEKk at step h, the following rela- tionships hold for any k' E [K] and h S h < H:
(a) Σsa (n(K, N1 1, 1, wp (n h' + 1).
(b) [wan,, s, 22 (wnl:,h')ll
(c) [wn(; M. a)ll $ (, (- h²') 1lo0 No +1 (s)
(d) [wn (on(://))) //]l = Ee.o (- h1, s, a)lll
(e) (wnn:,N h/ + 1)1lo0 - (1 + + [/wn(,, h') (wnls, h' + 1)]l2 S (- (1)l..
Proof. (a) because
Σ nu (K'' 1'' + 1,8,a) WankK' + (I),,, = =8s,a) = wn (k', + 1).
(b) is because for any k E [[]
w/. (W,,,, 0) (k'K', M²) I ak) (s s wn (K', n') s (wn(,,h0lla.
(c) is because
K
(M, 8, S
Σ
NK (sh akt) = (s. = 1/ (.))), N, a)
(d) is because
K Σ
K
Σ ( Σ
wp (k', hh'''' h''-11[<' ab) (s, a)l Σ
wp (n'k', (W','') h²) h.)h..))l..
18

---

Published as a conference paper at ICLR 2026
For (e), we first prove that
No (aff maaa )-1
wa(k', N' + 1)
wh(k (ohr, ab h1), 10 (0
i= N (t)
(ofreie))))))
Ny. (otoooooh [K (skesshh h() k1.
Σ wn(k; h')
E
(13)
This is because according to the definition of k. I ( ak h() k] if and only if (sW.0k)) = (0/2, at))) k s k - and = NoW (5% ab) and then we have:
K
wh (k) Σ
Nh (oeteaaa)))) ab0)) (sfe: h²) = k']
Σ
wh (ke W/
T (stk (5 a
k=
= E
wn (lett+(sst oft h'), h'mm mar (att (at)
N (gg)
The last equation is because for (s ) and (s (kt) (s ab,, h²). Moreover, due to the indicator [[sh aft = (sh af.) the summation in the second equation above only includes episodes in which (s aht is visited. Therefore, it terminates at the episode of the last visit to (s xx with vithi= N (sh al 1. Then for any k' [K],
(sh af.), we have k
N 1
1 -
wn. wn'(', h²' 1) S [ loo
This proves the first conclusion. The second conclusion is proved by Equation (13) and
K
N
wh (K', 1/' + +1) = Σ wh (ki 16)
Σ 11
No.
wa (k, =
Lemma D.4. For any non-negative weight sequence (wh) at step h E [H], any subsequent step h E [h, H), any state-action pair (s, E S x A, and any o E (0, 1), it holds that:
K
(k h' s,a)
Σ
<
| (., l1 ( h', s.al,
No. (s a )a
a
N
and
wn,kkh)
1
<
(SAllwn ) 1
No ( at))
1
K=
Proof. We first note that
wh s,
wn(k, of.) (s)a)
( a yar
NE. (s )
R= 1,
(o.0)
wh (x (s,,,,,,,
(14)
j
19

---

Published as a conference paper at ICLR 2026
Then we have
(s.a) wh wi (s, (,,,,, s (wnn (,, M' a)]l
Σ
Given the term on RHS of Equation (14), when the weights wn (A* (s, a, h²); h²) concentrate on the former terms with smaller index i 1, we can obtain the largest value. Let
[ (. s,, a)ll1 1w (:, 1l)l
and de,a, I|a (:s h', a)]l (Ca.o, D)llwa(( (-11
Ca.a,h!
Then we have;
K
wn (n(k N .s.a)
No. (oh )
A=1.N >0
(unn 1/ (1) du,ati'
ja S,0,/
11-a (i - (1-1)2-a
dea.
S (wun(:)'ll
(15)
1-a a
1ml
1) 1-a
daam
1-a
ca a,
[(e,a,, 1)]lwn(,, (,,,11'))) |-a 1-a
deam
1-a a
(C [whh h²) loo)
[Cs.a,,t ()llwn(;hh')l 1-0
dg,ak
(16)
1 a
1w (1 hi, ,,
Here the last inequality is because Ce alll/p( (lun(:h')ll) 1loo 2 (, 1/, 8,, s,a Equation (15) is be- cause for any 0 < y < x and (0, 1), we have:
x
1
(x1-a-
- - y2
xa
Then, let = and y = 1, holds that:
- 1 - 111-a (i - -d)=a)
in
Also let x = [| N1, 8, a)ll
and = (Cs,a,N - 1))l 11'))ooo we have:
dua.
[(Cr,a,h' ()]lun(( (. 1-a ||w (s, M, a) 1
[Wn(- h1, s, l)l
1 a
1 a
Applying this incquality to Equation (16), we have:
wh(k, ( (H).) as) 1
|nn [nn 111 [wn(,,'' saa)li)
(sh )a
K=1,N5
Therefore, we have proved the first conclusion. By summing this conclusion for all state-action pairs (s,a), we reach:
K
(k)
|w [.
N
( og )ai
k=
5.a
The last incquality is by Hölder's inequality, as
Σ ||w (., 1/, a))aa
20

---

Published as a conference paper at ICLR 2026
E PROOF OF THEOREM 3.1
E. PROOF OF LEMMAS IN SECTION 3.2
Before proceeding the proof, will provide several key lemmas. By Lemma 4.3 of Jin et al. (2018), we have the following conclusion.
Lemma E.1. Using (ss, a, h,,k).))))) k) as the simplified notation for V(s, a, 8 A [M] [K]. With probability at least p, and Bo and B.
8V 11 for E N_, the following event holds: No (V h+1 Vitz))( - Bxg. V(s, a,,,
N
0 S (Qh - (s) S %o
H +
==1
We now proceed to prove the lemmas used in Section 3.2. We begin with the proof of Lemma 3.1. In fact, this result holds for any learning algorithm.
Lemma E.2 (Formal statement of Lemma 3.1). For any learning algorithm with K episodes and T = HK steps, the expected regret is bounded as
H ΣΣ An(s,
(6.0).
E (T)
SE
Famm 8.0
Proof.
(vt - -11' (st) = Vi'(s}) (i + (Qi Q7") (s at)
A1(s,, at) + E [V3 V22) (5/) $ ~ Pi ss st,
E (0 10t,,, at) + A2 at))
2/ Pi(: at)
+ E [ Q3
(5/ ab)
5/ Pi at)
H
E
An
(3 att))
shht1 ~ Ph s at),
[H
Here, the second equation is from the Bellman Equation and the Bellman Optimality Equation in Equation (2). Therefore, we can get another expression of expected regret:
K
K
H
(Regret(TT) = Vi+ - V/""
(st)
= E
An (s att
h=1
Note that
(eggret(T))
Σ> Σ
A (s att
\= k=1
"
K
EE
An ()llss) = (s, a))
k=1
3,a
Σ
Nx(s.
5,a
We finish the proof of the lemma.
We then prove Lemma 3.2 by bounding the cumulative weighted estimation error
K
w (Qh -Qi) (s aft
for each state-action pair (s, a).
21

---

Published as a conference paper at ICLR 2026
Lemma E.3 (Formal statement of Lemma 3.2). For UCB- HCB-Hoofffding. under event & in Lemma E.I, for any non negaatieee weight sequence (wf hs at step h, it holds simultaneously for any (s,a) E Sxx and subsequent step h' E [h, H| that:
K wh (k, N, 8, (Q Qi.) ab) S
K
Σ
Wn , + 11, a, Qi,+1)
k'=1
+ ||wb 1ooo + 16 11 || h2) s, (17)
and
K
wi (k, h') (Qh Q7,) (5k,ak)) v
Σ
(k', h1 1)( +
+ +Iwm(;,')llas
16
Σ
Ha wh (:, h
(18)
Proof.
Under the event & in Lemma E.1, we have the following relationship
K
K
Σ
wh (nik, 11, 8, a) (O+
Qic) (s ae)) S
wh
(k, 11,
a) No H
k=1
k=1
N
wh (k, a)
(V N+1
(
Σ wn (k',,'
(19)
Here k² = (s a N/). For the first term in Equation (19), we have
K
(k, 8,,,8, No. H < (: (>) H I [s ax
k=1
k=1
< (170l1,))ll
(20)
The last inequality is because (, h², ax [k Io) by (b) of Lemma D.3.
For the second term in Equation (19), have
K
No.
Wh (k, R1, 8,0 a
Σ
1/
No.
(V
V/ (=++4)
km
1=1
K
wn (k:, h1 NT)TI [(ffe, = ai] Σ
Nu
(V - (
Σ
TiK = K1
t
k=1
T=1
[k'=1
N
Σ
Σ
wnlk, (ik,h') h()I [(shr aft:)))))) = (s,aa] 114 No. IIR= = k')
==1
K
K
<
(Q% (6
wn (k, 1 1')m) No. [Kt k", (shr, atte - (s, a)] e01)
M=1
Σ Wn hh' + 1,,, - Qi +2
(21)
The inequality is by O% (5% ab-1) 2 ( Qiv
(s (1 & (1
For Equation (21), by the definition of kt, T [K' (st: at hi") k'] holds only when (s a/)
22

---

Published as a conference paper at ICLR 2026
(sh, a and then we have:
K N
ΣΣ
wh (hikk 12 h') No. I II = k,, (5h,, a = (s,
A=1 1=1
K N =1 [ (/. as)
(k,kk H2') N') No [[K =k] = , h¹ + 1,,
wr
k=
The last equation is because of Equation (13) and the definition of (n''', H'' + 1, 1,8 For the last term of Equation (19), by Lemma D.4, it holds that
K
8,,,,, S H
Σ
wa (k, 5,
1 N ( att))
20
16 H3 Wh (,, ww) 8,a)]1e.
(22)
Combining the results of Equation (20), Equation (21) and Equation (22), we finish the proof of Equation (17). Summing this conclusion over all state-action pairs (s, a), and noting that
Σ s,a W, N + 1, = (,, N' 1), we prove Equation (18).
Lemma 3.3 then follows immediately from recursive application of the results established above.
Lemma E.4 (Formal statement of Lemma 3.3). For JCB-Hooffdingg under event in Lemma E.I, for any neg-tega weight sequence {w } step h, it holds simultaneously for any (s,a) E SxA and subsequent step E [h, H] that:
Σ wh (k, h²) (o Q7-) (sh..
H (en(shi))losAAH 16
EVHI bo
Σ
WVHllwn (-2))llellnn h1, a).
Proof. By applying recursion steps h² h' 1,..., H in Equation (18), since (s, Qu+11(s (s, a) = 0 for any (s, k, k) E S x Ax [K], the proof is complete.
Building on the previous lemma, we now establish novel upper bound on cumulative weighted visitation counts
N4,(s,)) (s.
8,0
which then enables the final bound expected regret through Lemma E.2.
Lemma E.5 (Formal statement of Lemma 3.4). For UCB- Hoeffding algorithm and C₁ 20736, under the event & in Lemma E.I, holds simultaneously for any h [H] that:
(s (Ns,,)NKk*1 kl ()
"
Hº
H3
(EH Ei=Nt1 v /Zop,t
< SAH +
Σ
Σ
+
C1
(s
Amin,h
9,0
:=
H²
EH v /Zoppee
Σ
Amio,
M=++1
Proof. We use mathematical induction to prove this conclusion. For step h, let
& = 1 [Q) att - (s ah) 2 (n af)) (s/i at) E Zaub.h)
wh
= 1 [st att)) Zsbb.n) < 1.
23

---

Published as a conference paper at ICLR 2026
The second equation is because for any given (h E [H] x [k], if (sh o%) Zuub, have (s a Q a 2 V Qh a 2 Vi (sh, a.)) = An a >
The first inequality holds because Q (s a 2 (s)), as guaranteed by the update rule in line of Algorithm 1. The second inequality follows directly from the & in Lemma E.1, which ensures that (8% a) 2 Qh (sh a) for all (a, k,, A [ [K] and thus
V/ (s min [H. Qh (5 o)} 2 min {I, max max (T a)} max Q% a) (sh)
Based on the definition of w for any (8, a) E Zub,h. we have
||w (. s, = -i((sh at) (8, = N
k=1
and (1 h, s, a)]l 0 for (s, Zopth- By Lemma E.3, for any (s,a) E Zuub it holds that,
Qi) (sh a (( att = (s. Σ (,, 8, (Qt Q7) (sh, at) Σ Wh (Qhh
K
S H + 16 KINK++G (s,a)e+ (s)
Σ
an (W' h 1, a) -1t1) (23)
Also note that for any as,a)= E Zuu we have
Σ k (Qh Qi) (sh, T (s, An Σ w ATT ag) (s)
= a) (kttss)) (s,
(24)
Combining the results of Equation (23) and Equation (24), holds for any (s, a) E Zuih, that, a+ (s,a) An(s, N)N
K
s H + 16 H3NK ++ (8, a)l+
Σ
Wn (K,
1, a, 1 - ohtz)
#=11
Solving this inequality, we can derive the following conclusion for any (s, a) E Zsub,h:
256H3, an
a Kr (s,a)
2H +
in h 1, a) (5
Since As(s, = 0 for (s, & Zsub,h and 1h+1 (s, 2 17+1 (s, a) for any (s, a k) E SxAx [H] x [K], by summing the inequality above over all actton pairs (s, a) Zub we reach:
Σ N
25
K h W - 1 (25)
<
+ 2SAH + 2
Σ k=
as
As(x,))0
Here we use
Wn h (,,,,)
by (a) of Lemma D.3.
Let h H, since Q (s. Q4411 (s) for any (s. E S S A x lemma for = H with Equation (25). Assuming the conclusion holds for steps h + 1,..., H, we now prove it for step h.
[K], prove the
24

---

Published as a conference paper at ICLR 2026
By Lemma E.4, have
K
wh (K', h 1) - a
H
H
Σ
SAH + 16
Σ
Σ
A s,a)ll
(26)
#'=h+1
h/=h++1
with
K'-h
1
(wn(-,/'>llo -
110((,))loo 33
(27)
H
and
(ub(;))ll < (,,((;1)]1== Σ [ h, a,
Σ N (s.
(28)
(a(a,))0
by part (e) of Lemma D.3. In this case, by Equation (27) and part (c) of Lemma D.3, we further obtain the following bound:
[ N², a)llı [| bo (s,
(s. a) S 3N,**(sss
(29)
Furthermore, by Equation (27), for the first term Equation (26), we have:
H
Σ
( S 3SAH²
M'=+11
For the second term in Equation (26), we divide the state-action pairs (s, a) at each step h' into two categories: Zopthr, where (s,
and Zuab,h', where (wr(s, a) We apply the Cauchy-Schwarz inequality to all sub-optimal state-action pairs jointly across all steps, and to optimal state-action pairs individually at each step //.
H
16
Σ
3 (w (-, 1woh (wwp (,,',, 5,
M=++1
H Σ
H Σ
< 16V3
Ha,
Asr(s,))00 Aw(ssa)
Σ
Σ
alllan (,, M,,, a)llı
N'=h+1
h'=l++1 (n(r)))0
16v3
Σ
H3 Zopn,b
Σ
(un(;"''s,a))
h' h'=
(s,0)
S 48 H3,
Σ
Σ
Σ
Σ (n(()))
(n(
(s,
W==++11
Aw (
W=++1
16V3
Σ
H Zop,
Σ
N NK+1
(30)
W=++1
An(s,a)>0
The last inequality is because I|w ,,,,,, S <3N 33NK+1 (8, a) by Equation (29) and
[kn(', ,,, a, & (wwx-.n')ll < Σ N (s,
(8.0)EZ
An(s.a>0
where the first inequality follows from part (d) of Lemma D.3, and the second from Equation (28).
For the first term in Equation (30), by AM-GM inequality, we have:
48
H3,
Σ
Σ
(n)
Σ
Σ
k'=h+1
W=
Apr(s,a)20
H
24vei
Σ
Σ
+44vo
Σ
Σ
(31)
(x
HCi
M=++1
(3.03)0
k=
Anr(s,)30
25

---

Published as a conference paper at ICLR 2026
By the induction hypothesis, the lemma holds for all steps h + N' H. Therefore, obtain:
Ar (s. N N (s.
H
< SSAH2
+
Σ Σ
(s
C1
8,0
imh
(s,0))2
H El=w41 Zoptiel
Eiziti v Zope.e)
Σ
+
min,h
minn
1=h++1
By summing this inequality for + 1 15 S H, holds that:
a +1 (s,a)
H
H
H
Σ
SAH +
Σ Σ Σ
Her
A1(s,))
M==++1 Aw (3,0)20
k'=h+1
W-=h+ 1i Aj(e,0)20
H
H²
EE V Zopt.t)
H1
H
E Ei=it1 v Zoppte
Σ
Σ
Amin,h
Amin,i
M=++1
W= t=
Σ H
H
H
Lt=h+1
ViZopzel
SAH
Σ
+2
Σ
(s, (s,a)))
Amin,h
W=++1
M=++1
Applying the above inequality Equation (31) and substituting it into Equation (30), obtain:
H
16
Σ Σ
W M=h+1
8.8
112 (Ett v /Zoprel
H4. +2 Σ (s,
H
$ 244/a
SAH +2
Σ
Σ
A min,h'
I M=h+1 Aur (x,))20
M=++1
16v3
Σ
H Zopphh
Σ
N N (s.a).
(32)
W=+++1
An(s,a)00
By applying this inequality to Equation (26) and substituting the result into Equation (25), and using the bound (. from Equation (27), conclude that the following inequality holds:
a) ( as)
5,0
2
H4,
H
H² (EH /Zopree)
< /
SAH? +
Σ
Σ
Σ
(s,
A Amin,k'
It' h An (+.a)>0
ht h1
+ +3233
Σ
H3 Zopuarle
Σ
N (s)
(33)
h
W==h+1
An(s,a)2o
Note that if Lsub.al 0, which means Amin, O, we have
Σ AN K+1 (s,a)) = Σ A (s, > Amin.h
Σ
8,0
(a(aa)20
Ax(s,0)20
Define
b b= Amin,hy == 32v3
Σ
V H3
13 Zap
Σ
NK+1 (s.
N
W=++1
An(s,a)>0
and let the first term the right-hand side of Equation (33) be denoted by d. Then Equation (33) can be rewritten as:
bx
d < 0.
26

---

Published as a conference paper at ICLR 2026
When b O, solving the inequality yields:
++ VC² + 4bd
26
Applying this upper bound to Equation (33). by AM-GM inequality, we obtain
Σ (n(s,)) (s. scr
c² + cv + 4bd
+ d
3c²
+
3d
2b
2b
2
8,8
Ei= v ViZppeel
H4
144Va
SAH?
Σ E
Σ
(s
A min,h
W/ A))))))>0
M=++1
1
4608
Amin.
/uub, O. then Amin, do and Σ.,. (s, N N a) 0. this case, the conclusion holds trivially. Therefore, the result is established for step h, completing the proof.
E.2 BOUNDING THE EXPECTED REGRET
Now we bound the gap-dependent expected regret. Letp = 7. then & holds with probability at least 1 and S ((log(SATT), Therefore, by Lemma E.2, we have
B(Regret(T)) E
An () (s..a)
1=1
H
H Σ
=
E
An(s, (
P(E)+ +E
Σ
a P(ET)
1=1
8.8
==1 8,0
13 (E
[apeetl log(SAT)
H log((AAT
0
Σ
Σ
Σ
SAH
(s
Amin,h
(n(s)))0
h=1
0
Σ
Σ
"1
H 1 (SATT)AT)
1º1 Zope log(SAA)
+ SAH
(s
Amin
A=1 (s,
The first inequality is because under the event by Lemma E.5, have
Σ a) (s,
H H
H4,
H H3
(E V (oor,e
<
3V SAH
Σ
Σ
(w(s,a)
Amia.h
h=1
hm W mh
Agt (8
h=
H
H
H²
H E Zap,,t
Amin,k
h=1 M=
2
H
Em v Zopit log(S
HS (og(SAT)
00
Σ
Σ
+ SAH3
an
Amin,h
(x,)00
h=1
by Lemma E.5 and under the event 8
HT.
A=1
The last inequality uses Cauchy-Schwarz inequality and Amin, 2 Amin for any h [H).
27

---

Published as a conference paper at ICLR 2026
F PROOF OF REGRET UPPER BOUNDS FOR ULCB-HOEFFDING
F.1 AUXILIARY LEMMAS
We first validate the upper bounds Q and lower bounds Q introduced in Algorithm For simplicity,
we denote a = -ep_irPPtt (-Is.a)) (sh++) 1)(8% 8, as = a) and I,/ - f(s) for any (s, a, h)
[H] and function f S + IR. We first prove some probability events facilitate our proof. Lemma E.1. For ULCB- -oee--oo algorithm (Algorithm 2), we have the following conclusions:
(a) With probability at least 1 the following event holds:
N No
Gi
Σ
Th
(L
Poaa)) Vitt1 22
(s,a) ((s,a,
H
(b) With probability at least 1 the following event holds:
1
(Petiahh Tohiss) (Vi+z - Vitts) $ 27V2H222
G2
1
H
Proof. (a) The sequence
Σ
vh (I sits -Poan) Vittz
NEN+
a martingale sequence with
N
Σ
TH (1 (1 - -Paan) Vh+t
S n H.
Then according to Azuma-Hoeffding inequality and (b) of Lemma D.2, for any 8 E (0, 1), with probability at least 1 3x7 holds for given (s, = N E N4 that:
p
Σ
1h
N (1 oht
- -Paa.)) Vh+1
2
H N
For any all h,k,, E S A
H x [K], we have (s) E
[ Considering all the possible
combinations (s, a, h, N) Sx
H x I with probability at least p, it holds simultaneously
for all (s, a, h, k) E S x A x H
x
K that:
N
Σ
1
No
11 (I sh
- -Paaa)) Vitza
S $2
H (s)
1=1
(b) For G2, the sequence
(1+ H
)(+))(((
h-1 (Pog.ot, Lot..) (Vitts virtt -Vitt))
can be reordered to martingale sequence based on the "episode first, step second" rule. The ab- solute values of the sequence are bounded by 27 According to Azuma- Haema-Hoeffding inequality, for any E (0, 1), with probability at least - ō, it holds that:
1 1)
(P (P.t.ata Ioti.)) (Vitz -V7t) 27T
Am Kmm
28

---

Published as a conference paper at ICLR 2026
Lemma F.2. For all (s, a,a,at h.) x x x [H] [K]. when event 91 in Lemma F.I happens, the upper and lower confidence bounds in Algorithm 2 are valid:
Vx(s) 2 (a) 2 (s) and (x( 2 @%(s,a) 2 (s,
Proof. We use mathematical induction on k to prove this lemma. For k = 1, the lemma holds based on the initialization in line 2 of Algorithm 2. Assuming the conclusion holds for all 1, 2.... k 1, we will prove the conclusion for k + at episode k.
If (s, a) ES x Ax x [H] {(5 " then have
h (s) (s) Z Vi((s 2 vh(ss) V (s).
and
Qn
h+ (s.a) (x, a) > (x, 2 (s.a) (s,
For (sh abz h), based on the update rule in line 12 and line 13 in Algorithm 2, we have
N++1
k+1 Qn
(chiah)
= 110
N
H
+
Σ
1/
N
Trass ah) +
v ( + bi
1=1
N
N
ru(sh ah) + Vhe Viti(shhi)) 2 / Mº+1
H3,
1100
H +
11
N
(34)
No
2
a/i)
Σ
Nk+1
(ra(o,, Whin (5h+1)))1))) -ba).
7
i=1
N++1
1
Nk+1
(rn(o) VK ( 3/
N
113
(35)
i=1
These two inequalities are because
N+++1
N+++1
NEIL
H
H N
1/1
b. 2
2
i
1=1
by (c) of Lemma D.2. Furthermore, by the Bellman Optimality Equation, holds that:
Q (s a = (s a + P Ptg.at V
Combining with Equation (34) and Equation (35), derive the following conclusion:
(0% h+1 - -Qh) (sh.at)
N
No-1
(Tii
(Dati(shti)) - -P aa Vitt1
H3,
2
7
+ 1
N²+1
N
Nd+t
Σ
n Ny (Vh
Vitt) ( + Σ 1
Nk1l
(1
Lec at Vi+1 + 2
H
2 0.
N
The last inequality is because V (
2 Viui V (sht for k² S k and the event G1. Similarly.
(2gh - -2%) (sh.aa) aft
N
S
-
(v
Pat
aa a Vint.)
12
H3,
N
N/
N111 Σ
- (vht)
N++1
H3, N
1
(3
1
(I +/4
P
Vitta 2/
< 0.
1=1
29

---

Published as a conference paper at ICLR 2026
The last inequality is because 1 I Vitt (sh+t) for ke < and the event 91. Now we have proved that Qn ++1 (s,a) 2 (% 2 2
++ (s, a). Therefore, by noting that
V g
(8) min H, max Φ (s,a)} z
max aE
a) (s)
(=)
and
v (s) = max {0, max (e)
1 a)} S max =
prove the conclusion for k + and thus complete the proof.
Lemma F.3. When event 91 in Lemma F.1 happens, for any (h, k)) E [H] x [K]. we have that:
( (ok) S (sh, att - 2% (shi of)).
Proof. If (s)) = 1, based on the definition of (s)),, we have
((())) S
(x(, - Q aB)
max REAR (xt)
and
(sh. 20h
max aE (sl)
Therefore, prove the conclusion. If (4 (/ 1, define:
( a); à arg max O (sh a)
à arg max
aEAR (ot))
aEAR ((a))
Then we have
V (*()) s 1 a) (5h
(2) a) (* a))
- 22t
(sh, ah) (sh att)
The last inequality is because
a arg max a) (EA
- (5h,
a) < when [+*())) > 1 and 2*, ()
(5 ū) based on the definition of à.
Lemma E.4. When event On in Lemma F.I huppens, for any (h, k) E [H] x [K], we have that:
( - (5 a 2 An at)
2
Proof. If (s) 1. based on the definition of (1(s we have
V% (*h+)) V (+
Ch a) @h a
max EEΛ Seat-t(st (xtt
Combining the result with 2¹ (s < (s a by Lemma F.2, it holds that:
Th et (sh 2 VA ( at) (n ot).
Therefore, prove the conclusion. If A | 1, define:
à arg max ( a). ac A (
30

---

Published as a conference paper at ICLR 2026
Then the conclusion follows from the following analysis:
An(hiaafi
(oh) (hh af)
V ( (sh ah)
(36)
th a) - 2 ax))
(ox(s), a) (sh, a)) + 2g (sh
+ (2h ak))
(37)
(on ot) (sh af)):
Here, Equation (36) is because of V (s 2 (st)) and (s ot) S ( at) by event 91 of Lemma F.2. Equation (37) because
di ang max (sh, Qtt a) (E)
when (A))) > and 0 (s a) ( s @x at) since ot E (z
F.2 PROOF OF THEOREM 4.1
In this section, we bound the worst-case regret under the event 91 n G2 in Lemma F.I.
For h E [H + 1]. denote:
6 V h Vi (o7), ch = (V' V (o%)
Here, +1 S 0. Because ViT(s) supx V (s). have 0% S c% for any h E [H 1]. In
addition, as V 7 (s) 2 (s) for all (s, k) ESX [H] [K] by Lemma F.2, we have:
K
K
K
(Tg =
(++(s))) - Vi* (st) $ Σ (vi VT" (o))) Σ
k=1
k=1
k=
Thus, we only need to bound
Ex= st. Noting that
K
K
)
a
1=1
k=1
Q (s) at) + (Q% -7 (7))
K
K
=
Φ ( a +
Σ
a (Viti - Virti)
(38)
In the last inequality, we use the Bellman Equation (Equation (2)):
(5 rn(s,a) a) P.,,a Vott:
QR" (s, rx(8, a) + P Pa,a, Viti-
Next, we will bound ΣK (+) at). Using Bellman Optimality Equation, we know
Nx
N
Φh -5) a < no
No.
+
1
No
(
- -P Patt.at.M Vitt1) +
"
bi
i=1
1=1
N
N
H +
1
(
(h+2(6hi22) - -P -Pot h Vhita
+ +
H3₁
N
1=1
< 1
Nk
H
+
1
N
(vitz= -Vitz) (bhitz)) =6..
H3,
N
(39)
1=1
31

---

Published as a conference paper at ICLR 2026
The first inequality uses:
Ng 7
No
H
H
by
i
N
by Lemma D.2. The last inequality is by the event 91 in Lemma F.1. By summing Equation (39) over & E [K], we reach
Σ Φ k=1
(5)
K
Nu
R
H
Σ
K
Σ
No
(V h+1 - (x+1)
+
Σ
K
6
H
(40)
N
k=1
k=1.N
> 1=1
k=1,N
>0
For the first term of Equation (40), we have:
1o
H E
N
INN 0, (sh a (s, HSA
(41)
For the second term of Equation (40), by Lemma D.4, it holds that:
H I
12VH'STT
(42)
N
For the last term of Equation (40), similar proof of Equation (4.7) in Jin al. (2018), it holds that:
K
(VAtI A+1 ($ 1 +
h+1
(43)
A= 1=
Taking the above results Equation (41), Equation (42) and Equation (43) together with Equation (40), back Equation (38) reach
K
K
1
gk
b+1 + 12VH2SAT + HSA+
PP afthh (Viiza vitta
1=1
k=1
+
+
H
(Pot.atih 1 1ster) ) (Vita Viitt)
H
By recursion on h, since + = O, we can get the following conclusion:
K
Regret(T) <
A
k=1
K
h-1
50
v HHSSTT + HASA +
1 H
(P (Pot.ogin
1 1et
(Viz Viti))
h=1 k=1
0 VHHSAAT++ SSSATT+H'SAA..
The last inequality is because of the event G2 in Lemma F.I. We note that when T>> SA*S have VH&SAT, 2 H²SA and when T < AH'SAT,, we have K 8% HK T s / SAT Therefore, we can remove the S term in the regret upper bound.
To summarize, with probability at least 2p, we have Regret(T) $ O(VHASATI) Rescaling p/2 finishes the proof.
32

---

Published as a conference paper at ICLR 2026
F.3 PROOF OF THEOREM 4.2
In this section, we derive the fine-grained gap-dependent regret bound for ULCB-Hoeffding follow- ing similar line of reasoning as in UCB-Hoeffding Let p 7. then the event 91 holds with probability least 1 T and S ((log(SAT)) Therefore, by Lemma E.2, we have
((Regret( ())
H
=E E
Σ 1==1 8,0
Σ
H P(G1)+ +E Σ
(
a) (s. A P(gf)
E
8,0
Veml 8,0
2
<
Σ
H
Σ
H (SAT) (s
+
H. H3 (Ei v Zapall
log(SAT)
+ SAH
Amin,
A=
Anls.))0
1=1
The last inequality is because under the event 91, by Lemma F.7, we have
H
O)
(s,aa
1=1
8,a
H H3
EE=t4 v Zopp,t]
(Sg(SAT)
H log(SAT)
00
Σ Σ
SSAH3
An(s,a)
Amin,h
1=11 As(s0)s0
h=1
and under the event gi.
H
ΣΣ 1=11 8.0
At HT.
Now we only need to prove Lemma F.7. Using the same fine tne-grained analytical framework, we first bound the cumulative weighted estimation error for each state-action pair (s, a) at step h.
Lemma F.5. For ULCB-I ULCB-Hloeffding algorithm (Algorithm 2), under the event 91 in Lemma F.I, for any non-negative weight sequence fwo l at step h, it holds simultaneously for any (s,a) E E x A and subsequent step h' E [h, H) that:
K
K
whik s, (Th-- - -2x) (5% aH S
Σ (n + +1, 1, a. ( - -2 (s,
k=1
#=1
1|wn 11') 11)1 16 11
11 wh (s h²) || 10 ww 81,
(44)
and
K
Σ k=1
wh (1) (oh. -2xx (kh)
ahr) S
Σ
wh (K' h' + 1) (D 2h ak
==1
+ +1
16
v HH ht') Wwn (. h², all
(45)
Proof. Under the event 91 Lemma F.1, by Equation (34) and Equation (35), we have
n+
(s a =
Not H
+
Ny.
(s axr) ) + Vil W- (s + bi
N
N <
11o
H +
(s (f))) + 1 + +4V
N
HJ,
(46)
1=1
33

---

Published as a conference paper at ICLR 2026
and
No.
(oh
Σ i=1
No
(rw(s + r 2 -bs) 61)
71
N
NW
(ra +6+ -4V
1
(47)
N
2m1
These two inequalities are because
2
No.
H
H
b = _
7/
N
by (c) of Lemma D.2. Therefore, by taking the difference between Equation (46) and Equation (47), reach
K
K
Σ
wa On (K, s,a)
-
(s
w/ (ki N², a) No
Ny a)
+
wh (k, h', Σ
No
(vii
W++1
v v((t1) (ohtt1) +
Σ
wn wn s, S,N) (48)
i=1
k=
Same as Equation (20) and Equation (22), we have
K wh
(k, 8,a) No H s [wals,
1=
and
Σ
wn N 8, 16
161163111 H3 (s. (1)) (ean N², a)
For the second term in Equation (48), similar Equation (21), we have
No
Wh (k, h1, s,a)
Σ
No.
(v
whit1
(shitt))
1k
K
No.
K
wh (k, 11') ( = (s,aa]
aht)
Σ
Not
V - Vbi+1 (sh/+1)
Σ TiK k1)
1=1
A1==1
N
vH(t1) (stria))
ΣV
Σ
w/ (k; h R [(t (s, a]] 173
"T= k-1
N41
i=1
K
No.
@ - Qt 2
ΣΣ
wh (k, h h!'m No. [M. k,, (sh a (s,
<
#=1
k=11=1
K
Wnnk'' + 1, a) () - 25%
=
The inequality follows from Lemma F.3. Combining the upper bounds each term in Equa- tion (48), we finish the proof of Equation (44). Summing this conclusion over all state-action pairs
(s, a). and noting that EnaWn(4 H' 1, a) = wn.k (k' h + 1), we prove Equation (45).
Building on the lemma above, we can establish the following result. The proof follows the same argument in Lemma E.4.
34

---

Published as a conference paper at ICLR 2026
Lemma F.6. For ULCB- LLCB--Hoffdding algoritim (Algorithm 2), under the event 91 in Lemma F.I, for any non nog-nega weight sequence [wf]s ls at step h, it holds simultaneously for any (s,a) E A and subsequent step h' E [h, H| that:
K
whikk h²) ( -2x) (sh:agh) Σ
H1
1o SAH + 16 h==
Σ h1=h/
Σ
H wn h1) bo)lloollal hi, a)
The following lemma bounds the summation E. (n (a(s,a)Ni N) (s, a), which directly contributes to bounding the expected regret via Lemma E.2. The proof largely mirrors that of Lemma E.5, with only minor differences; we therefore focus on the distinctions and omit the unchanged parts. Lemma F.7. For ULCB ULCB-Hoefie Hoeffding algorithm (Algorithm 2), under the event 91 in Lemma E.I. holds for any h E [H] and C2 82944 that:
(s N MNNK+1
H Σ
Ha (s,
H3 (Ei=nt1 v Zopr,
< SAH2
+
+
C2
mminh
8,0
W (s,a))>
H
H2
Σ/
Zopt.
2
+
Amin,h
W=h+1
Proof. We use mathematical induction prove this conclusion. For step h. let
w Qh at) (sh An(s att) (sh att E Zaabh
=I [ a E subb, S.
The second equation is by Lemma F.4. Based the definition of wh for any (8, a) Z
K [1 ho, s, a)ll = [ a = =s, = (
and (w (,,,, h, 8, a)ll 0 for (s, Zupth-- By Lemma F.,, for any (8, Z it holds that,
K
Σ wh @ 2%) (sh of [( ab) (s, = = E (ni h, a, (Øth 0%) (sh att
< H + 16 H3NK+ (s, (s, a) Σ
Wn (K' 1, a) ( 2itzs) (hhti,,btt)) (49)
k==1
Also note that for any (s, a) E Zaub,h with An a) > O, we have
Σ w
-2) (5% a [[( att (s,
k=1
(8,
a)
K
( att = (s, ] = An(s, NN
(50)
Combining the results of Equation (49) and Equation (50). it holds for any (3, a) E Zaub.h that,
(n a).. ( (s.a)
2
K
Hl + 16 H3NK (8, Σ
wi (K', h 1, 1, ( ohtz)
#=1
35

---

Published as a conference paper at ICLR 2026
Solving this inequality, derive the following conclusion for any (s, a) Zuub,ii
An N 1024H
K
W h 1, 1,,, Qt (/+11)
an(s,a) + +4H
+
4
===1
Since An(s, a) 0 for a) & Zuu and 2 (s, 2 2* (5,0) for any (s, a, h k) E S Ax
[ x [K], by summing the inequality above over all state-action pairs (s, a) Zuu,, reach:
Σ (s, (N
1
Σ
An(8,a) 4SAH 4
Σ W=1
wa(k' h +
M (+11)
(51)
Let = H. Since Q (s. a) = Qi++1 (s, a) = for all (s, a, k) E S x x [K]. the base case h H follows immediately from Equation (51).
Now, assume the lemma holds for steps h + l...., H. Using the same inductive argument as in Lemma E.5, we prove the case for step h. From Lemma F.6, have:
k
Wh h 1)(2 - (shta,
[w)(,,'')|l + 16 W==+1
Σ
Σ
ΣV
(,
( (52)
M W=++1
Similar to the proof of Equation (32), we can derive that
16
Σ
Σ
11 (n(, (t)
s,
W=h+1
"1
H+
"
H² Ei=h++ v Zoppeel
H
< 02
SAH +2
Σ
Σ
+2
Σ
(s
Amin, (8,a)
W=h+11
(
W=
H
+663
H3 Zo
Σ
NK+1
N (s,
W=++1
An(s,))0
By applying this inequality to Equation (52) and substituting the result into Equation (51), and using the bound (= I 3 from Equation (27), we conclude that the following inequality holds:
Σ NK K+
(s) (s,
114
H
ΣH
Ei=144 v Zoppell
19
SAH?
Σ
Σ
Σ
Am)(sa)
Amin,h (8, a)
M= Ag (s.a)200
W=h+1
H
+ 64v3
Σ
Zop
Σ
NK+ N
M=h+1
An(s.a)>0
By applying the same method used to solve Equation (33), similarly establish that
H Ei=+1 Zuppee
Σ Ak (s, S 18432
A Aminhh
s,a
H Σ Σ
H4,
H
122 Eit v Zopt.e)
288
SAH
Σ
(s,
Amin,h
M=h (s,))20
M==+1
This establishes the result for step h, thereby completing the proof.
36

---

Published as a conference paper at ICLR 2026
G PROOF OF FINE-GRAINED GAP-DEPENDENT REGRET BOUND FOR AMB
G.1 REVIEW OF AMB ALGORITIMM
We first review the AMB algorithm (Xu et al., 2021) in Algorithm 3.
Algorithm 3 Adaptive Multi-step Bootstrap (AMB)
I: Input: p E (0, (failure probability), H, A, S,K 2
2: Initializatinn: For any a(s,a, E S x A x [M]. initialize (2(sa) +- H, (3. t 0.
G 0. 4) A and V/(() = (s) 0.
3: for k= 1,2. 1.2...... K do
4:
Step 1: Collect data:
5: Rollout from a random initial state of ~ using policy mh = defined as:
Th (s) A arg max (+) (s, - (s,
if (s)) > if ( =1
the element in (*),
6:
and obtain an episode {(s). . rn (sh, ((,)))))
7:
Step 2: Update Q-function:
8:
for h H, H - ,,..., do
9:
if si & G% then
10:
Let n =N (s. a) be the number of visits to (s, a) at step h in the first &s episodes.
11:
Let h' = hi'k, h) be the first index after step / in episode k such that sy & G (If
such a state does not exist, set h' H + and V V = ( (s)= 0.)
Compute 8/2 4 H3 log(25 p) and Q (s,a) = Ensien rt.
12:
On k+1 (0 a = min
H, (1-1 Q2, (s +n (5t + +V +V (s%
13:
14:
Q (s at) = max
(0, (1 mm Q* (sh at) (Qh k. (0t, at) + + (s%) -bb)))))) (br))
( (s = maxx
2n k+1 (s d').
15:
16:
v (s+) = max max
2.++1 (8 d').
17:
end
18:
end for
19:
for
(s, (s,ah)) h) E x Ax x [H] \ a()) < h H. $ G
[il= do
Qn x+1 (s. = (x, ()..))....1 ( = (s, V/ (s) = k) vh(ss).
20:
21:
end for
22:
Step 3: Eliminate the sub-optimal actions:
Vs E S. h E [I], set A (s) -{a
{a {aE A*)) (x 2 2
23:
24:
Set Gf {s S |4 1 (s)) = 1}.
25:
end for
AMB maintains upper and lower bounds T% a) and (s, a) for each action-sti triple (s, a, h) at the beginning of episode k. The policy x² is selected by maximizing the confidence interval length Q - Q. Based on these bounds, for each state s and step h, AMB constructs a set of candidate optimal actions, denoted by 4 (s). by eliminating any action whose upper bound is lower than the lower bound of some other action. If (s) = 1. the optimal action is identified, denoted by T (s), and s is referred to as a decided state; otherwise, s is called an undecided state. Let Gh = {s (AA(()) (s) = 1} denote the set of all decided states at step h in episode k.
Let Fr.A denote the filtration generated by the trajectory up to and including step h in episode k. In particular, Fi. contains the policy T and the realized state-action pair (sf, af)) AMB constructs upper and lower bounds of the Q-function by decomposing the Q-function into two parts: the re- wards accumulated within the decided states and those from the undecided states. Formally, starting
37

---

Published as a conference paper at ICLR 2026
from state sf, at step h and following the policy n², we observe the trajectory { +k))
Let h' = h (k: h)) > denote the first index such that sy & Gk-- Then, the optimal Q-value function Q (s, a) can be decomposed as:
R-1 Σ
E
( Fras (sh, at) (s, ())
and
Q (s. - E (sh) | (5h, aft) = (s, a)]
where 2% and 2x and represent the contributions from the decided and undecided parts, respec-
tively. To estimate Qh..d (sp, ap), AMB uses the sum of empirical rewards in episode k:
W-11
Q (x, a) = Σ m af).
E
To estimate (si an). AMB performs bootstrapping using the existing upper-bound V V-estimate (s())) The resulting update rules of the Q-estimates are:
Qh ++1 2 min H. (1 "/ Q (sh a + 1/m (2% (sh,aa) af) + V ( + 11) (53)
2 (sh ohh max 0. (1 mn 2 s,,, a + 17 @o) (sh a + Vh 6/²
(1
(54)
The learning rate = #+1 action pair (s at) step within the first episodes. By unrolling the recursion in h, obtain:
# where n N (sh, a represents the number of visits to state-
No
shi min
H. no
No H
M
No
(0%
at) + (s + +b) } (55)
}
N Σ
(h att 2 max O,
No 770
m Nà
(0h (0t at + (+ 8.) }.
(56)
To ensure the optimism of the Q-estimates Q and the pessimism of Q. Xu et al. (2021) adopt the equality forms Equation (55) and Equation (56) in their Equation (A.5). However, these equal- ities do not hold under the actual update rules in Equation (53) and Equation (54), due to the presence of truncations at H and O. In fact, only the inequalities in Equation (55) and Equation (56) can be rigorously derived from the updates. This creates fundamental inconsistency: to establish optimism and pessimism of Q-estimates, we require an upper bound on Q and a lower bound on Q. which the reverse of the inequalities implied by the truncated updates. Therefore, the trun- cations at H and 0 in the update rules Equation (53) and Equation (54) in the AMB algorithm are theoretically improper and should be removed to ensure analytical correctness.
Moreover, the bonus term 6', is derived by bounding the deviation between @h a) and (7 a). This analysis relies on applying the Azuma Hoea-iiog inequality to two martingale difference terms:
N Σ
N
n NO
(Q
oft) 0% (st,
and
Σ
1
No
(5
afinnd (sh
based on the following assumed decomposition: (st,
2) (sh ) 2 at: = (7 akt)
(57)
This decomposition implies that the sum of the estimators 2/ bootstrapping forms an unbiased estimate of QJ a).
(s, a) and (s in multi-step
However, Xu et al. (2021) incorrectly apply the Hauma-Hooffdding inequality by centering the es- timators 2 a) and V (st) around their expectations (see their Equation (4.2) and Lemma
38

---

Published as a conference paper at ICLR 2026
4.1), rather than around their corresponding conditional expectations (s.a) and Q (s.a). Moreover, the unbiasedness of multi-step bootstrapping implied by Equation (57) requires formal justification. These issues compromise the claimed optimism and pessimism properties of the Q- estimators, thereby invalidating the corresponding fine-grained regret guarantees.
To address these issues, introduce the following key modifications:
(a) Revising update rules. We move the truncations at and 0 in Equation (53) and Equation (54) to the corresponding V-estimates (lines 15-16 in Algorithm 4), retaining only the multi-step boot- strapping updates. This allows us to recover the equalities in Equation (55) and Equation (56).
(b) Proving unbiasedness of multi-step bootstrapping. We rigorously prove Equation (57), show- ing that 2% 2 (s, a) and V - (s))) form an unbiased estimate of the optimal value function Q*
(c) Ensuring Martingale Difference Condition. We ensure the validity of Azuma-Hoeffice in- equality by centering the two estimators (s, a) and V (s in multi-step bootstrapping around their conditional expectations, Qfi a) and (s,udds,
(c) Tightening confidence bounds. By jointly analyzing the concentration of the estimators Qh (s. a) and V (sfe), we reduce the bonus by by half, leading better empirical performance. We detail our Refined AMB algorithm in the following subsection.
G.2 REFINED AMB ALGORITIM
We present the Refined AMB algorithm in Algorithm 4 and Algorithm 5, which preserves the overall structure of Xu et al. (2021).
To recover valid upper and lower confidence bounds for the Qesttimators, we slightly modify the update rules by shifting the truncation from the Q-estimates to the corresponding V-estimates:
(5 = (1 - 7 ) (s, a) + +7m (0t (s, a) - v*(())))) + bn
(s,aa = (1 1-77)) 2
k- (s, a) + +1 (Qh (s, a) + (*t,),))) bn.
V (s) = min
H, max Qn (())
@ (s,
V (s) = max
0. max O (s. (2)
Here, the refined bonus is defined b, /2, exactly half of the bonus used in the original AMB algorithm. These modifications enable us to establish the following theorem:
Theorem G.1 (Formal statement of Theorem 4.3.). With high probability (under the event H. in
Lemma G.I), the following conclusions hold simultaneously for all (s, a, h, k) E AxAx [H] x [K]:
vi((s) Z (s) 2 (h)ss) and ("(s,)) a) 2 (T(s,a) 2 (s,a).
(58)
Moreover, the following decomposition holds:
2 a) ( a) (s)
(59)
The proof is provided in Appendix G.3, where the optimism and pessimism properties of the Q- estimators are formally established. By adapting the remaining arguments from Xu et al. (2021) along with the simplifications in Appendix G.4, we show that the Refined AMB algorithm achieves the following fine- fineinrained gap-dependent expected regret upper bound:
11
HD log(SAT) An(s,a)
H 7 log ( (SAT)
Σ
Σ
Amin
A=1 (a(sn))0
Here, for any h E [H]. we have (s)) fa AlA, (s, 0} and
Zmmll
{(s h) E
S x Ax [H]JAN a) = 0, 1opr (s)l > 1}.
39

---

Published as a conference paper at ICLR 2026
Algorithm 4 Refined Adaptive Multi-step Bootstrap (Refined AMB)
1: Input: (0, (failure probability), H, A, S, 21
2: Initialization: For any V(s, a, h) E S x A x [M], initialize Q2(s,a) + H. (3, + 0.
C 0, (s) A and (*) = (s) 0.
3: for k == 1, 1....... K do
......KK
4: Step 1: Collect data:
5: Rollout from a random initial state of ~ using policy Th = { / defined as:
A (s) A arg max a (M a) 24 (s,a).
if AA (s) > 1 if (s)) =1
the element in (s).
and obtain an episode {s ah rh = (s a(11) {
6:
7:
Step 2: Update Q-function:
8:
for h = H. H 1..... ........d.. do
9:
if x & C then
UPDATE(S ho of, k, h).
11:
end if end for for
12:
13:
(s, E Ax [M] [(5 a < h H k $ G do
14:
On (s, -
() a). -
15:
VA 1+1
(s) (s)= -V) (s), L
(s).
16:
end for
Step 3: Eliminate the sub-optimal actions:
18:
Vs E S.h E [H], set A (s) = fa
(+) A
21(s))
Vs E S, set G+++1 E S: |/ =s] 11
20: end for
Algorithm UPDATE(S, a, h)
1: Set V
#+1 V (s) = 0.
2: Vn, set The 11+"
H+1
3: Let n N/ a) be the number of visits to (s,a) at step h in the first k episodes.
4: Let h = hh,, k)) be the first index after step h in episode k such that sy & G (If such a state
does not exist, set h H + 1.)
5: Compute bonus: 6, 2 H3 (S8T/A///)//
6: Compute partial return: 2 (s, = Ensien
7: Qh k+1
(8, a) (1 7h, 1 (8, T (s) Vx + bn
8: 2 Q (s, (1 The 1² (s, a) Tn (Q) (s,a) (xh bn
9: *+1 (s) min { max Qn (s,
10: L vi+l(s) max (AA))) 2h (
(s.
G.3 PROOF OF THROREM G.1
We first prove some probability events to facilitate our proof.
Lemma G.I. Let log(2S AT) for any failure probability p (0, 1). Then with probability at least 1 - p. the following event H holds:
N
NO 17
(10x
0% dd) (s,0) + Vi - 2t" (s,a)) $2
()) V(s,
Ha,
1=1
40

---

Published as a conference paper at ICLR 2026
Proof. The sequence
Σ The ((0h -0x 11 (5, (i((5))) a (0.
NEW+
is martingale sequence with
mn (00 () (s. (s. (
o (s. nf H.
Then according to Azuma- Hoeffding inequality and (b) of Lemma D.2, for any E (0, with probability least 1 P holds for given N (s N E N+ that:
Σ M ( - 2t -1 (s,
(M VM
o (s,
H S 2V
N
For any all (s, /, k) E A x [M] x [K]. we have (s, E 1 Considering all the possible combinations (s, a. h. N) Ax
H
x
H. with probabiiiyy at least 1 -p, it holds simultaneously
T
for all (s, a, h, k) E x A H x |
that:
N Σ 1=1
NN
((0H-- - -d) (s,a) + (2())) 0 (s.
-
H3, 5// (E(ssa)
%
Now we use mathematical induction on & to prove Theorem G.1 under the event H.
Proof. Part 1: Proof for ks 1.
For 1, the Equation (58) holds based on the initialization in line 2 of Algorithm 4.
Now prove Equation (59) for k 1 by induction on / H, I.....I. 1.
For h = H, we have h (1, H) = + 1. Equation (59) holds in this case since Qi a) TH (s, a) = Q2 (s, a) and Q (s. a) = 0. Now assume that Equation (59) holds for H,..., h + 1. We will also show it holds for step h.
First, we expand 27 a) as follows:
(s,
R'-1
as) =E
Σ
ni
क. (st))
FM.1, (sh, = (s,
h
Σ
Σ
Σ
mitt mi (6t) Fr,, at) (8, o = o
d'EG...
l=h
X = s'1(s)/ an) (s,
(60)
Σ a)(s, (s) = s s'((s), ah) (s,a))
S'G
Σ
(n)(s,)) + Qhd (s', (h,, (sh+1 s'1(s), at) = (s,
(61)
S'EGI
=s)(saa)+
Qid (8,, क (
(sh+1 = s'1 az) = (s,
(62)
PEG
The Equation (60) is obtained by applying the law of total expectation with respect to leveraging the Markov property of the process. Equation (61) is because:
$ and
41

---

Published as a conference paper at ICLR 2026
If s/+1 & Gh+ti then h' = hk, h) h 1 and
R
E
Σ 1=h
r(s).mt(8 (s))) | Fr.1: ($), a/) = (s.a), s/41 s = rr(ss, a);
If 8h1 E Gh+1 then R = k'(k, = (K, h + 1). In this case, since 2h+1 2 Vut 2 Uuti
a141 = Ti (1) is the unique optimal action T (1)+ Therefore we have
1
E
Σ
r(s),
(st)) Fh, (5), (s, a), s/+1 s'
l=
W-1
as) + +E
Σ 1=++1
rist (+t)) Futza, (sh+1, (5', mb+1((6))
= rr(ss a) + 0141 (s', Th Th+1
Similarly, we also have
(s,
1.nd (s.a) a) = (V FA.s, (sh m/) = (8,
E E (s)p Fh. (6/ ah) = (s, s/411 = = (sh+1 = s'( a/) = (8,
MEG
Σ
E (ste)) F,, o = (s. a), shyt = s (sh+1 = s'1(sh ah) = (s)
s'EG
Σ (5 (sh+1 s'I(shh ah) as)
Σ
( (5)))P (s/+1 a </hh ah) (s,a))
(63)
Here Equation (63) is because if 1/ $ Ch+1 then //' = hk) = h + 1 and
E [V (sk) | Fn,1, (sh, ah) = sh+ =s] = (i+i('');
If s Gh then W' = hkk,, h) h',,, h + 1) and
E (V F (5), at) (s. a), s =5] Quidd (s', (8))
Combining the results of Equation (62) and Equation (63), we reach:
(s, + Q (s,a)
=r)(s,a)+
Σ (S) (sh+1 s'1(s), (s)
MEGH
Σ
Th (s')) +
Quindd (s', The (s))) IP (sh+1 = (1hhhaah)) = (s, a))
REG
= =n((sa)++ +
Σ
Vhin (s')P (s)) s'I(s// a/. (s, a))
SEG)
Σ
(s'r (sh+1 = =11(sh) a/) = (s,a))
(64)
S'EG
a (s) (sh+r 5/1(th ah) (s,a))
(s)
(65)
42

---

Published as a conference paper at ICLR 2026
Equation (64) is because by induction, we have
2 (s', (s)) + Q1 (s') ( ( = Vi+t(s').
Equation (65) uses Bellman Optimality Equation Equation (2).
Part 2.1: Proof of Equation (58) for k + 1.
Assuming that the conclusions Equation (58) and Equation (59) hold for all 2,,,...AA h. we will prove the conclusions for k 1.
(s, a, h) ES x [M] {(6 a S H & G then we have
V k+1
(s) (=) 2 vi( 2 vk(ss (s)
and
Qh (s.a) (x a) 2 (% a) 2 (s.a) 2 (s,
For (sh a h) with sf $ G based on the update rule in line and line 7 in Algorithm 5, we have
No+:
Qn (5h
++1 (s an )) =
) 1/0
H
No
(Qh
+ V (y + by)
i=1
N
k++
N++1
Nx+1
(0% (s) + ( + 2 Nk+1*
H3,
2 110
H +
tli
(66)
1=1
and
Nx++1
(st
Σ
No
+ (h -b.)
b.).
=
"11
i=1
T
Nł+1
(Øt (s)
+ vk
Ko -2/ N
H3,
(67)
These two incqualities are because
N+++1
N
N
H3t
H3,
1/
2
1
2/
No+1
by (c) of Lemma D.2. Furthermore, by Equation (59) for ks S k, it holds that:
Q af: Of dl (s, Q% un (s.a).
x
Combining with Equation (66) and Equation (67), we can derive the following conclusion:
Qi)
(5 a
Nx++
Nk11
(Q
(0.'"s)))) + V (( Qi att) + +2
H3, Nk+I
1=1
N
Nk+1
( ViA (sti
11
1=1
N
Nē (2) a) ( (s, (/((s)) 2% (s,)) +2
H3,
T
N
2 0.
1=1
43

---

Published as a conference paper at ICLR 2026
Vhn The last inequality holds because h+1 (5 2 Vit for all k I k and the event H. in Lemma G.I. Similarly, we can prove the pessimism 2% g++1:
2 Qi) (5h a
N
Σ
N++1
(oh (s) ) + ((wmm))))))))))))) (1hh + +2
11a6
718
No.
i=1
N
Σ
(v--- - -0z) (
?h
1=1
N
No (0th (s, (s,a) - ((>(s))) (s - - N S 0.
Th
The last inequality holds because kh+1 (s - Vitta (5/+ta) for all k < k and the event H. With this, we have shown that Qn (s, 2 (7 a) 2 0 (ss Therefore, by noting that
vh k+1 (s) min H, max Qn (s, 2 aEAf(a)
max () (s) aEAf(e)
and
V (s) (8) max {o, max aEA
(s, a)) S max (% a) (s))),
we complete the proof of the Equation (58) for +
Part 2.2: Proof of Equation (59) for k: + 1.
Next we prove Equation (59) for k + by induction on h H....,
For h = H, we have h' (k, H) = H + 1. Equation (59) holds in this case since (H, a) = (s, a) and Q11²da (s. O. Assume that the conclusion holds for H,... 1. For step h, similar to Equation (62) and Equation (63) for h = 1, we obtain:
TH (s, a) Q
h (s, r) +
Σ d' e'EG
aft1dds (s', Th42(61)) (sht1 s'((s k+1 dbt1) (s,a))
and
(s,
Σ (s')
k+1 = s'((s ,0 _ = (s,
Σ S'EG
cttleed Quti (s', mh ( (s s </1s a k+1) (s. a))
By combining these two equations, as in Equation (65), we establish Equation (59) at step / for k + which completes the inductive process and thus proves Lemma F.2.
This lemma successfully establishes the optimism and pessimism properties of the Q-estimators. Leveraging the remaining arguments in Xu et al. (2021), we can recover the same gap-dependent expected regret upper bound presented in Equation (11).
G.4 RESULT SIMPLIFICATION
By adapting the remaining arguments from Xu et al. (2021), we can recover the following bound for Refined AMB algorithm:
H
Hd (og(SAT)
H Z (SA()
Σ
Σ
+ SAHH
(68)
An(s,a)
Amin
#=1 (e(e))20
44

---

Published as a conference paper at ICLR 2026
Define Zuub {(s, a.h) h) (s, > 0} and recall that Zept a( h) (s. a) = 0} and
Zuul = {(s, a. h)) (s a) = O, Zope, (s)) > 1}, where (op),h(5)) = {a A a) = 0}. Then
have
SAH
/ssbl
/mull
/usubl + 1zppl - (1Zopll 7 ) 2 S(A - 1)H 2
because suubbl
A1S.AA and
Zopt| /Zmull Zopz /muul = al(ss,,,)) (s 0, 1z [s)] 1 - HS
/umul, we have (s) = 1, which implies that the optimal action a is unique for each state-step pair (8, h). Therefore.
since for each (s, a, h) & Zope/ /
H
H HloggSAAT)
H m (SA)
Σ
Σ
+
(s,
Ani
h=
(s(0))>0
H
Σ
H log(SS))) + 1 mmal log(S
#= As(s,0)00
H Ha (IZaull + Zmal) )) log(SA7)
SAH
4
where we used 0 (s,s, a), Amin H in the first incquality and log(S.AT) > 1/2 for S,T 2 and A 2 2 in the last inequality.
Thus, the Refined AMB result in Equation (68) can be equivalently written as
H log((AT)
2 log( SAAT)
0
An
Amin
A=1 (a(s,))20
45


Reviews:
[{"review_id": "VnIbs63cJJ", "reviewer": "Reviewer_HMT1", "summary": "This work establishes gap-dependent regret bounds for UCB-based model-free RL regarding individual suboptimality gaps $\\Delta_h(s,a)$ instead of global one $\\Delta_{\\min}$. Besides, this work identifies the issues in analyzing the AMB algorithm, which is non-UCB-based model-free algorithm, on incorrectly applying concentration inequalities, and refines the algorithm and the analysis.", "questions": "1 There lacks comparison between this work and model-based RL. For example: a) What is the technical difficulty in adapting techniques in model-based algorithms for deriving fine-grained gap-dependent regret bound? b) Comparison on the dependency on $H$, and potential improvement on $H$.\n\n2 What is the advantage of ULCB-Hoeffding over UCB-Hoeffding? They achieve the same fine-grained gap-dependent regret bound and their analysis are also similar. Given that ULCB is considerably more complex, I don't see the necessity of introducing ULCB algorithm in the main context.\n\n3 Comparing the last term in Eqn. (10) and Eqn (2), the non-UCB-based algorithm AMB achieves a better sample complexity in $H$. Is it due to the sharper analysis of AMB? \n\nMinor issues:\n\n1* Line 226 \"line 15 in Algorithm 2\": line 15 should be replaced.\n\n2* Line 310 Eqn. (5): inside indicator function, should $k$ be $k'$? The recursive definition is hard follow. It would be great if the authors could come up with intuitive way to explain the intuition if exists.\n\n3* Line 951 \"(1),.\" -> \"(1).\"", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1 This work establishes the first and tight individual-gap-dependent regret bounds for model--free RL, which improves coarse global-gap-dependent coarse bound in the prior work. The core technical contribution lies in separating the analysis of of optimal and suboptimal state-action pairs.\n\n2 This work refines and fixed the issues in the AMB algorithm and associated analysis, which provides a rigorous fine-grained regret bound for non-UCB-based algorithm.", "weaknesses": "1 The analysis is based on episodic tabular MDP. The theoretical guarantees do not extend to complex settings such as linear MDP, MDP with function approximation. \n\n2 Model-based algorithms has shown to achieve fine-grained gap-dependent regret bound. This work addresses a theoretical gap where model-free algorithms were lagging behind model-based algorithms in this setting. The contribution may not be significant.\n\n3 The regret bound has high dependency on the horizon $H$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gFbUyH4Nnu", "reviewer": "Reviewer_F9mz", "summary": "This paper studies the online tabular RL problem.\nThe authors show that UCB-Hoeffding (Jin et al., 2018) achieves a fine-grained, gap-dependent logarithmic regret bound.\nSuch a result is the first among model-free algorithms.\nWhile there is an exception of AMB (Xu et al., 2021), the authors point out errors in the analysis of AMB and propose how to fix it, providing a correct fine-grained regret bound and its proof for the algorithm.", "questions": "1. While a general framework for fine-grained, gap-dependent bounds for model-based algorithms is known (Simchowitz & Jamieson, 2019; Dann et al., 2021; Chen et al., 2025), I see that the analysis in this paper is different from the one in Simchowitz & Jamieson (2019). What challenges are there in applying the techniques in these papers to the model-free setting?\n\n2. I don't understand why UCLB is proposed when it is no better than UCB-Hoeffding both theoretically and empirically. If the goal is to show the generality of the framework, couldn't any other model-free algorithm be used, for instance, UCB-Bernstein or UCB-Advantage?\n\n3. In Section 4, it is mentioned that the analysis of Xu et al. (2021) violates the martingale property. It is due to the fact that $h'$ in their work is also random? It is not clear what this part is trying to claim. For instance, what are the values of the expectation and conditional expectation described in this paper?\n\n4. Under what MDP was the experiment conducted?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 4, "strengths": "The paper proposes a general framework for obtaining fine-grained, gap-dependent logarithmic regret bounds of model-free algorithms.\n\nThe raised issues for AMB and the corrected version seem valid.", "weaknesses": "Some core definitions for the analysis are not properly given.\n\n- Is $\\eta_ i^{N}$, introduced in line 310, $\\eta_ i \\Pi_ {j=i+1}^N (1 - \\eta_ j)$ or the $N$-th power of $\\eta_ i$? It seems like it's the former but I could not find the definition.\n\n- What is the input state-action pair of $N_ h^k$ when written without one? It appears multiple times including in the definition of $\\omega_ {h'+1}^k(h)$, but it is not clear from the context.\n\n- It seems like the definition of $\\omega_ {h'+1}^k(h)$ requires a state-action pair as $k^i$ requires a state-action pair in its definition. However, the notation does not reflect the fact. Also, there is a problem of using $N_ h^k$ without definition, so I have no idea what $\\omega_ {h'}^k(h)$ is supposed to represent.\nI hope there is a description about what $\\omega_ {h'+1}^k(h)$ represents as it is hard to understand it intuitively.  \nPartially due to these ambiguities, Lemma C.3 is not trivial. Also, it is really hard to see why the equation in line 372 is true. Could the authors explain how these equations are established?  \nIn addition, as I see that $\\omega_ h^k = \\mathbb{I}\\lbrace (s_ h^k, a_ h^k) \\in Z_ {\\text{sub}, h}\\rbrace$ in the end, which is a simple function, wouldn't plugging in this value from the beginning simplify the analysis a lot without needing to define multiple series of $\\omega$?  \n\nI will be happy to raise my score once these points are clarified.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SNQMxkJM20", "reviewer": "Reviewer_Er67", "summary": "This paper aims to establish fine-grained, gap-dependent regret bounds for model-free algorithms in episodic tabular MDPs. While such bounds exist for model-based methods, model-free approaches have been limited to coarse bounds dependent on the global minimum gap, $\\Delta_{min}$. The authors provide a two-part affirmative answer:\n\n1.  For UCB-based algorithms, they develop an analytical framework that distinguishes between optimal and suboptimal state-action pairs. Using this, they derive the first fine-grained, gap-dependent regret bound for the classic UCB-Hoeffding algorithm.\n2.  For non-UCB-based algorithms, they revisit the AMB algorithm (Xu et al., 2021), identifying and correcting significant algorithmic and analytical flaws to propose a Refined AMB. They then provide the first rigorous fine-grained bound for a non-UCB-based method.\n\nEmpirical results on synthetic MDPs validate the theory, showing that the refined algorithms outperform the original AMB.", "questions": "1. Please explicitly compare your analytical framework in Section 3.3 to the techniques used in model-based papers like Chen et al. (2025). What are the key technical novelties required to make this style of fine-grained analysis work for model-free Q-learning? What new challenges arise from this difference that your analysis overcomes?\n2.  Can you elaborate on the source of the large polynomial dependence on $H$? Is this an artifact of the analysis, e.g., from recursively applying bounds, and do you see a path to tightening it?\n3.  Could you provide a direct comparison between your final bound for Refined AMB (Eq 10, depending on $|Z_{mul}|$) and the bound for UCB-Hoeffding (depending on $|Z_{opt}|$)? Which bound is tighter, and under what conditions?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.  A key strength is the identification and correction of critical flaws in the AMB algorithm (Xu et al., 2021). The identification of improper truncation and violation of martingale difference conditions is a valuable and clear-cut contribution.\n2.  The paper successfully applies a fine-grained analytical framework, separating optimal/suboptimal pairs,  to the model-free setting, yielding the first fine-grained, gap-dependent regret bound for the widely-known UCB-Hoeffding algorithm.\n3.  The experiments clearly support the theory. The flawed AMB algorithm performs poorly, while the Refined AMB and UCB-Hoeffding all perform well and exhibit the logarithmic regret behavior predicted by the new theory.", "weaknesses": "1.  The paper's primary weakness is its failure to position its analytical framework relative to recent model-based works that also achieve fine-grained bounds, e.g., Dann et al., (2021); Chen et al., (2025). The paper cites these works but does not discuss the technical challenges of adapting their analysis to the model-free setting. Without this comparison, the core technical contribution in Section 3.3 appears to be an incremental adaptation rather than a novel framework.\n2.  The derived bounds include $H^5$ and $H^6$ terms. While the focus is on the gap-dependence, this looseness in $H$ is a significant limitation of the current analysis and makes the bounds less tight, even if they match the lower bound except for the factors in $H$.\n3.  The inclusion of the ULCB-Hoeffding algorithm feels unnecessary. It achieves the same theoretical bound as UCB-Hoeffding in Theorem 3.3, but performs noticeably worse in the experiments shown in Figure 1, distracting from the two stronger, clearer contributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bXyMfebiqd", "reviewer": "Reviewer_omHP", "summary": "This paper presents the  fine-grained, gap-dependent regret bounds for model-free reinforcement learning in episodic tabular Markov Decision Processes. While previous algorithms achieved minimax worst-case guarantees, their gap-dependent analyses were coarse, depending on the smallest suboptimality gap rather than individual ones. The authors introduce a new analytical framework that explicitly separates optimal and suboptimal state-action pairs, enabling fine-grained regret analysis. They apply this framework to the well-known UCB-Hoeffding algorithm, deriving a tighter bound that matches known lower bounds up to polynomial factors, and propose a simplified variant, ULCB-Hoeffding, which achieves similar theoretical guarantees with improved empirical performance. The paper also revisits the non-UCB-based AMB algorithm, identifying key theoretical flaws and proposing a refined version that restores correctness, ensures valid concentration analysis, and achieves a rigorous fine-grained regret bound in this class. Experimental results on synthetic MDPs confirm the theoretical findings, showing that the refined algorithms outperform prior methods. Overall, the work provides a unified framework that advances theoretical understanding of model-free reinforcement learning by bridging worst-case and instance-dependent analyses.", "questions": "1.  Can the proposed fine-grained framework extend to function approximation (e.g., linear or neural models)?\n2.  How do fine-grained regret improvements translate to real-world tasks (e.g., navigation, games)?\n3.   Are the polynomial factors in H (e.g., H^5 or H^6) necessary, or could further refinement reduce them?\n4.  Does the fine-grained analysis provide insight into exploration dynamics, beyond theoretical improvement?\n5.  Could this framework be combined with variance-dependent or adaptive analyses to yield sharper or adaptive regret bounds?\n6. Could ULCB-Hoeffding’s structure be adapted to other algorithms (e.g., Q-learning with linear approximation)?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Introduces a fine-grained decomposition that separately analyzes optimal and suboptimal pairs, tightening gap-dependent bounds.\n2. Framework applies to both UCB-based and non-UCB-based algorithms.\n3. Provides the first fine-grained regret bound for model-free RL; matches known lower bounds up to polynomial factors.\n4.  Identifies and corrects subtle theoretical flaws in prior work (AMB).\n5. Experiments confirm theoretical improvements and show scalability across MDP sizes.", "weaknesses": "1. Results do not extend to function approximation or continuous-state RL.\n\n2.  The theoretical derivations are mathematically heavy and might be difficult for practitioners to follow or generalize.\n\n3.  Experiments are conducted on randomly generated MDPs rather than benchmark environments.\n\n4.  The bounds, while asymptotically tight, may not yield practical improvements in all regimes.\n\n5. The experimental comparison includes few competing algorithms beyond AMB and its variants.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)