Achieving Constant Regret in Linear Markov Decision Processes
Authors: Weitong Zhang
Zhiyuan Fan
Jiafan He
Quanquan Gu
Venue: NeurIPS 2024 poster (2024)
Keywords: Reinforcement learning
Constant regret
Misspecified linear MDP
Primary area: reinforcement_learning

Abstract: We study the constant regret guarantees in reinforcement learning (RL). Our objective is to design an algorithm that incurs only finite regret over infinite episodes with high probability. We introduce an algorithm, Cert-LSVI-UCB, for misspecified linear Markov decision processes (MDPs) where both the transition kernel and the reward function can be approximated by some linear function up to misspecification level $\zeta$. At the core of Cert-LSVI-UCB is an innovative certified estimator, which facilitates a fine-grained concentration analysis for multi-phase value-targeted regression, enabling us to establish an instance-dependent regret bound that is constant w.r.t. the number of episodes. Specifically, we demonstrate that for a linear MDP characterized by a minimal suboptimality gap $\Delta$, Cert-LSVI-UCB has a cumulative regret of $\tilde{\mathcal{O}}(d^3H^5/\Delta)$ with high probability, provided that the misspecification level $\zeta$ is below $\tilde{\mathcal{O}}(\Delta / (\sqrt{d}H^2))$. Here $d$ is the dimension of the feature space and $H$ is the horizon. Remarkably, this regret bound is independent of the number of episodes $K$. To the best of our knowledge, Cert-LSVI-UCB is the first algorithm to achieve a constant, instance-dependent, high-probability regret bound in RL with linear function approximation without relying on prior distribution assumptions.

