On the Convergence and Sample Complexity Analysis of Deep Q-Networks with $\epsilon$-Greedy Exploration
Authors: Shuai Zhang
Hongkang Li
Meng Wang
Miao Liu
Pin-Yu Chen
Songtao Lu
Sijia Liu
Keerthiram Murugesan
Subhajit Chaudhury
Venue: NeurIPS 2023 poster (2023)
Keywords: Reinforcement learning
Deep Q Network
Convergence analysis
Sample complexity
Generalization analysis
TL;DR: Convergence analysis and finite-sample analysis of deep Q-network equipped with $\epsilon$-greedy exploration

Abstract: This paper provides a theoretical understanding of deep Q-Network (DQN) with the $\varepsilon$-greedy exploration in deep reinforcement learning.
Despite the tremendous empirical achievement of the DQN, its theoretical characterization remains underexplored.
First, the exploration strategy is either impractical or ignored in the existing analysis.  
Second, in contrast to conventional Q-learning algorithms, the DQN employs the target network and experience replay to acquire an unbiased estimation of the mean-square Bellman error (MSBE) utilized in training  the Q-network. However,
the existing theoretical analysis of DQNs lacks convergence analysis or bypasses the technical challenges by deploying a significantly overparameterized neural network, which is not computationally efficient. 
This paper provides the first theoretical convergence and sample complexity analysis of the
  practical setting of DQNs with $\epsilon$-greedy policy. We prove an iterative procedure with decaying $\epsilon$ converges to the optimal Q-value function geometrically. Moreover, a higher level of $\epsilon$ values enlarges the region of convergence but slows down the convergence, while the opposite holds for a lower level of $\epsilon$ values. Experiments justify our established theoretical insights on DQNs.

On the Convergence and Sample Complexity Analysis of Deep Q-Networks with E-Greedy Exploration
Shuai Zhang
Hongkang Li Rensselaer Polytechmic Institute
New Jersey Institute of Technology
Meng Wang
Miao Liu
Pin- Yu Chen IBM Research
Songtao Lu IBM Research
Rensselaer Polytechnic Institute
IBM Research
Sijia Liu Michigan State University
Keerthiram Murugesan
Subhajit Chaudhury
IBM Research
IBM Research
Abstract
This paper provides a theoretical understanding of Deep Q-Network (DQN) with the s-greedy exploration in deep reinforcement learning. Despite the tremendous empirical achievement of the DQN, its theoretical characterization remains un- derexplored. First, the exploration strategy either impractical ignored in the existing analysis. Second, in contrast to conventional Q-lcarning algorithms, the DQN employs the target network and experience replay to acquire an unbiased estimation of the mean-square Bellman eтrоr (MSBE) utilized in training the Q- network. However, the existing theoretical analysis of DQNs lacks convergence analysis or bypasses the technical challenges by deploying significantly over- parameterized neural network, which is not computationally efficient. This paper provides the first theoretical convergence and sample complexity analysis of the practical setting of DQNs with e-greedy policy. We prove an iterative procedure with decaying converges to the optimal Q-value function geometrically. More- over, higher level of & values enlarges the region of convergence but slows down the convergence, while the opposite holds for lower level of values. Experi- ments justify our established theoretical insights on DQNs.
Introduction
Reinforcement learning (RI.) is a sequential decision-makinn process for a learning agent taking actions in the environment. RL has found important applications in autonomous control [37, 36), healthcare [16], Internet of Things [40, 33], and natural language processing [70]. The environment of RL problem is modeled as Markov decision process (MDP) with an underlying state transi- tion probability matrix. The goal the problem is to find an optimal policy to select the best actions to maximize the immediate and future rewards. Q-learning [77] has been recognized as of the most promising and efficient learning algorithms for seeking the optimal policy because it does not require the knowledge of the model of the environment (namely, "model free"") and learn from data generated from non-optimal policy (namely, "off-policy"), Traditional Q-learning approaches centered tabular methods [82, 41] linear function approximations [65, 13] estimate the optimal action-value (Q-value) function. However, tabular methods require sample complexity scal- ing the order of state space, which is impractical for modern RL problems involving large or even infinite state space [82]. Q-learning with linear function approximation is limited to applications only when the transition matrix admits linear feature representation [23].
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1: Comparison among some representative works of Q-learning with function approximation.
Work
Neural Approximation
Convergence of MSBE
E-greedy
Yang & Wang (2019)
X
Xu & Gu (2020)
/
al, (2020)
/
Liu et al. (2022)
/
X
This work
/
Due to the remarkable advancements in deep neural networks (DNNs), the Deep Q-network (DQN) framework has emerged as a powerful approach that leverages the expressive power of non-linear functions and the ability generalize to unknown states. DQN has proven to be a pioneering solution that addresses challenges encountered by traditional approaches. In the DQN framework [51], the Q-value function is approximated using a DNN, and the algorithm iteratively updates the Q- value function by collecting data following the é-greedy policy. The e-greedy policy is the simplest approach to balance exploration and exploitation. Namely, with probability of e, we select a random action (exploration), and with probability of 1 E, we choose the best action according to the current estimated Q-value function (exploitation). s-greedy is myopic compared with other strategic explorations, e.g., Thompson campling-basee [71, 55, 25] and optimism in the face of the uncertainty (OFU)-based [30, 31] ones. However, implementing these strategic explorations is not computationally efficient in DQNs [17], while DQNs equipped with e-greedy policy have shown empirical success in diversified applications, e.g., the game of Go [63], Atari games [51], robotics [34], and autonomous vehicles [61, 12, 60).
Despite the numerical success, the theoretical understanding of DQN remains elusive, which could prevent its applications in domains requiring reliable and safe decision-making. First, updating the Q-value function involves minimizing mean-squared Bellman error (MSBE) function. However, existing convergence analysis and statistical properties are predominantly limited to linear models, failing to capture the complexities present non-linear neural networks like DQN. Second, the sam- ple complexity required for the convergence of MSBE is still not well comprehended. Achieving the desired accuracy in this context often demands a sample complexity that grows exponentially with the input dimension [46], rendering it impractical and inefficient in real-world scenarios. Third, the optimal selection of the & value in DQN remains a gap in existing research. The hyperparameter tuning in algorithms involved with neural networks can be arduous and time-consuming. For in- stance, without a well-designed hyperparameter configuration, only a small fraction (c.g., 1%) of the possible combinations yield satisfactory results in neural network training [76].
Contributions. To the best of knowledge, this paper presents the first theoretical study with con- vergence analysis for Deep Q-Networks (DQNs) utilizing the e-greedy policy. A comparison with existing works can be found Table 1. The paper focuses on the Q-value function approximated by DNN. It offers a comprehensive analysis of the convergence of DQNs and provides insights into the estimation error of the learned Q-value function, accompanied by analysis of the sample complexity. The key contributions of this study are as follows:
1. The convergence analysis of DQN with bounded estimation errors. Assuming the existence of a DNN with unknown weights W* that matches the optimal Q-value function, this paper proves that the learned model via DQNs equipped with e-greedy policy through the (accelerated) gradient descent algorithm converges linearly to W up to some characterizable estimation error.
2. The theoretical characterization for a wide selection range of E over iterations. This pa- per provides lower and upper bounds of at each iteration for the convergence of DQNs and, in particular, characterizes the sample complexity, estimation error, and convergence rate of the DQN equipped with e-greedy with decreasing s. Moreover, this paper proves that a higher level of val- ues leads to an enlarged region of convergence, which relaxes the requirement on the initialization, while a lower level of values leads to faster convergence.
The sample complexity analysis for learning a desired Q-value function. We quantify the required sample complexity, depending on the neural network parameters and distribution shift of the collected data, for the learned model to converge to the desired accuracy. Typically, the estimation ervor of the converged model scales in the order of 1 /Ne, where N₂ is the number of samples.

---

2 Related Works.
Q-learning with linear function approximation. In the setting of linear function approximation, the Q-function is assumed to be a linear function of either the feature mapping [83, 32, 92] or a mixture of some basis kernels [91, 52]. Early works mainly focus on the algorithm design [6. 48, 2] and convergence analysis [38, 47, 67, 14, 69] but lacks theoretical guarantees with polynomial sample complexity. Assuming the underlying Q-function can be exactly represented as a linear function of the feature mapping with some unknown parameters, several sample-efficient algorithms are proposed to find the ground -ruth mapping with unite-sample guarantee [11, 80), and the sample complexity depends linearly on the feature dimension [80].
Q-learning with non-linear function approximation. Recent approaches with non-linear function approximation mainly fall into the frameworks of the Bellman Eluder (BE) dimension [30, 18, 58, 27], Neural Tangent Kernel (NTK) [81, 10, 79, 10, 20, 53], and Besov regularity [68, 29, 54, 46, 24). The Eluder dimension is at least in an exponential order even for a two-layer neural network [19], leading to uncharacterizable sample complexity. The NTK framework linearizes deep neural networks to tackle convergence in non-linear models. However, it requires using computationally inefficient extremely wide neural networks [81]. Moreover, the sample complexity can exponentially increase with the input feature dimension, necessitating a substantial number of samples for accurate estimation. Furthermore, the NTK approach fails explain the advantages of non-linear neural networks over linear function approximation [46, 24]. Besov space requires the neural networks to be sparse and makes an unpractical assumption that the algorithm can find the global optimal of the non-convex objective function [29, 54, 46, 24]. To the best of our knowledge, only [46] considers e-greedy policy with theoretical analysis applicable to DQNs. However, the model is limited to sparse neural networks, and it cannot characterize the case of varying E.
Supervised learning with neural networks. Compared with Q-learning in RL, where the label of the sampled data depends on the currently estimated Q function, analyzing supervised learning is less challenging. where sampled data label is known and fixed across the training. Existing theo- retical results for supervised learning are largely built upon NTK [28, 21, 39, 15, 43, 45], model recovery [90, 26, 3, 64, 88, 85, 87], and structured data [44, 62, 8, 1, 35, 78, 84, 42]. Due to the high non-convexity of neural networks [59], the one- me-hidden-layee neural network is still a sfate-of-the- art practice for convergence analysis and generalization guarantees. Additional assumptions, c.g., Gaussian distribution [89, 7J, linear separable data [75, 9] on the data distribution, are needed for finite-sample analysis.
3 Problem Formulation: Notation, Background, and Algorithm
The Markoy Decision Process and Q-learning. A discounted Markov decision process (MDP) is defined as (S,A, P.r.7). where S is the state space, A is the action set. P S x A - A(S) is the transition operator, and ph..* := P(s'|s, a) denotes the transition probability from current state and action to the next state s'. In addition, r S SSSXA A - Rmax, Rmax] is the reward function, and 7 E (0, 1) is the discount factor.
At a state s E S, the agent takes action a E A according to some behavior policy т, denoted as ~ T(s) (or s' following the transition probability Pa.... Meanwhile, the agent receives an immediate reward r(s, a) from the environment. Let {s,, a, 1000 be the generated sequential data given the behavior policy ı and transition probability P. We define the state-value function Vn at state as
((s) for deterministic policy). Then, the system moves to the next state
V (T(s)=E,,,
a:) 80 = =]]
which is the expected total discounted reward starting from the state s. For any state-action (s, a), the corresponding Q-value (or action-value) function Q, of policy π is defined as
Q a) =E,,p p E 7'r(,,, a.) 80 = 8, a0 = a].
Then, the goal of the agent is to find an optimal policy x² that maximizes the state-value function in (1) for all states, which is equivalent to
Q" (8, a) = max Q= (0(88 a) =r(s, a) + Eey max (*((', (s),a'),
(3)
3

---

