Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation
Authors: Jiafan He
Dongruo Zhou
Quanquan Gu
Venue: NeurIPS 2021 Poster (2021)
Keywords: reinforcement learning
linear function approximation
probably approximately correct

Abstract: We study reinforcement learning (RL) with linear function approximation. Existing algorithms for this problem only have high-probability regret and/or Probably Approximately Correct (PAC) sample complexity guarantees, which cannot guarantee the convergence to the optimal policy. In this paper, in order to overcome the limitation of existing algorithms, we propose a new algorithm called FLUTE, which enjoys uniform-PAC convergence to the optimal policy with high probability. The uniform-PAC guarantee is the strongest possible guarantee for reinforcement learning in the literature, which can directly imply both PAC and high probability regret bounds, making our algorithm superior to all existing algorithms with linear function approximation. At the core of our algorithm is a novel minimax value function estimator and a multi-level partition scheme to select the training samples from historical observations. Both of these techniques are new and of independent interest. 

Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation
Jiafan He
Dongruo Zhou
Department of Computer Science University of California, Los Angeles CA 90095, USA jiafaane19@ucla.cco
Department of Computer Science University of California, Los Angeles CA 90095, USA drzhou@cs ucla.edu edu
Quanquan Gu
Department of Computer Science University of California, Los Angeles CA 90095, USA qguêcs ucla. edu
Abstract
We study reinforcement learning (RL) with linear function approximation. Existing algorithms for this problem only have high-probability regret and/or Probably Approximately Correct (PAC) sample complexity guarantees, which cannot guar- antee the convergence to the optimal policy. In this paper, in order to overcome the limitation of existing algorithms, we propose a new algorithm called FLUTE, which enjoys uniform-PA -AC convergence to the optimal policy with high probability. The uniform- PAC guarantee is the strongest possible guarantee for reinforcement learning in the literature, which regret bounds, making our algorithm superior to all existing algorithms with linear function approximation. At the core of our algorithm is novel minimax value function estimator and a multi-level partition scheme to select the training samples from historical observations. Both of these techniques are new and of independent interest.
directly imply both PAC and high probability
Introduction
Designing efficient reinforcement learning (RL) algorithms for environments with large state and action spaces is one of the main tasks in the RL community. To achieve this goal, function ap- proximation, which uses class of predefined functions to approximate either the value function or transition dynamic, has been widely studied recent years. Specifically, a series recent works [11, 13, 18, 24, 3, 27] have studied RL with linear function approximation with provable guarantees. They show that with linear function approximation, one can either obtain sublinear regret bound against the optimal value function [13, 24. 3, 27] polynomial sample complexity bound [14] (Probably Approximately Correct (PAC) bound for short) in finding a near-optimal policy [11, 18).
However, neither the regret bound or PAC bound is perfect performance measure. As discussed in detail by [7], these two measures fail to guarantee the convergence to the optimal policy. Therefore, an algorithm with high probability regret and/or PAC bound guarantees do not necessarily learn the optimal policy, and can perform badly practice. detail, one can face the following two situations:
An algorithm with a sublinear regret suggests that the summation of the suboptimality gaps A. (the gap between the values of the current adapted policy and optimal policy, see Definition 3.3
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

for details.) in the first T rounds is bounded by o(T). However, this algorithm may be arbitrarily suboptimal infinitely times! thus fails to converge the optimal policy.
An algorithm is (e, 6)- suggests that with probability least 1 1- ô, the number of suboptimality gaps Ar that are greater than e will be at most polynomial in and log( 1/)). The formal definition of (e, -PAA can be found in Definition 3.4. However, this algorithm may still have gaps satisfying e/2 < A < E infinitely often, thus fails to converge to the optimal policy.
To overcome the limitations of regret and PAC guarantees, Dann al. [7] proposed a new performance measure called uniform-PAC, which is a strengthened notion of the PAC framework. Specifically, an algorithm is uniform-PAC if there exists a function of the target accuracy 6 and the confidence parameter o that upper bounds the number of suboptimality gaps satisfying A, >> sinultaneously for all é > with probability at least Definition 3.6. Algorithms that are uniform-PAC converge an optimal policy with high probability, and yield both PAC and high probability regret bounds. In addition, they proposed a UBEV algorithm for learning tabular MDPs, which is uniform-PAS Nevertheless, UBEV is designed for tabular MDPs, and it is not clear how to incorporate function approximation into UBEV to scale it up for large (or even infinite) state and action space. Therefore, a natural question arises:
The formal definition of uniform- -PAC can be found in
Can we design a provable efficient uniform-PAA PAC RL algorithm with linear function approximation?
In this work, we answer this question affirmatively. In detail, we propose new algorithms for both contextual linear bandits and linear Markov decision processes (MDPs) [22, 13]. Both of them are uniform-PAS -PCC, and their sample complexity is comparable to that of the sate-of-the-arr algorithms which are not uniform-Par PAC. Our key contributions are highlighted as follows.
We begin with contextual linear bandits problem as a "warm-up" example of the RL with linear function approximation (with horizon length equals 1). We propose a new algorithm called uniform- PAC OFUL (UPAC-OFUL), and show that our algorithm is uniform-PAC with O(d²/ /c²) sample complexity, where is the dimension of contexts and c the accuracy parameter. In addition, this result also implies an ((dyT) regret in the first T round and matches the result of OFUL algorithm [1] up logarithmic factor. The key idea of our algorithm is novel minimax linear predictor and a multi-level partition scheme to select the training samples from past observations. To the best of our knowledge, this is the first algorithm with a uniform PAC-bound for contextual bandits problems.
We also consider RL with linear function approximation in episodic linear MDPs, where the transition kernel admits a low-rank factorization. We propose algorithm dubbed uniForm-PAC Least-sqUare value iTEration (FLUTE), which adapts the novel techniques we developed in the contextual linear bandits setting, and show that our algorithm is uniform-PAC with (dd /2) sample complexity, where d is the dimension of the feature mapping. H is the length of episodes and is the accuracy parameter. This result further implies an ((v H+)) regret in the first T steps and matches the result of LSVI-UCB algorithm [13] up to a / H factor, while LSVI-UCB is not uniform-PAC. Again, FLUTE is the first PPC RL algorithm with linear function approximation.
Notation We use lower case letters to denote scalars, and use lower and upper case bold face letters to denote vectors and matrices respectively. For any positive integer n, we denote by [n] the set {I....,n.) For a vector x E Red we denote by [|x[[] the Manhattan norm and denote by ||x |2 the Euclidean norm. For a vector x E Rd and matrix Σ E Rdxd we define ||x|| = Vx Σx. For two sequences } and {6n]. we write a, O(b,) if there exists an absolute constant C' such that an 5 Cbn, We use Ō(:) to further hide the logarithmic factors. For logarithmic regret, we use Ō(-) to hide all logarithmic terms except To
SSpposs the suboptimality gaps satisfy A. 1 12,= I.... }. then the regret in the first T rounds upper bounded by O(VT), and the constant 1-gap will appear intinitely often

---

2 Related Work
2.1 Linear bandits
There is a series of works focusing on the stochastic linear bandits problem. These works can be categorized into two groups: the works aim providing sublinear regret guarantee and the works providing PAC bound for linear best-arm identification problem. In detail, for finite action set with K
arms, Auer [2] proposed SupLinRel algorithm which achieves an O( dT log" (TK)) regret, where K is the number of arms. Chu et al. [5] proposed SupLinUCB algorithm which has the same regret bound as SupLinRel, but is casier to implement. Li et al. [17] proposed a
-onfidence-Levee (VCL)) Su...inUCB algorithm and improved the regret bound to D(VaTTlo log 7 log K). For infinite action set, Dani et al. [6] proposed a Confidence Ball algorithm with an and proved an ((dvT) lower bound. Abbasi- Abbasi-Yadkori et al. [1] proposed OFUL algorithm and improved the regret bound to Odd T). When the reward has bounded variance, Zhou et al. [27], Zhang et al. [25] proposed algorithms with variance-aware confident sets, and obtained tight variance-dependent regret bounds. For the best-arm identification problem, to find arm which is c-suboptimal, Soare et al. [19] proposed a G-allocation strategy with an Ö(d/²²) sample complexity. Karmin [15] proposed an Explore- Verify framework which improves the sample complexity by some logarithmic factors. Xu et al. [21] proposed a LinGapE algorithm whose sample complexity matches the lower bound up to some K factors. Tao et al. [20] proposed an ALBA algorithm which improves the sample complexity to have a linear dimension dependence. Fiez et al. [8] studied transductive linear bandits and proposed algorithm with sample complexity similar to linear bandits. Compared with best-arm identification, the contextual bandits setting we focus on is more challenging since the action set will change at each round.
T) regret
2.2 RL with linear function approximation
Recently, line of work focuses on analyzing RL with linear function approximation. To mention a few, Jiang et al. [11] studied MDPs with low Bellman rank and proposed an OLIVE algorithm, which has the PAC guarantee. Yang and Wang [22] studied the linear transition model and proposed a sample-optimal Q-learning method with generative model. Jin et al. [13] studied the linear MDP model and proposed an LSVI-UCB algorithm under the online RL setting (without a generative model) with Ō(V HH)) regret. Later, Zanette and Brunskill [23] studied the low inherent Bellman error model and proposed an ELEANOR algorithm with a better regret V(HH using a global planning oracle. Modi al. [18] studied the linearly combined model ensemble and proposed a provable sample-efficient algorithm. Jia et al. [10], Ayoub et al. [3] studied the linear mixture MDPs and proposed a UCRL-VTR algorithm with an O(dv H²T) regret. Recently Zhou et al. [27] improved the regret bound to Ö(dH with new algorithm design and new Bernstein inequality. However, all of these works aim at deriving PAC sample complexity guarantee or regret bound, and none of them has the uniform PAC guarantee for learning MDPs with linear function approximation. Our work will fill this gap in the linear MDP setting [22, 13].
3 Preliminaries
We consider episodic Markov Decision Processes (MDPs) in this work. Each episodic MDP is denoted by a tuple (SS H, H (Pr, ( ( ). Here, is the state space, A is the finite action space, H is the length of each episode, Th S x A + [0. 1] is the reward function at stage h and PA (8'1s, a) is the transition probability function at stage which denotes the probability for state s to transfer to state s' with action a at stage h. A policy π S x [H] + A is function which maps a state s and the stage number h to an action a. For any policy æ and stage h E [H], we define the action-value function (7, a) and value function V (s) as follows
(T(s,a) r + E
Σ
Th (SH, T(w, shh s, an =a Vi((s) (T(ss
W==
where 8h++1 (- an:). We define the optimal value function V/ and the optimal action- value function Q7 as (s)
max, Vi (s) and (7((s,) a) = max, (7, a). By definition, the
3

---

value function (s) and action-value function 2% (s. a) are bounded in [0, H]. For any function V V S - R. we denote [PA, (s, a) E- V(s'). Therefore, for each stage h E [H] and policy we have the following Bellman equation, as well as the Bellman optimality equation:
Q% (s. a) (s, + [P (it,ls(s a), (s, (s, a) + [ a),
(3.1)
where VØ-1 カイ 0. At the beginning of the episode k. the agent determines a policy to be followed in this episode. At each stage h E [#]. the agent observes the state si. chooses an action following the policy тą and observes the next state with s ~ P- of.)
We consider linear function approximation in this work. Therefore, we make the following linear MDP assumption, which is firstly proposed in [22, 13].
Assumption 3.1. MDP M(S, A. H, fra ) (TA ) is a linear MDP such that for any stage [H], there exists an unknown vector P4, an unknown measure 0%(.) S + R and a known feature mapping S A Rdd, such that for each (s,a) E S x A and 8' E,
Pa s a) (d((s, a), On( ra(s, ( a), un).
For simplicity, assume that μ4, (-) and ( satisfy (|@(s, a)ll I 1 for all s, a, llaalla I va and ||0(()]|| I Vd. The linear MDP assumption automatically suggests that for any policy n, the action-valus function Q% is always a linear function of the given feature mapping Ø, which is summarized in the following proposition.
Proposition 3.2 (Proposition 2.3, [13]. For any policy æ, there exist weights (w such that for any 8, a,
A x [M], Q7 (x, a) = (Ø(8, a), wT)-
Next we define the regret and (e, 8AC formally.
Definition 3.3. For an RL algorithm Alg. we define its regret on learning an MDP in the first K episodes the sum of the suboptimality for episode k = 1...., K,
Regret( K)
(+( VT*
k=1
where Ty is the policy in the k-th episode.
Definition 3.4. For an RL algorithm Alg and fixed e, let म1, .., be the policies generated by ) > <} be the number of episodes whose suboptimality gap is greater than e. Then we say Alg is (e, 8PC with sample complexity f(e, 6) if
Alg. Let N, = =>= I
(V - V (sf)
P(N. > f(c, S 6.
Remark 3.5. Dann et al. [7] suggested that algorithm with sublinear regret is not necessarily to be an 6AAC algorithm. However, with some modification, Jin et al. [12] showed that any algorithm with sublinear regret can be converted to new algorithm which is (c. 8)-PAC, which does not contradict with the claim by [7]. For example, Ghavamzadeh et al. [9] and Zhang et al. [26] proposed algorithms with Ō (AHT) regret, and both algorithms can be converted into new algorithms which are (e, 6PC with sample complexity Ö(SAH?/e2
Both regret and PAC guarantees are not perfect. As Dann et al. [7] showed, an algorithm with sub-linear regret or (6, PAC bound may fail to converge to the optimal policy. For an (6, PAAC algorithm with A, = e/2(t E N). it still has linear regret O(eT') and will never converge to the optimal policy. For algorithm with sub-lineat regret bound, constant sub sub-optimality gap may still occur infinite times. Therefore, Dann et al. [7] proposed uniform- algorithms, which are defined formally as follows.
Definition 3.6. For an RL algorithm Alg, let πı, ...... be the policies generated by Alg. Let N. Σ 11 [1V (sf) VT (st) > <} be the number of episodes whose suboptimality gap is greater than We say Alg is uniform-PAC for some 5 E (0, with sample complexity f(c, d) if
P(Je 0, N f(e 8)) < 8.
The following theorem suggests that a uniform-PAr -PC algorithm is automatically PAC algorithm and an algorithm with sublinear regret.

---

Algorithm Uniform-PAC OFUL (UPAC-OFUL)
Require: Regularization parameter A, confidence radius Br N)
1: Set C² +- 0,1 N and the total level S1
2: for round & = 2, do
3: for all level E [S&] do
4: Set 2 AI Eieci X
5: Set bj. Eieci X,r; and w/ = -2
6: end for
7: Receive the action set D
8: Choose action X3 argmaXxED, minisis3, (wk) (wk) x B x
9: Set level 14 =
10: while / x (2
-xx - 2- and 15 S S₃ do
11:
LA 4 4 +1
end while
13: Add the new element i to the set C² and receive the reward
Set the total level Sk+1 as Sk-1 max
15: end for
Theorem 3.7 (Theorem 3, [7]). If an algorithm Alg is uniform-PAC for some 5 2 0, with sample
complexity O(C1/c+ C2/e²), where C1, C2 are constant and depend only S, A, H, (og(1/6)) Then, we have the following results:
1: Alg will converge to optimal policies with high probability at least 1 --: P [iim-++00 (1*(s
(++ 0) 2 8
With probability least for each K N, the regret for Alg in the first K episodes is upper bounded by Ö(VCkK C1 + C2).
3: For each 2 0, Alg is also (c,6)-PAC with the same sample complexity Ö C2/e)-
Theorem 3.7 suggests that uniform-PAC' is stronger than both the PAC and regret guarantees. In the remainder of this paper, aim at developing uniform-PAC RL algorithms with linear function approximation.
Warm up: Uniform-PAC Bounds for Linear Bandits
To better illustrate the idea of our algorithm, in this section, we consider a contextual linear bandits
problem, which can be regarded as a special linear MDP with H = 1. Let {Dx J be a fixed sequence of decision/action sets. At round k. the agent selects an action X E Di by the algorithm H and then observes the reward гж- (n²", Xx) + <g, where μ1" E IRd is vector unknown to the agent and eg sub-uuusee nab-Gaussian random noise. Xt. Ck. fr* satisfy the following properties:
Vk: E N, R. B[edc [x1, [ exp(X2/22 (22)) ||x S 1, "ll 1.
(4.1)
Our goal is to design (e, (-n--))nonor-P-ee algorithm with sample complexity [(e, d) such that
P BE> O, Σ 1 2
== max (n" x) (1t" Xb) > c > f(c.0) 6,
XED
k=1
where A = maXxED, (4L", x) (41", xx) denotes the suboptimality at round k.
Here assume the weight vector 4e satisfies || || < 1. be consistent with the assumption made in Abbasi- Yadkori et al. [1]. Our assumption can be easily relaxed to the general | S B case with additional log factor in the sample complexity,
be seen in the following analysis.
Why existing algorithms fail to be uniform-PAC? Before proposing our algorithm, is natural to ask whether existing methods have already been uniform-Par PAC. We take OFUL [1] for example,
5

---

which is the state-of of-tthe-at art linear bandit algorithm in our setting. At round k. OFUL constructs an optimistic estimation of the true linear function (4* x), by doing linear regression over all past selected actions x,, S i S k and their corresponding rewards. The optimistic estimation has closed-form as the summation of the linear regression predictor and a quadratic confidence bound
W x + + x 2g x, where Σn = AI - ;= x [16]. Following the standard analysis of OFUL in [1]. we obtain the following upper confidence bound of the suboptimality gap Au:
With probability least 5, Vk 0, A OV (lo xx Ix
(4.2)
where the log k is due to the fact that OFUL. makes use of all past &s observed actions. Since the agent can only say whether an arm is good or not based on the confidence bound of Ak. due to the existence of the log k term in (4.2), the bounds on the suboptimality gap for the "good" arms may be large (since log k grows k increases). That makes the agent fail recognize those "good" arms and instead pull the "bad" arms infinite times, which suggests that OFUL is not uniform- PAC algorithm. For other algorithms, they either need know the total round T before running the algorithm [5], or need to assume that the decision sets D3 are identical (e.g.. algorithms for best-arm identification (19]), thus none of them fits into our setting.
Key techniques of our algorithm. In order to address the aforementioned issue, we proposed UPAC-OFUL in Algorithm 1. The key idea of Algorithm is divide all the historical observed data into non-overlapping sets C², while each C¹ only includes finite past historical observed actions. This helps successfully avoid the log k term appearing in the confidence bound in [1]. Then at round k, Algorithm only constructs optimistic estimation of (J²", Xx) over the first S₃ sets C' individually, where S₂ is the number of non-empty sets C². In detail, the optimistic estimation over C¹ has the form
(w)) x Bey x (Ex)-1x,
(4.3)
where Σg is the covariance matrix for actions in set C (Line 4), and w is the estimation of u= obtained by ridge regression defined Line 5. Meanwhile, for a newly selected action X Algorithm 1 needs to decide which C¹ it should be added to. Inspired by [5], Algorithm 1 tests the Then Algorithm 1 adds x3 to the lowest possible level where the "uncertainty" is larger than a certain threshold (i.e., |xx (| > 2 '). Such selection rule guarantees two things simultancously. First, it ensures that the cardinality of each C¹ is finite, due to the fact that the summation of ||x* [x<l(E))-) can be properly bounded. Second, it also guarantees that the "uncertainty" of the reward corresponding to X₁ is still small, since by the level selection rule we have || S 2 (1-1), 1)_ Lastly, to make use of all Sy optimistic estimations, Algorithm I constructs the final predictor as the minimal value of Sy individual predictor (4.3) over C¹ (Line 8). Since each individual predictor is a valid upper bound of the true function, the minimum of them is still valid and tighter than each of them (except the smallest one), which makes it possible to provide a stronger uniform-PAC guarantee.
"uncertainty" of x5 against C², by calculating its confidence bound ||x
The following theorem shows that Algorithm 1 is indeed uniform-PAC.
Theorem 4.1. For any 8 E (0, 1). if we set À = 1 and 3:- = 6v di log (dl/o) oj for every level I E N, then there exists a constant C such that with probability at least rounds in Algorithm which have sub-optimality no less than is bounded by
8, for all e >> O, the number of
Ccf log (d/(6e)
Σ1
max (px x) (1 (x) xEDr
e2
Remark 4.2. Theorem 4.1 suggests that Algorithm 1 is uniform-PAr with sample complexity Odd log (d/(be)) According to Theorem 3.7, this new algorithm will converge to the optimal policy. Theorem 4.1 also implics an Ö(dVT) regret for infinite-arm linear bandit problem. This result matches the lower bound (Td [6] up to a logarithmic factor. Furthermore, Theorem 4.1 implies that Algorithm 1 is an (c, PPC algorithm with sample complexity O(d2/ /c²). Specifically, if we set Amin. Theorem 4.1 implies an Ō(d² a ) sample complexity to identify the best arm?, which matches the sample complexity (d log 2 in [19] when K = e(22).
2 "Sorre et al. [19] denoted by Anin the gap of the rewards between the best arm and the second-bec best arm. In this setting, the sample complexity to find the best arm is identical to the sample complexity to find an < Amin sub-optimal arm.

---

5 Uniform-PAC Bounds for Linear MDPs
In this section, we propose our new FLUTE algorithm (Algorithm 2) for learning linear MDPs, and provide its theoretical guarantee.
Intuition behind FLUTE At high level, FLUTE inherits the structure of Least-Square Value Iteration with UCB (LSVI-UCB) proposed in [13]. The Bellman optimality equation gives us the following equation:
(s, + [PA (PPalit ()) (0%
((s,a)),
(5.1)
where the second equality holds due to Proposition 3.2. (5.1) suggests that in order to learn Q7 it suffices to learn %. which can be roughly regarded as the unknown vector of linear bandits problem with actions (88, a) and rewards (s, a) V (s'), where (s, s') belongs to some set C. Since Vh+ is unknown, we use its estimation Vi++1 to replace Therefore, we can apply Algorithm to this equivalent linear bandits problem to obtain our uniform-PAC RI. algorithm FLUTE.
Details of FLUTE We now describe the details of FLUTE. For each stage h, FLUTE maintains non-overlapping index set J., each Cj contains state-actionn-eext-stttc triples (s), aj 8) Let S and Sy denote the number of non-empty sets { h at episode k for k: 2 2. Instead of maintaining only one estimated optimal value function Vg.h and action-value function QK, [13], FLUTE maintains a group of estimated value functions { ( and action-value functions 14 Jt. In detail, at stage h. given {V [V,,t+1)s, FLUTE calculates w as the minimizer of the ridge regression problem with training dataset (s), a s/++) E C2 and targets V. ( (Line 8), and defines Oh as the summation of the linear predictor (wi,,) (( a) and a quadratic confidence bonus Bt B (65 TT 1 a) (Line 9), where B1 is the confidence radius for level and E the covariance matrix for contexts set Cj Then FLUTE defines value function ViL, as the maximum of the minimal value over the first l action-value functions (Line 12). The max-min structure is similar to its counterpart for linear bandits in Algorithm 1, which provides a tighter estimation of the optimal value function and is pivotal to achieve uniform-PAC guarantee.
After constructing action-valut functions fQr, ht FLUTE executes the greedy policy induced by the minimal of action-value function Oe, over 1 S 1 1 1, where t5 Sx + 1 and 1 is the level of the set Ah-1 that we add the triple (s (,)_1, - s)) After obtaining (s% an s to decide which set C₁2 should this triple be added, FLUTTE calculates the confidence
bonus v / att (2%,,) - a and puts it into the 1-th set if the confidence bonus is large (Line 19), similar to that of Algorithm 1.
The following theorem shows that FLUTEE is uniform-PAC for learning linear MDPs.
Theorem 5.1. Under Assumption 1. there exists a positive constant C' such that for any 5 E (0, 1), if we set À = 1 and B₁ = CdHl Hl H5), then with probability at least - 8, for all > 0, we have
2
Σ
([V 1 2 O(d log (dH/
Remark 5.2. Theorem 5.1 suggests that algorithm FLUTE is uniform PAC with sample complexity H0 (dHH/(6))))/ According Theorem 3.7, FLUTE will converge to the optimal policy with high probability. Theorem 5.1 also implies an Ö(v H+) regret for linear MDPs. This result matches the regret bound σ d3 H3T) of LSVI-UCB [13] up to a / Hf-facoor. Furthermore, Theorem 5.1 also implies FLUTE is an (e, - with sample complexity O(d' which matches the (d H
OddHH3/ ((2) sample complexity of LSVI-UCB up to an H factor.
Computational complexity As shown in Jin al. [13], the time complexity of LSVI-UCB is O(HAHK)) Compared with the LSVI-UCB algorithm, Algorithm maintains noe-overlgp index sets (C.,) and computes the corresponding optimistic value function for each level f. Without further assumption on the norm of Φ6s, a), the number of different levels in the first K episodes is at
7

---

Algorithm 2 Uniform PAC Least-Square Value Iteration (FLUTE)
Require: Regualarization parameter X, confidence radius B1
1: Set Cj2 t 0, E N, h E [H] and set the total level S1 =
2: for episode k 1, 2, do
3: Set (1, a) = 0 for all state-action pair (s, a) E S x A and all level / E [Sx]
4: for stage = H, H L..., do
5: for all level E [kk] do
6:
Set E XI Eiec, Φ($), (shh)))))))))
7:
Set bk,n = Eiec, @ at) (a(( ai) + Vi ( wkin + -EE,,h "bbah
8:
(8, a) -- min { H. TT + ((s, end for
9:
10:
11:
for all level E [Sk] do V < max, minigis (s,a) end for end for
14:
Receive the initial state of and set the current level 1/ = Sy +
16:
for stage h = 1,2, H do
Take action of +- argmax, min minisistt_ 1
Set level 1 =
19:
while V ((55 a
- a s th and 1/ s 1 do
20:
th 6 1/ +1
21:
end while
Add element the set cht
22:
Receive the reward rh (s), a and the next state s s1+1
24:
end for
25: Set the total level S as Sk-1 max
end for
most K, which incurs an additional factor of K in the computational complexity in the worst case. However, if we assume the norm of (b(s, a) equals 1, then the number of levels the first K episodes is Olog K). Thus, since the computational complexity of our algorithm at each level can be bounded by that of LSVI-UCB, the computational complexity of Algorithm is (d AHK? log K) under the above assumption.
6 Proof Outline
In this section, we show the proof roadmap for Theorem 5.1, which consists of three key steps.
Step 1: Linear function approximates the optimal value function well
We first show that with high probability, for each level I, our constructed linear function (w (ss, a)) is indeed "good" estimation of the optimal action-vai value function (7,s, a). By the uniform self-normalize concentration inequality over specific function class, for any policy any level / and any state-action pair (s, a) E S x A, we have the following concentration property:
(wh,)) (ss. a) (s, (V [i++) (s,
(s, +A,
where | < Bi ((s,0) a) - Then, taking a backward induction for each stage [H] let Ω (Qh (s, (s, (s) (s), a) 8 x A, / N, [M] denote the event that the estimated value function Lk and Vh, upper bounds the optimal value function Q and Vi.. We can show that event Ω holds with high probability. (More details can be found in Lemmas C.4 and C.5)

---

Step 2: Approximation error decomposition
On the event Ω, the sub-optimality gap in round & is upper bounded by the function value gap between our estimated function Qk and the value function of our policy Tk-
(1+ - V/T (s & max min 1515
(f I 2 (s - -QT (s af),
-
From now we only focus on the function value gap for level lh Some elementary calculation gives us
2 a 2h (sh ah
s 2 -1 (sh T ((=)) - o0shhaaf at) + -littr ( Qh4 -ht
1/
+ Ph (V f- hh++1 V (sh, a - (Veh1t2 (s)
(Vli -1
Vh ( (sh+
(6.1)
As.h
Therefore, by telescoping (6.1) from stage 1 to H, we conclude that the sub-optimality gap (s*(s)) - VT (sf) is upper bounded by the summation of the bonus I and AR, The summation of the bonus Σ 1 is the dominating error term. According to the rule of level I, if & C2 at stage h [H] then 1 satisfies V a (T)T)(Z())))) ) (ss at))) S 2 (1(11),, Furthermore, the number of elements added into set Cj2, be upper bounded by lcl, S 17d1H4 (See Lemma C.I). Thus we can bound the summation of I For Σ AA,AA it is worth noting that Ag. forms martingale Azuma-Hoeffding
difference sequence, therefore by the standard Azuma Hoeffding inequality. Σ D can be bounded
by some non-innnn terms. Both of these two bounds will be used in the next step.
Step 3: From upper confidence bonus to uniform-PAC sample complexity
In Step 2 we have already bounded the sub-optimality gap by the summation of bonus terms. In this step, show how transform the gap into the final uniform-PAC. sample complexity. Instead of studying any accuracy directly, we focus on a special case where = H/2 E N), which can be easily generalized the general case. For each fixed
H //2 N), let K. denote the set |/]. On the one hand, according to the definition of set K,
K = (*f) V 2 c) and the summation of regret in episode k(k E K.) is lower bounded by me. On the other hand, according to Step the summation of sub-optimality gaps of episode le(k E K.), upper bound by
H
Iirr(tt- - VTTM]
2B
211--12
2-- 11) +
A
K.A
(6.2)
KEN
kEK h=1
REK
A=1
J1
J2
To further bound Jn we divide those episode-stage pairs (k;, E N [H] into two categories:
S = {(k: - (1% S {</(2H) and S2 { (k: h) 23 -1-00h-1-- > </(2H)) }. For the
first category Si, the summation of terms T in this category is upper bound by
ΣΣ (() E 8,,2 at 11) < k
c mc
(6.3)
2H
2
kEK
For any episode-stage pair (k, h) the second category S2, the level 14: satisfies 2 < O(dH² /c)
due to the choice of - Suppose is the maximum level that satisfies < (d(l1 /e) and for each level < I', the cardinality of set C₁2 can be upper bounded by |C|,1 S H4 Thus, the summation of terms I/. in category Sy upper bound by
ΣΣ ((k,h) 82)23 (1:-11 kERK=1
Σ
11h
11281112 (1-1)
h=

---

H V'
28 281-12-(1-1)
Σ
1 11
h=
Im1
KER
H 1'
28 12
k=
(6.4)
Back to (6.2), for the second term J2, according Azuma Hoeftding inequality, it can be controlled by Ö(H Hm). Therefore, combining (6.3), (6.4) with the bound of J2, we have
me S Vv V s mc/2 O ÖÖH
REK
and it implies that the number of episodes with a sub-optimality gap greater than is bounded by Odd 2 This completes the proof.
Conclusion and Future Work
In this work, proposed novel uniform-PAC algorithms for linear bandits and RL with linear function approximation, with the nearly state-of-the-art sample complexity. To the best of our knowledge, these are the very first results show that linear bandits and RI with linear function approximation can also achieve uniform-PAC guarantees, similar to the tabular RL setting. We leave proving their corresponding lower bounds and proposing algorithms with near-optimal uniform-PAC sample complexity as future work.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their helpful comments. Part of this work was done when JH. DZ and QG participated the Theory of Reinforcement Learning program at the Simons Institute for the Theory Computing in Fall 2020. JH. DZ and QG are partially supported by the National Science Foundation CAREER Award 1 1906169, IIS UIS-1904183 BIGDATA IIS 1855099 and AWS Machine Learning Research Award. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
References
[1] ABBASI- YADKORI, Y., PÁL, D. and SZEPESVÁR ÁRI, C. (2011). Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems.
[2] AUER, P. (2002). Using confidence bounds for exploitation-exploraiio trade-offs. Journal of Machine Learning Research 397-422.
[3] AYOUB, A., JIA, Z., SZEPESVARI, C., WANG, M. and YANG, L. F. (2020), Model-based reinforcement learning with value- targeted regression. arXiv preprint 27X11:2006.01107
[4] CESA-BIANCHI, N. and LUGOSI, G. (2006). Prediction, learning, and games. Cambridge university press.
[5] CHU, W., LI, I.., REYZIN, L. and SCHAPIRE, R. (2011). Contextual bandits with linear payoff functions. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics. JMLR Workshop and Conference Proceedings.
[6] DANI, V., HAYES, T. P. and KAKADE, S. M. (2008). Stochastic linear optimization under bandit feedback.
[7] DANN, C., LATTIMORE, T. and BRUNSKILL. E. (2017). Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems.
10

---

[8] FIEZ, T., JAIN, L., JAMIESON, K. and RATLIFF, L. (2019). Sequential experimental design for transductive linear bandits. arXiv preprint urXiv:1906.08399
[9]
GHANAAZADEI, M., KAPPEN, H., AZAR, M. and MuNos, R. (2011). Speedy q-learning. Advances in neural information processing systems 24 2411-2419.
[10] JIA, Z., YANG, L.,, SZEPESVARI, C. and WANG, M. (2020). Model-based reinforcement learning with talue-targeted regression. In Learning for Dynamics and Control. PMLR.
[11] JIANG, N., KRISHNAMURTHY, A., AGARWAL, A., LANGFORD, J. and SCHAPIRE, R. E. (2017). Contextual decision processes with low bellman rank are pac-learnable. In Proceedings of the 34th International Conference on Machine Learning-Volle Volume 70. JMLR. org.
[12] JIN, C., ALLEN-ZHU, 7.,, BUBECK, S. and JORDAN, M. I. (2018). Is q-learning provably efficient? In Advances in Neural Information Processing Systems.
[13] JIN, C., YANG, Z., WANG, Z. and JORDAN, M. I. (2019). Provably efficient reinforcement learning with linear function approximation. arXiv preprint arXiv:1907.05388.
[14] KAKADE, S. M. ET AL. (2003). On the sample complexity of reinforcement learning. Ph.D. thesis, University of London London, England.
[15] KARNIN, Z. (2016). Verification based solution for structured mab problems. In Proceedings of the 30th International Conference on Neural Information Processing Systems.
[16] LI, L., CHU, W., LANGFORD, J. and SCHAPIRE, R. E. (2010). A contextual- approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web.
[17] LI, Y., WANG, Y. and ZHOU, Y. (2019). Nearly minimax-optimat regret for linearly parameter- ized bandits. In Conference on Learning Theory. PMLR.
[18] MODI, A., JIANG, N., TEWARI, A. and SINGH, S. (2020). Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference Artificial Intelligence and Statistics. PMLR.
[19] SOARE, M., LAZARIC, A. and MUNOS, R. (2014). Best-arm identification in linear bandits. arXiv preprint 1rXiv:1409.6111
[20] TAO, C., BLANCO, S. and ZhOO, Y. (2018). Best arm identification in linear bandits with linear dimension dependency. In International Conference on Machine Learning. PMLR.
[21] XU, L., HONDA, J. and SUGIYAMA, M. (2018). A fully adaptive algorithm for pure exploration in linear bandits. International Conference on Artificial Intelligence and Statistics. PMLR.
[22] YANG, L. and WANG, M. (2019). Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning.
[23] ZANETTE, A. and BRUNSKILL, E. (2019). Tighter problen-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. arXiv preprini 1rXiv:1901.00210.
[24] ZANETTE, A., LAZARIC, A., KOCHENDERFER, M. and BRUNSKILL. E. (2020). Learning near optimal policies with low inherent bellman error. arXiv preprint P=XXi:2003.00/53
[25] ZHANG, Z., YANG, J., J1, X. and DU, S. S. (2021). Variance-aware confidence set: Variance- dependent bound for linear bandits and horizon-free bound for linear mixture mdp. arXiv preprint 2011v22101.12745
[26] ZHANG, Z., ZHOU, Y. and JI, X. (2020). Almost optimal model-free reinforcement learning via reforeence-advantage decomposition. arXiv preprint arXiv:2004.1000
[27] ZHOU, D., GU, Q. and SZEPESVARI, C. (2020). Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. arXiv preprint arXiv.2012.08507

---

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]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our work studies the uniform-PAC bounds for RL with function approximation, which a pure theoretical problem and does not have any negative social impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(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 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 (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite 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 obtained from people whose data you're you're using/curating? [N/A]
(c) Did you discuss whether the data you are 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, if 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]
12


Reviews:
[{"review_id": "rqzMXF-VDL8", "reviewer": "Reviewer_Bmer", "summary": "This paper designs an algorithm with uniform-PAC for reinforcement learning with linear function approximation. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is the first uniform-PAC algorithm for RL beyond tabular setting. This paper also proves sample complexity on the same order of that of algorithms which are not uniform-PAC.\n\nA major question is in Section 3, the action space $\\mathcal{A}$ is required to be finite. Is this requirement fundamental to the design of the algorithms? Can this condition be relaxed?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper focuses on theoretical analysis. It's expected that the paper does not have direct negative societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "rNiOlXVl6Dc", "reviewer": "Reviewer_4pTr", "summary": "The paper a proposes optimistic algorithm for reinforcement learning in linear MDPs and proves the first uniform-PAC bound for this setting. Unlike existing result, this stronger notion of a PAC bound ensures high-probability regret as well as convergence to the optimal policy. Along the way, the paper also provides an algorithm with uniform-PAC guarantees for the contextual linear bandit setting. The algorithms are similar to existing UCB algorithms but employ a sample-splitting technique. This technique essentially ensures the following key property for uniform-PAC results: the confidence bound for a certain state-action pair cannot increase arbitrarily with the number of episodes (as is the case with existing UCBs that typically have log(T) dependence in this setting and therefore increase with T unless an informative observation was gathered).\n", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is a solid paper with signifiant and technically interesting contributions. \n\nSignificance: Algorithms that can be run anytime and are guarantees to converge to the optimal policy are highly desirable since in practical scenarios, one is often interested in extracting a single policy eventually but does not know the number of episodes (desired accuracy level epsilon) ahead of time. Existing online-to-batch solutions (e.g. those mentioned for UCB-LSVI) that convert regret to PAC-style guarantees are based on randomly picking one of the policies executed by the algorithm but this is limited to PAC guarantees with 1/delta dependence instead of log(1/delta) and are thus too loose when the failure probability delta is small. \nThis work is the first to provide stronger guarantees that imply regret and PAC bounds simultaneously for all epsilon-levels in the function approximation setting, based on the notion of uniform-PAC that has been proposed for the tabular setting. This is an important result and the paper provides technical tools that will be of interest in extending such guarantees beyond the linear setting considered here.\n\nOriginality: Using sample splitting in bandits and RL is not new. It has been used for variance reduction in tabular RL as well as earlier algorithms (cf. MoRMax or Delayed-Q learning). However, to the best of my knowledge, the kind of splitting and analysis in this paper is novel, as well as the use to achieve uniform-PAC bounds. I expect this to be a useful tool for other settings as well.\n\nQuality: I have checked the main novel components of the analysis (e.g. Lemma A1 / B1 and A2 / B2 as well as the proof of the main theorems. Besides minor typos, I did not encounter any issues. The analysis is overall well done and presented in a sufficiently detailed and clear way.\n\nPresentation: Overall, the paper does a good job at conveying the main intuition and the details of the analysis. That said, I encourage the authors to do a careful pass on the paper for typos and to improve the writing in certain places (see detailed comments below).\n\nDetailed comments and typos:\n- Line 54: round -> rounds\n- Line 59: the RL -> RL\n- Line 59: on the -> in \n- Section 2.1: the writing is extremely monotonous and should be substantially improved. Every sentence has the exact same structure. It would also be more helpful to relate the existing works better to the contributions made in this paper. \n- Line 141: suboptimality for -> suboptimality gap for\n- Remark 3.5: I recommend mentioning that sampling a policy uniformly from the policies executed by the algorithm leads to a poly(1/delta) sample complexity result (and is therefore not considered PAC in the strict original definition) as opposed to a log(1/delta) achieved by the uniform-PAC bound presented in this submission.\n- Line 179: Why not just use general sub-Gaussian noise instead of bounding the magnitude? Also, why did the authors adopt a stronger l2 bound on the parameters for the bandit setting (1 vs sqrt(d))? This seems not necessary?\n- Sec. 5: provide a reference to Alg 2 in the text.\n- Factor H difference compared to UCB-LSVI: The additional factor of sqrt(H) in the regret bound seems to come from the bound in the number of samples per bucket. From what I understand, this is due to the fact that the level l at h can be at most the level at h-1 per episode and therefore additional elements may be added to the levels even though the first condition in line 19 of Alg 2 would hold for higher levels l. This makes the recursive bound on the gap go through nicely but I wonder whether one could avoid that and allow the levels to increase with h per episode (and thus save the additional H dependency). Did the authors explore this direction?\n- Line 278: , we -> . We\n- Line 300: pair -> pairs\n- Line 304 level satisfies -> level that satisfies\n- The paper does not discuss the computational cost of the algorithm. By the design of the levels, I think one can show that the number of level can only be logarithmic in k which is not a large additional computational burden. I recommend adding this result and a discussion.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper has adequately addressed limitations and potential negative societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "GGul1aSj3c", "reviewer": "Reviewer_FX5f", "summary": "In this paper, the authors develop a new algorithm for linear bandits that achieves a uniform-PAC bound of $\\tilde{O}(d^2/\\epsilon^2)$, meaning that for all $\\epsilon > 0$, the algorithm outputs an action whose suboptimality is at most $\\epsilon$ after $\\tilde{O}(d^2/\\epsilon^2)$ rounds of iterations. The authors further generalize their techniques to linear MDPs and develop an algorithm that achieves a uniform-PAC bound of $\\tilde{O}(d^3H^5/\\epsilon^2)$.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Uniform-PAC is a notion developed by Dann et al. [8], which says that with probability at least $1-\\delta$, for any $\\epsilon > 0$, the algorithm always outputs an $\\epsilon$-optimal policy after $f(\\epsilon, \\delta)$ rounds of iterations. It is known that such guarantee is stronger than the usual PAC guarantee and regret guarantee. In this paper, the authors develop uniform-PAC algorithms for linear bandits and RL with linear function approximation. \n\nThe main technical contribution of this paper is a new trick for developing UCB-based algorithms with uniform-PAC guarantee in the linear setting. The authors argue that existing algorithms may not satisfy the uniform-PAC guarantee either because they need to know the number of rounds of iterations in advance, or their confidence bound has a $\\log k$ factor which makes it possible for the algorithm to output suboptimal policies infinitely often. To remove the $\\log k$ factor in existing UCB-based algorithms, inspired by [6], the authors develop a clever layering method. Specifically, the authors classify all existing actions/data points into groups according to their uncertainty bonus, and each action/data point is added to a group $k$ so that the uncertainty bonus is at most $2^{-k}$. This makes sure that the size of group $k$ is at most $\\mathrm{exp}(k)$. For the analysis, instead of doing a union bound over all existing data points which will introduce a $\\log k$ factor in the confidence bound, for this new algorithm, we set the failure probably of group $k$ to be roughly $2^{-k}$. Doing so will introduce a factor of $k$ in the confidence bound of group $k$, but that will be ok for the algorithm because the uncertainty bonus is at most $2^{-k}$ for group $k$. The authors further show how to generalize the same technique to linear MDPs. \n\nOverall, the results and techniques in this paper look interesting and thus I recommend acceptance. For improvement, the authors could consider generalizing their results to generalized linear models / kernels / functions with bounded eluder dimension. For example, it seems possible to use the same technique and the algorithm in [1, 2] to achieve uniform-PAC guarantee for functions with bounded eluder dimension. Moreover, is that possible to give a hard instance so that the algorithm [3] fails to achieve uniform-PAC guarantee provably? Currently the authors only show why the analysis [3] fails to provide uniform-PAC guarantee. This still leaves the possibility that the algorithm could achieve uniform-PAC guarantee through a different analysis. \n\nMinor Comment: consider changing $(\\epsilon,\\delta)$-uniform-PAC in Line 160 to uniform-PAC, since uniform-PAC guarantee is not defined for any specific $\\epsilon$ and $\\delta$. \n\n[1] Eluder Dimension and the Sample Complexity of Optimistic Exploration\n\n[2] Provably Efficient Reinforcement Learning with General Value Function Approximation\n\n[3] Improved algorithms for linear stochastic bandits", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See main review. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers find this to be a theoretically strong paper.  I see no reason to disagree and acceptance seems warranted.  However, I feel that the technical notion of a uniform PAC bound is mainly of theoretical interest.  It not clear how much practical insight uniform bounds provide over the insights already provided by standard PAC bounds.  A poster seems appropriate.
Decision: Accept (Poster)