Provably Efficient Kernelized Q-Learning

We propose and analyze a kernelized version of Q-learning. Although a kernel space is typically infinite-dimensional, extensive study has shown that generalization is only affected by the effective dimension of the data. We incorporate such ideas into the Q-learning framework and derive regret bounds for arbitrary kernels. In particular, we provide concrete bounds for linear kernels and Gaussian RBF kernels; notably, the latter bound looks almost identical to the former, only that the actual dimension is replaced by a different notion of dimensionality. Finally, we test our algorithm on a suite of classic control tasks; remarkably, under the Gaussian RBF kernel, it achieves reasonably good performance after only 1000 environmental steps, while its neural network counterpart, deep Q-learning, still struggles.

1 Introduction Q-learning, which dates back to as early as Watkins and Dayan (1992), has undergone tremendous development in the past decades and remains one of the most sample-efficient reinforcement learning (RL) frameworks in practice. The modern implementation of Q-learning maintains a value function Q t at each step t such that where (s, a, r, s ′ ), representing the quadruple of state, action, reward, next state, is sampled from historical data, γ is a discounting factor, and actions that maximizes Q t are taken with priority (Mnih et al., 2013). The most successful implementation of the above paradigm is perhaps deep Q-learning (DQN) (Mnih et al., 2013), in which each Q t is represented by a (deep) neural network and actions are taken to maximize Q t with probability 1 − ǫ, and randomly otherwise. Despite the success of DQN, our theoretical understanding of Q-learning is still lacking. While there exist regret analyses for certain versions of tabular Q-learning (Jin et al., 2018;Liu and Su, 2021), these algorithms and their analyses hardly generalize to non-tabular settings. Algorithms and corresponding regret analyses have also been derived for more general function classes (see e.g. ; Zhou et al. (2021b), among others). However, the proposed algorithms use either episodic value iteration , which is not sample-efficient in practice, or extended value iteration Zhou et al. (2021b), which is not time-efficient in practice.
We seek to fill the gap between theory and practice in this paper. Specifically, we propose and analyze a kernelized version of (1), named kernelized Q-learning (KQL), where each Q t is restricted to a reproducing kernel Hilbert space (RKHS) and optimized with kernel ridge regression, and exploration is done through upper confidence bound.
RKHS are non-parametric function classes that are rich enough in that they are dense in the space of continuous functions if the kernel is universal (Sriperumbudur et al., 2011). Therefore, RKHS are, in some sense, as universal as neural networks (Hornik et al., 1989) while being easier to analyze thanks to decades of research on kernel machines. Combining standard machinery for analyzing kernel-based learning with our novel approach to analyze Q-learning, we arrive at general regret bounds for arbitrary kernels (Theorem 6.1); in particular, we provide concrete regret bounds for linear kernels (Corollary 6.2) and Gaussian RBF kernels (Corollary 6.4). Notably, the latter looks almost identical to the former, only that the actual dimension is replaced by a different dimensionality that is at most polylogarithmic in the number of steps.
We complement our theoretical analyses with experiments on a subset of classic control tasks provided in OpenAI Gym (Brockman et al., 2016). We faithfully implement the exact KQL algorithm for which we derive regret bounds and choose hyperparameters based on the bounds. We demonstrate superior sample efficiency of KQL, even when compared with DQN. To the best of our knowledge, KQL is the first provably low-regret algorithm that excels in commonly used benchmarks.  (2019); Zhang et al. (2020; gave regret bounds in the episodic setting. Regret bounds for the discounted setting was not studied until recently (Liu and Su, 2021;He et al., 2021b), due to trickier definition of the regret.
Later work generalizes tabular analyses to the linear model episodic setting Zanette et al., 2020), the linear mixture model episodic setting (Cai et al., 2020;Ayoub et al., 2020;Modi et al., 2020;Zhou et al., 2021a;He et al., 2021a), and the linear mixture model discounted setting (Zhou et al., 2021b). We note here that the linear mixture model assumes the model class has finite (and small) degrees of freedom, which mitigates many challenges in model estimation (see discussion in Jin et al. (2020, Related Work)). In particular, while Zhou et al. (2021b) gives a seemingly better regret bound than ours when the model class is linear in certain sense, they are under far stricter assumptions.
This paper is most related to , which proposes and analyzes KOVI, a kernelized version of episodic value iteration. The major difference is that  operates on an episodic setting, where in each episode, an optimistically optimal Q-value function is calculated based on all the historical data using episodic value iteration. On the other hand, we focus on the non-episodic setting, where in each step, a new Q-value function, which is not necessarily (optimistically) optimal based on current historical data, is calculated from the Q-value function from the previous step using one-step discounting. Such difference indeed affects theoretical analysis in that the non-episodic update introduces pathological dependencies that must be properly handled (e.g., Lemma 3.12). Furthermore, it also makes our algorithm significantly more applicable to real-world problems. For example, in our MountainCar experiment (Section 7), the length of an episode is 200. Given a budget of 1000 interactions, KOVI can only update its value functions 1000/200 − 1 = 4 times (since each step in an episode uses a different value function). It is very unlikely that any progress can be made after such a small number of parameter updates (indeed, we were not able to make KOVI work on Mountain-Car after extensive parameter tuning or even hacking). On the other hand, KQL does not distinguish between different episodes, and can update its value function 999 times. In fact, we will show that KQL even outperforms DQN in the low-budget setting.
Other kernelization efforts include Xu et al. (2005), which uses kernel regression to approximate the discounted return of a Markov chain, Xu et al. (2007), which uses kernel regression as a subroutine in a policy iteration procedure, no exploration is involved thus no regret bound can be obtained; Chowdhury and Gopalan (2019), which requires very restrictive assumptions, as discussed in ; , which assumes linear mixture models, therefore suffers from aforementioned limitations of such models; Ormoneit and Sen (2002); Barreto et al. (2016), which are based on local averaging and require Lipschitzness assumptions, and no exploration is involved thus no regret bound can be obtained; Domingues et al. (2021), which is similarly based on local averaging and require Lipschitzness assumption, but with Lipschitzness-based exploration. More general function approximation classes have also been considered. Notably, ; Ayoub et al. (2020) gave regret bounds in terms of Eluder dimension and covering number of the function class. However, most of these attempts either result in generally intractable algorithms (Krishnamurthy et al., 2016;Jiang et al., 2017;Dann et al., 2018;Dong et al., 2020;Ayoub et al., 2020), or make very restrictive assumptions such as deterministic environment (Wen and Van Roy, 2013;, or the existence of a finite latent state space .

Bandits
Bandit problems can be thought as a special case of RL problems by setting the horizon to 1 in the episodic setting, or setting the discounting factor to 0 in the discounted setting. Naturally, many ideas for RL analyses originates from the bandit literature.
Analyses for RL is generally much harder than for bandits, in that it needs to additionally avoid exponential dependencies on the state space and horizon. In particular, (near) optimal dependencies for these quantities require very sophisticated techniques.

Preliminaries
For a measurable space X, let B(X) be the space of real-valued bounded measurable functions over X equipped with the supremum norm · ∞ , let P(X) be the set of all probability measures over X. For any positive integer n, denote by [n] the set {1, 2, · · · , n}. For any two functions f, g : X → [0, ∞), f (x) = O(g) means that there exists c ≥ 0 such that for any x ∈ X, f (x) ≤ c · g(x).
Let H be a Hilbert space. Denote by ·, · H the inner product on H. Denote by · H the norm induced by the inner product. If T : H → H is a bounded self-adjoint positive-definite linear operator, define the Mahalanobis norm f T = T f, f H . Denote by B HS (H) the space of Hilbert-Schmidt operators from H to H. Denote by ·, · HS the inner product on B HS (H). Denote by · HS the norm induced by the inner product. For any u, v ∈ H, denote by u ⊗ v the linear operator such that for any f ∈ H, Let H be a real-valued RKHS over a set X such that the corresponding kernel K is bounded. For any x ∈ X, denote by K x the reproducing function at x, i.e., K x is the unique function that satisfies for any . For any f ∈ H, define the norm For any bounded linear operator T : H → H, define the norm

Effective Dimension and Pseudo Dimension
We are going to introduce two concepts used in the learning literature to capture the properties of a RKHS, effective dimension and pseudo dimension. Note that many similar concepts have been introduced (see Srinivas et al. (2009;; Valko et al. (2013); Chowdhury and Gopalan (2017); ;  among many others) under various names such as information gain. All these variants are in some sense equivalent to each other, in that they all capture the effective dimensionality of a RKHS, perhaps up to a logarithmic factor.
In this section, let X be a set, K : X ×X → R be a kernel, n be a positive integer, x 1:n = (x 1 , x 2 , · · · , x n ) ∈ X n , and λ > 0, K be a n × n matrix where
Remark 3.2. It is easy to see that d eff (λ, x 1:n ) is a non-negative non-increasing function of λ, it tends to 0 as λ → ∞. It is also a bounded function of λ in that d eff (λ, x 1:n ) ≤ n.
The following lemma gives a bases-independent representation of d eff ; in particular, it shows that the effective dimension is invariant to the permutation of data, therefore x 1:n in the definition of d eff can be simply treated as a set.
The following lemma gives yet another representation of d eff , which will be particularly useful when analyzing our proposed algorithm later.
The following lemma shows that the effective dimension is non-decreasing as data accumulate.
It is instrumental to see how d eff behaves under common kernels. For linear kernels, the following lemma is well-known.
Lemma 3.6 (Effective dimension under linear kernels). If X is a d-dimensional Euclidean space and For Gaussian RBF kernels, we have the following recent result. Notably, the effective dimension grows only polylogarithmically with n λ . Lemma 3.7 (Effective dimension under Gaussian RBF kernels (Altschuler et al., 2018)). Let d be a positive integer, X = x ∈ R d : x 2 ≤ 1 , and K(x, y) = e −η x−y 2 2 for some η ≥ 0, then for any λ ≤ n, 1 Also called effective degrees of freedom in Hastie et al. (2009).
Remark 3.9. Similar to d eff , d pse (λ, x 1:n ) is also a non-negative non-increasing function of λ, it tends to 0 as λ → ∞. However, in contrast to d eff , d pse (λ, x 1:n ) is not a bounded function of λ; if K is not a zero matrix, as λ → 0, it tends to infinity.
Remark 3.10. Because the determinant only changes sign when swapping rows or columns, the pseudo dimension is invariant to the permutation of data, therefore just like in the case of d eff , x 1:n in the above definition can be simply treated as a set.
The following lemma shows that d pse is at most a logarithmic factor (in terms of n λ ) larger than d eff . Lemma 3.11 ( (Jézéquel et al., 2019)).
The following lemma will play an important role in our analysis.
Lemma 3.12. The following are true: In particular, Lemma 3.12.(I) says that, similar to the effective dimension (Lemma 3.5), the pseudo dimension is also non-decreasing as data accumulate.
To conclude the introduction of pseudo dimension, let us introduce a generalization of Abbasi-Yadkori et al. (2011, Theorem 1) stated in terms of d pse in the following Lemma. Its proof is almost identical to the proof in the special case when H has a linear kernel. We also note that the inequality in the lemma visually resembles Theorem 1 in Chowdhury and Gopalan (2017), however, the quantities on the left hand side of the inequalities are actually quite different.
be a real-valued stochastic process such that η t is F t measurable, and is zero mean and R-sub-Gaussian conditioned

Covering Number of Operators
Let T : X → Y be a bounded linear operator where X and Y are normed vector spaces. N (ǫ, T ), the ǫ-covering number of T , is defined to be the cardinality of the smallest set V ⊆ Y such that for any x ∈ X, Given a real-valued RKHS H, we are interested in the covering numbers of two identity mappings, Both N (ǫ, I H, * ) and N (ǫ, I HS, * ) captures properties H. However, unlike the effective dimension introduced in Section 3.1.1 and the pseudo dimension introduced in Section 3.1.2 that depend on a scale λ, these covering numbers are data-independent and depend on a granularity ǫ instead.

Setup
Consider a Markov decision process (MDP) with state space S, action space A, transition function P : S × A → P(S), and reward function 3 r * : S × A → [0, 1]. Consider a T -step RL process. Denote by s t and a t the state and action taken in the tth step (t starts from 1), the algorithm receives reward r * (s t , a t ) after taking action a t and a new state s t+1 is sampled from P(s t , a t ).
We measure the performance of an RL algorithm by its γ-regret (Liu and Su, 2021;He et al., 2021b;Zhou et al., 2021b), defined by where V * (s) is the optimal γ-discounted return starting from state s, in the sense that and Here the multiplier (1 − γ) in (2) is only for normalization such that Regret γ (T ) ≤ T . Denote by a * (s) any action that attains V * (s) in (3).
Let H be a real-valued RKHS defined on S × A such that the corresponding kernel K : (S × A) 2 → R is bounded. Without loss of generality, we will assume K ∞ > 0; and we further assume K is properly normalized so that for any (s, a) ∈ S × A, K (s,a) H ∈ [1/2, 1].
Let us convert P into a linear operator by defining We will assume there exists an (unknown) M : B(S) → H such that The operator norm of M is defined by We assume M ≤ ρ. Similarly, for the reward function, we will also assume there exists an (unknown) r ∈ H such that Let σ ∈ [0, 1] be a bound on the stochasticity of the MDP. Specifically, for any (s, a) ∈ S × A, f ∈ B(S) such that f ∞ ≤ 1, f (s ′ ) is σ-sub-Gaussian when s ′ ∼ P(s, a). Clearly, σ can always be set to 1, and for a deterministic MDP, σ can be set to 0.

Algorithm
We propose kernelized Q-learning (KQL) (Algorithm 1), which can run in time O((T + g)T 2 |A|), where g is the time to compute x, y → K(x, y). When the kernel is linear, the running time can be improved (by special implementation) to O(T d 2 |A|), where d is the dimension of the feature space that S × A is embedded into.
We list closed-form representations of the variables maintained by Algorithm 1 below. In fact, our main results in Section 6 hold for any algorithm for which these variables are maintained.

Main Results
We now state the main result of this paper, an upper bound on the regret for KQL.
in Algorithm 1, or any algorithm that satisfies (1)-(3) in Fact 5.1 and acts to maximize Q t therein, with probability at least 1 − p, if then Let us take a closer look at how the bound depends on ρ, ǫ, σ, and λ. Note that the bound can be decomposed into three parts, involving ρ, ǫ, σ respectively: The first part, involving the complexity bound ρ, is Here d λ upper bounds a non-increasing function of λ that is bounded by T and log e(T +λ) λ log(1+1/λ) is a non-decreasing function of λ that tends to 1 as λ → 0 and tends to ∞ as λ → ∞. This suggests that λ needs to strive a balance between the two conflicting dependencies.
The second part, involving the approximation bound ǫ, is Here d λ upper bounds a non-increasing function of λ, log e(T +λ) λ log(1+1/λ)λ is a strictly decreasing function of λ, and tends to 1 as λ → ∞. This suggests that as far as the ǫ-related part is concerned, the larger the λ the better.
The third part, involving the stochasticity σ, is Here both d λ and c λ upper bound a non-increasing function of λ. log e(T +λ) λ log(1+1/λ)λ , as discussed before, is a strictly decreasing function of λ that tends to 1 as λ → ∞. log e(T +λ) λp is a strictly decreasing function of λ that tends to log e p as λ → ∞. This suggests that as far as the σ-related part is concerned, the larger the λ the better.
To conclude, both the ǫ-and σ-related parts of the regret bound prefers larger λ; however, the ρ-related part in general calls for a λ that is neither too large nor too small.
The following corollary is a direct consequence of Theorem 6.1, Lemma 3.6, Lemma 3.14.
Corollary 6.2 (Regret for linear kernels). In Theorem 6.1, if K((s 1 , a 1 ), (s 2 , a 2 )) = φ(s 1 , a 1 ) ⊺ φ(s 2 , a 2 ) where φ : S × A → R d for some positive integer d such that φ(s, a) 2 ≤ 1 for any (s, a) ∈ S × A. Then we can choose d λ = d and some c λ = O d 2 log eH(T +λ) λ such that (4) is always true, and therefore with probability at least 1 − p, Remark 6.3. Recall that in the general setting λ should be neither too large nor too small. However, since here d λ is bounded by d, which is independent of λ, if λ is sufficiently small such that λ = O(1/T ), we can make the dependency on ρ to be ρ √ T d (1−γ) 2.5 . In other words, in the linear setting, if the MDP is deterministic and the dynamics can be exactly represented by functions in H, then we can choose λ = O(1/T ) such that Comparing this with choosing λ = Θ(1), a factor of log(eT ) is reduced.
A perhaps more interesting example would be the regret bound for the widely-used Gaussian RBF kernel. The following corollary is a direct consequence of Theorem 6.1, Lemma 3.7, Lemma 3.15, Lemma 3.16.
Corollary 6.4 (Regret for Gaussian RBF kernels). In Theorem 6.1, if K((s 1 , a 1 ), (s 2 , a 2 )) = e −η φ(s1,a1)−φ(s2,a2) 2 2 for some η ≥ 0 and φ : S ×A → R n for some positive integer n such that φ(s, a) 2 ≤ 1 for any (s, a) ∈ S ×A. Then we can choose some such that (4) is always true, and therefore with probability at least 1 − p, We see that the above regret bound only differs from the bound in Corollary 6.2 in that d is replaced by O η + log e(T +λ) λ(1−γ) . This suggests that this new quantity indicates the effective dimensionality under the Gaussian RBF kernel at scale λ. Note that although a smaller η would benefit the regret bound, an η too small would violate the assumption on ρ as described in Section 4.
Remark 6.5. Again we can inspect how the ρ-related term in the bound, In other words, in the Gaussian RBF kernel setting, if the MDP is deterministic and the dynamics can be exactly represented by functions in H, then we can choose λ = Θ (1/T ) such that Comparing this with choosing λ = Θ(1), a factor of log(eT ) is reduced. Recall that in Remark 6.3, we showed that the same thing happens in the linear setting.

Experiments
We test KQL on a suite of classic control tasks included in OpenAI Gym (Brockman et al., 2016): Mountain-Car, Pendulum, Acrobot, and CartPole. The action space of Pendulum is discretized to {−1, 0, 1}, all other environments have discrete action space natively.

Methodology
For any state s and action a, let [s, a] be the concatenation of the state vector and the one-hot embedding of the action; let l be the length of state vectors. The states are first normalized such that s ∞ ≤ 1 for all s. We experiment with two types of kernels: • Linear Kernel K((s 1 , a 1 ), (s 2 , a 2 )) = [s 1 , a 1 ] ⊺ [s 2 , a 2 ] 2(l + 1) + 1 2 .
We normalize the rewards to fall within [0, 1]. Since all environments are deterministic we can let σ = 0. We also believe that for these simple environments, if a correct kernel is used, ǫ can be made infinitesimally small. Our theoretical results (Theorem 6.1) suggest that in this case we can set and our discussions in Remark 6.3 and Remark 6.5 suggest we can set We heuristically set β = √ λ 1−γ so that Q t 1/(1 − γ) at the beginning of learning, and set λ = 1 10T so that λ is large enough to not cause numerical issues.
To emphasize the test on sample efficiency, for each environment, all algorithms are only allowed 1000 steps through the OpenAI Gym interface; a reset is only allowed in the very beginning and after a done is received. We use the same discounting factor γ = 0.95 for all algorithms and all environments.

Results
The results are shown in Table 1. As we can see, the linear kernel performs poorly on all tasks. In fact, its performance is not noticeably better than a random policy. Without handcrafted or learned feature embedding, the value function is highly non-linear; thus linear kernel suffers from huge approximation error. DQN makes progress on most tasks, with the exception of MountainCar, which requires more than random exploration in order to succeed with a very limited amount of interaction. Remarkably, the Gaussian RBF kernel achieves high return and performs best on all tasks, compensating for its long running time by its far superior sample efficiency.

Where Next
We have demonstrated that KQL is both theoretically sound and empirically promising. However, kernel methods are known to suffer from the curse of kernelization -their time complexity has a super-linear dependency on the number of samples, KQL is no exception.
There are two standard ways to trade sample efficiency for time complexity in kernel-based online learning: one is sparsification, which aims at keeping the number of support vectors d ≪ T by various strategies (see e.g. Engel et al. (2004); Sun et al. (2012); Calandriello et al. (2017) and the discussion in Lu et al. (2016, Related Work)); the other is kernel approximation, which aims at projecting vectors in an RKHS into a Euclidean space, for example, using random Fourier features, and reduce the kernel setting to the linear setting (Lu et al., 2016;Jézéquel et al., 2019). Given its already impressive performance even without any kernel sparsification or approximation, it is not hard to believe that with proper acceleration, KQL is able to tackle more challenging tasks such as Atari games (Bellemare et al., 2013). We leave it as future work to investigate these directions.
Z. Zhang and X. Ji. Regret minimization for reinforcement learning by evaluating the optimal bias function. arXiv preprint arXiv:1906.05110, 2019.
Z. Zhang, X. Ji, and S. Du. Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon.

A Proof of Lemma 3.16
Let N be the set of non-negative integers. For any multi-index ν = (n 1 , n 2 , · · · , n d ) ∈ N d , define |ν| = n i=1 n i . The following facts will be useful. Fact A.2 (Taylor expansion). For any nonnegative integer n and t ≥ 0, Define the function It is well-known that B = e ν : ν ∈ N d is an orthonormal basis for H (see e.g. Steinwart et al. (2006, Theorem 3.7)). Consequently, e ν1 ⊗ e ν2 : ν 1 , ν 2 ∈ N d is an orthonormal (Schauder) basis for B HS (H). Now note that where (a) is due to Cauchy-Schwarz and (b) is due to Fact A.1. Next we introduce for all positive integer N two orthogonal projections: P N , which is the projection onto span {e ν1 ⊗ e ν2 : |ν 1 | < N, |ν 2 | < N }, and Q N , which is the projection onto P ⊥ N . Note that where (a) is due to Cauchy-Schwarz and (b) is due to Fact A.1 and (c) is due to Fact A.2. Note that we can choose N = 2 ln 2 √ 2 ǫ + e 2 η such that I HS, * Q N ≤ ǫ/2. Finally, note that ln N (ǫ, I HS, * ) ≤ ln (N (ǫ/2, I HS, * P N ) · N (ǫ/2, I HS, * Q N )) = ln N (ǫ/2, I HS, * P N ) where in (a) we used I HS, * P N ≤ I HS, * = 1 and the fact that a n-dimensional unit ball can be ǫ-covered by (1 + 2/ǫ) n points.

B Proof of Other Lemmas
Proof of Lemma 3.4. Let W = (Σ + λI) −1 , note that where (a) is due to Lemma 3.3.
Proof of Lemma 3.5. Let W n = ( n i=1 K xi ⊗ K xi + λI) −1 and f = W n−1 K xn . It is easy to verify that Therefore, where (a) is due to Lemma 3.4 and (b) is due to (6).
Proof of Lemma 3.6. Let Σ = n i=1 x i x ⊺ i . By Lemma 3.3 we have that d eff (λ, x 1:n ) = tr (Σ + λI) −1 Σ . Let λ 1 , λ 2 , · · · , λ d be the eigenvalues of Σ, we have tr (Σ + λI) −1 Σ = n i=1 λi λi+λ ≤ d. Proof of Lemma 3.12. First note that since Σ i−1 /λ is a linear operator of rank at most i−1, det (Σ i−1 /λ + I) is well-defined. Therefore, e dpse(λ,x1:i) e dpse(λ,x 1:(i−1) ) − 1, where (a) can be proved for example using the same argument used for Cesa-Bianchi and Lugosi (2006, Lemma 11.11). Note that (7) already implies (I), since a norm is non-negative. Next, it is easy to verify that K xi 2 (Σi−1+λI) −1 ≤ 1/λ and that x ≤ b ln(1+b) ln(1 + x) for any x ∈ [0, b]. Therefore, where (a) is due to (7). Therefore (I) is proved, since a norm cannot be negative. Note that the above argument is still true if we replace x i by an arbitrary x ∈ X. Consequently, denote by [a, b] the concatenation of sequence a and sequence b, we have where we used (I) in (a), (b), (c) and the nonnegativity of d pse in (b); in particular, in (b) we canceled the (i, τ )th term in (A) with the (2i + 1 − τ, i + 1)th term in (B), where the first index of a term is its position in the first summation and the second index is its position in the second summation. This concludes the proof of (II).
Proof of Lemma 3.14. In the case of linear kernel, for any x ∈ H, x H = x * = x 2 ; and for any linear operator T over X, T * ≤ T F = T HS . Because a n-dimensional unit ball can be ǫ-covered by (1 + 2/ǫ) n points, the lemma follows immediately.

C Proof of Main Results
We will prove Theorem 6.1 in this section. We first introduce some notations. For any t ∈ [T ], let prev(t) For any p > 0, let E p be the event that for any s ∈ S, a ∈ A, t ∈ [T ], Q t (s, a) − Q * (s, a) − γ M * V t−1 − V * (s, a) ≤ (Φ + Ψ p ) · K (s,a) Wt + 2ǫ 1 − γ .
where V 0 can be any function that is bounded in [0, 1/(1 − γ)]. We start from some auxiliary lemmas.
Lemma C.7. For any p > 0, E p happens with probability at least 1 − p.
Proof. First note that for any t ∈ [T ], Q * = r * + γM * V * , and consequently To proceed, note that for any t ∈ [T ], Let us bound E 1 (s, a), E 2 (s, a), E 3 (s, a), E 4 (s, a) separately. First note that |E 1 (s, a)| ≤ λ r W t K (s,a) + λ (γM V * ) W t K (s,a) (a) ≤ λ · r Wt + γM V * Wt · K (s,a) Wt where (a) is due to Cauchy-Schwarz and (b) is due to the upper bound in Lemma C.1.
Also note that Therefore, we have that Now we are ready to prove our main theorem.