Achieving Constant Regret in Linear Markov Decision Processes
Weitong Zhang"
Zhiyuan Fan" EECS
School of Data Science and Society
University of North Carolina Chapel Hill Chapel Hill, NC 27599
Massachusetts Institute of Technology Cambridge, MA 02139 fanzyêmit edu
weitongz@unc. edu
Jiafan He
Quanquan Gu
Department of Computer Science University of California, Los Angeles
Department of Computer Science University of California, Los Angeles Los Angeles, CA 90095 qguêcs ucla.
Los Angeles, CA 90095 anauucc edu
Abstract
We study the constant regret guarantees in reinforcement learning (RL). Our ob- jective is design an algorithm that incurs only finite regret infinite episodes with high probability. We introduce an algorithm, Cert-LSVI-UCB, for misspec- ified linear Markov decision processes (MDPs) where both the transition kernel and the reward function can be approximated by some linear function up to mis- specification level Ç. At the core of Cert-LSVI-UCE is an innovative certified estimator, which facilitates a fine-grained concentration analysis for multi-phase value-targeted regression, enabling bound that is constant w.r.t. the number of episodes. Specifically, we demon- strate that for a linear MDP characterized by minimal suboptimality gap A. Cert-LSVI-UCB has a cumulative regret of (dd H /A/A) with high probability, provided that the misspecification level ( is below Ó(A/(V/H²²) Here is the dimension of the feature space and is the horizon. Remarkably, this regret bound is independent of the number of episodes K. To the best of our knowledge, Cert-LSVI-UCB is the first algorithm achieve a constant, mestance-dependent high-probability regret bound in RL with linear function approximation without relying on prior distribution assumptions.
establish instance-dependent regret
Introduction
Reinforcement learning (RL) has been a popular approach for teaching agents to make decisions based on feedback from environment. RL has shown great success in a variety of applications, including robotics (Kober al., 2013), gaming (Mnih al. 2013), and autonomous driving. In most of these applications, there common expectation that RL agents will master tasks after making only a bounded number of mistakes, even over indefinite runs. However, theoretical support for this expectation is limited in RI. literature: in the worst case, existing works such as [Jin et al. 20200; Ayoub et al. (2020); Wang et al. (2019) only provided ((vK) regret upper bounds with K being the number of episodes; in the instance-dependent case, Simchhoitz and Jamieson (2019); Yang et (2021); He et al. (2021a) achieved logarithmic high giggh-rrbbbilityy regret upper bounds (c.g.,
"equal contribution
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Ö(A-) log K)) for both tabular MDPs and MDPs with linear function approximations, provided a minimal suboptimality gap A. However, these findings suggest that an agent's regret increases with the number of episodes K, contradicting to the expectation of finite mistakes in practice. To close this gap between theory and practice, there is a recent line of work proving constant regrets bound for RL and bandits, suggesting that an RL agent's 's regret may remain bounded even when it en- counters an indefinite number of episodes. Papini et al. (202 Zhang et al. (2021) have provided instance-dependent constant regret bound under certain coverage assumptions on the data distribu- tion. However, verifying these data distribution assumptions can be difficult or even infeasible, On the other hand, it is known that high-probabiligy constant regret bound can be achieved uncondition- ally in mulli-armed bandits (Abbasi-Yadkori et al., 2011)) and contextual linear bandits if and only if the misspecification is sufficiently small with respect to the minimal sub-optimality gap (Zhang et al. 2023b). This raises a critical question:
Is it possible to design a reinforcement learning algorithm that incurs only constant regrel under minimal assumptions?
To answer this question, we introduce a novel algorithm, which we refer as Cert-LSVI-UCB, for reinforcement learning with linear function approximation. To encompass broader range of real- world scenarios characterized by large state-action spaces and the need for function approximation, we consider the misspecified linear MDP (Jin et al. 2020) setting. where both the transition kernel and reward function can be approximated by a linear function with approximation error Ç. We show that, with our innovative design of certified estimator and novel analysis, Cert-LSVI-UCE achieves constant regret without relying on any prior assumption on data distributions. Our key contributions are summarized as follows:
We introduce a parameter-free algorithm, referred to as Cert-LSVI-UCE, featuring a novel certified estimator for testing when the confidence set fails. This certified estimator enables Cert -ert-LSV--CE to achieve a constant, instance-dependent, high probability regret bound of Ö(d AA) for tasks with a suboptimality gap A, under the condition that the misspecifica- tion level Ç is bounded by Ç < ((Ai( This bound is termed a high probability constant regret bound, indicating that it does not depend on the number of episodes K. We note that this constant regret bound matches the logarithmic expected regret lower bound of 22 -1 log K), suggesting that our result valid and optimal in terms of the dependence on the suboptimality
gap A.
When restricted to well-specified linear MDP (i.e.. = <00), the constant high probability re- gret bound improves the previous logarithmic result O(d'H²> - log K) in He et al. (2021a) by a log K factor. Our results suggest that the total suboptimality incurred by Cert-LSVI UCB remains constantly bounded, regardless of the number of episodes K. In contrast to the previous constant regret bound achieved by PPapini et al. (022a)) sumption on the feature mapping, such as the UniSOFT assumption made in [Papini et al. (2021a). To the best of our knowledge, Cert-LSVI-ug UCB is the first algorithm to achieve a high probability constant regret bound for MDPs without prior assumptions on data distributions. We further show that this constant regret soooprobbyiyltyy bound does not violate the logarithmic expected regret bound by letting 8- = 1/K
regret bound does not require any prior
Notation.
Vectors are denoted by lower case boldface letters such as x, and matrices by upper case boldface letters such as A. We denote by [k] the set 21,2, k for positive integers k. We use log x to denote the logarithm of z to base 2. For two non non-negative sequence {an), (6n ). a, S (b,,) means that there exists a positive constant C' such that a, I Cb an S Öbb,) means there exists a positive constant i such that an I Ob, log" b,): an 2 (bb,,) means that there exists a positive constant C such that an 2 Cbn: On 2 (i(w.) means there exists a positive constant l such that a, 2 (b, log -gg=bb,,)) b,,): a, 2 w(b,) means that lim,- bn/an, ann = O. For a vector x E Rd and positive semi-definite matrix A E IRdxd, we define ||x||² = x Axx. For any set C, we use |C] to denote its cardinality. We denote the identity matrix by I and the empty set by Ø. The total variation
distance of two distribution measures P-)) and Q(-) is denoted by IPP(-) - Q(-)
Thee detailed conversion is presented in Remark 5.2

---

Algorithm
Misspecified MDP?
Result
LSVI-UCB (He et al.
202
LSVI-UCB (Papini et al. 2021a
X
( H 1og(1/A)) O(d
Cert- (ours, Theorem 5.1
V
Table I: Instance-dependenn regret bounds for different algorithms under the linear MDP setting. Here d is the dimension of the linear function Φbs, a). И is the horizon length, A is the minimal suboptimality gap. All results in the table represent high probability regret bounds. The regret bound depends the number of episodes K in He et al. (2021a) and the minimum positive eigenvalue À of features mapping in Papini et al. () Misspecified MDP? indicates if the algorithm can (V) handle the misspecified linear MDP or not (x).
2 Related Work
Instance-dependent regret bound in RL. Although most of the theoretical RL works focus on worst-case regret bounds, instance-dependent (a.k.a.. problem-dependent, gap-dependent) regret bound is another important bound to understanding how the hardness of different instance can affect the sample complexity of the algorithm. For tabular MDPs, jaksch et al. (2010) proved a O(D25² AA -1 log K)) instance- instance-dependent regret bound for average-reward MDP where D is the diameter of the MDP and A is the policy suboptimal gap. [Simchowitz and Jamieson (2019) provided a lower bound for episodic MDP which suggests that the any algorithm will suffer from l -1 regret bound. Yang et al. (021) analyzed the optimistic Q-learning and proved O(SAH A log K) logarithmic destance-dependent regret bound. In the domain of linear func- tion approximation, He al. (2021a) provided instance-dependent regret bounds for both linear MDPs (i.e., (dd H A 1 log K)) and linear mixture MDPs (i.e., O - log K)). Further- more, Dann et al.] (2021) provided an improved analysis for this
result with a redefined suboptimal gap. Zhang et al.] (202a)) proved similar logarithmic instance-dependent bound with He et al.] (2021a) in misspecified linear MDPs, showing the relationship between mis- specification level and suboptimality bound. Despite all these bounds are logarithmic depended on the number of episode K, many recent works are trying to remove this logarithmic dependence. Pa- pini et al. 2021a) showed that under the linear MDP assumption, when the distribution of contexts (s,.a) satisfics the 'diversity assumption' (Hao et al. 2020) called 'UniSOFT', then LSVI-UCB algorithm may achieve an expected constant regret w.r.t. K. Zhang et al. (2021) showed a similar result on bilinear MDP YYnng and Wang 2020), and extended this result offline setting, indicating that the algorithm only need a finite offline dataset to learn the optimal policy. Table summarizes the most relevant results mentioned above for the ease of comparison with our results.
RL with model misspecification. All of the aforementioned works consider the well-specified setting and ignore the approximation error in the MDP model. To better understand this misspecifi- cation issue, Du et al. (2019) showed that having good representation is insufficient for efficient RL unless the approximation error (i.e., misspecification level) by the representation is small enough. In particular, Du et al. (0199) showed that an (VV H/d) misspecification will lead to 2(2 sam- ple complexity for RL to identify the optimal policy, even with a generative model. On the other hand, a series of work (Jin et al. 2020 Zanette et al. 2020b a provided O(VK + +KK)-type regret bound for RL in various settings, where Ç the misspecification leve and ignore the depen- dence on the dimension of the feature mapping d and the planing horizon H for simplicity. These algorithms, however, require the knowledge of misspecification level Ç. thus free. Another concern for these algorithms is that some of the algorithms (Jin et al. (020) would possibly suffer from trivial asymptotic regret, i.e.. Regret(k) > w(kç- -poly (d, H1 log log(1/0) (1)))), as suggested by Vial et al. (2022). This means the performance of the RL algorithm will possibly de- generate as the number of episodes k grows. To tackle these two issues, /Vial al. (2022) propose the Sup-LSVI-UG algorithm which requires a parameter Esol. When Eio d/ V K, the proposed
not parameter-
'The misspecification level for these upper bounds is measured in the total variation distance between the ground truth transition kernel and approximated transition kemel, which is strictly stronger than the infinite- misspecification used in Du et al. (2019)
3

---

algorithm is parameter-free but will have a trivial asymptotic regret bound. When Ewl = S, the algorithm will have a non-trivial asymptotic regret bound but is not parameter- since it requires knowledge of the misspecification level. Another series of works (He et al.) 2022b Lykouris et al.) 2021 Wei et al. 2022) are working on the corruption robust setting. particular, Lykouris et al. (2021): WWi et al. (2022) are using the model-selection technique to ensure the robustness of RI. algorithms under adversarial MDPs.
3 Preliminaries
We consider episodic Markov Decision Processes, which are denoted by MiS, A. H, (rn), (Ph)). Here, S is the state space, A is the finite action space, H is the length of each episode, Th : S A + [0, 1] is the reward function stage h and (+ a) is the transition probability function stage h. The policy π = {T 1==1 denotes a set of policy functions Ty : S + A for each stage h. For given policy n, we define the state-action value function Q7, (s,, a) and the state value function V (8)
(s, = rr((s
EN EN= T'e (sN, (swe)) Sh s, an = =q V. (s) = Q% (s, TT (s)):
where S4'+1 (- aw).. The optimal state-action value function Qi and the optimal state value function VW are defined by Q7 (s, = max, Q% a), (s) max= V22 (s).
By definition, both the state-action value function (s, a) and the state value function V, (s) bounded by [o, H for any state 8, action a and stage h. For any function V S + R, we denote PP..Pa())s.a) (s') the expected value of V after transitioning from state given action a at stage h and [B, VIs, a) rs a) + [PP, (s, a) where B is referred to as the Bellman operator. For each stage h E [H] and policy r,, the Bellman equation, as well as the Bellman optimality equation, are presented follows
by [F>, (] a)
(T, = (, + PAV. [(, a) = BA ((s (=(s = + PA (s. a) = [B, V a))
We regret to measure the performance of RL algorithms. It is defined as Regret( Σk_ (VT - (s+)), where n represents the agent's policy at episode k. This definition quantifies the cumulative difference between the expected rewards that could have been obtained by following the optimal policy and those achieved under the agent's policy across the first K episodes, measuring the total loss in performance due to suboptimal decisions.
We consider linear function approximation this work, where we adopt the misspecified linear MDP assumption, which is firstly proposed in Jin et al. (2020).
Assumption 3.1 (G-Approximate Linear MDP, Jin et al. 2020). For any C S 1, we say a MDP is a a-approoie linear MDP with feature map & : S A + Rd. if for any h E [M]. there exist unknown (signed) measures μ4 = (mh : : (d) over S and an unknown vector 0, Rdd such that for any as,a) E S x A, we have
M(S, A, H, (ri),
(a),,l)))) (Ø(8, ())))))))))))))))))))))))))))() TV S C. (r((s,)) (Ø(s a), 0p) SC
w.l.o.g. we assume v(x, a) E x A [10(, a)ll < and 4h E [M] || (S) S Vd, |10 S vd.
The (-approximate linear MDP suggests that for any policy म, the state-action value function Q7 can be approximated by linear function of the given feature mapping & up to some misspecification level, which is summarized in the following proposition.
Proposition 3.2 (Lemma C. Jin et al. 2020 For a (-approximate linear MDP, for any policy m, there exist corresponding weights (w, (e((H) where w = 0,, + V (s' (d') such that for
any (8, a, h) S A x [M) (+, (db(s, a), wX) < 2HC. We have || llla 2H
Next, we introduce the definition of the suboptimal gap as follows.
Definition 3.3 (Minimal suboptimality gap). For each S,a E A and step h E [H], the subop- timality gap gap, (s, a) is defined by (s(s,a) (z) Q7 a) and the minimal suboptimality gap A is defined by A mins,s (s,(s,)) a)): a) * 0).

---

Algorithm Cert-LSVI-UCB
1: Set V (s) for all (8, E E [K], C 2 for all (h, [H] x N+ À 16
2: for episode k .... K do
3: Set L = max [log, (k/d)].0)
4: for step h = H
do
5: for phase | = 1, 1,... L 1-1d do
6:
U - Al Σ , (1.)
7:
W (U),
Σ Fect, 0% (r% + k h+1 (5%
Ú 81 [U ) wh. Ki w / where 82 0.01 2- h.J
8:
9:
end for
10:
Cert Cert-LinUCB(s1, (wi,);, -0,,,,hhh Tx) for all 7 E [k:
11: end for
Observe st ES for step h = 1,. H do
13:
14:
(s)
( (5)), (sh) Cert Lint-LinU(B(s); (w 1h, - Li)
15:
C (1 = Ck-1
( ( if ( = else Ck-1
(
16:
Ch Ch for all I + (s()
Ch.
17:
Play n (s)), set Φf = ( Th (s)))) receive rf and observe s
18:
end for
19:
end for
Notably, a task with a larger A means it is easier to distinguish the optimal action nj, (s) from other actions A, while task with lower gap A means it more difficult to distinguish the optimal action.
Proposed Algorithms
4.1 Main algorithm: Cert-LSVI-UCB
We begin by introducing our main algorithm Cert-LSVI-UCH. which is modification of the Sup-LSVI-UCB (Vial et al., 2022). As presented in Algorithm for each episode gorithm maintains series of index sets C, for each stage h E [H] and phase 1. The algo- rithm design ensures that for any episode k; the maximum number of phases is bounded by T.k S max ( (flog (k/d)],0} During the exploitation step, for each phase associated with the index set C/ 1 the algorithm constructs the estimator vector w by solving the following ridge regression problem in Line Line 7
al-
w argmin Al[w|12 ErEct (w के - r/ V (
After calculating the estimator vector w in Line 8 the algorithm quantilizes w and (U%,,) to the precision Kg. Similar to Sup-LSVI-UCB (Vial et al. 2022), we note ū is the quantized version of inverse covariance matrix (U (U,,,) rather than the inverse of quantized covariance matrix (Ü h.1) -1. The main difference between our implementation and that in Vial et al. (2022) is that we use a layer-dependent quantification precision Kи instead of the global quantification precision 2-12/6 /d, which enables our algorithm get rid of the dependence on Olog K) in the maximum number phases T.k-
h.l After obtaining wh; and - subroutine, Cert-LinUCB, is called to calculate an optimistic
value function (/ for all historical states s,, Line 10 Then the algorithm transits to stage h 1 and iteratively computes wh, and Ü for all phase and stage h E [#].
In the exploration step. the algorithm starts to do planning from the initial state s/. For each observed state s the same subroutine, Cert-LinUCB, will be called in Line 14 for the policy n (sf)), the
5

---

Algorithm 2 Cert-LinUCE (s (U,,
1 L.) 1 (s) (s),
input: V. wh. E R. U E g N+
2: output: (s) E R, (+) (s) , (0.1)
3: (s) = A, V.l (s)) = V (s)
4: for phase 1, 1
5: Set (s,
(o(s, wh))
6: Set (s) argmax (
7: ifl> L then
8:
return (V) f
(
9: else if m maX,eAA, | 10 :22 then
return (11 11: else if max - 33
(Vh,- argmax ac (1
min (8) 1 then return (1) = (V)
12:
13:
else
(s) min ( (V.6)))++---2.VV_--
(s) max 1Vxx
15:
(s) {{a (s) (h,((s,)) Vs - -4.2-1
16:
17:
end if
18:
end for
corresponding phase (sf), and a flag (s If the flag (+ 1, the algorithm adds the index to the index set Ck (=g) Line Otherwise, the algorithm skips the current index and all index sets remain unchanged. Finally, the algorithm executes policy प (sh)) receives reward ry, and Line
observes the next state & h++
4.2 Subroutine: Cert-LinUCB
Next we introduce subroutine Cert-LinUCB, improved from Sup-Lin-UCB-Var (Vial et al. 2022) that computes the optimistic value function Vz The algorithm is described as follows. Starting from phase = 1, the algorithm first calculates the estimated state-action function Qh, a) as linear function over the quantified parameter wh, and feature mapping ((s, a). following Proposi- tion 3.2 After calculating the estimated state-action value function (s),(s), the algorithm computes the greedy policy o (s) and its corresponding value function VI (s).
Similar to Sup-Lin-UCB. UCB-Var (Vial et al., 2022), our algorithm has several conditions starting from Line to determine whether stop at the current phase eliminate the actions and proceed to the next phase 7 + 1, which are listed in the following conditions.
Condition 1: In Line 7 if the current phase / is greater than the maximum phase L, we directly stop at that phase and take the greedy policy on previous phase T = -
there exists an action whose uncertainty | s, a))l is greater than the threshold 2 2- our algorithm will perform exploration by selecting that action.
Condition 2: Line 9
Condition 3: In Line 11 we compare the value of the pessimistic value function (s) and the
optimistic value function (s) which will be assigned in Line a4d Line 15 if the pessimistic estimation will be greater than the optimistic estimation, we will stop that phase and take the
greedy policy on previous phase ()) = - Only in this case, the Algorithm 2 outputs
flag (s) (s) 0, which means this observation will not be used in Line 1.5 in Algorithm
Condition 4: In the default case in Line 16 the algorithm proceeds the next phase after elimi- nating actions.

---

Notably, in Condition 4, since the expected estimation precision in the 1-th phase is about Õ(2- ') our algorithm can eliminate the actions whose state-action value is significandyy less than others, i.e., less than (2 while retaining the remaining actions for the next phase.
Specially, our algorithm differs from that in Vial et al. 2022) in terms of Condition 3 to certify the performance of the estimation. In particular, hell-behaved estimation should always guarantee that the optimistic estimation is greater than the pessimistic estimation. According to Line [4 and Line 15| this equivalent to the confidence region for I-th phase has intersection of the previous confidence region [ I Otherwise, we hypothesis the estimation on /-th phase is corrupted by either misspecification or bad concentration event, thus will stop the algorithm. We will revisit the detail of this design later.
It's important to highlight that our algorithms provide unique approaches when compared with pre- vious works. In particular, He et al. (2021b) does not climinate actions and combines estimations from all layers by considering the minimum estimated optimistic value function. This characteristic prevents their algorithm from achieving a uniform PAC guarantee in the presence of misspecifica- tion. For a more detailed comparison with He al. (202bb) please refer to Appendix [.I] Addi- tionally, Lykouris et al. (2021) Wei et al. (2022) focus on base learners are employed in the algorithms, whereas we adopt a multi thate approach similar with
regime where set of
SupLinUCB rather than conducting model selection over base learners.
Constant Regret Guarantee
Theorem 5.1. Under Assumption 3.1 let "R = 5(1 + 20 + [log(Id)))dH (og((6GHHH)) for
some fixed 0 < 5 1/4. With probability least 1 - 46, if misspecification level Ç is below O(A/(VHH²)) where A the minimal suboptimality gap, then for K E N+, the regret of Algorithm Dis upper bounded by
Regret( S A
This regret bound is constant w.r.t. the episode K.
Theorem 5.1
demonstrates a constant regret bound with respect to number of episodes K. Com- pared with Papini et al. (2021a), our regret bound does not require any prior assumption on the feature mapping Φ such as the UniSOFT assumption made in Papini et al.] (2011)). In addition, compared with the previous logarithmic regret bound He al. (2021a) la) in the well-specified setting. constant regret bound removes the log K factor, indicating the cumulative regret longer grows w.r.t. the number of episode K, with high probability.
Remark 5.2. As discussed in Zhang et al. (2023b) in the misspecified linear bandits, Our high prob- ability constant regret bound does not violate the lower bound proved in Papini et al. (2021a), which says that certain diversity condition on the contexts is necessary to achieve an expected constant regret bound. When extending this high probability constant regret bound to the expected regret bound, we have
E Regrett K)] < A log(1/6)) (1 (1-6) 8K,
which depends on the number of episodes k. To obtain a lub-linear expected regret, we can choose 8 = 1//K, which yields a logarithmic expected regret (d A log K') and does not violate the lower bound Papini et al. (2021a).
Remark 5.3. Du et al. (001)) provide a lower bound showing the interplay between the misspec- ification level Ç and suboptimality gap A in weaker setting, which discuss in detail in Ap- pendix B.2 Along with the result from Du et al. (2019), our results suggests that ignoring the dependence on H. Ç ç Õ(A) / Vd) plays an important seperation for if misspeficied model can be efficiently learned. This result is also aligned with the positive result and negative result for linear
bandits (Lattimore et al. 2020 Zhang et al. 2023b).
Technical Challenges and Highlight of Proof Techniques
In this section, we highlight several major challenges in obtaining the constant regret under misspec- ified linear MDP assumption and how our method, especially the certified estimator, tackles these challenges.
7

---

6.1 Challenge 1. Achieving layer-wise local estimation error.
In the analysis of the value function under misspecified linear MDPs, we follow the multi-phase estimation strategy (Vial et al. (022) to eliminate suboptimal actions and improve the robustness of the next phase estimation. Similar approaches have been observed in [haang et al. (2023b); Chu al.) (011)) within the framework of (misspecified) linear bandits. However, unlike linear bandits, when constructing the empirical value function VA for stage h in linear MDPs. Jin et al. (2020) requires covering statement on value functions to ensure the convergence of the regression, which is written by: (see Lemma D.4 in Uin et al. (2020) for details)
Erechh [VA htt (87) K+
S SOn ( (Vdlog((C)) + log( ( + vdx) (0)) 1
(6.1)
where we employ notation OH to obscure the dependence H to simplify the presentation. We use the notation 1 to denote as an n-covering, (or quantification in Takemura et al. 2021 | Vial et al. )022 for the value functions V h+1- However, the multi-phase algorithm, the empirical value function 17/ h++ from the subsequent stage h + 1, which is formulated using all pairs of parameters ( U The L phases. Consequently, the covering number log | is directly proportional the number of phases L Olog K).
Therefore, when analyzing any single phase 1, prior analysis cannot eliminate the log K term from (6.1) achieve local estimation error independent that is independent of the logarithmic number of global episodes log K. Furthermore, due to the algorithm design of previous meth- ods (Vial et al.) 2022). additional log K terms may be introduced by global quantification (i.e.,
Exal
d/v d/
Our approach: Cert-LinUCR. To tackle this challenge, we introduce the certified estimator into Algorithm and use a 'local quantification' to ensure the quantification on the local phase Ö(I) instead of the global parameter log K. The certified estimator works as follows: Considering the concentration term we need to control for each phase I:
of each phase / depend
||ErEcR $7 [ E(VA
(s*)
(6.2)
h+1
(U
as discussed Challenge the function class D V involves L Olog K) parameters, leading to a log K dependence in the results when using traditional routines. The idea of certified estimator get rid of this by not directly controlling log 1 1 Instead, certified estimator es-
tablishes covering statement for the value function class 1 P e Vi+ where 1/ 14411__ is the value function that only incorporates the first 4 phases of parameters { (wi,t: U Uh. Under this framework, the covering statement becomes:
Lemma 6.1 (Lemma C.4 informal). Let V be the output of Algorithm terminated at phase 4 t then with probability is least 1 26,
Erech,oi 0% (V (s*) -EV (s" (U) S 7.,1 = =51 dH
/og Mog
Lemma 6.1 suggests concentration inequality at any phase 4, and the following lemma sug- gests that this procedure will only introduce an Õ(2 error, under some faithful extension of the h.1. (s):
Lemma 6.2 (Lemma C.2 informal). For any 4 E N+, (V/ Vu h.I. (5) < 6-
Therefore, if a large enough 4. can be reached in Algorithm 2 combining Lemma 6.1 and Lemma 6.2 allow us to bound (6.2) without introducing log K factors. The next lemma shows that the Line will only never be triggered in shallow layer I.
Lemma 6.3 (Lemma C,8 informal). With probability at least - 28, for any (k, E [K] x [M]. Line Algorithm can only be triggered on phase / > ÿ (llog(1/()).
8

---

Lemma 6.3 delivers a clear message: In the well-specified setting, Line 11 will never be triggered
2 00). When the misspecification level is large, then Line [T] will be more likely triggered, indicating it's harder for the algorithm to proceed to deeper layer. The contribution of the certified estimator yields the following important lemma regarding the 'local estimation error":
Lemma 6.4 (Lemma C.12 Informal). With high probability, for any E > ((VdH))) and h E [H],
Cert-LSVI-UCB ensures
20 1=1
(V) - V (sf)
2 2 ((d9H4=-2)
2022b) achieved similar O uniform-PAt bound for (well- specified) linear MDP. Comparing with 4emma/6.4) with Ç (= 0, one can find that our result is better than He al. (2021b). In addition, Lemma 6.4 ensures this wniform-PAC result under all stage E [H] while He et al. (2021b) only ensure the = 1. This improvement is achieved by a more efficient data selection strategy which will discuss in detail in Appendix [..]
Remark 6.5. He al.
6.2 Challenge 2. Achieving constant regret from local estimation error
In misspecified linear bandits, Zhang al. (202bb) concludes their proof by controlling Ek=1 [V. (sf) - V (xf) 2 A Although it is trivial showing that rounds with instantaneous regret (s*) (sf) < A is optimal in bandits (i.e., (s*) V (s* previous works fail to reach a similar result for RL settings. This difficulty arises from the randomness inherent in MDPs: Consider policy that is optimal at the initial stage h 1. After the initial state and action, the MDP may transition to state si with small probability where the policy и is no longer optimal, or to another state $2 where i remains optimal until the end. In this context, the gap between V/7 (s1) and V/ ($1) can be arbitrarily small, given a sufficiently small p > 0:
((*(s) - VT (s1) = p(V2 (s2) Vi" (s/2) + (1 (V
(82)) = (V2 V22 (x)2).
Therefore, one cannot easily draw constant regret conclusion simply by controlling Ee= [V
V (st) 2 A] since the gap between (i (sf) needs to be fur- ther fine-grained controlled. In short, the existence of A describing the minimal gap between (*(s) (* a) cannot be easily applied to controlling regret (*) (s)...
Our approach: A fine-grained concentration analysis We address this challenge by providing fine grained concentration analysis in connecting the gap with the regret. Notice that the regret V Vr (s%) in episode & is the expectation of cumulative suboptimality gap E E A taking over trajectory { In addition, the variance of the random variable can be self-bounded according to
Var D A
< EE (EI= 4:) S H2R Σx A H (VT - VT (of)).
Denote 7i be the difference between VA (8t) V (sh) and the actual Σ - A Freedman in- cquality (Lemma H.5 implies that Σ n/ 2 aC and Σi= Var[n'] S vC' happens at the same with a small probabulity for certain constant and Using fine-grained union bound statement over C, we can reach the following statement indicates the cumulative regret can be upper bounded using the cumulative suboptimality gap:
Lemma 6.6 (Lemma C.14 Informal). The following statement holds with high probability:
1== (s.) - V (sw) < DE + +
Comparing with Lemma 6.1 in He et al. (2021a), Lemma 6.6 eliminates the log K dependence, which is achieved by the aforementioned fine-grained union bound. As result, together with Lemma 6.44 we reach the desired statement that Cert-LSVI-UE achieves constant regret bound when the misspecification is sufficiently small against the minimal suboptimality gap.
7 Conclusions and Limitations
In this work, we proposed a new algorithm, called certified estimator, for reinforcement learning with a misspecified linear function approximation. Our algorithm is parameter-free and does not
We employ the RL notations and set /t 1 for the ease of comparison.

---

require prior knowledge of misspecification level or the suboptimality A. Our algorithm is based on novel certified estimator and provides the first constant regret guarantee for misspecified linear MDPs and (well-specified) linear MDPs.
Limitations. Despite these advancements, several aspects our algorithm and analysis warrant further investigation. One significant open question is whether the dependency on the planning horizon and dimension d, H can achieve optimal instance-dependent regret bounds. For the gap- independent regret bounds, the regret lower bound is (d H&K) as shown by /hou et al. (2021a), and this benchmark has recently been met by works such as He et al. (2022a) (Agarwal al. (2022) Additionally, our analysis assumes uniform misspecification across all actions. Investigating other types of misspecifications could lead more sophisticated results, enhancing the algorithm's bustness and applicability to diverse real-world scenarios. This exploration remains an important direction for future research.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their helpful comments. This work done while WZ was a PhD student at UCLA. WZ is partially supported by UCLA dissertation year fellowship and the research fund from UCLA-Amazon Science Hub. JH and QG partially supported by the research fund from UCLA-Amazon Science Hub. The views and conclusions contained in this paper are those of the authors and should not be interpreted representing any funding agencies.
References
ABBASI- YADKORI, Y., PÁL., and SZEPESVÁRI, C. (2011). Improved algorithms for linear stochastic bandits. Advances in neural information processing systems 24
AGARWAL, A., JIN, Y. and ZHANG, T. (2022). Vo q: Towards optimal regret in model-free rl with nonlinear function approximation. arXiv preprint arXi::2212.06069
AYOUB, A., JIA, Z., SZEPESVARI, C., WANG, M. and YANG, L.. (2020). Model-based reinforce-
ment learning with value-targeted regression. In International Conference on Machine Learning. PMLR.
CESA-BIANCHI BIANCHI, N. and LUGOSI, G. (2006). Prediction, learning, and games. Cambridge univer- sity press.
CHU, W., LI, L., REYZIN, L. and SCHAPIRE, R. (2011). Contextual bandits with linear payoff functions. In Proceedings the Fourteenth International Conference on Artificial Intelligence and Statistics. JMLR Workshop and Conference Proceedings.
DANN, C., MARINOV, T. V., MOHRI, M. and ZIMMERT, J. (2021). Beyond value-function gaps: Improved denendt regret bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems 34.
DU. S. S., KAKADE, M., WANG, R. and YANG, L. F. (2019). Is good representation suf- ficient for sample efficient reinforcement learning? In International Conference on Learning Representations.
HAO, B., LATTIMORE, T. and SZEPESVARI, C. (2020). Adaptive exploration in linear contextual bandit. In International Conference on Artificial Intelligence and Statistics. PMLR
HE, J., ZHAO, H., ZHOU, D. and GU, Q. (2022a). Nearly minimax optimal reinforcement learning for linear markov decision processes. arXiv preprint arXiv:2212.0611:
HE, J.. ZHOU, D. and Gu, Q. (2021a). Logarithmic regret for reinforcement learning with linear function approximation. In International Conference Machine Learning. PMLR.
HE, J., ZHOU, D. and GU, Q. (2021b). Uniform-PAC bounds for reinforcement learning with linear function approximation. In Advances in Neural Information Processing Systems.
10

---

HE, J. ZHOU, D., ZHANG, T. and GU, Q. (2022b). Nearly optimal algorithms for linear contextual bandits with adversarial corruptions. In Advances in Neural Information Processing Systems.
HOEFFDING, W. (1963), Probability inequalities for sum of bounded random variables.
ISHFAQ. H., CUI, Q., NGUYEN, V., AYOUB, A., YANG, Z.,, WANG, Z., PRECUP, D. and YANG, L. (2021). Randomized exploration in reinforcement learning with general value function ap- proximation. In International Conference on Machine Learning. PMLR.
JAKSCH, T., ORTNER, R. and AUER, P. (2010). Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research 11.
JIA, Z., YANG, L., SZEPESVARI, C. and WANG, M. (2020). Model-based reinforcement learning with value-targeted regression. In Learning for Dynamics and Control. PMLR.
JIN, C., YANG, Z., WANG, Z. and JORDAN, M. I. (2020). Provably efficient reinforcement learning with linear function upproximation. In Conference on Learning Theory. PMLR.
KOBER, J., BAGNELL, J. A. and PETERS, J. (2013). Reinforcement learning in robotics: A survey. The International Journal of Robotics Research 1238-1274.
LATTIMORE, T., SZEPESVARI, C. and WEISZ, G. (2020). Learning with good feature represen- tations in bandits and in rl with generative model. In International Conference on Machine Learning. PMLR.
LYKOURIS, T., SIMCHOWITZ, M., SLIVKINS, A. and SUN, W. (2021). Cormption-robust explo- ration in episodic reinforcement learning. Conference on Learning Theory. PMLR.
MNIH, V., KAVUKCUOGLU, K., SILVER, D., GRAVES, A., ANTONOGLOU, I., WIERSTRA, D. and RIEDMILLER, M. (2013). Playing atari with deep reinforcement learning. arXiv preprint arXiv: 1312.5602.
MODI, A.. JIANG, N., TEWARI, A. and SINGH. S. (2020). Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics.
PAPINI, M., TIRINZONI, A., PACCHIANO, A., RESTELLI, M., LAZARIC, A. and PIROTTA, M. (2021a). Reinforcement learning in lincar mdps: Constant regret and representation selection. Advances in Neural Information Processing Systems 34 16371-16383.
PAPINI, M., TIRINZONI, A., RESTELLI, M., LAZARIC, A. and PIROTTA, M. (2021b). Leverag- ing good representations in linear contextual bandits. In International Conference on Machine Learning. PMLR.
SIMCHOWITZ. M. and JAMIESON, K. G. (2019). Non-asymptotic gap-dependent regret bounds for tabular mdps. Advances in Neural Information Processing Systems 32 1153-1162.
TAKEMURA, K., ITO, S., HATANO, D., SUMITA, H., FUKUNAGA, T., KAKIMURA, N. and KAWARABAYASHI, K.-1, (2021). A parameter-fre free algorithm for misspecified linear contextual bandits. In International Conference on Artificial Intelligence and Statistics. PMLR.
VIAL, D., PARULEKAR, A., SHAKKOTTAI, S. and SRIKANT, (2022). Improved algorithms for misspecified linear markov decision processes. In International Conference on Artificial Intelli- gence and Statistics. PMLR.
WANG, Y., WANG, R., DU, S. S. and KRISHNAMURTHY, A. (2019). Optimism in reinforcement learning with generalized linear function approximation. In International Conference Learning Representations.
WEL, C.-Y., DANN, C. and ZIMMERT, J. (2022). A model selection approach for corruption robust reinforcement learning. In International Conference on Algorithmic Learning Theory. PMLR.
YANG, K., YANG, L. and DU, S. (2021). Q-learning with logarithmic regret. In International Conference on Artificial Intelligence and Statistics. PMLR.

---

YANG. L. and WANG, M. (2020). Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning. PMLR.
ZANETTE, A., BRANDFONBRENER D., BRUNSKILL,, E., PIROTTA, M. and LAZARIC, A. (2020a). Frequentist regret bounds for randomized least-squares value iteration. In International Conference on Artificial Intelligence and Statistics.
ZANETTE, A., LAZARIC, A., KOCHENDERFER, M. and BRUNSKILL, E. (2020b). Learning near optimal policies with low inherent bellman error. International Conference on Machine Learn- ing. PMLR.
ZIIANG, W., HE, J., FAN, Z. and GU, Q. (2023a). On the interplay between misspecification and sub-optimality gap: From linear contextual bandits to linear MDPs.
ZHANG, W., HE, J., FAN, Z. and GU, Q. (2023b). On the interplay between misspecification and sub-optimality gap in linear contextual bandits. arXiv preprint arXiv:2303.093390
ZHANG, W., HE, J., ZHOU, D., ZHANG, A. and Gu, Q. (2021). Provably efficient representation learning in low-rank markov decision processes. arXiv preprint arXiv:2106.1 19355
ZHOU, D., GU, Q. and SZEPESVARI, C. (2021a). Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theooy. PMLR.
ZHOU, D., HE, J. and GU, Q- (2021b). Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning. PMI.R.
A Additional Related Work
RL with linear function approximation. Recent years have witnessed line of work focusing on RL with linear function approximation to tackle RL tasks in large state space, widely studied MDP model is linear MDP al. (2020). where both the transition kernel and the reward function are linear functions of a given feature mapping of the state-action pairs ( a). Several works have developed RL algorithms with polynomial sample complexity sublinear regret bound in this setting. For example. LSVI-UCB (Jin al. 2020) has ((Vd=H* regret bound, randomized I.VVI (Zanette al. 2020a) has an O(vd' H²K) regret bound and Ishfaq et al. (002) achieved an (Vdd' H* H*K) K). He et al. (022a)) then improves this regret bound to a nearly minimax-optimal while Agarwal al. (2022) provides general function approximation extension given the above result. Linear mixture/kernel MDPs (Modi et al. 2020: Jia et al. 2020 Ayoub et al.) 2020 Zhou et al. 2021b) have also emerged another model that enables model-based RL with linear function approximation. In this setting, the transition kernel is a linear function of a feature mapping the triplet of state, action, and next state (bss, a, s'). Nearly minimax optimal regrets can be achieved for both horieehorizon episodic MDPs (Ayoub et al.) 2020: Zhou et al., 2021a) and infinite-horizon discounted MDPs (Zhou et al. 2021b) under this assumption.
result (dv
B
Additional Discussions on Algorithm Design and Result
B.1
Comparison with He et al. (2021b)
It is worth comparing algorithm with He et al. (2021b), which also provides uniform PAC bound for linear MDPs. Both our algorithm and theirs utilize a multi-phase structure that main- tains multiple regression-based value function estimators at different phases. Despite this similarity, there are several major differences between our algorithm and that in He et al. (2021b), which are highlighted as follows:
(1)
In Line 7 of Algorithm I when calculating the regression- bassed estimator, for different phase
we use the same regression target & while their algorithm uses different V 1. for different phase 1.
(2) When aggregating the regression estimators over all different Ly phases, we follow the arm elimination method as in Chu et al.] (20TT), while He et al.] (202Tb) simply take the wosnt-wise minimum of all estimated state-action functions, i.c., Q(s, a) minse[Le] (s,
12

---

(3) When calculating the phase 1/2 (sf)) for trajectory sf s5. H He et al. 22021b) require that the phase (sf) ) to be monotonically decreasing with respect to the stage h. i.c., (s I 1h-1 (s (see line 19 in Algorithm 2 in He et al. (021b)), Such requirement will lead to poor estimation for later stages and thus increase sample complexity, In contrast, we do not have this requirement or any other requirements related to (s), and //
As result, by (3) He al. (022b)) have sacrifice some sample complexity make their al- gorithm work for different target value functions V As a comparison, since we use the same
regression target for different phase I, we do not have to make such a sacrifice in (3) Moreover, by
(2) He et al. (2021b) cannot deal with linear MDPs with misspecification, while algorithm can handle misspecification as in Vial et al. (2022).
B.2
Discussion on Lower Bounds of Sample Complexity
We present lower bound from Du et al. specification level Ç and the suboptimality gap A.
(0119) to better illustrate the interplay between the mis-
Assumption B.1 (Assumption 4.3, Du et al. 2019 A-Aproxiimaee Linear MDP). There exists Ç 0, A, E IRd and f4n : S - IRd for each stage h E H such that for any (s,a, E x A S, we have ( |s a) - (Ø(s, a), Mn (s')) I Ç and (m(s,a) - (Ø(s, a), 0p) S.
Theorem B.2 (Theorem 4.2, Du al. 2019). There exists family of hard-to-learn linear MDPs with action space |A| = 2 and a feature mapping Φ(s,a) satisfying Assumption B.1 such that for any algorithm that returns 1 1/2-optimal policy with probability 0.9 needs sample least Mminn 2d exp(d< /1 episodes.
Remark B.3. As claimed in Du al. (2019). Theorem B.2 suggests that when misspecification in the Lo norm satisfies Ç < (24 (AVH// H/d), the agent needs an exponential number of episodes to find near-optimal policy, where A 1/2 in their setting. It is worth noting that Assumption [B.] is s approximation for the transition matrix. Such a lo guarantee (Il ll S () weaker than the & guarantee (|) |l I provided in Assumption 3.1 So it's natural observe a positive result when making a stronger assumption and a negative result when making a weaker assumption. In addition, despite of this difference, one could find that Ç ~ A/vd plays a vital role in determining if the task can be efficiently learned. Similar positive and negative results also provided in Lattimore et al. (2020); Zhang et al. (2023b) in the linear contextual bandit setting (a special case of linear MDP with H 1).
C
Constant Regret Guarantees for Cert-LSVI-UCB
In this section, we present the proof of Theorem 5.1 To begin with, we recap the notations used in the algorithm and introduce several shorthand notations that would be employed for the simplicity of latter proof. The notation table is presented Table 2 Any proofs not included in this section are deferred to Appendix
C.1 Quantized State Value Function set Vh
To begin our proof, we first extend the definition of VA to arbitrary and give a formal definition of the state value function class Vh, skip the detail of this definition in Section 6
Definition C.1. We extend the definition of state value function Vek any tuple (k, h,t) [K] x [H] x N+ by
a hdl: = Cert Cert-LLnUCB(ss [Wh, (wh,e
( he
1
We also define the state value function family Vi, be the of all possible & h (W.yk/ (Ū ( (1 k
D4 '' Cert-LinUCH(S '
where Algorithm
We and (Ü,71) 3/21 referring to any possible parameters generated by Line g in
13

---

Notation
Meaning
Misspecification level of feature map 9%. (see Definiton 3.
Minimal suboptimality gap among An. (see Definition
States and actions introduced in the episode by the policy Th-
as,
Ground-truth state-action value function and state value function of policy æ.
(s,
The optimal ground-truth state-action value function and state value function. Suboptimal gap with respect to the optimal policy π." (see Definition 3.3
(s,a)
I Bb
The ground-truth -ruth transition kernel and the Bellman operator.
Ki
The quantification precision in the phase (see Algorithm
The confidence radius in the phase 1. (see Theorem 5.1
Index sets during phase in the episode k. (see Algorithm
Wh. U
Empirical weights and covariance matrix in the phase L. (see Algorithm
w hd: U
Quantified version w and U (see Algorithm
(s)
The overall optimistic state value function. (see Algorithm 2
(h,
Empirical state-action value function in phase 1. (see Algorithm
Vh,((s)
Empirical state value function in phase 1. (see Algorithm
Vhi(s)
Optimistic state value function in phase 1. (see Definition
(s)(s)
Pessimistic state value function in phase I. (see Algorithm
Policy played in the episode k. (see Algorithm 2)
Th.1
Policy induced at state s during phase of episode k. (see Algorithm
(s)
The index of the phase at which state stops in episode k. (see Algorithm
of
The feature vector observed in the episode k. (see Algorithm
Vi
Function family of all optimistic state function V (see Definition C.I
n.4
The confidence radius with covering on phase (4. (see Definition C.3
4
The phase offsets for the covering statement. (see Lemma C.5)
X
The inflation misspecification. (see Lemma C.6
L
The deepest phase that tolerance Ç misspecification. (see Lemma C.8
Le
The shallowest phase that guarantees accuracy. (see Lemma C.9
A
The suboptimaility gap of played policy Th. = at state s (see Lemma C.13
G1
The event defined in Definition C.3
G2
The event defined in Definition
D.13
G. The condition defined in Definition C.10
Table 2: Notations used in algorithm and proof
worth noting that one can check the definition of V. here is consistent with those computed in Algorithm with / < 1/ (s). Therefore, we will not distinguish between the notations in the remainder of the proof.
The following lemma controls the distance between (s) and V (s) for any phase 1.
Lemma C.2. For any (k:, h 8) E [K] x H x S,1 E (*) 1]. holds that
(+) < (x) (s), 1 - (3), 6-
Moreover, for any tuple (ks 8,44,, [ [ x S N+, the difference (V) VAh (s) is bounded by 6 2-4, following the extension of the definition scope of V h.4 outlined in
Definition C.I
Lemma C.2 suggests that given any phase 4, Vit is close Vz. This enables us to construct covering on Vy using the covering V
C.2 Concentration of State Value Function (s)
In this subsection, we provide a new analysis for bounding the self-normalized concentration of get rid of the log factor in Vial al. (002)).
Σ, (, V1T,,, aT) (s
14

---

To facilitate our proof, we define the filtration list Fx to verify that si. af are both F -eaasurabbble. Also, for any function V built on Fi; [P, ( ax) (( is F -measurable and it also a zero-mean random variable conditioned on Ji;
{ | of J==1,=11' {st a [i=1] It easy
H
The first lemma we provide is similar with Vial et al.
2022 which shows the self-normalized
concentration property for each phase and any function
V
Definition C.3. For some fixed mapping + 4 = (() that 1_ 2 L, we define the bad event as
(1
B (k,
Σ
6% (PAV ah) - ((s
n.I+
TECH,1
(UN,))-
The good event defined by 91 = n OH- Niz Ovevt.,, (k, where we define
R1, = 5 / (og(16llH//) = OldH log(6
Lemma C.4. The good event 91 defined in Definition happens with probability at least 1 26.
Lemma C.4 establishes the concentration bounds for any given phase I. However, the total number of phases for the state value function V/2 (s) can be bounded only trivially byl = O(log K). resulting in log K dependence. To address this issue, the following lemma proposes method to eliminate this logarithmic factor:
Lemma C.5. Under event 91, for any (ki, h4,,,1) E [K] x [ X N
Σ TEC
- / (5
S 1.1m.
(C.1)
(U%
where we set 71,4 with 4 = 1 20 [log(Id)].
Then Lemma C,5 immediately yields the following lemma regarding the estimation error of the state-action value function Qh
Lemma C.6. Under event 91 for any (k: h 8) E [K] x [M] x S, -
- fh(6)), e Ah,()))
(0,,(s,0) [BA V (1)(s,a) 22.2 + +xvic
(C.2)
where we define 12
Lemma C.6 build an estimation error for any E (s) - 1]. As we mentioned the algorithm design, larger here will lead to more precise estimation (a smaller 2 term in (C22) but will suffer from larger covering number (a larger a term in (C.2)). Following similar proof sketch from Vial et al. (2022). the next lemma shows that any action that is not eliminated has a low regret,
Lemma C.7. Fix some arbitrary Lo > and let x 12vdH. Under event G1, for any (k, s) (
[K] x [ x S,1 E [min(Lo. (s) - -s))l 0141 E Ak.
max 1s [B h+ (s,, a.+1) 8. + 21 WVIS. aEAA
C.3 The Impact of Misspecification Level Ç
Next, we are ready show the criteria where Line in Aigorithh@will be triggered, which shows the impact of misspecification on this multi-phased estimation.
Lemma C.8. Under event Gi, for any (k E [K] x [H] such that f!(s = 0, we have ( T.ç where L.g is the maximal integer satisfying 2 2 xL1 for x 12 i.e., L ((log(1/S))
Equipped with Lemma C.8 the following lemma suggests that how much estimation precision can be achieved by accumulating the error 2 (x.) that occurred in Lemma C.6
15

---

Lemma C.9. Under event 91 and for all & > 0, define Lę to be the minimal integer satisfying
2 v 0.01e/H, i.e., L = (=0--oo0.00::/11)) When L. I Ls. then for any K S [K]. h E [H],
Σ 2 (16h)) 2 0.001K e/H H + I. . AEA
2-
The relationship between Le < Le can be translated to the relationship between and Ç. We characterize this condition as follows:
Definition C.10. Condition Ge is defined for given and is satisfied if Lş 2 Le where Le is the minimal integer satisfying 2 he 0.01e/11 H H and Lę is the maximal integer satisfying 2 44 2 X
Lemma C.III I 2 & (og then g. satisfied.
Proof. lf 2 log we have
hh 0.005e/11 2 2 2
where the first inequality is given by the definition of Le, the last inequality is given by the definition of Tiç, and the second inequality holds since HxI. I (VdH2 log"(1/()) and the last inequal- ity is given by the definition of Le and Lç. respectively. Since 2 decreases as increases, we can conclude that La S Lş.
The above analysis of the interplay between misspecification level and precision yields the following important lemma in our proof, showing a local decision error across h E [H]:
Lemma C.12. Under Assumption 3.1 let ru 5(l 5(1+200 20 [log(ld)])ddl / (66ddH))))) for some fixed 8 < 1/3. With probability at least 1 38, for any E 2(vdH2 (og"(((())()))))))))) and h e [H], we have
(s Vg (st) 2
S co log log(ó
where refers some polynomial of log log 1 This can also be written as
Pr 3e > so, h [H],
Vi (stt)
V (o > [(E,0) s 6.
with 8o = ((VāH) and ((, H6 log(6
C.4 From Local Step-wise Decision Error to Constant Regret
The next lemma shows that the total incurred suboptimality gap is constant if the minimal subopti- mality gap A satisfies A > Eu.
Lemma C.13. Suppose RL algorithm Alg. satisfies
Pr Bc Eo, h
H.)
11
V.. (s
V (s =] f(E,0) 5
k=1
such that f(r, - 0 C2/E2) where C1, C2 > 0 are constant in E, but may depend on other quantities such as d, H, lo ( 1). If the minimal suboptimality gap A satisfies A >> Ep. then
K
H
A O(C,H/A+C.H
where A An (s))) stage h of episode k.
(x)) Q% (5), # (++)) the suboptimality gap suffered in
16

---

The following Lemma is refined version of Lemma 6.1 in He et al. (2021a) that removes the dependence between regret and number of episodes K.
Lemma C.14. For each MDP M(S, A, H, {rn), (Px)) and any O, with probability least 1 6, we have
Regret( K) <Ō
ΣΣ
Σ
A + H²2 H2 log((10))
1=1h=1
We now ready to prove Theorem 5.1
Proof of Theorem 5.7 By plugging in Lemma C.12 and Lemma C.13 into Lemma
C.14
we can
reach the desired statement.
D Proof of Lemmas in Appendix C
In this section, we prove lemmas outlined in Appendix are deferred to Appendix
Any proofs not included in this section
D.1 Proof of Lemma C.2
Proof of Lemma
According to the criteria for Line 11 we have (s) S (s) for any
I e (s) - 1]. From the definition of (s) and V. (s). they are monotonic in that 1 (s) S
Th and V2 < V (s) hold. Combining with 1 (s) i - have
vl 1 (s) - 1), Vi v (s)
(D.1)
From the definition of (s) and (s), we have
5 (s) V < (V2 (s) + (V (s)( 6-2-7
(D.2)
Plugging D.I into D.2 conclude that for any phase I E (s) 1). it holds that (1)
V. (s)) S 2-2
Now consider the extended state value function D h, with arbitrary 4 E N+ For every where 4 I (s) 1, we have (s) V [+)] S 6 2 reasoned above. For the other e S (s) following the procedure of Algorithm This suggest
where 4 (s), we have 17, = (s)
that 1 (s) V/, (s) 6 2- always holds.
D.2 Proof of Lemma C44
The following Lemma shows the rounding only cast bounded effects on the recovered parameters. Lemma D.1. For any (k, h, s) E [K] (M] 8,1 E [1 (s) (s)), A
4 (s), it holds that
(o(s,a), wh.)) (0(s, a), wi.)| s 0.01 ||< a)ll || allog .1 s 0.1 21
The following lemma shows the number of episodes that are taken into regression |Ck,// bounded independently from the number of episodes
Lemma D.2. For any tuple (k, 1) [K] [H] N+, we have |Ch,l 167 2dd
The following lemma shows the number of possible state value functions [* h.1 bounded indepen- dently from the number of episodes k.
Lemma D.3. For any tuple (k, h,1) [K] H] x N+, we have 1 22 &2
Now are ready to prove Lemma
C.4
17

---

Proof of Lemma C.4 Recall in Definition C3
the good event defined by the union of each single
bad event:
9 - n nn n
(,, V),
k= A= 121 veva.
where each single bad event is given by
(T oR) v(s > nnj )
(,,
Σ F
(U%,))-
in which [PPA ([, a) = Ey (a ((s).
Consider some fixed (4, E [M] x N V E h,1,"" Arrange elements of C/ in ascending order as (rih.. Since the environment sample s according to (- a J. we have [IP ;a))) (55)11) is F% -eeasurable with E [PAV (s),, ,aa,) ( F O. Since 0 s V(s)+t) S
H. we have [[Px VI( a ((5 H. This further leads
Σ ([A V (6
(UHH))+
(PPV o,) - ((
(Ut
H V 2dln (1+1C)11((aN) + 221n(12 1/0)
< H 2d +2 +2 (6)
S 7744
where the first inequality holds following from the good event of probability 1 5/(
defined in Lemma H.2 over filtration (F%')s J. the second inequality is derived from combin- ing Lemma D.2] and Lemma [33] and the last inequality is given by Lemma G.3 Accord-
ing to Lemma H.2 we have the bad event U B1 (ks h, I, V) happens with probability at most
8/ 5/(? HIVK, D) Taking union bound over all (h E [H] N+, V E Vki we have the bad event
happens with probability most
H
H
Prigi < ΣΣ Σ Pr
Σ
PHVK S 28,
4=1
VEVA.
1=1
1=
VeVA,
where the last inequality holds due to En>1 n== 2²/ /6. This completes our proof.
D.3 Proof of Lemma C.5
Proof of Lemma
C.3
Denote the martingale difference between V/h, V/J as:
(V,, (7AD)(s *((stt) (V (sh+1) V (sti
By triangle inequality:
Σ
(IP V (
(U
Σ
(F.V) ((5 Vih, (sh+
+
Σ
(D.3)
rEC
(U
rEC
((
18

---

According to the definition of event G1, we can upper bound the first term by
Σ
(s a
V. (5h+
87.4 = =.
(D.4)
TEC
(U)
we have P.. (s) 1it [+)] S 6 2- for any 8 Thus, difference be bounded by | 5 6 2- Consequently, bound the second term by
According to Lemma
Σ
Phithed
26.2 vick
(UN
I 6.2 1+ V 161 4
24 2 2'-1+ Vtd,
(D.5)
where the first inequality is provided by Lemma H.3 second inequality is from Lemma D.2 By plugging in the definition of 4., we can further bound the final term of (D5 by
utilizing the condition 1,T, < 6 the
Σ
24 2' +vVi S 22-22-20 S 0.1
(D.6)
(U).))
Plugging (.4 and (.6) into
D33) yields the desired statement such that
Σ
2% PA
4 115 o7. - V (
$ 1.1m.
(U
which concludes our proof.
D.4 Proof of Lemma C.6
The following lemma shows the state-action value function Q (s, a) is always well estimated.
Lemma D.4. Under event G1, for any (k, s, [K] x H x N x S x A.
10h,(s, a) [B, 1 < (1.2+ 8vidH 2l a) al) 0.01 2- 2HC.
Equipped with Lemma D.I and Lemma D.4, we are ready to prove Lemma C.6
Proof of Lemma C.6 In case that 1 < 12 f (s), for any a E (s), we have that
(1o(s,))l(ugp) - S |0 a) a1) h.1
+ || a) a))l 1 a))
<2- + 0.10.... 2- - 1-112-11-1
(D.7)
where the first inequality holds due triangle inequality, and in the second inequality, the first term is satisfied since state passes the criterion in Line 9 in phase 1 and the second term follows from
Lemma D.I and the last inequality is given by Lemma G.2 which implies 2 > % Plugging (D.7)
into Lemma D.4 gives
(8),(s, [B, D (s,
0.01 1.32 2- + 8.8vidHH + 2HÇ
2. + 12VIHH..
which proves the desired statement.
19

---

D.5 Proof of Lemma C.7
Equipped with Lemma C.6 we are able show several properties of the state value function Vi, throught the arm-climination process. The first lemma suggests that for any action E (s), there is at least one action a1+1 [Bx V2 h+ (8, a) after the elimination.
(1) close to aj in terms of the Bellman operator
Lemma D.5. Under event G1, for any (k, h s) E [K] [H] XS [min (s) 52 (s))),
A,, (s), there exists a1+1 E 1 (s) that
BA B
[B, D Atl 0411) s 22XVLoS
where X 12vdH for arbitrary Lo 2 1.
Then the following lemma shows that by induction on stage h E [H], we can show the elimination process keep at least one near-optimal action at+1 E A (s).
Lemma D.6. Under event G1. for any (k, h 8) [K] [M] x S Loin(Lo,1(00) (+))), there exists 01+1 E (1) that,
max aEA
V (1, - [B, & (1s, < 21 XVLoS.
where x 12 for arbitrary Lo 2 1.
The following two lemmas indicate that the state value function (s), stage h is good estima-
tion for the state value function given by Bellman operator Vss) max.e [B, / (s,
Lemma D.7. Under event 91, for any (k,, h, s) [K]
H x S, [min Lo. (x)) 5h (s))
max B
V Th ((s a) VA,, 2 2 + (21 - 1)xV
where X 12VdH for arbitrary Lu 2 1.
Lemma D.8. Under event G1, for any (k, h, s) E [K] [M] x S, [min(Lo. (2()) - -h (s))).
Vh, max B h+ (s. a) 2-22 xVLLo. aEA
where x = 12VCH for arbitrary Lo 2 1.
Now we are ready to show any actions remaining in the elimination process are near-optimal.
Proof of Lemma C.7
First, according Lemma D.7 we can write
max
BA 2 1(s, a) Vi,,(s) 2. 2- + (21 - 1)xx Loç.
(D.8)
aEA
Any action a1+1 E A
h.141 (s) passes the elimination process will satisfy:
(,, a(41) 2 Vsf,(s) - --22-1
(D.9)
According to Lemma C.6 with the condition that S Lop, we have that the empirical state-action
value function Qh, :) is good estimation for [B, 1 (3,,)) among every a1+1 E Aft (s) under event G1:
1B ++ a1)) Qh, 22.2-' LXVLOS.
(D.10)
Combining D.8
D.9 and 10 gives
max aEA
BB 4
(s, a) [B, 4
(141)
=mmxx BB 4 (s, a) (s) + (V) Qh, + (s,,(s,,44)) -BB) (11,,,((44444))) A
(2- 1 (2) 1)xy + 4. 2- + (2 2 + Xv Inc)
8 5- 21 XV TTo
which proves the desired statement.
20

---

D.6 Proof of Lemma C.8
The following two lemmas demonstrate that, at stage h, both the optimistic state value function, (s),,, and the pessimistic state value function, V (s),,,,, exhibit gap relative to the state value function determined by the Bellman operator, given as (s) max.e D ((s.
Lemma D.9. Under event G1, for any h, E [K] H x S,1 [min Lo. (s) fhh (s))
min (s) + 3-22 2_,, ( max a
BB 7 (s, a) 2 2- - (21 - 1)xV Loc.
where X 12v for arbitrary Lo 2 1. In case that s (s) - 1. the inequality is equivalent to
(s) max aEA
(ls 1 2 2- (21 - Lox
Lemma D.10. Under event G1, for any (k: h 8) E [K] x [ x 8 E [min| Lo, (s) (s)H,
max[B,, V/ il a) max (s), 2- [ 2 2 LoC.
aEA
where X 12vdH for arbitrary Lo 2 I. In case that s (s) - 1, the inequality is equivalent to
max aEA
V ( (s) 2 2 XV BA
Proof of Lemma C.8 Set Lo Le be the maximal integer satisfying 2- x X 2 0. Combin-
ing Lemma
D.10 and Lemma D.9 for any 1 E [min{Lo, 4/ (s) - (s))}, we have that
min (s), + 2-2 2- V [s) - max (s) 33 2 2-, [s)}
(s) - max BB, 1 11,, a)) + +(++mm (max (B, 12 h+ ((s, Vit((s)
aEA
aEA
2 (2-1- -(1 1)x Los) + (2- xo(
2 21 XV X LoS
2- -2x 2
where the second inequality holds since 2 decreases as I increases and the last inequality holds according to the selection of Lo-
When 1 (s) = 0, consider = 1/ (s). The above reasoning indicates the criterion Line can never satisfied. Thus fi: (s) = can only happen if (s) Lu Lç.
D.7 Proof of Lemma C.9
By partitioning [K] based whether Algorithm stops before phase Le, prove Lemma C.9 Specifically, Lemma D.2 bounds the number of episodes which Algorithm P stops before phase Le. This allows us establish upper bound for the desired summation over these episodes. Fur- thermore, for episodes that stop after phase Lee the contribution of 2 ni (st)) to the definition of Lg.
is small according
Proof of Lemma C.9
Denote +
[K] - U
cK In this sense, we have h.1-
2
Σ
2 2
Σ 2 2-12()))
(D.11)
KEK
kERnek
1=1 kEIene
From the construction of CK we have (1())) for any k E CKK Fix some CK + (+ = 0. we have (=))) 2 Le 2 Le where the first inequality is given by Lemma C.8 and the second inequality is given by the assignment of L.. Otherwise, have (s Le according to
21

---

the definition of CK h,1-
This indicates (s 2 Le holds for any l E Ch This allow is to bound the
first term by
Σ
2-th(s))
Σ
2 5..01|K] - e/H,
(D.12)
kEKnO A.+
keKneE
where the first inequality holds since (s > Lg and the second inequality holds from both 2 < 0.0le/H H and IK n n,C,,, [K].
Furthermore, we can bound the second term by
Σ
Σ
2 2-12
K Enncll.2
1=1
4,1
Σ
161 44 2-
1=1
16L.d 2 < 22 Led
(D.13)
where the second inequality is given by Lemma D.2 and the last inequality holds due to 0.0055/H < 2--1,, which because Le is a minimal integer such that Le 0.0le/H.
Finally, plugging D.12 and (D.33 into (.111) gives
Σ kEK
(o < 0.01| s/H 22 LedHt L =1
D.8 Proof of Lemma C.12
The following lemma provides upper bound for the underestimation error of the empirical state value function 1%7 with respect the optimal state value function VAA Lemma D.11. Under event 91 and for all 0 that Ge is satisfied, for any (k,h, [K] [K]x|H]XS)
V (s) 1% (s) S 0.07e.
As 1 represents empirical state value function with potentially optimal policy T (s), the fol- lowing lemma provides an upper bound for the overestimation error of V/ with respect to deploying the policy 7 (8) on the ground-truth transition kernel.
Lemma D.12. Under event 9i and for all that Ge satisfied, for any (k, [1]x
T (s) - [B, K+ ((s,
(s) ==+ 20 (x) 0.16s/H.
To start with, we define a good event according to: Definition D.13. For some bad event as
0, let Kj, [k E [K] Vg V (s+t 8). We define the
82(
Σ
Σ
th AV H log log(4H log(e 10ogg(--1//0)))))) 1))
kEKS w=h
where v/f ( h+1
V
[[ (s
(V (s ( The good event is
defined as G2- = 0 N1z1
By (h, 2-
The following lemma provides the concentration property such that the cumulative sample error is small with high probability.
Lemma D.14. Event G2 happens with probability at least - 8.
22

---

Using the above results, we can bound the instantaneous regret of any subsets once the misspecifi cation level is appropriately controlled.
Lemma D.15. Under event 91, G2 and for all that Ge is satisfied, for any K. C [ and h E [H], satisfies that
Σ (v)) Vi (sh) - 0.49//0 2 L.dH = + +4/ H log log(= 1))8). REK:
With all lemmas stated above, we can show Cert-LSVI -UBVc-veesss constant step-wise decision emror. The following lemma gives sufficient condition that Ge defined in Definition/C.Ii C. satisfied.
Now, we ready prove Lemma
C.12
Proof of Lemma C.72 We focus on the case where the good event G Ng occurs. By the union bound statement over Lemma C.4 and Lemma Lemma[D.14 and Lemma C.11 this good event happens with a probability of at least - 36 and requires 2 D(CVdH' log" (dH ()). W.l.o.g. consider K3, for some h E [H] and 2- where 0 an integer. On the one hand, have
(V
V (sh) 2 ICã
(D.14)
On the other hand, Lemma D.15 gives
Σ
(V% - Va (oh)) s 0.49 + 2 L 2 =-
REK
+ 4 Ha KjJ |og((//HHC
(D.15)
Combining (.14)) and D.15 gives
0,51 l S 17 ni + +
1)/5).
Plugging the value of Yr., we have
0.51 I 2 I. (Le + log(2" o 1og(16
+ 44 H KG log KC
(D.16)
According to Lemma
G.4
D.16) implies
K
S OLLe (Le + +og(d))))'' log Led) log(ō ))))
where i refers to a polynomial of log 1181). With the definition of Lgg, we conclude that
KK < # log
(dH-s-) lod's
log(ō logg( ())).
D.9
Proof of Lemma
C.13
Proof of Lemma
C.13
From the definition of suboptimality gap, have
A Ví (s/))
[B, V 1(5 (s)))
(*))
[BB [BA (
Væ" (st).
(D.17)
According to the assumption,
K
-1
(5t) > 5)
<
C1
C2
loga
C1
+
C2
23

---

holds for every e > with probability at least - 6, replacing the Vit( V/ (0%) with its lower bound A yields for every 5 > Eo.
K E1
C
C2 82
C ( )Φ)
25
log"
k=1
In addition, according to the definition of minimal suboptimality gap A in Definition 3.3
have
Af is either O or no less than A. Since for any x E {0} U U HJ. it holds that æ 5 11 [ 2 A] l
1 2 dj, we decompose the total suboptimality incurred in stage by
K
Σ
A
1
+
1
A
de
K
K
Σ
Σ
1
A
2
8
ds.
(D.18)
k=1
k=1
In case that Eo I A, the first term in D.18
be bounded by
K
C1
C2
C1
C2
A
<
+
log
9
+
(D.19)
A
A
A
We further bound the second term by
K
1 (i(( - 17T
(s 2
de
H
C1
+
C2
log"
{
Ci
+
C2
ds
g²
E2
k=
C1
C2
(a In
C2
S log
+
A
A
A
A
< (Ci log H + C2/A) polylog(Ci, C2, A-, (D.20)
Plugging (D.99) and (D200) into (D.18) with summation over [H]] conclude that the total suboptimality incurred in stage h is bounded by
H
ΣV A S H. (C1 + C2/A + Ci log C2/4) polylog(Cy, (Ci, Cz 1-1
1=1h=1
+(CcHH/A+CiH1)
D.10 Proof of Lemma C.14
Proof of Lemma C.14 For given policy π and any state 8/ E S, we have
(s))s - (sp)
(VV - [BA, V (sh, (s()))) + (Ba V (sh, (A( (sh,
[TB, V 1ssh,, Tn (8x)))
= (s),,, FA (sn)) + [P' (V - 11+1))(ss, TA (sn)),
where the second equality is given by the definition of suboptimality gap (x in Definition 3.3 Taking expectation on both sides with respect to the randomness of state-transition and taking tele- scoping sum over all h E [M] gives
H
(1) (s1) = =E
Σ
An m.(sn)).
where 8h41 ~ Pa(-/s,, Th (sn)). Let the filtration list be Jzk = {1ot ) )
we have
H
E
k F
ho
- (st).
24

---

Denote random variable nf = (Vi*(+ - (sf) -E A We can see see rf is 1s+Fu--mmauuuabbl with |[ = O. Furthermore, for the variance of 17", we have
Varln/| s E
[(
Σ h=1
H²
A [M
(V* V (st)):
where the first inequality holds due to Var[X] S B[(x 1) for any fixed I, the second inequality follows I A H. As result, the total variance of the random variables {n²² can be bounded by
K
K F S
Varln
Σ H - vx"(s))) = Reggete((K).
Let F(x) 2nH2² log(a/0) + H² H log(x/8), using peeling technique, can write
Pr
71
F F(Regret( Regret(K))
K
K Var Varln1|F4 & Reggett K)
PPr
{)) 2 F (Regget((K), < Regret K),
Pr
n*) (R)egre((K)),2- < Regret(K) 2
Varln S H Re)get(())
k=1
k=1
Pr
1/ 2 F(22),
Σ
Varlo* 2'
1=1
1=1
h=1
-F(2?22 2 + 2F22))
exp
(D.21)
where the last inequality follows Lemma H.5 Plugging F(x) v 2x log(z/0)) + 122 log(x/0)) back into (D2T)
yields
Pr
Σ
"
+ H² log (Regree(()))))) < Regret( K)
k=1
exp( - 1og(22/0)) /8)) = Σ
5/2' = 6. i=1
1=1
Therefore, whenever Regret(K) > 1, with probability at least - 6, we have
K
(oPggeee)) (K)))) + 2 log (3)) /
Combining with the fact that Regret( = Ek= x² + E ΣH A we have
K
H
Regret(K) K)
A + / loeggree (K)/5) + H BoggeReett(A
Jmm Am
25

---

whenever Regret(K) > 1. Taking z = Regret( K). a - -E Σm= A% + H log (Regret(())))) and = 2H² log (egret(KK)/)) inequality (1) yields
Regret K) 2
Σ k=
h
2H22 log (Regret(K))) + 4H² log(Regre((K)/0)
K
A + 6/12 + 6//2 log(Regre)(K))
(D.22)
According to the fact that x E a aloog + + - x S 4a (2g) + 2b, letting I = Regret(
2 2 h==
Ai.
+ 1og2 and = 6H² (D22
becomes
k 4 k=1k=1
Regret(K) -
4 2411 log(1/6) log
at 12/12 log(1/)) 12/12
k= h=1
Hiding the logarithmic factors within the Ô notation yields
H
Regret(K)) <
A + H² log(1/6))
E Proof of Lemmas in Appendix D
In this section, we prove lemmas outlined in Appendix deferred to Appendix F
D Any proofs not included in this section
E.1 Proof of Lemma D.1
We first introduce the claim from Vial et al. 2022 controlling the rounding error:
Lemma E.1 (Claim 1, Vial et al. 2022 restate). For any (k, h,,,,,,,,, a) E [K] [ x S.A. have
((8 a) T (wh,t wi.)) s vdna, ||bb(, ()(ut)) [ Vdni,
where is used to quantify the vector w and inverse matrix (U%
Proof of Lemma D.I From Lemma H.I we have
(o(s, a), wh.)) (Ø(s, a), wh.)l s vdki I 0.01 41
where the first inequality is due to Lemma E.I and the second inequality is valid due to Ky 0.01 2 2-4 Similarly, have
||[((,, All 11,(, 0lo S ddki S 0.1.227 21
E.2 Proof of Lemma D.2
Proof of Lemma D.2 First, both 17, (s and fT[(s]) held for any J Ch This implies that the criteria for either Line 7 or Line hollds as [=]][ss)). For r that satisfies the first criterion, we have 17, (sT) > L,. Note that L,- max { [To]] 0}, so this only happens for < 4'd. For other that satisfies the second criterion, we have that
[1 2 |1 |1 - |10 -aah----IMAlllle
| ( 1 2 2- 0.1 2-122-10 'M 0.9 2 7
26

---

where the first inequality holds due to the triangle inequality. In the second inequality, the first term |
1 is bounded by criterion in Line 9 while the second term | 0,,77' 11 (ug,))
follows from Lemma D.I
Arrange elements of C in ascending order as { According to the above reasoning, the number of elements T E Ch., that ( 2 0.9 2 2 is at least (c ,l - -4dd. This gives
-1
l
(Ug,) - 2 (0.9 2 1 (1Ck,1 4'd).
(E.1)
1=1
On the other hand, Lemma
H.1 upper bounds the LHS of E.1 by
min 16T1((,,)))11 S 2n (1+ (dd)).
(E.2)
Combining
E. and gives
0.81 4 4'1 " d'd) s 2dln (1+ + (1,,1111(111)))
(E.3)
From algebra analysis in Lemma G.1 a necessary condition for E.3 is C,, S 167 4'nfd.
E.3 Proof of Lemma D.3
We first present a claim from Vial et al. (002)) controlling the infinite norm of coefficient w.
Lemma E.2 (Claim 10. Vial et al. 2022). For any (ks h, e [K] [H] x Nt, we have [| S
[|w S (2)
Proof of Lemma D.3 Denote Xe as the set of all whe and V'e as the set of all 2, From the definition of Vi we have that 1V s IT' (1x+)- [Del). From Lemma E.2 we have || S (2 4 Note that wh. e E Rd, we have the number of different whe controlled by [ S (1 + 2- (2 /x) s (2- (2'dH)) 26+4 djd < 2(748))d Had. In addition, we have ((U))) - 11 E 1/A = 1/16. So we can bound the number of Ú D - (1 + 2 1/ (1)6x)) dd < (2- 22+4 dyj S 2(344ffd gel As result, we can conclude that
hit by
| S II (lxel D&l) s II (2(748)) god H 2(3+4)6 x S (2 H
E.4 Proof of Lemma D.4
Proof of Lemma D.4 According to Proposition 3 2 there exists parameter w/ such that for any
(s,a) S x A, it holds that (Ø(s, a), wn) [B, V (s. a) I 2HÇ. Denoting n/ (0% wa)
[B, V. h+ 155 (7) and 5 = (Vi (8h+)) - [PA 1 a))),, we have
Uk (w - wh)= = Σ 0 rh + ( - (VI+ Σ (T(H))) Wh
rECT
rEC
= --AW +
Σ
0 r/ ( + Di ( - (0h wol)
TeCk
=-AWn +
Σ
0% 1% + V (5h+1)) - [B, V/ (8)) + Σ
T
rEC
= Σ
O +
Σ
Hiah
(E.4)
TECk-1
T
27

---

where the first equality holds due to the definition of U wh. the second equality holds by rear- ranging the terms, the third equality holds according the definition of ny, and the last equality holds from the relationship that [B,, V/ 1s o%) r% + [PA V/4 1+1 ag) Therefore, for any vector @ Rd, it holds that
1(0, wh. wn)l
= Φ T (U - U (w., - wa)l
Φ ((U).))) -1 Awn + Σ
p1 +
Σ
Slon
rECh,
TEC
$ [ - -w +
Σ TEC
+
Σ
(E.5)
TEC
(12-))1
where the second equality follows (E.4) and the inequality holds from Cauchy-Schwarz Schwarz inequality (i.e.. x Uyl < ||x|||||y||u) From the triangle inequality, we have
Awa
Σ TEc
o +
Σ
(U%
S S/
Σ
Σ TECK
Dinh
(E.6)
TECK
(U
(
There are three terms which we will bound respectively. For the first term, we have
A Alwaall S
2 dAH < 0.1%,
(E.7)
where the first inequality holds due to the fact that ||all2 < 2H / as of Proposition 3.2 and the fact that Uh, ž AI. Under the good event 91 and Lemma C.5 the second term can be bounded by the following:
oich Σ rEck
$ 1.1%
(E.8)
(UR
And the last term can be bounded by:
Σ Tin
2HC 2HC /icid s 2112 161 --1fd--f--- 8VidH 2'
(E.9)
TEC
(+
where the first inequality is due to Lemma H.3 and the second inequality follows from Lemma D.2 Plugging (E.6), (E.7.. (E.)) and E.. into (E. gives
(60 wh. wx) (1.2% SVIdH 211c))
(E.10)
So for any (8, S x A, we have
1h, [Ba 1 at] - (b(s, wh.) [Ba D (s,
<(<0(s,)) Wh, - w (( wh. -w.) (6( (8(,,)), wh. - [B,, 2h ((,
< 0.01 2- (1.2 SvIdH mllllls a)),,)), + 2H1.
(E.11)
where the first inequality holds from the triangle inequality, and there are three terms in the second inequality which we will bound them respectively: the first term given by Lemma the second term follows E..0). and the third term holds from the definition of wi-
28

---

E,5
Proof of Lemma D.5
Proof of Lemma D.5 We prove by doing case analysis. case that action as 1 we can
assign 01+1 = ai E A 141 (s) so that
[B Vet 11t, [BA, Vh
(1, a++1) = 0.
(E.12)
On the other hand, in the case that a $ A))141(s), the action a eliminated with Q (s, ai) (s) 4. 2- Note in this case, there exists a++1 (s) (s) such that
<
Qh, ai) + < Vi,
(E.13)
According to Lemma and the condition that / S Lo. we have that empirical state-value function (s,,) is a good estimation for [BA, VA 1 on actions ar, a++1 E (s) under event 91
[B, 14 1s an) - (h,((s, 22.2 +XV LoS
(E. (8.14)
[B, h+ 1 (h, 22.2 Xv x
(E.15)
Moreover,
BD 1 (ss ( v 1 a41)
= (IBA 1 ((,, a1) - (s, a1)
+ (Oh,, a1) Q ((1)))4+1)))) + (Qh,(s,441)) 1s,,
2 2- + XV Loc) - -4.2
= -xxVLoS.
(E.16)
where the first inequality is derived from combining E.13
E.14 and E.15). So from E2.12) and
E.16
we have that [IB, 1 at) [ 1 a+1) 2xv Loc holds in both cases.
E.6 Proof of Lemma
D.6
Proof of Lemma D.6 We prove by induction on l. The induction basis holds at / - 0 by selecting a1 argmax A [ h (s, a) A which ensures max.e.4 [BB, V/ (s,, a) [B, 1/ (s. 01)
0. Additionally, the induction hypothesis holds for - 1, we have that
max[Br D (htil(s, a) [B 1 a141)
((max([, BB, D/ ( a) [BA 1 ai)) (IB, V. V/t (1t11(0,,
s 2(1 L)xV LoS
= 21 XVIC.
where the first inequality term is derived from combining induction hypothesis with Lemma D.5 We can then reach desired statement holds for all 7 the range by induction.
E.7 Proof of Lemmal D.7
Proof of Lemma D.7
According to Lemma D.6 there exists some action aj E (s, that
max[B, V (ss, a) [B, A ((s, an) s 2(1 1)xVLuC. aEAA
(E.17)
Moreover, we have
BA De ( an) (s) < [A DA (
(8, a1) 22 + + Los.
(E.18)
where the first inequality comes from the definition (s) m Qh, (s, a) and the second
inequality holds according to Lemma C.6 with 1 < Lo. Adding up E..77) and E. leads to
ma D.
dEAA ((,,) v s 2 + (21 1)x Loç.
This completes the proof.
29

---

E,8
Proof of Lemma D.8
Proof of Lemma D.8
The statement holds by simply checking:
Vh,
max 1 a) S (s,,(s) [B8, (s,,((s
REA
(H,,(5.=m,110)) [BA mf,,
22. XV Lol
where the first inequality holds from max 1 a) 2 [B h++ (s. (s)) the equality is
from the definition v,, = Qh, (s)), and the last inequality holds according to Lemma C.6
with the condition / I Lo-
E.9 Proof of Lemma
D.9
Proof of Lemma
D.9
The statement holds by checking
min (V., 3 3. 2 V (s)} - max BA Vi (s,,))
aeA
(v +3 2 (=1
max [B,, P/ (8,,
aaA
2 (3. (3.2 - 2- + (28 - 1)xv (n())
(=1
2- - 12111)xV Tao,
where the first equality holds due to (s) m (s) 3 ---2-)) the inequality holds according to Lemma D.7 and the last equality holds since 2 decreases as increases.
E.10
Proof of Lemma D.10
Proof of Lemma
D.10
The statement holds by checking
max "EA b+
B
5 [(s, a) max (s) - 3. (s)}
By (s. a) - máx((V -3.2
max eEA
E=1
min { [max
V h+ (s. 0) - Vi(e(s) +3.2-
8=1 aEA
2 mint (2 (2. 2 + XV Los) +3.2
t=1
=2 - -
where the first equality holds due to the design of Algorithm such that (*) (V - 3 2-4) the inequality holds according Lemma D.8 and the last equality holds since 2-1 decreases as / increases.
E.11 Proof of Lemma D.11
We prove Lemma D.Il in this subsection. The first lemma which we introduce establishes upper bound on the underestimation of the state value function 17 for every action and every state through reaches phase Le for state 8. Specifically, if the process does not reach phase Lg, we can substantiate the statement by applying Lemma D.9
a categorised discussion based on whether Algorithm 2
to phase (s) 1. Conversely, if the process reaches phase Lg. the statement can be proven by applying Lemma D.7 to phase Le.
Lemma E.3. Under event G1 and for all > 0 that G. is satisfied, for any (k, h, E [K] (H) S
max BA h-
[ V (s) < 0.07e/
30

---

Now we are ready to prove Lemma D.11 by induction.
Proof of Lemma D.I1 E [ (HSES,
We prove by induction stage h [H]. It is sufficient to show for any
(s) (s) S 0.07F (H + 1 h)/H.
(E.19)
We use induction on from H to prove the statement. The induction basis holds from the definition that V H++ (s) = + (+) = Assume the induction hypothesis E. 19 holds for h + 1, we have
max [BA Vitil((s, max [B A max (V / (+ aEA
max (Vh+1(b)) (s') e'ES
0.07s (II - -h/HH.
(B.20)
So for level h, holds that
(8) (s)
(max BA 1 max(BA Br V (s,))s)))))) (nax(BB, V ((s, (s)) aEA
(s))
acA
aЕA
S 0.078 (H - h)/H + 0.07e/ S 0.07e (H + h)/H,
where the first inequality holds by combining (E.20) with Lemma statement (9.19) for h. which leads to the desired statement.
E.3 This proves the induction
E.12 Proof of Lemma D.12
We prove Lemma D.12 in this subsection, the first lemma we use establishes an upper bound on the overestimation of the state value function V// for the executed policy (s) across all states.
Lemma E.4. Under event G1 and for all > that Gr satisfied, for any (k:, h, 8) E [K] x X
F max BB ((. [B V (s. (+)) S 16 (x)) + 0.10e/H.
aЕA
Then the following lemma establishes an upper bound on the decision error induced by the arm- elimination process with respect to the state-action value function given by the ground-truth trans-
form.
Lemma E.5. Under event G1 and for all that Gr is satisfied, for any (k, E [K] x (H] S
[B, V s 10 (s) 0.06s/H.
max "EA
Proof of Lemma
D.12
We can directly reach the desired result by taking summation on Lemma E.4
and Lemma E.5
(s)
BB & (s,
< max
BB 4 (8, a) - [B, D 1s, xx(s)) + (1/)()) - max
max(Ba [Ba (Ba 1
aEA
aEA
< (16 2 (2)) + 0.10s/H1 (10 (,)) + 0.06s/H)
= 26 2- (+) 0.16e/
E.13 Proof of Lemma D.14
We can prove the statement by applying union bound the concentration event, as given by the Azuma-Hoefii Hoeffding inequality.
31

---

Proof of Lemma Consider some fixed h [H] and = = 2- > 0. List the episodes index k such that Vi (s%) v (sh) > holds in ascending order as { Recall that
Th (V ( N, (s%))
(i+i($
Since the environment sample 4/ according to Pa (-1s) a we have mi is 7
with E 1 F = O. Since both 0 < V (5 + & and 0 & (5 I hold, we
have m - 2H. According to Lemma H.4 over filtration
F C FR+ -... CF C C C h+1 C... C.. .... .... C s...
C
for some fixed S | the good event that
K
H
The - 2H
= 4
(lo((=1)))
happens with probability at least (2 By the union bound statement over all (h, S, () [H] x [K] x N+ we have the bad event happens with probability at most
K 00
H
0C
Pr
(h(
4HSa 86,
A=15=1
h=1
where the last inequality holds from Σn>1 22= n²/6, which reach the desired statement.
E.14 Proof of Lemma D.15
We first provide the following instantaneous regret upper bound by combining Lemma D.11 and Lemma D.12
Lemma E.6. Under event G1 and for all O that Ge is satisfied, for any (k,h) E [K] [H].
H
H
Vi (sh) V (sh) $ 0.23e + 26
Σ 2
(o
Σ
Mhi
k=
h'=h
where u/h [P random variable that EE and mn/l
(V/+ [
(s
(v
(s
(s)+)) is a Fk measurable
h+1
h+1
H.
Together with Lemma subsets.
C.9 and the definition of G2, we can provide an upper bound for arbitrary
Proof of Lemma D.15 Taking summation on result given by Lemma E.6 all E gives
E (v) V (bh)) < 0.23 26
2
mhe
(B.21)
bE M=
kE kEKW
We can bound the second term according to Lemma
C.9
26
2 (r
0.226 L 72,
(B.22)
Under event G2 the third term satisfies that
H
[[ 1)/8).
(E.23)
kEK
f
Plugging E.22 and (E.23) into
E.21 gives
Σ (Vi V (s
< 0.49//]= + 27 L LgdH2 -1 + 4, lo log(e 1)/8).
REK
(E.24)
32

---

Proof of Lemmas in Appendix
F.1 Proof of Lemma
Proof of Lemma E.3 We start the proof by discussing different cases. First, if (8) S Lec, we have
(s) 1 < min Ley (6) 1}, according to the definition of (/,((s),
BB VA (+t1( (s) max
V aEd A (1 k 111)())-1(8)
max
aEd
< - 2-2
(1 +2(1(())) - -1xxV
$ 50+2x 2X -
- 50.02e H,
(F.1)
where the first inequality holds from Lemma D.9 and the last inequality holds due to x 2-4e 0.01s/H given by ge-
On the other hand, when 1/ (s) > Le, we have Le S min Le, (s) - 1} and thus
(s) Vr (s) Vh_, (8) 2-2
(F2)
where the first inequality due to Lemma C.2 and the second inequality holds due to the definition
of V. h.t. (s). Therefore, Le I min Le, (s) 1 yields
max BA max[BB R 1(, (l) aEAl
(x) < max [B Dh (8, a) - Vr,, (8) + 3.22" 2-
aEA
< 5 2 + (2L: - 11)
0.05z H 0.022 H O.
(F.3
where the first inequality is given by last inequality holds from x <
F22
the second inequality is given by Lemma D.7 and the S 0.01e/H H given by Ge- So considering both F.I and
F3 we have the first statement
max BA (s), - (s) s 0.07e/H
aeA
always holds under event G1.
F.2 Proof of Lemma
We prove Lemma E.4 by applying Lemma C.7 on phase min min (s) - 1}, in this subsection.
Proof of Lemma
E.4 Note we have t - (s) A (e according to the definition of
Ale 11,14(()). (s). This implies (s) E A (,)((s) (s) during the elimination process.
If (s) < Le. we have (5()) - S min Le (s)) - 1}. Thus,
max(B, 22 (/ [Bx 1 +s)) 88 (1(())-) 21)(s) XV Les
aEA
$ 16 (100 2.55
< 16. (1) + 0.022/HH,
(F4)
where the first inequality follows from Lemma C.7 with <)(s) A (s) and the last inequality holds due to & 0.01s/11 H given by Ge.
Otherwise, we have L, 5 min (s) - 1}. In this case, we have
max[BB, 4* 1 a) - [B, i (ss, *+)) < 2.22 + 2xL3.35 aEA
s 0.085/ 0.055/ 0.10s/H, (F.5)
33

---

where the first inequality follows from Lemma C.7 with (s) E A (2) (8) S A,, (s) according
to the elimination routine and the final inequality holds due to x S 2 S 0.01e/H H given by ge. So by combining (F:4) and F.5). we have the desired statement that
max[BB Pitlls, [BB 1B xs)) - 16 2 (+) + 0.100/11 /1.
aEA
F.3
Proof of Lemma E.5
We prove Lemma B.5 this section by applying Lemma D.8 on phase min (s( - 1}.
Proof of Lemma E.S
If 11))(s)) Le, we have (s)) - min (s) 1}. Firstly, we have
(s)
DA VA (1)) S VR (=) (8) + - ()))
(F6)
where the first inequality is given by Lemma C.2 and the second inequality follows from the defini- tion of V (s) (s). This leads to
(s) -
[B, V ( (V) V (= (V ( max D/
and
33. (1) + 2 2- (+) XV LeC
10 11(0) 0.01e/H,
(F.7)
where the second inequality, the first term is given by (F.6) and the second term holds according to Lemma D.& and the third inequality holds from xv C 0.01s/ H given by Ge-
Otherwise, we have L. S (s) - 1}. this leads to v max V (s) < (V/ - Vht (5)) + (V (s) max[BA VA
h+ (s,,aa
aEA
53.2-4, 2. 2h < 0.03= H + 0.02e/ H + +0.01e/H = 0.060/ H,
Lr XV XV TTeS
(F8)
where in the second incquality, the first term is given by the detinition of (s) and the second term holds according to Lemma D.8 and the third inequality holds from xL C S 2 Le < 0.01s/H
given by Ge- Combining F.7 and F.8) gives the desired statement
(s) max [B, max[B, (4 & 10.2 2,,)) + 0.06s H.
.EAA
F.4 Proof of Lemma E.6
Proof of Lemma E.6
According to the definition in which V. (st) [Bx V wetilll 1 (st))) and ghh + [P h+1 ( (s(t))
V 1))). We can write
t (s)) v.** (s = (V. (s)) [B, V ( * (sh))) o. + ( - ( (st
By telescoping statement from h H with the final terminal value ( VBL1() reach
H
(s - vg (sh) = Σ (V)() [B, - +
Σ
nhe
(F.9)
Mmh
34

---

As result, we can bound the desired term by
Vi (sh) - (sh)) V/_" (s 0.07c
Σ (V)
BA Vh hh+1 (5 =
Σ
The 0.07e
*
k/=h
k'=h
-
(26 2 ( + 0.16E/ H)
Σ
t + 0.07
M=h
H
H
(+
0.23s + 26
h M=A
=/
where the first incquality is given by Lemma D.1I the first equality given by (.9 and the final inequality is given by Lemma D.12
G
Technical Numerical Lemmas
Lemma G.1. If C%,,1 S 4'd + 2.5 d'7fdln (1 (C,,1/(16d)), then |Ck,1 S 161 4'7fd.
Proof. Denote c = // d)) We have that
+ - 4 < 4'd + 2.5 d
Dividing both sides by dd we have that
cl 1/ 1/ 2.5 In cl 4/77/16)
$ 1 1/ + In 5167/16) = 1/1/ + 2.5
Since / 2 and ? 2 1, we can further conclude that
< 5.1 + 2.5 In(c) S 5.1 + 2.5(1 + c/6)-
The necessary condition for the above inequality is < 16, which proves the desired statement. n
Lemma G.2. For any 2 1, 141/7 S 1.4.
Proof. Firstly, we have that
+ 22 log(1 + 1)
1 20 + log(l) - 1+ 22 0.21
-12,
(G.I)
L+
where the first inequality holds due to log(æ + 1) S 0.2x + In addition, we have
+ log(l +1) + log(()
4 + log(!) +1
<
4 + log(1) < 1.25,
(G.2)
where the first inequality holds due to log(z (++xx+++)) +1) < log(z) + 1. As a result, we can reach the desired statement according
5(1 + 1 | (og
7++
21
5(1 20 + log(l)) (lg(1
1+ 22 - log(1 + 1)) log(d)
log(l + 1) + log(16d11/0) log(!) + log(16dH/8))
7 20 log () + log(d)
1+ 22 - log(1 1) /lo(1++1
1 20 log(!)
V log(1)
< 1.2v1.25
< 1.4,
where the third inequality holds from plugging both G.I and
G.2
35

---

Lemma G.3.
2dIn(1 +1 +1.441f) + 2In( H 18) S 11
Proof. By calculation, we have that
Hy +1 +
I H 2d +1. 1 + H 12 da ln(24ldH/))
I,dH 241HH/221(22HH1//00 + dH / (221n224dH18
51,dH 1og(2" IdH1/0)
n1
Lemma G.4. If some constant 61, that
[Cc < (L + log(dH))) : log(Led/0) + | 111 1oge/////ooo/////////////
Then, there exists > 0 such that
KK caLo + 1 loght Led(Led) log(6
where is polynomial of log loglog((Let)) Lo
Proof. Let x = |CC log(/ We have that
I r<cL + log(d H log(Led/0) + VegHiz +Vo'Vo log (H 1og(s-1)/8)
Since <a var implies x < 2a 2h, so the above inequality implies
< T.e (Tg + log(d d H log( (lgd H log( log(e 1)/))
Moreover, since y/ log(t) < a implics y < 2a log a, we can conclude that there exists c3 > 0 that
KK
(L + log(dH))) & H log(Led) log(8-1)e,
where i is polynomial of log log -
H Auxiliary Lemmas
This section provides some auxiliary concentration lemmas frequently used in the proof.
Lemma H.1 (Lemma 11, Abbasi- Yadkori et al. (2011).. Let {Ø l be any bounded sequence such that t E Rd and o S B for some constant B O. For k 1, let U Al +
Ik=1 oJ (ΦT)T. Let X >> 0, then for k E [K], we have that
Σ min 11 s 2d (1 kB²
Lemma H.2 Gelf-Noormllize Martingale, Abbasi- Yadkori et (011 ). Let { be filtra-
tion, and (Ø* k n7*h [k=1 be stochastic process where o² I is g measurable and 17t is F.+1. measurable such that
E | 0, 01 - R, 1| < B
some constant B, > 0. Let > 0. For 1: > 1, let U = AI - o ( Then for any
5 E (0, 1), with probability at least 1 6, for all & >
have that
Σ ""
s Rv 2dln (1 + kB2/(d)) + 5-1
(U+)-1
36

---

Lemma H.3 (Lemma 8, Zanette et al.
)020b)). Let fΦ² ,17" > fk= be any bounded sequence satis-
rying de E 18 and bn for some constant <> O. For 1, let U AI ++=+++ o (
Then, for all & 2 1, we have that
Σ n" o
S SvVk.
(U+)-1
Lemma H.4
inequality, Hoeffding 1963)) Let {n1* kk=1 be martingale differ-
ence sequence with respect to filtration {FF) ===1 satisfying Iny1 I M for some constant M > 0
and 17 is -measurable with ||]]| = 0. Then for some fixed E [K] and any & E (0, 1),
with probability at least we have
& Σ n MV2K
Lemma H.5 (Freedman incquality, Cesa- Dosa-Bianchi and Lugosi (0066). Let {n² Jk=1 be martingale
difference sequence with respect to a filtration { JRm satisfying In/1 I M for some constant
M > 0 and n/ is -measurbaaee with | 0. Then for some fixed & E [K]. a >> 0 and
v > 0, we have
-2
Pr
a
Var(n" [F] [ sv)
S exp 20 + 2aM/3
I Numerical Simulation
We added experiments on synthetic datasets to verify the performance of the algorithm and the contribution of each component. Specifically, we consider linear MDP with S 4, A = 5, H = 2, and d = 8. Each element in the feature vector Φ(s, a) and jus') is generated by uniform distribution U (0, 1). Subsequently, & normalized to ensure that ((s|(s,a) i.e. (ss, a) ((s,,)() a,) E.' & (s)ss) The reward defined by r(s,a) = & (s, a)0, where 0 ~ (0,, Ia). The model misspecification is also added to the transition IP and reward function r. For a given misspecification C. the ground truth reward function is defined by r(s, a) & (s, a)0 0++ 7(s, a), where ((s,a) a) U(- When adding the model misspecification
probability measure,
the transition kernel, we first random sample a subset S4 C S such that |S4] = |S|/2. Then the misspecified transition kernel is then generated by
P()1s, + 2 1ss e ES4] S'
we can verify that [|P(()ss a) (-Iss, Ç. We investigated the misspecification level from 0.3 <= 0, 0.01, 0.3 in 16 randomly generated environments over 2000 episodes. We report the cumulative regret and runtime with respect to different misspecification levels. Additionally, we performed an ablation study by 1) removing the certified estimation (Algorithm Line I1 and 2) removing the quantization (Algorithm [ Line [))
The results of these configurations are presented in the following table. The detailed regret for all misspecification level is presented in Table and Figure [ plot the cumulative regret for 2000 episodes with respect to the misspecification level Ç. The cumulative regret curve is plotted in Figure [
The experimental results suggest several key findings that support our theoretical analysis:
When the misspecification level is low, it is possible to achieve constant regret, where the instan- taneous regret in the final rounds is approximately zero.
The certified estimator and the quantization do not significantly affect the algorithm's 's runtime.
contrast, the certified estimator provides an 'early-stopping" condition Algorithm 2 which slightly reduces the algorithm's runtime. In particular, our algorithm yields a computational com- plexity of (dd² AH 2 log K), which the same as Vial et al. (022)) and only log K greater than the vanilla LSVI-UCB (Jin et al. 2020) due the multi multi-phased algorithm.
37

---

Average Cumulative Regret vs. Misspecification level
Average Cunulative Regret vs. Misspecifiattion level
700
700
Fert.
CertEst./r), Quant (#1
CertEst//)) Quant [s]
Avarage Curruaaive Rapiot
600
Awarage Cumulative Ropiet
600
400
400
300
300
0.00
0.05
0.10
0.15
0.20
0.25
0.30
0.35
0.00
0.05
0.10
0.15
0.20
0.25
0.30
0.35
Misspecificatin (
Misspedfication level
(a) With quantization
Without quantization
Figure 1: Cumulative regret over 2000 episodes with respect to different misspecification level Ç- The result is averaged over 16 individual environments.
The certified estimator helps the algorithm by providing robust estimation in the presence of mis- specification. As shown in the table, using the certified estimator does not make a significant difference when the misspecification level Ç is low, but it becomes significant the misspecifica- tion level increases.
The quantization does contribute significantly the results, the numerical results intrin- sically discrete and quantized. In Figure 2 the regret curve with quantization and the one without quantization are highly overlapped.
Q.
(= 0.0
0.01
0.02
0.03
0.04
X
189.01 + 57.21
190.57 = 59.49
194.74 + 61.99
201.36
63.67
211.67 = 66.06
189.00 57.18
190.55 59.49
194.75 + 61.99
201.41
63.67
211.68
66.06
X
196.32 64.09
203.68 = 77.24
200.41 + 66.88
207.47
70.97 207.52
222.61 + 78.77
196.31 + 64.06
199.07 68.45
200.42 + 66.88
70.96
222.62 + 78.77
C.
Q.
< 0.05
0.06
0.07
0.08
0).09
220.52 67.85
233.57
66.54
248.08 + 68.70
264,49 + 72.05
279.82 + 78.28
X
220.50 67.86
233.48 = 66.50
248.06 + 68.69
264.56 + 72.00
279.81
78.25
221.87 + 73.51
232.75
73.75
261.16 + 84.44
262.07 + 82.05
273.56
+ 96.19
221.86 73.51
232.70
73.81
261.14 + 84.43
262.15 82.01
273.55 96.17
C.
Q
0-1.1
0.11
0.12
0.13
0.14
292.59 80.52
305.73 1 83.47
323.93 1 90.25
337.65
94.39
355.49
106.22
292.68 80.55
305.71
83.44
323.91
1 90.23
337.65
94.39
355.49
106.22
X
285.81
1 102.54
297.98
107.21
315.22
114.50
335.69
1 110.76
339.81
1 99.26
285.90 + 102.57
297.97 = 107.18
315.20
114.49
335.69 + 110.76
339,82 = 99.27
C.
0.1.15
0.2
0.25
0.3
Time(s) 1654,76 = 125 40
377.27
127.21
450.49 = 154,80
526.45
181.90
634.46 + 245.70
X
377.23 127.13
450.48 + 154.79
526.36
181.91
634.48 1: 245.68
1654.21 + 141.31
351.52 118.09
436.30 = 154,89
530.15 + 194.89
605.64 + 233.19
1599.66 66 + 138.18
351.50 118.03
436.29 = 154.91
530.58 195.24
605.67 + 233.18
1593.38 98.11
Table 3: Average cumulative regret (1: standard derivation) and execution time 2000 episodes.
The results are averaged over 16 individual runs. indicates Certified Estimator is used. Q indicates if Quantization is used.
38

---

Crculdiis
Caridtion
coces andia
(a) (=)
(b) Ç = 0.05
(c) C 0.10
(d) 0.15
(c)
0.20
( 0.25
Figure 2: Cumulative regret with respect to the number of episodes. We reported the median cumu- lative regret with the shadow area the region from 25% percentage 75% percentage statistics over 16 runs.
NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We study the constant regret analysis in reinforcement learning from the- oretical perceptive. The contribution, assumptions and scope are clearly claimed in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 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.
It is fine to include aspirational goals motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discussed the limitations and future potential directions in Section 7
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not 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-specification, asympiotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
39

---

The authors should reflect on the scope of the claims made, e.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, a 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 't 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 a complete (and correct) proof?
Answer: [Yes].
Justification: We provide detailed proof for all theorems in the appendix, starting from Appendix C
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 appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should 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 provided not)?
Answer: [NA]
Justification: Our submission paper does not include experiments
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 various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specifie model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with
40

---

the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via 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 a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS 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) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If 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 be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: 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?
Answer: [NA]
Justification:
Our paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
publicc/guudes//odeSSuttti soseeeooiiiiisiioooooooooo.ie for more details.
While we encourage the release code and data, we understand that this might not be possible, so "No" is an 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 to reproduce the results. See the NeurIPS code and data submission guidelines (https:
wttp://gideeeeeeeeeeeeee https///ooooooeoimiioooooooooee ssionPolicy) 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 are omitted from the script and why.
At submission time, to 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
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?
Question:
Answer: [NA]
Justification:
Our paper does not include experiments.
Guidelines:
41

---

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, 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: The paper does not include experiments.
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.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK report I-sigma error bars, but should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors verified.
For asymmetric distributions, the authors should careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA 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 runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't i make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://erarrppp.ccpppc/cctttccaa
Answer: [Yes]
Justification:
We have reviewed the NeurlPS Code of Ethics.
42

---

Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification:
Our work provides the theoretical understanding of reinforcement learning- Although there might be some potential social impacts on reinforcement learning applica- tions, according to the guidelines, we believe our result does not have direct connection with these issues.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or 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.
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 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 is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (c.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 ML).
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: We place this paper on the theoretical understand of reinforcement learning thus the paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by quiring that users adhere to usage guidelines or restrictions to 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.
43

---

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. Licenses 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 do not existing assets in the paper.
Guidelines:
The answer NA means that the paper does not use 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 used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should provided.
assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
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:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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 instructions given to participants and screenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does involve crowdsoureing 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 in the main paper.
44

---

According to the NeurIPS Code of 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 equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
45


Reviews:
[{"review_id": "CdPWK3ApgY", "reviewer": "Reviewer_jLch", "summary": "The paper presents improved regret bounds for Linear MDPs when the suboptimality gap \\Delta is known. Most crucially (a bit surprisingly), the regret bounds are constant in a number of episodes K", "questions": "Please see above, I am willing to engage during the rebuttal phase.", "limitations": "NA", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The contributions are broadly theoretical, and the removal of dependence on the number of episodes K seems to be a good contribution to the academic understanding of the gap-dependent (instance-dependent)learning bounds for reinforcement learning.\n\nThe paper provides a good coverage of related works in this area and describes the setting well.", "weaknesses": "1) b_h^\\pi seems to be undefined in proposition 3.2\n2) \\kapp_\\ell in Algorithm 1, line 8, as claimed by the author, helps to get rid of log(K). Can you explain more about how it helps to remove log(K)? is this the reason why the regret bounds do not have log(K) dependence?\n3)I would urge the authors to provide a full expression of regret without O notation, including the log factors either in the main text or in the appendix (I could not find a full expression for the result in theorem 5.1). Specifically, it is surprising, perhaps I am missing something, that the regret is O(1) when Delta = 1/(d^3H^5) when K=1. I suspect some lower-order terms are hidden, or maybe the result is only valid for K \\geq something. The asymptotic dependence can be right still.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback. We address your questions as follows. \n\n**Q1. What's the meaning of notation $\\lVert wb_h^\\pi\\rVert_2^2$ in Proposition 3.2?**\n\n**A1.** Sorry for the typo caused by the LaTeX macros. The $\\lVert wb_h^\\pi\\rVert_2^2$ should be $\\lVert \\mathbf{w}_h^\\pi\\rVert_2^2$ instead.\n\n---\n**Q2. How the $\\kappa_l$ eliminates the dependence of $\\log K$.**\n\n**A2.** We discussed the contribution of applying layer-wise quantization in Section 6.1, Line 268. Previous work (Vial et al., 2022) used a global quantization $\\epsilon_{\\mathrm{rnd}} = d / K^2$. Therefore, the quantity of all possible quantized parameters \n$\\tilde{\\mathbf w}$ and $\\tilde{\\mathbf U}$ in each layer $l$ unnecessarily depends on the total number of episodes $K$.  In our algorithm, each layer $l$ uses a different quantization parameter $k_l$ so the quantity of the quantized parameters $\\tilde{\\mathbf w}$ and $\\tilde{\\mathbf U}$ only depends on $l$ (Lemma D.3).\n\nIn addition to the benefit from layer-wise quantization, another technique to eliminate the $\\log K$ dependence is the certified estimator discussed in Section 6. Without the certified estimator, one needs to cover the parameters for all $L$ layers. The certified estimator builds the connection between the output value function between consecutive layer $l$ and $l +1$. As a result, in the analysis, we can focus on the concentration of some fixed layer $l_+$, which does not depend on the parameter $K$ (Lemma 6.1). The details are discussed in Section 6, Challenge 1.\n\nBesides the aforementioned challenges and techniques to remove the logarithmic dependence in the estimation error, we also provide a novel concentration analysis in Section 6.2 that achieves constant regret. In sharp contrast, previous analysis (He et al., 2022) has the logarithmic dependence for this concentration.\n\n---\n**Q3. Why the regret is $O(1)$ when $K = 1, \\Delta = 1/(d^3H^5)$? What is the full expression of regret without $O$ notations?**\n\n**A3.** We would like to first clarify that the extreme case with $O(1)$ regret you mentioned is incorrect. The regret is in the form of $\\text{Regret}(K) \\le \\tilde O(d^3H^5 \\Delta^{\\color{red}{\\mathbf{-1}}}\\log(1 / \\delta)$. Therefore, to achieve $\\text{Regret} = O(1)$, one would need to set $\\Delta = d^3H^5$ instead of $\\Delta = 1 / (d^3H^5)$. Since the reward is bounded by $0 < r(s, a) < 1$, the gap $\\Delta$ is trivially bounded by $[0, H]$ due to $0 \\le Q^*(s, a) \\le H$. Therefore, letting $\\Delta = d^3H^5$ is unrealizable in this setting. \n\nIn response to your request for the regret bound without $O$ notation, the full expression of the regret bound can be obtained through Lemmas C.12, C.13, and C.14. We present the full expression as follows:\n> $$\\begin{align}&\\textrm{Regret}(K) \\le \\left(8I_{\\Delta} + 24H^2\\log(1 / \\delta)\\right)\\log\\left(4I_{\\Delta} + 12H^2\\log(1 / \\delta)\\right) + 12H^2,&I_{\\Delta} =4I_{\\text{C.13}}\\log\\left(2I_{\\text{C.13}}\\right),\\end{align}$$\n> $$\\begin{align}&I_{\\text{C.13}} =  c_1 L_{\\Delta}(L_{\\Delta}+\\log(dH))^2 d^3 H^5 \\Delta^{-1} \\log(L_{\\Delta} d/\\delta) + c_2 H^3 \\Delta^{-1} \\log (H\\log(\\Delta^{-1})/\\delta), &L_{\\Delta} = \\lceil -\\log(0.01 \\Delta / H) \\rceil. \\end{align}$$\n\nThe dominating term is $I_\\Delta \\sim I_{\\text{C.13}} = \\tilde O(d^3 H^5 \\Delta^{-1} \\log(1 / \\delta)$. In the paper we use the $O$ notation for readability of the proof due to the complexity of this expression.\n\n---\n- Vial, Daniel, et al. \"Improved algorithms for misspecified linear markov decision processes.\" AISTATS, 2022", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "j1WbwoCK33", "reviewer": "Reviewer_8jf2", "summary": "This paper gives a constant regret (total regret independent of the number of episodes $K$) algorithm for online reinforcement learning of linear MDPs. The environment is considered to be a $\\zeta$-approxinate linear MDP as in (Jin et al 2019), with an assumption that the misspecification level ($\\zeta$) is not too large. The algorithm is a more sophisticated variant of the original LSVI-UCB, which is a further improvement of earlier work that improves the regret of LSVI-UCB (but does not achieve constant regret).\n\nThe regret is parametrized by the instance-dependent minimal suboptimality gap $\\Delta := \\min_{h,s,a} \\\\{V_h^\\ast(s) - Q_h^*(s,a) : V_h^\\ast(s) - Q_h^*(s,a) \\neq 0\\\\}$, which also appears in earlier instance dependent regret bounds for linear MDPs (and also in general episodic MDPs).\n\nTheir algorithm, Cert-LSVI-UCB, has a regret bound of $\\tilde{O}(d^3 H^5 \\Delta^{-1})$. The dependence on $\\Delta$ is optimal, whereas the dependence on $d$ and $H$ may be suboptimal.\n\nThis paper is also an improvement on the previous work that provides \"constant regret\" bounds for linear MDPs (Papini et al 2021) in that it does not require the \"UniSoft\" assumption on the feature mapping (only requires the standard assumptions of misspecified linear MDPs as in Jin et al 2019, plus that the misspecification level $\\zeta \\leq \\tilde{O}(\\Delta/\\sqrt{d}H^2)$).", "questions": "NA", "limitations": "* The limitations have been adequately addressed and there is no negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* The algorithm and its analysis gives a substantial improvement over earlier algorithms with instance-dependent bounds for linear MDPs, in that it is the first algorithm with a constant regret bound that requires minimal assumptions, even for misspecified linear MDPs.\n* The algorithm is cleanly based on earlier linear MDP algorithms starting from LSVI-UCB, applied in more sophisticated ways (multiple regression phases per episode etc), and the improvements in the algorithm and challenges in the analysis have been highlighted in the main paper itself (especially, in avoiding the dependency of the regret on the number of phases).", "weaknesses": "* The contribution of the paper is entirely theoretical, but most of the proof is in the appendix (which is unavoidable).\n* Some experimental results (even on synthetic data) would definitely enhance the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive feedback on our work! We will address your questions as follows:\n\n**Q1. Adding some experimental results in addition to the theoretical result**\n\nA1. Thank you for the suggestion. We have included some experimental results on a synthetic dataset during the rebuttal phase. Specifically, these results are provided in our response to all reviewers. The experimental results indicate the potential for achieving constant regret and highlight the contributions of each algorithm component through ablation studies. We will include this information in the camera-ready revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QF2M08jXbo", "reviewer": "Reviewer_33Lb", "summary": "This paper proposed a constant regret learning algorithm for linear MDPs with approximation error (misspecification). Specifically, it proved an instance dependent regret that is independent of the number of episodes. In addition, the algorithm does not require prior knowledge of misspecification level or suboptimality gap.", "questions": "1.\tThe new algorithm does not require UniSOFT assumption made by Papini et al. (2021a). However, in Thm 5 of that paper, they showed that UniSOFT is a necessary condition for constant regret. Can you explain how this does not apply to the current setup? \n2.\tIt is not very intuitive to understand the constant regret with no dependency on the number of episodes. Are there any simple examples that can run the algorithm empirically to verify this behavior?", "limitations": "There is no potential negative societal impact.\n\nThe authors addressed the limitations in Section 7 such as the tightness of the bound and uniform misspecification assumption.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.\tThe background of the problem is stated clearly with well summarized review of the literature.\n2.\tThere is a comprehensive comparison of the new constant regret results with existing works.", "weaknesses": "1.\tThe proposed algorithm and analysis follow the algorithm in Vial et al. (2022) closely. The main differences seem to be the layer-dependent quantification in Algorithm 1 and the exit condition 3 in Algorithm 2. It would be better to discuss more clearly how these two modifications contribute to getting rid of the log(K) dependence. \n2.\tSome of notations are used without explanation. For example, $\\lambda$ in algorithm 1, $\\gamma_l$ in Algorithm 2 and Theorem 5.1. Also, how the certified estimator is defined in Algorithm 2 is not clear.\n3.\tSome analysis and results require more clarification: (a) The $\\delta$ condition used in Theorem 5.1 does not match the one used in Lemma C12. (b) It is not very clear how the key results in getting rid of log(k) (Lemma C14 line 765) is derived using $x\\leq a+\\sqrt{bx}$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback. We address your questions as follows:\n\n**Q1. How do the layer-dependent quantization and certified estimator contribute to getting rid of the $\\log K$ dependence?**\n\n**A1.** We would like to highlight the contribution of the layer-dependent quantization and certified estimator in eliminating the $\\log K$ dependence. Vial et al., 2022 applied a global quantization $\\epsilon_{\\text{rnd}} = d / K^2$, making the number of quantized parameters $\\tilde{\\mathbf w}_l$ and $\\tilde{\\mathbf U}_l$ in each layer $l$ depend on $K$. Our method uses unique quantization parameters $k_l$ per layer, thus eliminating the $\\log K$ dependence in regret bound (Lemma D.3).\n\nIn addition to the $\\log K$ term introduced by the quantization, the estimated value function of Algorithm 2 comes from a total of $L = O(\\log K)$ individual regressions. If controlled trivially, the union bound over all $L$ layers would also introduce the $\\log K$ dependency to the final regret bound. The certified estimator further helps by connecting estimations across layers. As a result, during the analysis, we can focus on the concentration of some fixed layer $l_+$, which does not depend on the parameter $K$ (Lemma 6.1). The details are discussed in Section 6, Challenge 1.\n\n---\n**Q2. How is the certified estimator and other notations defined?**\n\n**A2.** The `certified` estimator ensures that each layer's estimate is within a predefined confidence radius from the previous layer. $\\lambda$ is the regularization parameter from Algorithm 1, and $\\gamma_l$ is the confidence radius in Theorem 5.1.\n\n\n---\n**Q3. Why is the $\\delta$ condition different between Theorem 5.1 and Lemma C.12?**\n\n**A3.** Theorem 5.1 integrates Lemmas C.12 and C.14, which hold with probabilities of $1−3\\delta$ and $1−\\delta$, respectively. Applying the union bound, Theorem 5.1 holds with $1−4\\delta$, differing from Lemma C.12. We will clarify this in the revision.\n\n---\n**Q4. Could you clarify the technical details of getting rid of $\\log k$ in Lemma C.14 derived using $x \\le a + \\sqrt{bx}$?**\n\n**A4.** $x \\le a + \\sqrt{bx} \\Rightarrow x \\le 2a + 2b$ is applied in Section D.10, Line 763 after getting \n$$\\textrm{Regret}(K) < \\sum_{k=1}^{K} \\sum_{h=1}^H \\Delta^k_h + \\sqrt{2\\textrm{Regret}(K)H^2\\log(\\textrm{Regret}(K)/\\delta)} + H^2\\log(\\textrm{Regret}(K)/\\delta).\\quad (1)$$\nTaking $x = \\textrm{Regret}(K)$, $a = \\sum_{k=1}^{K} \\sum_{h=1}^H \\Delta^k_h + H^2\\log(\\textrm{Regret}(K)/\\delta)$, and $b = 2H^2\\log(\\textrm{Regret}(K)/\\delta)$, inequality (1) yields\n$$\\textrm{Regret}(K) \\le 2\\sum_{k=1}^{K} \\sum_{h=1}^H \\Delta^k_h + 2H^2\\log(\\textrm{Regret}(K)/\\delta) + 4H^2\\log(\\textrm{Regret}(K)/\\delta) = 2\\sum_{k=1}^{K} \\sum_{h=1}^H \\Delta^k_h + 6H^2\\log(1 / \\delta) + 6H^2\\log(\\textrm{Regret}(K)) \\quad (2)$$\n\nAccording to the fact that $x \\le a \\log x + b \\Rightarrow x \\le 4a \\log (2a) + 2b$, letting $x = \\textrm{Regret}(K), a =  2\\sum_{k=1}^{K} \\sum_{h=1}^H \\Delta^k_h + 6H^2\\log(1 / \\delta)$ and $b = 6H^2$, (2) becomes\n$$\\textrm{Regret}(K) \\le  \\left(8\\sum_{k=1}^{K} \\sum_{h=1}^H \\Delta^k_h + 24H^2\\log(1 / \\delta)\\right)\\log\\left(4\\sum_{k=1}^{K} \\sum_{h=1}^H \\Delta^k_h + 12H^2\\log(1 / \\delta)\\right) + 12H^2.$$\nHiding the logarithmic factors within the $\\tilde O$ notation yields the claimed result in Lemma C.14. We will clarify the technical details of this part in the revision. \n\n---\n**Q5. What’s the connection between the UniSOFT assumption and the result obtained in this paper?**\n\n**A5.** We would like to highlight the connection between the UniSOFT assumption and the result obtained in this paper, which we also discussed in Remark 5.2. First, Papini et al. showed that UniSOFT is necessary for obtaining an `expected` constant regret, suggesting that a $\\log K$ expected regret is unavoidable without UniSOFT. In our result, we proved a `high-probability` constant regret, suggesting that with probability at least $1 - \\delta$, the regret is bounded by a constant $O(d^3H^5\\Delta^{-1} \\log (1 / \\delta))$.\n\nOur result does not violate Papini et al. When translating the high-probability regret bound to an expected regret bound, we have $E[\\text{Regret}(K)] \\le \\tilde O(d^3H^5\\Delta^{-1}\\log(1 / \\delta)) \\cdot (1 - \\delta) + \\delta K =  \\tilde O(d^3H^5\\Delta^{-1}\\log K)$. Setting $\\delta = 1 / K$ will lead to a logarithmic expected regret bound. In short, a `high-probability` constant regret bound results in a logarithmic `expected` regret bound.\n\nOn the other hand, the constant regret upper bound in Papini et al. is obtained under the UniSOFT assumption. Ours, in contrast, obtain the same high-probability constant regret upper bound without the UniSOFT, which is the first constant regret bound without prior assumptions in the literature.\n\nIn conclusion, the UniSOFT assumption is a necessary condition for expected constant regret but not a necessary condition for high-probability constant regret. Our result is the first work showing the high-probability constant regret bound without this assumption\n\n---\n**Q6. What’s the experimental result and the intuitive understanding of the constant regret?**\n\n**A6.** We have added some experiments on the synthetic dataset to verify the performance of the algorithm, which is presented in the global response. In addition to the experimental results, the understanding of constant regret is quite intuitive: A constant regret bound suggests that the total mistakes made by the RL agent are finite, with high probability. Taking the two-armed stochastic bandit as an example, if the gap between the two arms is strictly positive, it only takes finite time to distinguish the optimal arm from the suboptimal arm. Thus, the total mistakes made by the RL agent are finite.\n\n---\n- Vial, Daniel, et al. \"Improved algorithms for misspecified linear markov decision processes.\" AISTATS, 2022\n- Papini, Matteo, et al. \"Reinforcement learning in linear mdps: Constant regret and representation selection.\" NeurIPS, 2021", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HVFhN4Jai3", "reviewer": "Reviewer_YEKy", "summary": "The paper studies constant regret guarantees for linear MDPs. The main result is the first algorithm with this guarantee. The algorithm is a modification of LSVI-UCB with a careful quantization technique and some form of action elimination. This improves upon the regret of previous works by a factor of $\\log K$ where $K$ is the number of episodes.\nUnlike previous works, the algorithm is robust to some degree of model mispecification and does not need to know it in advance.", "questions": "See above.", "limitations": "N/a", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The method is robust to some model mispecification and does not need to know it in advance.\n2. The regret guarantee is tighter compared to previous works.\n3. The algorithm is computationally efficient in the sense that it runs in polynomial time in the problem parameters.\n4. There are significant technical challenges in the work. In particular the careful quantization required to avoid dependence on $K$ and the refined analysis of the regret bound by the suboptimality gaps.", "weaknesses": "1. While it's challenging to achieve regret that is independent of $K$, I do not see this as a significant improvement over the logarithmic dependence. This is especially true since it is not clear whether the correct polynomial dependence on the remaining parameters has been established. Moreover, this improvement is only relevant in the regime of a fixed success probability $\\delta$, which is often dependent on $K$, e.g., if bounding the expected regret.\n2. The improvement to the regret comes at a significant increase to the algorithm's complexity. It's not clear whether this is necessary. For example, are you certain that the quantization cannot be replaced by a more careful analysis of the value cover? Why do you need both bonuses and action elimination and sample rejection? The runtime complexity also seems higher (though this is a minor concern). If you think these modifications are indeed necessary, perhaps you could demonstrate this with experiments.\n3. While I am not familiar with better results, the dependence on the worst case gap weakens the result. Do you think it is possible to achieve a better dependence? e.g. on the average inverse gap with respect to the optimal policy.\n4. The writing is not very consistent with some places having phrasing and grammatical issues (e.g., quantification should be quantization and many more).\n5. The algorithm needs to be better explained. While it seems the authors made significant efforts in this regard, many parts of the algorithm remain rather unclear. For example, the bonuses are not immediately apparent. As I understand it, you use a quantization of the standard bonus. It would be much easier for the reader if this is made explicit in the algorithm and explained. Other examples are the action elimination and sample rejection whose purpose is unclear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed feedback, and we address your questions as follows:\n\n**Q1. Why is it significant to improve the logarithmic dependence on $K$?**\n\n**A1.** We would like to first highlight that achieving constant regret is actually an important topic in bandits (Abbasi et al., Papini et al., 2021a, Zhang et al.,) and RL (Papini et al., 2021b). This is not merely shaving off a $\\log$ factor but a stronger performance guarantee than logarithmic regret. Specifically, the constant regret bound indicates that the agent incurs only a finite number of mistakes when making decisions over an infinite run, whereas the number of mistakes can become arbitrarily large if the regret guarantee is only logarithmic.\n\n---\n**Q2. Is the correct polynomial dependence on the remaining parameters established?**\n\n**A2.** We would like to point out that our algorithm suggests a $\\tilde O(d^3H^5\\Delta^{-1})$ polynomial dependence on the parameters $H, d, \\Delta^{-1}$, which is consistent with previous literature (He et al., Papini et al.), as discussed in Table 1. Therefore, we are confident that the polynomial dependence on these parameters is correct.\n\n---\n**Q3. What is the necessity of each component in the algorithm?**\n\n**A3.** We believe both the certified estimator and the layer-dependent quantization are necessary for our theoretical analysis. As discussed in Section 6, certified estimators build the connection between different layers $l$ so that we can avoid taking the union bound over all $L = \\log K$ layers during the concentration. Layer-dependent quantization removes the additional $\\log K$ dependence introduced during the covering of the value function in Vial et al..\n\nIn addition, we have also conducted experiments on a synthetic dataset as presented in the response to all reviewers. In particular, the certified estimator helps stabilize the estimation so that the algorithm can achieve lower regret when the misspecification grows larger. It is true that the quantization does not significantly contribute to improving the regret, which aligns with our intuition since the numerical results are intrinsically discrete and quantized. In addition, experimental results also suggest that neither the certified estimator nor the quantization decreases the efficiency of the algorithm.\n\n---\n**Q4.** Why is the analysis based on the minimal sub-optimality gap instead of other gaps (like averaged gaps)?\n\n**A4.** The averaged sub-optimality gap, as you suggested, can only be applied to the tabular bandits setting, to the best of our knowledge. In reinforcement learning with function approximation, the number of actions can be arbitrarily large, making it difficult to define the ‘averaged’ sub-optimal gap in this setting.\n\n---\n**Q5. Explain the details of the algorithms? Why do you need both bonus and arm elimination?**\n\n**A5.** First, we would like to clarify that our algorithm does not use the `reject sampling`, instead, we call the exit condition in Line 11 in Algorithm 2 `certified estimator` to ensure that the optimistic estimator for the current layer $l$ should be always greater than the pessimistic estimator from the previous layer $l-1$, and vice versa. Therefore, in case the concentration of layer $l$ fails, it will be detected and the performance of the estimation is not affected since the certified estimator (line 11) is triggered and the algorithm returns the estimation from the previous layer. There is no connection between the certified estimator and reject sampling since neither of the $V, \\hat V, \\check V$ are sampled from some distribution and our algorithm is a learning algorithm instead of a sampling algorithm. \n\nSecond, regarding the bonus and the arm elimination, we quantize the parameter $\\mathbf w$ and $\\mathbf U$ in Line 8, Algorithm 1, in order to control the quantity of the function set. Both of the bonus term $\\lVert\\mathbf {\\phi}(s, a) \\rVert_{\\tilde {\\mathbf U}}$ and $Q$ functions are calculated using this quantized $\\tilde {\\mathbf w}$ and $\\tilde {\\mathbf U}$. In Algorithm 2, for each layer $l$, the action with a bonus term larger than $O(2^{-l})$ will directly get selected for exploration. \n\nThird, Regarding the arm elimination process, for each layer $l$ in Algorithm 2, we eliminate all actions $a$ which $Q_{h, k}^l(s, a)$ is smaller than the estimated optimal value function $V_{h, k}^l(s)$ by $4 \\cdot 2^{-l}$. As a result, arm elimination shrinks the arm set before proceeding to the next phase $l+1$. Since the algorithm pursues higher decision in the deeper layer, which is more vulnerable to model misspecification, the arm elimination tries to remove the suboptimal arm in the shallow layers in order to deliver a more robust decision.  \n\nAdditionally, in response to your question about the simultaneous use of bonus and arm elimination, it's important to note that this combination is commonly employed in bandits (Chu et al., Takemura et al.) and reinforcement learning (Vial et al.). Therefore, our design choice is conventional and aligns with standard strategies in the field.\n\n---\n- Abbasi-Yadkori et al. \"Improved algorithms for linear stochastic bandits.\" NeurIPS, 2011\n- Papini, Matteo, et al. \"Leveraging good representations in linear contextual bandits.\" ICML, 2021a\n- Papini, Matteo, et al. \"Reinforcement learning in linear mdps: Constant regret and representation selection.\" NeurIPS, 2021b\n- Zhang, Weitong, et al. \"On the interplay between misspecification and sub-optimality gap in linear contextual bandits.\" ICML, 2023.\n- Vial, Daniel, et al. \"Improved algorithms for misspecified linear markov decision processes.\" AISTATS, 2022\n- Chu, Wei, et al. \"Contextual bandits with linear payoff functions.\" AISTATS, 2011\n- Takemura, Kei, et al. \"A parameter-free algorithm for misspecified linear contextual bandits.\" AISTATS, 2021", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We first thank all reviewers for their valuable feedback. 

In response to Reviewers 8jf2, 33Lb, and YEKy, we added experiments on synthetic datasets to verify the performance of the algorithm and the contribution of each component. Specifically, we consider a linear MDP with $S = 4$, $A = 5$, $H = 2$, and $d = 8$. Each element in the feature vector $\phi(s, a)$ and $\mu(s')$ is generated by a uniform distribution $U(0, 1)$. Subsequently, $\phi$ is normalized to ensure that $P(s' | s, a)$ is a probability measure, i.e., $\phi(s, a) = \phi(s, a) / \sum_{s'} \phi^\top(s, a) \mu(s')$. The reward is defined by $r(s, a) = \phi^\top(s, a) \theta$, where $\theta \sim N(0, I_d)$.

We also consider adding model misspecification to the transition $P$ and reward function $r$. For a given misspecification $\zeta$, the ground truth reward function is defined by $r(s, a) = \phi^\top(s, a) \theta + Z(s, a)$, where $Z(s, a) \sim U(-\zeta, \zeta)$. When adding the model misspecification to the transition kernel, we first random sample a subset $\mathcal S_+ \subset \mathcal S$ such that $|\mathcal S_+| = |S| / 2$. Then the misspecified transition kernel is then generated by 
- For $s' \in \mathcal S_+$, $P'(s' | s, a) = P(s' | s, a) + \zeta / S$
- For $s' \notin \mathcal S_+$, $P'(s' | s, a) = P(s' | s, a) - \zeta / S$

We can verify that $\lVert P(\cdot | s, a) - P'(\cdot | s, a)\rVert_{TV} = \zeta$.

We investigated the misspecification level from $\zeta = 0, 0.01, \cdots, 0.3$ in 16 randomly generated environments over 2000 episodes. We report the cumulative regret and runtime with respect to different misspecification levels. Additionally, we performed an ablation study by 
1. removing the certified estimation (Algorithm 2, Line 11) and 
2. removing the quantization (Algorithm 1, Line 8). 

The results of these configurations are presented in the following table. The detailed regret for all misspecification level is presented in Table 1 in the attached PDF. In Figure 1 of the attached PDF, we plot the cumulative regret for 2000 episodes with respect to the misspecification level $\zeta. The cumulative regret curve is plotted in Figure 2 of attached PDF.

|Cert.Est.|Quant.  | $\zeta=$0 | 0.05 | 0.1 | 0.15 | 0.2 | 0.25 | 0.3 | Running Time |
|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|
|$\times$|$\times$| **754.84 $\pm$ 221.06** | 868.10 $\pm$ 278.24 | 1160.24 $\pm$ 436.41 | 1583.37 $\pm$ 690.67 | 2160.15 $\pm$ 794.80 | 2644.05 $\pm$ 823.24 | 3206.85 $\pm$ 825.13 | 1654.76 |
|$\times$|$\checkmark$| 755.21 $\pm$ 220.71 | 868.25 $\pm$ 278.19 | 1159.56 $\pm$ 436.90 | 1583.99 $\pm$ 690.68 | 2160.03 $\pm$ 795.28 | 2643.40 $\pm$ 823.50 | 3206.92 $\pm$ 824.89 | 1654.21 |
|$\checkmark$|$\times$| 758.26 $\pm$ 220.62 | **845.62 $\pm$ 297.89** | 1015.95 $\pm$ 321.12 | **1154.01 $\pm$ 340.98** | 1290.21 $\pm$ 380.01 | **1433.30 $\pm$ 544.80** | **1438.27 $\pm$ 471.33** | 1599.66 |
|$\checkmark$|$\checkmark$| 758.63 $\pm$ 220.23 | 845.80 $\pm$ 297.92 | **1015.41 $\pm$ 321.57** | 1154.45 $\pm$ 341.32 | **1289.96 $\pm$ 380.03** | 1434.09 $\pm$ 544.40 | 1438.55 $\pm$ 471.24 | 1593.38 |

The experimental results suggest several key findings that support our theoretical analysis: 
- When the misspecification level is low, it is possible to achieve constant regret, where the instantaneous regret in the final rounds is approximately zero. 
- The certified estimator and the quantization do not significantly affect the algorithm's runtime. In contrast, the certified estimator provides an ‘early-stopping’ condition in Algorithm 2, which slightly reduces the algorithm's runtime. In particular, our algorithm yields a computational complexity of $O(d^2AHK^2\log K)$, which is the same as (Vial et al., 2022) and only $\log K$ greater than the vanilla LSVI-UCB (Jin et al., 2020) due to the multi-phased algorithm.
- The certified estimator helps the algorithm by providing robust estimation in the presence of misspecification. As shown in the table, using the certified estimator does not make a significant difference when the misspecification level $\zeta$ is low, but it becomes significant as the misspecification level increases. 
- The quantization does not contribute significantly to the results, as the numerical results are intrinsically discrete and quantized. In Figure 2 of the attached PDF, the regret curve with quantization and the one without quantization are highly overlapped.


We hope these results help clarify the theoretical insights of our work, and we will include this in the revision.

---
- Jin, Chi, et al. "Provably efficient reinforcement learning with linear function approximation." COLT, 2020
- Vial, Daniel, et al. "Improved algorithms for misspecified linear markov decision processes." AISTATS, 2022

Meta-review: This papers studies the linear MDP setting and achieves a high probability regret bound that is independent of the number of episodes, while past work had a log(K) dependence. An expected regret bound necessarily has a log(K) dependence, so the novelty holds when the high probability bound holds with probability 1-delta where delta is independent of K. Achieving this result required a careful union bound and analysis of a novel algorithm.

Given that such results hold for bandits, this result is not particularly surprising but nevertheless was unknown. Reviewers were skeptical of the practical value of the result given that the log(K) is necessary for an expected regret bound, and the questionable dependence on the more relevant parameters like the dimension d and horizon H. Indeed, there are many papers that suggest no greater than a d^2 H^3 dependence (versus d^3 H^5) is optimal (e.g., Zannette, Lazaric et al 2020). The authors' defensive reaction to this well-justified line of inquiry was a rebuttal misstep. We suggest the authors more suitably address this dependence in the paper and comment on ways to improve the algorithm and/or analysis. Nevertheless, the techniques and technical content may warrant a valuable contribution.
Decision: Accept (poster)