Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation

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.

heading: 1 Introduction
text: 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 approximation, which uses a class of predefined functions to approximate either the value function or transition dynamic, has been widely studied in recent years. Specifically, a series of 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 a sublinear regret bound against the optimal value function [13, 24, 3, 27] or a 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 a 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 in practice. In detail, one can face the following two situations:
• An algorithm with a sublinear regret suggests that the summation of the suboptimality gaps ∆t (the gap between the values of the current adapted policy and optimal policy, see Definition 3.3
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
for details.) in the first T rounds is bounded by o(T ). However, this algorithm may be arbitrarily suboptimal infinitely times 1, thus it fails to converge to the optimal policy.
• An algorithm is ( , δ)-PAC suggests that with probability at least 1−δ, the number of suboptimality gaps ∆t that are greater than will be at most polynomial in and log(1/δ). The formal definition of ( , δ)-PAC can be found in Definition 3.4. However, this algorithm may still have gaps satisfying /2 < ∆t < infinitely often, thus fails to converge to the optimal policy.
To overcome the limitations of regret and PAC guarantees, Dann et 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 and the confidence parameter δ that upper bounds the number of suboptimality gaps satisfying ∆t > simultaneously for all > 0 with probability at least 1− δ. The formal definition of uniform-PAC can be found in Definition 3.6. Algorithms that are uniform-PAC converge to 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-PAC. 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:
Can we design a provable efficient uniform-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-PAC, and their sample complexity is comparable to that of the state-of-the-art algorithms which are not uniform-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 uniformPAC OFUL (UPAC-OFUL), and show that our algorithm is uniform-PAC with Õ(d2/ 2) sample complexity, where d is the dimension of contexts and is the accuracy parameter. In addition, this result also implies an Õ(d √ T ) regret in the first T round and matches the result of OFUL
algorithm [1] up to a logarithmic factor. The key idea of our algorithm is a 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 an 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 Õ(d3H5/ 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 Õ( √ d3H4T ) 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 uniform-PAC 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 {1, . . . , n}. For a vector x ∈ Rd , we denote by ‖x‖1 the Manhattan norm and denote by ‖x‖2 the Euclidean norm. For a vector x ∈ Rd and matrix Σ ∈ Rd×d, we define ‖x‖Σ = √ x>Σx. For two sequences {an} and {bn}, we write an = O(bn) if there exists an absolute constant C such that an ≤ Cbn. We use Õ(·) to further hide the logarithmic factors. For logarithmic regret, we use Õ(·) to hide all logarithmic terms except log T .
1Suppose the suboptimality gaps satisfy ∆t = 1{t = i2, i = 1, . . . }, then the regret in the first T rounds is upper bounded by O( √ T ), and the constant 1-gap will appear infinitely often

heading: 2 Related Work

heading: 2.1 Linear bandits
text: There is a series of works focusing on the stochastic linear bandits problem. These works can be categorized into two groups: the works aim at 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 a SupLinRel algorithm which achieves anO( √ dT log3(TK)) regret, where
K is the number of arms. Chu et al. [5] proposed a SupLinUCB algorithm which has the same regret bound as SupLinRel, but is easier to implement. Li et al. [17] proposed a Variable-Confidence-Level (VCL) SupLinUCB algorithm and improved the regret bound to O( √ dT log T logK). For infinite
action set, Dani et al. [6] proposed a Confidence Ball algorithm with an O(d √ T log3 T ) regret and proved an Ω(d √ T ) lower bound. Abbasi-Yadkori et al. [1] proposed OFUL algorithm and
improved the regret bound to O(d √ T log2 T ). When the reward has a 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 an arm which is -suboptimal, Soare et al. [19] proposed a G-allocation strategy with an Õ(d/ 2) sample complexity. Karnin [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 an 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.

heading: 2.2 RL with linear function approximation
text: Recently, a 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 a 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 Õ( √ d3H3T ) regret. Later, Zanette and Brunskill [23] studied the low inherent Bellman error model and proposed an ELEANOR algorithm with a better regret Õ(dH √ T ) using a global planning oracle. Modi et 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̃(d √ H3T ) regret. Recently Zhou et al. [27] improved the regret bound to Õ(dH √ T ) with a new algorithm design and a 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].

heading: 3 Preliminaries
text: We consider episodic Markov Decision Processes (MDPs) in this work. Each episodic MDP is denoted by a tuple M(S,A, H, {rh}Hh=1, {Ph}Hh=1). Here, S is the state space, A is the finite action space, H is the length of each episode, rh : S × A → [0, 1] is the reward function at stage h and Ph(s′|s, a) is the transition probability function at stage h which denotes the probability for state s to transfer to state s′ with action a at stage h. A policy π : S × [H]→ A is a function which maps a state s and the stage number h to an action a. For any policy π and stage h ∈ [H], we define the action-value function Qπh(s, a) and value function V π h (s) as follows
Qπh(s, a) = rh(s, a) + E [ H∑ h′=h+1 rh′ ( sh′ , π(sh′ , h ′) )∣∣sh = s, ah = a], V πh (s) = Qπh(s, π(s, h)),
where sh′+1 ∼ Ph(·|sh′ , ah′). We define the optimal value function V ∗h and the optimal actionvalue function Q∗h as V ∗ h (s) = maxπ V π h (s) and Q ∗ h(s, a) = maxπ Q π h(s, a). By definition, the
value function V πh (s) and action-value function Q π h(s, a) are bounded in [0, H]. For any function V : S → R, we denote [PhV ](s, a) = Es′∼Ph(·|s,a)V (s′). Therefore, for each stage h ∈ [H] and policy π, we have the following Bellman equation, as well as the Bellman optimality equation:
Qπh(s, a) = rh(s, a) + [PhV πh+1](s, a), Q∗h(s, a) = rh(s, a) + [PhV ∗h+1](s, a), (3.1)
where V πH+1 = V ∗ H+1 = 0. At the beginning of the episode k, the agent determines a policy πk to be followed in this episode. At each stage h ∈ [H], the agent observes the state skh, chooses an action following the policy πk and observes the next state with skh+1 ∼ Ph(·|skh, akh). 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. MDPM(S,A, H, {rh}Hh=1, {Ph}Hh=1) is a linear MDP such that for any stage h ∈ [H], there exists an unknown vector µh, an unknown measure θh(·) : S → Rd and a known feature mapping φ : S ×A → Rd, such that for each (s, a) ∈ S ×A and s′ ∈ S,
Ph(s′|s, a) = 〈 φ(s, a),θh(s ′) 〉 , rh(s, a) = 〈 φ(s, a),µh 〉 .
For simplicity, we assume that µh, θn(·) and φ(·, ·) satisfy ‖φ(s, a)‖2 ≤ 1 for all s, a, ‖µh‖2 ≤ √ d and ∥∥θh(S)∥∥2 ≤ √d. The linear MDP assumption automatically suggests that for any policy π, the action-value function Qπh 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πh}Hh=1 such that for any s, a, h ∈ S ×A× [H], Qπh(s, a) = 〈φ(s, a),wπh〉.
Next we define the regret and ( , δ)-PAC formally. Definition 3.3. For an RL algorithm Alg, we define its regret on learning an MDP M(S,A, H, r,P) in the first K episodes as the sum of the suboptimality for episode k = 1, . . . ,K,
Regret(K) = K∑ k=1 V ∗1 (s k 1)− V πk 1 (s k 1),
where πk is the policy in the k-th episode . Definition 3.4. For an RL algorithm Alg and a fixed , let π1, π2, . . . be the policies generated by Alg. Let N = ∑∞ k=1 1{V ∗1 (sk1)− V πk 1 (s k 1) > } be the number of episodes whose suboptimality gap is greater than . Then we say Alg is ( , δ)-PAC with sample complexity f( , δ) if
P(N > f( , δ)) ≤ δ. Remark 3.5. Dann et al. [7] suggested that an algorithm with a sublinear regret is not necessarily to be an ( , δ)-PAC algorithm. However, with some modification, Jin et al. [12] showed that any algorithm with a sublinear regret can be converted to a new algorithm which is ( , δ)-PAC, which does not contradict with the claim by [7]. For example, Ghavamzadeh et al. [9] and Zhang et al. [26] proposed algorithms with Õ( √ SAHT ) regret, and both algorithms can be converted into new
algorithms which are ( , δ)-PAC with sample complexity Õ(SAH2/ 2).
Both regret and PAC guarantees are not perfect. As Dann et al. [7] showed, an algorithm with sub-linear regret or (δ, )-PAC bound may fail to converge to the optimal policy. For an (δ, )-PAC algorithm with ∆t = /2(t ∈ N), it still has linear regret O( T ) and will never converge to the optimal policy. For an algorithm with a sub-linear regret bound, a constant sub-optimality gap may still occur infinite times. Therefore, Dann et al. [7] proposed uniform-PAC algorithms, which are defined formally as follows. Definition 3.6. For an RL algorithm Alg, let π1, π2, . . . be the policies generated by Alg. Let N = ∑∞ k=1 1{V ∗1 (sk1) − V πk 1 (s k 1) > } be the number of episodes whose suboptimality gap is greater than . We say Alg is uniform-PAC for some δ ∈ (0, 1) with sample complexity f( , δ) if P(∃ > 0, N > f( , δ)) ≤ δ.
The following theorem suggests that a uniform-PAC algorithm is automatically a PAC algorithm and an algorithm with sublinear regret.
Algorithm 1 Uniform-PAC OFUL (UPAC-OFUL) Require: Regularization parameter λ, confidence radius βl(l ∈ N)
1: Set Cl ← ∅, l ∈ N and the total level S1 = 1 2: for round k = 1, 2, .. do 3: for all level l ∈ [Sk] do 4: Set Σlk = λI + ∑ i∈Cl xix > i
5: Set blk = ∑ i∈Cl xiri and w l k = (Σ l k) −1blk 6: end for 7: Receive the action set Dk 8: Choose action xk ← argmaxx∈Dk min1≤l≤Sk(w l k) >x + βl √ x>(Σlk) −1x 9: Set level lk = 1
10: while √
x>k (Σ lk k ) −1xk ≤ 2−lk and lk ≤ Sk do
11: lk ← lk + 1 12: end while 13: Add the new element k to the set Clk and receive the reward rk 14: Set the total level Sk+1 as Sk+1 = maxl:|Cl|>0 l 15: end for
Theorem 3.7 (Theorem 3, [7]). If an algorithm Alg is uniform-PAC for some δ ≥ 0, with sample complexity Õ(C1/ + C2/ 2), where C1, C2 are constant and depend only on S,A,H, log(1/δ). Then, we have the following results:
• 1: Alg will converge to optimal policies with high probability at least 1−δ: P (
limk→+∞ V ∗ 1 (s k 1)−
V πk1 (s k 1) = 0
) ≥ 1− δ
• 2: With probability at least 1 − δ, for each K ∈ N, the regret for Alg in the first K episodes is upper bounded by Õ( √ C2K + C1 + C2).
• 3: For each ≥ 0, Alg is also ( , δ)-PAC with the same sample complexity Õ(C1/ + C2/ 2).
Theorem 3.7 suggests that uniform-PAC is stronger than both the PAC and regret guarantees. In the remainder of this paper, we aim at developing uniform-PAC RL algorithms with linear function approximation.

