Reinforcement Learning with Logarithmic Regret and Policy Switches
Authors: Grigoris Velegkas
Zhuoran Yang
Amin Karbasi
Venue: NeurIPS 2022 Accept (2022)
Keywords: reinforcement learning theory
function approximation
instance-dependent regret

Abstract: In this paper, we study the problem of regret minimization for episodic Reinforcement Learning (RL) both in the model-free and the model-based setting. We focus on learning with general function classes and general model classes, and we derive results that scale with the eluder dimension of these classes. In contrast to the existing body of work that mainly establishes instance-independent regret guarantees, we focus on the instance-dependent setting and show that the regret scales logarithmically with the horizon $T$, provided that there is a gap between the best and the second best action in every state. In addition, we show that such a logarithmic regret bound is realizable by algorithms with $O(\log T)$ switching cost (also known as adaptivity complexity). In other words, these algorithms rarely switch their policy during the course of their execution. Finally, we complement our results with lower bounds which show that even in the tabular setting, we cannot hope for regret guarantees lower than $O(\log T)$.

Reinforcement Learning with Logarithmic Regret and Policy Switches
Grigoris Velegkas
Zhuoran Yang Yale University zhuoran. yan.ooaln.aaggylle.... edu
Yale University grigoris. vel.grrss.vlllggsssyllle...de
Amin Karbasi
Yale University, Google Research
amin. karbasi@yale.co edu
Abstract
In this paper, we study the problem of regret minimization for episodic Rein- forcement Learning (RL) both in the model-free and the model-based setting, We focus on learning with general function classes and general model classes, and we derive results that scale with the eluder dimension of these classes. In contrast the existing body of work that mainly establishes instance-independent regret guarantees, we focus on the instance-dependen setting and show that the regret scales logarithmically with the horizon T, provided that there is gap between the best and the second best action in every state. In addition, we show that such a logarithmic regret bound is realizable by algorithms with O T') switching cost (also known adaptivity complexiry). In other words, these algorithms rarely switch their policy during the course of their execution. Finally, we complement our results with lower bounds which show that even in the tabular setting, we cannot hope for regret guarantees lower than Ollog T)-
Introduction
The main goal of Reinforcement Learning (RL) the design and analysis of algorithms for auto- mated decision making in complex and unknown environments. The environment is modeled as a state space and the available decisions are modeled as an action space. In recent years, RL has seen tremendous success in practical applications including, but not limited to, games and robotics 1MS 16H DCH+ 16, ISSS 17, VBC+ 19). Despite this success, a theoretical understand- ing of the algorithms that are deployed in these settings remains elusive. Traditionally, theoretical RL approaches have focused on the tabular setting where the complexity of the algorithms depends on the cardinality of the aforementioned spaces [SB8.. Thus, they not suitable for applications where the state-action space is very large.
A different approach that has gained lot of attention recently is the function approximation regime where the cumulative reward of the algorithm is modeled through a function, such linear functions over some feature space. The advantage of this approach is that the algorithm can perform its search over a lower-dimensional space. There a long line of work that provides regret guarantees for RL in the function approximation setting TER14/OVRWTO YW20 [YW]2] AIS 20
CYJW20
KKL 20
ZBB 20 HZG2I KSWY2I ZHG21 CN*211
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Most of these works have focused on establishing worst-case VT guarantees, where T is the number of interactions with the enviromment. The caveat with these guarantees is that they are pessimistic since they neglect benign settings where even an exponential improvement over these bounds is achievable. To address this issue, there are some works that obtain esstace-deepedem regret bounds for RL in the tabular setting and in the linear function approximation setting [SI1 Y220, HZGHI. However, getting logarithmic regret bounds in the context of general function approximation remains open. Hence, natural question is the following:
Can we establish instance dependent logarithmic regret bounds with general function approximation?
In this paper, we provide an affirmative answer to this question. Following the assumptions in the existing literature, we model the RL problem as MDP that enjoys the property that the optimal policies are at least map better than the rest, where gap > O is a parameter that captures the hardness of the underlying problem. We focus both on the model-free and the model-basee settings with general function approximation, where we represent the value function or the transition model by a given function class, respectively.
In the model-free setting, we study the algorithm proposed in KSWY21,, which is a variant of the least-squares value iteration (LSVI) with upper confidence bound (UCB) bonuses that guide exploration. Here, the bonus functions are given by the width of a data-dependens confidence region for LSVI. For the model-based setting, value-targeted regression with UCB bonuses. On top of the logarithmic regret guarantees they enjoy, our algorithms feature lazy policy updates, in the sense that the policy is updated rarely and only when certain conditions are met. For both settings, we establish ((poly (log 7) poly(H) (H) poly(dy) 1 //gapqun)) regret guarantees, where T is the number of interactions with the environment, H is the planning horizon, dy is a term that captures the complexity of the function class F which is used to approximate either the value function or the transition model. In particular, dF involves both the eluder dimension [VRI3 and the log-covering numbers of the function classes. That is, for benign MDPs these RL algorithms achieve logarithmic regret, which is exponentially better than the
develop similar algorithm which combines
worst-case O -regret Moreover, we extend the result of [KWW2I regarding the adaptivity complexity of the algorithm. i.e. the number of different policies it uses, to the model-based and show that it logarithmic in T. We remark that in many real-world applications. like medical trials and personalized recommendation, there is a high cost and overhead associated with changing the underlying policy. Thus, coming up with algorithms that have low adaptivity complexity is an important task. To the best of our knowledge, this is the first work that establishes logarithmic instance-dependent regret guarantee for RL with general function approximation.
1.1 Related Work
Logarithmic regret bounds for bandits. There is long line of work that establishes logarithmic regret guarantees in bandit problems. Essentially, bandits are special case of RL where the transition to the next state does not depend on the action that was taken by the agent. An extensive list of such
algorithms can be found in [BCB 2
9 S20].
Logarithmic regret bounds for RL. A series of works are devoted to proving mustance-dependee logarithmic regret bounds in tabular RL. [OPTI& [S]19] prove lower bounds that show that loga- rithmic dependence on is unavoidable. Considering the upper bounds, [AO0 [B07] establish logarithmic regret guarantees in the average reward setting. Both of these guarantees are asymptotic as they require the number of interactions T with the MDP to be large enough. Regarding non- asymptotic bounds, [OA 1O] provide such an algorithm that achieves O(Da S log(T)) / /gapmii)) regret for the average-reward MDP, where 1 is the diameter of the MDP. For episodic MDPs, loga- rithmic regret upper bounds are established in SSI YYDII. The work that is probably the most closely related to ours is [HZ22]] It provides instance-dependee setting with linear function approximation. Moreover, the
logarithmic regret guarantees
both in the model-free and model- proposed algorithms update the policy in every episode. Our work generalizes these results since the linear regime is special case of the setting we are studying. Furthermore, we achieve an exponential improvement on the adaptivity complexity over their algorithms.
Bandits with limited adaptivity complexity. There is a lot of interest in obtaining bandit algorithms that update their policies rarely [AYPSII] 1RCS166 AAAK17 GHRZI9 DL7220 RYZ21]. No- tably. (DIZZZ0 study rare policy switching constraints for a broader class of online learning and decision making problems such as logit bandits.
2

---

RL with limited adaptivity complexity. Recently, there has been a lot of interest in developing RL algorithms that achieve sub-linear regret and have low adaptivity complexity [BXJWI9 ZZ]20
CK20, WZG21 KSWY2I GXDY21] We develop an algorithm with low adaptivity complexity that works in the model-based, general function approximation setting.
RL with general function approximation. As we have alluded to already, it is important to develop and analyze algorithms in the function approximation regime, So far, the most commonly studied setting is RL with linear function approximation 22 DYW120 DLMW20 WSY20 Z 2B AKKS20). Recently, there are also important results RL with general function approximation. To be specific, [ЛK** 17] design efficient algorithm whose sample complexity is bounded in terms of the Bellman rank of the function class. [JJS 20) develop an algorithm for model-based RL, whose regret bound depends on the eluder dimension of the underlying class of models. [JLM[]] propose an algorithm for problems where the underlying class has bounded Bellman eluder dimension. Recent works such as 2WSY0 Y21 FRSL X20 develop algorithms in the model-free setting whose regret scale with the eluder dimension of the functions.
Preliminaries
2.1 Notation
We use the notation [N] = (1, (1,2...., N). We also define the infinity norm of some function f: -
R, where X' is some domain, be ||/||>> supzex [f())) For dataset D { 9:) )²) C
X' x R and function f X - R. define the following norm Ilfllp (fin 1/2
((;)))) be the data-dependent norm. Given measurable set X, we denote with A (xt') the probability simplex over X. We also denote by 1[8] the indicator function of the event and by poly(x) a function that a polynomial in x.
Given set 2 [= X' we let ||ʃ||z
2.2 Episodic Markov Decision Processes
The learning agent interacts with the enviromment over sequence of K rounds which we call episodes. We model the interaction of the agent with the environment in every episode as a Markov Decision Process (MDP). We denote an MDP by M AS, r, H, s1), where S is the state space, A is the action space, P (Pr S x A- -> A(S) are the transition kernels, r = {rh- S [0, 1] are the reward fewarffunctinn functions which we assume be deterministic, is the planning horizon, which is the length of every episode, and is the initial state of every episode. We let T= H be the total number of interactions with the MDP. During every episode, the agent uses A) to take an action at a given state. We use the Q-function and V-function to evaluate the expected total reward generated by a policy æ. More specifically, we define
policy π {TH. : S -
H Σ
(ī( E
Σ Tw (ww, an)) =s as a, Vi((s) =E
(sw, an) 8, n
where the actions are picked according to π and s ~ (- ). For simplicity, we denote (Pa(- a), V) = Px, (V())) [s')]. We denote the optimal policy for a given MDP with x For the optimal Q-function, V-function we use Q7, (s, a) = QT, (s, a), Vr (s) = Vi"" (s). respectively.
The goal of the learner is to improve its performance as it interacts with the unknown environment. In the episodic setting, the agent commits to a policy at the beginning of every episode. We n denote the policy that the agent uses in the k-th episode. At each step h E [H). the agent observes the state st, chooses an action according to x² and then observes the reward r' (s% af)) and the next state + ~ Pa(- ). In this work, to measure the performance of the agent we use the notion of regret, defined as
Regret (K) Σ (s1) (sx)
The regret measures the difference between the total reward that the agent would have accumulated if she was following the optimal policy and the reward she actually accumulates. We strive for
3

---

algorithms that guarantee sub-linear regret, because, as K - 0o, the reward of the algorithm approaches that of the the optimal policy.
An assumption we make in order to achieve logarithmic regret guarantees is that the minimum sub-optimality gap is positive.
Definition 2.1. We define the sub-optimality gap of a state-action pair (s, a) at step h to be
gapa (s. a) = Vi (s) (s,
The minimum sub-optimality gap is defined to be
gap h,s,a
inf (sap, (s, a) 40}.
It is well-known that if we do not make any assumptions the best regret guarantee (VVT) [[OAT]] In this work, derive instance-dependent regret guarantees that achieve an exponential improvement on when gap > O. We remark that this assumption is not restrictive and it rules out some pathological cases. In particular, it allows to handle MDPs with multiple optimal policies. For a detailed discussion, we kindly refer the reader to Appendix A.
hope for
2.3 Model-Free Assumption
In this paper, we deal with general function classes. In the model-free setting we assume that we have access to a function class FC : A + [o, Hl + 1]}. Our goal is to use the functions in F to approximate the optimal Q-function. In order to derive meaningful results we assume that this class has some structure. We follow the same assumption as in 2W KSWY2I]
Assumption 2.2 (Bellman Operator Assumption). For any h E [H] and V S - [0, H] there exists some fv E F such that for all (s, a) E S A we have
(v(s = rx(sa)) + [)((
8'ES
The intuition behind this assumption is that if we apply the one-step Bellman backup operator to some value function V. i.e. rh (8, a) + Eves Pa(s'|s, (s'),, the result will remain in the function class. Thus, it implicitly poses some constraints both on the transition probabilities and the reward function. It is known that both the tabular setting and the linear MDP setting satisfy this assumption [YW19) [YW]2 Another assumption we make is that the function class and the state-action space have bounded covering numbers. We will show that the dependence of the regret on the covering number is logy-logari This assumption has also appeared in other works KSWY1J.
RVR13 WSY20
Assumption 2.3 (Bounded Covering Number). We say that W(F, =) is a bound on the e-covering number of F, if for any > 0 there is E-cover C(F,s) C F with size |C(F, (F,,s), so that for all f E F there is some f' E C(F,e) such that || - -''l S 6. Similarly, we say that ((S x A, e) is bound on the E-covering number of S A with respect F, if for any there is an g-cover C(S x A, C S x A with size IC(S x A, I NSS x A,E), E), so that for all (s, a) E S A there is some (s',a') C(S A,E) such that sup [f a) f(s', (,)) <..
0
The intuition behind this assumption is straightforward: even if the function class the state-action space are infinite, we can approximate them using a small number of points.
2.4 Model-Based Assumption
The assumptions in Section 2.3 are model-free since they impose some structure on the function class that approximates the Q-function instead of the transition kernel. In order derive our results, we can also follow different route and impose some structure directly on the transition kernel A
Assumption 2.4 (Known Transition Model Family). For all h E [H]. the transition model Pa belongs to family of models Pe which is known to the learner. The elements of Pr are transition kernels that map state-action pairs to signed distributions over the state space S.

---

We allow signed distributions in our model class to increase its generality, For example, this is useful when we are given access model class that can be compactly represented only when it includes non-probability kernels. For an extensive discussion about this, the reader is referred to [PST6].
Transition kernels have been used model complex stochastic controlled systems. For instance, transitions in robotics systems are often modelled using parameters of the environment, such as friction. An important class that satisfies this assumption are the linear mixture models.
Definition 2.5. The class of models P with feature mapping o(s'|s, (ss[s,,, a) S x S A + R and some 8" E R whose euclidean norm is bounded, called linear mixture model if:
. P(s'|s,0 a) = (d(-1s,a),0% 0").
For any bounded function V : + [0, H and any pair (8,a) E S A, we have (n,as)))ll: S VH, where dv (s, a) = (o(-1s, a), V).
One way to interpret the linear mixture model is as aggregation of some basis models which are known to the designer [MJTS20] Another interesting way to think about it comes from large-scale queuing networks where both the arrival rate of jobs and the processing speed for the queues unknown. If we approximate this system in discrete time, then the transition matrix from timestep t to timestep & + At approaches that of a linear function with respect to the arrival rate and the processing time GK89 Another interesting setting that satisfies this assumption is the linear-factored
MDP YW20
2.5
Complexity Measure: Eluder Dimension
Our results depend on the complexity of the function classes and the model classes that we consider. To measure this complexity. we use the eluder dimension of these classes [RVR13].
Definition 2.6. Fix some 2 and sequence of n points
{(x))ssm S X. Then:
1. A point E X' is e-dependent on Z with respect to F if for all f. Fuch that || M| S it holds that [f(x) - f'(x)] < 6.
2. A point æ is e-independent of Z with respect to F if is not e-dependent on Z.
3. The c-eluder dimension of F, which is denoted by dimg e), the length of the longest sequence of elements in X' such that every element in this sequence is &s g'-independent of its predecessors, for some 2.
Intuitively, the eluder dimension of F quantifies the smallest set of elements 2 C 2' so that if all E are close with respect Z, then they close all elements of X.
is known that when X' x A dimg(F,s) < [S|- |A|, for all 0 RVRE WSY20 Moreover, when F is the class of linear functions, i.e., fo(s, is bounded by dimg(FFe) (ss, a). for a given feauture vector o(s, a). the eluder dimension of F ((llog(1/)) for all : 0. We remark that classes which go beyond linear functions have bounded eluder dimension. Some examples are quadratic functions, generalized linear functions (e.g. sigmoids) which have the form g (((())) 2)), where g is increasing and Lipshitz- continuous with non-zero derivative, all finite function classes, sparse linear combinations of features, linear thresholds with Gaussian i.i.d. features, etc. [RVR13] OVR 14 LKFS2T] It is an ongoing line of work to understand what is the most general class of functions that has bounded eluder dimension. We refer to the setting we are working on as general function approximation align with the previous works that study function classes with bounded eluder dimension.
x A + [0, H). and S,A are finite, we have that
2.6 Switching Cost
Essentially, the switching cost the adaptivity complexity measures the number of episodes the algo- rithm has to update its policy in order to achieve the guaranteed regret bound [BXJW19 19 KSWY2II.
Definition 2.7. We define the switching cost of an algorithm A over K episodes to be
N Nywitch
1| * Tt
5

---

3 Overview of the Algorithms and Main Results
In this section, we present our main results and give high-level description of the techniques we use. We treat both the model-free and the model- setting in a unified way. The algorithm for the model-free setting comes directly from (2W We extend it appropriately model-based setting. The main algorithm is presented in Algorithm D The only differences between the two settings are the different sampling routine and Q-function estimator used by Algorithm [ In nutshell, the low-switching cost algorithm works follows:
order to handle the
After each round of the interaction with the MDP, Algorithm | adds elements to the current dataset with some probability that depends their significance and updates the policy only if the dataset has changed. This guarantees that the adaptivity of the algorithm depends logarithmically T, without hurting the regret guarantee. The sampling routines postponed to Appendix A.2
There is a least-squares estimate of the Q-function (transition kernel) in the model-free (model- setting.
A bonus is added this estimate which encourages exploration and, with high probability, guarantees that the current estimate of the Q-function serves as an sementtwise upper bound of Q' This bonus is based on sub-sampled dataset that has been accumulated from previous interactions with the MDP.
Before we delve deeper into the two settings separately, we describe a parameter that is crucial for both of the algorithms we are using. Following KSWW221), the sensitivity of an element 2 with respect dataset Z and function class F is defined to be
(fi())-f22))) f2(=))² fi.f min(1lf1 - f2 1)²
sensitivityz, min
sup
Intuitively, this parameter captures the importance of the current element relative to the dataset we are working with. We will elaborate on the choice of the parameter 3 for each of the two settings separately. To establish the regret guarantee, we propose novel regret decomposition for this algorithm where we utilize the "peeling technique" that has been applied in prior works in local Rademacher complexities (BBM05) and in RI. (HZG21 (YD21] By doing that, we show how the regret of the algorithm relates to the suboptimality gap.
To establish the lower bound the regret of any algorithm in the settings are interested in, we utilize a result that was proved in [PPTI8 (SJI). It states that for all algorithms that achieve sublinear regret, there exists tabular MDP where its regret is at least ((poly(log(T) We remark that tabular MDPs satisfy both the model-free assumption 2WS and the model-based assumption
poly(H) 1/gapmiit
thus the lower bounds follow immediately from this result.
3.1 Model-Free Setting
We first present the approach we use in the model-free setting, i.e., where we have access to some function class F and state-action space S x AA that satisfy Assumption 2.2 and Assumption 2 respectively. The algorithm we use comes from I2SW The Q-function estimator and the sampling routine that use for this setting are presented in Algorithm and Algorithm respectively.
The dataset includes pairs of the form z = (sf, )..). The Q-function routine is a least-squares estimator that is based all the previous interactions with the MDP. Notice that the bonus function is based only on the sub-sampled dataset and depends on a hardcoded parameter B3. This parameter is chosen in a way that ensures the Q-function is an optimistic estimate of the actual one and the bonus we add is not too large. The choice of / is given in KSW
A crucial part of the algorithm is the online nub-sampinng routine. The reason are using this routine is twofold. Firstly, if we use the entire dataset there will be a huge number of distinct elements in it, which can make the exploration bonus unstable since it changes constantly and can take infinitely many different values. In order to establish the optimism of the Q-fucction estimation, namely,
(s, < (s, a) < (Pr a), Vit + 2b/ (s, a),

---

ISW Y21 show that it is crucial to bound the complexity of the exploration bonus. Secondly, if we samle the dataset based on the importance of the elements, we can achieve the regret guarantees that we are aiming for by switching the policy only when an important element has been added. Notice that whenever an element added to the dataset, multiple copies are included. This is make the sub-sampled dataset behave like an unbiased estimator of the orignal one. Then, using concentration bounds one can show that it approximates the original one with high probability (KSWY2I) The full description of this procedure is presented in Algorithm 4 For more detailed discussion about the importance of sub-sampling the dataset, the interested reader is referred to WSY20 KSWY2II
Algorithm 1 Low Switching Cost Value Itera- Algorithm Q-function Model- Free Estimator tion (with parameters 6, K)
Require: Current sub-ennpel dataset 2, history
Require: Failure probability 5 E (0, 1), number of episodes K, and setting of operation
of execution T
1: D - {(8 071 1 + Vh+ h+1 (81+1))
1: k <-1
f f arg argminfes I1f11B
2: Z 0. vh [H]
3: Ft. f
{fi, f2 E F : min(llfi
3: for k E [K] do
fzl 2x
T(H + 1)2 s s
4:
for h H, H ....,, do
5:
if 2 2 then
4: b (+.) f sup, sup [/((+)) - S2(.-)
6:
2 < Sample(F, 2k-1, k ,
5: Return mmn((/((,)))) (f(.),,,
7:
end if
8:
end for
9:
if A:
1 or 3he H 7/ F 2/ then
10:
1o
++H k
Algorithm Q-function Model-Based Estima- for
11:
QH+1 (()) <- V 0 0
H+ do
12:
for h
H. H 1,
Require:
Function class F, current sub-sampled dataset 2, current regression dataset DD
13:
The history of execution
14:
Q (-.-) t Q-Estimator (T: 2%)
1: Ph arg minsePh
15:
V. A (: a)
Σ (P(+s ag Vi+1) V. h+1 (sh
16:
T (-) f arg max.eA ()(aa)
17:
end for
2: F = ffr min - fellzy. T(H
18:
end if
1)² S B}
19:
Receive initial state $1 of episode k
3: ()())
+ sup [5(( Vn+1)
20: for l E [H] do
fa(+,.Vo+1)
Take action a + R (5h)
21:
4: Return minfra(s-) + (PA(I:)) (,())),11 113
22:
end for
23:
end for
We are now ready to state our main result in this setting.
Theorem 3.1. There exists an absolute constant C' 0, and a proper parameter 3 for Algorithm i
such that with probability of at least 1 - [log _ - 8 the regret of the algorithu is bounded by
Regret () I Cd log' T 16
+
gap
for any 8, > O, where dy = (F, (F.1/T) log(N(FF 5/T log(N x A, /88 is a parameter that captures the complexity of the function class. The value of the parameter B is
B = Cd 22 log" T.
where d' (F,((( dim (f.m((F./7)) log(N x A, A,8/19)/6)) Moreover, the number
of switching policies is bounded by
( (H (og(TT((F, dime))/))mmmmmmm (7 T).
3.2 Model-Based Setting
In this regime, we assume that the MDP satisfies Assumption 2.4 We also assume that the reward function is known to the learner similar to 2A]S+ If the reward is unknown, we just estimate and construct confidence region.
7

---

Before we discuss the details of our approach, we need to describe an important set of functions that show up in our algorithm and in the regret guarantee. Let V be the set of all measurable functions that are bounded by H. Let Ph be the set of potential models in step H. We also let f x Ax - IR and define the following set:
Fn - [:
(-(1::3 :: E Pn so that [s, a, V) Pa(s'ls, ())( V(, a, V) v)
The bounds we state scale with the complexity of Fr. The Q-function estimator and the sampling routine we use that are specific to this setting are presented in Algorithm g] and Algorithm 5 respectively. The dataset includes elements of the form 2 = (s df v The Q-function
routine works in the following way. We first estimate a model P, E Ph, using a least-squares estimator that is based on all the previous interactions with the MDP. Using concentration argument for this estimator of the model, similar to [RVRT3 AJS 20 we can show that for an appropriate choice of B. the estimated model lies in a data-dependens ball centered at PR. with high probability (see Lemma C.IT the Appendix). Thus, we can set the bonus function be the diameter of this ball in order to ensure that Qn an optimistic estimate Ti. In addition, the choice of ensures that the bonus we add is not very large. Notice also that since the concentration argument in this setting differs with that the model-free setting, we do not need to round the elements that we are adding to the sub- sampled dataset. In this setting, the main reason sub-sumpp sub-sample the dataset is to achieve logarithmic adaptivity. To bound the adaptivity complexity, we use a similar approach as in (KSWY2IJ
We are now ready to state our main result in this setting.
Theorem 3.2. There exists absolute constant C and proper value of the parameter for Algorithm such that with probability at least - [log T Te- the regret of the algorithm is bounded by
Cd logT 2
Regret(K)
+
gapmin
3
where dy = log(NNFF, d The value of the parameter (3 is
B = 4H2 1og(22 + 4/H (c HHH/////oooo /HP/4log(TT8))
where ([F, 1/T) maxmε|и dim), 1/T) maxxe[M] dim (Fr, 1/T).
The number of switching policies is bounded by
(oggg[TN(F, / / di, log2 T))
We remark that the eluder dimension and the log-covering numbers, which show up in both of our bounds, depend on T. To the best of our knowledge, in all the known cases that the eluder dimension is bounded (e.g. linear functions, quadratic functions, generalized linear functions), the scaling is poly(log T) (see e.g. [VRR3))
3.3 Technical Contributions
We briefly highlight the main technical contributions of this work. Regarding algorithmic contri- butions, we extend the algorithm from (2S) which works in the model-free setting, to the model-based setting, Even though these two algorithms look similar, the approach to prove concentra- tion, optimism, and correctness the model-based setting different (see, e.g., Lemma C.12). This perspective provides unified treatment of both settings that can be beneficial and leads to new results. For instance, if we wish to get restance-indepenee decomposition, we can get -T-rreget with poly T) adaptivity complexity in the model-based setting. This is an exponential improvement in the adaptivity complexity compared to [AJS* 20). Furthermore, the analysis to get the instance-dependent guarantees of both algorithms diverges significantly from KSW since we use different regret decomposition. Logarithmic regret guarantees in the linear function approximation setting have been established in [HZG2T] However, the technical results that are needed to derive the guarantees in this setting are tailor-made to linear
regret guarantees using the standard regret
8

---

functions. Importantly, [HZG2N bound several quantities in terms of Ø(s, a) [o)][(AA) (AA)) Ó a) where á(s, a) are the features of the state-action pair (s, a) and A = - ((s), at (s{), oi) + AL. Since we are working with general functions, we need to derive bounds that scale with the eluder dimension of these classes (see, e.g. Lemma (.3))
Remark 3.3 (Computational Complexity). As it argued in IKSWY2I, the main computational bottleneck the algorithms is solving a (weighted) least squares problem over some set. Given such a procedure, one can also construct the confidence region and estimate the exploration bonus and the sensitivity. 12W shows that the computational complexity of the algorithm overall is O (poly(d log K) Importantly, if there is some structure the space and solving the least- squares problem becomes easier then the computational complexity of the algorithm drops. We underline that solving a least-squares problem an important component of most theoretical RI. algorithms that we are aware of which go beyond the tabular setting. A similar result holds in the model-based setting well.
4 Proof Sketch of Main Results
In this section, we sketch the proof of our main results. Due to space limitation, we only discuss the model-free setting. The full proofs in the model-free, model-based setting can be found in
Appendix
B Appendix C
respectively.
The first step in our analysis is the regret decomposition of the algorithm. Lemma B.J shows that
E k= En (sh, af Thus, we see that to bound the regret it is enough
E Reggret [}] = E
K to bound Σ k= gap, ( a for every E [H]. Towards this end, notice that gapn(st ax))) or gap, (s) af)) E [gap H). We apply the "peeling technique" that has also been used in local Rademacher complexities (BMO55) and in HHZG2 YYDII. The idea is to split the interval [0, H] into log( /gaa/m))n intervals, where the i-th interval is [2 gap 2' 2'gapmin] Hence, for every gap, a that falls in the i-th interval its contribution to the regret is at most 2' gagamiin. Thus, to bound the regret it suffices to bound the number of suboptimalities that fall into every interval. Notice that for some gap, (sh, af)) in this interval we have that
Vy Q% (sh, at) 2 gap, (sh. 2 2¹-1 ggammnn
so it suffices to bound the number of sub-optimalities VT - Q (st,, at) that fall into the i-th interval. Both for the model- free and the notice that once we have bounded the number of suboptimilaties in every interval, it is not difficult to bound the total regret. Let C; [ gapamii 2' map and N log(Ht gapp/aap)mm Then, we know that Regret(K) () can be upper bounded by
setting, we can derive such bound. Finally,
K
H1
N
K
gap, (sh. (N)
Σ
gap (oh
2' (sh. C.)
k=14=1
gupa (st . EC.
k=1
N
1
V
(s
Q (sh
2 2 gap min
1=1
k=1
Hence, deriving the regret guarantee boils down to bounding
K
(V
Q (s at) 2' d'ggapmmn]
We provide such bound in Lemma B.9 which depends polynomially log T, 1/gap min' and the complexity parameters of the function class. The outline of the proof is the following. We fix some episode h (H) and let K" be the of rounds where (s Q (st, at) 2 2' "gaammin To get bound on JK', our approach is to lower bound and upper bound the quan- tity >|K'| of (s
; .an ) by f(('')), f2(K')),, respectively. Then, we use the fact that ((((K')) < (')) to establish our bound. For the lower bound, using the defi- nition of K' we get f((K') 2'gapmin K'). For the upper bound, we leverage the fact that 2% (s ax
k.) .
2 (5% nh, whe
A. 1411 + 2b (5 a (cf. Lemma B.8 and obtain fa((')) <

---

EE Σ R=n EN + k'=h (055),;, where E forms bounded martingale difference sequence. We bound each term on the RHS separately. For the first one, we use the Azuma-Hoeffding Hoeffding inequality which can be found in Lemma [.. For the second term, we generalize the bound on the summation of the bonus functions over all the episodes from IKSW21]. and show that a similar bound holds for the summation of the bonus over any set of episodes K' (see Lemma B.6). Putting everything together, get that | O (1/(4"gap gapmin) H llog'" T poly(ds)), where dy is the complexity parameter of the class.
Conclusion and Societal Impact
In this paper, we consider episodic RL with general function approximation. We prove that there are algorithms with logarithmic adaptivity complexity both in the model-free and model-based settings that achieve logarithmic instance-dependent regret guarantees. This is theoretical work and does not have any negative societal implications.
Acknowledgments and Disclosure of Funding
Grigoris Velegkas is supported by NSF (IIS-18450) 1845032),, an Onassis Foundation PhD Fellowship and a Bodossaki Foundation PhD Fellowship. Amin Karbasi acknowledges funding in direct support of this work from NSF (IIS- 1845028,,,,, ONR (N00014- 19- 1-2-406), and the AI Institute for Learning-Enan -nableed Optimization at Scale (TILOS). The authors would like thank the anonymous reviewers for helpful comments and suggestions.
References
[AAAK17] Arpit Agarwal, Shivani Agarwal, Sepehr Assadi, and Sanjeev Khanna. Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons. In Conference on Learning Theory, pages 39-75. PMLR, 2017.
[AJS+20) Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pages 463-474. PMLR, 2020.
[AKKS20] Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank mdps. arXiv preprint arXiv:2006. /08/4, 2020.
[A007] Peter Auer and Ronald Ortner. Logarithmic online regret bounds for undiscounted reinforcement learning. Advances in neural information processing systems, pages 49-56, 2007.
[AYPS11] Yasin Abbasi- Yadkor, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing xystems, 24:2312-2320, 2011.
[BBM05] Peter L Bartlett, Olivier Bousquet, and Shahar Mendelson. Local rademacher complexi- ties. The Annals of Statistics, 33(4): 1497-13777 2005.
[BCB12] Sébastien Bubeck and Nicolo Cesa-Bianchi. Regret analysis of stochastic and non- stochastic multi-armed bandit problems. arXiv preprint arXiv: 1204.5721, 2012.
[BXJW19] Bai, Tengyang Xie, Nan Jiang, and Yu-Xiang Wang. Provably efficient q-learning with low switching cost. arXiv preprint arXiv: 12849, 2019.
[CBL06] Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[CK20] Tongyi Cao and Akshay Krishnamurthy. Provably adaptive reinforcement learning in metric spaces. Advances Neural Information Processing Systems, 33:9736-9744, 2020.
10

---

[CY]W20] Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimization. In International Conference on Machine Learning. pages 1283-1294. PMLR, 2020.
[DCH*1) 16] Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In International conference on machine learning, pages 1329-1338 PMLR, 2016.
[DLMW20] Simon S Du, Jason D Lee, Gaurav Mahajan, and Ruosong Wang. Agnostic q-learning with function approximation in deterministic systems: Near-optimal bounds ap- proximation error and sample complexity. Advances in Neural Information Processing Systems, 2020, 2020.
[DLZZ20] Kefan Dong, Yingkai Li, Qin Zhang, and Yuan Zhou. Multinomial logit bandit with low switching cost. In International Conference on Machine Learning, pages 2607-2615. PMLR, 2020.
[Fre75] David A Freedman. On tail probabilities for martingales. the Annals of Probubility, pages 100-118, 1975.
[FRSLX20] Dylan J Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. Instance- dependent complexity of contextual bandits and reinforcement learning: A disagreement-baade perspective. arXiv preprint arXiv:2010.03104, 2020.
[GHRZ19] Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou. Batched multi-armed bandits problem. arXiv preprint arXiv: 1904.09447.75 7633, 2019.
[GK89] Boris Vladimirovich Gnedenko and Igor Nikolaevich Kovalenko. Introduction to queueing theory. Birkhauser Boston Inc., 1989.
[GXDY21] Minbo Gao, Tianle Xie, Simon S Du, and Lin F Yang. A provably efficient algo- rithm for linear markov decision process with low switching cost. arXiv preprint arXiv:2101.00494 2021.
[HZG21] Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. International Conference on Machine Learning, pages 4171-4180. PMLR, 2021.
[IC Haque Ishfaq, Qiwen Cui, Viet Nguyen, Alex Ayoub, Zhuoran Yang, Zhaoran Wang, Doina Precup, and Lin Yang. Randomized exploration in reinforcement learning with general value function approximation. In International Conference on Machine Learning, pages 4607-4616. PMLR, 2021.
[JKА+17 17] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contextual decision processes with low bellman rank are pac-learnable. In International Conference Machine Learning, pages 1704-1713. PMLR, 2017.
[JLM21] Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. arXiv preprint arXiv:2102.00815. 2021.
[JOA10] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for rein- forcement learning. Journal of Machine Learning Research, 1 11()), 2010.
[JWJ200] Chi Jin, Zhuoran Yang, Zhaoran Wang. and Michael I Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143, PMLR, 2020.
X2] Sham Kakade, Akshay Krishnamurthy, Kendall Lowrey, Motoya Ohnishi, and Wen Sun. Information theoretic regret bounds for online nonlinear control. arXiv preprint arXiv:2006. / 2020.
[KSWY21] Dingwen Kong, Ruslan Salakhutdinov, Ruosong Wang, and Lin F Yang. Online sub-sampling for reinforcement learning with general function approximation. arXiv preprint arXiv:2106.0777 07203, 2021.

---

[LKFS21] Gene Li, Pritish Kamath, Dylan J Foster, and Nathan Srebro. Eluder dimension and generalized rank. arXiv preprint arXiv:2104.06970 2021.
[LS20] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[MJTS20] Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pages 2010-2020. PMLR, 2020.
[MKS* 15] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):529-333, 2015.
[OPT18] Jungseul Ok, Alexandre Proutiere, and Damianos Tranos. Exploration in structured reinforcement learning. arXiv preprint
2018.
[OVR14] Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. arXiv preprint arXiv: 1853, 2014.
[OVRW16] Ian Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. International Conference on Machine Learning, pages 2377-2386. PMLR, 2016.
[PRCS16] Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg. Batched bandit problems. The Annals of Statistics, 44(2):660-66 681, 2016.
[PS16] Bernardo Ávila Pires and Csaba Szepesvári. Policy error bounds for model-based reinforcement learning with factored linear models. In Conference Learning Theory, pages 121-151. PMLR, 2016.
[RVR3]] Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. In NIPS, pages 2256-2264. Citeseer, 2013.
[RYZ21] Yufei Ruan, Jiaqi Yang. and Yuan Zhou. Linear bandits with limited adaptivity and learning distributional optimal design. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pages 74-87, 2021.
[SB18] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018
[SHM* 16] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam,, Marc Lanetot, al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
[SJ19] Max Simchowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. Advances in Neural Information Processing Systems, 12:1153-1162 2019.
[Sli19] Aleksandrs Slivkins. arXiv: 2019.
Introduction to multi-armed bandits.
arXiv preprint
[SSS 17] David Silver, Julian Schritwieser,, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Master- ing the game of go without human knowledge. nature, 550(7676):354 359, 2017.
[TB07] Ambuj Tewari and Peter L Bartlett. Optimistic linear programming gives logarithmic regret for irreducible mdps. In NIPS, pages 1505-1512. Citeseer, 2007.
[VBC+19] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature 575(7782):350-354 2019.
12

---

[WSY20] Ruosong Wang. Ruslan Salakhutdinov, and Lin F Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. arXiv preprint arXiv:2005. 10804, 2020.
[WZG21] Tianhao Wang. Dongruo Zhou, and Quanquan Gu. Provably efficient reinforcement learning with linear function approximation under adaptivity constraints. arXiv preprint 101.022 2021.
[YW19] Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004. PMLR, 2019.
[YW20] Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pages 10746-10756. PMLR, 2020.
[YYD21] Kunhe Yang. Lin Yang, and Simon Du. Q-learning with logarithmic regret. In Interna- tional Conference on Artificial Intelligence and Statistics, pages 1576-1584. PMLR. 2021.
[ZBB+20] 20] Andrea Zanette. David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessan- dro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Conference on Artificial Intelligence and Statistics, pages 1954-1964.
PMLR, 2020.
[ZHG21] Dongruo Zhou, Jiafan Hc, and Quanquan Gu. Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning, pages 12793-12802. PMLR, 2021.
[ZLKB20] Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learn- ing near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pages 10978-10989, PMLR, 2020.
[ZZJ20] Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference-advantage decomposition. arXiv preprint arXi::2004.10019 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Yes, for example we have
described which function classes have bounded eluder dimension.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] In
Section 5
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We have described the assumptions under which results sorrect(Assupption
2.4 positive minimum sub-optimality gap).
(b) Did you include complete proofs of all theoretical results? [Yes] Due to space limita- tions, the full proofs are postponed to the appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
13

---

(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (c.g., code, data, models) or curating/releusing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you' re using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "tBqUvSoGmJZ", "reviewer": "Reviewer_jPGw", "summary": "The paper considers the reinforcement learning problem with \ngeneral function classes and general model classes. In a specific\nsetting with a strictly positive optimality gap, the authors show \nlogarithmic regret can be achieved (in contrast to the minimax \noptimal regret $\\sqrt{T}$). Moreover, the proposed algorithm \nonly switches policies for polylog times. The results are established\nin both the model-based and model-free settings.", "questions": "In bandit problems, the optimal number of batches/switches\nis of the order $\\log\\log{T}$. Is the number of switches $\\log{T}$ optimal\nin RL, or is it the same as in the bandit problem?\n", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. The paper is well-written, with an extensive literature review\nand a clear exposition of the proposed method; the analysis of \nthe algorithm is complemented with explanation and intuitions.\n\n2. Technically, the paper is solid to my knowledge and the extension of the method is nontrivial. \n\n3. It might help if this paper could show numerical results\nillustrating the claims made in theories.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "aUcoEQNvETq", "reviewer": "Reviewer_HxV2", "summary": "The paper studies the problem of regret minimization for episodic RL with general function approximation. Under both model-free and model-based settings, logarithmic regret and policy switch results are presented. ", "questions": "Could you elaborate on the technical improvements made in this paper over previous results? I would also suggest discuss Theorem 3.1 and Theorem 3.2 in context of previous results of log regret for RL under tabular/linear function approximations. ", "limitations": "The authors discussed this and I agree that this is a theoretical work, which has no potential societal impact. ", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros: The paper is very well written, and all the results are presented clearly. The background and the related works of this work are also discussed sufficiently. The results presented are new and important to RL as well.\n\nCons: The results are not very surprising given the prior works on RL with logarithmic regret and RL with general function approximation. The peeling techniques for regret decomposition are also used to obtain logarithmic regret for RL under linear function approximation. The other parts of the proof for the main theorem and the sub-sampling method mainly follow from results for RL under general function approximation [KSWY21]. By the property of the sub-sampled dataset, and as Lemma C.3 pointed out, logarithmic policy switching is a direct result.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Rbz6an1SaSR", "reviewer": "Reviewer_PwVr", "summary": "The paper studies the instance-dependent logarithmic regret bounds on the RL problem with general function approximation. The paper introduces the notation of “adaptivity complexity”. The paper designs two RL algorithms with general function approximation separately in model-based and model-free settings that archive the logarithmic regret bounds and logarithmic adaptivity complexity simultaneously.", "questions": "I think this paper is somewhat missing an assessment of the tractability of the proposed algorithm, especially the computational complexity of the optimization problems involved in Algorithms 2 and 3. Can the author clarify this?", "limitations": "The assumptions and limitations are stated in Section 2.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Logarithmic instance-dependent regret bounds and logarithmic switching cost has been studied in tabular RL and RL with linear function approximation. The idea is not novel, but this paper is the first work that establishes a logarithmic instance-dependent regret and logarithmic switching cost guarantee for RL with general function approximation. This is a good paper. The paper is well-written and clearly delivers the message. Related work is covered well. The paper makes strong use of the theoretical results published in a previous paper [KSWY21] but presents novel and important generalizations to model-based RL.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7zMcta8fafo", "reviewer": "Reviewer_Bt98", "summary": "Regret in the RL setting has been extensively studied for linear approximations but not for other families of functions. In addition, it is more typical to have episode specific policies which is clearly undesirable. The authors study regret for a general set of functions and with a switching cost of policies among episodes. They exhibit an algorithm with optimal regret by showing an upper bound on regret of their algorithm and a lower bound of the same order. \n\nMinor typos: line 57: to model-based \nline 129: of the optimal policy", "questions": "Theorems 3.1 and 3.2 use tau and delta. The statements hold for any non-negative values of these two parameters. It's never discussed what value should they have in order to minimize the regret bound. ", "limitations": "This being analytical work, there are no clear societal negative impacts. ", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Although this is an analytical paper, it would be great to showcase practical performance of their algorithm. \nThe introduction is slightly misleading as it doesn't mention that the regret bounds are in the probabilistic sense. \n\nThe paper has many contributions, including the algorithm and the underlying non-trivial analyses. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept