A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation
Authors: Heyang Zhao
Jiafan He
Quanquan Gu
Venue: NeurIPS 2024 poster (2024)
Keywords: Reinforcement learning
function approximation
Primary area: reinforcement_learning

Abstract: The exploration-exploitation dilemma has been a central challenge in reinforcement learning (RL) with complex model classes. In this paper, we propose a new algorithm, Monotonic  Q-Learning with Upper Confidence Bound (MQL-UCB) for RL with general function approximation. Our key algorithmic design includes (1) a general deterministic policy-switching strategy that achieves low switching cost, (2) a monotonic value function structure with carefully controlled function class complexity, and (3) a variance-weighted regression scheme that exploits historical trajectories with high data efficiency. MQL-UCB achieves minimax optimal regret of $\tilde{O}(d\sqrt{HK})$ when $K$ is sufficiently large and near-optimal policy switching cost of $\tilde{O}(dH)$, with $d$ being the eluder dimension of the function class, $H$ being the planning horizon, and $K$ being the number of episodes. 
   Our work sheds light on designing provably sample-efficient and deployment-efficient Q-learning with nonlinear function approximation.

A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation
Heyang Zhao
Department of Computer Science University of California, Los Angeles
Los Angeles, CA 90095 hyzhao@cs ucla.
Jiafan He
Quanquan Gu
Department of Computer Science University of California, Los Angeles Los Angeles, CA 90095 j jiafanhhe9@uclle edu
Department of Computer Science University of California, Los Angeles Los Angeles, CA 90095 gguõcs wuw.auclaeeeeee.o.
Abstract
The exploration-exxlloiation dilemma has been central challenge in reinforcement learning (RL) with complex model classes. In this paper, we propose new algorithm, Monotonic Q- Q-Learning with Upper Confidence Bound (MQL-UCB) for RL with general function approximation. Our key algorithmic design includes (1) a general deterministic policy-switching strategy that achieves low switching cost, (2) monotonic value function structure with carefully controlled function class complexity, and (3)
setiance-weighte regression scheme that exploits historical trajectories with high data efficiency. MQL-UCB achieves minimax optimal regret (dd/H(( when is sufficiently large and near-optimal policy switching cost of (dH)), with d being the eluder dimension of the function class, H being the planning horizon, and K being the number of episodes. Our work sheds light on designing provably sample-efficient and deployment-effiee efficient Q-learnng with nonlinear function approximation.
1 Introduction
In reinforcement learning (RI), learner interacts with unknown environment and aims maximize the cumulative reward. As one of the most mainstream paradigms for sequential decision- making, RL has extensive applications in many real-world problems (Kober al., 2013 Mnih et al., 2015; Lillicrap et al., 2015; Zoph and Le, 2016; Zheng et al., 2018). Theoretically, the RL problem is often formulated as Markov Decision Process (MDP) (Puterman, 2014). Achieving the optimal regret bound for various MDP settings has been a long-stann standing fundamental problem in RL research. In tabular MDPs where the state space S and the action space A are finite, the optimal regret bound has been well eola-sstabl,she, ranging from the episodic setting (Azar et al., 2017: Zanette and Brunskill, 2019; Simchowitz and Jamieson, 2019; Zhang et al., 2020), average-reward setting (Zhang and Ji, 2019) to the discounted setting (He et al., 2021b). Nevertheless, these regret guarantees are intolerably large in many real-world applications, where the state space and the action space A are often large or even infinite.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

As is commonly applied in iiniiattions,,uuettii approximation has been widely studied by theorists demonstrate the generalization across large state-action spaces, proving the performance guarantees of various RI. algorithms for specific function classes. There are recent works on RI with linear function approximation under different assumptions such as linear MDPs (Yang and Wang, 2019; Jin et al., 2020), linear mixture MDPs (Modi et al., 2020; Ayoub et al., 2020; Zhou et al., 2021a). Among them, Zhou et al. (2021a) achieved nearly optimal regret bounds for linear mixture MDPs through model-based approach adopting variance-weighted linear regression. Later, Hu et al. (2022) proposed LSVI-UCB+ algorithm, making an attempt to improve the regret for linear MDP through an over-optimistic value function approach. However, their analysis was later discovered to suffer from a technical issue (Agarwal et al., 2022: He et al., 2022). To fix this issue, Agarwal et al. (2022) introduced similar over-optimistic value functions to construct a monotonic variance estimator and a non-Markov policy, achieving the first statistically optimal regret for linear MDPs. They also proposed novel algorithm dubbed VOQL for RL with general function approximation. Concurrently, He et al. (2022) proposed LSVI-UCB++, which takes a different approach and employs rare-switching technique to obtain the optimal regret. In a parallel line of research, there has been a growing body of literature proposing more general frameworks to unify sample efficient RL algorithms, e-g., Bellman rank (Jiang et al., 2017), Witness rank (Sun et al., 2019), eluder dimension (Russo and Van Roy, 2013), Bellman eluder dimension (Jin et al., 2021), 1), Bilinear Classes (Du et al., 2021),
Coefficient (Foster al., 2021), Admissible Bellman Characterization (Chen et al., 2022) and Decoupling Coefficient (Agarwal and Zhang, 2022a,b). However, when applying these frameworks linear MDPs, none them can achieve the minimax optimal regret. To our knowledge, Agarwal et al. (2022) is the only algorithmic framework achieving optimal regret for RL beyond linear function approximation. Since VOQI. requires a non-Markov planning procedure, where the resulting policy does not act greedily with respect to a single optimistic value function, it is natural to ask
Can we develop a RL algorithm with Markov policy' to solve MDPs with general function approximation and achieve the optimal regret?
While the sample efficiency of RL algorithms for MDPs with nonlinear function classes has been comprehensively researched, deployment efficiency (Matsushima et al., 2020) is also a major concern in many real-world application scenarios. For example, in recommendation systems (Afsar et al., 2022), it may take several weeks to deploy a new recommendation policy. On the other hand, the system is capable of collecting an enormous amount of data every minute implementing fixed policy, As a result, it is computationally inefficient to change the executed policy after each data point is collected resolve this issue, Bai et al. (2019) first introduced the concept of switching cost, defined as the number of policy updates. Following this concept, a series of RL algorithms have been proposed on the theoretical side with low switching cost guarantees (c.g., Zhang et al.. 2020; Wang et al., 2021: Qiao et al., 2022; Kong al., 2021; Velegkas et al., 2022; Li et al., 2023). Xiong et al. (2023) considered low-switching RL with general function approximation, which achieves O(dH) switching cost. However, their algorithm has intractable planning phase and is not statistically optimal. Kong et al. 1),1), Velegkas et al. (2022), and Li et al. (2023) considered RL with general function approximation, all of which achieved the switching cost of (dd Hpolylog( (K)), where d is the eluder dimension of the underlying function class, H is the planning horizon, and K is the number of episodes. In contrast, Gao al. (2021) proved an Q(d log d) lower bound of switching cost for any deterministic algorithms in learning linear MDPs. Therefore, the following question remains open:
is demanded by most of the online RL algorithms in theoretical studies. To
Can we design an efficient algorithm with (dH)) switching cost for MDPs with bounded eluder dimension?
In this paper, we answer the above two questions simultaneously by proposing a novel algorithm Monotonic Q-Learning with UCB (MQL-UCB) with all the aforementioned appealing properties. At the core of our algorithmic design are the following innovative techniques:
' Markov policy means that the action chosen by the policy only depends on the current state instead of the prefix trajectory. It is more aligned with the empirical RL approaches, since the estimated value function is not well-defined under non- Markov policy.
2

---

