Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs
Authors: Shulun Chen
Runlong Zhou
Zihan Zhang
Maryam Fazel
Simon Shaolei Du
Venue: NeurIPS 2025 poster ()
Keywords: Reinforcement learning
gap-dependent
variance-dependent
instance-dependent
Primary area: theory
TL;DR: We develop a variance-aware gap-dependent regret bound with better $H$ dependence for tabular MDPs.

Abstract: We consider gap-dependent regret bounds for episodic MDPs.
We show that the Monotonic Value Propagation (MVP) algorithm (Zhang et al. [2024]) achieves a variance-aware gap-dependent regret bound of 
$$\tilde{O}\left(\left(\sum_{\Delta_h(s,a)>0} \frac{H^2 \log K \land \mathtt{Var}\_{\max}^{\textup{c}}}{\Delta_h(s,a)} +\sum_{\Delta_h(s,a)=0}\frac{ H^2 \land \mathtt{Var}\_{\max}^{\textup{c}}}{\Delta_{\mathrm{min}}} + SAH^4 (S \lor H) \right) \log K\right),$$ 
where $H$ is the planning horizon, $S$ is the number of states, $A$ is the number of actions, $K$ is the number of episodes, and $\tilde{O}$ hides $\mathsf{poly} \log (S, A, H, 1 / \Delta\_{\mathrm{min}}, 1 / \delta)$ terms. Here, $\Delta_h(s,a) =V_h^* (a) - Q_h^* (s, a)$ represents the suboptimality gap and $\Delta_{\mathrm{min}} := \min_{\Delta_h (s,a) > 0} \Delta_h(s,a)$.
The term $\mathtt{Var}\_{\max}^{\textup{c}}$ denotes the maximum conditional total variance, calculated as the maximum over all $(\pi, h, s)$ tuples of the expected total variance under policy $\pi$ conditioned on trajectories visiting state $s$ at step $h$. 
$\mathtt{Var}\_{\max}^{\textup{c}}$ characterizes the maximum randomness encountered when learning any $(h, s)$ pair.
Our result stems from a novel analysis of the weighted sum of the suboptimality gap and can be potentially adapted for other algorithms.
To complement the study, we establish a lower bound of 
$$\Omega \left( \sum_{\Delta_h(s,a)>0} \frac{H^2 \land \mathtt{Var}\_{\max}^{\textup{c}}}{\Delta_h(s,a)}\cdot \log K\right),$$ 
demonstrating the necessity of dependence on $\mathtt{Var}\_{\max}^{\textup{c}}$ even when the maximum unconditional total variance (without conditioning on $(h, s)$) approaches zero.

Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs
Shulun Chen
Tsinghua University
chens1220mails. www.aaillssssiiisateeeee tsinghua. edu. cn
Runlong Zhou
Zihan Zhang HKUST zihanzBust.
University of Washington vectorzhêcs, washington, edu
Maryam Fazel
Simon Du
University of Washington mfazel @uv. edu
University of Washington ssduêcs wwshington. edu
Abstract
We consider gap-dependent regret bounds for episodic MDPs. We show that the Monotonic Value Propagation (MVP) algorithm (Zhang et al. [2024]) achieves variance-aware gap-dependent regret bound
lo K Var
H² A Var
Σ
Σ (s(50))-
SAH H)
log K
An(s,a)
Amin
where H is the planning horizon, S is the number of states, A is the number of actions, K is the number of episodes, and Ô hides poly log( A, H, 1/ 1/Amin: 1/8) terms. Here, (n a) = V (a) Q a) represents the suboptimality gap and Amin := ( An(s, a). The term Var max denotes the maximum conditional total variance, calculated as the maximum over all (IT, h, 8) tuples of the expected total variance under policy и conditioned on trajectories visiting state at step h. Var characterizes the maximum randomness encountered when learning any (h, s) pair. Our result stems from a novel analysis of the weighted sum of the suboptimality gap and can be potentially adapted for other algorithms. To complement the study, we establish lower bound of
H² A Var An(s,a)
Ω
Σ
log K
(x.a))>
demonstrating the necessity of dependence Varf Vari even when the maximum unconditional total variance (without conditioning on (h, s)) approaches zero.
1 Introduction
Reinforcement learning (RL, Sutton et al. (1998]) is an interactive decision-making problem where an agent gains information from unknown environment through taking actions, with the goal
Work done while Shulun Chen visiting the University of Washington.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