heading: 4 Warm up: Uniform-PAC Bounds for Linear Bandits
text: 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 {Dk}∞k=1 be a fixed sequence of decision/action sets. At round k, the agent selects an action xk ∈ Dk by the algorithmH and then observes the reward rk = 〈µ∗,xk〉+ k, where µ∗ ∈ Rd is a vector unknown to the agent and k is a sub-Gaussian random noise. xk, k,µ∗ satisfy the following properties:
∀k ∈ N, λ ∈ R, E [ eλ k |x1:k, 1:k−1 ] ≤ exp(λ2/2), ‖xk‖2 ≤ 1, ‖µ∗‖2 ≤ 1. (4.1)
Our goal is to design an ( , δ)-uniform-PAC algorithm with sample complexity f( , δ) such that P ( ∃ > 0, ∞∑ k=1 1 { ∆k := max x∈Dk 〈µ∗,x〉 − 〈µ∗,xk〉 > } > f( , δ) ) < δ,
where ∆k := maxx∈Dk〈µ∗,x〉 − 〈µ∗,xk〉 denotes the suboptimality at round k. Here we assume the weight vector µ∗ satisfies ‖µ∗‖2 ≤ 1, to be consistent with the assumption made in Abbasi-Yadkori et al. [1]. Our assumption can be easily relaxed to the general ‖µ∗‖2 ≤ B case with an additional logB factor in the sample complexity, as can be seen in the following analysis.
Why existing algorithms fail to be uniform-PAC? Before proposing our algorithm, it is natural to ask whether existing methods have already been uniform-PAC. We take OFUL [1] for example,
which is the state-of-the-art linear bandit algorithm in our setting. At round k, OFUL constructs an optimistic estimation of the true linear function 〈µ∗,x〉, by doing linear regression over all past k selected actions xi, 1 ≤ i ≤ k and their corresponding rewards. The optimistic estimation has a closed-form as the summation of the linear regression predictor and a quadratic confidence bound
w>k x+α √ x>Σ−1k x, where Σk = λI+ ∑k−1 i=1 xix > i [16]. Following the standard analysis of OFUL in [1], we obtain the following upper confidence bound of the suboptimality gap ∆k:
With probability at least 1− δ, ∀k > 0, ∆k = O (√ d log(k/δ)‖xk‖Σ−1k ) , (4.2)
where the log k is due to the fact that OFUL makes use of all past k observed actions. Since the agent can only say whether an arm is good or not based on the confidence bound of ∆k, 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 as k increases). That makes the agent fail to recognize those “good” arms and instead pull the “bad” arms infinite times, which suggests that OFUL is not a uniform-PAC algorithm. For other algorithms, they either need to know the total round T before running the algorithm [5], or need to assume that the decision sets Dk 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 1 is to divide all the historical observed data into non-overlapping sets Cl, while each Cl 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 1 only constructs optimistic estimation of 〈µ∗,xk〉 over the first Sk sets Cl individually, where Sk is the number of non-empty sets Cl. In detail, the optimistic estimation over Cl has the form
(wlk) >x + βl √ x>(Σlk) −1x, (4.3)
where Σlk is the covariance matrix for actions in set Cl (Line 4), and wlk is the estimation of µ∗ obtained by ridge regression defined in Line 5. Meanwhile, for a newly selected action xk, Algorithm 1 needs to decide which Cl it should be added to. Inspired by [5], Algorithm 1 tests the “uncertainty” of xk against Cl, by calculating its confidence bound ‖xk‖(Σlk)−1 . Then Algorithm 1 adds xk to the lowest possible level where the “uncertainty” is larger than a certain threshold (i.e., ‖xk‖(Σlk)−1 > 2
−l). Such a selection rule guarantees two things simultaneously. First, it ensures that the cardinality of each Cl is finite, due to the fact that the summation of ‖xk‖(Σlk)−1 can be properly bounded. Second, it also guarantees that the "uncertainty" of the reward corresponding to xk is still small, since by the level selection rule we have ‖xk‖(Σl−1k )−1 ≤ 2
−(l−1). Lastly, to make use of all Sk optimistic estimations, Algorithm 1 constructs the final predictor as the minimal value of Sk individual predictor (4.3) over Cl (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.
The following theorem shows that Algorithm 1 is indeed uniform-PAC. Theorem 4.1. For any δ ∈ (0, 1), if we set λ = 1 and βl = 6 √ dl log(dl/δ) for every level l ∈ N, then there exists a constant C such that with probability at least 1− δ, for all > 0, the number of rounds in Algorithm 1 which have sub-optimality no less than is bounded by
∞∑ k=1 1 { max x∈Dk 〈µ∗,x〉 − 〈µ∗,xk〉 > } ≤ Cd2 log3 ( d/(δ ) ) 2 .
Remark 4.2. Theorem 4.1 suggests that Algorithm 1 is uniform-PAC with sample complexity O(d2 log3 ( d/(δ ) ) / 2). According to Theorem 3.7, this new algorithm will converge to the optimal policy. Theorem 4.1 also implies an Õ(d √ T ) regret for infinite-arm linear bandit problem. This result matches the lower bound Ω(d √ T ) [6] up to a logarithmic factor. Furthermore, Theorem 4.1
implies that Algorithm 1 is an ( , δ)-PAC algorithm with sample complexity Õ(d2/ 2). Specifically, if we set = ∆min, Theorem 4.1 implies an Õ(d2/∆2min) sample complexity to identify the best arm2, which matches the sample complexity Õ(d logK/∆2min) in [19] when K = Θ(2
d). 2Soare et al. [19] denoted by ∆min the gap of the rewards between the best arm and the second-best arm. In this setting, the sample complexity to find the best arm is identical to the sample complexity to find an < ∆min sub-optimal arm.

heading: 5 Uniform-PAC Bounds for Linear MDPs
text: In this section, we propose our new FLUTE algorithm (Algorithm 2) for learning linear MDPs, and provide its theoretical guarantee.
Intuition behind FLUTE At a 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:
rh(s, a) + [PhV ∗h+1](s, a) = Q∗h(s, a) = 〈θ∗h,φ(s, a)〉, (5.1)
where the second equality holds due to Proposition 3.2. (5.1) suggests that in order to learn Q∗h, it suffices to learn θ∗h, which can be roughly regarded as the unknown vector of a linear bandits problem with actions φ(s, a) and rewards rh(s, a) + V ∗h+1(s
′), where (s, a, s′) belongs to some set C. Since V ∗h+1 is unknown, we use its estimation Vh+1 to replace it. Therefore, we can apply Algorithm 1 to this equivalent linear bandits problem to obtain our uniform-PAC RL algorithm FLUTE.
Details of FLUTE We now describe the details of FLUTE. For each stage h, FLUTE maintains non-overlapping index set {Clh}l, each Clh contains state-action-next-state triples (sih, aih, sih+1). Let S1 = 1 and Sk denote the number of non-empty sets {Cl1}l at episode k for k ≥ 2. Instead of maintaining only one estimated optimal value function Vk,h and action-value function Qk,h [13], FLUTE maintains a group of estimated value functions {V lk,h}l and action-value functions {Qlk,h}l. In detail, at stage h, given {V lk,h+1}l, FLUTE calculates wlk,h as the minimizer of the ridge regression problem with training dataset (sih, a i h, s i h+1) ∈ Clh and targets V lk,h+1(sih+1) (Line 8), and defines Qlk,h as the summation of the linear predictor (w l k,h) >φ(s, a) and a quadratic confidence bonus
βl √ φ(s, a)>(Σlk,h) −1φ(s, a) (Line 9), where βl is the confidence radius for level l and Σlk,h is the
covariance matrix for contexts in set Clh. Then FLUTE defines value function V lk,h 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-value functions {Qlk,h}l, FLUTE executes the greedy policy induced by the minimal of action-value function Qlk,h over 1 ≤ l ≤ lkh−1 − 1, where lk0 = Sk + 1 and lkh−1 is the level of the set Alh−1 that we add the triple (skh−1, akh−1, skh). After obtaining (skh, a k h, s k h+1), to decide which set Clh should this triple be added, FLUTE calculates the confidence
bonus √
φ(skh, a k h) >(Σlk,h) −1φ(skh, a k h) and puts it into the l-th set if the confidence bonus is large
(Line 19), similar to that of Algorithm 1.
The following theorem shows that FLUTE is uniform-PAC for learning linear MDPs. Theorem 5.1. Under Assumption 3.1, there exists a positive constant C such that for any δ ∈ (0, 1), if we set λ = 1 and βl = CdHl √ log(dlH/δ), then with probability at least 1− δ, for all > 0, we have ∞∑ k=1 1{V ∗1 (sk1)− V πk 1 ≥ } = O(d3H5 log 4(dH/(δ ))/ 2).
Remark 5.2. Theorem 5.1 suggests that algorithm FLUTE is uniform-PAC with sample complexity O(d3H5 log4(dH/(δ ))/ 2). According to Theorem 3.7, FLUTE will converge to the optimal policy with high probability. Theorem 5.1 also implies an Õ( √ d3H4T ) regret for linear MDPs. This result matches the regret bound Õ( √ d3H3T ) of LSVI-UCB [13] up to a √ H-factor. Furthermore,
Theorem 5.1 also implies FLUTE is an ( , δ)-PAC with sample complexity Õ(d3H5/ 2), which matches the O(d3H3/ 2) sample complexity of LSVI-UCB up to an H factor.
Computational complexity As shown in Jin et al. [13], the time complexity of LSVI-UCB is O(d2AHK2). Compared with the LSVI-UCB algorithm, Algorithm 2 maintains non-overlapping index sets {Clh} and computes the corresponding optimistic value function for each level `. Without further assumption on the norm of φ(s, a), the number of different levels in the first K episodes is at
Algorithm 2 Uniform PAC Least-Square Value Iteration (FLUTE) Require: Regualarization parameter λ, confidence radius βl
1: Set Clh ← ∅, l ∈ N, h ∈ [H] and set the total level S1 = 1 2: for episode k = 1, 2, .. do 3: Set V lk,H+1(s, a) = 0 for all state-action pair (s, a) ∈ S ×A and all level l ∈ [Sk] 4: for stage h = H,H − 1, .., 1 do 5: for all level l ∈ [Sk] do 6: Set Σlk,h = λI + ∑ i∈Clh φ(sih, a i h)φ(s i h, a i h) >
7: Set blk,h = ∑ i∈Clh φ(sih, a i h) [ rh(s i h, a i h) + V l k,h+1(s i h+1) ] 8: wlk,h ← (Σlk,h)−1blk,h 9: Qlk,h(s, a)← min { H, (wlk,h) >φ(s, a) + βl √ φ(s, a)>(Σlk,h) −1φ(s, a) }
10: end for 11: for all level l ∈ [Sk] do 12: V lk,h(s)← maxa min1≤i≤lQik,h(s, a) 13: end for 14: end for 15: Receive the initial state sk1 and set the current level l k 0 = Sk + 1 16: for stage h = 1, 2, ..,H do 17: Take action akh ← argmaxa min1≤i≤lkh−1−1Q i k,h(s k h, a) 18: Set level lkh = 1
19: while √
φ(skh, a k h) >(Σ lkh k,h) −1φ(skh, a k h) ≤ 2−l k h and lkh ≤ lkh−1 − 1 do
20: lkh ← lkh + 1 21: end while 22: Add element k to the set Cl k h
h
23: Receive the reward rh(skh, a k h) and the next state s k h+1 24: end for 25: Set the total level Sk+1 as Sk+1 = maxl:|Cl1|>0 l 26: 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 φ(s, a) equals 1, then the number of levels in the first K episodes is O(logK). Thus, since the computational complexity of our algorithm at each level can be bounded by that of LSVI-UCB, the computational complexity of Algorithm 2 is O(d2AHK2 logK) under the above assumption.

heading: 6 Proof Outline
text: 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 l, our constructed linear function 〈wlk,h,φ(s, a)〉 is indeed a "good" estimation of the optimal action-value function Q∗h(s, a). By the uniform self-normalized concentration inequality over a specific function class, for any policy π, any level l ∈ N and any state-action pair (s, a) ∈ S ×A, we have the following concentration property:
(wlk,h) >φ(s, a)−Qπh(s, a) = [ Ph(V lk,h+1 − V πh+1) ] (s, a) + ∆,
where |∆| ≤ βl √ φ(s, a)>(Σlk,h) −1φ(s, a). Then, taking a backward induction for each stage
h ∈ [H], let Ω = { Qlk,h(s, a) ≥ Q∗h(s, a), V lk,h(s) ≥ V ∗h (s),∀(s, a) ∈ S × A, k, l ∈ N, h ∈ [H] } denote the event that the estimated value function Qlk,h and V l k,h upper bounds the optimal value function Q∗h and V ∗ h . 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 k is upper bounded by the function value gap between our estimated function Qlk,1 and the value function of our policy πk.
V ∗1 (s k 1)− V πk 1 (s k 1) ≤ max
a min 1≤l≤lk0−1 Qlk,1(s k 1 , a)−Q πk 1 (s k 1 , a k 1) ≤ Q
lk1−1 k,1 (s k 1 , a k 1)−Q πk 1 (s k 1 , a k 1),
From now we only focus on the function value gap for level lkh. Some elementary calculation gives us
Q lkh−1 k,h (s k h, a k h)−Q πk h (s k h, a k h)
≤ 2βlkh−1 √ φ(skh, a k h) >(Σ lkh−1 k,h )
−1φ(skh, a k h)︸ ︷︷ ︸
Ikh
+Q lkh+1−1 k,h+1 (s k h+1, a k h+1)−Q πk h+1(s k h+1, a k h+1)
+ [ Ph(V lkh−1 k,h+1 − V πk h+1) ] (skh, a k h)− ( V lkh−1 k,h+1(s k h+1)− V πk h+1(s k h+1) )︸ ︷︷ ︸ ∆k,h . (6.1)
Therefore, by telescoping (6.1) from stage h = 1 to H , we conclude that the sub-optimality gap V ∗1 (s k 1)− V πk 1 (s k 1) is upper bounded by the summation of the bonus I k h and ∆k,h. The summation of the bonus ∑ Ikh is the dominating error term. According to the rule of level l, if k ∈ Clh at stage
h ∈ [H], then Ikh satisfies √ φ(skh, a k h) >(Σl−1k,h ) −1φ(skh, a k h) ≤ 2−(l−1). Furthermore, the number
of elements added into set Clh can be upper bounded by |Clh| ≤ 17dlH4l (See Lemma C.1). Thus we can bound the summation of Ikh . For ∑ ∆k,h, it is worth noting that ∆k,h forms a martingale
difference sequence, therefore by the standard Azuma-Hoeffding inequality, ∑
∆k,h can be bounded by some non-dominating 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, we show how to transform the gap into the final uniform-PAC sample complexity. Instead of studying any accuracy directly, we focus on a special case where = H/2i(i ∈ N), which can be easily generalized to the general case. For each fixed = H/2i(i ∈ N), let K denote the set K = { k|V ∗1 (sk1)− V πk 1 ≥ } and m = |K|. On the one hand, according to the definition of set K, the summation of regret in episode k(k ∈ K) is lower bounded by m . On the other hand, according to Step 2, the summation of sub-optimality gaps of episode k(k ∈ K), is upper bound by
∑ k∈K [V ∗1 (s k 1)− V πk 1 ] ≤ ∑ k∈K H∑ h=1 2βlkh−12 −(lkh−1)
︸ ︷︷ ︸ J1
+ ∑ k∈K H∑ h=1
∆k,h︸ ︷︷ ︸ J2 . (6.2)
To further bound J1, we divide those episode-stage pairs (k, h) ∈ N × [H] into two categories: S1 = { (k, h)|2βlkh−12 −(lkh−1) ≤ /(2H) } and S2 = { (k, h)|2βlkh−12 −(lkh−1) > /(2H) } . For the first category S1, the summation of terms Ikh in this category is upper bound by∑ k∈K H∑ h=1 1{(k, h) ∈ S1}2βlkh−12 −(lkh−1) ≤ ∑ k∈K H∑ h=1 2H = m 2 . (6.3)
For any episode-stage pair (k, h) in the second category S2, the level lkh satisfies 2l k h ≤ Õ(dH2/ ) due to the choice of βlkh−1. Suppose l ′ is the maximum level that satisfies 2l ≤ Õ(dH2/ ) and for each level l ≤ l′, the cardinality of set Clh can be upper bounded by |Clh| ≤ 17dlH4l. Thus, the summation of terms Ikh in category S2 is upper bound by∑
k∈K H∑ h=1 1{(k, h) ∈ S2}2βlkh−12 −(lkh−1) ≤ ∑ k∈K H∑ h=1 l′∑ l=1 1{lkh = l}2βl−12−(l−1)
= H∑ h=1 l′∑ l=1 2βl−12 −(l−1) ∑ k∈K 1{lkh = l} ≤ H∑ h=1 l′∑ l=1 2βl−12 −(l−1)17dlH4l
= Õ(d3H5/ ). (6.4)
Back to (6.2), for the second term J2, according to Azuma–Hoeffding inequality, it can be controlled by Õ(H √ Hm). Therefore, combining (6.3), (6.4) with the bound of J2, we have
m ≤ ∑ k∈K V ∗1 (s k 1)− V πk 1 ≤ m /2 + Õ(d3H5/ ) + Õ(H √ Hm),
and it implies that the number of episodes with a sub-optimality gap greater than is bounded by Õ(d3H5/ 2). This completes the proof.

heading: 7 Conclusion and Future Work
text: In this work, we proposed two 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 to show that linear bandits and RL 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 of Computing in Fall 2020. JH, DZ and QG are partially supported by the National Science Foundation CAREER Award 1906169, IIS-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.

Review summaries:
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).