Table 1: A comparison of existing algorithms in terms of regret and switching cost for linear MDP and general function class with bounded eluder dimension and Bellman completeness. The results hold for in-homogeneous episodic RL with horizon length H, number of episodes K' where the total reward obtained in an episode is not larger than 1. For regret, we only present the leading term when K' is large enough compared to other variables and hide goly-logari factors in K, d or dim, H and the constant. For linear MDPs, d is the dimension of the feature vectors. For general function class, dim is a shorthand of the eluder dimension of the underlying function class, N is the covering number of the value function class, and NA.A is the covering number of the state-action space.
Algorithm
Regret
of Switches
Model Class
LSVI-UCB
K
(Jin et al., 2020)
LSVI-UCB-RareSwice RareSwitch
Ö(dH)
Linear MDPs
(Wang et al., 2021)
LSVI-UCB++
dvHK
Ö(dH)
(He et ul., 2022)
FLLVV
( Vlg N log Ns.A HVK
K
(Wang al., 2020a)
GOLF
log N. HVK
K
(Jin al., 2021)
Bounded eluder dimension + Completeness
VOQI.
V dim(F) log N HK
(ddi((F)
(Agarwal et al., 2022)
MQL-UCB
v (F) log IIK
O(dim(F)II)
(Theorem 4.1)
We propose novel policy-switching strategy based on the cumulative sensitivity of historical data. To the best of our knowledge, this the first computationally -racctaallll deterministic switchig algorithm for RL with general function approximation which achieves OdH)) switching cost. We also prove nearly matching lower bound for any algorithm with arbitrary policies including both deterministic and stochastic policies (See Theorem B. I). Previous approaches for low switching cost in RL with general function approximation are sampling bbaedd (Kong et al., 2021; Velegkas et al., 2022; Li et al., 2023) and highly coupled with a sub-sampling technique used for regression, making it less efficient. When restricted to the linear case, sampling- campling-based rare-switching has worse switching cost of (d H) (Section 3.3 in Kong al. 2021; Theorem 3.3 in Velegkas et al. 2022; Section C in Li et al. 2023) than that in Wang et al. (2021).
With the novel policy-switching scheme, we illustrate how to reduce the complexity of value function classes while maintaining a series of monotonic value functions, strictly generalizing the LSVI-UCB+ algorithm (He et al., 2022) to general function class with bounded eluder dimension. Based on the structure of the value functions, we further demonstrate how MQL-UCB achieves a variance-dependern regret bound that can gracefully reduce to a nearly constant regret for deterministic MDPs. While the worst case, our algorithm still attains a nearly minimax optimal regret guarantee. Our work is the first work for RI. with general function approximation that achieves the nearly minimax optimal regret when specialized linear MDPs, while still enjoys simple Markov planning phase.
is worth noting that recently, Qiao et al. (2023) also considered RL with low-switching cost beyond linear function approximation, i.e., MDPs with low inherent Bellman error (Zanette al., 2020b) and generalized linear MDPs (Wang et al., 2020b). Their approach can be seen as a slight extension of RL. with low-switching cost for linear MDPs, since in both settings, the covariance matrix still exists and they can still use the determinant of the covariance as a criterion for policy switching.
Notation. We use lower case letters to denote scalars and use lower and upper case bold face letters to denote vectors and matrices respectively. We denote by [ni] the set (1,..., nn). For two positive sequences {ax) and {b,,} with n = 1, 2,2,.... we write a, = (b,,) ) if there exists an absolute constant C > such that an I Cb, holds for all n 2 and write an s2(b,) if there exists an absolute constant > 0 such that a, 2 Cbn holds for all 2 1. We use Ō(-) to further hide the polylogarithmic factors except log-covering numbers. We use { to denote the indicator function.
3

---

2 Preliminaries
2.1 Time-Inhomogenneous Episodic MDP
We consider a time-inhomogencous episodic Markov Decision Process (MDP), denoted by tuple M (M, A. H, (I" ( {ra (r1))=1) 1). Here, S and A are the spaces state and action, respectively, H is the length of each episode, Ir,, : S x A x S - [0, 1] is the transition probability function at stage h which denotes the probability for state to transfer to the next state s' with current action a, and rh S x A + j0, 1] is the deterministic reward function at stage h. A policy := { > is collection of mappings Th from an observed state s to the simplex of action space A. For any policy ग = Th h== and stage h E [H], we define the value function VØ (s) and the action-value function (s, a) as follows:
H Σ W=a+1
a (sw, (S)))) = s, = a V. (8) = (x) (s)),
(x = (s) +E
where sw++1 (nr(- anr). Then. we further define the optimal value function Vi and the optimal action-value function 27 as ()( max, V (s) and Q7 (s,a) max, Q7 a). For simplicity, we assume the total reward for each possible trajectory (81, 01, SH, an) satisfies Di (sh. an) S Under this assumption, the value function V₂(() and Q7 (.--) bounded in []. For any function V S + R and stage h E [H]. we define the following first-order Bellman operator Th and second-order Bellman operator T on function V:
V an) Beati [r + ((S++1) mn): TV2 (sn mn) Ben.r (Th ((8++1)) on]
where 86+1 PP,(-1st on) and Pı (H an). For simplicity, we further define [TP [ a) Egr (-Is.a) (s') and [V, (] a) = Vs o₂) (T% (s,, (s,)) Using this notation, for each stage h E [H], the Bellman equation and Bellman optimality equation take the following forms:
Q7 Tv (s.
Q'(s,a) Th (s.
where (++ = (++ = 0. At the beginning of each episode At E [K], the agent selects a policy Th to be executed throughout the episode, and an initial state st is arbitrarily selected by the environment. For each stage / E [H]. the agent first observes the current state sy chooses an action following the policy . then transits to the next state with o ~ Pa af) and reward (sh, a.). Based on the protocol, we defined the suboptimality gap in episode i as the difference between the value function for selected policy r² and the optimal value function (s VT (sf). Based on these definitions, we can define the regret in the first K episodes as follows:
Definition 2.1. For any RL algorithm Alg, the regret in the first K episodes denoted by the sum of the suboptimality for episode l = I,...,K. K,
Regret( K) = Σ (+ - (T*), k=1
where n² is the agent's policy at episode k.
2.2 Function Classes and Covering Numbers
Assumption 2.2 (Completeness). Given J := (Fr M which is composed of bounded functions fa : S x A + [0, L]. We assume that for any function V S - [0, 1] there exists fi. f2 E F, such that for any (8, a) E A.
Ex (r, a) V(5') fi(s, a), and Bxara((aa)) + = fz
We assume that I. 0(1) throughout the paper.
Remark 2.3. Completeness is fundamental assumption in RL with general function approximation, as recognized in Wang al. (2020b); Jin et al. (2021); Agarwal et al. (2022). Our assumption the same that in Agarwal et al. (2022) and is slightly stronger than that in Wang et al. (2020a) and

---

Jin et al. (2021). More specifically, in Wang et al. (2020a), completeness is only required for the first-order Bellman operator. In contrast, we necessitate completeness with respect the second-order Bellman operator, which becomes imperative during the construction of variance-basee based weights. Jin et al. (2021) only requires the completeness for the function class Fh+1 (TrJh++1 C F1.). However, the GOLF algorithm (Jin et al., 2021) requires solving an intricate optimization problem across the entire episode. In contrast, we employ pointwise exploration bonuses as an alternative strategy, which requires the completeness for function class V = (V : S + [0, 1]} i.e., T C Fr. The completeness assumption on the second moment is first introduced by Agarwal et al. (2022), and is crucial for obtaining tighter regret bound. More specifically, making use of the variance of the value function at the next state is known to be crucial to achieve Manimax-optiman regret bound in RL ranging from tabular MDPs (Azar et al., 2017) to linear mixture MDPs (Zhou et al., 2021a) and linear MDPs (He et al., 2022). In RL with general function approximation, the second-moment compleness assumption makes the variance of value functions computationally tractable.
Definition 2.4 (Generalized Eluder dimension, Agarwal et al. 2022). Let Z 0, a sequence of state-action pairs Z = { and a sequence of positive numbers a = ho The gener- alized Eluder dimension of a function class F S A - [0, L] with respect to defined by dima,r (FF) == sup22o:/2|=TTo222 dim(F FF Z.
1 () (z: 2/1 11-11 (-)))
dim(F, 200 = Σ min 1, o7
(f1()) f2(2))²
sup (2t fI.fETJ
21 of (fi(z)) - fz(z.))² +X
We write dim H-1 Enem (ein,,T(Fi) for short when F is a collection of function classes F = ( in the context.
Remark 2.5. The D3. quantity has been introduced in Agarwal et al. (2022) and Ye et al. (2023) to quantify the uncertainty of state-action pair given collected dataset with corresponding weights. was inspired by Gentile et al. (2022) where an unweighted version of uncertainty has been defined for active learning. Prior to that, Wang et al. (2020a) introduced a similar "sensitivity" measure to determine the sampling probability in their sub-sampling framework. As discussed in Agarwal et al. (2022), when specialized to linear function classes, Dix(2e: [t--1], [t-1)) can be written as the elliptical norm ||; 112 x- where Σ₁_1 is the weighted covariance matrix of the feature vectors 2[r-1]-
Definition 2.6 (Bonus oracle D3.). In this paper, the bonus oracle is denoted by D3, which computes the estimated uncertainty of a state-action pair 2 = (s, a) E S x A with respect to historical data 9|-11 and corresponding weights Ø[--1]. In detail, we assume that a computable function (s 1111
(2; 11-1), (t-1) satisfies (x:F 11 2)? E [1, C). where C is fixed constant.
Remark 2.7. Agarwal et al. (2022) also assumed access to such a bonus oracle defined in Defini- tion 2.6, where they assume that the bonus oracle finds proper bonus from finite bonus class (Definition 3, Agarwal et al. 2022). Our definition is slightly different in the sense that the bonus class is not assumed to be finite but with finite covering number. Previous works by Kong et al. (2021) and Wang et al. (2020a) proposed a sub-sampling idea to compute such a bonus function efficiently in general cases, which is also applicable in our framework. In similar nonlinear RL setting, Ye et al. (2023) assumed that the uncertainly D3. can be directly computed, which a slightly stronger assumption. But essentially, these differences in bonus assumption only lightly affect the algorithm structure.
Definition 2.8 (Covering numbers of function classes). For any O, we define the following covering numbers of the involved function classes:
1. For each h E [H], there exists an e-cover c) C FF with size [(F,,, c) < [FF E). such that for any f E F. there exists f' C(Fr. e). such that |l - f'l xo S e. For any e > 0, we define the uniform covering number of FF with respect to e as Nz(() == ma N (FF,,e). e).
2. There exists a bonus class B 8 A + IR such that for any / 2 žμ E (S A)¹, o RR. the oracle defined in Definition 2.6 Dz(: (+: 2[4] m1) is in B.
For bonus class B, there exists an coover C(B, <) C with size ((B,e) & N(B,e), c), such that for any b E B, there exists 6' e C(B,e). such that b b' bl Se.
5

---

Remark 2.9. In general function approximation, it is common to introduce the additional assumption on the covering number of bonus function classes. For example, in Ye et al. (2023), Agarwal and Zhang (2022a), and Di et al. (2023), the covering number of the bonus function class is bounded.
3 Algorithm and Key Techniques
In this section, we will introduce our new algorithm, MQL-UCB. The detailed algorithm is provided in Algorithm 1. Our algorithm's foundational framework follows the Upper Confidence Bound (UCB) approach. In detail, for each episode k: [K], we construct an optimistic value function QR,A(s, a) during the planning phase. Subsequently, in the exploration phase, the agent interacts with the environment, employing a greedy policy based on the current optimistic value function Qx,A a). Once the agent obtains the reward r and transitions to the next state + these outcomes are incorporated into the dataset, contributing to the subsequent planning phase. We will proceed to elucidate the essential components of our method.
3.1 Rare Policy Switching
For MQL-UCB algorithm, the value functions Qk.h. Q along with their corresponding policy Tk- undergo updates when the agent collects a sufficient number of trajectories within the dataset that could significantly diminish the uncertainty associated with the Bellman operator Th, (::.) through the weighted regression. In the context of linear bandits (Abbasii Yadkori et al., 201 1) or linear MDPs (He et al., 2022), the uncertainty pertaining to the least-square regression is quantified by the covariance matrix Σg. In this scenario, the agent adjusts its policy once the determinant of the covariance matrix doubles, employing a determinant-basee function approximation setting, such method is not applicable in the absence of the covariance matrix which serves as a feature extractor in the linear setting. Circumventing this issue, Kong et al. (2021) proposed a samplingmmaanae Their subsampling technique is inspired by Wang et al. (2021), 1), which showed that one only needs to maintain small subset of historical data to obtain a sufficiently accurate least-square estimator. Such subset can be generated sequentially according to the sensitivity of a new coming data point. However, their approach leads to a switching cost of (d H), which does not match the lower bound in linear MDPs proposed by Gao et al. (2021).
criterion. Nevertheless, in the general
method to achieve low-switching properties in nonlinear RL.
To resolve this issue, we proposed a more general deterministic policy-updating framework for non- linear RL. In detail, we use D3, (zi,ni F( -kta) to evaluate the information collected at the episode i, given the last updating klast. Once the collected information goes beyond a threshold from last updating, i.e.,
Σ 1
1 D' (2..1 ((hmaa O ( 1,,) X.
(3.1)
the agent will perform updates on both the optimistic estimated value function and the pessimistic value function. Utilizing the D3, -based criterion, will show that the number of policy updates can be bounded by O(H dim x (F)). This further reduces the complexity of the optimistic value function class and removes additional factors from a uniform convergence argument over the function class. Specifically, we showcase under our rare-switching framework, the c-covering number of the optimistic and the pessimistic value function class at episode is bounded by
N.(k) == (c/() N(B, e/23x))
(3.2)
where 3x is the maximum confidence radius as shown in Algorithm 1, which will be specified in Lemmas G.3 and G.4, I is the number of policy switches before the end of the k-th episode according to Algorithm 1.
3.2 Weighted Regression
The estimation of Q function in MQL-UCB extends LSVI-UCB proposed by Jin et al. (2020) to general function classes. While the estimators in LSVI-UCB are computed from the classic least

---

squares regression, we construct the estimated value function fk. for general function classes by solving the following weighted regression:
fu. = argmin Σ
(fu(sh oh) - r/. Va
1E[k-1] o.h
EN
In the weighted regression, set the weight 0, as
kth = max (JK.A, a, D' (2: 11. I[,)),,))
where ki is the estimated variance for the stochastic transition process, Dy, 221 11,b. 11,A) denotes the uncertainty of the estimated function fr, conditioned on the historical observations and
x²a = log (2 + - +
(+(e) N²(K))
(3.3)
is used to properly balance the uncertainty across various state-action pairs. It worth noting that Ye et al. (2023) also introduced the uncertainty-awar variance in the general function approximation with a distinct intention to deal with the adversarial corruption from the attacker. In addition, according to the weighted regression, with high probability, the Bellman operator TT V.,A satisfies:
A+ Σ कस (FEA of) Ta Ve. (sh, at) B
1]
where 3r is the exploration radius for the Q functions, which will be specified in Theorem 4.1. According to the definition of Generalized Eluder dimension, the estimation error between the estimated function fI. and the Bellman operator is upper bounded by:
(s,0) To (e. Ba (2; (1 (1-1))))
Therefore, introduce the exploration bonus bu,n and construct the optimistic value function (k, a)..e., (s. ~ a) + by,n a), where (s.n(s, = 3x D5 2 -1..). Inspired by Hu et al. (2022); He et al. (2022); Agarwal et al. (2022), in order to estimate the gap between the optimistic value function (s,n(s) and the optimal value function V (s), we further construct the pessimistic estimator fk. by the following weighted regression
JM argmin
1 (Sa (sh,, r Ven+z((h+1))), INEF 4E[k-1] oi
Σ
and introduce a negative exploration bonus when generating the pessimistic estimator. Qu, (8, a) R f (s, a) b (s, a), where (s, a) = 3.. ((s, a); 1],- [[-1]]A-- Different from Agarwal et al. (2022), the pessimistic value function FR,A a is computed from similar weighted-regresse scheme as in the case of the optimistic estimator, leading to tighter confidence set.
3.3 Variance Estimator
In this subsection, we provide more details about the variance estimator dk.k. which measures the variance of the value function V (5/41) caused by the stochastic transition from state- action pair
(s) a.).. According the definition of Ja. the difference between the estimator JE,N and To VR,b+1 satisfies
Σ #E[k-1] 22,
(fr, af) Vi.Niiss ah)) S2
(f(sh. ah) - Pa ok)) Th (Ve,t+)) (E[K-1] H.h
Σ
where the noise (V) r V -
V(s
EginPheg (oooeaeee..oaaraa (s at + V(s)) denotes the
stochastic transition noise for the value function V. However, the generation of the target function Vk,++1 relies on previously collected data =| thus violating the conditional independence property. Consequently, the noise term f%/ (V.. may not be unbiased. To address this challenge, it becomes imperative to establish a uniform convergence property over the potential function class, which is first introduced in linear MDPs by Jin et al. (2020).
Following the previous approach introduced by Azar al. (2017); Hu et (2022); Agarwal et al. (2022); He et al. (2022), we decompose the noise of optimistic value function 7 (V&, (Vk,4+1) into the
7

---

end for Algorithm Monotonic Q-Learning with UCB (MQL-UCB)
Require: Regularization parameter A, confidence radius {EK) {Bu (ee(K] and (ButeeTN)
1: Initialize A 0. For each stage h E [H] and state-action (s,a) E S x A, set (o, t-
H, (s, a) <
2: for episodes h = 1,.... K do
3: Received the initial state si.
4: for stage h = ,,..., do
5:
if there exists a stage N E [H] such that (3.1) holds then
6:
SK,A - argmin F. Eie i,n (Ja(s) o/)) r/ - 1
Fu. argmin MEER EiE of ap) 1 - -rh. (1/1)1100 w/)) (r) + (=
7:
8:
J& f- argmin EiEN-11| (on
9:
Qs, min| (s, (3, a), QR-L,Ms,
(s, max (Tn,(s, (8, a); ( a), (8,
10:
11:
Set the last updating episode Kusst t k and number of policies as 4 t 4-11 + 1.
else
13:
Qs, + Q)-1,((,a), (s,n( + 1N a) and 4. + 14-1.
end if
15:
Set the policy ah as x²(()) +- argmax DEA Qu, VE,((s) + max. (8,)
(s) + maxe (s,
16:
end for
for stage h 1........
do Take action o +- ~ (* and receive next state shtr
18:
19:
Set the estimated variance oh in (3.4) and set σ max (o a,?
DJ/22 (z; (2; 21 1k-1,.)
20:
end for
21:
noise of optimal value function (VK++) and the noise / (Vi,N+1 - Vi++) reduce the extra log (N (K)) dependency in the confidence radius. With the noise decomposition, we evaluate the variances [V a) and (V,.A44 Vi+1)] (s, a) separately.
For the variance of the optimal value function V [ss, a), since the optimal value function V independent with the collected data 2[km.] it prevents uniform convergence-based argument over the function class. However, the optimal value function Vi++ is unobservable, and it requires several utilize the optimistic function Vk,4+1 to approximate
steps to estimate the variance. In summary, the optimal value function Vi+ and calculate the estimated variance [V, Vk. as the difference between the second-order moment and the square the first-order moment of Vi.h
[V Ve.tta] Fr. PE.
Here, the approximate second-order moment FI,h and the approximate first-order moment fE.A is generated by the least-square regression (Lines and 8). addition, we introduce the exploration bonus Ex to control the estimation error between the estimated variance and the true variance of Vk,b+1 and Fk.h to control the aub-optimality gap between Vk,++1 and Vi+1
ER (2L + 3e) min (1, Dy, (2; 2p--1,6 11))),
FR. = (log(N(FF,)) e) N.(K)) min (1, 2 a - ( of + 4,0 D., (z) 2ik 1).b o 01--11,)),,
where
((kk))((F.)) 8
G4Le k Be = 1 128 log (()))N((FFe)) + 64Te k/a".
3 = 128 log
8
For the variance of the sub-optimality gap. [V, 1) (s, a). based on the structure of optimistic and pessimistic value function, it can be approximate and upper bounded by
V (V (i a s (V (=+ af))

---

I 2| Va ob) ~ 2fhn of) - 2f (sh aft),
where the approximate first-order moments fk, fk.n are generated by the least-square regression (Lines and 7) and can be dominated by the exploration bonus Fe, In summary, we construct the estimated variance krth as:
kkh Va, Sa.iaVa Va, 11 oft + Ek, + Fk.
(3.4)
3.4 Monotonic Value Function
As discussed in the previous subsection, decompose the value function Vi, and evaluate the variance [V ( a), [Va(Ve,t+1 - (s, a) separately. However, for each state-action pair (s%, aff) and any subsequent episode k, the value function Vi.1 and corresponding vari- ance (V,.VV
Vi++1] (s af)) may differ from the previous value function Vi. and variance [VA(V&,A+1 - [i+1) a Extending the idea proposed by He et al. (2022) for linear MDPs, we
ensure that the pessimistic value function Qu.A maintains monotonically increasing property during updates, while the optimistic value function Qk. maintains a monotonically decreasing property. Leveraging these monotonic properties, we can establish an upper bound on the variance as follows:
[Va(V,,41 - (st a S (V - (.)+))((s a s 2V V1, at) S Fx,
this scenario, the previously employed variance estimator σ offers a consistent and uniform upper bound for the variance across all subsequent episodes.
Main Results
In this section, we present the main theoretical results. In detail, we provide the regret upper bound of Algorithm MQL-UCB in Theorem 4.1. As complement, in Section B. we provide a lower bound on the communication complexity for cooperative linear MDPs. Finally, in Section B.2, we discussed the connection between the generalized eluder dimension and the standard eluder dimension.
The following theorem provides the regret upper bound of Algorithm MQL-UCB.
Theorem 4.1. Suppose Assumption 2.2 holds for function classes F {Fr and Defini- 1. we set a = I/VKH, = (KLH)-1, and set 3 = 3 := [log(N>(e)) +1] + O()) + ((ek/aa)) then with probability 0(5), the regret MQL-UCB upper bounded follows:
tion 2.4 holds with
0( log 2k (2log(() ))2) ++2) (log(4L/a3)
8/H
Regret(K). (0 log Vark)
+ HHH22 dim ( / log log((N No)) / H log N + dim(F) .N)
where Varx == Σx= Σ function class by No. the covering number of function class J by N, and the dimension dim,, k (F) by (F). Meanwhile, the switching cost of Algorithm is ((dima,k(F) H).
at) = Ö(K), denote the covering number of bonus
In the worst case, when the number of episodes K is sufficiently large, the leading term in our regret bound is Ö( / dii(() log N HK). Our result matches the optimal regret achieved by Agarwal et al. (2022). While their proposed algorithm involves the execution of a complicated and non- Markovian policy with an action selection phase based on two series of optimistic value functions and the prefix trajectory, MQL-UCB only requires the knowledge of the current state and a single optimistic state-action value function Q to make a decision over the action space. addition, our theorem also provides variance-deye dependent regret bound, which is adaptive the randomness of the underlying MDP encountered by the agent. Our definition of Var inspired by Zhao et al. (2023) and Zhou et al. (2023), which studied variance-adaptive RL under tabular MDP setting and linear mixture MDP setting, respectively.
As direct application, also present the regret guarantee of MQL-UCB for linear MDPs.

---

Corollary 4.2. Under the same conditions of Theorem 4.1, assume that the underlying MDP is linear MDP such that F : (Fr)nejn) composed of linear function classes with known feature mapping over the state-action space Φ S x A + R If we set X = 1, 1//K, then with probability - O(), the following cumulative regret guarantee holds for MQL-UCB:
Regrot( (K) = ÖddVHK + H2.. H +
Remark 4.3. The leading term in our regret bound, as demonstrated in Corollary 4.2, matches the lower bound proved Zhou et al. (2021a) for linear MDPs. Similar optimal regrets have also been accomplished by He et al. (2022) and Agarwal et al. (2022) for linear MDPs. Since we also apply weighted regression to enhance the precision of our pessimistic value functions, the lower order term (i.e., 12 d V + d²) in our regret has a better dependency on H than VOQL (Agarwal et al., 2022) and LSVI-UCB+ (He et al., 2022), which may be of independent interest when considering long-horizon MDPs. In addition, the switching cost of Algorithm 1 is bounded by OddH), which matches the lower bound Gao et al. (2021) for deterministic algorithms and our new lower bound in Theorem B.1 for arbitrary algorithms up to logarithmic factors. For more details about lower bound, please refer to Appendix E.
5 Conclusion and Future Work
In this paper, we delve into the realm of RL with general function approximation. We proposed the MQL-UCB algorithm with an innovative uncertainty-base rare-switching strategy in general function approximation. Notably, our algorithm only requires (dd)) updating times, which matches with the lower bound established by Gao et al. (2021) up logarithmic factors, and obtains a ()) regret guarantee, which near-optimal when restricted to the linear cases.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their helpful comments. HZ. is partially supported by the research award from Cisco. JH and QG are partially supported by the research fund from UCLA- Amazon Science Hub. The views and conclusions contained in this paper those of the authors and should not be interpreted as representing any funding agencies.
References
ABBASI- YADKOR,, Y., PÁI., D. and SZEPESVÁRI, C. (2011). Improved algorithms for linear stochastic bandits. Advances in neural information processing systems 24
AFSAR, M. M., CRUMP, T. and FAR, B. (2022). Reinforcement learning based recommender systems: A survey, ACM Computing Surveys 55 1-38.
AGARWAL, A., JIN, Y. and ZIIANG, T. (2022). Voql: Towards optimal regret in model-free rl with nonlinear function approximation. arXiv preprint arXiv:2212.066
AGARWAL, A. and ZHANG, T. (2022a). Model-based with optimistic posterior sampling: Structural conditions and sample complexity. Advances in Neural Information Processing Systems 35 35284- 35297.
AGARWAI, A. and ZHANG, T. (2022b). Non-linear reinforcement learning in large action spaces: Structural conditions and sample-efficiency of posterior sampling. In Conference Learning Theory. PMLR.
AYOUB, A., JIA, Z., SZEPESVARI, C., WANG, M. and YANG, L. (2020). Model-based reinforcement learning with value-targete regression. In International Conference Machine Learning. PMLR.
AZAR, M. G., OSBAND, I. and MUNOS, R. (2017). Minimax regret bounds for reinforcement learning. International Conference on Machine Learning. PMLR.
BAL, Y., XIE, T., JIANG, and WANG, Y.-X. (2019). Provably efficient q-learning with low switching cost. Advances in Neural Information Processing Systems 32.
10

---

CHEN, Z., LI, J., YUAN, H., GC, Q. and JORDAN, M. (2022). A general framework for sample-efficient function approximation in reinforeement learning. In The Eleventh International Conference on Learning Representations.
DANN, C., JIANG, N., KRISHNAMURTHY, A., AGARWAL, A., LANGFORD, and SCHAPIRE, R. E. (2018). On oracle-efficient pac rl with rich observations. Advances in neural information processing systems 31.
DI, Q. ZHAO, H., HE, J. and GU, Q. (2023). Pessimistic nonlinear least-squares value iteration for offline reinforcement learning. arXiv preprint 10.0:333
DU, S., KAKADE, S., LEE, J., LOVETT, S., MAHAJAN, G., SUN, W. and WANG, R. (2021). Bilinear classes: A structural framework for provable generalization in rl. In International Conference Machine Learning. PMLR.
DU, S. S., KAKADE, S. M., WANG, R. and YANG, L. F. (2019). Is a good representation sufficient for sample efficient reinforcement learning? International Conference on Learning Representations.
FOSTER, D. J., KAKADE, M., QIAN, J. and RAKHLIN, A. (2021). The statistical complexity of interactive decision making. arXiv preprint 11X1v:2112.13487
GAO, M., XIE, T., DU, S. S. and YANG, L. F. (2021). provably efficient algorithm for linear markov decision process with low switching cost. arXiv preprint arXiv:2101.00494.
GENTILE, C., WANG, Z. and ZHANG, T. (2022). Achieving minimax rates in pool-based batch active learning. In International Conference on Machine Learning. PMLR.
HAN, Y., Zuoo, Z., ZIOO,, Z., BLANCHET, J., GLYNN, P. W. and YE, Y. (2020), Sequential batch learning in finite-action action linear contextual bandits. arXiv preprint arXiv:2004.0632. 20.22000........
HE, J., ZHAO, H., ZHOU, D. and Gu, Q. (2022). Nearly minimax optimal reinforcement learning for linear markov decision processes, arXiv preprint arXiv:2212.06132.
HE, J., ZhoU, D. and GU, Q. (2021a). Logarithmic regret for reinforcement learning with linear function approximation. In International Conference on Machine Learning. PMLR.
HE, J., ZHOU, D. and GU, Q. (2021b). Nearly minimax optimal reinforcement learning for discounted mdps. Advances in Neural Information Processing Systems 34 22288-22300.
HU, P., CHEN, Y. and HUANG, L. (2022). Nearly minimax optimal reinforcement learning with linear function approximation. In International Conference Machine Learning. PMLR.
HUANG, J., CHEN, J., ZHAO, I.., QIN, T., JIANG, N. and LIU, T.-Y. (2022). Towards deployment- efficient reinforcement learning: Lower bound and optimality. arXiv preprint arX1v:2202.06445
JIA, Z., YANG, L.,, SZEPESVART, C. and WANG, M. (2020). Model-based reinforcement learning with value-targeted regression. Learning for Dynamics and Control. PMLR.
JIANG, N., KRISHNAMURTHY, A., AGARWAL, A., LANGFORD, J. and SCHAPIRE, R. E. (2017). Contextual decision processes with low bellman rank are pac-leamable. In International Conference on Machine Learning. PMLR.
JIN, C., ALLEN-ZHU, 7.,, BUBECK, S. and JORDAN, M. I. (2018). Is q-leaming provably efficient? Advances in neural information processing systems 31.
JIN, C.,, LIU, Q. and MIRYOOSEFL, S. (2021). Bellman cluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances in neural information processing systems 34 13406-13418
JIN, C., YANG, 7.,, WANG, Z. and JORDAN, M. I. (2020). Provably efficient reinforcement learning with linear function approximation. 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 32 1238-1274.
KONG, D., SALAKHUTDINOV, R., WANG, R. and YANG, L. (2021). Online sub-sampling for reinforcement learning with general function approximation. arXiv preprint arXiv:2106.077200
LI, Y., WANG, Y., CHENG, Y. and YANG, L. (2023). Low-switching policy gradient with exploration via online sensitivity sampling. In International Conference on Machine Learning. PMLR.
LILLICRAP, P., HUNT, J. J., PRITZEL, A., HEESS, N., EREZ, T., TASSA, Y., SILVER, D. and WIERSTRA, D. (2015). Continuous control with deep reinforcement learning. arXiv preprint arXiv:1509002977
MATSUSHIMA, T., FURUTA, H., MATSUO, Y., NACHUM, O. and Gu, S. (2020). Deployment- efficient reinforcement learning via model-based offline optimization. In International Conference on Learning Representations.
MNIH, V., KAVUKCUOGLU, K., SILVER, D., RUSU, A. A., VENESS, J., BELLEMARE, M. G., GRAVES, A., RIEDMILLER, M., FIDJELAND, A. K., OSTROVSKI, G. ET AL. (2015). Human-level control through deep reinforcement learning. nature 518 529-533.
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.
PUTERMAN, M. I.. (2014). Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons.
QIAO, D., YIN, M., MIN, M. and WANG, Y.-X. (2022). Sample-efficient reinforcement learning with loglog (t) switching cost. International Conference on Machine Learning. PMLR.
QIAO, D., YIN, M. and WANG, Y.-X. (2023). Logarithmic switching cost reinforcement learning beyond linear mdps. arXiv preprint 1rXiv:2302.12456
RUAN, Y., YANG, J. and ZHOU, Y. (2021). Linear bandits with limited adaptivity and learning distributional optimal design. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing.
RUSSO, D. and VAN ROY, B. (2013). Eluder dimension and the sample complexity of optimistic exploration. Advances Neural Information Processing Systems 26.
Russo, D. and VAN ROY, B. (2014). Learning to optimize via posterior sampling. Mathematics of Operations Research 39 1221-1243.
SIMCHOWITZ, M. and JAMIESON, K. G. (2019). Non-asymptotic gap-dependent regret bounds for tabular mdps. Advances Neural Information Processing Systems 32.
SUN, W., JIANG, N., KRISHNAMURTHY, A., AGARWAL, A. and LANGFORD, (2019). Model- based rl in contextual decision processes: Pac bounds and exponential improvements over model- free approaches. In Conference on learning theory. PMLR.
VELEGKAS, G., YANG, Z. and KARBASI, A. (2022). Reinforcement learning with logarithmic regret and policy switches. Advances in Neurul Information Processing Systems 35 36040-36053.
WANG, R., SALAKHUTDINOY, R. R. and YANG, L. (2020a). Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems 33 6123-6135.
WANG, T., ZHHOU, D. and GU, Q. (2021). Provably efficient reinforcement learning with linear function approximation under adaptivity constraints. Advances Neural Information Processing Systems 34 13524-13536.
WANG, Y., WANG, R., DU, S. S. and KRISHNAMURTHY, A. (2020b). Optimism in reinforcement learning with generalized linear function approximation. In International Conference on Learning Representations.
12

---

XIONG, N., YANG, Z. and WANG, Z. (2023). A general framework for sequential decision decision-making under adaptivity constraints. arXiv preprint arXiv:2306. 244.64888....
YANG, L. and WANG, M. (2019). Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning. 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.
YE, C., XIONG, W., GU, Q. and ZHANG, T. (2023). Corruption-robur algorithms with uncertainty weighting for nonlinear contextual bandits and markov decision processes. 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. International Conference on Artificial Intelligence and Statistics.
ZANETTE, A. and BRUNSKILL, E. (2019). Tighter problem-dependent regret bounds in reinforce- ment learning without domain knowledge using value function bounds. In International Conference on Machine Learning. PMLR.
ZANETTE, A., LAZARIC, A., KOCHENDERFER, M. and BRUNSKILL, (2020b). Learning near optimal policies with low inherent bellman enror. In International Conference on Machine Learning. PMLR.
ZhANG, Z. and JI, X. (2019). Regret minimization for reinforcement learning by evaluating the optimal bias function. Advances in Neural Information Processing Systems 32.
ZhaNg, Z., J1, X. and DU, S. (2021). reinforcement learning more difficult than bandits? near-optimal algorithm escaping the curse of horizon. In Conference on Learning Theory. PMLR.
ZHANG, Z., JIANG, Y.. ZHOU, Y. and J1, X. (2022). Near-optimal regret bounds for multi-batch reinforcement learning. Advances in Neural Information Processing Systems 35 24586-24596
ZhANG, Z., ZHOU, and J1, X. (2020). Almost optimal model-free reinforcement learningvia reference-advantage decomposition. Advances in Neural Information Processing Systems 33 15198-15207.
Zhao, H., HE, J., ZHOU, D., ZHANG, T. and GU, Q. (2023). Variance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency. arXiv preprint 1033
ZHENG, G., ZHANG, F., ZHENG, Z., XIANG, Y., YUAN, N. J., XIE, X. and LI, Z. (2018). Dr:: A deep reinforcement learning framework for news recommendation. In Proceedings of the 2018 world wide web conference.
ZuoU, D. and GU, Q. (2022). Computationally efficient horizon-free reinforcement learning for linear mixture mdps. arXiv preprint arXiv:2205.
ZHOU, D., GU, Q. and SZEPESVARI, C. (2021a). Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory. 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. PMLR.
ZHOU, R., ZITANN Z. and DU, S. S. (2023). Sharp variance-dependent bounds in reinforcement learning: Best of both worlds in stochastic and deterministic environments. International Conference Machine Learning. PMLR.
ZOPH, B. and LE, Q. V. (2016). Neural architecture search with reinforcement learning. arXiv preprint arxiv: arxiv:1611.. 1611.08
13

---

A Additional Related Work
A.1 RL with Linear Function Approximation
In recent years, substantial body of research has emerged to address the challenges of solving Markov Decision Processes (MDP) with linear function approximation, particularly to handle the vast state and action spaces (Jiang et al., 2017; Dann et al., 2018; Yang and Wang. 2019; Du et al., 2019; Sun et al., 2019; Jin et al., 2020; Wang et al., 2020b; Zanette et al.. 2020a; Yang and Wang, 2020; Modi al., 2020; Ayoub et al., 2020; Zhou et al., 2021a; He et al., 2021a; Zhou and Gu, 2022: He et al., 2022; Zhao et al., 2023). These works can be broadly categorized into two groups based on the linear structures applied to the underlying MDP. One commonly employed linear structure is known as the linear MDP (Jin et al., 2020), where the transition probability function I', and reward function Th are represented as linear functions with respect to a given feature mapping Φ S x - TR.. Under this assumption, the LSVI-UCB algorithm (Jin et al., 2020) has been shown to achieve regret guarantee of /d Subsequently, Zanette et al. (2020a) introduced the RLSVI algorithm, utilizing the Thompson sampling method, to attain regret bound of O(v More recently, He et al. (2022) improved the regret guarantee to Ö D(vd2 K)) with the LSVI-UCB++ algorithm. aligning with the theoretical lower bound in Zhou et al. (2021a) up to logarithmic factors. Another line of research has focused on linear mixture MDPs (Modi et al., 2020; Yang and Wang. 2020; Jia et al., 2020; Ayoub et al., 2020; Zhou et al., 2021a), where the transition probability is expressed as a linear combination of basic models 11, P2.,,,.. Pa. For linear mixture MDPs, Jia et al. (2020) introduced the UCRL-VTR algorithm, achieving regret guarantee of Ō de K)). Subsequently, Zhou et al. (2021a) enhanced this result to ((v reaching nearly minimax optimal regret bound. Recently, several works focused on time-homogeneous linear mixture MDPs, and removed the dependency on the episode length (horizon-free) (Zhang and Ji, 2019; Zhou et al., 2021b; Zhao et al., 2023).
A.2 RL with General Function Approximation
Recent years have witnessed a flurry of progress on RL with nonlinear function classes. To explore the theoretical limits of RL algorithms, various complexity measures have been developed to characterize the hardness of RL instances such as Bellman rank (Jiang et al., 2017). Witness rank (Sun et al., 2019), eluder dimension (Russo and Van Roy, 2013), Bellman eluder dimension (Jin et al., 2021), Bilinear Classes (Du et al., 2021), Decision-Fstimatio Bellman Characterization (Chen al., 2022), generalized eluder dimension (Agarwal et al., 2022). Among them, only Agarwal et al. (2022) yields a near-optimal regret guarantee when specialized to linear MDPs. In their paper, they proposed new framework named generalized eluder dimension to handle the weighted objects in weighted regression, which can be seen as a variant of eluder dimension. In their proposed algorithm VOQL, they adopted over-optimistic and over-pessimistic value functions in order to bound the variance of regression targets, making it possible to apply a weighted regression scheme the model-free framework.
Coefficient (Foster et al., 2021), Admissible
A.3 RL with Low Switching Cust
Most of the aforementioned approaches necessitate updating both the value function and the corre- sponding policy in each episode, a practice that proves to be inefficient when dealing with substantial datasets. To overcome this limitation, a widely adopted technique involves dividing the time sequence into several epochs and updating the policy only between different epochs. In the context of the linear bandit problem, Abbasi-Yadia Yadkori et al. (201 1) introduced the sarely-switching OFUL algorithm, where the agent updates the policy only when the determinant of the covariance matrix doubles. This method enables the algorithm to achieve near-optimal regret of Ö( /K) while maintaining policy updates to Odd log K) times. When the number of arms, denoted as [D], is finite, Ruan et al. (2021) proposed an algorithm with regret bounded by Ö( (VvdK) and a mere Od log d log K) policy-updating times. In the realm of episodic reinforcement learning, Bai et al. (2019) and Zhang et al. (2021) delved into tabular Markov Decision Processes, introducing algorithms that achieve regret of Ö Ö(VT) and (SS A log K) updating times. Wang et al. (2021) later extended these results to linear MDPs, Siich algorithm. LSVI-UCB-RareSwiite delivers a regret bound
unveiling the
14

---

of H²t H*) with policy switching frequency of Od T). which matches the lower bound of the switching cost (Gao al., 2021) up to logarithmic terms. Furthermore. if the policy is updated within fixed-length epochs (Han et al., 2020), the method is termed batch learning model, but this falls beyond the scope of our current work. In addition, with the help of stochastic policies, Zhang et al. (2022) porposed an algorithm with ((V K)) regret guarantee and only Õ(H) swithcing cost for learning tabular MDPs. Later, Huang al. (2022) employed the stochastic policy in learning linear MDPs, which is able find an e-optimal policy with only Ö(H) switching cost.
B
Additional Results
B.1 Lower Bound for the Switching Cost
As complement, we prove new lower bound on the switching cost for RL with linear MDPs. Note that linear MDPs lie in the class of MDPs studied in our paper with bounded generalized eluder dimension. In particular, the generalized eluder dimension of linear MDPs is (d).
Theorem B.1. For any algorithm Alg with expected switching cost less than dH/ /16 log K), there exists a hard-to-learn linear MDP, such that the expected regret of Alg is at least {2(K).
Remark B.2. Theorem 1.1 suggests that, to achieve sublinear regret guarantee, an (2(dH) switch- ing cost inevitable. This lower bound does not violate the minimax upper bound of ((H) proved in Zhang al. (2022); Huang al. (2022), which additionally assume that the initial state sf is either fixed or sampled from a fixed distribution. In contrast, our work and Gao et al. (2021) allow the initial state to be adaptively chosen by an adversarial environment, bringing more challenges to the learning of linear MDPs. When comparing our lower bound with the result in Gao et al. (2021), is worth noting that their focus is solely on deterministic algorithms, and they suggest that an (dH)) switching cost is necessary. As a comparison, our result holds for any algorithm with arbitrary policies including both deterministic and stochastic policies.
B.2
Connection Between D2-Unncertainty and Eluder Dimension
Previous work by Agarwal et al. (2022) achieved the optimal regret bound Ö( / dim(F) log N HK), where dim defined as the generalized eluder dimension as stated in Definition 2.4. However, the connection between generalized eluder dimension and eluder dimension proposed by Russo and Van Roy (2013) is still under-discussed 2, Consequently, their results could not be directly compared with the results based on the classic eluder dimension measure (Wang et al., 2020a) the more general Bellman eluder dimension (Jin et al., 2021).
In this section, make first attempt to establish connection between generalized cluder dimension and cluder dimension in Theorem B.3.
Theorem B.3, For a function space G, a > 0, let dim be defined in Definition 2.4. WLOG, we assume that for all g E G and E Z, lg(=) < 1. Then the following inequality between dim(F [F, Z, σ) and dimmeG 1/vT) holds for all Z = {zi)ee with 2; E 2 and {ox)eet s.t. 0, < M Vi E [T]:
Σ min (1. d? De 2-11) S (F, log log log(M/a)+ + +E[2T
According to Theorem B.3, the generalized eluder dimension upper bounded by cluder dimension up to logarithmic terms. When the number of episodes K is sufficiently large, the leading term in our regret bound in Theorem 4.1 1 is ((Vdim((F)log/ HK), where dimæ(F) is the eluder dimension of the function class F.
C Proof of Theorem B.3
To start with, we first recall the concept of eluder dimension as follows.
2 Agarwal et al. (2022) (Remark 4) also discussed the relationship between the generalized eluder dimension and eluder dimension. However, there exists technique flaw in the proof and we will discuss it in Appendix D.
15

---

Definition C.1 (Definition of eluder dimension, Russo and Van Roy 2013). The eluder dimension of function class 9 with domain defined as follows:
A point Z is e-dependent 21, 22. 2 E Z with respect G, if for all gr, 92 g such that Σ [0 (z+) (2(zi)]² c, holds that (2) 92(2)l S e.
Further is said to be r-independent of 21, 22, .... 2k with respect to 9, if is not dependent on 21, 22," 2k.
The eluder dimension of G, denoted by (G is the length of the longest sequence of elements in Z such that every element is é' e'-independent its predecessors for some e' 2 c.
With this definition, we can prove Theorem B.3.
Proof of Theorem B.3. Let I, (1 S j S [log, M/ be the index set such that
Ij {i E [T] [2/-1. a, 2/)
Then we focus the summation over Ij for each j. For simplicity, we denote the subsequence (rihvez, by for (elz,,1 Then we have
Σ min (1, I
D8 D8 (1) -
1 o7
Σ
min (1. (.aI6-11; 1R-1)))
iE|IZ,1l
To bound Σierz |I min (1,4Dg (I: 1(-1))),
Σ min (1,4D) (1: 1(-1))
RE|
< 4//++ Σ
(D) (1=08-1)) 1(=11) 2 p} dp
1/xX
xE[[T,]]
< <4/A+4
Σ
1 1D (In) 11-11) 2 p} dp.
(C.1)
1/AT
Then we proceed by bounding the summation
Eieliz,1] (D& (1;; ([-1) 2 p} for each
p 2 1/(T.). For short, let d = (9, Essentially, it suffices to provide an upper bound of the cardinality of the subset Jy == {ie I, D3 (I 44-11) 2 p}.
For each i E Tj. since D3 (m=zzp-1) 1], 1 ()=1 11) 2 p, there exists 91. I2 in G such that
(g) (x:) - g2 )2
Ei (z,) - g2 (xx )2 2 p/2.
Here (01(x;) (xx))) 2 Ap 2 1/T. Denote such value of (or (Ix;) - 2 by L(xx). Then we consider split cJj into [log, 7 layers such that in each layer Jht (I: E [[log I)), we have 1/T & T(x;,) & 2 for some ç.
Denote the cardinality of JHt by A and the subsequence far by (uihee(a- For the elements in {v), we dynamically maintain [A/d] queues of elements. We enumerate through {v} in its original order and put the current element y; into the queue Q such that y; is g-independent of the current elements in Q. By the Pigeonhole principle and the definition of eluder dimension d, we can find an element yı in {y} such that yı is E-dependent of all the [A/d] queues before
Then by the definition of L(v)) and &, we can choose 91, I2 such that
(gr (vs) (2))))
E1eti-1 ()) 92().))2 2 p/2, 2 2 (91 92(2)))2
(C.2)
16

---

By the E-dependencies, we have Eee(tr)(or(oe) - 92(31))2 2 [A/d] &. At the same time, Ene - 92(w)))² I 4 due to (C.2). Thus, we deduce that A |J = O(d/p) for all E [oog2 M.. Substituting into (C.1), we have
min (1, 4D (1 ((-1)) s 4/1+ [ 1/AT O(d/p log, Td
Σ iel|z,1
Od T log XT +
Here is chosen arbitrarily. Hence, the generalized eluder dimension can be further bounded as follows:
Σ KE[T]
min
(
1, 0.
Dg (zn 11-1), (--1))
In the following part, we will also discuss the issue in Agarwal al. (2022) about the relationship between the standard eluder dimension dimg and the generalized eluder dimension dim. In detail, Agarwal et (2022) proposed the concept of Generalized Eluder dimension and made the following claim:
Lemma C.2 (Remark 4, Agarwal et al. 2022). If we set the weight a 1, then the Generalized Eluder dimension dim supz.o: Z|=T dim(F, Z, 1) satisfied
dim S dimg(F, A.F.VAAATT +1,
where dimg denotes the standard Eluder dimension proposed in Russo and Van Roy (2013). In the proof of Remark 4, Agarwal et al. (2022) claims that given the standard Eluder dimen- sion dimg(FF (F, vX)
there at most different (sorted) indices {t,, 12, such that Dz (1(1,1,,1111)) -1, 1) 2 2/x. However, according to the definition of Dn-uncertainty, we only have
-
D (2) 1) sup fi. ((i())) (2()))) fz(=,))
However, R4, is e-dependence with .1, - is only a sufficient condition for the uncertainty (2: 1) rather than necessary condition. In cases where both (Ji(z) - f2(=))² e² and Eeepy (f((2)) f²(z.))² 2 e² hold, the uncertainty (11 1) may exceed e² P/,, yet will not counted within the longest e-independent sequence for the standard Eluder dimension.
D Proof of Theorem 4.1
In this section, we provide the proof of Theorem 4.1.
D.I High Probability Events
In this subsection, define the following high-probability events:
E
X Σ
(Jen(sh af) - (sh. S 38
(D.I)
EE|k-1]
x Σ
(Fen(Sh) To Vo 5 32
(D.2)
k
J.hn
iE|k-1]
1]
X+ Σ
(Frn(sha -Ta--aaa TaVanti(shaaa)) s 33
(D.3)
oih
iE[k-1]
17

---

where
(k) Nz(()) H
+ 64Le k. Bp V 128 log Ne(k). NN(()
3x V 128 log
64Le k/a?.
of Sa, ef and Eigh are the hoeffding-yy type concentration results for Fa.n. Fu. and FA.n respectively.
Then define the following bellman-type concentration events for Se, Je which implies tighter confidence set due to carefully designed variance estimators and an unverse-variance weighted regression scheme for the general function classes.
x
(Fnar(She. ahe) Th V oh)) (2
I By vh S N' SN'SSHH H.
k-
(Faar(sh.ah ahe) - Th VaN S Br vh s &N's &HKE [K]
c
x
(o
(D.4)
where
21 (2log (2og((2k//at) +2) (log(4L/a))+3)
82 = 22 = 0 log
[log(N>(e)) +
8/H
+ O(A) + O(ckL/a²). We also define the following events which are later applied to prove the concentration of fe,A and Ja. by induction.
ELA -
{ x+ Σ
1 (Fralsh, at)) - -Th--hh V s <B2
(D.5)
iE(K-1 (o,,a)²
where Le, is the shorthand for the following product of indicator functions
i == 1 (IVA Vi+ 11sh a I oi,n)) 1 ((T. V1,++1 - -VV il (log Nx(() + log N.(
- 1 (Vin+1($)) 2 (s) E
(D.6)
E - - - Σ
is (Fh, a Ta V. V
32
(D.7)
(os,)2
EEjK-1j
where Te is the shorthand for the following product of indicator functions
i. == 1 (IVA (iV ahh s )i,,)) 1 ([TVi++ Ta V. S (log N=(() + log N. (
1 (V S (s) Vs VsES).
(D.8)
The following Lemmas suggest that previous events hold with high probability.
Lemma D.1. Let Ju.n be defined as line 8 of Algorithm 1, we have g = N Ef holds
with probability at least 8, where Ef is defined in (D.1).
Lemma D.2. Let Pr.m be defined as in line 6 of Algorithm 1, we have EL == = El holds
with probability at least - 8, where El is defined in (D.2).
Lemma D.3. Let Fr,n be defined as in line 7 of Algorithm 1, we have g. == = El holds
with probability at least - 8, where E is defined in (D.3).
Lemma D.4. Let f be defined as in line 6 of Algorithm 1, we have E NK2I.eelmn k holds
with probability at least - 26, where eL is defined in (D.5).
Lemma D.5. Let Je.n be defined as line of Algorithm 1, we have E! holds with probability at least 1 28.
18

---

D.2 Optimism and Pessimism
Based on the high probability events, we have the following lemmas for the function Ru, a) and (s.0)
Lemma D.6. On the events E/. and E/ for each episode &s E [K]] we have
[ a) Tv V a)l S Bg (z; [(--))) k- [k, a) - Th V. a) $ Drs (2: 2[ - 1J.b x-
where = (s, a) and 11, = {21,h, 22, 1.
Lemma D.7. On the events Ehyy and E/411 for each stage < h' s H and episode k E [K], we have Qu, a) 2 (s, 2 Qu,n(s, a). Furthermore, for the value functions Vi, (s) and (s),, we have (s) 2 (s) 2 (s).
D.3 Monotonic Variance Estimator
In this subsection, introduce the following lemmas construct the monotonic variance estimator.
Lemma D.8. On the events el.E/ and e/, for each episode A E [K] and stage h [H], we have
[A, To V a)l s B.Dx, (z: [z 11.
(s, a) Th. (I a) s BrDD, (2; 2|= 11. 1
[ a) T Vi.b+ (8, (8,a) S 3x Dr, (z; F -k-
where = (s and 1], (21, 22,1 2k
Lemma D.9. On the events g¹, gº, gL. Eiy eh_,, for each episode & E [K], the empirical
variance [V, Ve, a satisfies the following inequalities:
I Ve, a VV W. at) S Ek,h:
[V V. (ssh ah) - [V i ati) S Ex,t Fu.K.
Lemma D.10. On the events EL Eी sî Sh of
for each episode & [K] and i > k, we have
(log Nx(() + log (K)) (V Vk+z)) (5% a S Fi,
[logN>(e) + log (K)) (V - V.,+z)] (s at S Fi,.
Based on previous lemmas, we can construct an optimistic estimator kt for the transition variance. Under this situation, the weighted regression have the following guarantee.
Lemma D.11. If the events g¹ gL. gf. Ef and gr hold, then events gf = =&f and gi Ef hold.
D.4 Proof of Regret Bound
In the subsection, we first define the following high proSbability events to control the stochastic noise from the transition process:
H Σ
vh' [H), Σ
-
(Ve.+i((si4a)) (s
1= h=
h=
K H
$ 2
VVaVVen41 - 1(t att log(2K2H/8) + 2 +
+ 22
Am Ro
" YA E [H) Σ Σ
H k
E2
(P -
Σ
Σ
(Vo,441(5h41) - ((n+z(5/
k=1k=
k=1
19

---

K
H
Va(VE. - (..+1))((f of log(2K2H/0) + 2 2 + 2log((K22H8)
h=
According to Freedman inequality (Lemma H.5), we directly have the following results.
Lemma D.12. Events & and Eg hold with probability at least 1 - 22.
Proof. Fix an arbitrary h [H]. Applying Lemma H.5, we have the following inequality:
Σ
Σ
PA(VE,,41
V (o (5
(Van+1(5h+1)) Vati (5%
-
H
2
Va(VeN+1
(5h log +2 22000/)22) + 2og
())
R= #==h
(D.9)
Applying union bound for (D.9) across all [H]. k 2 have Event & holds with probability at least 1 - 25.
Similarly, also have the corresponding bigh-probability bound for &2.
Next, we need the following lemma to control the summation of confidence radius.
Lemma D.13. For any parameters 3 2 and stage h E [A]], the summation of confidence radius over episode k E [K] is upper bounded by
Σ min (BDr, (zi 2| b) o (A-11,))11) k=1
K
< (1 + By2) dimo, (FF) + 23, /dimo (Fr),
Σ o +
where (s, a) and 2[k- {21,h, 11
Then, we can decompose the total regret in the first K episode to the summation of variance ΣK Ii oh.n as the following lemma.
Lemma D.14. On the events gी = Ef. g = Ef and E,, for each stage h E [H]. the regret in the first K episodes can be decomposed and controlled as:
Σ (Vr,(())) VØ (sh)) S 2CH(1 + x)(1 + BaY2) dima, (F)
K
+ 4C(1 + +)33 v ((F),
H
+ a2)
R.
1=1
K
H
+ 2
VVA(V - Vith (s at) log(2k²H/0) + 2/1o((2K2/// + 2
A=
and for all stage h [M], we further have
PA vx+1)] (st a
k=1-1
K H
22CH2 + x) + B672) dimn) (FF 4CH(( + /ima.
H
(02 ce
+ a?)
20

---

K H +
2
ΣΣ VA(VE,
a log(2K2H/6) + 2 (2tl:))))222///2// log(2k22H0)) + 2log(2
In addition, the gap between the optimistic value function Vs,((8) and pessimistic value function Vi,((s) can be upper bounded by the following lemma.
Lemma D.15. On the events gî = =ff. g Ef and Ez, for each stage h E [H], the regret in the first K episodes can be decomposed and controlled as:
K
(v.)(())) - (on())))) & 4CH(1 + x) + Ban?) dima, (Fr))
(D.10)
1=1
8C(1 x)3,y dimm,
H
(o + a²)
(VA Vl a 1og(2K311/0) 22/000++2211g2////0000000 + +2log(2k2
and for all stage h E [H]. we further have
PA.VV 11, (5%, att)
Rin Rml
K H
4CH + x) + B672) (im SCH x)3xxy dima.
(o2 k.h +
K
H
+ 2H
2
Σ
[V V
+ +
We define the following high probability event Eg to control the summation of variance.
Eg ΣΣ W.Veil a s 3K 3H log( log(1/)) }
According to Jin al. (2018) (Lemma C.5)², with probability at least - 6. Condition on this event, the summation of variance Σx= Eh oi can be upper bounded by the following lemma.
Lemma D.16. On the events &,, &g, Eg, Eी Ef and gd = E.. the total estimated variance upper bounded by:
K
Σ
Σ oh S (x()) log
log (K()) (4)) ((1 + H3 + BB)H dima, x (F)) + (log N)(()) + log (K))² x Ō( + H3x + B.) 2H dim (F))
Am h=1
+ + +HHa?).
With all previous lemmas, we can prove Theorem 4.1
Proof of Theorem 4.1. The low switching cost result is given by Lemma G.I.
Ō(KH² + H²)) when Σh= (r an) < H. In this work, assume the total reward satisfied E (1(sh, on) S 1, and the summation of variance upper bounded by Ö(K + H)
'Jin al. (2018) showed that IM
at)
21

---

El g.. g.. gf and gf hold with
After taking union bound, the high probability events E Eg, E3. probability at least 1 - 106. Conditioned on these events, the regret is upper bounded by
Regret(K)
K
(Vi - (of))
Σ k=1
(V v
k H ΣΣ
< 2CH( x)) (1x+++1++)))))) dima. x (F)+
[Vn
V (1
k=1k=1
+ +CC(1 + x)3x v dima,
H
(ot +
k=1h=1
K Pa - V
22CH(1+ x 3x7 dima, (F)+ō
k=1k=1
K
+4C(1 + x)3x dima,
H
ΣΣ k=1h=1
Σ
(o +
s 2CCH( + x1(1 3k dima, (F) xF)+
BK dima,
H
Σ k=1h=1
(ok, + a2)
< 0 H dima, ( (F) (1+ 3xク2)) (1+BBx72) + BK V VHVark
+ Ō H didia (F) (Bx + HßK + Bx) log
logg Nx(()) No(K))) + +ō H dima
((F)a,.(FFBBk (F) + +22))
S dima, (F) log N/
-log
Nf
N B,
2KHL)
2KHL
2KHL3K
+
11..5 2. (F)
log logN= Nr
-lgg.5
NF
N B,
(2KHT.
2KHT.
2K 2KHLBK
+
(Fima.(())og
No
HVarK
(D.11)
2KHL
where the first incquality holds due to Lemma D.7, the second inequality holds due to Lemma 14 the third inequality follows from Lemma D.7 and Var[X] < B[X] MM if random variable X is in
[0, MJ. the fourth inequality holds due to (F.41) and 2ab < a² + 62, the last inequality holds due to Lemma D.16. Thus, we complete the proof of Theorem 4.1.
We can reorganize (D.11) into the following upper bound for regret.
Regret(K)) K) Ö(v dim(F) log N H Vark)
Ō 222 dim? (F) log N log(NN No) / H log N + F)m
log(N No)
where we denote the covering number of bonus function class N (B, 2KHLaK by No. the covering number of function class F by N and the dimension dima, (F) by dim(FF. Since Eg occurs with high probability according to Jin al. (2018) (Lemma C.5), we have Vark = Ö(K), which matches the worst-case minimax optimal regret bound of MDPs with general function approximation.
D
22

---

D.5 Proof Sketch of Regret Bound
In this subsection, we provide a proof sketch on the regret bound and show how our policy- strategy works.
First, we introduce the following lemma which illustrates the stability of the bonus function after using the uncertainty-based policy-switching condition.
Lemma D.17 (Restatement of Lemma G.2). If the policy is not updated at episode k, the uncertainty of all state-action pair = (s,a) E and stage h E [H] satisfies the following stability property:
1
Dj, (2: 2p-- le I1.A)
D2,, (2) M/uus - 1) Maaee 11,))
1+X
With Lemma G.2, we can then convert D3, (zj 11,6 1111), with cost of an additional + X constant.
Fú (2; 2 -).b o Mause (aaoe-1),
1J.b
in the bonus term into
As direct consequence of Lemma G.2, We have the following lemma, which controls the gap between optimistic value functions and real value functions resulting from the exploration bonuses.
Lemma D.18 (Restatement of Lemma D.14). On the events Eी = EL. g &f and & for each stage h E [H], the regret in the first K episodes can be decomposed and controlled as:
(s)) Via (sh) S 2CH(1 + () + BBn²)) dima, (F)
k H H
+ 4C(1 + x)3x V dimo, (FF)
(o + a2)
K
H
+ 2
[VA(VRA41 - at) log(2k²H/0)) + 2/log(2K31/0) + +2log(2k22100)
and for all stage h [W], we further have
[V (sk, k=1k1
K H H
< 21 + x) + dim,, 4CH((1 + (2))
(o bo + a2)
k=
A=1
+ 2
ΣΣ k=1h=1
As need to bound the sum of bonuses corresponding to weighted regression target, we derive the following results on the sum of inverse weights.
Lemma D.19 (Informal version of Lemma D.16). With high probability, the total estimated variance is upper bounded by:
K
ohn S (log N=(e) log N. x (o)
+ H3. + BB) dima, x (F)) log Nog (K))² x Ō((8 + H33 + +3, 2 dim K (F))
k= k=1
+ (log Nx()) Nog Ö(Vark KHo
Proof sketch of Theorem 4.1. As the result of optimism, we have shown that with high probability, for all k, h E [] [H), Vi.h is an upper bound for Vr Hence, further have,
K
Regrot (K)
(VT(st) VE
(Vr, Vz. (st)).
23

---

To further proceed, we apply Lemma D.14 and obtain
K H
(R) < 2CH(1 x1(11 + 3x7?) dima, x (F)+
VV
vitti)( at)
k=1 1=
K H
4C + x)3K dima,
H
Σ
(o + a²),
where the second term be bounded by applying Lemma D.14 repeatedly and the third term can be controlled by Lemma D.16.
Then after substituting the value of belax, 7 and a, we conclude that with high probability, Regret K) ddi log N. HVark)
δ 2 dim?(F) Vlg N log(N Nτ) / H log N + dim(F) No))
Please refer to Subsection D.4 for the detailed calculation of this part.
E Proof of Theorem B.1
In this section, we provide the proof of Theorem B.1. prove the lower bound, we create series of hard-to-learn MDPs as follows. Each hard-to-learn MDP comprises d/4 distinct sub-MDPs denoted MM,,,.,aaa Each sub-MDP M, is characterized by two distinct states, initial state s; and absorbing state $1,1, and shares the same action spaces are finite, these tabular MDPs can always be represented as linear MDPs with dimension |8] |A| d.
{oo,ar a1}. Since the state and action
To generate each sub-MDP M,, for all stage h E [H], a special action 0, is uniformly randomly selected from the action set {ap, ). Given the current state 8,,0, the agent transitions the state 8c. if takes the special action ai Otherwise, the agent transitions to the absorbing state 8 and remains in that state in subsequent stages. The agent will receive the reward 1 if takes the special action di at the state 85,0 during the last stage H. Otherwise, the agent always receives reward O. In this scenario, for sub-MDP M,, the optimal policy entails following the special action sequence (a.,1 04,2. ..., H..H) ) to achieve a total reward of 1. In contrast, any other action sequence fails to yield any reward.
Now, we partition the K episodes to d/4 different distinct epochs. For each epoch (ranging from episodes 4(i 1)K/d + 1 episode 4 k/d)), initialize the state $1,0 and exclusively focus the sub-MDP M, The regret each epoch can be lower bounded separately as follows:
Lemma E.1. For each epoch E [d/4] and any algorithm Alg capable of deploying arbitrary policies, the expected switching cost in epoch i is less than H/(2 log K), the expected regret of Alg in the i-th epoch least (KK/d).
Proof of Lemma E.I. Given that each sub-MDP is independently generated, policy updates before epoch: only offer information for the sub-MDPs M M,- and do not provide any information for the current epoch i. In this scenario, there is no distinction between epochs and for simplicity, we only focus on the first epoch, encompassing episodes 4K/d.
Now, let ho = and we denote = {ki k2....} as the set of episodes where the algorithm Alg updates the policy. If Alg does not update the policy times, we k; 4K/d 1. For simplicity, we set C = 2 log K and for each i < H/C, we define the events & as the algorithm Alg has not reached the state $1,0 the stage iC before the episode kip
Conditioned on the events Ei,..., E,-1, the algorithm Alg does not gather any information about the special action 41Sh for stage h (i 1)C + 1. In this scenario, the special actions still be considered as uniformly randomly selected from the action set ag, 01. For each episode between k;-1 and k;, the probability that policy arrives at state 81,0 stage iC is upper- by:
[ Epyg ne a0 [ (r( = a1,x)] s Eny,e ne 10 [ 1)C+++ Pr(m)(s1,0) = aa],)] 20
24

---

where the first inequality holds due to TT$1.0) = 01.A) S 1 and the second equation holds due to the random generation process of the special actions. Notice that there are at most episodes between the - and k; and after applying an union bound for all episodes, we have
K 20 = =
Pr(E &,..), 11
K
Furthermore, we have
Pr(En//) < Pr(Ei n & n Be.ann..//eee (&jjc) 1 H/C
H/C
S CK
1K
(E.I)
Notice that the agent cannot receive any reward unless it has reached the state s,0 at the last stage H. Therefore, the expected regret for the algorithm Alg for the sub-MDP M can be bounded by the switching cost d:
Em (Regrett(AAg)) 2 Em[[(EH]C) (kule -1]
H 2 EMIkHIc 11 C
H
2 EM[1(6 < H/C) K/d C
2 4k/d-EMb 4KC
(E.2)
C
where the first inequality holds due to the fact that the agent receives no reward before kæzc conditioned on the event Ez/C, the second inequality holds due (E.1) with ky/c -1 K, the third inequality holds due the definition of ky/c and the last inequality holds due E[1 > a)] [[2]]/ /a for any non-nen -egaaivve random variable According to the result in (E. 1). if the expected switching [[]6] < H/(C)), the expected regret at least ((K)), when K is large enough compared to H.
With Lemma B.I, we can prove Theorem B.I.
Proof of Theorem B. I. For these constructed hard-to-lean MDPs and any given algorithm Alg, denote the expected switching cost for sub-MDP M; as 6,
According to Lemma E.I, we have
E,, Regret Alg)]
2 Pr (6 < H/ K)) K/d
2 (1 E,M, [6:] 2 2og K/H) K/d,
(E.3)
where the first inequality holds due to lemma B and last inequality holds due to E 2 a) < R[x)) /a for any non-negative random variable æ. Taking summation of (E.3) for sub-Mdps, we have
d/4 E E.M [eggre(AAlg]
EM [Regret( (Alg))
d/4
2
(1 [M. 2og K/H) K/d
(d/4 EM 2log K/H) K/d,
where 5 is the total expected switching cost. Therefore, for any algorithm with total expected switching cost less than dH/ (16 log K), the expected is lower bounded by
E EM Regret((AAl))) 2 (d/4 Em[0] 2log K/H) K/d 2 K/8.
Thus, finish the proof of Theorem B.I.
25

---

Proof of Lemmas in Appendix D
In this section, we provide the detailed proof of lemmas in Appendix D.
F.1 Proof of High Probability Events
F.1.1 Proof of Lemma D.1
Proof of Lemma D.I. We first prove that for an arbitrarily chosen [H], E holds with probabil- ity at least - H/H for all k.
For simplicity, in this proof, we denote VE (sh, as (fh where Jt Fn exists due to assumption. For any function V : S - [0, 11, let (V) (1% () aa [r(s of, s') + V
By simple calculation, for all f E Fh, we have
Σ 1E[k-1]
[2 ah)) +2 Σ
(fth) - (6h. Th (Vinn+1)
#E(k-1
E =E[K-1]
Vi,+ - 16hh a
- Σ
(1h + Vi - [h)²
iE(K-1]
Due to the definition of Jk.ns we have
Σ -(((),,a))-(((()..)))) (()) + 2T, VR,+41) S.O.
(F.I)
(R
Then we give high probability bound for -T(S, fk. Ve,t+1 through the following calculation. Applying Lemma H.4, for fixed and V, with probability least 1 5,
-I(.f.VV = Σ
(f(s). ah) - F(sh a()) (V)
iE(N-1]
8A Σ
(h) - a1)))
log
1
EEIK-1]
By the definition of V in line of Algorithm 1, Vi,441 lies in the optimistic value function class V/ defined in (G.4). Applying union bound for all the value functions V in the corresponding c-net yo, we have
- -TU.J,V S 1 Σ (1(shaah)) ((sh:ah)) 32 log 8
N.(k)
iE[K-1]
holds for all & with probability at least 1 5.
For all V such that ||V V I e, we have - 4e. Therefore, with probability 1 - 8, the following bound holds for I(f,f, Vk,++1);
N.(k) + 4c ht
- -TU. <
Σ ve(k-1]
(f(sh, af) (h)) + 32 log
To further bound I(JU,R. n. Fe. Vx, in (F.1), we apply an c-covering argument on F, and show that with probability at least - 8,
(Jaa(tha oh) - (i(hhh (h)) + 32 log Ne(k) Nz(())
-T(Je Ven+1) S 7
Σ iE(M-1]
8
26

---

+ 16LE k
(F.2)
for probability at least Substituting (F.2) into (F.1) and rearranging the terms,
Σ (t Ftt (sh. oh))) 128 log ((k)-Nz(e) H
+ 64Le k
1E(R-1)
for all & with probability at least 8/H.
Finally, we apply a union bound over all h E [H] to conclude that & holds with probability at least 1-6. 6.
E11. Proof of Lemmas D.2 and D.3
Proof of Lemma D.2. Similar the proof of Lemma D.1, we first prove that for an arbitrarily chosen
h [H) EL holds with probability least 1 6/H for all k.
In this proof, we denote T% Vr,A+1 (s af) as fū af,)) where fūz E Fn exists due to our assumption.
For any function V S + [0, 1]. let (V) = (r): + ((s - -Eg at [rn( a 8') + (s
For all f E FR. we have
Σ
1
(f(h)) ah) (k(shh +2 Σ
(fsh ah) (((sh: M (Ven+z)
(o2,)2
sE[k-1] (ōr,))²
VE k-
(U.iz.eentt)
[1h + 1 s()).
Σ
(or.))² Ir Vknht(sh)) Pt ah)]
(o,,a)2
(E[k-1]
sE[k-1]
By the definition of fe we have
Σ -OL
(Jealshh ah) PE(sh) 2T VaA++)) $ O.
(F3)
(o
=E[k-1
Then we give high probability bound for -I(fr,n fūz Ve,4+1) through the following calculation. Applying Lemma H.4, for fixed and V, with probability least 1 5,
-Vf...V)
Σ
(f(sh ah) - f(sh,, ah)) (%
(o
iEik 1]
1
(f(sh ah) F(sh, of))) 2
< 8A
X log g
(
1E(K-1]
By the definition of V in line of Algorithm 1, Ve.44 lies in the optimistic value function class V defined in (G.4). Applying a union bound for all the value functions V in the corresponding e-net yr, we have
-I..F.V9
Σ iE|k-11 (or.))² (((hh.ah) f(sh ah))
2 +
32 Ne(k) a²
log
holds for all & with probability at least - 8.
For all V such that ||V - V I e, we have (n)(()) mi (V9) < 4e. Therefore, with probability 1 - 8, the following bound holds for I(S, Vr,4+1):
-T(J. F. Ve = Σ -)(
(1(hh, ah)) - f(sh, af))²
32
log
Nekk)
+ 4e k/o²
(or.))
a² 8
27

---

To further bound I(fa,ee fiz Vi,N+1) ) in (F.3), we apply an e-covering argument on Fr and show that with probability at least
Σ (os,)) (fealsh. al) - oh)) + 32 log N.(k) N=(()
-I(fa,h Vantt2) -
8
iE(k-1]
+ 16Le kk/a².
(F.4)
Substituting (F.4) into (F.3) and rearranging the terms, we have
Σ sE[R-1] (or.))3 (fan(sh ah) (sh. af)) - 128 log Na(k) Nx(()
+ 64Le k/a²
8
for all & with probability at least - 6/H. Then we can complete the proof by using a union bound over all h E [H].
Proof of Lemma D.3. The proof is almost identical to the proof of Lemma D.2.
F.1.3 Proof of Lemmas D.4 and D.5
Proof of Lemma D.4. Similar to the proof of Lemma D.I, we first prove that for an arbitrary E [H]
k.h holds with probability at least 1 5/H for all k.
In this proof, we denote T% h+ (s), af)))=))))) as (o af,) where ft E F exists due to our assumption.
For any function V + [0, 1). let 7/h (V) = (r): + V - -Ey-ot (o ax 8') + V(s'))
For all f E Fh. we have
Σ
(f(sh, ahh - Pi (sh ) +2 Σ
Pun (Trn)3
(soh ahd (sh M (Venta)
(o
kE
iE(k-1]
(e,
Lin (o.,))²
Í.A (or,n)²
[rh + Vv. Vn (s)))² f(s), ah)]
Σ
(rh (inti(sh) Pt oh))
kE(k-1]
sE(R-1)
Due to the definition of fE.no we have
Σ
(o.,))² (Ranlsh, oh) (e(sh) + 2 Veh++) S 0.
(F.5)
-E[R-]]
Then it suffices to bound the value of Ilf. f. Ve,)+1) for all f. Unlike the proof for Lemma D.I, we decompose I(f, Ve.+1) into two parts:
Nu vE(k-11 (or,))2
Iff.f. Vk.b11)
Σ
(f(sh. af) - f(sh, af)) (V(+1)
Lin kE(R-1) (or.)² (f(sh, - f(sh, ah.) (V..--1 Vi+i).
+ Σ
(F.6)
Then bound the terms separately.
For the first term, we first check the following conditions before applying Lemma H.2, which is variant of Freedman inequality. For fixed ff and f. we have
Nih
E
(f(sh, ab) - f(sh ah) T. (V = 0. (G.,))2
since sh,t is sampled from Pa (- at).
28

---

Next, we need to derive a bound for the maximum absolute value of each 'weighted" transition noise:
iin (or.)22
(f(s), o/) - -(shhh T. (Vi+1)
max iE kE(k-1]
Mi,n (oi,a)2
$ 4 max -][
((shhaah) J(sh: ah))
< 4 max iE(k-
1
DJ (ELN5 (1-11,N)
i (or,a)² (1( - ((%%.15) + A TE/K-11
Σ
1] (
Ir (or,,)² (f(s), a.) - a7)) +1,
$ $4.72
Σ rE[k-1]
(F.7)
where the second inequality follows from the definition of Dr, in Definition 2.4, the last inequality holds since ot, 2 7 D'H, (ZL.s 11,- 2k- definition of Ti,n (D.6) we directly obtain the following upper bound of the variance:
(1-1)..)) according to line 19 in Algorithm 1. From the
iek (o).))
Σ
(f(sh ah) - f(sh. a()). th (V
E
iE[A-1]
1]
11m (os,h)²
$ 4 iE k]
(f(sh: af) - F(sh F(sh: 4L3k/a² V.
= Applying Lemma H.2 with V = 412k//22 2. = =2L/a² and v. = m = 1, for fixed S, J. k, with probability least 1 6/h222 Nz(e) -H).
1i (o.,))2
Σ
(J(s) a f(sh. ah)) (Vi+1)
(F.8)
VE 1-
i, (f(s) 2(6h)a)))2 +1 +1
<
2+1
(o
[E(k-1]
2
Ir (f(sh, 0.) - F(5h a5))² + x
+
2
8y
(F.9)
3
rE(R-1] (ōr,,)²
4
16
3
2
Σ
(J,,,)) )2
i in
(J(S), (h) ((8% + v2,
3²
2 2
(F.10)
rE(k-1)
-V 24t 22 16lt )+2)
(Ing( 44
Nz(()) Nz()
where : 21 (k:, 8)
6/H
Using union bound across all f. E C(Fr, E) and l 2 1, with probability at least 1 8/H,
Σ
(f(sh, ah) - F(sh, af)) (Vi+1)
(2
1E(A-11
4e
3
16
Σ rE]k-1]
in (1(() (()) + +x+ V2u +2, (F.1I)
(o
3
holds for all f,f E C(Fr, and k. Due to the definition of c-net, deduce that for fr and fr.
1,,
Σ
(fhn(shsaa) P2 (h))) (Vi21)
k
29

---

< 4t +
16
Σ
In (Tr,ha)
(fanl0))
- ())
+ +X+ v2r +20+ + 2 2
3
3
rE]k-11
+ 41 +
16
22-22
/16keL/a2 Sek/a².
(F.12)
3
For the second term in (F.6), the following inequality holds for all V Vk,++1-
(o (s(s), at) [() af)) (V -Vi+1) O.
(oi,n)² (f(sh ah) - F(0h/ of)) (V Vitta)
max xE[R-11
I 4 max iE (E[k-1] 1| (ōr.))² (f(sh oh) - f(sh/ ax))
< 4 max iE[k-1] (0i,h))
DJ, (21,i (-1,) E
(Jr,))) (f(s), - aT)) + A
TElK-1]
= =4.7
Σ rE]K-1j
(T,,))2 (1( a7) - [(8h ) + X,
where the calculation is similar to that (F.7).
We denote the sum of variance by Var(V vi+t) as follows for simplicity:
ies (Gr,a)
Var(V Vh+t)=
Σ
(f(sh aish T. Vieza?
(F.13)
1E[k-1] 1] S 1,? 12/ea
(F.14)
For Vi.h+1, we have
Linh
Var(Ve,t41 Vi+t)==
Σ 1E(k-1] 1]
E
(f(s) f(sh, att)²² M (Va.t+1 Vitta)
(or,aa
Ain (o,,a)²
Σ
(S(sh o(hh.ah)))
log Nr + log (K)
KE(K-1]
where the second inequality holds due to the definition of D.. in (D.6).
With a similar argument as shown (F.8)~((.11) we have with probability at least 22k
Nr(c)- (k 1). H), for fixed f. & and V. (applying Lemma H.2, with V = k LL/a"* and M = 2L/ , (log Nz(e) + log (K)) 112 = v
L (or.a)²
(f(sh, ah) - f(s), af)) M (V Vitt))
iE(k 1]
1 2 Var(VV Vitt) (logNN(e log log log (.K)))
i Tn (ār,)²
+ 3
2
8y -2
(f (.) F(8% 47)) + + (logNr(() + log (K))
rE[k-11
where
2k2 2 1og
1.2k(log (K)))) +2) (log(
4Lllog Nx(())NN(()), +2) -Nx(e) NN(k) a²
log
6/H
30

---

2h (2log 1itk +2) (log( 41 + 22 -N((c) -N2(K) S log
8/H H
Using union bound over all (f. f. V) C(Fh.e) c(F,,e) Vi, and all L, we have the inequality above holds for all such f. V, with probability at least 1 - 6/H.
There exists V k in the e-net such that [| VEG+illan S.e. Then we have
i.m (os,)))
(fralsh ai) (oh Th (VK,n - Vi+t)
12(k, h)
12(ki h 8)2
0
Vlg (c) + log (x)
7-2
D (or,h)²
(Imn(th: .7)) - PE ()) +1
rE[K-1]
h,
O(ckL/a))) log (x(c + log N₂(K)
(F.15)
for all & with at least probability 1 - H. Substituting (F.15) and (F.12) into (F.5), conclude that
Σ
(pe,((hh ah)) S2 (6))
(o2,))2
kE(k-1]
((7
< 00
12(k, h,
+ 12(k; h, 1, 1.) + +0 (lul(t
Nr (t))
+
+ log (e(
From the definition of in (3.3), we can rewrite the upper bound of the squared loss
Eiek--1)
Lrn (G
(fa.a(sh at) (1h. ah))) follows:
Men (or.a)2
(fen(sh a/) P2 .f.)
A+
iE(R-1]
Lik 2k (2log
+2) (log( +2) at 8/H
<
log
Proof of Lemma D.5. The proof is almost identical to the proof of Lemma D.4.
F.2 Proof of Optimism and Pessimism
F.2.1 Proof of Lemma D.6
Proof of Lemma D.6. According to the definition of D3. function, we have
( (s)
$ D3, (z) 162.1-111.1 11)1), x
x+ Σ
(fan(sh. ah) To (hh oh))
(o.,))3
$ 3. x D2, (2; 3/4 11 110.::01111110 11,b),
31

---

where the first inequality holds due the definition of D function with the Assumption 2.2 and the second inequality holds due to the events E%. Thus, we have
(s. V a)p s Be (2: 2[p- 13,6 1j,n).
With similar argument, for the pessimistic value function fk,n, we have
(Jan(s,)) - Tn aV)
< D2, (2) 2|k 11,b la 11,6) x A+ (os,)) (Fun(sh. oh) (hhh))s(
- 3 x Dj, (2) 2|2 111)),
where the first inequality holds due to the definition of D3 function with the Assumption 2.2 and the second inequality holds due to the events E/ In addition, we have,
- V a)1 BeD (zi 11,-11,6 k-1,))
Thus, we complete the proof of Lemma D.6.
F.2.2 Proof of Lemma D.7
Proof of Lemma D.7. We use induction to prove the optimistic and pessimistic property. First, we study the basic case with the last stage H + 1. In this situation, II, a) = (s, = Qk,r(s, a) and (s) (s) VRLA (s)
hold for all state s E and action a A. Therefore, Lemma D.7 holds for the basic case (stage H + 1).
Second, if Lemma D.7 holds for stage h 1, then focus on the stage h. Notice that the event En directly implies the event En+1. Therefore, according the induction assumption, the following inequality holds for all state s E S and episode k [K].
VR,++i(s) 2 ( 2 (s).
(F.16)
Thus, for all episode E [K] and state-action pair (8,a) E S x A, we have
fa,(ss a) (s,n(s, (s,
2 Th V (s, - Br Dyn (2; 21: 11k ( k111),n) + -
Ta VA V (3, - (i((sa)
PA P (8,
20. 0,
(F.17)
where the first inequality holds due to Lemma D.6, the second inequality holds due to the definition of the exploration bonus by, and the last inequality holds due to the (F.16), Therefore, the optimal value function Q (s, a) is upper bounded by
(s, a) I min { min (s) + b s (s,nss
(F.18)
where the first inequality holds due to (R.17) with the fact that Q7, (8, a) S 1 and the second inequality holds due to the update rule of value function QK.
With a similar argument, for the pessimistic estimator Su,n, we have
(s, (s, a) (s,
< Ta V Bt. DDr (2; 2[4-1],b 111,0 (s. (x,
< Th TnVnniiss,0 Qñ(s, a)
Pr Va (8, - 1
S 00
(F.19)
32

---

where the first inequality holds due to Lemma D.6, the second inequality holds due to the definition of the exploration bonus bR, and the last inequality holds due to the (F.19). Therefore, the optimal value function Q% (8, a) is lower bounded by
(s. a) max
(s, b,, 0 2 (s, a). ISSK
max
(F.20)
where the first inequality holds due (F.19) with the fact that Q (s, a) 2 0 and the second inequality holds due to the update rule of value function Qu,
Furthermore, for the value functions VA,h and VE, we have
Vs,n(s) = max (s,a 2 max Q% = (s),
(s) = max (s, a) max 07 (s, (s),
where the first inequality holds due to (F.18) and the second inequality holds due to (F.20). Thus, by induction, we complete the proof of Lemma D.7.
E3 Proof of Monotonic Variance Estimator
F3.1 Proof of Lemma D.8
Proof of Lemma D.8. According to the definition of D3. function, we have
(fen(s,a) - -aii))--VVVaaae (V
$ DJ (2) 1]. Th 11,b) x A
(fan(sh. ah) - Tn (V
(ox,))²
s 3 Dj, (2: 2(k- b) 11,)),
where the first inequality holds due the definition D3 function with the Assumption 2.2 and the second inequality holds due to the events E/. Thus, we have
( a) VAVK, a)l Dr, (2: 7Pe- 1).b: T I-1)).
For the pessimistie value function Je.n have
(F,n Th as)
(oxn)3 (Fan(sh - ( ()
$ D3, 11, T.p 11.b) x
A Σ
1)
< x D2,, (2; 2pa- (].n. 11.)),,))
where the first inequality holds due the definition of D3. function with the Assumption 2.2 and the second inequality holds due the events g/. In addition, we have
& (s, a) To Vi a)l S B3 Dr, (z; IIk- x-1.)))
With a similar argument, for the second-order estimator Jh we have
(F -T (s)
< D2, (2; 2 --- 1j,n)) x
A x Σ (os.n)2 (Frilshh ((Vent1(shaaa))
< 3 D2 (2) (2 -1-))),)
where the first inequality holds due the definition D3 function with the Assumption 2.2 and second inequality holds due the events gf, Therefore, we have
fr. a) TVV a)) < 3r (2; 21- 11 o 11.b).
Now, complete the proof of Lemma D.8.
33

---

F.3.2 Proof of Lemma D.9
Proof of Lemma D.9. First, according to Lemma D.8, we have
V +1 (sh ax) - [V af)1
J.. P2 - & ( (IPn (1 (x)) x/
x PEr (IEn
F - [Px [P (s at)
$ 2L fr.h - -(PAVe. a + |Fk, - [P V2 V
11 x%)
S (2L3k + Dr) (2; at 11 1s-
E
(F.11)
where the first inequality holds due to la + bl S |a] + (6], the second inequality holds due to la² ba1 = aa bl la + b) $ a bl max((al (6)) and the last inequalirtnholds due to Lemma
D.8.
For the difference between variances [VAVeN+al a and (Va ( af). it can be upper bounded by
[V A+ (( at - IVn at))
VP V2
k. att) - (I (P.VV [6 )² (Pa 16 a V )²
[P V2. A s/ d - P (5 at) + VI oh)) (Pr V ati))
([Fx, VA, 4 ( ) - [ af))
(IP^ V4 V [ a [Px V. v. (sh at))
S (s a ( at)) + 23, Dr, (2; 216-
(F.22)
where the first inequality holds due to la + bl S |a| + 16]. the second inequality holds due to 1 12 (.))+1(-)2 2 (-) 2 0 (Lemma D.7), the third inequality holds due to (%-1()= 2 (+))+(+)) (Lemmaa D.7) and the last inequality holds due to Lemma D.8. Combining the results in (F.21) and (F22) with the fact that 0 & (-),+1(),, Vi++ S 1, we have
V Ve a Vi afl
< V a [V VVAenn ab) + Veatals5 att - IV Wi at
< Fx,h + Fk.
Thus, we complete the proof of Lemma D.9.
F.3.3 Proof of Lemma D.10
Proof of Lemma D.10. On the events Eी and El we have
V (Vent ( a
[P((Vi141 Vitta) at) ([PA (i++)((s,, at))
< [PA(VeNtI - ? a
S 2(PA (Ve,t+1 Vit ( a
< 2 (IPA V.. att) Vr. + (s aj))
< 2 V2. a - (( of)).
(F.23)
where the first equation holds since the reward function is deterministic, the second inequality holds due to Lemma D.7 with the fact that S Vr,4+1 (s), ( S and the third inequality holds due to Lemma D.7 and the last inequality holds due the fact that Vi,411 2 Vi,+1-
34

---

With a similar argument, on the events ε and E we have
Va - Vin+t) a/))
PV ( att (PPn(Vit) V a²))²
S [PA(VE+I
S 2 2FP (Vh+1 Vin+1)] (s/ afp
< 2 VE,N+ 16 a - [Px Vi, (8 af))
- 2 (1P VA, 1] o - [Px + af)),
(F.24)
where the first inequality holds since the reward function deterministic, the second and third inequality holds due to Lemma D.7 with the fact that 0 I (s), ( S H, the last inequality the fact VI, S Vi,++1 (s). For both variances [Va(Vi,++1 Vi+1)) (0%, at)) and
[VA(Vitt V) ah), they are upper bounded by
((PPA. vI a - [P Vn,n+ 11(+ af))
= 2Th Vo. aht - 2Tn V Ven++1 (5 af)
< ( a 2 (5% a + 43 Dr, (2) (13 (1-111)
(F.25)
where the first inequality holds due to Lemma D.8 and the second inequality holds due to the definition of Fk.h. Substituting the result in (F.25) into (F.23), (F.24) and combining the fact that
(V V[++1] ) [Va - V. (s a I 1, we finish the proof of Lemma D.10.
E4 Proof Lemmas Section D.4
F4.1 Proof of Lemma D.11
Proof of Lemma D.I.. We use induction to shows that the conclusion in Lemma D.7 and events E/, E hold for each stage h E [H]. First, for the basic situation (stage H + 1), Qk. a) (s,ss, a) = (s. 0 and (s) (s) = (s) 0 hold for all state e S and action a E A. Therefore, Lemma D.7 holds for the basic case (stage H + 1)
Second, if Lemma D.7 holds for stage h + 1, then focus the stage h. According to Lemmas D.10 and Lemma D.9, we have the following inequalities:
o = [VnVs,t a + Ex,, + D.,. 2 [V 1lsh ah),
Nx(() + log N₂ (K)) [Va(Ve, V ah): o,k 2 FLN 2 (log N
o 2 F.N. 2 (log (c) + log N. (K))
-V
- Vi (sh af),
where the first inequality holds due to Lemma D.9, the second and third incquality holds due to Lemma D.10. Thus, the indicator function in events E/, and ε/, hold, which implies events E/., e hold. Furthermore, when events of. e/ hold, then Lemma D.7 holds for stage h. Thus, we complete the proof of Lemma D.11 11 by induction.
E.4.2 Proof of Lemma D.13
Proof of Lemma D.13. For each stage h, divide the episodes {1,2, K) to the following sets:
I {k [K] Dy, O0 2 1),
Ig {1 E [K] (=)((=77 < 1, =0k,h
Ig {A E [K]
Dy 1 < 1,ōR, =a),
I = {k E [K]
< 1,0kk DJ (2; 2|1-1],b 1]. (111),))
35

---

The number of episode in set 21 is upper bounded by
IZ
Σ min (D3, (2i2)-1111 o 11110, 1) S dima, (Fr)) RE
where the equation holds due to D (zi F[k-1] b] :b..:::::-ee.... 11.b1),a//oz 2 and the inequality holds due to the definition of Generalized Eluder dimension. Thus, for set Σ,, the summation of confidence radius upper bounded by
min (2 2k- 11 o 1,), & I1 < dima, K (Fi)-
(F.26)
RET
For set Iz, the summation of confidence radius is upper bounded by
Σ
min (9Dr) (2; 2(A 11.n. lh- (kk,).)) 1)
k
$
BD (zi 2pk 11. 111h))
ke
< 3
ohin-
DJg (2; -
kELZ
KEZZ
$ /V dima, K (Fr)
Σ oi
(F.27)
KEIz
where the second inequality holds due to Cauchy- inequality with σ ōR and the last inequality holds due the definition of Generalized Eluder dimension with the fact that Da, (2: =1k-1],,, (R-1).)))))))) /ēk, < 1.
With similar argument, the summation of confidence radius set Ig is upper bounded by
min
(3Dx, (2; 2|k- 1),n, 1,, 11.n)
3Dy, (z) 2t 11.1s 11,11, -1,b)
kETa
Σe² a².
Σ NETa
D2, (2) 2p- 11.b: T 11,,1////
V
hETa
B // dima, (Fi)
Σ heIa
a²
(F.28)
where the second inequality holds due to Cauchy-Schward inequality with ōR a and the last inequality holds due to the definition of Generalized Eluder dimension with the fact that Dy, (z; (1,_),,,, 11.)), ///bh 1.
Finally, the summation confidence radius over set I₁ is upper bounded by With a similar argument, the summation of confidence radius over set I3 is upper bounded by
Σ
min (8Ds, (z; 1|,- 0 1111),,),11
KET4
S Σ
BDr, (2; 2k 1111)),))
kEI
= Σ
D2 (2; 11 T 11,b 0
KEI.
< 37 dim K (Fr),
(F.29)
where the first equation holds due to Th = y D (z; 111 -1-)) and the last inequality holds due to the definition of Generalized Fluder dimension with D,s, (2; F[6-1], 11,)) ōx.a 1.
36

---

Combining the results in (F.26), (F.27), (F.28) and (F.29), we have
(1: 11 min
k=1
S (1 + 3y,) diimm..xxF.. + 23 (dima..(F))
Σ (o + a²)
Arm
Thus, we complete the proof of Lemma D.13.
F.4.3 Proof of Lemma D.14
Proof of Lemma D.14. First, for each stage [H] and episode & [K], the gap between Va,a (s
and V (sh) can be decomposed as:
Vi,a - Vi (s%)
= -K ah) - QT (sh, att)
S min (Phanth(s a) + (8, - Vi
+ Th V at))) Tn V (s a/)))
[PPh (V Vi+ti] (shi at) min (3mm Drn (zi Fihma 11 Thn Thun 11,b), 1) min (s 1)
[P Vi+t (s a + 2C min (Brm Dr, (zi Pak - 11./ Ibmm 11,11);
[P - V (s ) + +0 x) min (3x D (2; 21-- o 11.h),
( V (5h+ + (Ve. V ) (s a V Vit (sh++ + +2C(1 x) min (3 Dyr (z: 21k- 11, -R.))))
(F.30)
where the first inequality holds due to the definition of value function & at), the sec- ond inequality holds due to Lemma D.6, the third inequality holds due to bran (8f, at) < C Drj (2; 11 -1),a) and the last inequality holds due to Lemma G.2. Taking summa- tion of (F.30) over all episode &e E [K] and stage h' h, we have
Σ (s),
VØ (sfi)
K
11
(Pr(VVLAII (s a (Vin+i(shtt)) Voti (sf((sh+1))
k=1 W
H
20 + x) min (3. (z; 11, o 1k-
k=
Σ 20(1 + +x) min (x; 1)
K "
+2
Σ
- -f (00(222H10)))) 2 21g((2232/0) + 22ogg(2
k= W=
" Σ F=h
"
K Σ
20(1 + x) + 3e72) dina,, (Fr) + Σ
40(1+x) + x)3x hadii//iiiii..... ((F))
/dima,
Jo + a2)
k'=h
K H
+ 2
VA - vrt ( o (og(222H///))) 2/oog(2K22//) + 2
A=1 W==
37

---

H
K
H
$ 2CCH( + x) + 3x72) dima, + 4C(1 + x)3xg
dima, K (Fic)
Σ
(o
+
W'=h
k=1 1
K
H
+2
Σ
(V - VV af) log((k222))) (agoaai-_-elll(ldodo)og222// + 2 log(2k22/0)) + 2log(2k
K H H
< 2CH(1++ + +x((1+ + 3x7²) dimo, 40 + x)3,, di
(o + 02)
k=
K
H
+ K=IA-
VA - ViD)((s) a log(2k>H/00 + 2 2o/oo(22>2 + 1og 1/0),
1//0
(F.31)
where the first inequality holds due to (F.30), the second inequality holds due to event ε,, the third inequality holds due to Lemma D.13, the fourth inequality holds due to Cauchy-Schward inequality and the last inequality holds due to = dim (Fwr) S E dim K (Fw) = H dim K (F). Furthermore, taking summation of (F.31,, we have
PA vx+1)] (s (.
K
(Vin+1(sh (+++2a)
[Ph(Ve,t41 v ah) (Venn1(Shit)) -vat (oh+)))))))
1=1
K
Ven4i(6hh11 (+h+1a))
1=
+2
Va(VaNt1
(20))//222//1))222222)2 2 (1181118)))
k= A=1
22CH2 + x) 3 dim (C))
+ (1)) dima, ((FN)
H
o a
A=1
H
+ H
2
VV.VV -V V
(2 + +200))+++
where the first inequality holds due to event E, and the second inequality holds due to (F31), Thus. we complete the proof of Lemma D.14.
E.4.4 Proof of Lemma D.15
Proof of Lemma D.15. Similar to the proof of Lemma D.14, for each stage [H] and episode
k [K], the gap between (s,)( and (s)) can be decomposed as:
(( - (st Qu.A (s), a Qn,n(st att)
I min (fmeethss,) a) b (s, (s, a), a)) -Th Vn,n+ at)
- max (Jhnnhh (8, a) b (8, Th Th
38

---

+ VA o/)) - -Th Vant22 a%)
Ph (VK,h+1 - VA,++1)] (sh: att + min (Bkm Drn (2; Fllon- 11 0 (1he--1).b (,)) 1)
+ 2. min (Dimmi (5 a.) .)).))
Ph (Vi,h++ VAnuta) (sh ) + 4C min (Shm Dan (2) 2l b:: o Tksee 11,be); 1)
[PP((V - Ve, (sh: o + +C4C(1 + x) min (3 D5, (2; (z; 11 Tl (1,)))))11] 1)
Vo.n+1 V + [PP - Van++)] (sh aB) V - V
+ +4C(1 + x) min (5x (2: 2Qk- ll (Tk-),,),,
(F.32)
where the first and second inequalities hold due to the definition of (s, and (s,)(,H),, the third incquality holds due to Lemma D.6 with BRE. 3Re.. the fourth inequality holds due to A a C- Dy, (2) ziMuu l).b. (Ma 1].A) and the last inequality holds due to Lemma G.2. Taking a summation of (F.32) over all episode l E [K] and stage h 2 ht we have
K
(sh) - (x
K
H ([Pa(VEA411 1 a7 (Van+i(sh+t)) (
H
40(1+ + x) min (z; 1 ( -1,n),
k=1h==h
K H
40(1+x) + min (2: -R-
1m 1 h mm
H Vu V ( 1og(23331))) 22gg0)) + 21og(2k
+ 2
k=1h==h
K Σ fo + a
Σ
4C(1 + x) + Bun²) dima, K (Fw) + Σ SC(1 dima.
H Σ
+
< 4CH(1+ + xx Ban?) dima, (Fa)+ 8C(1 x)
dima, (Fw))
Σ Σ
2o + a
k=lW=/h
H Σ
+2,
(V V log 2 (og(2K2H/0) + (210/)))2222g///// 2log(2K
K=1A'sh
4CH(1 x)11+ + Ba72) dima. (Fr) + 8C(1+ x)3x, v dima, ((F)
H
h, + +
1=1
Σ H
[V Vr,N+1)((s) - at) (0g 2gg ( 21og
+
(F.33)
where the first inequality holds due (F.32), the second inequality holds due to event &,, the third inequality holds due to Lemma D.13, the fourth inequality holds due to Sauchy-Schwarte inequality and the last inequality holds due to Md' dima, (.nnn.FFFr (Fw) E dima. (Fw) H dim x (F).
39

---

Furthermore, taking summation of (F.33), we have
H
(V (sh
K
H
(Ve++1(s - (e.++(0hh+1)
H
[PA(VVRA+ Vann+a)] (sh att (Ven41(6h+tz) vantt(sh++1))
h=1
(1,tt((hh+)) - (
k=1k=1
H
#11
2
Va(Ve.t1 1 at) 10g(2k2118) 2/10((2K21/0) + 21og(2k
k=1h= ==
$ 22CH1 x) 3, dima, (F)) +x) dima, (F),
11
o +
2H
2
(Vn Vx log(2 (100//22000// 1og(2K2H166)
where the first inequality holds due to event &g and the last inequality holds due to (F.33.. Thus, we complete the proof of Lemma D.15.
L
F4455 Proof of Lemma D.16
Proof of Lemma 16. According to the definition of estimated variance dg the summation of variance can be decomposed following:
K
H
K
H
Me. 4a a + Eu, + Fk.b
h=
K
H
(V Veaai att 168
Ei.h
F
k= h=1
k= k=l
H
oft WV Vot
Wv V
(8
k= -=1
16
(F.34)
For the term 7, it can be upper bounded by
H
K ΣΣ
1= -=
(e af) -V Vo att)
Ex
(F:35)
==
1=1
where the inequality holds due to Lemma D.9.
For the second term I2 = Σk Σ Eu,o, we have
K
Σ Σ (2L + 3R) min (1, (1, 2/p 1).br 11.1)
Exhh
k=1h=1
40

---

H
(2 + Bx) x (1+ 72) dimo. (FFi)
h=1
K ko + a2)
+ Σ (2L3x + Bb) x 2 dima, K (Fi))
h=1 1
k=1
$ (2L Bx)H (1 +1+ ?2) dima,
H
K
H
+ (2L3x + 3b) x 2
Σ
dima,
(o +
1=1/=1
(2L + Bx)ll x (1 + 7²) Hiima,((3
+ (2L3) B&) x 2 dima, (F)
H
Ro + a
(F.36)
k=1h=1
where the inequality holds due to Lemma D.13 and the second inequality holds due Cauchy- Schwartz inequality.
For the term I3, we have
K
H
13
F
h=1
-llog (e) + log (K))
K
"
x
min
(1,2fu, ah) 2
a/) 43. (25 (2.2 o1k-11.11)
1==1
S (log (c) + log No (K))
K
H
min (1, 2T. Ve, ( (0%,a))
2T VT (5 at) +5, (); (2; 11k- -(1-
h=1
S (logNFF NF(e) + log (K))
PP V oht)
K H
+ (x(g)>((e)ao) + log N₂ (K))
min (1,88 (2; 2/p 1].b -(==)
k=1 h=1
"
N=(e) + log N. x
Pa(VENtI - Vn. VA (sh att)
(log log (K)) (1 + 88 2 dima, (F)
K H
+ +(log Nz(c) + log N.(K)) x 1633 v (FF
Σ
(o + a2)
(F.37)
k=1k=1
where the first inequality holds due to Lemma D.8, the second inequality holds due to Vz,++1-)) > (++r(+) Z (+)+ the third incquality holds due Lemma D.13 with Cauchy-Schwartz inequality. By Lemma D.15,
ΣΣ
PR V att < 4CH x1 Ber2) dim (Fr)
k=1k1
K
+ SCHC + /dimaaiik
H
(o + a.)
1=1æ=1
41

---

K H
+ +2H
(A - VE l log(2K2H/0) + 2 (og(2K2H/0) + 21og
k=1h=1
K
H
(FF 4CH + x) + 3 ( 8CH x) dima, (F)
H
(o
a?
+Ō(H ΣΣ P Ve,++)) -a
(F.38)
where the last inequality follows from Lemma D.7.
Notice that for each variable z, avvi + implies S a² + 2b, from (F.38), we further have
K
PA(VE,t+1 Vk.n+1) (sh.
<ō
CHP(1 + x)(1 + Bu7²) dimo, (Fr) CH(1 + x))ax dimm,
H
Σ
Co + +a2)
(F.39)
Substituting (F.39) into (F.37), obtain the following upper bound for Is.
K H
13 Ō (log (log (=(()) log
(K)) H 33x log
dimo,x
MEX Σ k=1h=1
R +
+ +0 ((te
11 BAT?) dima. (Fi))
(F.40)
For the term 14, we have
K
H
4
(V (Va
(VaV aft))
k=
k=1
K
t att Vir ot))² PA at) + (IPb Vi ati)
K H
k=1 h=1
K
2
PA PA aft)
h=1
K H
< 8CH x) + Bx (kimn,x(F + 16CH + x) ((F
2
+ a²)
k.
k=1k=1 h=1
K H
+2H 2,
Σ (V Va v a4) log(2 (og(2k2H/))+ + +2
+ log (2K 22
K
H
σ H1 (1 din,, (F) H3 (F)
H
Co + a2)
(F41)
k=1ı=1
where the first inequality holds due to V+,4+1(-) (+++(() 2 W (+), the second inequality holds due to 0 < (-), V (.) < 1, the third inequality holds due to Lemma D.14, and the last inequality follows from Lemma D.7 and the fact that z 5 aaz b implics S a + 2b.
42

---

For the term 1s according to the definition of Vark. we have
Is V V. og) Vark-
(F.42)
Substituting the results in (F.35), (F.36), (F.40), (F:41) and (F.42) into (F.34), have
k,
k=1
1 12 13 + + Is
θ (4L8x + + x (1 + 72) dima. K (F)
K H
+ (4LBs + 28k) 2 (dd
(o a2) + Vark
1=1h=1
K H
+ +8CH2(1 + x)(1 + Ba7 dima,x(F)) + 16CH(1 + x) /dima,
H
(o + a2)
1==1
+ (log Nx(c) + log (K)) H (F)),
H
(o +
k=1k=1
+ (x() Log 2 + BaT dima, (Fr))
Vark + (log (log (og x Õ(( + +3x + 13 + BB) dima, x (F))
K H
+ (log NN(e) log (.))) δ (Bs - H3, + 3R)) dima. (F)
(o + a2)
k=1h=1
Notice that for each variable x, r S avvi + implies I S sa² 2b. With this fact, we have
k S (log Nz(() + log Nc)) x 5((1 (3x H3x + Ba) H dim x (F))
+ (log NN(() log N. (K))² x Ö((8 + -3.. + 3.) 2 dima. K (F))
Ö(Vark 2
Thus, we complete the proof Lemma 1.
G Covering Number Argument
G.1
Rare Switching
Based on the policy-updating criterion, the following lemma provides a upper bound of the switching cost.
Lemma G.1. The number of episodes when the algorithm updates the value function is at most O (dima,.(FF) H).
Proof. According to line 9, the policy is updated at episode only when there exists a stage h [H] such that
Σ
1 D2, (24,4i PPrnat 11,b: Breat- 11,b) 2 X/C.
Ve vE(kiost, 1]
43

---

and
Σ
(z,,i F[ktour 1j,h < X.
(G.1)
oih
EE Feust
Then the following inequality holds,
EiEp in
1 (fi(zin)) - f2(2i.))2 x
sup f..feTT
(G.2)
EiE(I ai (f((ze,)) - f2(2),)))2 +
Eielhrant 2- a.A (fi(24.N) - f2((2,,))2
=1+ sup fuhet Eie(I -1] iih
(fi(za,)) - f2((2,))) +
< 1 +
Σ
D3,, (Zi,hi (hha 1) (kaae
o2 8E k
1 X:
(G.3)
where the first inequality holds due to the definition of Dy, (Definition 2.4), the second inequality follows from (G.1).
(G.3) further gives lower bound for the summation
Σ
(2,,
2b- (1-1)
k 1]
Σ
1
D2 "hhan -1 11ame-1).h)
1+X tE klase
i.
X/C
1+x
Note that x/C I 1, we also have 1+x
X/C
min
1, -
1+x
Then we have upper bound and lower bound for the following summation:
IK x/C
K
H
(z 1 o 11m) } s dimo, H.
< min
1, - -
1+X
k=1h=1
Therefore, the number of policy switching 4x is of order O(dim, (F) -).
Lemma G.2 (Stability of uncertainty under rare switching strategy). the policy is not updated at episode k, the uncertainty of all state-action pair = () E x A and stage h E [H] satisfies the following stability property:
1 D2, (zi Flki 11 7 11,
Dj, (z; 11 o -1.))
2 1 1
Proof. Due to the definition of kiast in Algorithm 1, we have
Σ
Dz Mera - 1l Thee 11,h) < XX
o
ie Kelmma.k 1]]
As is shown in (G.3), here also have
EIELA-1] h. (fi(ec.) - f2(
sup
Eig(1A 0. (fi(ze,)) f2(2.,))) +1
fi.fEFF
44

---

From the definition of Ds.
D3, (z: qp- 1). T(K-1),)) 2 1+X
D3g (2; Minn - 1].b 0 Moan -1aue11)a)
The proof is then completed due to the arbitrariness of h.
G.2 Value Function Class and Its Covering Number
The optimistic value functions at episode k and stage E [H] in our construction belong to the following function class:
V max min min (1. 3.b( aEd 1815
V&,b
(G.4)
where 44 the number of updated policies as defined in Algorithm fi E Fn and b B.
Similarly, we also define the following pessimistic value function classes for all 1:
V = V max max max (0, (().a)) - (.b())))))b()))) b(,,a)))
(G.5)
aEA 18154+1
Lemma G.3 (e-covering number of optimistic value function classes). For optimistic value function class VR, h defined in (G.4), we define the distance between two value functions V1 and V2 as ||V oo == max,es V (s( - V2(s)). Then the e-covering number with respect to the distance function can be upper bounded by
(k) [Nz(e/2) ((B.)
(G.6)
Proof. By the definition of (NF, e), there exists an net of F, denoted by ((F,c//2) such that for any f E F, we can find f' E C(F,e/2 such that | f'll S e/2. Also, there exists an e/ e/2,B-net of B,
Then we consider the following subset of Vk.
v max min min (1, + B (,(, c(Fn, e C(B,e/28)
aEA 15154++1
Consider an arbitrary V E V where V = a each f.. there exists f C(F, e/2) such that II - ff 2 c/2. There also exists & E C(B, e/23) such that ||b b I e/28. Let V = max.e. m min mf + (.)))))) V It is then straightforward to check that VVV V S < 3 8
mi, + 8. (.(..a)). For
By direct calculation, we have |V = [N e () N(B,,e28))
Lemma G.4 (e-covering number of pessimistic value function classes). For pessimistic value function class V,, defined in (G.5), we define the distance between two value functions Vi and V/2 as ||V Vz == max,es (vi(s) (2(s)) Then the c-covering number of V22 with respect to the distance function be upper bounded by (e(k) defined in (G.6).
Proof. The proof is nearly the same as that of Lemma G.3.
H Auxiliary Lemmas
Lemma H.1 (Azuma-Hoeffdinn inequality). Let {-:}]_] be a martingale difference sequence with respect to filtration (G,) satisfying |a;] < M for some constant M, 2; is Gi-r-measurable, B|a; [+]] = 0. Then for any 0 < 8 <, with probability at least - ō, we have
n
Σ
Φ < Mv 2n log(1/5).
45

---

Lemma H.2 (Corollary 2. Agarwal et al. 2022). Let M > 0, 0 be constants, and (ai)ee|s) be stochastic process adapted to filtration (Hi) Suppose E|z,|H;-11
b I M and Mag I v2 almost surely, Then for any ö,e > 0, let c =
log 12 (2 /mm)/m/))))))))) we have
P
Σ iEM
>
2
2
E Esr H4-11 + x2
2 +
2 max | + +mm
S 8.
3
veld
sEld
Lemma H.3 (Lemma 7, Russo and Van Roy 2014). Consider random variables (Zn, E N) adapted
the filtration (Ha, n 0, 0,1,... 1,.... Assume eex [AZ;) finite for all X. Define the conditional mean 14; E i2 Hi-1). We define the conditional cumulant generating function of the centered random variable [2 [4l by 4/ (A) log E (exp (A [Z, p.]) H4-1). For all 2 and 2 0,
n
Σ
XZ S x Σ
Aau + th (A) Vn E
2 21-
Lemma H.4 (Self-normalized bound for scalar-valued martingales). Consider random variables (Ux In E N) adapted to the filtration (Hn 0,1,..). Let {n: ) be sequence of real-valued random variables which is 1441-measurah
and is conditionally o-sub-Gaussian. Then for an
arbitrarily chosen À > 0, for any 5 > O, with probability at least - 8, it holds that
2a
Σ G. S 1=1
2 + log(1/6)/A
Vn E N.
2
i=1
Lemma H.5 (Lemmaa 10, Zhang et al. 2020). Let (Mr) be martingale such that Mo = 0 and
JM, MM-1l S for some and any n 2 Let Var, = Σi= [[MM, MM- F for
2 O, where Fū (M,, My...., Mx). Then for any positive integer and any E, > 0, we have that
()) p
2 elog (1)
()) p
P
Mnl 2
Var, log
2c
(2ne² 2) p
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer:[Yed Yes]
Justification: In both abstract and introduction, we highlight the contribution in our paper. The proposed algorithm and the corresponding theoretical results are discussed in the followed sections.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
46

---

Answer: [Yes]
Justification:
We explicitly list all the necessary assumptions for our theoretical analysis.
Guidelines:
The answer NA means that the paper has no 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 asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it 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 address 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 that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We state all the assumptions in Section 2 and give the proof of theorems in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
47

---

Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, 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 dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel urchitecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is 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 large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions 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 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 reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to 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, described in supplemental material?
Answer: [NA]
Justification: 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/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / /twpps.cc/ppp//e wwtpccpwwppppcceeeeeeeeoooeppeee /Codeeeomiisssseeeeooeeee sssssnoliccy for more details.
The authors should provide instructions 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 subset of experiments are reproducible, they should state which ones are omitted from the script and why.
48

---

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 is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate 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 are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
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.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to 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 the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the 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.
49

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
cechiiescllllliic le ines?
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
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 circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper is theoretical work with societal impact.
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 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 specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate point that 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 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 mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
50

---

Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere 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.
We recognize that providing effective safeguards is challenging. and many papers do not 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: [Yes]
Justification: We have described the related works, especially those work which our work based on with proper citations in corresponding sections.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, 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 be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license 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 assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [No]
Justification:
This is theoretical paper without experiments.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
51

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not include crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, 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
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?
Question:
Answer: [NA]
Justification: This paper does not include crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the 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.
52


Reviews:
[{"review_id": "HHU1rSWCjX", "reviewer": "Reviewer_6wYy", "summary": "The paper studies reinforcement learning with general functional approximation and proposes a near-optimal algorithm with low policy switching times.", "questions": "You have proposed an algorithm that achieves optimality of regret of switching costs simultaneously under the condition that $K$ is large. Also, the lower bound from Theorem B.1 suggests $\\tilde{O}(dim(\\mathcal{F})H)$ is unavoidable when one wants to achieve a regret sublinear in $K$. Obviously, the current results will not make sense if the number of episodes $K$ is relatively small compared to the length of episode $H$. I am thus wondering: do you have any insights (what can be done and what cannot be done) in this different regime?", "limitations": "There is no obvious limitation in this paper.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The paper is very well-written, and the main results of the paper are of high quality. The authors improved prior works on RL with general functional approximations to get an algorithm that achieves both the near-optimal regret and the lowest possible switching cost when the number of episodes is large. Besides, the proposed algorithm is intuitive and clean, and the proofs are well-written and easy to follow.", "weaknesses": "It would be helpful to provide a bit more details for readers (like me) who are not very familiar with the literature on RL with policy switching cost on how to obtain the counting of switches in Table 1. For example, [1] doesn't seem to optimize the number of policy switches (while only trying to optimize the regret); since the paper is directly improving upon [1], it would be helpful to provide a more detailed discussion on why [1]'s algorithm needs $\\tilde{O}(dim(\\mathcal{F})^2H)$ number of switches and why the authors' algorithm can strictly improve upon the number of switches to $\\tilde{O}(dim(\\mathcal{F})H)$ without worsening the regret.\n\n[1] Agarwal, Alekh, Yujia Jin, and Tong Zhang. \"VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation.\" The Thirty-Sixth Annual Conference on Learning Theory. PMLR, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer 6wYy\n\nThank you so much for your strong support! We address your questions as follows.\n\n---\n**Q1** It would be helpful to provide a bit more details for readers who are not very familiar with the literature on RL with policy switching cost on how to obtain the counting of switches in Table 1. For example, [1] doesn't seem to optimize the number of policy switches (while only trying to optimize the regret).\n\n**A1** Thanks for your suggestion! In [1], to compute the bonus function, the authors slightly generalize the method proposed by [2] (see Algorithm 2, [1]). According to Theorem 1 in [2], the utilization of this online subsampling subroutine will automatically lead to an $\\tilde{O}(\\dim(\\mathcal{F})^2H)$ switching cost guarantee. We will add the explanation for the result shown in the table in the revision. Specifically, [2] employs online subsampling techniques, which maintain a small 'core' set of the history data and the policy is switched only if the subset is updated. In contrast, our algorithm applies a novel uncertainty-based policy switching strategy, which directly controls the cumulative sensitivity of historical datapoints.\n\n---\n**Q2** You have proposed an algorithm that achieves optimality of regret of switching costs simultaneously under the condition that $K$ is large. Also, the lower bound from Theorem B.1 suggests $\\tilde{O}(\\dim H)$ is unavoidable when one wants to achieve a regret sublinear in $K$. Obviously, the current results will not make sense if the number of episodes is relatively small compared to the length of the episode. I am thus wondering: do you have any insights (what can be done and what cannot be done) in this different regime?\n\n**A2** Thanks so much for your insightful question!\n\n- For the regret bound, when restricted to linear MDPs, our regret bound still suffers from the $\\tilde{O}(H^{2.5}d^5\\sqrt{H + d^2})$ $K$-independent term, which will be the leading term when $K = O(H^4d^8(H + d^2))$. If we aim to achieve better results in the small $K$ regime, it is crucial to improve the $\\tilde{O}(H^{2.5}d^5\\sqrt{H + d^2})$ term in the current regret upper bound. Essentially, this term results from the inaccuracy of the variance estimators. It is still an open problem if we can achieve optimal regret for linear MDPs even when $K$ is relatively small. To tackle this issue, we may consider (1) more accurate estimation of the variance term $\\sigma_{k, h}$ (e.g. [3] for linear mixture MDPs) or (2) variance-aware confidence set which does not require additional knowledge of the value of variance [4, 5, 6].\n\n- For the switching cost, our lower bound also holds when $K$ is small. For example, if $K = o(\\dim(\\mathcal{F}) H)$, our lower bound can be interpret as 'to achieve sublinear regret, the switching cost should be $\\Omega(\\dim(\\mathcal{F}) H)$'. Since such a high switching cost is not achievable, our lower bound result implicitly implies that sublinear worst-case regret is not possible when $K = o(\\dim(\\mathcal{F}) H)$.\n\n---\n[1] A Agarwal, Y Jin, and T Zhang. \"VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation.\" The Thirty-Sixth Annual Conference on Learning Theory. PMLR, 2023.\n\n[2] D Kong, R Salakhutdinov, R Wang, L Yang. \"Online sub-sampling for reinforcement learning with general function approximation\"\n\n[3] D Zhou, Q Gu. \"Computationally efficient horizon-free reinforcement learning for linear mixture mdps.\"\nAdvances in neural information processing systems, 2022\n\n[4] Z Zhang, J Yang, X Ji, SS Du. \"Improved variance-aware confidence sets for linear bandits and linear mixture mdp.\"\nAdvances in Neural Information Processing Systems, 2021\n\n[5] H Zhao, J He, D Zhou, T Zhang, Q Gu. \"Variance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency.\" The Thirty Sixth Annual Conference on Learning Theory, 2023\n\n[6] Z Zhang, JD Lee, Y Chen, SS Du. \"Horizon-Free Regret for Linear Markov Decision Processes.\" ICLR 2024", "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": "wlIEalbNa4", "reviewer": "Reviewer_Zbvr", "summary": "This paper studies the reinforcement learning under general function approximation. This paper attempts to find an algorithm which achieves optimal regret and maintains low switching cost in the mean time. \n\nIn the algorithm, first they calculated the empirical value function using the weighted ERM, where the weights are chosen according to the variance of the estimator. Next, they utilize optimism and pessimism over the Q-function. The algorithm only collects new samples if the existing dataset does not have enough coverage. \n\nThis paper brings in the technique of constructing monotonic value function (originally from He et al. (2022)) into the cases of general function approximation. \n\nThis paper achieves the optimal rate (matching the lower bound) in both the regret and also the number of switches.", "questions": "I have the following questions:\n\n1. Regarding the completeness assumption, I am curious is there a lower bound showing that the normal completeness assumption $T_h F_{h+1}\\subset F_h$ is not enough?\n\n2. In the algorithm, calculating $D_F$ requires solving an optimization problem over $(f_1, f_2)\\in F$, which is not computational tractable due to the non-convexity of the function. Is there any way to bypass this?", "limitations": "Yes. The authors addressed all the limitations listed in the guidelines.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper studies MDP with general function approximation, which is more general than the common linear MDP and tabular MDP setting. \n\nAssumptions made in this paper include the completeness and finite Eluder dimension, which are common in related literatures as well.\n\nFrom the regret and switching cost perspective, this paper matches the optimal rate for both of the terms. This paper seems to be the first paper which achives this goal.\n\nCompared to Agarwal el al. (2022), the algorithm and analysis are similar to theirs, but this paper has the following advantages:\n(1) The policies output by this paper is Markovian, while Agarwal el al. (2022) has non-Markov policies.\n(2) The switching cost is better than Agarwal el al. (2022) by a factor of d_elu.", "weaknesses": "The assumptions made on completeness and eluder dimension are somehow stronger than the usual assumptions in related literatures. Specifically, the completeness assumption requires closeness after executing Bellman operator for any value function, and the Eluder dimension requires additional parameter $\\sigma$. This completeness assumption is difficult to check unless under strong assumption over dynamics, e.g. linear structure or linear mixture MDPs, etc.\n\nCompared to the related work Agarwal el al. (2022), the techniques does not have significant improvement. The algorithm idea is very similar to the algorithm in Agarwal el al. (2022). Specifically, the technique of calculating the variance and monotonicity of value functions are both used in Agarwal el al. (2022).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer Zbvr\n\nThank you for your positive feedback! We address your questions point-by-point.\n\n---\n**Q1** The assumptions made on completeness and eluder dimension are somehow stronger than the usual assumptions in related literatures. Is there a lower bound showing that the normal completeness assumption $\\mathcal{T}\\_h \\mathcal{F}\\_{h + 1} \\subseteq \\mathcal{F}\\_h$ is not enough?\n\n**A1**  To our knowledge, there is no lower bound proving that the normal completeness assumption$\\mathcal{T}\\_h \\mathcal{F}\\_{h + 1} \\subseteq \\mathcal{F}_h$ is insufficient for achieving a minimax optimal regret bound. However, all existing works that achieve minimax optimal regret for linear MDPs or MDPs with general function approximation require estimating the variance of the next-state expected return. This necessitates a slightly stronger completeness assumption of the second-order moment. Additionally, while GOLF [1] only requires the standard completeness assumption, both in [2] and our work, a series of optimistic value functions are computed for a tractable planning phase. This requires including the optimistic/pessimistic value functions in the function classes, making the normal completeness assumption on $\\mathcal{F_h}$ insufficient from an algorithmic perspective.\n\n---\n**Q2** In the algorithm, calculating $D_{\\mathcal{F}}$ requires solving an optimization problem over $f_1, f_2 \\in \\mathcal{F}$, which is not computational tractable due to the non-convexity of the function. Is there any way to bypass this?\n\n**A2** Thanks for your insightful question! Here we do not require the functions are convex. However, when the function class $\\mathcal{F}$ is convex, [2, 3] have showed that using a binary-search based algorithm such sup over $f_1$ and $f_2$ in the bonus oracle can be efficiently and accurately evaluated. Empirically, [4] approximated the uncertainty by computing the standard deviation of an ensemble of networks and showed experimental results supporting the effectiveness of using such an uncertainty weighting technique in offline RL.\n\n---\n[1] C Jin, Q Liu, S Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances in neural information processing systems, 2021\n\n[2] D Kong, R Salakhutdinov, R Wang, LF Yang. Online sub-sampling for reinforcement learning with general function approximation.- arXiv preprint arXiv:2106.07203, 2021\n\n[3] Q Di, H Zhao, J He, Q Gu. Pessimistic nonlinear least-squares value iteration for offline reinforcement learning. ICLR 2024\n\n[4] C Ye, R Yang, Q Gu, T Zhang. Corruption-robust offline reinforcement learning with general function approximation. Advances in Neural Information Processing Systems, 2024", "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": "mGiHvCbvit", "reviewer": "Reviewer_ZRKX", "summary": "This paper considers reinforcement learning with low switching cost. The authors design a new algorithm named MQL-UCB for RL with general function approximation. The key algorithmic design includes a general deterministic policy-switching strategy that achieves low switching cost, a monotonic value function structure with carefully controlled function class complexity, and a variance-weighted regression scheme that exploits historical trajectories with high data efficiency. MQL-UCB achieves minimax optimal regret and a near optimal switching cost.", "questions": "See the weakness above.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The problem of reinforcement learning with low switching cost and general function approximation is interesting.\n2. The paper is solid.  The proof looks correct to me. \n3. The bounds are strong. The switching cost bound is optimal according to the lower bound.\n4. The presentation is clear in general.", "weaknesses": "1. Some of the assumptions look very strong.  The completeness of all functions $V:\\mathcal{S}\\rightarrow [0,1]$ , the second-order completeness and the existence of bonus oracle are not standard to my knowledge. It seems that the weighted regression is possible only if these assumptions hold.\n\n2. The paper [1] also studies low switching reinforcement learning with general function approximation. It seems that the setting in [1] is slightly more general (please correct me if there is misunderstanding) and their algorithm is cleaner.\n\n[1] Xiong et al. A general framework for sequential decision-making under adaptivity constraints.\n\n3. The algorithm itself is very complicated and whether it can be implemented in practice is unclear. Since low switching RL is a very practical problem, some experiments (even under the simplified linear MDP) to show the performance of the algorithm will be helpful. I am curious about how this algorithm performs compared to the standard approach: LSVI-UCB with a doubling trick under linear MDP.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer ZRKX\n\nThank you for your insightful comments and suggestions! We answer your questions as follows.\n\n---\n**Q1** Some of the assumptions look very strong. The completeness of all functions $V: \\mathcal{S} \\to [0, 1]$, the second-order completeness and the existence of bonus oracle are not standard to my knowledge. It seems that the weighted regression is possible only if these assumptions hold.\n\n**A1** The completeness assumption on the second moment, introduced by [1], is crucial for achieving tighter regret bounds in reinforcement learning (RL) with general function approximation. This assumption involves leveraging the variance of the value function at the next state, which is essential for obtaining minimax-optimal regret bounds in various RL settings. These settings range from tabular Markov Decision Processes (MDPs), as shown by [2], to more complex scenarios like linear mixture MDPs, as demonstrated by [3], and linear MDPs, as discussed by [4]. Given that the only previous work [1] to achieve the optimal regret bound also relies on this assumption, we believe it does not lessen the importance of our contribution. Additionally, while GOLF [9] only requires the standard completeness assumption, both in [1] and our work, a series of optimistic value functions are computed for a tractable planning phase. This requires including the optimistic/pessimistic value functions in the function classes, making the normal completeness assumption on $\\mathcal{F_h}$ insufficient from an algorithmic perspective.\n\nAs for the bonus oracle, when the function class $\\mathcal{F}$ is convex, [6, 7] has shown that using a binary-search based algorithm such sup over $f_1$ and $f_2$ in the bonus oracle can be efficiently and accurately evaluated. Empirically, [8] approximated uncertainty by computing the standard deviation of an ensemble of networks and showed experimental results supporting the effectiveness of using such an uncertainty weighting technique in offline RL.\n\n---\n**Q2** The paper [5] also studies low switching reinforcement learning with general function approximation. It seems that the setting in [5] is slightly more general (please correct me if there is misunderstanding) and their algorithm is cleaner.\n\n**A2** Both their setting and ours encompass MDPs with bounded eluder dimensions as special cases. Upon closer examination, [5] proves to be slightly more general because, in our Definition 2.4, the dimension is equivalent to (3.2) in [5] after taking the supremum of each term. Compared to [5], our approach is oracle efficient, assuming an oracle is available to compute the bonus for UCB-based exploration. As discussed in Section 1, [5] addresses low-switching RL with general function approximation, achieving a switching cost of the same order. However, the algorithm in [5] features an intractable planning phase and is not statistically optimal. Additionally, checking the policy-switching in [5] requires recomputing the cumulative loss functions at every episode, which becomes inefficient when $K$ is large.\n\n**Q3** The algorithm itself is very complicated and whether it can be implemented in practice is unclear. Since low switching RL is a very practical problem, some experiments (even under the simplified linear MDP) to show the performance of the algorithm will be helpful. I am curious about how this algorithm performs compared to the standard approach: LSVI-UCB with a doubling trick under linear MDP.\n\n**A3** Since our algorithm provides a general framework for solving MDPs with general function classes, the computational complexity of our method highly relies on the efficiency of the regression subroutine and bonus oracle implementation. Actually, our proposed algorithm reduces to LSVI-UCB++ in the linear MDP case, which is a computationally efficient algorithm that shares the same computational complexity as LSVI-UCB with a doubling trick. Additionally, we want to clarify that it is a desirable property for an RL algorithm designed for general function classes to resemble a more efficient algorithm designed for simpler settings.\n\n---\n[1]  A Agarwal, Y Jin, T Zhang. VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation. The Thirty Sixth Annual Conference on Learning Theory, 2023\n\n[2] MG Azar, I Osband, R Munos. Minimax regret bounds for reinforcement learning. International conference on machine learning, 2017\n\n[3] D Zhou, Q Gu, C Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. Conference on Learning Theory, 2021\n\n[4] J He, H Zhao, D Zhou, Q Gu. Nearly minimax optimal reinforcement learning for linear markov decision processes. International Conference on Machine Learning, 2023\n\n[5] Xiong, N., Yang, Z., and Wang, Z. A general framework for sequential decision-making under adaptivity constraints.\n\n[6] D Kong, R Salakhutdinov, R Wang, LF Yang. Online sub-sampling for reinforcement learning with general function approximation.- arXiv preprint arXiv:2106.07203, 2021\n\n[7] Q Di, H Zhao, J He, Q Gu. Pessimistic nonlinear least-squares value iteration for offline reinforcement learning. ICLR 2024\n\n[8] C Ye, R Yang, Q Gu, T Zhang. Corruption-robust offline reinforcement learning with general function approximation. Advances in Neural Information Processing Systems, 2024\n\n[9] C Jin, Q Liu, S Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances in neural information processing systems, 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:

Meta-review: I recommend acceptance for this paper. There is a general consensus among the reviewers that the contribution is technically sound and it advances the theoretical state-of-the-art in online reinforcement learning. The authors clarified in the rebuttal the assumptions made and their relationship with prior work. Similarly, the authors addressed the concerns related to the "practicality" of the algorithm. While theoretical algorithms need to rely on "black-box" optimization routines, the overall structure of the algorithm seems rather simple and its different elements are well justified in terms of their theoretical impact. 

As the authors work on a camera ready version of the paper, I strongly encourage them to borrow part of the discussion into the paper, notably 
* Elaborate more on the assumptions, their connection with existing literature, and which parts of the theory they enable.
* Expand the comparison with related works, in particular similarity and novelty of the algorithmic and technical components.
Decision: Accept (poster)