where (3) is known as the Bellman equation. With the optimal Q-value function Q*, the optimal policy can be derived via (s) argmax, (* a) [77. 66].
The Deep Neural Network Model. The DQN utilizes deep neural network (DNN) H : R - R
to approximate the optimal Q-value function Q' in (3). Specifically, given input a e R2 the output of the L-hidden-layer DNN with K neurons in each hidden layer is defined as
H(W x) := 1 (W,, @ (W, æ)),
(4)
where W1 E R Wi E R with 1 = 2. L, and W = [vee (W1) ..... vec...ec(((M)))) (WL)
the concatenation of the vectorization of all parameter matrices. ((-) is the nonlinear activation function, and we consider the ReLU activation function, i.e., 6(2) max (0, z). Then, the Q-value function ((s,a) is parameterized using the DNN as
((W;s,0) = H (W:
(5)
where x: : SS A + Rd is the feature mapping of the state-action pair. Without loss of generality, assume <<ss, a)l < 1. Then, the goal of DQN-based Q-learning is to minimize the mean squared Bellman error (MSBE) as
min f(W) == a) (Q(W: 8, - r(s, a) - 7 Ee'je, max :':'''')) (6) W
a'
where μ is the distribution of (s, a) following the optimal policy n².
3.1 The Deep Q-Network Algorithm
Algorithm Deep Q-Network
1: Input: Number of iterations T x M, and experience replay buffer size N, exploration probability {Er)7=1. step size n, and momentum parameter 3.
2: Initialize the Q-network with weights (10..))
3: for t 1= 0, 2, ................................ T 1 do
4: Select the initial weights (((.0)
5: for m = 0, 2.... .M- do
6: Sample data and store in the experience replay buffer D, following e--gredy policy,
namely, state an, with probability Ex, select random action a., otherwise select an argmax, ((W((..))8...))
7: Sample random mini-batch of transition m( from the replay buffer D..
8: Set yo = To + y max. Q (t.0)) s',, a) for n E 1,2,..., ,, (m))
9:
Perform gradient descent step
((.+++1) (t(.. (m) (w(l.m) + ((W().)) - w((m--1)
10: end for
Set (++1.0) (t.M))
12:
end for
The learning problem (6) is solved via the DQN equipped with s-greedy exploration, as summarized in Algorithm 1. In (-th outer loop, we initialize the Q-value function using currently estimated weights (t..0) as (t.())))) (line 4). Then, for each inner loop. the agent selects and executes actions according to the e-greedy policy (line 6), namely, with probability e, we select a random action, and with probability 1 E, we select the action based on the greedy policy with respect to (t.(). The data are stored in replay buffer with size N (line 7). Then, we sample a mini-
batch of independent samples from Dr, denoted as D(m)) for the m-th inner loop (line 8). Next, we update the current weights using mini-batch (accelerated) gradient descent algorithm (line 9). The gradient descent (GD) direction in this step at point W is represented as
(m) (W) EnED(()) (m)) (Q(W: Sn, an) -/²)) VwQ(W: Sn, an),
gi
where
v r. + 7 max ma)) a').
(8)
d'EA
Note that (7) can be viewed as the gradient of E(e.a)=pe (Q(W;s, - Ea max Q (w(( s'
(9)
o'

---

which is the approximation to (6) via fixing the max, ( as max, (WW())). After moving along the GD direction, accelerated gradient descent (AGD) adds momentum term, denoted by 3 (t.m)) ((1 to accelerate the convergence rate [57]. Vanilla SGD can be viewed special case of AGD by letting / = O. After updating neuron weights in the inner loop, we set the network as the currently estimated Q-value function (WW(..) (line 1 11) and repeat the steps above.
4 Theoretical Results
4.1 Takeaways of the Theoretical Findings
We consider the general setup of DQNs with e-greedy under some commonly used assumptions. To the best of our knowledge, we provide the first theoretical characterization of both the convergence and sample complexity analysis for DQNs with e-greedy. The major notations are summarized in Table 2. We first briefly introduce the key takeaways our results, and the formal theoretical results are introduced in Section 4.3.
Table 2: Some Important Notations
K
Number of neurons in each hidden layer.
L
Number of the hidden layers.
d
Dimension of the feature mapping of (s, a).
N,
The sample complexity for 8-optimal policy.
w
The global optimal to (6).
The value of || - W'
A small positive constant with linear depen- dence Et.
C2
The fraction of actions with data at itera- tion such that argmax, Q(W(tt)) s,a) * argmax, Q(W";
(TI) Theoretical characterizations of [T for convergence. We prove that for wide selection of {st} values that decrease over time, Algorithm I converges to Q" linearly up to some estimation error. Let Ce measure the value level of e s. A higher level of æ values (i.e., a larger c.) leads to an enlarged region of convergence (in the order of cz), measured by the distance from the initialization (0.0) to W Thus, larger & values relax the requirements on (0,0)) A lower level of values (i.e.. smaller c₂) leads to faster convergence with rate in the order of c.. Our findings explain the intuition that the agent tends to explore more at the beginning and exploit more after gaining enough knowledge during the exploration.
(T2) Convergence to the optimal Q-value function Q' with geometric decay. The learned models converge to the ground truth model Q* with a geometric decay up to some bounded estimation error. The convergence rate is upper bounded by 7 Cg (1 7). When y is close to one, the problem emphasizes long-term rewards. While the immediate reward can be observed directly, the future reward needs be estimated by the learned Q function shown in (7). Therefore, with a large % the learned Q function needs more iterations to converge, which leads to a slow convergence rate.
(T3) Sample complexity for achieving desired estimation error of the optimal Q-value func- tion. With the proper selection of {ex) the estimation error of the learned model scales in the Cr order of //_, CT is the fraction of actions following the current greedy policy that differ from
the ones following the optimal policy. N, is the number of samples. With a smaller discounted fac- tor 7, the problem focuses more on the immediate reward, which can be observed directly, making Q* easier to learn. The learned model achieves a small estimation error given a small distribution shift, large sample size, or a small discounted factor.
4.2 Assumptions
We propose assumptions commonly used in existing RL and neural network learning theories and notations to simplify the presentation. Assumption 1 assumes the existence of a good approximation of DNN to Q", which guarantees (6) is solvable. The assumption is commonly used in both deep learning theories [90, 86) and reinforcement learning theories [46, 24]. Assumption 2 assumes the samples from experience replay are independent and identically distributed (i.i.d),, which follows the assumptions in existing theoretical analysis of DQN [24, 53] and matches the intuition of using experience replay to break temporal dependence among the samples. Specifically, we have
Assumption 1. There exists DNN with weights W such that minimizes (6) as f(W*) 0.
5

---

Assumption assumes that the Q-value function with some unknown ground truth W can repre- sent the optimal Q-value function.
Assumption 2. Suppose the mini-batch data i.id. samples from the replay buffer following the distribution μ4, which the stationary distribution of the behavior policy at t-th outer loop.
Assumption 2 assumes the mini- batch at the t-th outer loop are i..dd samples following 14,, where H4 is the stationary distribution of (s, a) generated by er-gredy policy at f-th outer loop". The mini- batch samples are close to being independent given the experience size in practice is sufficiently large (~ millions [51]).
In what follows, we define two quantities Ct and p to simplify the presentation of theoretical results. Definition 1. C. [0, is the fraction of non-optimal state-action pair (8, a) in the greedy policy with respect to Q(W(1.0)) i.e, the fraction of (s, o) pairs that satisfy
a = argmaxx Q(W(L.))
s. ; + π (s)
(10)
among all (8, pairs following the greedy policy at t-th outer loop as a argmax Q(Wit.)) 8,a'),
C can be viewed as the difference between behavior policy and optimal policy. Theorem 1 shows the general results for any value of C. Nevertheless, the greedy policy is improved over time, e.g.. updating the weights every few steps (line 11 in Algorithm 1). Hence, C, depends W(t,0) and is expected to decrease as (((,,)) approaching W [56, 92], which will be discussed in Corollary 3.
Definition 2. Let be the value of
p min B(e.a) (a VWQ(W":s.a))
(11)
suggests the radius of the local convex region of the objective function. We provide the lower bound for p in Lemma (see the proof in Appendix E.2), suggesting a sufficiently large local convex region near W*
4.3 Major Theoretical Results
Lemma I characterizes the convergent point when minimizing (9) using the mini-batch gradient descent in the (-th outer loop under certain conditions. Specifically, given that the initial weights at the t-th outer loop sufficiently close to the ground truth as shown in (12) and the replay buffer is large enough as shown in (13), the distance between the learned model weights ((+11,0) and W are bounded from above as shown in (14).
Lemma 1 (Estimation error of (++1.))) Suppose Assumptions 1 & 2 hold and the initial neuron weights at the t-th outer loop satisfy
1 1-ll))) (1-11166)) p. [
| W 0 -11- O(VN)
ex
(12)
K
The step size n is 1/T, and the size of the replay buffer is
N ==ppp= K3 L. L-6 d. log 17gg--7 T).
(13)
Then, with the high probability of at least 1 dd the neuron weights (+++1,0) generated from Algorithm satisfy
(1- -
W'
7 (1.)) W C1
-
(14)
@(vN)
1 1-7
Remark 1 (Large replay buffer reduces the estimation error and the requirement for (t.0)). From (14), a larger N leads to reduced distance between (t-11,0) and W Moreover, (12) implics that we increase the size of replay buffer N, the upper bound of e increases, indicating the algorithm can tolerant a large range of W (t.0).
Note that W' does not need unique. We abuse notation W W' to denote minimum distance of W to any W satisfying Assumption 1.
The framework can be extended into non i..dd samples, Appendix G.

---

In the following corollary, we show the upper and lower bound of at the t-th outer loop. The lower bound guarantees that the RHS of (12) larger than O, so we have sufficiently large radius for convergence. The upper bound ensures (14) be less than et, indicating an improved estimation of Q' across the iterations.
Corollary 1 (Range of e). Given the assumptions and conditions in Theorem 1 hold. To ensure the existence of a good initialization at iteration t, Es needs to satisfy
E z 1 @(VN). (1-e+),
(15)
To ensure the estimated learned model is improving iterations, Et needs to satisfy
(1
Ct
(16)
C1- |A| Rmmax 1 1-C,
Remark 2 (Reduce as increases). The lower bound can always be smaller than the upper bound given a sufficiently large N as shown in (13). From both (15) and (16), we know that & needs to decrease as e decreases. Specifically, the lower bound of & is a linear function of ct, and the upper bound of E, a linear function of e. Namely, we need a relatively large En at the beginning since the distance between initial point (0.00) and W is large. As increases, ct, which is the distance of learned neuron weights (t.00) the ground truth W becomes smaller, and should decrease e, to guarantee an improved ((++1.0) over ((+.9).
Theorem I shows that the learned model from Algorithm converges to the optimal Q-value func- tion Q with geometric decay up to an estimation error shown in (20).
Theorem (Convergence to Q')- Suppose Assumptions and 2 hold, the buffer size N satisfies (13). Let us define Cmax be constant that is larger than Ct for 1 StST. when satisfy
Ce ..OVN) Ct
Cmax
= (1 (1- (max) |A| Rmax
1 Cmax
(17)
for a fixed constant Cg E (0, (1 - 7),,, and the initialization satisfies
w (0,0)) - W - 0(1 - O(VN)
C- W
(18)
K
Then, with the high probability of at least 1 - T q-h we have
1. the learned weights decay geometrically with
W(+1.0) - Wf (7 + ce (1-7)) - W' A I log,(1/N), (19)
2. the returned model (IW(),))) exhibits estimation error in the order of 1/VN with
-W* Cmax |AA] Rmax
sup (Q(W)).))) - Q-1 (a,0)
(20)
(1-7)).((VN)
where T 2 log, (1/N).
Remark (Selection of st). The value of e, is influenced by three key factors: Cg. Cmax. and the current estimation error bound e,. The constant &₂ is fixed and controls the magnitude of the values in the sequence < providing way to regulate the level of Et. Regarding Cuaxx C2 tends to decrease as the iteration index t increases, indicating a progressive improvement in the policy and resulting in smaller data distribution shift. Hence, estimate Cuax, we can leverage Co. which is obtained by collecting data based on the policy max, (0,00 8, a). Moreover, with cg fixed, the estimation error e follows a geometric decay pattern, as depicted in (19). This behavior allows us to use the expression (7 + Ce (1 - 7))" eo an estimate for e
Remark 4 (Geometric decay to Q*).. From (19) and (20), we know that the learned model from the proposed algorithm converges Q" with a geometric decay up to some estimation error. The convergence rate is in the order of + (1 - 7), and the estimation error is in the order of (1-7)-2, Ciax/ V VN. As we mentioned in the takeaways in Section 4.1, a small discounted factor y leads to a fast convergence rate. We have a reduced estimation with large buffer with size N, small distribution shift Cr, and small 7.
7

---

Remark 5 (Larger values for enlarged region of convergence and smaller values for faster con- vergence). From (17), we know that c. controls the value level of Es. From (18), larger ce (i.e., a higher level of values) increases the upper bound of | W 1l2 and, thus, enlarges the proper region of W(0,)) (19) indicates that the convergence rate is in the order of cg. A smaller cs (i.e., lower level of e values) leads to faster convergence.
In the following corollary, we provide the sample complexity for achieving 8 estimation error as shown in (21), where (x-)) omits some log factors. The corollary can be obtained by letting (20) to be less than a desired accuracy 6.
Corollary 2 (Sample complexity). To achieve an estimation error of 6, the required number of samples, referred to the sample complexity, needs to scitisfy
N₂ = N log7 = (-((1111))
Cmax 1A K d T/8²).
(21)
Remark 6 (Sample complexity). (21) shows that the sample complexity is a linear function of d and L, where is the feature mapping of the state-action pair (s, a) and L is the number of layers. Given the freedom of degree of W is a linear function of d and L, respectively, the sample complexity is almost order-wise optimal with respect to d and L.
The following corollary presents a tighter bound for the model estimation error compared with (20). This improvement arises from stronger assumption on C., which becomes a function of [ W 1|2. Compared with (20), the estimation error bound in (24) and (25) considers the
cases that the behavior policy is improved as W(t,0) becomes closer to W As a result, we achieve a more precise and tighter estimation of the error in the model.
Corollary (Distribution shift and estimation error). Assume that C. is Hölder continuous with a factor a
C = O (1.0) ()))),
(22)
ffor 0 < a S and all & E [T]. When &, satisfy
Ce (VVN).e et
C.
(23)
(1- Ci) -AA Rmmx
1- 1-Ce"
the estimation error of the Q-function satisfies
(AA) Rmax) T
Q(
sup
-
(24)
(s.a)
(1 (1-7) O(N
In the special case that C O([ W 112), then
SuP(..a) Q
Q+1 =0 O.
(25)
Remark 7 (Reduced zero estimation error when behavior policy is improved over iterations).
Recall the definition of C2 in Definition 1. If e is zero, i.c., W, = W the action selected following the greedy policy always the optimal action, which means that C. O. Therefore, it is reasonable to assume that C2 is Hölder continuous as shown in (22). When a > O, we can see that (24) is less than (20), indicating a reduced estimation error and sample complexity. Typically, if C₁ has an order of growth less than e, near W zero estimation error is achievable.
4.4 The Roadmap of Proofs, Comparison with Existing Works, and Limitations
The proof of Theorem I draws inspiration from the model estimation framework in the supervised learning setting [90, 88). The key idea is to use a population risk function (PRF) to characterize the objective function in (9). By satisfying certain conditions such as having sufficient training sam- ples and a bounded data distribution shift, the approximation error between the PRF and objective function can be bounded. This allows for the characterization of the optimization problem in (9) by analyzing the landscape and convergence properties of the PRF.
"Although this equation depends on the algorithm's trajectory, it can be easily derived from a time- independent equation IT (s|a) x (s|aa) < Cl[W - W Also, this equation is weaker condition than (2) in [92]. which holds universally across the entire space and model parameter space.
8

---

In comparison to existing proofs based on the model estimation frameworks, this paper addresses two additional challenges. Firstly, it extends the proof from onehidden-llayr neural networks to multi-layer neural networks. This extension is achieved by providing new tools for characterizing the Hessian matrix (refer to Lemma 3) and concentration bound (refer to Lemmas 3 and 6). Addi- tionally, this paper characterizes the differences between the two functions caused by the interaction of neuron weights across layers in the gradient and Hessian matrix. Secondly, the paper extends the proof from supervised learning settings to Q-learning settings. This requires characterizing the addi- tional error term caused by the data distribution shift and "noisy" labels (refer to Lemma 3) because the empirical risk function is no longer an expectation of the defined population risk function.
Existing state-of-the-ar theoretical results on Q-learning with neural network approximations pri- marily revolve around the NTK and Besov regularity frameworks. In the NTK framework, the networks are assumed to be extremely over-parameterized, requiring impractical projection step and resulting in еπхог bounds that cannot be characterized for networks with finite width. In the Besov regularity framework, the neural network needs be sparse, which does not align with the DQN algorithm. Furthermore, the analysis in the Besov regularity framework relies on the achiev- ability of the global minimizer of the non-convex problem in (9), which cannot be guaranteed using GD algorithms. This paper takes a significant step towards bridging the gap between theoretical understanding and practical applications of DQN by addressing these challenges. However, there still remains a gap between the theoretical results and numerical findings. Future research directions include devising efficient exploration strategies for DQNs to further enhance their performance and extending the theoretical analysis to variants of DQNs and policy gradient-basee methods.
5 Numerical Experiments
In this section, we provide numerical justification that our theoretical findings are aligned with practical DQNs through the Atari Pong game, which is commonly used for DQNs in [50, 51, 73]. We take the Double DQN (DDQN) [73], one of the most popular variants of DQN, as the backbone in the setup. DDQN differs from DQN only in (8) via changing y y QWW((.)) s', "²,"") to y + (W.((.)) s', a²) where a' = argmax, QWW(+.)); s', a). DDQN outperforms DQN in the relief of overoptimism and the improvement of stability. Our numerical experiments on DDQN also indicates that our analysis applies to the variants of DQN.
The input to the network is 84 x 84 4 images, where the last dimension represents the number of frames in history. The network is a convolutional neural network consisting of three convolutional layers and one fully-connected layer. The algorithm terminates if the average score over the recent 20 episodes does not improve or the algorithm reaches the maximum episode set as 200, which is around 4 10a training steps. The testing score is calculated based similar setup as the training process by fixing the maximum memory size N as 2000 and greedy policy, i.e., & = 0. Each point in the plot is averaged over 10 experiments with error bar representing the standard deviation.
Estimation errors with respect to the sample complexity N. As the Q-value function is the estimate of the expected cumulative reward, we use the difference between the reward obtained from the estimated Q-value function and the maximum reward as the estimation error of the learned model to the optimal Q-value function, which is also consistent with the experiments in [50. 51, 73]. Given that the full test score in the Pong game is 21, we set the test error as the value of (21 test score) in each experiment. The e in e-greedy policy decreases geometrically from 1 to 0.01. We vary the number of samples in the replay buffer from 400 to 2500. Figure shows that the test error is almost linear in 1/ L/VN, which is consistent with our characterization in (20). In addition, experiments with a large N have a shorter error bar indicating more stable learning performance with a large sample complexity as shown in (12).
Convergence with different selections of e. Figure 2 illustrates the convergence rate when E, in the e-greedy policy changes. For each point, en selected as the value in the x-axis, and we decrease ε, geometrically as the iteration increases. Each point is averaged over 5 independent trials. We can see that the convergence rate is a linear function of cg. matching our findings in (19).
Performance with different selections of &. We investigate the effect of e-greedy policy during the training. In Figure 3, we show the test scores using E-greedy policy with (1) geometrically decreasing e from to 0.01, (2) fixed E as 0.1, and (3) fixed e as O. Each test score in the curve is averaged over the past 10 episodes to smooth the trend. One can observe that gradually decreasing

---

0.995
derrssss to 0.01
Test Error in Soore
Rised and)
Converpence nalo
0.934
20
Riaed col)
20
Tearr Score
10
10
0.99
-10
0.988
-20
0.02
0.03
0.04
0.05
0.985
0.02
0.00
0.04
0.05
Episode
100
200
1/v
Figure 3:
Test scores of the
Figure 2: The convergence rate against the number of samples. against the value of Ge.
Figure 1: Test error in scores
cases of e-greedy down to dif- ferent values.
E Ieads to a better score than fixing E to be the final value. The test score of = = 0.1 shares a similar trend to the e-greedy policy but with slower speed, matching our findings in (19) that small leads to a slow convergence rate. The test score of e = O has the fastest convergence rate at the early stage, but the convergent point is the worst and the most unstable, matching our findings in (18) that a small è leads to a reduced radius of convergence.
Conclusions and Discussions
This paper provides the first convergence and sample complexity analysis of the DQN algorithm equipped with e-greedy exploration. We establish the theoretical guarantee for the convergence of the learned model to the optimal Q-value function Q", which can be used to derive the optimal policy. We provide a nearly optimal sample complexity for achieving an arbitrarily small estimation error. We also prove that s-greedy with decreasing & achieves both an enlarged radius of convergence and an improved convergence rate, Future directions include the generalization of the theoretical analysis to the variants of DQNs and the design of efficient exploration strategies for DQNs.
One of the anonymous reviewers raised concerns about (12) regarding its demanding requirements on the initial policy. We would like to clarify that (12) primarily concerns the optimization analysis of the objective function rather than the initial policy. Instead, impose only minor assumption on the initial policy, with no specific environmental constraints. In our work, Co quantifies the initial policy's 's difference from the optimal policy and is independent of (12) in our primary theoretical results. With a sufficiently large replay buffer, Co can approach one, except when it equals 1, indicating an extreme divergence from the optimal policy in all states. Thus, our initial policy assumption is minimal. Considering the highly non-convex nature of deep neural network objective functions with countless local minima. (12) represents the wate-offthe--ee art assumption for optimizing deep neural networks.
As mentioned by the anonymous reviewers, the selections of e, in (17) depends on e, = | Wl which is unknown to the agent. Here, we would like to clarify that e, can be replaced by its upper bound in (19) and lower bound (20). By plugging (19) and (20) into (17), we have
Ce
((vN) (7 + C. (1 (1- (1-7))' (1 Cmaxx)
Cmax
Cmax
maxx
[A] Rmax
1 Cinax
Ce
T T-Coax Cmaxx
(26)
As mentioned by one of the anonymous reviewers, Corollary 3 relies on assumption that depends on the algorithm's trajectory, which lacks mathematical rigor. Here, we would like to clarify that although this equation depends the algorithm's trajectory, it can be easily derived from time- independent equation
(Tw(sla) (sla) T'' (s)aa C W 1l-.2.
(27)
Additionally, it is worth mentioning the difference between (22) in this paper and (2) in [92]. Specif- ically, want to highlight that the equation above, (27), leads to (22). In contrast, (2) in [92]
requires the following condition to hold for for all W1 and W2:
(Tw((sla) - (sla) S C Wzll2
(28)
As comparison, (27) only requires W2 to the ground truth and W, to be some weights near
ground truth. In other words, (27) is sufficient condition for (22). While equation (2) in [92] does not hold with resilon-greedy. (27) can hold with Q-learning using aosilon-greedy. thus ensuring the mathematical rigor of (22).
10

---

Acknowledgment
This work was done when Shuai was a postdoc at Rensselaer Polytechnic Institute (RPI). We thank Dr. Tianyi Chen at RPI for providing remarkable and inspiring insight into the analysis of temporal difference learning. This work was supported by AFOSR FA9550-20-1-0122, ARO W91 0255, NSF 1932196, and the Rensselaer-IBM AI Research Collaboration (http://airc.rpi.ccm part of the IBM AI Horizons Network http://ibm.biz//lHorizoo We thank all anonymous reviewers for their constructive comments.
References
[1] Zeyuan Allen-Zhu and Yuanzhi Li, Feature purification: How adversarial training performs robust deep learning. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 977-988. IEEE, 2022.
[2] Kamyar Azizzadenesheli, Emma Brunskill, and Animashree Anandkumar. Efficient explo- ration through bayesian deep q-networks. In 2018 Information Theory and Applications Work- shop (ITA), pages 1-9, JEEE, 2018.
[3] Ainesh Bakshi, Rajesh Jayaram, and David P Woodruff. Learning two layer rectified neural networks in polynomial time. In Conference on Learning Theory, pages 195-268. PMLR, 2019.
[4] Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference learning theory, pages 1691- 1692. PMLR, 2018
[5] Rajendra Bhatia, Matrix analysis, volume 169, Springer Science & Business Media, 2013.
[6] Steven Bradtke and Andrew G Barto. Linear least- squares algorithms for temporal difference learning. Machine learning, 22(1):33-3555)) 1996.
[7] Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for a convnet with gaussian inputs. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 605-614. JMLR. org, 2017.
[8] Alon Brutzkus and Amir Globerson. An optimization and generalization analysis for max- pooling networks. In Uncertainty in Artificial Intelligence, pages 1650-1660. PMLR, 2021.
[9] Alon Brutzuus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. Sgd learns over- parameterized networks that provably generalize on linearly separable data. In International Conference Learning Representations, 2018.
[10] Qi Cai, Zhuoran Yang, Jason D Lee, and Zhaoran Wang. Neural lemporal-difference learning converges to global optima. Advances Neural Information Processing Systems, 32, 2019.
[11] Yichen Chen, Lihong Li, and Mengdi Wang. Scalable bilinear pi learning using state and action features. In International Conference on Machine Learning, pages 834 843. PMLR, 2018
[12] Yu Fan Chen, Michael Everett, Miao Liu, and Jonathan P How. Socially aware motion planning with deep reinforcement learning. In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 1343-1350 IEEE, 2017.
[13] Zaiwei Chen, Sheng Zhang, Thinh T Doan, Siva Theja Maguluri, and John-Paul Clarke. Per- formance of q-learning with linear function approximation: Stability and finite-time analysis. arXiv preprint arXiv: /905. 11000..1122.... 1425, page 4, 2019.
[14] Girish Chowdhary, Miao Liu, Robert Grande, Thomas Walsh, Jonathan How, and Lawrence Carin. Off-policy reinforcement learning with gaussian processes. IEEE/CAA Journal of Au- tomatica Sinica, 1 13)):277-23,, 2014.
[15] Mohammed Nowaz Rabbani Chowdhury, Shuai Zhang, Meng Wang, Sijia Liu, and Pin- Yu Chen. Patch-level routing in mixture-offexperts is provably sample-efficient for convolutional neural networks. arXiv preprint arXiv:2306 04000, 2023.
[16] Antonio Coronato, Muddasar Naeem, Giuseppe De Pietro, and Giovanni Paragliola. Rein- forcement learning for intelligent healthcare applications: survey. Artificial Intelligence in Medicine, 109:101964 2020.

---

[17] Chris Dann, Yishay Mansour, Mehryar Mohri, Ayush Sekhari, and Karthik Sridharan. Guaran- tees for resilon-greedy reinforcement learning with function approximation. In International Conference Machine Learning, pages 4666-4689 PMLR, 2022.
[18] Kefan Dong, Jian Peng, Yining Wang, and Yuan Zhou. Root-n for learning in markov de- cision processes with function approximation and low bellman rank. In Conference on Learn- ing Theory, pages 1554-1557. PMLR, 2020.
[19] Kefan Dong, Jiaqi Yang, and Tengyu Ma. Provable model- nonlinear bandit and rein- forcement learning: Shelve optimism, embrace virtual curvature. Advances in Neural Infor- mation Processing Systems, 14:26168-26182 2021.
[20] Simon S Du, Jason D Lee, Gaurav Mahajan, and Ruosong Wang. Agnostic q-learning with function approximation in deterministic systems: Near-optimal bounds on approximation er- and sample complexity. Advances in Neural Information Processing Systems, 33:22327-
22337, 2020.
[21] Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably opti- mizes paraametetter neural networks. In International Conference on Learning Repre- sentations, 2018.
[22] Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably op- timizes parrrparameterrzed neural networks. International Conference on Learning Repre- sentations, 2019.
[23] Yaqi Duan, Zeyu Jia, and Mengdi Wang. Minimax-optimal off-policy evaluation with linear function approximation. In International Conference Machine Learning, pages 2701-2709. PMLR, 2020.
[24] Jianqing Fan, Zhaoran Wang, Yuchen Xie, and Zhuoran Yang. A theoretical analysis of deep q-leaming. In Learning for Dynamics and Control, pages 486-489. PMLR, 2020.
[25] Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Ian Osband, Alex Graves, Vlad Mnih, Remi Munos, Demis Hassabis, Olivier Pietquin, et al. Noisy networks for exploration. arXiv preprint arXiv:1706, 100.109900,,995, 2017.
[26] Rong Ge, Jason D. Lee, and Tengyu Ma. Learning one-hidden-llyer neural networks with landscape design. In International Conference on Learning Representations, 2018
[27] Haque Ishfaq, Qiwen Cui, Viet Nguyen, Alex Ayoub, Zhuoran Yang. Zhaoran Wang, Doina Precup, and Lin Yang. Randomized exploration in reinforcement learning with general value function approximation. In International Conference on Machine Learning, pages 4607-4616. PMLR, 2021.
[28] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018
[29] Xiang Ji, Minshuo Chen, Mengdi Wang, and Tuo Zhao Sample complexity of nonparamet- ric off-policy evaluation on low-dimensional manifolds using deep networks. arXiv preprint arXiv:2206. 02887, 2022.
[30] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contextual decision processes with low bellman rank are pac-learnable In International Con- ference on Machine Learning, pages 1704-1713. PMIR, 2017.
[31] Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficiee algorithms. Advances in neural information processing systems, 14:13406-13418 2021.
[32] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference Learning Theory, pages 2137- 2143. PMLR, 2020.
[33] Shusen Jing, Songyang Zhang, and Zhi Ding. Reinforcement learning for robust header com- pression under model uncertainty. arXiv preprint arXiv:2309.13291 2023.
[34] Dmitry Kalashnikov, Alex Irpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Eric Jang, Deirdre Quillen, Ethan Holly, Mrinal Kalakrishnan, Vincent Vanhoucke, et al. Scalable deep reinforcement learning for vision-based robotic manipulation. Conference on Robot Learn- ing, pages 651-673. PMLR, 2018
12

---

[35] Stefani Karp, Ezra Winston, Yuanzhi Li, and Aarti Singh. Local signal adaptivity: Provable feature learning in neural networks beyond kernels. Advances in Neural Information Process- ing Systems, 34:24883 24897, 2021.
[36] Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey.
The International Journal of Robotics Research, (2( 123--1274, 2013.
[37] Petar Kormushev, Sylvain Calinon, and Darwin G Caldwell. Reinforcement learning in robotics: Applications and real-world challenges. Roboties, 2(3):122- 148, 2013.
[38] Michail G Lagoudakis and Ronald Parr. Least-squares policy iteration. The Journal of Machine Learning Research, 4:1 107-1149, 2003.
[39] Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. In International Confer- ence on Learning Representations, 2018.
[40] Lei Lei, Yue Tan, Kan Zheng, Shiwen Liu, Kuan Zhang, and Xuemin Shen. Deep reinforce- ment learning for autonomous internet of things: Model, applications and challenges. IEEE Communications Surveys & Tutorials, 22(3):172--1760, 2020.
[41] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Sample complexity of asyn- chronous q-learning: Sharper analysis and variance reduction. Advances in neural information processing systems, 33:7031-7043, 2020.
[42] Hongkang Li, Meng Wang, Sijia Liu, and Pin-Yo Yu Chen. A theoretical understanding of shal- low vision transformers: Learning, generalization, and sample complexity. In The Eleventh International Conference on Learning Representations, 2023.
[43] Hongkang Li, Meng Wang. Sijia Liu, Pin-Yu Chen, and Jinjun Xiong. Generalization guaran- tee of training graph convolutional networks with graph topology sampling. In International Conference Machine Learning, pages 13014-13051 PMLR, 2022.
[44] Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In Advances in Neural Information Processing Systems, pages 8157-81 8166, 2018
[45] Yuanzhi Li, Tengyu Ma, and Hongyang R Zhang. Learning over ever-parametrized two-layer neural networks beyond ntk. In Conference on learning theory, pages 2613-2682. PMLR, 2020.
[46] Fanghui Liu, Luca Viano, and Volkan Cevher. Understanding deep neural function approxi- mation in reinforcement learning via E-greedy exploration. arXiv preprint arXiv:2209.03776, 2022.
[47] Hamid Maci, Csaba Szepesvári, Shalabh Bhatnagar, and Richard S Sutton. Toward off- policy learning control with function approximation. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pages 719-726, 2010.
[48] Francisco S Melo and M Isabel Ribeiro. Q-learning with linear function approximation. In International Conference on Computational Learning Theory, pages 308-33 322..2.. Springer, 2007.
[49] Mitrophanov. Sensitivity and convergence of uniformly ergodic markov chains. Journal of Applied Probability, 42(4):1003-100 1014, 2005.
[50] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5600 2013.
[51] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 51887540):529-533, 2015.
[52] Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of rein- forcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pages 2010-2020. PMLR, 2020.
[53] Thanh Nguyen-Tang. Sunil Gupta, A Tuan Nguyen, and Svetha Venkatesh. Offline neural contextual bandits: Pessimism, optimization and generalization. International Conference on Learning Representations, 2022.
13

---

[54]
Thanh Nguyen-Tang, Sumil Gupta, Hung Tran-The and Svetha Venkatesh. On sample com- plexity of offline reinforcement learning with deep reLU networks in besov spaces. Transac- lions on Machine Learning Research, 2022.
[55] Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. Advances in neural information processing systems, 29, 2016.
[56] Theodore Perkins and Doina Precup. convergent form of approximate policy iteration, Ad- vances in neural information processing systems, 15, 2002.
[57] Boris T Polyak. Introduction to optimization. New York: Optimization Software, Inc, 1987.
[58] Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of opti- mistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
[59] Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks. In International Conference Machine Learning, pages 4430 4430-4438, 2018.
[60] Wilko Schwarting, Javier Alonso-Mora, and Daniela Rus. Planning and decision-making for autonomous vehicles. Annual Review of Control, Robotics, and Autonomous Systems, 1:187- 210, 2018.
[61] Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforce- ment learning for autonomous driving. arXiv preprint arXiv:1610.03295, 2016.
[62] Zhenmei Shi, Junyi Wei, and Yingyu Liang. A theoretical analysis on feature learning in neural networks: Emergence from inputs and advantage over fixed features. In International Conference on Learning Representations, 2022.
[63] David Silver, Aja Huang. Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Pannecrshelvam, Mare Lanc- tot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
[64] Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the op- timization landscape of over peeapaaraeterizeed shallow neural networks. IEEE Transactions on Information Theory, 65(2):742-769, 2018.
[65] Zhao Song, Ronald E Parr, Xuejun Liao, and Lawrence Carin. Linear feature encoding for reinforcement learning, Advances in neural information processing systems, 29, 2016.
[66] Richard S Sutton and Andrew G Barto. Reinforcement learning; An introduction. MIT press, 2018.
[67] Richard S Sutton, Hamid Maei, and Csaba Szepesvári. convergent o(n) cemporal-differeme algorithm for off-policy learning with linear function approximation. Advances in neural in- formation processing systems, 21, 2008
[68] Taiji Suzuki. Adaptivity of deep reI.U network for learning in besov and mixed smooth besov spaces: optimal rate and curse of dimensionality. In International Conference on Learning Representations, 2019.
[69] Manel Tagorti and Bruno Scherrer. On the rate of convergence and error bounds for Istd (A)- In International Conference on Machine Learning, pages 1521-1529, PMLR, 2015.
[70] Ian Tenney, Patrick Xia, Berlin Chen, Alex Wang, Adam Poliak, R Thomas McCoy, Najoung Kim, Benjamin Van Durme, Samuel R Bowman, Dipanjan Das, et al. What do you learn from context? probing for sentence structure in contextualized word representations. In Interna- tional Conference on Learning Representationss 2018.
[71] William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-29) 1933.
[72] Joel A Tropp. User- friendlr tail bounds for sums of random matrices. Foundations of compu- lational muthematics, I ((4))33944344 2012.
[73] Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q-learning- In Proceedings of the AAAI conference on artificial intelligence, 2016.
[74] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.30277 2010.
14

---

[75] Gang Wang, Georgios B Giannakis, and Jie Chen. Learning relu networks on linearly separable data: Algorithm. optimality, and generalization. IEEE Transactions on Signal Processing, 67(9):235722370, 2019.
[76] Yulong Wang. Haoxin Zhang, and Guangwei Zhang. epso-enn: An efficient pso-based algo- rithm for fine-tuning hyper-parameters of convolutional neural networks. Swarm and Evolu- tinnary Computation, 49:1 14-123, 2019.
[77] Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3):279-222,
1992.
[78] Zixin Wen and Yuanzhi Li. Toward understanding the feature learning process of self- supervised contrastive learning. In International Conference on Machine Learning, pages 11112-11122. PMLR, 2021.
[79] Pan Xu and Quanquan Gu. A finite-time analysis of q-tearning with neural network func- tion approximation. In International Conference on Machine Learning, pages 10555-10565. PMLR, 2020.
[80] Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004. PMLR, 2019.
[81] Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael I Jordan. On function ap- proximation in reinforcement learning: optimism in the face of large state spaces. In Proceed- ings of the 34th International Conference on Neural Information Processing Systems, pages 13903-13916 2020.
[82] Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal provable uniform convergence in of- fline policy evaluation for reinforcement learning. In International Conference on Artificial Intelligence and Statisties, pages 1567-1575. PMLR, 2021.
[83] Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pages 10978-10989, PMLR, 2020.
[84] Shuai Zhang, Meng Wang, Pin-Yo Yu Chen, Sijia Liu, Songtao Lu, and Miao Liu. Joint edge- model sparse learning is provably efficient for graph neural networks. In The Eleventh Inter- national Conference on Learning Representations, 2023.
[85] Shuai Zhang, Meng Wang, Sijia Liu, Pin- Yu Chen, and Jinjun Xiong. Fast learning of graph neural networks with guaranteed generalizability.one www.rooon-dddd--lyeeeeee case. In 2020 International Conference on Machine Learning (ICML), 2020.
[86] Shuai Zhang, Meng Wang, Sijia Liu, Pun-Yu Chen, and Jinjun Xiong. Why lottery ticket wins? theoretical perspective of sample complexity on pruned neural networks. In Thirty- fifth Conference on Neural Information Processing Systems (NeurIPS), 2021.
[87] Shuai Zhang, Meng Wang, Sijia Liu, Pin-Yu Chen, and Jinjun Xiong. How unlabeled data im- prove generalization in telf-training? a one www--hidde-layyee theoretical analysis. In International Conference on Learning Representations, 2022.
[88] Shuai Zhang, Meng Wang, Jinjun Xiong, Sijia Liu, and Pin- Yu Chen. Improved linear vergence of training cnns with generalizability guarantees: A one-hidden-layer case. JEEE Transactions on Neural Networks and Learning Systemx, 2020.
[89] Yuchen Zhang, Jason D. Lee, and Michael I. Jordan. Ll-regularized neural networks are improperly learnable in polynomial time. In Proceedings of The 33rd International Conference on Machine Learning, volume 48, pages 993-1001, 2016.
[90] Kai Zhong, Zhao Song, Prateek Jain, Peter L Bartlett, and Inderjit S Dhillon. Recov- ery guarantees for one-hidden-layer neural networks. In Proceedings of the 34th In- ternational Conference on Machine Searning-Volune 70, pages 4140-4149. JMLR. org, https://axxiv.rr//bb// http//abs/770..000 03150....5,... 2017.
[91] Dongruo Zhou, Jiafan Hc, and Quanquan Gu. Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning, pages 12793-12802. PMLR, 2021.
[92] Shaofeng Zou, Tengyu Xu, and Yingbin Liang. Finite-sample analysis for sarsa with linear function approximation. Advances in neural information processing systems, 32, 2019.
15

---

Supplementary Materials for:
On the Convergence and Sample Complexity Analysis of Deep Q-Network with Epsilon-Greedy Exploration
The structure of the appendix mainly follows the roadmap of the proof described in Section 4.4.
In Appendix A, we define the characterizable population risk function in (31) to approximate the objective function. Also, some notations to simplify the analysis are introduced in Appendix A, and we recommend the readers to refer to Table 3 for the major notations used in the proofs.
In Appendix B, we provide the proof for Lemma and Theorem 1 following the steps as (1) Char- acterization of the local convex region of population risk function (Lemma 2). (2) Characterization of the distance between the population risk function and the objective function (Lemma 3), (3) Characterization of the convergence of two consecutive iterations ((t,m+] and (tt,,), and (4) Mathematical induction over the & and to obtain the error bound between the convergent point (T,0) and the desired point W*
In Appendix C, we provide the preliminary lemmas and the whole proof for Lemma 2, which char- acterizes the local convex region of the non-convex population risk function.
In Appendix D. we provide the preliminary lemmas and the whole proof for Lemma 3, which char- acterizes the difference of 9r and the gradient descent of defined population risk function in (31).
In Appendix E, we provide the proofs for the preliminary lemmas in proving Lemmas and 3.
Before moving to the details, we provide an overview of the techniques in the proofs.
(PI.) The local convex region near W'. To characterize the local convex region, we first bound the Hessian matrix of the defined population risk function in (31) at W Then, we derive the changes in the Hessian matrix when the neuron weights move around the W Specifically, we prove that when neuron weights W are not far away W*, then the Hessian matrix in this region is always positive-definite, indicating that a local convex region near W [90] considers the one- hidden-layer neural network, and the lower bound of the Hessian matrix only holds for Gaussian input. Instead, in this paper, we consider multi-layer cases and need to derive lower bound for the Hessian matrix for all the layers. Instead, the input of the intermediate layer cannot be proved to be Gaussian but belong to sub-Gaussian distribution. Therefore, we built the proof for the lower bound of the Hessian matrix when the input belongs to the sub-Gaussian distribution. Compared with Gaussian input, Sub-Gaussia does not have a closed form of the probability density function. Instead of directly calculating the lower bound, we convert the problem into proving a series of functions are linearly independent over Hilbert space (see Lemma 7 and the proof in Appendix E). Instead of directly calculating the distance of the population risk function in different points, we characterize a Gaussian variable such that the distance over the sub- Gabb-aanni distribution can be upper bounded by the one over the Gaussian variable (see Lemma 6 and the proof in Appendix E).
(P2.) The difference between the gradient and the population risk function. With the local convex region of the population risk function, can characterize the convergence of the population risk function. With Lemma 3, we can prove that the distance between the population risk function and St is small enough, the behaviors of the iterations via 9t can be described by the ones in the population risk function with some additional error terms. Compared with the proof in [90], We need to address the extension from supervised learning settings to Q learning settings and the extension from the one- one-hidden-lee hidden-layer neural networks to the multi-layer neural networks. First, similar to challenges in (P.1), we provide a new concentration bound the two functions for the intermediate layers (see I in the proof of Lemma 3). Second, the distance between the two functions has an additional error term due to the inconsistency the label defined in (31 and (8) (see 22 in the proof of Lemma 3). Third, we need to develop new concentration bound to characterize the error term caused by the distribution shift when training samples are collected by e-greedy policy (see Ig in the proof of Lemma 3).
characterize the distance between
16

---

(P3.) The convergence analysis of Algorithm 1. When the initialization is not far away from W the initialization lies in the local convex region of W for the population risk function. When we have enough samples N and large enough et, we can guarantee that the distance between the ft and the gradient of the population risk function is small enough such that the iterations following Or converges to point nearby W as well. However, if e is too large, the convergent point nearby W can be even worse than the initial point. To avoid this issue, we have an upper bound for selecting Et, and the upper bound decreases as [W(t..) W*|| decreases over Therefore, we build the convergence analysis of Algorithm 1.
A Definitions and Notations
In this section, we implement the details of algorithms described in Algorithm 1, and some important notations are defined simplify the presentation of the proof.
A.1 Definition of the Empirical Risk Function and Its Corresponding Notations
Recall that the goal of Q-learning is to find the Q*-function minimize (6). Therefore, we have
Q' as, r(s.a) + Ba'|a,a max Q* (s), for (s,a) mp"
(29)
Since W is the global minimal to (6), have Q(W*: s,a) r(s, + Egja max (W""''',") d'E
(30)
Therefore, the population risk function is defined as
f(W)- (( (QWW; a.a) r(s,a) 7 la,a Q(W', is's " s',a
(31)
-( (QWW; s, a) s.
where n² is the distribution of the sampled data following the optimal policy n².
The gradient of the (31) is
(w) = (Q(W; r(xr) 7 Egg max
a'EA (*(s'aa') VwQ(W;:)
Q("'; VwQ(W:z). (32)
=Ewep'' of d' (Q(W: xx) -r(x) y max d'EA
As W* is one of the ground truths ((W), i.e., ((W)) achieves the minimum value as f(W*)
0 < (W) for any other W. Given f is smooth function, we have the gradient of f with respect
to any We at the ground truth W* equals to zero, namely.
ve((W*)= V Ww, Vw,"(W") 0,
Vl E [Z]]-
(33)
In addition, without special descriptions, = |a a I ...
k
stands for any unit vector that
in R K, with a₁ R2 (Ko = d). Therefore, we have
K
Oh
v rhh || max / Vehl22 max
awv
j=l
(34)
K
Ōh
2
= la V hal2 max
Tw
A.2 Notations in Algorithm 1
Recall that the gradient in the t-th loop is
9t. WW)
Σ (Q(W:an) - (()) QwQ(W:
D m))
(M)
(35)
N
(Q(W; r((x)) max Q(Wit-1)) 8/, a')) VwQ(W; a'EA
17

---

Then, we define (m) (We; W) as the components of st (m) (W) (W) with respect to W.. Recall that in (4) we have
W [vec Wi)". vec rec(W))",
vec vec(WL.
(36)
Then, with the definition of gt (mm)
(We: W), we have
(m) (W) = L (m)
W)",
9i (m))
(W2; W)
9:
(mm)
W)
(37)
To simplify the analysis, the update of ((.m) is analyzed in the form of
w (1)++ w((.)) 17 9: (m) (We: ((t.m)) + 5 ((W(tmm) w(tm--)), ve E [L].
(38)
One can see that (38) returns the same ((.++l) as the gradient step line 9 in Algorithm
Table 3: Notations for the proofs
9:
(W)
The gradient function at point W in the t-th outer loop, defined in (7).
9: We W)
The gradient function of 9: (W) with respect to the components of W,.
d
Dimension of the feature mappings of the state-action pair (s, a) E x A.
K
Number of neurons in the hidden layer.
L
Number of hidden layers.
W
The desired Weights for approximating the optimal Q function.
(t,.))
Model returned by Algorithm at t-th outer loop and m-tth inner loop.
f
The population risk function defined in (31).
V Wwf(w")
The full gradient of a function f at point W
Ve)(W*)
The gradient of function with respect the components of We point W
(W
The Hessian matrix of a function f with respect to the components of W, at point W*
The dimension of W.
n
The dimension of vectorized We.
(9) (W)
The input to the E-th layer, defined in (39).
Ke
The dimension of (*)
J((W)
function in E. IR defined in (42).
The value of æ in the behavior policy at t-th outer loop.
C.
The distribution shift between the optimal policy and behavior policy iteration t.
N
The size the experience replay buffer.
Rmax
The upper bound of the reward.
A.3 Notations for the Deep Neural Networks.
Let denote the dimension of W defined in (4). We denote ny as the dimension of the vectorized neuron weights in the L-th layer, namely, n, = dim(vec(W.)).
Then, let (0) (W) denote the input in the f-th layer (or the output the (f-1)-th layer) with respect the neuron weights as W. and (1) (s, a), where
h ( (W) = (W,, (WT,n( = = =o [W (W xl]T
(39)
18

---

10 (W) may be shortened as h when the neuron weights are clear from the contexts. Then, we
denote the dimension of (9) as Ke, where
K, if {>1
Ke
(40)
d, if 1-
Then, Q(W; 8, a) can be written as
1 QW 8,0) K ((w
1
(
(41)
K
where ugys denotes the k-th neuron weights in the E-th layer. Then, we define a group of functions Je(W) R RKK such that
[1 d' (1 WT b 1 1=
(W h ((4))
will if e>1
J(W)-
(42)
Then, the gradient of can be represented
aQ
(W) = K Jex((W)
(43)
Owss
where Je,s stands for the k-th component of Tz.
A.4 Notations for Order-wise Analysis
Without loss of generality, consider the case that d >>>>> K. K >> d, order K and in the proof. Let oy (L) denote the i-th largest singular value of W In this paper, consider the case that W7, is will-conditioned and bounded, i.c., 0j (L) and o oo (L) can be viewed as the constant and will be ignored in the analysis. In addition, some constant numbers will be ignored in most steps. In particular, some positive constant C' such that hy (z) 2 (or S.= h2(2)) when 2 E R is sufficiently large.
always switch the
use h2(2) 2 (or (22)) to denote there exists
B Proof of Lemma 1 and Theorem
The main idea in proving Theorem I is to characterize the gradient descent term by the Mean Value Theorem (MVT) in Lemma 4 as shown in (47) and (48). The MVT is not directly applied in ge because it is not smooth. However, the population risk functions defined in (31), which are the expectations over random variables, are smooth. Lemma characterizes the bounds of the Hessian matrix defined in (49). Lemma 3 characterizes the bounds of gradient differences between the population risk function defined in (31) and gi in (7) shown in (60). Furthermore, according to Lemma 3, we know that the distance [[V,f(W) V.f(W*)) | is upper bounded in the order of I - W as shown in (60). Then, we can establish the connection between [|t++,+++) I|2 as shown (59). Then, by mathematical induction over m, one can characterize the iteration of (t.00) 2 as shown in (65), which completes the proof of Lemma 1. Finally, selecting E, based on (68) for all t [T], derive the error bound of [[.00. W* by mathematical induction over t, which completes the proof of Theorem 1.
W and || (t,m) W
Lemma 2. Given any W E TR"", let W satisfy
IW - -- P. OK
(44)
K
for some constant E (0, 1). Then, for the f defined in (31), we have
c1pp (1-c))
ViS(W) -
(45)
K2
K
Lemma 3. Let be the function defined in (31). Let gr be the function defined (7). Then, we have
2 E,
Ke logg
Vef(WW- (We: 2
|| - WW
K
N
(1
=1/2) -7 || - W
+
(46)
K
Rmax
+ Cs (C, + (1 - -C)))
1-
19

---

with probability at least 1 - g Kr
Lemma 4 (Mean Value Theorem), Let c Rdd be open and f : U - Rda be continuously differentiable, and æ E U, h E Rdd vectors such that the line segment + th, 0 S S remains U. Then we have:
(Lo Vf(x +1)di) h.
((x+h) + f(x)) f(x)=
where V f denotes the Jacobian matrix of f.
Proof of Theorem I. Let Wt denote the neuron weights in the E-th layer. From Algorithm and (38), in the s-th iteration and f-th episode, we have
w(tm++)
w "991" (mm) (We; W(t.m)) + (( w((m--1)
= W (((.) -/Ve + 3( (W w(l.m-1)
(47)
+ 7 (V..(W((t..))
Di (m)) (We; w((.)))).
From (31), we can see that W is the global optimal to f because f(W*) achieves the minimum value as O. Therefore, we have Vef((W') = O. Since Vef is a smooth function W from the Mean Value Theorem in Lemma 4, we have
(e.(m)) = =Vef(W
Vef(W")
L Vis (((t)))) u (W((m)) -W*) W (w(lim) W2).
(48)
For notational convenience, H to denote the integration
H
vis (W(tmm) + u. (a.(t..)) w du.
(49)
Then, we have
W(1m+1) W'
- nH 31
Wit.m) W
W((.m) W
I
w(t.m-1) W
(50)
Vef(W((..)) g:
(We: W (t.m))
0
Let SAS" be the eigen-decomposition of H. Then, we define
T
0
S
A
+
3I
3I
A(3)=
A 3
(51)
ST
0
0
TT
I
[ n + 31
31
Since
=
we know A(3) and
share the same
0
S
0
TT
0 I
I
eigenvalues. Let (A) be the i-th eigenvalue of H ( then the corresponding i-th eigenvalue of (51), denoted by (A) satisfies
(1 (1 (1( ( (3) =
(52)
By simple calculation, we have
if 32 (1 v {))
A (8))
(53)
(1 lur + B) + (11 - m7 + 9)2 49
(1-
otherwise.
Specifically, we have
(0) (()
(3), for VB (0, (1 ()))))))).
(54)
20

---

and X ((A) achieves the minimum X(A)= = | -11
V m when 3 -1-- { From Lemma
for any a Rd with ||a||2 1, we have
(W /'" a VVv (((mm)) + u. (W(tm)) - -W*)) a du
s Amax ||au||| lalBdu Amax.
(55)
Vef ) /-" T Vif VVV2f W/(mmm) +u. (Wr(mm) - -W") du
Amin |a Amin.
where Amax ~ 1 R. and Amin k Therefore, we have
(A)
(1-c)) cr)p
(1 (1-cH
K2 and
max
K
1
(56)
Thus, when 7 S 2x
X K, (3+) 1|2 can be bounded by
||A(8*)12 =1 Vn.
A (A)
S
1
(1 C1 mP
(57)
K22
Therefore, we have
(1,++1) Wellz 5 1 (1 cr)np
W
w((m.)) (f.m)
Welle
K2
+ 17 / W (l.m)
ge
(m)
(w(l.)))l
(58)
1 (1
o 2
np
Will
K2
+ 1) VV (t.m))
(m))
( (1mm))]l2
Take the sum of (58) from é to l = L, we have
[((m++1)- S - (1 2)
1p
|| W1
K2
(59)
L + +1
Σ [es[(W((mm)
(m) (m)(((m))))
9i
From Lemma 3, we have
Vef(W()-m) 96 (mm) (We: (t.m)
- E2
K₂ log4
[
W
2
K
N₂
(1
et/2)7
+
||
W*
(60)
Rmax
+ Ca
(Ce + (1- Ct)s)
1-7
For some small constant cx 2 let
1
Kelogg
No < CN np
n K
L V K2'
(61)
which requires
N₂ Z CN p pー1 .] .1 12 max Ke log
2
(62)
= cV² p L log q.
21

---

Then, the sample complexity
T
N =
No
2 N
2
pp- L.d logg T.
(63)
1=1
Therefore, we have
- - W - 1 (2))eN
et
2 TK2
|| -
-
+ vn- (1 11-E,,1 Ex/2)) || - -
(64)
K
Rmax
+ Ca (C, + (1 - C.)e) 1-7
By mathematical induction, when log -1 and 1 = 1/T 1/O(N), we have
W(LM) W*
K²
Rmax +11 - E1/2)7 | W
<V
N Ca
1- 7
CN Ca (C+ (1 - Ct) -e))
Rmax
(65)
1-7 + -11 (1-2//2)7 [ W
K
CN .Cs (Cmax + (1 Cmax) .E.)
Rmax
(1 - E2/2) [ W
K
From Algorithm 1, we know that ((+ = (t,,), To guarantee that iteration converge to the ground truth W*, namely, (++100 W" l2 < (1.0) - W+ we need
6 < (1 7) K |(( W C.
(66)
(1 (1-C))- Ca Rmax
C-
To guarantee that ET 2 0, then we have
Or. Cov-Ca Ca Rmax [ - W 2 (1- K
(67)
Specifically, let
G: K. [[(.0) W C.
E [1 -
(68)
(l-C) C,)-cN .CN Cs Rraxx 1- Ci'
we have
[ W S + -7)- -| - -W 1|,,
(69)
and [T.0) S (++6((1-)) -
|| -1 - W
which completes the proof.
C Proof of Lemma 2
Lemma 2 provides the lower and upper bounds for the eigenvalues of the Hessian matrix of popu- lation risk function in (31). According to Weyl's inequality in Lemma 5, the eigenvalues of (-) at any fixed point W can be bounded in the form of (75). Therefore, we first provide the lower and upper bounds for V at the desired ground truth W Then, the bounds for V at any other point W is bounded through (31) by utilizing the conclusion in Lemma 6. Lemma illustrates the distance between the Hessian matrix of f at W and W Lemma provides the lower bound of
E, [>K1
a.J ow:
8Q (W+))² 2 when æ belongs to sub-Gaussian distribution, which is used in proving
the lower bound of the Hessian matrix in (76).
22

---

Lemma (Weyl's inequality, [51). Let B = A E be a matrix with dimension m x m. Let (B) and (A) be the i-th largest eigenvalues of and A, respectively. Then, we have
Aa(B) (,(A)) E E1 A i [m].
(70)
Lemma 6. Let f(W) be the population risk function defined in (31), If W is close to W such that
W W 12 2 K
(71)
we have
[V((() V 2 K
I
(72)
Lemma 7. Suppose the following assumptions hold:
1. {wyli= E Ke are linear independent,
2. PH (h): RK - 10 1] be the probability density for h such that En Sh/// S to0.
Let K2 be the unit vector defined in (34), have
K CrrTowwl (wrss)) hi) pn(h) dh > O,
/
p: = min ||]||2=1 jm1
(73)
where R C Ke with JR. Jn > O. Moreover, further assuming P is Gaussian distribution and
R = RK, have p > 0.091.
Lemma 8. Let h (W) be the function defined in (39). When W is sufficiently close W*, i.e.
W W ||2 smaller than some positive constant e < 1, we have
(0 (W) z |
(74)
1 (W) - 1 (W*) & W - W* ||0|||2.
Proof of Lemma 2. Let Amax W) and Amin W) denote the largest and smallest eigenvalues of V (W) at point W, respectively. Then, from Lemma 5, have
Amaxx W) S Amax W (W) V2r(W)) 122
(75)
Amin (W) Amin (W*) (W) vif(W*)ll>
Then, provide the lower bound of the Hessian matrix of the population function at W Let P be the distribution for (0) when p4 with probability density function denoted as pa- For any a E K defined in (34) with ||a||2 = 1, we have
TVff(")aa ) |||||==1
min
K a Jen(wi
= K²
EpOP |a||=1
min
E
Σ
j=1
min
Σ
11(0 (1) Tex
PH (h( (h
(76)
K2
[all==1
j=1
min
Σ
a T
10 (wi (1)
( dh
K2
|all==
(k(0)
2V
K2
where the last inequality comes from Lemma 7, and Lemma holds since ( belongs to sub- Gaussian distribution and We is full rank.
23

---

Next, the upper bound of f can be bounded as
max a ViJ(W")a
||a||==1
max Ex ||a|||=1
Σ a
Jeno(wwijh
K2
K Σ
K
max
En
a (0)
Je, h!0) a jo
K ||||||=
12
K
K
Em a 31
T h(0) Texol(w 10)) a Ju h())
K²
J1 1
(a,,, ( ( (1))) Ez (a (d (10)) 1/4
Σ
max
K ||]||=1
$1
12=1
K
K
1/4
Ex (ax, x²
Ex (a. 2))4
max
k2
|||]||=1
K
K
K K
||as lla ||a -
|laj, 12 + +1jaj 11
K²
K2
2
j1=1
j==1
j1=1 j==1
6
K
(77)
Therefore, we have
6
Xmax (*)= = max a T VV/S ;p)a S
(78)
|||||
Then, given (71), we have
2p
W W 112 x
(79)
K
Combining (79) and Lemma 6, we have
112 S
P K2
(80)
Therefore, from (80) and (75), we have
Amax W) S Amax ( + (V ver(W")) )112 - + p <
K 2K K
(81)
Amin W 2 Amin
( -1 - 2
K2
2K 2K2
which completes the proof.
D Proof of Lemma 3
Before illustrating the whole proof, we first introduce some preliminary lemmas and definitions. Lemma 9 is the concentration theorem for independent random matrices. The definitions of the sub-Gaussian and sub-exponential variables are summarized in Definitions 3 and 4, and it is easy to verify that any bounded variables belong sub- Gab-Gaussian distribution. Lemmas 10 and 11 serve as the technical tools in bounding matrix norms under the framework of the confidence interval.
The eтror bound between V/ - gell2 is divided into bounding I, Iz, and Ig shown in (91). I (92) represent the deviation of the mean of several random variables to their expectation, which can be bounded through concentration inequality, i.e, Chernoff bound. 72 in (93) come from the inconsistency "noisy" label (8) and the "ground truth" label the population risk function (31). 13 in (94) come from the data distribution shift defined in Definition 1.
24

---

Lemma 9 (172), Theorem 1.6). Consider a finite sequence [ of independent, random matrices with dimensions d, d2. Assume that such a random matrix satisfies
E(Z+) 0 and
2 S
R
almost surely.
Define
8² = max
Σ
Z
|:
Σ
R 2
Zx)
Then for all t t O, we have
2 ) S (d1 + +2) d2) d2)exp exp
t /2
Prob
Σ Z
52 Rt/3)
Definition (Definition 5.7, [74]). A random variable X is called a sub-Gaussian random variable if it satisfies
(E|XP)) S Sci/p for all p 2 1 and some constant > O. In addition, we have
(82)
RX S "
(83)
for all E R and some constant C2 > O. where || is the sub-Gaussian norm of X defined as || supp21P -11
Moreover, random vector X E Rd belongs to the sub-Gaussian distribution if one-dimensional marginal a is sub-Gaussian for any a E Rd, and the sub-Gaussian norm of is defined as
|
suP/|a]]z=1 ||a Taxx 2X 1z2-
Definition 4 (Definition 5.13, [74]). A random variable X is called sub-exponential random variable if satisfies
(E| I c3p for all p 2 1 and some constant C3 > In addition, we have
(84)
(XxXXX S "
(85)
for 8 S 1/1|X[|lv Ii and some constant C4 > O, where ||x is the sub-exponential norm of X defined as ||X [v, = supp21P (EEX]) (E
Lemma 10 (Lemma 5.2, [74]). Let B(0, 1) E [a||||al22 = 1, E TRyy denote a unit ball in TR. Then, a subset Se is called a E-net of B(0, 1) if every point z E B(0, can be approximated to within& & by some point E B(0, 1), i.e., || all2 S. Then the minimal cardinality of a E-net Se satisfies
Se S (1 + 2
(86)
Lemma (Lemma 5.3, [74]). Let A an dj x d2 matrix, and let Se(d) be a g-net of B(0, 1) in
Rdd for some & E (0, 1). Then
|| S (1 - E)
max a ((5
aa Aa
(87)
Proof of Lemma 3.
From (7), we know that
ge We W)
N
aQ(W: sn, an)
(Q(W; Bn, ax) - yy)
N
iwik
(Q(W: Bm, un) - Q(W* 8n,
:W," an) + max Q(8n, 0; W*)
7 max Q 0; w((00))
aQ(W; 8n, an)
(88)
Owik
Q(W: Sn, an) Q(W Sn,
s. aw))
aQ(W; Sn. an)
Owgg
N
max Q(s,, a; W*) - max Q(8n, a; w(th))) OQ(W: Sny an)
Σ
Swiy
25

---

From (31), we know that
f
(a) (Q(W; s.a") aQ(W;s.a)
(W)
(89)
ow,y
ow,y
Then, from (88) and (89), have
0 @wek
ge Wee: W)-
(W) = ge W) D. (w,, W)
(90)
0f
(e W)
(W),
Owizk
where Dj and 14 equivalent because of Assumption 2. Then, we have go WEWK W)
0f
(W)
OUEER
QQW:: an) QQW": 8nz an)
(Q(W; Sn. ow
Sn. an)
(s (Q(W::;0) ((W":s,))
(Q(W: s,a)
(91)
Owir k
max Q(s,, a; W*) max Q a; (((nn):)())))) aQ( W; 8nz on)
7
Owe,
0s (W).
E
W)
Twiek
For convenience, we define 1, I2, and Is in the following ways with æ,, (Sn, an) be the feature mapping of state-action pair (sn, an). Then, I is defined as
I Σ
- an)
an))
aQ(W: sny an)
(92)
aQ(W:s.a)
E D. (Q(W:s,))-Q(W":.
iw,,
Iy is defined as
L 1 7. max Q(2 W max Q(5 a; w((.)))
aQ(W; Sn, an)
(93)
Owi.
and I3 is defined as
0f
I3 : 91 (Wrn W)
(W),
(94)
where
aQ(W; an)
Te Tesdl hn
(95)
Owi,
from (43). Therefore, we have
g W)
(W)
< I 1|2 + | + 1
(96)
Twer
2
Next, we will provide the bound for ||4 112 ||/2 and |3]|2
Bound of In We first divide the data in D, into two parts, namely, D.,1 and Dt.2. Di,1 includes the state-action pair (s, a) such that o,, is randomly selected from action space A, and Dr.2 includes the state-action pair (s, a) such that o, is selected based on the greedy policy with respect (+W)..)))
26

---

Then, we define random variable Z = (Q(x: W) Q(x; W Je, a
(W) with
a ~ Dt,1 and - = (Q( W) Q( W*)) Tr, a a'h,, h (W) as the realization of z for n = 1,2.... .N. where E R is any fixed unit vector with | S 1. We know that and are independent for a Dr,1. Let Σ denote the covariance matrix of x Dr,1- Moreover, a(, is bounded by 1, then we have Σ 2 I 1.
Similar to ((f.1), we define a random variable Z = (Q(2; W) Q(:; W*)) -r,x- hh (W)
with a D1,2 and Z ((222) for n = 1,2.... N. Differ from Z((,1), $ and a are dependent for x ~ Dt.2. Let Σ₂ denote the covariance matrix of a1,-- Then, have |Ea|| S max, Pzj,a where Pay.a
(Q(zn: - Q W*)) Je, - a a²hh (W) as the realization of
denotes the correlation between a and Z3..
According to the definition of (92), we can rewrite 1 as
N
I
(Q(W;a,)
Q(W (e
K
N
1=
E Eg (Q(W: - Q(W* Te.
Σ (Q(W: ...) - -(.
K
N
nED
Σ (Q(W; ..)) -.."
+
nED
&E D.. (Q(W; Q(W"; Je
(97)
+
8) E) (Q(W; ;
1
1
Σ (Q(W: J..
K2
NN
nED
EEwD.. (Q(W:z) Q(W*: (e.
+(1 e)
(1 E)N Σ (Q(W: QWW); Jen of ( h
nED
Rin (Q(W; (na
Then, for any E N we have
(E) 1/P
E E Dr, 1Q(W::
x) D.e..,
Q(W => |Je, (w (w.xx)) -w la=h 1/p
EewD. (Q( 1Q x) Q(W": =)1" |a 7 h '10) 1/8
(98)
1/2
(BE.D.. | W 1l2 ||0|||
1a 2
SC. | W 1
where C1 is a positive constant.
From Definition 4, know that ( belongs to sub eabbexxonentaal distribution with (
Ci|l W 1|2. Therefore, by Chernoff inequality, we have
N
< s c C(( [|W WWWWWWIW 122)..
-
N
Net
(99)
for some positive constant C' and any R.
27

---

Let t = W
W 22
dlogg N
and & = w. + for some large constant q >> O. Then, we
have
N Σ
d
loga
(100)
N
n
N
with probability at least 1 q d Similar to (98), we have
(12(42)p)) 1/p
C2. |W W* P.
(101)
where C2 = 2- C1. Then, we have
N
220,| - W l2 dlogg
() - (
(102)
N
n=1
with probability at least 9-a
From Lemma 11 and (97), we have
| 2
71) - E2
K2
EN
nED
+ (1-
Σ
()) -)) EZ
(103)
N
nED
2- EE W W* l2
dlogg
K2
N
with probability at least / (d) q a-d.
From Lemma 10, we know that |S (d) S 5 Therefore, the probability for (103) holds least
1 1- (g) -d Because >> 5, we denote the probability as --- for convenience.
Bound of Iz. Let 0 arg max.e. QWW S a). While for Q(W), we have max Q(W; S' a) 2 Q(W:s' aa).
(104)
Then, we have
max Q(W s a) max Q W; 8' a) =QW a.,) max Q(W;: a)
(105)
<Q(W" ; 8/ ax) Q(W; 8 (7)) Similarly to (105), let define a = arg max, Q(W: 8,, a). Then, have
max QWW 8 a) max QWW: 8', a) >Q( S' 8' ;.,) Combining (105) and (106), we have max Q(W"; ; s/,, a) max Q(W: s a)
Q(W; a;)
(106)
< max ((W";sh, a) - Q(W;Q a)
(107)
Following the definition of (t.1) in (98), we define
( (j) max QW"*; 8/ a) max Q(W; a)) (u ax (1))
a
Therefore, from (105) and (106), we know
RF] ())))/) < EEnD, max Q(W*: :/) max Q(W; a)
Jen .1a (1 1/8
(108)
1/2
5 BeND, max Q(W 8/ a) Q(W; 8/ a))" 1 -aaT((00) h(0ppp)))
< (2 8) l W 11 log |A| p.
28

---

Following the steps in (98) to (100), we have
12l12 x
-//2)
(IIW
-
d log q. log |A
+ R.((33)
K
N
2A
(1
E/2)7
W= (V (IIW
d logg q (Vd-logg
log |A|
+ +0)
(109)
K
N
(1 e/2)7
2A
.I W
K
with probability at least 9-d
where the last inequality holds when N 2 d log q log [A].
Bound of Iz. We have
l
0f
- weri W)
(W)
Zweek
= (((W:s.a) ( aQ(W:s.a)
Öwir
-B(aaa ()) - -.(")..) (Q(W;s.a)
dwy,
-ee (Q(W; r(8, - -. max Q(W*; 88 ,')) (Q(W:s,a)
(110)
Owgk
-Eis,a) (Q(W: - r(s, - Ed' max Q ; a')) aQ(W:s,a)
Swer
-Ele.o (Q(W: - -1(8, a) - max Q(W"; (''')) (Q(W;s.a)
Zwy,
-Iss. (Q(W: - r(s, a) max Q(W"; :8: aQ(W:s,0)
Owik
Then, we have
Jaaa /. (a(W: -((,a)) -7 max ((W':'',a)) OQ(W;s.0)
[zl
max
dwe,
(ds, da)ssss - dd)ss a))
QQW s, a) r(8, - - max Q( s'''') (Q(W;s,a)
Owoy
V / (p (ds, da) dd) s 0) (ds, P ss ss)
aQ(W; 8.
Q(W; s. - -((s,)) - - max :s a') --a
(111)
Owi
{(--)) 1/ (ara) / (d'sss, do P(ds' a) (d, ddds
da) + I (aca) I (ut(ds da) (d)ss (d
Renx (1- (1 (ddds, s, - ( (ds, da P (ds'' ss a))
1
+ 1 / / da)dddd))dsssss..oo
da) (ddd
29

---

Then, we have
Ui dda s. wt.(ds.da)P(dd'ss..
( (ssaa /
P (dalsssss
< J(en)) /
(112)
- ((a
+ / Pt.
de) - (daldd (40l
(5.0) S|A| C2.
Therefore, the bound of 13 can be found as
[al - Rmax
|A| ((1 - Cc
(113)
Rmax
-Ca (C. -1-1111011 (1-)))
1-7
where C. = [A].
In conclusion, let E Rkd and aj E Rd with a= [a a², KK
T.
we have
(W):(W) (.((W)llz
a (W) - v(((W))
0f (w)) Zwegk
a (9o W)
0f (W)
ge (e W) Zwack
||00s
(114)
K
<1 + ||22122 + [al12) ||au|12
k=1
2-8
d dlogg
I W 12 +
(1 (1-8) e/2)7
(
W'
V
K
N
K
Rmax
+ Ca (C, + (1 Ct)E)
1-7
with probability at least q-d
E
Additional proof of the lemmas in Appendix C
E.1 Proof of Lemma 6
The distance of the second order derivatives of the population risk function f(-) point W and W can be converted into bounding P,, Pg. which are defined in (116). The major idea in proving P; is to connect the error bound to the angle between W and W* given ( belongs to the sub-Gaussian distribution.
Proof of Lemma 6. From the definition of f in (31), we have
8f Own, Owri,2
1 Em Jr (wo h) Jen (w)) (TTT)) h) hT
(W*)
K2
(115)
82
and
(W)
End Te (uT h) Ti h) hh. T
Fwi Owi.jj
k2
30

---

where h = (W) and ht (W*).
Then, we have
(W*) 83 (W)
Swe, Owee
Ji Jn
Een Tineh (wijs ht J (w +T h hh"h" JI (w Jt Jeddd hihh"
K2
Ex [T (wi ht (T (w h hh Jend' Cend'wE (whss
K2
Te (w h)) (T ( hih'' (exd((w), h)hh
(1 P2).
K2
(116)
For any a E Kr with |allz = 1, we have
a' Pla PPaa-- -aa=B H''wws h²)
h² (a hr)² ha Jend' h)(a h)²). ())a)
(117)
Then, we have la Pia|
Ex Ti (w))) h²) Ti ( h (a - Jend (w h) h)))))))))))))))))))))
Ex
h² (a h2 Jed'(w n)(aa
h²)² Jidd(w (a h)?
+ E. Th
(a h)² Je, (w) (a h)²
(118)
+ Ex Je,do (w) T (a h)² Je, Jexo ha h))²
W W1 + W - W/
+ Ex (d'(w) h) Ø [w T Jo h)) (a h)²
W W + Exe (d'(wi h) o' (wi h)) (a hn)
Utilizing the Gram-Schmin process, we can demonstrate the existence of a set of normalized or- thonormal vectors denoted as B = {a, b, c, a..... ag} E Rd. This set forms an orthogonal and normalized basis for Rd, wherein the subspace spanned by a, b, includes We,z. and wi,a"" Then, for any Rdd we have a unique = [21, 22, 2d] T such that
h= 21a + 22 + 230
z2az.
Because (i) a, We,j and wien belongs to the subspace spanned by vectors fa, b. and (ii)
af.' ". a are orthogonal to a, b, and c. Then, we know that
w = (zia= + b2 + 23C +
.... ................ 22a
=2 a =2 b+ 2 c+ ......... za ad
=2:w a 22 b 2z c c+0
(119)
= (zza
a b 23c)
w f.j2
where h = =1== b2 + 23c. Similar to (119), we have w h w h and a h a Th.
Then, we define I4 as
4 = F,, (0' (Wi h) 2'(wT, hi) (a (aTh)
10' (W h) 6 (w h) |a h12 fnr (h)dh
(120)
Rn
(d(wTy & ('(wif.1 h))
la h12 fz(z)) (Jn (z)
31

---

where [Ja(2)] is the determinant of the Jacobian matrix 0h Since is a representation of h based on an orthogonal and normalized basis, we have [2)(2]] 1. According to (119), I4 can be rewritten as
11 / 16' 1'(we, h) o (w h)l |a h12 fz(z)dz
(121)
( h) o' (w h) |a h| fz(=1, #2, 23 25)dzıd22das
R.
where in the last equality we abuse fz 22, 23) to represent the probability density function of (21, 22, 23) defined in region R.,
Next, we show that is rotational invariant over R. Let R [a b c agl we have h Rz. For any (1)) and 22) with ||= || ||2. We define (1) Rz(1) and h2) = Rz Since is rotational invariant and ||2 | | ||2 || ||,, then we know h( and
(2) has the same distribution density. Then, 211) and (2)) has the same distribution density as well. Therefore, z is rotational invariant over R...
Then, Rsin sin@2, 23 = R.siiiicssse cosØ2. Hence, we have
consider spherical coordinates with
21
RcosØ1, 22
(d' (h) o' (wi h)l cos $11² fz Φ1, 02) Re sin 01 dRdø (122)
Since is rotational invariant, we have that
f2 $1, (22) = (2(
(123)
Then, we have
1 ( (h/R)) - (w (T/R))] Recos 2212 (2()) sin Rid
(2((R) (1(R)
Rd ((R)dR
cos 2212. sin d1
(124)
1 (h/R)) - o (wi T
12 (h/ R)) dd
dáp d0p2
</. ( [ I 2m
si 10' (wis o' o'(wiJ. (dp dóo,
where the first equality holds because @ (w. h) only depends on the direction of h, and h/R- R = (cos Φ1, sin @1 sin sin Φ1 cos Φ2) in the last inequality.
g²
Because z belongs the sub- Gaussian distribution, we have F2(R) 2 1-2e = for some constant > 0. Then, the integration of R can be represented as
f²)2 =
RC(1 F2(R))
0
S
AR²(1 F=(R))
8R ER
(125)
32
_2 Reee
# dR
V2T
-300
R²
1
e B2
dR,
V2T0²
where the last inequality comes from the calculation that
2Re
R²
"2 dR = 3
(126)
82 2R E o
dR = 40
32

---

Then, we define I E R belongs to Gaussian distribution as ã ~ ~~N(0,,02 02) Therefore, we have
14 s 3202
10 R2
1
82
dR
/-
2m
sin
(0((w,,,)) o' (' x) 3) iddiddd
V
50
(127)
=320² E.,,,
0 W1 [w2,22
Φ [
Ex (' σ) Ø (w) TT
where Eे belongs to Gaussian distribution.
Therefore, the inequality bound over sub-Gaussian distribution is bounded by the Gaussian distribution. In the following contexts, we provide the upper bound of Ex oe (w σ)
o' d'(wi.] (1)))))) |.
Define set A1 = signs, which means the value of o' d'(w )) and ('w T x) are different. This equivalent to say that
)) 0}. If e A1, then w x. and wt x have different
10' (o(w[,, ②) 6 ((wi
{
{
if A 0, if E A
(128)
Moreover, if @ A1, then we have
W J22
w
x S | - we.izll2 1|
(129)
Let us define set A2 such that
120 2.j
|100 - -eesall2 l12)
A
1120
1| ||202,2211
2
|102 1l2
(130)
/ we.
Oz
cos az wi.
/w ll2
Hence, we have that
Ezlø' (o? 3)
2'
(()))))) 22 =Eg p((w,jj 3)
0' ('wwt x)]
-Prob @ A1)
(131)
<Prob E E Az).
Since ãे (|0)11) 0z 0 belongs to the uniform distribution on [- T). we have
| ||
W2.jz lla | 10 l1a
arccos
||00 We
Prob(T E A2)
lan(T arccos
|| ||10 j.
cot (arecos ||
we
We 112
/e 112
(132)
|w
we.i l|2
| 112
W;
Well2
Hence, (124) and (132) suggest that
L S W; W 1| ||a| 2-
(133)
and
P [ < W
W* || la w W
The same bound that is shown in (133) holds for Pa well.
33

---

Therefore, we have
((lW"-vV((W)))) = max
a T
- - a
a 251
K
K
Pi P2l12 || 212 ||0y/112
K
K
K
W - W 122 || 11211
(134)
J= 121
K
a
+
| 11
Σ
Σ
W W
2
カ==رر==1
W
12
K
where a R Kd and a, Ke with a |aj, a....... ,
E.2 Proof of Lemma 7
We aim to prove that JR. (E/=1 a ho' (w PH (h) dh is strictly greater than zero for any a. Therefore, the p in (2) strictly greater than zero. The proof inspired by Theorem 3.1 in [22]. It is obviously that (E a ho hi) is greater or equal to T
zero. Given (Ej= a T ho' ho' hi) is continuous, we only need to show that a such that Σ a he' [ h) # O for any a, namely, [ho'(w] (h))
linear independent. Com- pared with Theorem 3.1 in [22], we need to address two challenges: (1) the neuron weights is the random variable in [22] while the input h is the random variable in this paper and (2) the random variable belongs Gaussian distribution in [22] while the random variable belongs to uub-Gaussian distribution in this paper.
Proof of Lemma 7. Let H. be a Hilbert space on R and the inner product of H is defined as
(f.)) - s(h) g(h)Sn(h) dh, Vf.g H,
(135)
where the Lebesgue measure of R over Re is non-zero. Instead of directly proving 2 TT ho'(w] h)) In (h) dh for any a, we note that it is sufficient to prove that
SR Ek= a (ho'(w) h)] are linear independent over the Hilbert space H. Namely, if (ho'(w) h) h)] are linear independent, we have
a ho' Tho' hoo h) f almost everywhere.
(136)
Therefore, know that JR Ex a ho ho (wT PH (h) dh is strictly greater than
Next, we provide the whole proof for that keσ'(w) h) b)]k are linear independent over the Hilbert space H.
We define a group of functions (w))))} where w (h) he' he h). From the assumption in Lemma 7, we can justify that EE |1, (2) < En-D //|2 < co.
Let X; {h w. h 0} for any i E [K]. For any fixed k. we can justify that X's cannot be covered by other sets {&& figk as long ww does not parallel to any other weights wy with j & k. Namely, X's & Ug The idea of proving the claim above that the intersection of X; and X; is only a hyperplane in Xz. The union of finite many hyperplanes is not even a measurable space and thus cannot cover the original space. Formally, we provide the formal proof for this claim as follows.
34

---

Let be the Lebesgue measure on Xs. then A(H2) O. When y does not parallel to wk, N4 0 X only hyperplane X₂ for * k. Hence, we have X(X, n X3)) = 0. Next, we have
1 n (U)SA
- Σ j
A n n22) = 0.
(137)
Therefore, have
1(Xx/ ((X (+)+)))))))))))))))))())))))())) X(Hx)) X n (U)++ {(X(s) >
(138)
Therefore, we have / (UjjA is not empty, which means that 24. & Uzz Next, Since Xx Xz/(U)x12)) is not an empty set, there exists a point E Xx/ (4/(() and ro >> 0 such that
((z D2= = 0 with Vr S ro and j + k, where B(zk. r) stands for ball centered at z4 with a radius of r. Then, we divide B(zk. r)) into two disjoint subsets such that
(139)
B B(z,, r) n (h) w h > 0},
(140)
B, B(za, r) (h) w h < 0}.
Because is a boundary point of (h|wy h = 0}, both 1, and B, are non-empty. Note that 15y(h (h) is continuous at any point except for the ones in X,. Then, for any # k, know
that by (w h) is continuous at point 23 since z & Xy. Hence, it is easy to verify that
lim 1 + A(B,)) 187
the (h)dh
lim r-0 A(B,) J (x(h)dh c/((=
(141)
While for s/. we know that s/e (h) = 0 for h E B7, (ii) sha (h) = h for h E B Hence, it is easy to verify that
/
lim
A(B,1) So.
(x) 2
(142)
lim 00
(h(h)dhh = O.
X(Br)
B Now let us proof that (w))) are linear independent by contradiction. Suppose ( are linear dependent, we have
(h) =0, 0, vh.
(143)
Then, we have
K (n)y( =
1
lim
-00
X(B,t)
1,
j=1
(144)
K
lim
Σ
r-
A(Br)) J
j=1
Then, we have
K
0 = lim r-0 X(B
Σ
lim
Σ j=1
B
j=1
T-0 A(B,) B.
(145)
-0
where the last equality comes from (141) and (142).
Note that 25 cannot be because 2g X,- Therefore, have ag 0. Similarly (145), we can obtain that ai- 0 by define 2, following the definition of 2μ for any j E [K]. Then, we know
that (143) holds if and only if a O, which contradicts the assumption that (35 ) are linear dependent.
In conclusion, we
know that {
are
linear
independent, and
fr [ a (ho'(w PH (H(h) dh is strictly greater than zero
35

---

E.3
Proof of Lemma 8
Proof of Lemma 8. From the definition of (39), we have
(W) - 10 (W
(W)) (WWiI
=1lo( 1h - -WWa-n
@W 8-1 (1-1) (()) o(W2 ((
(146)
1 (W, (( (W)) - -o
+ 11
(w (W)))(((W))))) h (t- (W
W W2-1le 1 (W(())(()) (W)ll
With the assumption in the Lemma such that W is close enough to W', we have
|| W - Wf + W, 2
(147)
Therefore, we have
① (W) 12 S Wi [| ||ا| 2 |0||
(148)
Then, we have
11 (W) - 10 (W*) (W")I ll
We-1 Wi-1ll | 1| |1 (w)) - h1t h-"-))(""Il
W. Wil | + ( (W) - (W
(149)
W. W 1/2122222 + ||c x:
W. W (1((-1)(
W W 12 |
which completes the proof.
F Additional experiments
In this section, we provide numerical justification that our theoretical findings are aligned with DDQN through the Atari Breakout game The neural network follows the same architecture as the one used in Section 5. The algorithm terminates if the average score over the recent 100 episodes does not improve or the algorithm reaches the maximum episode set 200, which is around 4 x 10 training steps. The testing score is calculated based on a similar setup as the training process by fixing the maximum memory size N as 2000 and greedy policy, i.e., O. Each point in the plot is averaged over 10 experiments with an error bar representing the standard deviation.
Estimation errors with respect to the sample complexity N. We follow the setup in Section use the expected cumulative reward as the estimation error of the learned model the optimal Q-value function. The & in e-greedy policy decreases geometrically from to 0.01. We vary the number of samples in the replay buffer from 3000 to 10000. Figure 4 shows that the test emror is al- most linear in 1/ //, which is consistent with our characterization in (20). addition, experiments with a large N have a shorter error bar indicating a more stable learning performance with a large sample complexity as shown in (12).
Convergence with different selections e. Figure illustrates the convergence rate when e; the e-greedy policy changes. For each point, ég is selected as the value in the x-axis, and we decrease & geometrically as the iteration increases. Each point is averaged over 10 independent trials. We can see that the convergence rate is a linear function of c., matching our findings in (19).
36

---

16
0.986
15.5
Convergence rate
0.984
Score
15
0.982
14.5
0.98
0.978
13.5
0.976
0.01
0.012
0.014
0.016
0.018
0.02
0.01
0.02
0.03
0.04
0.05
1/vN
Ce
Figure 4: Test error scores against the number of samples.
Figure 5: The convergence rate against the value
of Cg.
G Extension to non i.i.d. samples
Assumption 3. At any fixed outer iteration the behavior policy n. and transition kernel Pt satisfy
sup drv (P(s, E.) s), Pi) S Av", Yr
(150)
#ES
for some constant À > O and v E (0,1), where drv denotes the total-variation distance between the probability measures.
Assumption assumes the Markov chain { induced by the behavior policy, i.e., e--gred policy 1-th outer loop, is uniformly ergodic with the corresponding invariant measure Pa. Compared with i.i.d. cases, we need to handle an additional error term when bounding the distance between the Ii and f as shown in (91). Therefore, the upper bound in Lemma 3 changes, which suggests an additional term in the final bound.
We present the major theoretical findings for non-i.i.d samples in Theorem 2. The major proofs in this context follow similar steps to the proof of Theorem 1, with slight changes in the error bound between the sequences gr and f. In this section, we omit the details of the proof for Theorem but provide the proof for Lemma under the assumptions outlined Assumption 2 to simplify the presentation.
Theorem 2 (Convergence for non-i.i.d. case). Suppose Assumption I and (143) hold, the buffer size N satisfies (13). Let us define Cuax a constant that larger than C2 for S T and Ca A| + log, X-1 + ) when satisfy
Ce O(VN). Ct
Cmax
(151)
(1 Cmax) Ca Rmax
- Cmax
for a fixed constant E (0, (1 - ?), and the initialization satisfies
| (0.0) - W < 0(1 O(vN)
1- p. [
(152)
K
Then, with the high probability of least 1 qd, we have (C1) The learned weights decay geometrically with
(2 RMaxx
(++100)) W + ( W +
(153)
(1 (1-))0(N))
(C2) the returned model Q(V(T.0)) exhibits an estimation error as
Cinx Ca Ruux
+ R + (1 (1 -T)
T*
sup QT(((:))) -Q1 (1 (1-7)2. C (x,a)
(154)
where 7" = min(t (t] Av < 1/ T)}
37

---

Proof of Lemma 3 under Assumption 2. Recall that in (91), we have
0f
ge(We, W)
(W)
dwir
QQ(W:sns - Q an))
aQ(W; sn, an)
Swy
Bi (Q(Wis,a) Q( aQ ; 8, a)
@wick
(155)
N
(Q(W;
(W; ; 8n; an)
max Q(sn; a; W*) - max ((sn, a; W((.))
N ==1
0ʃ (W)
(t W)
Owik
E(a.a)DD,, P (er, W) PD W)]
:=/ 11 + 1/2 + 13 + 1..
Bound of I and 1z. Compared with (91), the upper bound for I and I2 is the same those shown in (103) and (109), respectively.
Bound of I3. Following (111), the upper bound of Ia can characterized as
[ l _ Rmax
/. (1--))
I/
(ds,,, (ds, da) da) a) Ma,1 (ds, ddds (s)dss)(s))))))))))))))))))
1-
(156)
+ + I da) ((d)'(sss)) (d2 (adsss
and
Meann (n' (de, -
- (d. (dd
(157)
{ ((0.0) / (d*(ds) - (ds, (daas)
+ (e.0) / (r. (da x" (dal s(ds'(s,a) ((dss)
From Theorem 3.1 in [49], we know that
I (s.aa)
(P*(ds) - Pt, (ds)) < |A[(log, --1 + - Cr
(158)
and
(dal T" (dalds) SCC.
Therefore, the bound of I3 can be found as
Rmax
|all2 < 1-7 |A| . ((1 (11-)Ca++ =E. (1 + log, --1 + 1-v
(159)
Rmax
=Ca- (Ci+ (1 (1- 1-7"
Ca= where Ca = |AA - log, X-1 -
Bound of 44. I4 is the bias of the data because the data (s, a) at iteration depends on the neural network parameters W. Let us define Gt as
De (e W) EP,P ( W)
(160)
and
A, ge(WERk W) ge (wwE W).
(161)
38

---

It is easy to verify that
( W) ge W) (1+ | W..
( W)
De (wee W - (1+7)
W W
(162)
Rmax
and
11 x 1 1-7
Then, have
A.(W) (W+) I W
(163)
Therefore, have
(W((00) = (W(((-)0))
+ 1 i=(-
1+7
Rmax
(164)
Then, we need to bound 6, (W((.))))
Let us define the observed tuple Os(s, a, 8') as the collection of the state, action, and the next state the f-th outer loop. Note that
((+ St- 8: O2
(165)
forms Markov chain introduced by the policy Te-T-
Let (tt-7.0) and O be independently drawn from the marginal distributions of (t-rr.0) and O., respectively.
With Lemma 9 in [4], we have
E (W((LT)))) O.) EA (W(T..))))) Õ.) 2sup (W, A. w,O
(166)
By definition, we have A. (t-T0) 0), Õ.) = and
2 Rmmx
AA(W, 1 1-7
(167)
Therefore, we have
t-1
EA. (W(L)) (W +
1+
Rmax
1-? 1=
(168)
Rmax -- (Λ.1² + (1 T T/--))
where the last inequality comes from the fact that the step size T) is non-increasing.
Choose T" min (t 0, 0, Av= I <. When < T", we choose т = and have
Rmax
EA, (w.))) < I-
T 770-
(169)
When n², we can choose and obtain
EA. (W. < Rmax
+ (1+7)7* -
(170)
Combining (169) and (170), have
Rmax (1 (1+7) 7maxx (U,
144 <
(171)
where r' = minft dv S m.
L
39


Reviews:
[{"review_id": "q18tpAaHhM", "reviewer": "Reviewer_2co6", "summary": "This paper analyzes the sample complexity of using $\\epsilon$-greedy for exploration in the setting of general function approximation.", "questions": "1. The definition of Theta in Equation 12 is not found in the main text.\n\n2. Why is the requirement of the initial point in Equation 18 become higher as \\rho grows bigger? What is the intuition behind this phenomenon?", "limitations": "See 'Weakness' Session", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This paper provides an convergence analysis of using $\\epsilon$-greedy in Q-learning.", "weaknesses": "In my opinion, this paper is studying optimization rather than sample complexity. Equation (18) is saying that the initial Q value is accurate. However, in the research of sample complexity, we are concerning that how to explore the environment even when the initial policy is nothing and we know nothing about the environment. Here we have a good initial point, which weaken the need of exploration.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "***Q1**: In my opinion, this paper is studying optimization rather than sample complexity.*\n\n**A1**: Thank you for sharing your thoughts. Your input is greatly appreciated. We find that the concept of \"sample complexity\" lacks a precise definition within the RL literature. To make a fair comparison with established practices, e.g., [74], [23], we follow the existing work to define our \"sample complexity\" as the number of samples needed to attain a specific accuracy, which has been studied in our manuscript. We recognize the importance of clarity in our terminology, and we intend to enhance the clarity of the \"sample complexity\" definition in our revised paper.\n\n***Q2**:  Regarding initialization assumption as shown in Equation (18).*\n\n**A2**: Thanks for your insightful and constructive question. To provide a clear understanding, we would like to clarify that equation (18) does not assert the accuracy of the initial Q value, and such an assumption regarding initialization aligns with the state-of-the-art practice in the theoretical analysis of DQNs.\n\n**Firstly, (18) is not equivalent to assuming the accuracy of the initial Q value.** Equation (18) presumes an initialization near the ground truth within the range of $1/K$. Meanwhile, the resulting neuron weights by Algorithm 1 have an estimation error in the order of $1/\\sqrt{N_s}$, with the potential to become considerably smaller than $1/K$ provided that the value of $N_s$ surpasses $K^2$ as shown in (21). This indicates a substantial enhancement over the initial assumption.\n\n**Secondly, our initialization assumption in (18) is the state-of-the-art practice in DQNs.** Due to the significant convexity of the DQN learning problem, existing DQN results with non-linear activations require various initialization or objective function landscape assumptions to prove convergence, as seen in (i) two-layer assumptions for characterizable Eluder dimension in [18, 17, 29, 53], (ii) the achievability assumption of global optimal in [23, 28, 41, 49], and (iii) the assumption of a good initialization near the ground truth in [10, 19, 48, 74, 76]. These assumptions do not hinder the valuable insights these papers offer. As mentioned in [R1] and [R2], analyzing non-linear neural networks is complex due to the highly non-convex optimization problem with numerous spurious local minima. This complexity prevents tracking iterations without any assumptions on the initialization or landscape of the objective function. Consider [74] and [23] as examples. [74] confines initial points within a radius of $K^{-1/2}L^{-9/4}$ (based on numbers of hidden neurons $K$ and layers $L$) near a good point (nearly as good as the ground truth $W^*$) for $1/\\sqrt{T}$ convergence. In our work, we assume initialization near the ground truth with radius $1/K$, similar to [74] when $K$ is at the $L^4$ order. Notably, [R3] uses a 5-layer network with 512 hidden neurons, which satisfies $K\\sim L^4$. Moreover, [23] directly assumes global optimum is attainable. In contrast, we detail how mini-batch stochastic gradient descent secures convergence systematically by characterizing the initialization region, providing a deeper understanding.\n\n**Thirdly, we would like to emphasize that our theoretical analysis informs the practice of DQNs.** Our manuscript (Section 5 and Appendix F in the supplementary) presents enlightening empirical findings that are obtained based on real-data experiments using the DQN algorithm with random initialization. We showed that these empirical insights are aligned with the theoretical analyses built upon the initialization assumption. Moreover, it is noteworthy that within the NTK framework for supervised learning using neural networks [R4, R5], a good convergence point—almost as good as the ground truth—is consistently found near random initializations. We believe this observation underscores the practical validation of equation (18).\n\n\n[R1] Liang, Shiyu, et al. \"Understanding the loss surface of neural networks for binary classification.\" ICML, 2018.\n\n[R2] Safran, Itay, et al. ''Spurious local minima are common in two-layer relu neural networks.'' ICML, 2018.\n\n[R3] Mnih, Volodymyr, et al. \"Playing atari with deep reinforcement learning.\" arXiv preprint arXiv:1312.5602 (2013).\n \n[R4] Allen-Zhu, et al. \"Learning and generalization in overparameterized neural networks, going beyond two layers.\" NeurIPS, 2019.\n\n[R5] Arora, Sanjeev, et al. \"Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks.\" In ICML, 2019.\n\n\n***Q3** : The definition of Theta in Equation 12 is not found in the main text.*\n\n**A3**: We apologize for the lack of clarity in the notation. To clarify the notation, we use $\\Theta$ to denote the order of a function. Specifically, if $f(N) = \\Theta(g(N))$, it means there exist constants $C_1$ and $C_2$ such that $C_1 g(N) \\leq f(N) \\leq C_2 g(N)$. \n\nReturning to Equation 12, we can interpret it as follows: there exist some constants $c_1, c_2, C_1, C_2$ such that $1-\\frac{1-c_1\\cdot \\epsilon_t}{ \\sqrt{c_2\\cdot N}}$ $\\le 1-\\frac{1-\\Theta(\\epsilon_t)}{\\Theta(\\sqrt{N})}$ $\\le 1-\\frac{1-C_1\\cdot \\epsilon_t}{\\sqrt{C_2\\cdot N}}$.\n\n***Q4**: Regarding $\\rho$ in (18).*\n\n**A4**: We apologize for the confusion caused by the typo in (18). The correct expression should have $\\rho$ in the numerator instead of the denominator, as $e_t:=||W^{(t,0)}-W^\\star||\\_F\\le\\mathcal{O}\\Big(1-\\frac{1-\\Theta(\\epsilon_t)}{\\Theta(\\sqrt{N})}\\Big)\\cdot \\frac{\\rho\\cdot ||W^\\star||\\_F}{K}$. As a result, the requirement for the initial point becomes *more relaxed* as $\\rho$ increases in magnitude. \n\nTo clarify, $\\rho$ corresponds with the smallest eigenvalue of the Hessian matrix of the objective function in (6), which also affect the radius of the local convex region of the objective function. When we have a larger $\\rho$, we have a larger region of the local convex region, resulting in a more relaxed requirement for the initial point."}, {"review_id": "ccadyCHzmz", "reviewer": "Reviewer_KLjC", "summary": "This paper provides a theoretical analysis of the converge of DQN in deep reinforcement learning. Its contributions are mostly theoretical and concern the important setting of epsilon-greedy exploration DQN with general function approximation. The paper includes convergence and sample complexity analysis for DQN as well as bounds for varying the exploration epsilon. Its results extend prior work with more restrictive assumptions (e.g. no epsilon greedy exploration in Xu and Gu, 2020).", "questions": "Question to authors: It is not immediately obvious to me which strong intuitions we should have about the Holder exponent of quantity C_t that intervenes in Corollary 3, or if we could attempt to measure a pathwise estimate empirically. Could we detail this point further, perhaps in supplementary ?", "limitations": " ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The paper is well written and clear. The main strength of the paper is that as far as we know, this is the first theoretical work to tackle convergence of the Bellman error under both neural approximation and epsilon greedy exploration, without overly restrictive assumptions (two-layer networks etc). We appreciated for instance the fact that even as the epsilon exploration bounds are somewhat loose (as shown in empirical sections), they qualitatively explain crucial phenomena known to RL practitioners such as the necessity to anneal the exploration epsilon. The clarity of exposition also contrasts with the technicity of proofs (e.g. using tools from sub-Gaussian concentration of measure). Overall we find the theoretical contribution to be valuable and significant.", "weaknesses": "As far as weaknesses go, there are minor orthographic typos that remain in the main text, and should be addressed in second reading. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer's comprehensive reading of this paper and valuable suggestions. The point-to-point responses will be posted based on the reviewer’s questions.  \n\n***Q1**: As far as weaknesses go, there are minor orthographic typos that remain in the main text, and should be addressed in the second reading.*\n\n**A1**: Thank you for your valuable feedback. We appreciate your keen observation regarding the minor orthographic typos in the main text. We have diligently addressed the issues in the revised paper at our best (with some examples listed below), and we will be committed to ensuring that the revised manuscripts meet the highest standards of quality.\n\n* “A small positive constant with linearly dependence on $\\epsilon_t$” —>“A small positive constant with a linear dependence on $\\epsilon_t$”.\n\n* “denote the the minimum distance of” —> “denote the minimum distance of”.\n\n* “Guassian” —> “Gaussian”\n\n* “bellman function” —>”Bellman function”\n\n* “such as e.g., Gaussian distribution” —>”e.g., Gaussian distribution”\n\n***Q2**: Question to authors: It is not immediately obvious to me which strong intuitions we should have about the Holder exponent of quantity C_t that intervenes in Corollary 3, or if we could attempt to measure a pathwise estimate empirically. Could we detail this point further, perhaps in supplementary?*\n\n**A2**: Thank you for your thought-provoking inquiries! Corollary 3 can be interpreted as \n\n$$|C_t - C^\\star | \\le |W^{(t,0)} - W^\\star |_2^\\alpha,$$ \n\nwhere $C^\\star=0$. While directly calculating the Holder exponent isn't feasible due to the unknown value of $C^\\star$, we can estimate this exponent by identifying an appropriate $\\alpha$ that satisfies the following inequality:\n\n$$ |C_j-C_i| \\le C \\cdot \\|W^{(j)} - W^{(i)} \\|_2^\\alpha.$$ \n\nThis estimation involves selecting some random pairs of points $W^{(i)}$ and $W^{(j)}$. Should we identify a constant $C$ and an $\\alpha$ that ensures the equation holds true for any combination of $W^{(j)}$ and $W^{(i)}$, it would consequently establish the validity of the same $\\alpha$ for Corollary 3. We are fully committed to providing a detailed implementation of this process in the supplementary materials, further solidifying our theoretical findings.\n"}, {"review_id": "CaSMmXNjau", "reviewer": "Reviewer_5oZJ", "summary": "The paper studies non-asymptotic behavior of deep Q-network where the inner loop uses momentum and the behavior policy is time-varying epsilon greedy policy. With nice choice of initialization and exploring strategy $\\epsilon_t$, the authors prove that the DQN algorithm enjoys $1/\\sqrt{N}$ sample complexity.\n\nThe analysis of inner loop iteration follows the spirit of bounding the error between the gradient of population risk function and its estimation, with a novel lower bound on the Hessian of population risk function.", "questions": "1. Please give reference or more explanation for the definition of local convex region in equation (11). It looks like norm, but what does it have to do with convexity? Why do we need to care about its lower bound?\n\n2. To prove local convexity of $f(W)$ around $W^*$, the lower bound on the hessian of $f(W)$, Lemma 6 plays a key role, but I think the details are quite omitted. The coordinate transform to bound $I_4$ from line 856~861 is not really intuitive. Is this a standard techinque or have been used in other literature? Please give more details and explanation.\n\n3. Regarding proof of Lemma 7, what is the intuition behind leveraging on a series of functions that are linearly independent over a Hilbert space?\n\n\n- Miscellaneous\n\nRegarding the footnote in page 6, which comments on the extension to non i.i.d. case, I think there is typo. It should be Appendix G not F. Moreover, what is the result on the non i.i.d. case? Mentioning about only the Lemma seems to be incomplete. Please add a full theorem or proposition about the non-i.i.d. case if to argue as in the footnote. \n\nIn Algorithm 1, how do we initialize the buffer and does it work like First-in-First-out queue or do we have to collect $N$ new samples whenever we start the inner loop?\n\n In line 713,  $M=\\log \\gamma$ does not make sense since $M$ should be positive while $\\log \\gamma$ is negative.", "limitations": "Even though, there are strict assumptions such as prior knowledge on optimal policy to select the exploration strategy $\\epsilon_t$, stationarity of Markov chain for every time step, and strict conditions on the initialization, I think the paper paved a way for analysis of DQN algorithm, and theoretical contribution is substantial. Hence, I am leaning towards acceptance.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper manages to derive sample complexity deep Q-network under epsilon-greedy policy, which has been difficult due to time-varying policy. The authors tackle this problem by defining $C_t$, a quantity that measures the difference of behavior policy and optimal policy. The theoretical contribution seems to be meaningful. \n\n2. Moreover, the technique to lower bound the Hessian matrix, levereging on a series of functions that are linearly independent over a Hilbert space,  seems to be novel.", "weaknesses": "1. The exploration strategy $\\epsilon_t$ requires prior knowledge of optimal policy, which is not possible. Moreover, the upper and lower bound for $\\epsilon_t$ is not really intuitive.\n\n2. The work assumes that mini-batch is sampled from time-varying stationary distribution. The transition matrix induced by behavior policy at every time step is assumed to be have stationary distribution.\n\n3. The step-size depends on the number of outer loop iteartions, $T$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "***Q1**: Regarding $\\epsilon_t$.*\n\n**A1**: Thanks for your insightful question! $e_t$ in Corollary 1 can be replaced by its upper bound, which is independent of $\\epsilon_t$. See GR for details.\n\nMoreover, we would like to clarify the insights from our upper and lower bound for $\\epsilon_t$. The upper and lower bound indicates: as $e_t$ diminishes, the corresponding $\\epsilon_t$ also decreases. This implies a strategy shift wherein greater exploration (characterized by a larger $\\epsilon_t$) is preferred in instances of limited environmental knowledge ($e_t$ being larger, indicating a behavioral policy somewhat distant from optimality). Conversely, as our understanding of the environment deepens, a preference for exploitation emerges. Furthermore, As we scale up the number of samples $N$, the lower bound of $\\epsilon_t$ becomes smaller while the upper bound becomes larger. This enlarged gap between the lower and upper bound signifies a broader spectrum of potential selections for $\\epsilon_t$, aligned with the augmented sample size. This phenomenon underscores the advantages associated with employing a larger sample size. \n\n\n***Q2**: Regarding extension to non i.i.d. cases.*\n\n**A2**:  Thank you for bringing our typo to our attention. Following your suggestion, we introduce Theorem 2 (see the pdf uploaded in GR due to the character limit), which serves as a variation of Theorem 1 tailored for the non-i.i.d. scenario. The analysis of non i.i.d. has yielded the following key distinctions:\n\n(i) Compared with Theorem 1, $|\\mathcal{A}|$ is replaced with $C_d$ in equations (17) and (20). This substitution is drawn from the difference between the stationary distribution and collected data distribution when the revised Assumption 2 holds. The difference has been elaborated in the error bound of $I_3$, as outlined in (148) within the supplementary materials.\n\n(ii) Furthermore, Theorem 2 introduces an additional error term into equations (19) and (20) because of the dependence between the collected data and current neural network weights.  This distinction has been elaborated through the error bound of $I_4$, which can be found in (160) within the supplementary materials.\n\n***Q3**:(11) implies local convexity.*\n\n**A3**: To establish the existence of a local convex region, a crucial requirement is to demonstrate that the Hessian matrix within this region is non-negative. Specifically, the smallest eigenvalue in this region is non-negative, which can be achieved with both (i) the Hessian function must be continuous, and (ii) the Hessian matrix at the ground truth must be strictly positive. Once these two conditions are satisfied simultaneously, we can ensure the presence of a neighboring region around the ground truth where the Hessian matrix is always non-negative. This region corresponds to the desired local convex region near the ground truth.\n\nEquation (11) relates to the smallest eigenvalue of the Hessian matrix at the ground truth. By establishing a strictly positive lower bound for (11), that makes condition (ii) hold, we guarantee the existence of the desired local convex region.\n\n\n***Q4**: Details of $I_4$.*\n\n**A4**: We apologize for the omitted details. The concept conveyed in lines 856 to 861 aims to streamline the integration process by transitioning from a high-dimensional space to a more manageable three-dimensional space. We have elaborated on the details (see the pdf uploaded in GR due to the character limit) for a comprehensive understanding.\n\n***Q5**: “Linearly independent over a Hilbert space”.*\n\n**A5**: The main objective of Lemma 7 is to establish the existence of a local convex region around the ground truth. As replied in A3, we need the Hessian matrix at the ground truth to be strictly positive. With this condition and the continuity of the Hessian matrix, we can guarantee the presence of a neighboring region around the ground truth, where the Hessian matrix is always positive. This region corresponds to the desired local convex region near the ground truth.\n\nTo ensure the smallest eigenvalue of the Hessian matrix is strictly greater than zero, we analyze the expression for $$I:=\\min_{||\\alpha||2=1} \\mathbb{E}_h \\Big\\( \\sum\\_\\{j=1\\}^K \\alpha\\_j^\\top h \\phi ( w\\_j^\\top h) \\Big)\\^2.$$\n\nNotably, $I$ is always greater than or equal to zero. To rule out the possibility of $I$ being exactly zero, we need to prove the linear independence among $\\\\{h \\phi^{\\prime}(w_{j}^{\\top}h)\\\\}\\_{j=1}\\^K$, meaning that there should be no $\\alpha$ that can make $\\sum_{j=1}^K \\alpha_j^\\top h \\phi^{\\prime}(w_{j}^{\\top}h)$ equal to zero. By demonstrating the linear independence of $\\\\{h \\phi^{\\prime}(w_{j}^{\\top}h)\\\\}\\_{j=1}\\^K$, we establish the assurance that $I$ cannot be zero, leading to a strictly positive smallest eigenvalue for the Hessian matrix. This result, in turn, ensures the existence of the desired local convex region around the ground truth.\n\n***Q6**: Initialization of the buffer: First-in-First-out (FIFO) queue or collect $N$ new samples?*\n\n**A6**: In each outer loop, it is necessary to collect $N$ new samples according to the theorem. However, to optimize computational efficiency, we implement the FIFO queue to manage the data collection for the buffer, along with a random sampling strategy in the inner loop, during numerical experiments. \n\n***Q7**: Typo of $M=\\log\\gamma$.*\n\n**A7**: Thanks for pointing out our typo. $M$ should be $\\log \\gamma^{-1}$. To further clarify, $M$ should be exactly $\\log_\\nu \\gamma = \\frac{\\log \\gamma}{\\log \\nu}$, where $\\nu$ is a constant that is less than 1. As $\\log \\nu$ is a negative constant, we can safely ignore it when determining the complexity. Thus, we can simplify the expression for $M$ to $\\Theta(\\log \\gamma^{-1})$. We appreciate your careful observation, and we hope this clarification resolves any confusion."}, {"review_id": "efEqZgyKAt", "reviewer": "Reviewer_fZ7E", "summary": "This paper studies DQN (one of the most popular RL algorithms in the literature) with $\\epsilon$-greedy behavior policy. Specifically, the authors provide the convergence and sample complexity guarantees and numerically verify the algorithm's performance.", "questions": "When using linear function approximation, Q-learning can be divergent [1,2] even if the target network is used as in this paper. In addition, there are several impossibility results in the literature [3,4] stating that unless certain assumptions are made (such as Bellman completeness, or both $V^*$ and $Q^*$ belong to the function class), the sample complexity can be exponential. While this paper uses neural network approximation, it is similar to linear function approximation when there is only one layer (the difference is only about the activation function). Then, (i) why is the algorithm naturally stable? and (ii) why does this algorithm achieve polynomial sample complexity? It is important to investigate the fundamental reason behind these questions to provide a better understanding of the behavior of Q-learning with function approximation.\n\n[1] Baird, L. (1995). Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995 (pp. 30-37). Morgan Kaufmann.\n\n[2] Chen, Z., Clarke, J. P., & Maguluri, S. T. (2022). Target Network and Truncation Overcome The Deadly Triad in $ Q $-Learning. arXiv preprint arXiv:2203.02628.\n\n[3] Zanette, A. (2021, July). Exponential lower bounds for batch reinforcement learning: Batch rl can be exponentially harder than online rl. In International Conference on Machine Learning (pp. 12287-12297). PMLR.\n\n[4] Wang, R., Foster, D. P., & Kakade, S. M. (2020). What are the statistical limits of offline RL with linear function approximation?. arXiv preprint arXiv:2010.11895.", "limitations": "The comments in the weakness section (especially comment (3)) should be the theoretical limitations of this work.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "This paper is well-written, and the appendix seems of high quality.", "weaknesses": "Major Comments:\n\n(1) Corollary 1: It is unclear to me how to choose $\\epsilon_t$ based on this result as $e_t$ is precisely the error of the algorithm, which is unknown to the agent.\n\n(2) Theorem 1: The authors refer to $W^{T,0}$ as the convergent point of the algorithm, which is confusing because $W^{T,0}$ depends on the iteration number. In addition, it is unclear to me why Theorem 1 implies the almost sure convergence (or any other kind of asymptotic convergence) of the weights.\n\nIn Eq. (19), I saw $t$ on the LHS. and $T$ on the RHS. Is this a typo? The claim of geometric decay based on Eq. (19) is not entirely convincing because $\\epsilon_t$ is not a constant but an implicit function of $t$. This also impacts the claim in Corollary 2. From my understanding, Corollary 2 is derived solely based on Eq. (20) because the transient term in Eq. (19) decays at a geometric rate, thereby does not contribute to any polynomial sample complexity. \n\n(3) Corollary 3: The assumption in Eq. (22) is not completely rigorous. In general, one should not make any assumptions about the trajectory of the very algorithm that is being studied.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*Q1:  Regarding Corollary 1.*\n\n**A1**: Thanks for your insightful question! $e_t$ in Corollary 1 can be replaced by its upper bound, which is independent of $\\epsilon_t$. See GR for details.\n\n*Q2: Regarding “W^T depends on the iteration number.” and “almost sure convergence of the weights”.*\n\n**A2**:  Thank you for bringing up the confusing parts, and we appreciate your feedback. In the following contents, we would like to clarify the key points regarding the revised Theorem 1, which can be found in the GR.\n\n**Firstly, there exists an upper bound for estimation error of the learned model weights that is independent of the iteration number.** We did not make that explicit in the original Theorem 1, and we revised Theorem 1 to reflect that. See (iii) in GR for details.\n\n**Secondly, we have revised (20) in Theorem 1 to indicate the convergence of the weights.** In our revised Theorem 1,  $C_\\max$ is bounded above for any arbitrarily large $T$. In addition, as the left-hand side of (20) goes to zero as $T$ goes to infinity, indicating the convergence of our proposed algorithm. We apologize for the unclear description of the upper bound of the learned weights in our manuscript because of the dependence between the upper limit and iteration number.\n\n**Thirdly, we would like to clarify that Theorem 1 holds with a high probability of at least $1 - T\\cdot q^{-d}$, which we regret was missing in the submitted manuscript.** We regret the oversight of points 2 and 3 that may have led to your confusion about “convergence of the weights.”\n\n*Q3: Typo in (19)?*\n\n**A3**: We apologize for the typo. It should be $t$ in both the LHS and RHS of (19), and please check GR for the updated Theorem 1. \n\n*Q4: Regarding Corollary 2.*\n\n**A4**:  Thank you for your insights. Although $\\epsilon_t$ is not a constant, the convergence rate is $\\gamma + c_\\epsilon(1-\\gamma)$ from (19), and $c_\\epsilon$ is a constant, which is pre-determined and remains unchanged over time $t$, see the line 245 after (17).\n\n*Q5: Regarding Corollary 3.*\n\n**A5**: Thank you for your thoughtful feedback. We believe the raised concern may stem from a misunderstanding of the relationship between Theorem 1 and Corollary 3. We would like to clarify that Theorem 1 contributes to our primary conclusion and does not rely on the assumption presented in (22). We apologize for the improper presentation of Theorem 1 in the original draft, and we anticipate that the revised version of Theorem 1 in GR will help alleviate any such misunderstanding.\n\nTo elaborate, our significant theoretical findings, outlined in Section 4.1,  are directly derived from Theorem 1 without any reliance on the assumption in (22). Namely, (i) the theoretical characterization of $\\epsilon_t$ for convergence, (ii) the convergence analysis of DQN with bounded estimation error, and (iii) sample complexity for achieving a desired estimation error of the optimal Q-value function. These three major contributions do not rely on the assumption in (22).  Moreover,  we introduced Corollary 3 as an extension to our primary theorem, showcasing a tighter bound, which diminishes to zero, for the estimation error of the Q-value function under a stronger assumption (22), compared to the general constant upper bound in (20). \n\nWe are acutely aware of your concerns about the rigor of Eq. (22), and such a concern is carefully addressed in our original draft by not incorporating the aforementioned assumption into our core theoretical findings.\n\n*Q6: “When using linear function approximation, Q-learning can be divergent [1,2].”*\n\n**A6**: Thank you for providing the relevant papers. We agree with your observation that Q-learning can be divergent without making certain assumptions. In [2], the authors demonstrate that using a target network together with truncation is sufficient to stabilize Q-learning. The truncation effectively restricts the learned function's weights from deviating too far away from a certain point, which could potentially be a ground truth or some other reference point. A similar idea, as seen in [84], involves restricting the weights within a local region to ensure a stable algorithm. \n\nAlthough our work does not restrict the update of the weights, the weights naturally move in a relatively small region in our proposed algorithm. To see this, we characterize a local convex region in our work. Using a proper step size and a good initialization, we prove that the learned weights in Algorithm 1 are guaranteed to remain within this local convex region. This result aligns with the idea presented in [2] for stabilizing Q-learning. We will include the relevant papers in our work and provide a clear connection with existing research.\n\n*Q7: “The sample complexity can be exponential in [3,4].\"*\n\n**A7**: Thank you for providing the relevant papers. We want to clarify the distinction between our manuscript and [3, 4], as [3, 4] both address offline RL (or batch RL) scenarios where the agent cannot access the environment during the algorithm's execution. However, this manuscript focuses on an online setting. In online settings, during each outer loop of the algorithm, the agent can access the environment and actively collect data based on the updated policy. This fundamental difference in the setup allows the proposed approach to leverage real-time data and adapt the policy during the learning process, which can lead to more efficient and adaptive learning compared to offline RL methods. The ability to access the Markov transition matrix and actively collect new data enables the algorithm to make informed decisions based on up-to-date information, potentially leading to more effective policy learning. For example, polynomial sample complexity has been achieved for online Q-learning with function approximation in [19, 22, 31, 74] (citation number in submitted version). We will add a new paragraph in the related work to clarify the sample complexity differences between offline and online RL.\n"}]

Author rebuttal:
We thank all the reviewers' comprehensive reading of this paper and valuable suggestions, and the paper will be revised according to the reviewers’ comments. We will first provide our general response (GR) to capture the major modifications made, focusing particularly on our revision of Theorem 1. Furthermore, we will address the reviewers' specific inquiries concerning the dependence between $\epsilon_t$ and $e_t$ in GR, drawing from the insights provided by our revised Theorem 1.


**(Revision of Theorem 1.)** A revision of our Theorem 1 is presented in the following text while retaining the core insights outlined in Section 4.1. Namely, Theorem 1 still implies that (T1) Theoretical characterizations of   $\\{\epsilon_t\\}_{t=1}^{T}$ for convergence, (T2) Convergence to the optimal Q-value function $Q^\star$ with bounded estimation error, and (T3) Sample complexity for achieving a desired estimation error of the optimal Q-value function. 

Here are several significant changes in Theorem 1:

(i) The notation in equation (20) requires a correction to be $N\cdot T$ instead of just $N$, as there was an incorrect use of notation in equation (59) within the supplementary materials. The revised equation (59) should read as follows: $N\cdot T \ge \sum_{t=1}^T N_t \ge c_{N}^{-2}\rho^{-1} Ld \log q \cdot T$ instead of $N \ge \sum_{t=1}^T N_t$.

(ii) Theorem 1 holds with a high probability of at least $1 - T\cdot q^{-d}$, which we regret was missing in the submitted manuscript.

(iii) $C_t$ in both (17) and (20) are replaced with $C_\max$, which serves as an upper bound of $C_t$ for $t\le T$. Recall that $C_t$ reflects the proportion of non-optimal state-action pairs during the $t$-th iteration, it logically follows that $C_\max$ is upper bounded by at least $1$. This bound ensures that $C_\max$ is upper bounded in (20) for any arbitrarily large $T$. As the left-hand side of (20), $\frac{ |\mathcal{A}|\cdot R_{\max}}{(1-\gamma)^2 \cdot \Theta(\sqrt{N\cdot T})}$, goes to zero as $T$ goes to infinity, indicating the convergence of our proposed algorithm.

(iv) $e_t$ is replaced by a characteriable upper bound in (17), which makes the selection of $\epsilon_t$ independent of $e_t$. 

---
**Theorem 1** (Convergence to $Q^\star$)
Suppose Assumptions 1 and 2 holds, the buffer size $N$ satisfies (13). Let us define $C_{\max}$ be a upper bound of  $C_t$ for $1\le t\le T$,  when $\epsilon_t$ satisfy

$$\epsilon_t = \max\Big\\{ \frac{c_{\varepsilon}\cdot  \Theta(\sqrt{N})\cdot \big(\gamma + {c_\epsilon}\cdot(1-\gamma)\big)^t e_0 }{(1-C_{\max}) \cdot |\mathcal{A}|\cdot R_{\max}} -\frac{C_{\max}}{1-C_{\max}}, ~~~~
\frac{C_\max}{1-C_\max}\Big\\} ~~~~~~(16)$$


for a fixed constant $c_\epsilon\in (0, (1-\gamma)^2]$, and the initialization satisfies


$$||W^{(0,0)}-W^*||\_F \le \mathcal{O}\Big( 1 - \frac{1-c_\epsilon}{\Theta(\sqrt{N})} \big)\cdot \frac{\rho\cdot ||W^\star||_F}{K}.   ~~~(18)$$  


Then, with the high probability of at least $1-T\cdot q^{-d}$, we have
   
   * the learned weights decay geometrically with
  
 $$|| W^{(t,0)} -W^\star ||\_F \le \big(\gamma + c_\epsilon \cdot(1-\gamma)\big)^t \cdot ||W^{(0,0)}-W^\star||\_F, ~~~ t \le T_0:=\log_{\gamma} (1/N), ~~~~~~~~(19)$$


   * the returned model $Q(W^{(T,0)})$ exhibits an  estimation error as
   
$$\sup_{(s,a)}\big|Q(W^{(T,0)})-Q^\star\big| \le \frac{{C_{\max}}\cdot |\mathcal{A}|\cdot R_{\max}}{(1-\gamma)^2 \cdot \Theta(\sqrt{N\cdot T})}. ~~~~~~~~~~~(20)$$

---

**(Theoretical derivation of the revised Theorem 1.)** We would like to clarify that the updated results in (iii) and (iv) can be derived by taking 

$$\begin{align}&\frac{c_N\cdot C_d\cdot \big({C_t +(1-C_t)\cdot \epsilon_t}\big)}{K}
\cdot \frac{R_\max}{1-\gamma} +(1-\epsilon_t/2)\gamma \cdot ||W^{(t,0)}-W^\star ||\_2\\\\
\le &\frac{c_N\cdot C_d\cdot \big(C_\max +(1-C_\max)\cdot \epsilon_t\big)}{K}\cdot \frac{R_\max}{1-\gamma} +(1-\epsilon_t/2)\gamma \cdot \big(\gamma+ {c_\epsilon}\cdot(1-\gamma)\big)^t e_0.\end{align}$$

in equation (62) in the supplementary materials.

**(Selection of $\epsilon_t$ and revision of Corollary 1.)** In the revised Theorem 1, when $t<T_0$, $c_\epsilon$ in $\epsilon_t$ remains constant, controlling the upper bound of $e_t$, thus offering a way to upper bound the magnitude of $e_t$. This observed behavior empowers us to utilize the expression $\big(\gamma+c_\varepsilon\cdot (1-\gamma)\big)^t\cdot e_0$ to replace $e_t$ in the selection of $\epsilon_t$. When $t>T_0$, $\epsilon_t$ satisfies equation. (20), the upper bound of $\epsilon_t$ becomes a small constant. Therefore, the choice of $\epsilon_t$ gradually decreases following a geometric decay until it reaches a low threshold, beyond which it remains constant at this threshold level. Our numerical experiments also adhere to this standard, and we intend to incorporate a similar clarification regarding $e_t$ in the updated version of the paper. 

Following similar steps to (19), the lower bound of $\epsilon_t$ in (15) can be derived as 

$$\epsilon_t \ge \max\Big\\{  1-\Theta(\sqrt{N})\cdot \Big(1-\big(\gamma + {c_\epsilon}\cdot(1-\gamma)\big)^t e_0\Big), ~~~ 
1- \Big(\Theta(\sqrt{N})-\frac{{C_\max}\cdot |\mathcal{A}|\cdot R_\max}{(1-\gamma)^2 \cdot \Theta(\sqrt{T})}\Big) \Big\\}~~~~~~~~~~~~~(15)$$ 

and the upper bound of $\epsilon_t$ in (16) can be derived as 

$$\epsilon_t \le \max\Big\\{ \frac{(1-\gamma)^2\cdot  \Theta(\sqrt{N})\cdot \big(\gamma + {c_\epsilon}\cdot(1-\gamma)\big)^t e_0 }{(1-C_{\max}) \cdot |\mathcal{A}|\cdot R_{\max}} -\frac{C_{\max}}{1-C_{\max}}, ~~~\frac{C_{\max}}{1-C_{\max}} \Big\\}  (16)$$
which are independent of the iteration number $t$. Similar to Remark 2 in the original manuscript, we can derive the conclusion that $\epsilon_t$ needs to decrease as $t$ decreases. Namely, more exploitation (a smaller $\epsilon_t$) is preferred as we gain knowledge of the environment (larger iteration number $t$).


Meta-review: A new analysis for the eps-greedy exploration in deep Q learning is presented. Despite a negative average of ratings at the very beginning, authors did a great job clarifying a few concerns shared among reviewers (who reached a positive consensus). After checking the original submission, I realized that most such concerns (most of which are due to an unclear way of presenting and a lack of comparison) are valid but can be fixed by a thorough revision. On the other hand, the authors’ rebuttal made them clear. Although I recommended acceptance, I urge authors to incorporate the rebuttal material into the original paper (maybe as a discussion section), which will make it much more solid.
Decision: Accept (poster)