expected total of maximizing the total reward. RL has a wide range of applications, such as robotics and control [Lillicrap al., 2015]. games [Silver al., 2016]. finance [Nevmyvaka al., 2006], healtheare [Liu et al., 2017], and recommendation systems [Chen et al., 2019].
The most canonical setting in RL is episodic learning in tabular Markov decision processes (MDPs), where the agent interacts with the MDP for K episodes, each episode allowing exactly H steps taken. Under this setting, we choose cumulative regret as the performance criteria, which should scale sublinearly with K to indicate that the agent is making progress by shortening the performance difference between the policy n² played in episode and the optimal policy л* Most work [Azar et al., 2017, Jin et al., 2018, Dann et al., 2019. Zhang et al., 2020, 2021a] in this topic focused on minimax regrer that is the worst-case guarantee for the algorithms over all the MDPs. Typically, these minimax regret bounds have main order terms scaling with VK.
The MDPs in practice often enjoy benign structures, so the above-mentioned algorithms may per- form far better than their worst-case guarantees. Consequently, problem- dependent regret bounds are of great interest. Variance- depeedee- regret bounds [Talebi and Maillard, 2018, Zanette and Brunskill, 2019, Zhou et al., 2023, Zhang et al., 2024] are informative when the MDP is near- deterministie. This type of regret bounds have main order terms scaling with v Var K where Var is a symbol for some variance quantity (might be different across different works). For deterministic MDPs and MDPs such that (s) V% (s') for any h, 8, 8', Var O.
Meanwhile, gap-dependent regret bounds [Simchowitz and Jamieson, 2019, Yang et al., 2021, Dann et al., 2021, Xu et al., 2021, Zheng et al., 2024] are especially favored when for every h, the optimal value (*) is better than other suboptimal values (7, a) by a margin. Formally, let (n a) V 0}. then a typical gap-depee dep-deenndent regret bound is
(s. a) and Amia min (s, (h, [H] S A,, >
((E
Σ
1 An(s,a)
+
Zoptl
+ poly(H,
poly(H)) log K
(1)
A min
(h. Zout.
where Zaub is the set of all suboptimal (h, s, a) tuples, Zopt is the set of all optimal (h, a) tuples, and Ô hides poly log(S, (S, A, H, 1/ Amin, 1/0) terms. When K is large enough, gap-dependent regrets grow much slower than minimax and variance-dependen, (when Var > 0) regrets.
A natural yet fundamental question about
regrets is:
What is the tightest problem-dependent regret while considering both variance and gap?
If such regret outperforms variance-onll-deeendee and gap-only-dependent regrets asymptoti- cally (as T - b0) while also being nearly minimax optimal, it is actually best-of-three-worldd:
To address the above problem, there are two factors that can be improved in previous gap-dependent regrets. First is the dependence on variance quantities. Only Simchowitz and Jamicson [2019], Zheng et al. [2024] contain variance-dependent terms in their gap-dependent regrets, while their variance quantities are defined as the maximum per-step variance, Q & H², This quantity is first defined in Zanette and Brunskill [2019], and all of them use HQ* on variances. This upper bound can be substantially larger than an expected total variance (such as Definitions 5 and 6 in Zhou et al. [2023]). From this side, a tighter dependence variance can improve the regret.
almost-sure upper bound
Second is the dependence on H. Specifically, when compared under the time-inhomogeneous set- ting, the poly( H) factors in Equation (1) are H3, Ho HJ, and H3 in Simchowitz and Jamieson [2019], Yang et al. [2021], Xu et al. [2021], Zheng al. [2024], respectively. Simchowitz and Jamieson [2019] provides a lower bound of Ω (Es,a (1//A((s,0) (s) shaving out extra H dependence.
which indicates the chance of
Our contributions. We analyze the gap-dependent regret of the Monotonic Value Propagation (MVP, Zhang et al. [2024] version) algorithm, which is a model-based algorithm already proven to be near-optimal in the sense of minimax and
regrets. After careful analysis,
Xu et al. [2021] used more fine-grained notion named Zmmi instead.

---

we show that the gap-dependent regret depends on a variance quantity Var max < HQ* and the worst-case dependency on is H². We improve the above-mentioned two factors simultaneously Formally, with probability at least 1 6, the regret in K episodes by MVP is bounded as
((1 Σ
log K A Var max
(H² A Var Zopt
+ SAH H) log K
An(s,a)
min
(h,,sa)EZZnn)
To the best of our knowledge, we are the first to incorporate righter variance quantity into gap- dependent regrets, and the worst-case dependency of H2 in gap-dependent terms is also the state- of-the-art (see Table 1).
To complement our upper bound, we provide a lower bound (see Theorem 3) of
H² A Var max log K
Ω
Σ
An(s,a)
(b,s,a)eZuub
With this lower bound, we show that the first term in the upper bound (2) is tight (modulo log terms). This implies that (i) is necessary to introduce the conditional total variance (see Definition 2) to derive variance-aware gap-dependent bound. In comparison, the unconditional total variance (see Definition 1) is sufficient for variance- aware minimax bounds (e.g.. Zhou et al. [2023]); (ii) When the first term in (2) dominates, the order of H cannot be improved.
Technical novelty. We propose a new variance metric to describe the upper bound of regret in gap-dependent MDPs. Our version of variance metric considers the conditional total variance to allow for some states with small visiting probability to accumulate a large regret over the whole training progress.
To derive a tighter regret bound using our new metric, we utilize novel analysis which reweighs the suboptimality gaps. Our approach does not require the clipping and recursion method in Simchowitz and Jamieson [2019] for the main bound; instead, we directly prove that a certain weight sum over all suboptimality gaps times the visitation counts is bounded by lower-order term of visitation counts, and establish congregated upper bound of all visitation counts. We believe our approach is novel and reveals fundamental facts about suboptimality gaps.
We also propose a more refined version of clipping for optimal actions. Our version of clipping utilizes the new conditional variance metric while also providing an O(11²) worst case bound for A Amin-depender terms.
Finally, we prove that the A,,s, a) terms in our upper bound match the lower bound modulo log factors. The construction is based on a reduction Bernoulii bandits. A key insight that low- frequency states, though often neglected in deriving minimax regret bounds, can still contribute substantially to regret gap-dependent bounds.
Paper overview. In Section 2, we introduce previous research about gap-dependent regret bound. In Section 3, we list the basic concepts of MDPs and define the conditional variance. In Section 4, we describe the MVP algorithm and provide a proof sketch of the gap-dependen regret upper bound. We conclude our paper in Section with a matching lower bound.
2 Related works
Gap-dependent regrets and sample complexities. Research gap-dependent regrets originates from aulti--rmed bandits, which are special MDPs with H S 1. Auer et al. [2002] showed a EoeZ log K x/A(a) type regret when running UCB algorithm MABs. Bubeck et al. [2012] proposed algorithms achieving Eoez... (A(a) + log(1/e)/ ((a)) bounded regret given knowledge of the maximum reward max, r(a) as well as lower bound E of A.
Aside from the works studying finite-horizon tabular MDPs mentioned in Section 1, there a line of work under the setting of gap-dependent regrets for infinite-horize tabular MDPs [Auer and Ortner,
3

---

Algoriha
Gag Gap-bpandoon Regust
Minirax Optinall
Sinnggtee
ON Wallan) Aead
Yos (Oly AK))
01 (a 1Z Daass SAMM( Wiy
No
O.0enilgg- Praget 1031)
Ne Blosral 2019
IN [[
XVI
Df (l iZ (f/ K SAI""
An
hee Prondded
Oging* mA log -
Yo (AIQ")
Yas H5
[Zaag et 2000
Fally
Yeuodig">>
Vix 1
This wet
Ofl (fPlig aastaa 1Svilt
SAM Ri) K) Yeu
[Phargg NMM
Lawer
Table 1: Comparison between different algorithms and their gap-dependent regrets for time- inhomogeneous MDPs. The result in Simchowitz and Jamieson [2019] is scaled accordingly as originally studied homogeneoss MDPs. Variance-dependenee: whether the gap-dependent regret is also variance-dependee
Var HQ* dependence H² Var is tighter. Min- imax Optimal: whether the analyzed algorithm achieves a Ō({H3SAK) (main order) minimax regret. Xu et al. [2021] did not provide such guarantee.
2006, Tewari and Bartlett, 2007, Auer et al., 2008, Ok et al., 2018], while these works, the gaps are usually defined as the difference between policies instead of actions. Recently, gap-dependent regrets have been studied for risk-sensitive RL [Fei and Xu, 2022], linear/general function classes [He et al., 2021, Papini et al., 2021, Velegkas et al., 2022], and Markov games [Dou et al., 2022].
Gap-dependenn sample complexities under online [Jonsson al., 2020, Marjani and Proutiere, 2020, Al Marjani et al., 2021, Wagenmaker et al., 2022b, Tirinzoni et al., 2022, Wagenmaker and Jamieson, 2022, Tirinzoni al., 2023] and offline [Wang et al., 2022, Nguyen- Tang et al., 2023] RL setting are also widely studied.
Minimax optimal regrets. Under the setting of tete-imm-nnen -otm---ihooogeeouss MDPs, algorithms achieving
a bigh-probability regret upper bound of Ö(v H3SAK) are (nearly) minimax optimal. There have been many works with this guarantee while optimizing the lower order terms: Azar al. [2017], Osband and Van Roy [2017], Zanette and Brunskill [2019], Simchowitz and Jamieson [2019], Zhang and [2019], Zhang al. [2020, 2021a], Ménard al. [2021], Li al. [2021]. Xiong al. [2022], Zhou et al. [2023], Zhang et al. [2024]. Notably, Zhang et al. [2024] derived the tightest Ö(v Ö(VH3SAK HK) regret up to logarithm factors.
derendet regrets. Talebi and Maillard [2018] studied variance deeundeed regrets for infinite horizon learning under strong assumptions on ergodicity of the MDPs. Zanette and Brunskill [2019) defined and incorporated the maximum per-step conditional variance, Q**, and first proved ((Q SAK) regret for the finite-horizon setting. Zhou et al. [2023], Zhang et al. [2024] proved regrets depending on expected total variances (see our Definition for one of their quantities) that are more fine mne-grinedd than the coarse HQ* upper bound. Variance-dee -erraneeddeeedeett regrets have also been studied for bandits [Zhang et al., 2021b, Zhou al., 2021, Kim et al., 2022, Dai al., 2022].
Other problem-dependent regrets. Under infinite-horizo setting, Bartlett and Tewari [2012], Fruit et al. [2018] studied regrets depending on the span of the optimal value function. There are works studying first-order regrets, whose main order terms depend value functions: Jin et al. [2020], Wagenmaker et al. [2022a], Huang et al. [2023].
3 Preliminaries
Notations. For any event E, let 1{E) be the indicator function of E. For any set X. we use x to denote the probability simplex over X. For any positive integer n, we denote [m] == 21, n). Ô, L, hide poly log(S, A, H, Amis 1/8) factors.
Finite-horizon MDPs and trajectories. A finite-horizon MDP is described by tuple M (S, A, H, P, R, p). is the finite state space with size S and A is the finite action space with size A. H is the planning horizon. For any (s, h) S A x [H] , Pa aa E A is the transition

---

function and Re,a, E (00 is the reward distribution with mean ra S x - [], H]. l e A
the initial state distribution. trajectory {ss, a1, 11 $2, ag r2.... Sn. ar. r'H3 is sampled with Ps oh, 1 ah where dn can be chosen arbitrarily.
jr, 8h+1
Unlike most common settings, we relax the standard assumption that Re.. E A lo, (uniformly bounded reward) and instead assume bounded total reward setting (Assumption 1). Problems under this setting can contain spike in reward and are therefore harder than standard problems.
Assumption (Bounded total reward). We assume that Σ Th & H for any possible trajectory.
deterministic policy chooses an action based on the current state and time step. Formally, ग = {TT where TT S - A maps state to an action. Any trajectory sampled by π satisfies = TT (sn). For any random variable X related to a trajectory, we denote E ["[X] and [=[X] as the expectation and variance of X when the trajectory sampled under
Policies. A
Value functions and Q-functions.
Given n, define its value function and Q-function
H Σ
H Σ
(8) = ET
Tt
8h
@T( = E"
rz (on, un) = (8, a)
It is easy to verify that (T,(s,) a) ra(s, a) + Psaah V We define Vi" := E [V [s) as the expected total reward when executing policy и.
Learning objective. Episodic RI on MDPs proceeds for total of K episodes. At the beginning of episode k, the learner chooses a policy xx and uses to sample a trajectory.
We aim to maximize VØ. Using dynamic programming, we can find policy x* maximizing all (T,ss,) a) simultaneously. and we denote V** := V** Q* == Q=*
Performance is evaluated by the cumulative regret:
Regret
Σ V/** Vor
Gap quantities.
The suboptimality gap is defined as follows:
as) (i) (s)
The sets of optimal and suboptimal actions defined as
Zopt {(s, a, h)) E S A [ (s = 0}, Zaub S Ax x [
The minimum gap Amin g An(s, is the smallest positive gap. WLOG, we only consider MDPs with nonempty Z
Variance quantities. The variance at each as, h) tuple [Zanette and Brunskill, 2019, Sim- chowitz and Jamieson, 2019] is defined as
(ar v P
Praa [r + V*)+1
The maximum per-step conditional variance is defined as Q max Var a). Previous works including Zheng et al. [2024] use HQ* which could be as large as H in their variance- dependent terms.
The maximum unconditional total variance has been introduced in prior works [Zhou et al., 2023, Zhang al., 2024] when studying variance-dependent regret bounds for MDPs.
Definition (Maximum unconditional total variance).
ff Σ
Varmax max : max T
Vax (sh, an)
5

---

These works showed that Var X min H2) and incorporated it in the main order terms of aariance-only-depeddee
regrets for better results. However, as we will discuss in Theorem 3, variance-aware gap-dependent regrets must scale with separate variance quantities for each (s, h) pair, even for those hard to visit. Thus, the quantity should be conditioned on (s, h).. We propose the following quantity as the maximum conditional total variance:
Definition 2 (Maximum conditional total variance).
H Σ (sw, ax)) 8/ =
Var max == max IE m,5,h
Remark 1. The maximum conditional total variance is novel in literature, as in variance-onke dependent works, marmax better quantity, while in previous variance-aware gap-dependent works, researchers did not develop better approaches other than bounding total variance by HQ* By definition, Var & HQ*, and our final results will scale with analysis, which can improve the dependency on H by one order.
H²) after careful
4
Main Results
4.1 Algorithm Overview: MVP
Monotonic Value Propagation (MVP, Appendix B) is a representative [Zhang et al., 2021a, Zhou et al., 2023, Zhang al., 2024] model-based optimistic algorithm which maintains upper bounds of V and Q*, namely 4 and Q*, in each episode. The rollout policy x* picks the action that max- imizes (s.)) at each step and updates the upper bounds using Bellman equation with empirical estimates of reward and transitions:
(s a) - (s, a) + B 1 a) + (s.
Vx(s) < max (s,
Here by (s. a) is a bonus term ensuring that Qn. V22 are upper bounds of Q Vi*t ("optimism") with high probability. For the proof of optimism, interested readers refer to Zhang et al. [2021a].
4.2 Gap-dependent Upper Bound
Now, present the main result of this work gap-dependent regret upper bound ensured by MVP. For the formal version, please refer to Appendix C.
Theorem 2 (Gap-dependent upper bound). There exists universal constants Ct2 02, Cg such that, for any MDP instance, any episode number K, and regret bound with probability at least 1 8:
MVP (Algorithm 1) attains the following
H² log K A Var
(H² Var max) Zopt!
Regret(K).
Σ
+ SAH v H)
log K.
(s)
Amin
(h,8,a)EZ,ut
Remark 2. This bound contains a new notion of maximum conditional total variance (Defini- tion 2). Since this definition requires us to condition any possible state, Var can be as large as O(H)). However, Var max is bounded by H max,,a, [Var (s, a, h)), so this term still no worse than previous O(HQ") bounds. Furthermore, there is sufficient condition to make Var max max = O lo))) for any policy и and (s, a, h) E S A x [H] the state-action pair (s, a) not reachable at step h if we sample the trajectory under n, it is visited with probability at least 5. We can even generalize this concept to exclude the states that are difficult to reach from the definition of Var V We omit this approach for simplicity.
The H² term in H² A Var is derived by conditioning on the event where all trajectorics have bounded total variance to avoid the dependence on Var max when it is large.
Our lower bound (Theorem 3) shows that Var cannot be replaced by Var (Definition 2), quantity used by previous prriance-only-dpeeeee
works. Intuitively, Var can be very small as long as all states with large variance have small visiting probability, but those states can accumulate a total regret of order Var a).aaa/a/) A a) that cannot be bounded by Varmax. The leading term matches with the lower bound modulo log factors. Furthermore, Simchowitz and Jamieson [2019] has shown that A -mieedepnddent term is unavoidable for UCB-base algorithms. Our coefficient of the Amin term is also improved to worst case O (22), better than previous worst-case factors of HQ* [Simchowitz and Jamieson, 2019) and 33 [Zheng et al., 2024].

---

4.3 Proof Sketch
We present the high-level ideas in the proof for Theorem 2 here, deferring the details to Appendix C. We assume the optimistic condition holds (see Lemma 9).
Regret decomposition. Following Simchowitz and Jamieson [2019], define a)) == (h(s, a) - (R, + E=' [+]
(3)
as the surplus at (s, a, h, k) E SX A x [H] x [K]. Standard analysis show the regret bound
Regret K) z I
ΣΣ (s)
A=1
Analyzing gaps and surpluses. Suppose that the algorithm takes action a at state at episode k stage h. By optimism, Q a) must be at least V (s) (f. (s,s, a), so have
(s, a) E "
(it)( An(s.a).
By recursively expanding the V term, have
An(s, a) E
Σ
(Sw (s, (s.
(4)
That is, the expectation of future surpluses is small, then the algorithm will avoid actions with large suboptimality gap.
The analysis of Ej shows that (see Lemma 16)
(ar a)e
SH n (3 as)
(x) $
E=*
(s,
8/
low order terms
We consider the restrictions of n (s, a) when (s) 0. If the lower bound Equation (4) wrote An(s,a) a) & (s, a), then n (s, a) & Varf (n) a)?, which would directly provide regret bound. However, Equation (4) contains the sum all future surpluses, so we cannot directly apply this method.
We will circumvent this problem by adding Equation (4) over all k and h. The summation of the left-hand side is Le,,hh (s a)n a), while the summation of the right-hand side can be shown
as approximately (low-order terms discarded) E / /ar (s, (s.
This inequality has the form Esa.h Mo,a,hM((s, a) & Ee,an "s n (s, a) for some non-negative coefficients Ua Ve,a.h- It entails upper bounds of nz(s, a). and if we proceed with the calcula- tions, we will recover the bound
Σ HVar (some low-order terms)
Regret(K) S
(s
S.0.h
in Simchowitz and Jamieson [2019] while avoiding complex calculations. In the latter steps, we will refine this method for tighter bound.
Generalized weighted anced as (s, a) = ((H2) only happens for small portion of (s, a, h). In contrast, the summa- tion of Equation (4) contains enough degrees of freedom for utilize it for better bound. Let wp. (8, a) be any set of nonnegative weights. Then the weighted sum of Equation (4) writes
of suboptimality gaps. Intuitively, the previous bound is not bal-
H
Σ wn(s. als. (s. S.a.h
Σ
Σ
wh (s)
(5)
h-1
W-hh
where Fk-1.h the a-field generated by first episodes and the first states in the k-th trajectory. We will choose (n carefully to balance the contribution of cach term.
7

---

Bounding weighted sum of surpluses.
The right-hand side of Equation (5) needs to be manipu- lated carefully. Rewriting the summation order, the leading term of Equation (5) becomes
H
K
(ar ad)e
W Σ
Σ Σ
wn
(s',''
We will apply certain probability inequalities to approximate ([1 -
with 1f 1( ) (s',a'}} (approximation error omitted). Then, the innermost sum over h con- tains only (s ) which can be bounded by W = H Var max if we pick w a) = Var,,, a). Now, the sum over is
(K,a') aa)
Var (s', (s',d') =0 0 (vvar a') a')))
71
so by Equation (5),
Σ
Σ Var a)nk (s, a)c.
End of proof.
With similar (and simpler) arguments above, we have
Regret( $ R,
where again, we ignore the lower-order terms.
We apply the Cauchy-Schware inequality Equation (6) and get
N
2 (s, a)nk (8, = R²
WR.
Σ 3,0
Σ 18a,
(s
so we conclude that
We
Σ 8,ah
An(s,a)
5 Gap-Dependent Lower Bound
In this section, we will prove the following gap-dependent regret lower bound. shows a separation between Var max and Var as well as the necessity of Var max in gap-dependent regrets.
Theorem 3. /Gap-dependent lower bound (informal)] Fix S, A, H and the target conditional vari- ance L E [1, H²]. Given a of SAH suboptimality gaps (Ai), assume that all non-zero gaps are sufficiently small. For any algorithm, there always exists an MDP with gaps equal to e ((ii), V (L) but Var max- O(1), such that
Regret (K) St
Σ 6:
L A.
log K
Proof sketch. We sketch the proof as follows. For simplicity. we assume there are 4 states {A, B, D) in each h-th layer. The dynamics of the four states are presented below.
A There only one action at A, which transits the agent A in the next layer with probability LH. and with probability LH The reward 0 at A;
There are actions at B. For each action a, the agent transported with probability A(a.).
A(a;) and D with probability 2 IVL
1VL
C This state is terminal state with reward VL;

---

D This state is a terminal state with reward 0.
In this instance, the learner makes a decision only at state B for each layer h, and state A has variance O (VL)²) O(H and state B has variance (LL), showing Varmax = (()). For any strategy т, it visits B with probability 1 - -1 LH = =,
max & O-O LO(L=)) O(1).
Clearly, the decision problem at state B and layer h could be viewed Bernoulli bandit problem. The expected visiting count at state and layer is @ L.). Let Regret, ( be the regret by taking suboptimal actions at B and the h-th layer. Consequently, applying the classical lower bound on regret for Bernoulli bandits yields:
lim K -0
Regret (K) !
Σ
\A(BBaa)
L
log( ()
Thus,
Regret K.
2
Regret n. (K) 2Ω (B,
Σ h.a
L
log
for sufficiently large K.
This example shows separation between unconditional variance Var and con- ditional variance Varmax- Even if Varmax = 0(1), there can still be regret lower bound of order (H1²). In this view, our introduction to Var is essential in proving gap-dependent regret bounds.
Discussion.
We also observe that the second term (H2 vars Mopp in our upper bound (2) is not yet matched Amin by this lower bound. This could pose a significant challenge for existing optimistic algorithms, as they typically explore all potentially optimal actions, resulting in additional surplus terms. We refer the readers to Appendix D the full proof of Theorem 3.
Conclusion
In this paper, we study gap-dependent regret bounds for episodic MDPs and demonstrate that the Monotonic Value Propagation (MVP) algorithm Zhang et al. [2024] achieves tighter upper bound compared to previous works from the aspects tighter dependence on a better variance notion, as well as reduced order of H. Our analysis centers around a careful bound of the weighted sum of suboptimality gaps. Along the way, we introduce a new notion of maximum conditional total variance and provide lower bound to establish its necessity well as the tightness of the (s(,, term.
We also acknowledge some limitations. First, the (H² Var max Zopil term in our upper bound does Amia
match the lower bound of 3mm in Theorem 2.3 of Simchowitz and Jamieson [2019]. Improv- ing either the upper bound lower bound will help advancing the understanding of gap-dependent regrets. Second, we only apply our new techniques to tabular MDPs. For future work, we be- lieve analysis
be adapted other problem settings (e.g., linear MDPs [Wagenmaker and Jamieson, 2022] and MDPs with general function approximation) to derive tighter gap-dependent regret bounds.

---

Acknowledgement
SSD acknowledges the support NSF DMS 2134106, NSF CCF 2212261, NSF ISS 2143493, NSF IIS 2229881, Alfree P. Sloan Research Fellowship. and Schmidt Sciences AI 2050 Fellowship. RZ and MF acknowledge the support of NSF TRIPODS DMS-2023166 The work MF was supported in part by awards NSF CCF 2212261 and NSF CCF 2312775.
References
Aymen Al Marjani, Aurélien Garivier, and Alexandre Proutiere. Navigating to the best policy in markov decision processes. Advances in Neural Information Processing Systems, 34:25852- 25864, 2021.
Peter Auer and Ronald Ortner. learning. Advances neural information processing systems, 19, 2006.
Logarithmic online regret bounds for undiscounted reinforcement
Peter Auer, Nicolo Cesa-Bianche and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-255 2002.
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, lan Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International conference on machine learning, pages 263-272. PMLR, 2017.
Peter I. Bartlett and Ambuj Tewari. Regal: A regularization based algorithm for reinforcement learning in weakly communicating mdps. arXiv preprint arXiv: 1205.666,, 2012.
Sébastien Bubeck, Nicolo Cesa- Desa-Bianchi, et Regret analysis of stochastic and nonstochastic multi- armed bandit problems. Foundations and Trends@ in Machine Learning, 5(1):1-122, 2012.
Minmin Chen, Alex Beutel, Paul Covington, Sagar Jain, Francois Belletti, and Ed H Chi. Top-k off poolcy correction for a reinforce recommender system. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pages 3364464, 2019.
Yan Dai, Ruosong Wang, and Simon S Du. Variance-aware sparse linear bandits. arXiv preprint arXiv:2205. 13450, 2022.
Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards accountable reinforcement learning. In International Conference on Machine Learning, pages 1507-1516. PMLR, 2019,
Christoph Dann, Teodor Vanislavov Marinov, Mehryar Mohri, and Julian Zimmert. Beyond value- function gaps: Improved instance-dependent regret bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 34:1-12, 2021.
Zehao Dou, Zhuoran Yang, Zhaoran Wang, and Simon Du. Gap-dependent bounds for two-player markov games. In International Conference on Artificial Intelligence and Statistics, pages 432- 455. PMLR, 2022.
Yingjie Fei and Ruitu Xu. Cascaded gaps: Towards logarithmic regret for risk-sensitive reinforce- ment learning. In International Conference on Machine Learning, pages 6392-6417. PMLR, 2022.
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient bias- taas-span-constrannee in reinforcement learning. In International Conference on Machine Learning, pages 1586-158. PMIR, 2018
Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. In International Conference on Machine Learning, pages 4171- 4180. PMLR. 2021.
10

---

Jiayi Huang, Han Zhong, Liwei Wang, and Lin Yang. Tackling heavy-tailed rewards in reinforce- ment learning with function approximation: Minimax optimal and instance- deeendeet regret bounds. Advances in Neural Information Processing Systems, 36:56576-56588 2023.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. 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, pages 4870-4879. PMIR, 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. Advances in Neural Information Processing Systems, 33: 13:1223-1200 2020.
Yconeung Kim, Insoon Yang, and Kwang-Sune Jun. Improved regret analysis for variance- suriance-adaptive linear bandits and forezon-frree linear mixture mdps. Advances in Neural Information Processing Systems, 35:1060-1072, 2022.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
Gen Li, Laixi Shi, Yuxin Chen, Yuantao Gu, and Yuejie Chi. Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Advances in Neural Information Processing Systems, 34:17762- 2021.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint /rxiv
2015.
Ying Liu, Brent Logan, Ning Liu, Zhiyuan Xu, Jian Tang, and Yangzhi Wang. Deep reinforcement learning for dynamic treatment regimes on medical registry data. In 2017 IEEE international conference on healthcare informatics (ICIII), pages 380-385, IEEE, 2017.
AA Marjani and Alexandre Proutiere. Best policy identification in discounted mdps: Problem- specific sample complexity. arXiv preprint arXiv:2009. / 13405, 2020.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penal- ization. arXiv preprint arXiv:0907.3740, 2009.
Pierre Ménard, Omar Darwiche Domingues, Xuedong Shang, and Michal Valko. Ucb momen- tum q-laarnig: Correcting the bias without forgetting. In International Conference on Machine Learning, pages 7619-7618. PMLR, 2021.
Yuriy Nevmyvaka, Yi Feng, and Michael Kearns. Reinforcement learning for optimized trade exe- cution. In Proceedings of the 23rd international conference on Machine learning. pages 673-680, 2006.
Thanh Nguyen-Tany Ming Yin, Sunil Gupta, Svetha Venkatesh, and Raman Arora. On instance- dependent bounds for offline reinforcement learning with linear function approximation. In Pro- ceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 93 10-93118, 2023.
Jungseul Ok, Alexandre Proutiere, and Damianos Tranos. Exploration in structured reinforcement learning. Advances in Neural Information Processing Systems, 31, 2018
Ian Osband and Benjamin Van Roy. Why posterior sampling better than optimism for reinforce- ment learning? In International conference on machine learning, pages 2701-2710. PMLR, 2017.
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-16683, 2021.
11

---

David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
Max Simchowitz and Kevin G Jamieson. Non-asympiotic gap-dependent regret bounds for tabular mdps. Advances in Neural Information Processing Systems, 32, 2019.
Richard S Sutton, Andrew G Barto, et al. Reinforcement learning: An introduction, volume 1. MIT press Cambridge, 1998.
Mohammad Sadegh Talebi and Odalric-Ambrym Maillard. Variance-aware regret bounds for undis- counted reinforcement learning in mdps. In Algorithmic Learning Theory, pages 770-805.
PMIR, 2018.
Ambuj Tewari and Peter Bartlett. Optimistic linear programming gives logarithmic regret for irre- ducible mdps. Advances in Neural Information Processing Systems, 20, 2007.
Andrea Tirinzoni, Aymen Al Marjani, and Emilic Kaufmann. Near instance-optimal pac reinforce- ment learning for deterministic mdps. Advances in neural information processing systems, 35: 8785 $785-8798, 2022.
Andrea Tirinzoni, Aymen Al-Marjani, and Emilie Kaufmann. Optimistic pac reinforcement learn- ing: the instance-depnndent view. In International Conference on Algorithmic Learning Theory, pages 1460-1480. PMLR, 2023.
Grigoris Velegkas, Zhuoran Yang, and Amin Karbasi. Reinforcement learning with logarithmic re- gret and policy switches. Advances in Neurul Information Processing Systems, 35:36040-36053, 2022.
Andrew Wagenmaker and Kevin G Jamieson. Instance-dependen near-optimal policy identification in linear mdps via online experiment design. Advances in Neural Information Processing Systems, 35:5968-5981, 2022.
Andrew Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson. First- order regret reinforcement learning with linear function approximation: robust estimation approach. In International Conference on Machine Learning, pages
PMLR, 2022a.
Andrew J Wagenmaker, Max Simchowitz, and Kevin Jamieson. Beyond no regret: Instance- dependent pac reinforcement learning. In Conference on Learning Theory, pages 358-418. PMLR, 2022b.
Xinqi Wang, Qiwen Cui, and Simon S Du. On gap-dependent bounds for offline reinforcement learning. Advances in Neural Information Processing Systems, 35: 15:14765-4887,,2 2022
Zhihan Xiong, Ruoqi Shen, Qiwen Cui, Maryam Fazel, and Simon S Du. Near-optimal randomized exploration for tabular markov decision processes. Advances in neural information processing systems, 35:6358-6377, 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 T'heory pages 4438-4472. PMLR, 2021.
Kunhe Yang, Lin Yang, and Simon Du. Q-learning with logarithmic regret. In International Con- ference on Artificial Intelligence and Statistics, pages 1576-1584. PMLR, 2021.
Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds, In International Conference Machine Learning, pages 7312- PMLR, 2019.
Zihan Zhang and Xiangyang Ji. Regret minimization for reinforcement learning by evaluating the optimal bias function. Advances in Neural Information Processing Systems, 32, 2019.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learningvia reference-advantage decomposition. Advances Neural Information Processing Systems, 33: 15198-15207, 2020.
12

---

Zihan Zhang, Xiangyang Ji, and Simon Du. Is reinforcement learning more difficult than bandits? near-optimal algorithm escaping the curse of horizon. In Conference on Learning Theory, pages 4528 4531. PMLR, 2021a.
Zihan Zhang, Jiaqi Yang. Xiangyang Ji, and Simon S Du. Improved variance-aware confidence sets for linear bandits and linear mixture mdp. Advances in Neural Information Processing Systems, 34:4342 4355, 2021b.
Zihan Zhang, Xiangyang Ji, and Simon Du Horizon-free reinforcement learning in polynomial time: the power of stationary policies. In Conference on Learning Theory, pages 3858-3904. PMLR, 2022.
Zihan Zhang, Yuxin Chen, Jason Lee, and Simon Du. Settling the sample complexity of online reinforcement learning. In The Thirty Seventh Annual Conference on Learning Theory, pages 5213-5219. PMLR, 2024.
Zhong Zheng. Haochen Zhang, and Lingzhou Xue. Gap-dependent bounds for q-learning using referenceeadvaattage decomposition. arXiv preprint arXiv:2410.07574, 2024.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learn- ing for linear mixture markov decision processes. In Conference on Learning Theory, pages 4532 4576. PMLR, 2021.
Runlong Zhou, Zihan Zhang, 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, pages 12878-42914. PMLR, 2023.
13

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We prove new bound for gap-dependent MDP and this is reflected in the abstract.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss about the Amin term and an extra log factor in our regret bound.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specificattin, asymptotic approximations only holding locally). The au- thors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't i acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [es]]
14

---

Justification: Our main text discusses the intuition and provides a proof sketch. Full proof can be found in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: Our paper focuses on the theoretical part. No experiment was performed.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data also be provided via
often one good way accomplish this, but reproducibility detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models. it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
15

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
Our paper focuses on the theoretical part. No experiment was performed.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https: cc/
mublic//guides/CoeeSuuuui sosiodddessmmssssoooooi.c for more details.
While we encourage the release code and data, we understand that this might not be possible, so "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: wwtpcc/cppppp..ciiieeee.
Codeeubm ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only a subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Our paper focuses on the theoretical part. No experiment was done.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Our paper focuses on the theoretical part. No experiment was done.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
16

---

The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of eπrоrs is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Our paper focuses on the theoretical part. No experiment was done.
Guidelines:
The answer means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: https: httpppss//////ips../eee wctpppblcc/.thicscscteeeeeeeee
Answer: [Yes]
Justification:
We believe that our work conforms with Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our paper focuses on proving theorems for an existing algorithm. We are not aware of any societal impact from our paper.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility MI).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
No dataset is required for purely theoretical proof.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere usage guidelines or restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We didn't 't use any assets for theoretical proof.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, paperswi tecodhhodeee com/ dataasts has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
We didn't 't create any assets for our theoretical proof.
Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details of the dataset/code/mmodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: We didn't conduct any crowdsourcing or research with human subjects for our theoretical proof.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: We didn't conduct any crowdsourcing or research with human subjects for theoretical proof.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
19

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: We only used LLM for editing paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to LLM policy (https:/ httpss:///euripss.t http://uuurpsscc//oeeeeeeeeeeeee cct////nfeeeeece//2/////ii./ for what should or should not be described.
20

---

A Notations and Technical Lemmas
A.1 Notations
We list notations in Tables 2 to 4.
S,S = S
State space and its size Action space and its size
A,
[
H
Horizon
K
Learning episodes
8,8'
States in S
a, a'
Actions in
N.M.H. hh
Horizon numbers
k, K
Indices of learning episode
Paa.
Transition probability
Be
Distribution of rewards
Distribution of beginning state Expected reward Policy
(h(s,a)
π
(8)
Action that policy æ takes at state 8, step h
(s), (*())
V- Vufucction of policy and of optimal policy, respectively
(8, a), (s,
Q-uuctiion of policy ı and of optimal policy, respectively
Var (s,0)
Variance state action a, and step h
Var
Maximum unconditional variance Maximum conditional variance
Var Var max
(s(s,0)
Suboptimality gap
A min
Minimal nonzero suboptimality gap
Zoub
Set of suboptimal actions
Zopt
Set of optimal actions
Table 2: Parameters of MDP
Kh ah rk (s)
k
States, actions, and rewards observed in the k-th episode V/, of the algorithm before the k-th episode Qn of the algorithm before the k-thh episode Estimation of rn (s, a) before the k-th episode Estimation of a (s, a) before the k-th episode Estimation of P. before the k-th episode
(s,
(s)
(s,a)
pk s.ahh ñ (s)
Visitation count at (s, a, h) before the k-th episode
b (s.a) k
Bonus term in the k-th episode
The policy at the k-th episode
Table 3: Values used in the algorithm
A.2 Technical Lemmas
Lemma 1 (Bennett's inequality, Theorem 3 in Maurer and Pontil [2009]). Let X1, X2, Xn be i.id. random variables with values [0, a] > 0) and let > 0. Then,
1 Σ
2V[X, (2/0) log(2/8)
PP B
x
<
n
Lemma (Freedman's inequality, Lemma 10 Zhang et al. [2020]). Let (Xn) be martingale difference sequence (i.e., [[[,]|Fa-1] = 0 for all n > 1, where Fx = oX .2..... ..))))) such that (x,) & a for some > 0 and for all n > Let Va En_ E[X 1 for > 0. Then, for any positive integer n, and any e, 8 0, we huve
Σ x. >
2/ Vv log 1/8) + 2 log 1/8) + 2a log(1/8)
< 2(nna=-1 + 1)6.
21

---

7 A I RAD y IV y 1 clip [a|=]
Set 21,
Set of distribution functions over set B
min(x, y)
max y)
Indicator function of y, i.c. if y is true and otherwise a > =}
Acceptable error probability
(s,
Surplus; Qh a) - Th(8, a) - IE Pa.. [V (s')
E (3,a)
Clipped surplus
log(S AH
wh(8. W Regret F FEA E.
Weights used analysis
160 log(4 1)/6) Var
Total regret
o-field generated by the first
episodes of the algorithm
o-field generated by the first k k- episodes and the first h steps in the k-th episode
Exes: Las L.eS.aeA> respectively Expectation when r is sampled from distribution X
E V
P E
Probability and expectation over trajectory when following policy π Table 4: Other notations
Lemma 3 (Lemma 10 in Zhang et al. [2022]). Let X1, X2... be a sequence of random variables taking values in [0, Define Fk oX1,, X2,...... ...,. Xk-1) and Yv E[Xx [F for k. 1. For any > O, we have that
3
X
Σ
YB (1168/
$
3
Y4
Xx (ln(1
<
Lemma 4 (Lemma F.5 in Simchowitz and Jamieson [2019]). Let X,Y be two random variables defined on the same probability space. Then
V V &
Lemma (Lemma B.5 in Simchowitz and Jamieson [2019]). Let a1, a2. am be sequence of nonnegative reals and > 0. Then,
clip
Σ a
< 2
clip
ag
2m
A.3
Model errors
Our analysis will mostly be based the success of following inequalities. Lemma 6 (Good events). Let log( SAHK/5). With probubility least 1 105, the following inequalities hold for all 8, a, s', s',h,,.. h,,k: k:
2 2
H (s,
a)( (r(),a)
()
(s, 2P 2P..a.h
Lpk (s') ----Paa Pe.) <1
n (8,
B At m [V Bd'ppte
[V+
[V+++((5))) (6')] &
1/tt1
27/a' Pala. V (s')
Hi +
n (s,
(x( a)
22

---

Yo' PE
[ [6 /o (5)] H
2b
ni
(5, a)
2x
v ())(s,)) (f)(s (()(s,))((((ssa)))
Ver'nReaahh [r]] & H
(s, -
Proof. The first three incqualities can be derived from Theorem 1, Theorem 2. The last two inequal- ities are adapted from Theorem 10 in Maurer and Pontil [2009].
Lemma 7. Let V be a function defined S. Conditioned on the success of Lemma
[ [V()) Ed Pr. h. [V(')] & 25B - Ps.a. [V(s)
m&X.ss V(s)
(8,
(s, a)
Proof.
Let M max [[s)]. Then, by Lemma 6,
B P. uin [V(>'] Be' [V6']]
Σ (e (6) Paan(())V((S)
Σ [V(')] (v
2P (PPaan(00) (8,
())
Σ P..a (o))(1))
Σ
2x
+ MS
Yes n (5,,))
n (s,
NES
28t
+ MSc
Ed ~ Parac [V(692].
(s,
(s,
A.4 Variance bounds
Corollary 4. Let be any fixed policy. For any and S, we have
H
Σ
(aw, aw) 8h = H
Proof. Recall that Ed'nPs..h
[V h++1 (s') = (s,
< VV) (x)
-ra(s, a), so
H
Var
8h = an))
H
H
E T
R n M
[r/] +
Σ
o M [V/+ (8') =
h
h-h
H
H
<E
Σ
(rh- rw (sw,
+
(V (SW+11 - (gr and + (sN)) 8h
W-h
H
<
(Phe + V ( - vi((s)))
34 =
23

---

(E)
H Σ Nm-h
<E"
r/v
Via (sn) 5h H??
where Equation (7) is because of independence and that (sw, + (sw)] & 0- Ex Roginii - The (sw, ax:)
PapinPar [V
Lemma 8 (Lemma 42, Zhou al. [2023]). Let be any fixed policy, For any d > 0,
p
Var x (sw,ax) > 160HH log(4(H + 1)/5) = $ 8.
Proof. We have
H
ah))
Σ
Σ
y Pa | [V
W-hh
h'
H
s' ">PPa N ow [V [V)++
Σ
(sw, Tho(sw, aw1)) 2
+ Σ
(sw
M
W=
W=h
-P w [V (5') +1 (1))
(E"
H
+
(sW
rw (s + H²
"
22
2
(1) + 2 H (1/0) 2/1² log(1/8)
(8)
H
+ 2H
Σ
(Vi((w)) (w (sw. ax)) H²
H
<4H
poor-Pa Pan ( (+)))))) (/8) + 5H2 log(1/0) + 2H (sx)
Hf
+ 4H
yo "Ar ( log(1/0) + HH + 4H2 log(1/0) (9)
R h
H
<8/1
2
Σ h-=h
Var (SW, aw) + 15/12 log(1/8),
where Equations (8) and (9) holds with probability 1 1-2(H 1)8 each by Lemma 2. Thus, by solving the quadratic equation,
H
]
Var an) > 160//² log 8n
< 1 4(1 + 1)6.
The proof is finished with rescaling 6.
B MVP Algorithm descrpition
This section provides description of MVP algorithm (Algorithm 1) in detail
'The original version of MVP contains a doubling mechanism to trigger updates of and Q mainly to lower switching cost. Since switching cost is not central to gap gap- nep-dependent analysis, we choose to update Vi. and Qn every episode for simplicity.
24

---

Algorithm Monotonic Value Propagation (MVP)
Require: MDP M (S, R, p), learning episode number K, confidence parameter 6,
universal constants C1, C2, Initialize: For all (s.a.s' h) e A S [H + 1), set (s,sa)) O, 0,,n(s, a')
log( SAHK/ /8).
0, (s, a). (s a), (s) 0.
2: for k 1.2.
do 3: Construct policy x" such that (s) arg max, Qs(s.a).
4: Observe trajectory st at, rt, 82 az r ... &h o r
5: for h H. H 1..... do
6:
(s.a,s") - (5% hh k+1)
7:
Update ny (s, s) -
+ (,nx(s,a) - m)(s,a) 1,0,(s,a) - 0)(3,a) +
Th (ss, 0) - (s, + (rt))
8:
an(s,a) an(saa
(s.a.)
9:
(s(8))) mals,a)
(s.aa
10:
as
(s.aa,)))
(s,a
for
(s, a) E Ao
v ( [V]n) + 22 (0n ((hn(t(())) +
12:
(s, a) - -aV
H mn
mllsaa
(a(s,))v
13:
Qn(s.a) min(fx(s,a) + V/+1 + (s, H]
(s) max, (s)
15: end for
end for
17: end for
C Proof of main theorem
We begin by choosing the universal constants in the algorithm as c1 C2 = 2, = 10.
C.1 Clipping surpluses
Existing analysis MDP already shows that Q and V are upper bounds of 1 and Vi* with high probability as expected:
Lemma 9, With probability at least for all 8, a, h k E S Ax [H] x [K].
(+) > (% a), (s) (s).
Proof. The proof is almost the same Lemma 8 in Zhang al. [2024] with necessary modifications for our constant choices. Since C3 = 10 > cî, the monotonic function can be constructed as
V-- ([(())
4HL
(p.n(v): = : [B>P((((s)
+ max 2V
n
We define clipped surpluses as
Var ,, (s.
1
(s,,, ax)) = clip (s and lesA max
(10)
min H² Var
H
Also, we recursively define
1 = Vt (s) = =0,
(%(s,a) a) (*, a) E (8, a) + R P..PP (Vtt (s) max (1(
for h = H, H 1,... and O V = -
25

---

Lemma 10.
Amin
(s) = (s)
3
Proof. We have (x, > a)
Amin Var (s,a) 6(H Varimax
Amin for any pair of a, h. Thus,
6ff
(s) (s)
=E"
Σ
(sh: : ah)
8/ =
W=h
Amin E
11
H1
Amin
(sh, ah
9h
Var Sh. an) ) 8h
Σ
6 6H22 A Var )ax
6H
1/
Amin
21, (s)
3
where the last line is due to Theorem 4 and definition of Var max*
This lemma links the half-clipped values V with the optimal values Vi.
Lemma 11. Conditioned on success of Lemma 9, for any state 8 and h [H].
3 (s) (s) (V)(()) (s)).
Proof. The first step in the proof is to recursively expand both sides at all states where an optimal action is taken. Specifically, we let
E = [ (sw) = a'', h hh],
and Enu Ei +1 as the set of the trajectories ENi* but not Eams1 (that is, those trajectories where the first suboptimal action after the h-step is at the (h* + 1)-th step). Since trajectories are sampled with policy =² &n is the set of all trajectories with 8p = 8.
We hope to claim that
**
(x) - (1((s) = Σ E Ew V/ (SH)))sR = s]
(11)
W-h+1
+ B [1|E I( (V%)
v | 8]
(12)
and
** ())(s) -/ >
Σ
E" [1[EN-1 Ex |x Vi (ss) s]
(13)
+++
[1{E, (V (V (1
(s I s].
(14)
These claims are proved by induction on ho and expanding the last term event +1 For Equation (11), we have
(sn*) - V (s**)
= 2 (she, tt (sn*) - Q (S Tht (s**))
= Pe.T,
[V. h [ (s') - V (s')
when the trajectory is in +1 and for Equation (13), we have
V (s) ViT" (s) Qi (s. M (s)) Q (s, Th. (s))
s'-P (o) [ [ (5')
Et (s, a) + EE"
26

---

[1 - Vi (s')].
We will use Equation (11) and Equation (13) when h** H. In this case, the last lines are both zero, so it suffices show that
3 2 (VW) VW (sw)) ((N(s)) VØ (sw)
on Ehr-1 - Eny In fact, since the trajectory is sampled from n", and since aN is suboptimal, we have that
Amin = Qh aN) Amin
> (sw) Aw(sne, aw)
(sw) > V (Sw)
v
(s(s),
3
3
3
3
where the last inequality is because (s and = VN (sw) (Sr & V/2 (shr).
Lemma 12. Conditioned on success of Lemma 9, if = T then
a)) & Σ
E (
Lemma 13. Conditioned on success of Lemma 9,
3
VØ
0
Σ
E
(sn,
2
h-1
Proof. We prove Lemmas 12 and 13 together. By recursively applying
V/) = (s, (s)) + E R0. ( V (s),,
have
# (5) - (s)
R=* (F), = =] Σ
Then we use Lemma and
An(s, a) 1/7 (s) (s) & Vi( (*),,, Vi* Vo - (V7+t))) V (81)].
for Lemmas 12 and 13, respectively.
C.2 Estimating Surpluses
Lemma 14. Conditioned on success of Lemma 6,
2 ()) & Pt. Ph [(Vit1(5')= - Vie (s))) 3/
(ar 20H
(
Proof. Recall that our choice of bonus in the algorithm is
yos Pha. (V)t + 2/
(o (F n)
10HL (s.
(s, = 21/
()
Since the last term is at least H if n (8, 1, it suffices to consider (8, > 2. The first term can be bounded using
V v's' [V [s']] = (Vyerne ain [v') yoon siom [V+t+
+ +VVys--fhan [Vtt - / sad [Ve [V / [ (s/)
27

---

< SV (+))
V (
HN
2x n
(5,00) 0) -1 + V
(ys'-Pa a.. -a 1
by Lemmas 4 and 6, so
W aia [V)+1(5']]
(8)
18 Pk 1(1++( Vittt (5)))]
2Hr
We' P.
[V h+ (s)
+
(s,
(s)
(s,0)
Es Ex'-Pha.t
[[V
(5))
Voln A. [V h+1 (s)]l
3H
(8)
(s.
The second term of (s, a) can easily be bounded by Lemma 6 as
(0) (s))))))
Wy'' R [ri]l 2H
())
(s,
n
Thus
2 a)) & 2 BBd-Phan no [ [(V)++165') - (s')))+ -2
( 20H
H
(
(s,a)
Lemma 15. Conditioned on success of Lemma 6,
- V & E*
Σ H A 22H
St
8h =
(sw,
Proof. We begin by decomposing (s') - (s') as follows:
(s) (s) < Vi - Of (s)
=))(s,a) + b, + P V.b (s)) Th (s, - "gd'PP.a. -ee'PP.e 1
(1)((s,0)-((6 a)) + [ - Ps 1 (8') Vi"= - E [V (6') - (=)))
+ (EE'>P....h / E - Pea.h (5')) + Pa.'aP....n [V+ (5') [s')] + (3) a).
By Lemmas and (with V V v and definition of byj (/((s,))) a), we conclude
22r [r/]
Hi
(s) (s) < B P [++ (5') - V.L (
(V
+
()
n (8,
2SE P... [[V (s')
V (5))){
SHi (s,
(s,a))
27/5'~ m... [V [ (8/)2]
Hi.
+
n// (8,
n)((sa)) a)
vor-Pu mm (8))
(ot(s, a) (P)(s,)))3))
10Hr
+ 21
+ +2
(s,
()
n((s,a)
St.
13SH
[V/t (5') - Vse 1 +3v2+++32++++ 4)H,
+
()(
28

---

If St & (s, a) then we have
St
(s) (s) & Es'-Pan (
(V2+1
1 + H 22H
(15)
(5
If St n (s, a), then Equation (15) also holds since (s) -V (s) & H. Thus, recursively apply Equation (15) and conclude
H H A 22H
St n (sWr an)
(s) (s) & Ex
8h =
Lemma 16. Conditioned on success of Lemma 6, i (8) then
Var (s, a)l
1500SH (5N, ax)
()) & H H
ET
Σ Wー
3H
(8h. (8)
" (8,
Proof. Similar to the proof of Lemma 15,
(s. ()) a) - Es' & (s')]
h41
(8, a) + (s) + Be' (8') rn(s, B Pr.a V (8')
(8')
(s, (s, a) + | PasnPannn V h+1 (5') - Vitti(s']] E -Po 1i
11 (htz - V/+ (s)]]
+ - (s') EE' V (s') + by (s.
We will apply Lemmas 6, 7 and 14 to bound each term. So
2v H a
(s,
())
SHc
+
Ed Pa ( - (itta(s))
(s)
24 (ys's
Hi
a)
()
2 ppd-Pt
2V a)e 20Hc
+ E sich [(V (V (s)))
H1
(s,
(s)
By Lemma (with V= -V-6
/+1 )2++1) again,
B B a... ((') - 1 (8)) pp'-Pa... [(V] (8) - (
(s')
2SB* PP.c. [(V h+ (8)) V (8)))
SH²,
n/ (s,
n
2H2 Prach [VV h+1 (s') - (s))2]c
S112
(s,aa) a)
n (s.
2SH²,
$ E
((V) Vi+t1(55)) (61))
()(88a)
By Lemma 15,
(V'r Vi & x
(
Σ
S1
2
H A 22H
8h+1 =
T2 (sw aw)
W=++1
29

---

H
500SH T (sw,
H
8h41
1h-h+1
Hence,
Var (s,
3 R E o, ((V)+
27SH
08, & (2+ (2++2v2)
+
V/+ (8)) ( a)
nh (8,0) a)
H
V (s) (s, +
H
1500SH12
E=*
Σ
3H²
(sh; = (8,
k (sW, aw)
The extra "H ^ part is because (s, a) & H by definition.
C.3
Concentration of visitation count
This lemma shows that the sum of visiting probabilities is bounded by n Lemma 17. With probability least 1 6.
Σ E [[I - (s,a))[Ful & (n, a) +
for all s, a, h, k, where Fk is the o-field generated by the first k episodes.
Proof. This a direct consequence Lemma
The next lemma considers a weighted sum over visiting probabilities.
Lemma 18.
With probability at least 1 25,
ΣΣ wn (
a EEL a (FFe))[Feed) & 9W
+ 4HW,,
F-IW-1
for all h, k, where we recall the definition
a)(s,a) a) = Vari a), W min (in(160/12 log(4K + 1)/0), Var
and FR, is the o-field generated by the first (k- 1) episodes and the first h steps of the k-th episode.
Proof. By Lemma 3 and wn (s) a W.
Σ Σ wp wn ON and = (8, (s) < Σ Σ ( a ( an) (8, (s,
--11-1
for all 8, a, h k. Then, we will bound Σ Σn w a ( an) = (s, a)} in two differ- ent ways for each term in W.
First, we apply Lemma again with respect to only the sum over k' with (o at = (s, a). This shows
( a (1((H of = (s. & 3Vr max (5. + H i
#=1h=1
Second, by Lemma 8, with probability 1-8
wn N.
( a 1 oi' = (s, < 160 (K(( + 1)/6)1 o = (s.
30

---

for all K' = =1,2, K. Thus,
wh wn(s ((0
ax) - (8,a)) & logHH + 1)/8)n((8,0) a).
Hence we conclude
wh wn( B[) a = (s & (Wn(((s
+ 4HW.
Lemma 19. Lel I be non-increasing nonnegative function defined [1,+00) with f(1) & M. Conditioned on success event of Lemma 17. we have
m f(z)dx.
Σ (( (s, Fx. M(1 (((++3) +3
Proof. Let n/g - P((s) a = (s. & 3n (s) and
Ko minfk: n 2 + 3).
(If n'x <1+3 3 then we define Ko K.) Then,
K
(s a = (s, a))
Ka
K
Σ (s, P((s) att - (F +
Σ ())(ss (8, [F
k-Ko+1
Ko
<M
>
P[( a (s, +
Σ
f((nk - ()/ r/p-1)
k=1
k=
<Muk,
1((x - 1)/3)dz
Ko+ w
n'k
f((x f((x-1)/3)dr & (((+3) f"k f((x -))3 (3
<M(++3)
Jn'oo
J43
pn (o,a)
f(x)dx & M(e +3) + +))++3)+ +3
f(z)da.
Lemma 20. Let be non-increasing nonnegative function defined on [0, +00) with upper bound M. Conditioned on success event of Lemma 18, we have
K
h
p (s.a)
Σ f(n a)) Σ (n a P(ss,, a (s. (W(4HL+9)
f(x)dx.
The proof is similar to that of Lemma 19.
C.4 Final calculations
Our calculations conditioned success of Lemmas 6, 9, 17 and 18, and they happen simultane- ously with probability at least - 205.
We begin by analyzing the clipped surplus. By Lemmas 5 and 16, we have E (s, a)
31

---

Var a),
Amin (s, a)
<2clip
H A /
n (s,
24(H2 A Var
H Σ W=
1500S
A Ami
+ 2clip
E"
3H
(shr an) = (s,
(s aw)
24H12
(5r ,')e
Amin Var ( (s',a') 24(H2 a Var
22 Σ
11(5' = (8, a) clip
H A N
d'aa'
cclpp
Σ Σ ΣΣ
E**
(3112^
1500SH14 (
1 1((5 aw) (6', (5', (sn, (sh) (s,
Amin 24
L' n-h
1((,'aa))
(s, ((,
H
clip ( [3H², 1500SHP'
Ex* [1{(s,,aN) (8, (s,,))](s, an) = (8,a)]
A min 488 AH3
+
(s,a)
8/al 1==h
22
1((s'aa') = (s,,
E= [1{(s,a) (sx (w))) an) (s, [s.a)]clip 3H² 1500S A min
4
n (8.a) a)
485
8,0' 1/=h
22 Σ 11 a') (s, a)) (s..
8,0'
p=* [(5 = (s ( an) (s.
2/00
where
Var a)e
A Amin Var+ (8, 24(H² Var
1500SH2
Amin
fx(8,0;z) - clip a BN
.g(x) - clip 3H²
22
48SAH3
C.4.1 Bounding regret
By Lemma 13, have
Regret (K)
3 E= [B))
3 K =
Σ Σ BLE
2 k= A=1
k=14=1
E (l(s, = (oh.
1= 1
K
E
P [(s,a) (sw, on a (sh, an) (s ((nh, a))
K
fh(8, a; nn a))P[((, -s at) [i
2.0 h
+ ΣΣΣΣ
glnk (s. () (
8.0 -
We will use Lemma 19 to bound the two sums.
For the first sum, we have then
K
o (e.0)
Σ fa(s, a: ()))((())) = (s/, aBl < H(l+ 3) +
32

---

When an(s,)) > O, we bound the integration by
m (v.0)
(s,a)
Var * (s, a)
Amin y
a; a))dr =
clip
5
dx
24 Var
m (x,a)
Var a) dx 1 Var ()) (8,
$1/
30
When an(s,a)
O, we bound by
m (v,0)
mf (s,a)
Var A (s, a)u
Amin (s,
fals, a))do
clip
5V
dx
24 24(H2 (H2
Var
+00
V8 a) clip
Amin Var % (s, a)
5V
dr
x
24(H² a Var max)
(120(H Var Var 1 Var (s,a)
(s. a).
51
dr
J0
1200 H2
Var max
Amin
For the second sum, we bound similarly that
Σ
g(nk (8, a))
[(+,a)
(shr, ak.)
F=h
m
(e,0)
1500S
A Amin
<3H (1 + +3
clip
dr
48SAH3
720005 i/Amin
1500S
<3/1 + +3
dr
=3H [1+ 3) log((70005* AH 1/ 1/4 Amaa).
Thus,
3600 (H²
Var maax )
Regret(K) E3
Σ
(4H++ 101++30,
+3
Σ
4HL +
min
(e.
(e,o,
4 4 45005FFF: AH* (/Amm)))
(H2 Var
$00
Σ
(s, 10800
Σ
Amin
2ep
277005 AH log' AH Amaa) + 965AH
(16)
C.4.2 Lower-bounding visitation count
Recall the lower bound in Lemma 12. We begin by taking a weighted sum over all states visited during the algorithm:
( a An
Σ
wh (n at)
Σ
(
o [Fan
1-
Wi (, ah
Σ Σ
E [I((s, (s
a))
W-h 3.a
wh (st af
ΣΣΣ
E
pa [(s,
(S**, (0)*,a)*](33.. ax) ato) g(n (s, Fx.
N
33

---

H K
N¹
Σ
fn(s,a; (s,
Σ
wh(s% P [(s,a) = (sh az Fk.
9.0 R k=1
h-1
1*
A
Σ
g( ())
Σ
Σ
wh (()) = (s/ ait Fr,nl
A
H
3
an (s)
Σ
wh P [(s.a) (sh a [k
5,
6H Σ
Σ
Σ g(n (s, a))
Σ w/ (s a P(),s = (s/== ax Fr
8,0 A
Take up (8, Var (8, a), follows from Lemma 20 that
ΣΣ
wn (s.
Σ
wn (sh a²) An at)
(s.a)
(
8:0
m
K (s.a)
+ 6H Σ Σ W (4H +
Sh* (n
8,0 h
2351 + 270W
Σ
Var a)nk (s,
(e Lub
32400 oope WWH
Var marm
+
810000 AH
A (17)
Amin
For notational simplicity, denote
Ro
Σ
V (s)
By Equation (17) and Cauchy-Schwarz Schwarz inequality,
351SAH 2700 + 32400 Zopt (H2 A Var
W
+ A logg700000 A Amin)
Amin
Σ
> RM
An(s,
(eeu,
It follows by solving the quadratic equation that
540WL
120 AHS 120
(H² Var
Ro
Σ
+3005 A AH 1/Amiu).
An(s,a)
Amin
From Equation (16).
(H² A Varman)) 270005 & Aoo'7000000 AH 4/Aml))
R)) & 90Rg + 96SAH* + 10800
Σ
Amin
Zopt
48600W, A)(s,)
21600] /ope/ (H2
Var )
+
+ 2700005 AH A Ami)) + 2765 A
Amia
(s,a, Banb with probability at least 206, as we have claimed in the main text.
Thus we have proved the following main theorem.
34

---

Theorem (Formal statement of Theorem 2). Suppose we run MVP algorithm with universal con- stants C1 C2 C3 10. For any MDP instance M satisfying Assumption and any confidence
parameter > 0, any episode number K = 1, with probability at least 1 206
1122
A Var max log( SAHK/O)
Regret
Σ
(s(5,a)
()
+ Zopt (H² A Var log (SAHK/6)
Amin
+ 52 AH (SAHS/AHHH log(S (og(SAHH/0)
+ SAH log SAHK/0)
D Regret Lower Bound
Theorem (Formal statement of Theorem 3). For given configuration of S, A, H. target condi- tional variance L E [1. J. as well as set of suboptimality gaps A {A1, A2.... ASAH), we make the following mild assumptions:
Let I (i { O}. Assume that [I] SH, i.e., the suboptimality gaps are realizable.
Assume that A; < for all 1 ii< SAH.
For any algorithm πI there exists an MDP instance M satisfying:
It has |S]
states and A actions.
There exists S = S such that |S| S, and a bijection between [H] x S Annd [SAH]. satisfying An (8, a) Ahh,,, for any (h, a) E [H] Sx A.
Var = (LL), while Var & O().
such that
Jim ET [Rerett M K)] Ω
Σ :A
L
log K
A,
Proof. First consider multi-armed bandit lower bound given a set of gaps A A2.... A and a target variance L. WLOG, assume A; & Ai+1. Construct Bernoulli outcomes for each action ag: w.p. Ps = A(a.)
4vL E [ 2.1 get reward VL; w.p. Pt, get reward O. Then 4v/." and Q(a)) ((a:) A(as)
Q(a.) Pi invoke standard lower bound [Lai and Robbins, 1985] with reward outcomes [o, 1]. We first scale the rewards in example by -T. For any algorithm π, there exists permutation the gaps (into
A(a))
4VT. Then Var(a)) p.(1 p.) O(T)) We
such that
VL
Reegrtt
VT A K)]
((ai) - ((a))
Var Var(a:)
lim K
UΩ
Σ
log K
kl(p;, 1)
:A: ((a1) Q(a;)
Av/VL
where kl(p, 9) = plog P + (1 p) log 1 (i) is by
x(|ا) >े r log (2x) + (1 (1-x) log(2 2x) for
E [0, 1] (we take
p.). To see this, we substitute
( - 2r E 1-1, 11. then
( x)
6²
2 1
xx1 - x)) (1-1) +t)
and
1-t
log(1 -t)+ 1+1
log (+t) -((1
1(1 + t) +2
r :log(22)) (1 (1-x) 1og(2-22 2x)
2
2
35

---

Scaling back, we have
B[Regret A", K)]
VL Regrot( A", K]]
I
lim R -000
lim -000
vT
2
Σ
s(ai)
log K
log K
FA,50
Then, we construct the MDP as:
States:
in total S + 2 states. 8o as a main state, 81, $2, ,g as bandit states, 8-1 as
terminal state.
so does require decision- making: P = LH. (sn LSH for & i & 8, is bandit problem, and directly transits into 8-1: (s.an(8-1) for < < S. s is self-absorbing: (a, 1.
Transition:
Rewards: for so and 8-1. all rewards O. Rewards for (s,, a, h) are decided by the construction below.
Assign A into H x S groups, each with exactly A items: (An.s (M.))(H]]((]] and from the as- sumption we guarantee at least one 0 gap in each group. We have da(s:) = LSH (1 LH ) LLSH LSH for 1 < & S. For each (h, 2) [H] [S]. from Lemma 1, with probability least 2HS
(8.) (8:)
(s)( d, (8:)) log(45H)
log (4SH)
$
K
K
K
2K
(s) NK (s.)
log( log(4SH) (4SH) log( 4SH).
LSH
When K > 2c (1 + VI+O log( 4SH), we have RHS & 2LLS so we have (s;) >> (di
K
Denote the event & = (N (s:) > 25L.S (h, [M] [S]], then
20f.5ff
201.S1
P[ε] >
2'
Since we set independent random instances for each (h, st), we have that
Reggrt A h.e.
AT.e. т. K)]
[[E]e[Regret( A
K
+ (1 (1)
lim
lim
h,
BeLSH
00
log K
log K
E[Regret A R
K
hesp 2LSH
lim K-x
log( 22LSH
L
Ω
A (n.
a::h.,, (a)=0
where (i) is by P[E] > and taking K > (2eLSH)² 2. So
E (Regret(M π K)]
E. Regrett A h.e, n,, K)]
lim
lim
K -
log K
K 02
log K
h,
E[Regret A h. π,, K)]
lim
K=
log K
3 Ω
Σ
L
Ansolo (a)
(b.i,a):An,,, (a)=0
Ω
Σ
A
AA,50
36

---

We have Var = @((1 LH LH L) O h), (s = 0, and (ar) = ( Is easy to verify that Var max is taken at states (h, 8;), so
h-1
Var = max (ar
Σ
Var (50) O(L).
max
h,3
However,
Var max
Σ h-1
ds(k))Var((so) +
d (8, (sr & <0(),
showcasing the separation between Var max and Varmax.
37


Reviews:
[{"review_id": "vMy8NnmJbF", "reviewer": "Reviewer_unm4", "summary": "The authors introduce the notion of conditional total variance into a new instance dependent (bounds depend on the gap of the MDPand total conditional variance quantity) performance bounds of the MVP algorithm of Zhang et al 2024. The paper also has a matching lower bound, which is the first in this style of performance bounds.", "questions": "Can the authors comment if there are other lower instance dependent lower bounds which may not be \"variance-aware\" ? How does their lower bounds compare with those? \n\nDo the authors make any changes to MVP algorithm ? or one should consider this paper as proving properties for the MVP algorithm?", "limitations": "lack of empirical validation, potentially limited impact", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "S:\n1)The paper is extremely well written and easy to follow. Clarity and organization is very good.\n2)The lower bounds are a definitely an exciting addition to the literature.\n3)The proof techniques seem novel to me.\n\nW:\n1)A detailed discussion about the significance of conditional variance is needed. e.g., what are some cases where conditional variance is significantly small? (better still , small experiments to depict this intuition)\n2) Why is this a tighter or more appropriate notion than unconditional total variance (Def 1). \n3) How does the MVP algorithm behave with small \\Delta_min.", "was_revised": true, "final_justification": "I retain my score.\nI was satisfied with the author's rebuttal. While this paper presents theoretical results that may be of value, their impact may be somewhat limited due to the limited empirical guarantees.", "rebuttal": "> A detailed discussion about the significance of conditional variance is needed. e.g., what are some cases where conditional variance is significantly small? (better still , small experiments to depict this intuition)\n\n> Why is this a tighter or more appropriate notion than unconditional total variance (Def 1).\n\nThank you for raising this point about the distinction between conditional and unconditional variance. In Appendix C, we construct an MDP instance that matches our lower bound, where the unconditional variance is significantly smaller than the conditional variance. This demonstrates that the unconditional variance fails to capture the complexity relevant to gap-dependent regret, making it inadequate for deriving tight lower bounds in such settings. We will clarify this distinction more explicitly in the camera-ready version, should the paper be accepted.\n\nThat said, empirical investigation of MVP is not straightforward. Currently, we lack conclusive evidence that changes in performance can be attributed specifically to differences in (un)conditional variance, as other factors—such as suboptimality gaps or constant scaling—may dominate. As a result, designing meaningful experiments to illustrate this point remains an open challenge.\n\n> How does the MVP algorithm behave with small \\Delta_min.\n\nWe suspect you are referring to the second term $\\sum_{\\Delta_h(s,a)=0}\\frac{H^2\\wedge \\texttt V\\texttt a\\texttt r_c^*}{\\Delta_\\min}$ in our bound. While this term does not appear in our lower bound, Simchowitz et al. (2021) established that a regret term of order $\\frac{S}{\\Delta_{\\min}}$ is unavoidable for any optimistic algorithm. Our $\\Delta_{\\min}$-dependent term reflects this intrinsic limitation. For a more in-depth discussion, we refer you to the aforementioned work.\n\n> Can the authors comment if there are other lower instance dependent lower bounds which may not be \"variance-aware\" ? How does their lower bounds compare with those?\n\nTo the best of our knowledge, there are no other instance-dependent lower bounds that incorporate both suboptimality gaps and variance information. However, there are bounds that focus solely on the suboptimality gaps. As mentioned earlier, Simchowitz et al. derive a lower bound of $O(\\sum_{\\Delta_h(s,a)>0} \\frac{1}{\\Delta_h(s,a)} + \\frac{S}{\\Delta_{\\min}})$ for optimistic algorithms. Xu et al. later generalized this bound to cover all algorithms when $S$ is logarithmically small. Our work extends this line of research by introducing conditional variance as an additional key factor.\n\n> Do the authors make any changes to MVP algorithm ? or one should consider this paper as proving properties for the MVP algorithm?\n\nThe MVP algorithm analyzed in our paper is a slightly modified version of the original algorithm proposed by Zhang et al., which includes a doubling update trick. We believe this trick is intended to reduce update costs in the minimax setting and is not essential for the gap-dependent analysis considered here. Therefore, we omit it in our version. Relevant discussion can be found in the footnote on page 6."}, {"review_id": "ij3jHAP5qa", "reviewer": "Reviewer_RgUt", "summary": "This paper presents a new theoretical analysis of the Monotonic Value Propagation (MVP) algorithm, establishing the first variance-aware, gap-dependent regret bound using a newly introduced metric: the maximum conditional total variance. The analysis achieves a state-of-the-art worst-case horizon dependence of H^2 in the regret bound, improving over prior work. The authors also prove a matching lower bound, showing that no algorithm can significantly outperform MVP in this setting. Key technical contributions include a novel reweighting analysis of suboptimal gaps and a refined clipping strategy for optimal actions.", "questions": "- The favorable bounds of the MVP algorithm shown in this work is very interesting, however, does this tight bound mean the MVP algorithm is very close to an optimal algorithm? Do you think we should still try to develop newer RL algorithms, or just focus on adapting existing ones into practical problems? \n- Is there any empirical evidence showing that MVP works much better than alternative RL algorithms? (perhaps even in some special MDPs)\n- How easily will the analysis made in the paper be extended to other more general MDP settings? \n- Does these theoretical results bring insight on how to better adapt MVP (or similar model-based algorithms)  to settings with function approximation or large state spaces?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n**Quality**\n- Overall, the paper is very well written. \n- The arguments are supported by cleanly organized proofs.\n\n**Clarity**\n- The paper is written clearly, terms and concepts are clearly explained or defined. \n- Concepts such as suboptimality gaps, conditional variance, and the role of the MVP algorithm are well-motivated and easy to follow for readers with background in RL theory.\n\n**Significance**\n- The paper studies the important question of \"What is the tightest problem-dependent regret while considering both variance and gap?\". Obtaining such a bound can be helpful for the further adaptation of new and potentially better RL algorithms such as MVP. \n- The theoretical results are very interesting, providing a tight bound on MVP can be a significant result\n- The tight lower bound further strengthens the impact by showing near-optimality.\n- The new techniques discussed in the paper can be useful for other theoretical works. \n\n\n**Originality**\n- The theoretical results are new, the new techniques that are used to prove the results are also novel\n\nWeaknesses\n\n**Significance**\n- While the theoretical results are impressive, the paper does not include any empirical evaluation, whether on small toy problems or other more complex settings. It is unclear how these theoretical improvements translate to practical reinforcement learning problems. But I understand the main goal of this paper is to provide theoretical contributions.", "was_revised": true, "final_justification": "The authors have answered my questions in the rebuttal. I believe further empirical results and analysis in the function approximator settings will enhance the paper even more, but I understand that these results are non-trivial and are important future directions. \n\nGiven the significant theoretical contribution already presented in this paper, I keep my final score as 5 (accept).", "rebuttal": "> The favorable bounds of the MVP algorithm shown in this work is very interesting, however, does this tight bound mean the MVP algorithm is very close to an optimal algorithm? Do you think we should still try to develop newer RL algorithms, or just focus on adapting existing ones into practical problems?\n\nWe believe there is still significant room for developing new RL algorithms. A result by Simchowitz et al. shows that a regret term of order $S/\\Delta_{\\min}$ is unavoidable for any optimistic algorithm—this limitation is reflected in the second term of our regret bound. In contrast, Xu et al. propose the AMB algorithm, which reduces this term to $|\\mathcal Z_{\\mathrm{mul}}|/\\Delta_{\\min}$ in a variance-independent setting, where $|\\mathcal{Z}_{\\mathrm{mul}}|$ is a more refined structural quantity (equal to zero when every state has a unique optimal action). This comparison suggests that there may be unexplored algorithmic directions that combine the variance-awareness of MVP with the structural adaptivity of AMB. Hence, we are optimistic about future algorithmic advances beyond MVP.\n\n> Is there any empirical evidence showing that MVP works much better than alternative RL algorithms? (perhaps even in some special MDPs)\n\nEmpirical comparisons between MVP and other RL algorithms are nontrivial, especially in finite-horizon tabular MDPs. The performance is often sensitive to constant factors and logarithmic terms, which makes isolating the impact of the theoretical improvements quite difficult. At this stage, we do not have conclusive empirical results supporting a performance advantage for MVP. A rigorous experimental study, particularly on carefully designed MDPs that highlight the role of variance, is an important direction for future work.\n\n> How easily will the analysis made in the paper be extended to other more general MDP settings?\n\nWe believe the techniques in our analysis can be extended to other gap-dependent settings without significant difficulty. The key challenge typically lies in identifying appropriate weighting schemes that lead to tight bounds. Once those are identified, our framework for incorporating conditional variance could likely be reused or adapted with modest effort.\n\n> Does these theoretical results bring insight on how to better adapt MVP (or similar model-based algorithms) to settings with function approximation or large state spaces?\n\nTo our knowledge, there has not yet been an attempt to generalize the analysis of MVP—or other similar model-based algorithms—to the function approximation setting. We view this as an important and open problem. While our theoretical results provide some insight into how variance affects regret in the tabular case, extending these insights to large or continuous state spaces will likely require new techniques. We consider this a promising avenue for future research."}, {"review_id": "iqHvx39jqO", "reviewer": "Reviewer_gPCR", "summary": "The paper addresses regret bounds of tabular MDPs. They focus on providing gap-dependent regret bounds that are also variance-aware. They study the dependence of regret on the maximum conditional total variance (conditioned on the states) instead of the maximum unconditional total variance studied in existing literature. They show that the existing Monotonic Value Propagation (MVP) algorithm enjoys improved regret bounds. A lower bound on the gap-dependent regret is also provided.", "questions": "- Why did the authors choose to present only the informal version of the regret bound in the main paper and leave the formal theorem to the appendix? The formal version of the lower bound is particularly different than the informal version presented in Theorem 3. I strongly recommend including the complete technical theorem in the main paper. \n\n- While the upper bound proof of the regret is well written, it was challenging to follow the presentation of the lower bound, due to the following reasons. \n\n1. A lot of details (including assumptions) are missing from the informal version of the lower bound theorem (Theorem 3).  \n\n2. Instead of giving a summarized, intuitive idea of the proof in the proof sketch, a simplified instance is discussed, which does not give much insight into how the instance can be generalized. \n\n3. Even though I am well aware of the multi-armed bandits lower bound proof (Lai & Robbins, 1985) utilized in appendix C, it was difficult to see how to it utilized to get a lower bound here, I request authors to expand and provide more detailed and easy to follow proof of the lower bound in the appendix.\n\n\n- The abstract includes the mathematical expression for regret bounds. Mathematical expressions are not displayed properly when the abstract is shown outside the PDFs (for e.g., openreview website). Hence, the authors might want to consider rewriting the abstract with fewer (or none) mathematical expressions to improve readability. \n\n- As evident in the questions, my primary concern with the paper is with the writing of Section 5 and the corresponding Appendix C; the score given currently is a reflection of that.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- The paper studies the dependence of regret on the maximum conditional total variance instead of the maximum unconditional total variance studied in existing literature, and shows how it allows a better regret bound for an existing algorithm (Monotonic Value Propagation). \n- The introduction of the conditional variance allows improvement in dependence on $H$.\n- The techniques used in this paper can be used to improve regret bounds in a variety of RL settings. \n\n\n**Weaknesses**\n- The clarity and structure of the paper can be improved. The paper only includes an informal version of theorems (upper bound and lower bound theorems. This is acceptable if the primary contribution of a paper is algorithmic or experimental. The primary contributions of this paper are regret bounds (upper / lower bounds), so it would be a better idea to include complete formal theorems in the paper. If space is a concern, authors can move the MVP algorithm to the appendix, as the algorithm is not a contribution of this work.", "was_revised": true, "final_justification": "The authors have addressed my questions adequately. I have updated my score accordingly. The overall consensus of the reviewer is positive, and I expect the authors to incorporate all the changes discussed during the rebuttal phase.", "rebuttal": "> Why did the authors choose to present only the informal version of the regret bound in the main paper and leave the formal theorem to the appendix? The formal version of the lower bound is particularly different than the informal version presented in Theorem 3. I strongly recommend including the complete technical theorem in the main paper. \n\n> The abstract includes the mathematical expression for regret bounds. Mathematical expressions are not displayed properly when the abstract is shown outside the PDFs (for e.g., openreview website). Hence, the authors might want to consider rewriting the abstract with fewer (or none) mathematical expressions to improve readability. \n\nWe would like to thank the reviewer for their helpful suggestions regarding the presentation of our main theorem and the rendering of the abstract. These issues will be addressed in the camera-ready version, should the paper be accepted.\n\n> While the upper bound proof of the regret is well written, it was challenging to follow the presentation of the lower bound, due to the following reasons.\n\nWe apologize for any confusion caused by the proof of the lower bound. We are happy to clarify any specific concerns. If any part of the proof remains unclear, please indicate the exact step or argument that you find troubling, and we will provide a detailed explanation.\n\n>> A lot of details (including assumptions) are missing from the informal version of the lower bound theorem (Theorem 3). \n\nWe chose to present an informal statement of the lower-bound theorem in the main text to balance precision and clarity. The formal version, which includes all technical details and assumptions, is available in the Appendix for interested readers.\n\n>> Instead of giving a summarized, intuitive idea of the proof in the proof sketch, a simplified instance is discussed, which does not give much insight into how the instance can be generalized. \n\nThe example in the proof sketch captures the key behavior of the MDP used in the formal lower-bound proof: the agent starts in the main state $\\texttt A$, transitions once with high probability to an action state $\\texttt B$, and then makes a decision. This structure generalizes to arbitrary $S,A,H$ by introducing more action states, as detailed in the Appendix.\n\n>> Even though I am well aware of the multi-armed bandits lower bound proof (Lai & Robbins, 1985) utilized in appendix C, it was difficult to see how to it utilized to get a lower bound here, I request authors to expand and provide more detailed and easy to follow proof of the lower bound in the appendix.\n\nFinally, the lower bound for multi-armed bandits is used to bound the regret incurred in each action state. Summing these contributions yields a valid lower bound for the regret in the MDP setting."}, {"review_id": "o5i5z5gnCd", "reviewer": "Reviewer_hoFY", "summary": "This paper investigates gap-dependent regret bounds for tabular episodic Markov Decision Processes (MDPs).\n\nThe authors demonstrate that the previously proposed MVP algorithm can attain a variance-aware, gap-dependent regret bound.\n\nThey also establish a matching lower bound, highlighting the tightness and complementarity of both the upper and lower bounds.\n\nThe proofs use a novel analytical approach.", "questions": "In the abstract, should the definition of delta_min be restricted to (h,s,a) that delta_h(s,a) > 0 as is discussed in more detail later in the part of the paper?\n\nIn Definition 2, the summation starts from h'=1 and it is conditioned on a potentially later step s_h, which feels somewhat unconventional. Could you provide some intuition on why this formulation is important and how it plays a role in the regret bound?\n\nIn line 181, should the reference be to Definition 2?\n\nI’m particularly interested in the gap between the upper and lower bounds presented in the paper. Line 261 refers to Appendix H for further discussion, but I couldn’t locate it in the supplementary material. Could you provide clarification or additional insights on this point?", "limitations": "not needed", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "This paper effectively identifies an important gap in the RL literature: achieving the tightest problem-dependent regret bounds while accounting for both variance and gap.\n\nThe concept of maximum conditional total variance is novel to me.\n\nThe writing is clear and accessible, making the main contributions easy to understand. The related work section provides a well-structured comparison with prior approaches, helping readers contextualize the significance of the results.\n\nNew notations and concepts are introduced in a clear and organized manner. The overall structure of the paper (such as including a proof highlights section in the main text, as well as dedicated sections for notation and technical lemmas in the appendix) greatly enhances readability.\n\nOne limitation is that the MVP algorithm is restricted to tabular MDPs. It would be exciting to see future work that extends these ideas to more general settings beyond the tabular case.", "was_revised": true, "final_justification": "It seems that there is no major questions regarding the work, and this work makes a great contribution.\n\nI find the rebuttal satisfactory and will keep my score.", "rebuttal": "> In the abstract, should the definition of delta_min be restricted to (h,s,a) that delta_h(s,a) > 0 as is discussed in more detail later in the part of the paper?\n\n> In line 181, should the reference be to Definition 2?\n\n> I’m particularly interested in the gap between the upper and lower bounds presented in the paper. Line 261 refers to Appendix H for further discussion, but I couldn’t locate it in the supplementary material. Could you provide clarification or additional insights on this point?\n\nWe thank the reviewer for identifying these typographical and referencing issues. We will correct them in the camera-ready version, should the paper be accepted. Specifically:\n\n- In the abstract, the definition of $\\Delta_{\\min}$ is indeed intended to apply only to $(s,a,h)$ tuples with $\\Delta_h(s,a) > 0$, consistent with the more detailed discussion later in the paper.\n\n- The citation on line 181 should refer to Definition 2, not Definition 1.\n\n- The reference on line 261 should point to Appendix C, not Appendix H. Appendix C contains the formal proof of Theorem 3 and elaborates on the gap between the upper and lower bounds.\n\n> In Definition 2, the summation starts from h'=1 and it is conditioned on a potentially later step s_h, which feels somewhat unconventional. Could you provide some intuition on why this formulation is important and how it plays a role in the regret bound?\n\nWe agree that the formulation of conditional total variance in Definition 2 may appear unconventional, as it conditions on a future state $s_h$, which breaks the usual Markov structure. However, this definition is crucial to our analysis.\n\nThe summation from $h'=1$ to $h$ quantifies the variance accumulated before reaching the state-action pair $(s,a,h)$. The conditioning on $s_h$ reflects that this quantity is only meaningful along trajectories that actually visit $(s,h)$. This captures the following phenomenon: to obtain sufficiently accurate estimates at $(s,a,h)$ and avoid regret from under-sampling, the agent may need to visit earlier states more frequently than would be necessary. This additional sampling effort is encoded in the conditional variance, making it central to understanding and bounding the regret."}]

Author rebuttal:

Meta-review: This work derives a tighter instance-dependent regret bound for the MVP algorithm in the episodic, tabular MDP setting. Unlike most prior works covering this topic, the authors focus on tightening the variance terms in the instance dependent bounds. The regret upper bounds are supplemented by a lower bound which matches the upper bound term containing the sub-optimal states, which is quite standard for optimism based algorithms.

All reviewers are happy with the theoretical contributions of the paper, find that the techniques used may be of independent interest and think that the notion of conditional variance is interesting. Reviewers are also happy with the matching lower bound. Most reviewers were also very happy with the presentation of the paper and the quality of the writing. The only minor concerns were about lack of empirical evaluation and questionable practical impact of the work. Given that this is a purely theoretical paper that explores new types of regret bounds for existing algorithms I think the work stands on its own without the empirical evaluation and recommend acceptance.
Decision: Accept (poster)