Paper deep dive
Online Statistical Inference of Constant Sample-averaged Q-Learning
Saunak Kumar Panda, Tong Li, Ruiqi Liu, Yisha Xiang
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 94%
Last extracted: 3/31/2026, 1:58:46 AM
Summary
This paper introduces a statistical online inference framework for a sample-averaged variant of the Q-learning algorithm. By adapting the functional central limit theorem (FCLT) for Markov chains, the authors establish theoretical guarantees and propose a random scaling method to construct confidence intervals for Q-values. Numerical experiments on grid world and dynamic resource-matching problems demonstrate that the sample-averaged approach provides tighter confidence intervals and improved accuracy compared to vanilla Q-learning.
Entities (5)
Relation Signals (3)
Random Scaling → constructs → Confidence Intervals
confidence 95% · construct confidence intervals for the Q-values via random scaling
Sample-averaged Q-learning → uses → Functional Central Limit Theorem
confidence 95% · We adapt the functional central limit theorem (FCLT) for the modified algorithm
Sample-averaged Q-learning → outperforms → Vanilla Q-learning
confidence 90% · our approach showcases higher accuracy in terms of the coverage rates and confidence interval lengths
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Reinforcement learning algorithms have been widely used for decision-making tasks in various domains. However, the performance of these algorithms can be impacted by high variance and instability, particularly in environments with noise or sparse rewards. In this paper, we propose a framework to perform statistical online inference for a sample-averaged Q-learning approach. We adapt the functional central limit theorem (FCLT) for the modified algorithm under some general conditions and then construct confidence intervals for the Q-values via random scaling. We conduct experiments to perform inference on both the modified approach and its traditional counterpart, Q-learning using random scaling and report their coverage rates and confidence interval widths on two problems: a grid world problem as a simple toy example and a dynamic resource-matching problem as a real-world example for comparison between the two solution approaches.
Tags
Links
- Source: https://arxiv.org/abs/2603.26982v1
- Canonical: https://arxiv.org/abs/2603.26982v1
Trouble viewing inline? Open PDF directly →
Full Text
30,388 characters extracted from source content.
Expand or collapse full text
Online Statistical Inference of constant Sample-averaged Q-Learning Saunak Kumar Panda spanda@uh.edu Department of Industrial Engineering University of Houston &Tong Li tli31@cougarnet.uh.edu Department of Industrial Engineering University of Houston &Ruiqi Liu ruiqliu@ttu.edu Department of Mathematics and Statistics Texas Tech University &Yisha Xiang yxiang4@central.uh.edu Department of Industrial Engineering University of Houston Abstract Reinforcement learning algorithms have been widely used for decision-making tasks in various domains. However, the performance of these algorithms can be impacted by high variance and instability, particularly in environments with noise or sparse rewards. In this paper, we propose a framework to perform statistical online inference for a sample-averaged Q-learning approach. We adapt the functional central limit theorem (FCLT) for the modified algorithm under some general conditions and then construct confidence intervals for the Q-values via random scaling. We conduct experiments to perform inference on both the modified approach and its traditional counterpart, Q-learning using random scaling and report their coverage rates and confidence interval widths on two problems: a grid world problem as a simple toy example and a dynamic resource-matching problem as a real-world example for comparison between the two solution approaches. 1 Introduction Reinforcement learning (RL) has emerged as a powerful paradigm for training agents to make sequential decisions in complex and uncertain environments. While many RL algorithms have shown remarkable success in a variety of applications, there is a growing recognition of the need to incorporate statistical inference techniques into RL to enhance its robustness, reliability, and interpretability. This motivation stems from the inherently stochastic nature of RL environments, where randomness can arise from various sources, such as sensor noise, unobservable state variables, or even the inherent uncertainty in the agent’s interactions with the environment. Statistical inference plays an important role in several real-world applications ranging from financial analysis of stocks and other financial assets to critical applications like medical research where confidence intervals of mean difference in outcomes between treatment and control groups are calculated to determine whether a new drug or treatment is effective. Several frequently employed methods in statistical inference, particularly for computing confidence intervals, encompass bootstrapping, spectral variance, and batch-means, among others. The majority of these methods leverage the central limit theorem (CLT) to attain the asymptotic covariance of estimate distributions of our RL algorithms. One promising research direction is the application of the functional central limit theorem (FCLT) to RL algorithms, particularly in the context of Q-learning. The FCLT, which provides a theoretical foundation for the emergence of normality in certain functionals of random processes, offers a novel perspective for understanding the statistical properties of Q-learning and related algorithms. Leveraging FCLT results in the context of Q-learning can help provide insights into its convergence behavior and uncertainty quantification, making it a valuable tool for characterizing its statistical properties. This paper aims to explore and leverage the FCLT to advance our understanding of statistical inference, specifically for a sample-averaged variant of the Q-learning algorithm, called sample-averaged Q-learning. Our main contribution lies in providing theoretical guarantees for our sample-averaged Q-learning algorithm under standard assumptions and further demonstrate higher accuracy of our method using a random scaling approach for computing confidence measures on a few numerical examples. The remainder of the paper is organized as follows. In Section 2, we review relevant literature on statistical inference methods, in the context of stochastic gradient descent(SGD) and RL. In Section 3, we provide the problem setup and propose our sample-averaged Q-learning. In Section 4, we discuss the main theoretical result in detail and provide the method to perform statistical inference for the proposed sample-averaged Q-learning. In Section 6, we present numerical results and compare the confidence measures of Q-values obtained from both the vanilla Q-learning method and our proposed sample-averaged Q-learning approach on two numerical examples. Our approach showcases higher accuracy in terms of the coverage rates and confidence interval lengths. 2 Literature Review The literature on statistical inference methods in the context of SGD and RL has seen significant growth in recent years, with researchers proposing various methodologies to address the challenges associated with making statistical inferences from data generated by these methods, specifically iid and Markovian data. li2018statistical introduce a statistical inference framework using SGD. Their methodology relies on the asymptotic properties of SGD and established convergence results. It provides a foundation for making statistical inferences on parameters learned through SGD optimization. This approach is less expensive than bootstrapping for large data size and parameter dimensionality, that is, there is no need for re-sampling many times. An added advantage is that this approach only uses first-order information and we can also conduct finite sample inference. fang2018online present online bootstrap confidence intervals for the SGD estimator. By incorporating bootstrapping techniques into the analysis, they proposed a method for constructing confidence intervals for the parameters learned through SGD, addressing the problem of estimating uncertainty in this context. chen2020statistical propose statistical inference for model parameters in SGD. Their work provides a comprehensive framework involving two methods, namely batch-means and plug-in estimators for quantifying uncertainty in parameter estimates. They show that the plug-in estimator achieves faster convergence than batch means, while the batch-means estimator needs less storage and calculation. chen2021statistical propose a statistical inference method for online decision-making via SGD. Their approach utilizes asymptotic normality results to construct confidence intervals for online decision rules. They derived an inverse probability-weighted value estimator to estimate the optimal value, and proposed plug-in estimators to estimate the variance of the parameters. lee2022fast propose a novel technique through an FCLT result that enables them to develop an efficient online inference method via random scaling. They show the robustness of their inference method for SGD algorithms using simulation experiments. The above methods are well suited to cases where the data is generated by an iid sampling procedure and are unable to account for the underlying dependence structure of the observations following a Markovian structure. ramprasad2023online propose an online bootstrap inference method for policy evaluation in RL. They leverage the bootstrap technique to construct confidence intervals for policy value estimates in both on- and off-policy estimates. The approach adapts to non-i.i.d. and temporally correlated data encountered in RL tasks, making it suitable for dynamic environments. However, this method may be computationally intensive and sensitive to the choice of bootstrap parameters. li2023statistical propose the Polyak-Ruppert-Averaged Q-learning algorithm and provide an FCLT result showing their algorithm is statistically efficient. However, they require stronger conditions on their noise moments. xie2022statistical introduce a statistical online inference approach in averaged stochastic approximation. They develop a unified framework for analyzing algorithms such as SGD and Q-learning from the perspective of stochastic approximation. They establish an FCLT for time-homogeneous Markov chains under weaker conditions and then construct confidence intervals for parameters via random scaling. Since the random scaling approach uses a studentized approach to obtaining the variance, it avoids additional estimation steps and hyper-parameters, resulting in its higher accuracy over traditional estimators like bootstrapping and batch-means. 3 Problem Setup An infinite-horizon MDP is represented by ℳ=(,,γ,P,R,r)M=(S,A,γ,P,R,r), where S is the state space and A is the action space, γ∈(0,1)γ∈(0,1) is the discount factor, P:×→Δ()P:S×A→ (S) represents the probability transition kernel, R:×→[0,∞)R:S×A→[0,∞) is the random reward, and r:×→[0,∞)r:S×A→[0,∞) is the expectation of the reward. For a given deterministic policy π:→π:S , the Q-function for any state-action pair (s,a)∈×(s,a) ×A is given by, Qπ(s,a) Q^π(s,a) =τ∼π[∑t=0∞γtr(st,at)|s0=s,a0=a], =E_τ π [ _t=0^∞γ^tr(s_t,a_t)|s_0=s,a_0=a ], (1) where τ=(st,at)t≥0τ=\(s_t,a_t)\_t≥ 0 is a trajectory of the MDP induced by the policy π. The optimal Q-function Q∗Q^* is defined as Q∗(s,a)=maxπQπ(s,a)Q^*(s,a)= _πQ^π(s,a). We know that Q∗Q^* is the unique fixed point of the Bellman operator T, where (Q)(s,a)=r(s,a)+γs′∼P(⋅∣s,a)maxa′∈Q(s′,a′).T(Q)(s,a)=r(s,a)+ _s P(· s,a) _a Q (s ,a ). Suppose that we have a sequence of i.i.d. observations (ri,si′),i=1,2,…\(r_i,s _i),i=1,2,…o\ given state action pair (s,a)(s,a). For each (s,a)∈×(s,a) ×A at the t-step, we generate BtB_t rewards Rt,1(s,a),…,Rt,Bt(s,a)R_t,1(s,a),…,R_t,B_t(s,a) and the associate next states St,1′,…,St,Bt′S _t,1,…,S _t,B_t. We consider dividing them into several batches. To estimate Q∗Q^*, the sample-averaged Q-learning will have the following update rule: Qt+1(s,a) Q_t+1(s,a) =Qt(s,a)−ηtQt(s,a)−^t+1(Qt)(s,a) =Q_t(s,a)- _t \Q_t(s,a)- T_t+1(Q_t)(s,a) \ (2) where ^t+1(Qt)(s,a)=1Bt∑i=1BtRt,i(s,a)+γBt∑i=1Btmaxai′Qt(St,i′,ai′). T_t+1(Q_t)(s,a)= 1B_t _i=1^B_tR_t,i(s,a)+ γB_t _i=1^B_t _a_i Q_t(S _t,i,a_i ). (4) and γ is the discount factor. In particular, when Bt=1B_t=1 is a constant, it reduces to vanilla Q-learning. Hence, our sample-averaged approach can be considered as a generalization of the single-sample vanilla Q-learning algorithm. It can be easily shown that ^t T_t is an unbiased estimator of the Bellman operator T. 4 Asymptotic Results In this section, we provide a theoretical result for the constant sample-averaged Q-learning update given in equation (2) such that Bt=B≥1B_t=B≥ 1, where B is a constant. Specifically, to state our FCLT result, we first show that our sample-averaged Q-learning process converges to a stationary distribution and, we further provide an upper bound for the bias arising from the gap between the expectation and the ground truth solution. Finally, we establish the FCLT for our sample-averaged Q-learning algorithm which enables us to perform inference using a random scaling method. Assumption A1 (Uniformly bounded reward). The random reward R is non-negative and uniformly bounded, i.e., 0⩽R(s,a)⩽10 R(s,a) 1 almost surely for all (s,a)∈×(s,a) ×A. In the above assumption, we impose a boundedness condition on the random reward of the model. 4.1 Functional Central Limit Theorem for sample-averaged Q-learning Theorem 1 Assume access to a generative model for each state-action pair (s,a)∈×(s,a) ×A. Let Q∈ℝ||×||Q ^|S|×|A| be the matrix form of the Q-function Q(s,a)Q(s,a). Then there exists a constant η0>0 _0>0 such that for any η∈(0,η0)η∈(0, _0), 1. the sample-averaged Markov process (t)t≥0(Q_t)_t≥ 0 defined by (2) has a unique stationary distribution ηQ_η 2. for ∼ηQ _η, we have η‖−∗‖∞=(η1/2)E_Q_η||Q-Q^*||_∞=O(η^1/2) 3. The following FCLT holds 1∑t=1TBt−1∑t=1⌊rT⌋(t−η)⇒Ση12M(r),0≤r≤1, 1 _t=1^TB_t^-1 _t=1 rT (Q_t-E_Q_ηQ) _Q_η 12M(r), 0≤ r≤ 1, (5) where (Mr))r≥0(M_r))_r≥ 0 is the d-dimensional standard Brownian motion and ΣQη=limn→∞ncovQη(Q¯n) _Q_η= _n ∞ncov_Q_η( Q_n) is the asymptotic covariance matrix. A direct consequence of Theorem 1 with r=1r=1 is the asymptotic distribution of the sample-averaged estimator via averaging, which is summarized as the following corollary. Corollary 1 Under the uniform bounded reward assumption, it follows that T∑t=1TBt−1(¯T−∗)→N(0,Ω) T _t=1^TB_t^-1 ( Q_T-Q^* ) LN(0, ) Noting that there are total N=∑t=1TBtN= _t=1^TB_t observations used after T iterations, by Corollary 1 , we can quantify the asymptotic covariance of ¯T Q_T by Var(N¯T)≈N∑t=1TBt−1T2Ω=∑t=1TBt∑t=1TBt−1T2Ω.Var ( N Q_T )≈ N _t=1^TB_t^-1T^2 = _t=1^TB_t _t=1^TB_t^-1T^2 . It can be verified that the estimator ¯T Q_T with a constant batch size Bt=B_t=B is asymptotically efficient with an asymptotic covariance matrix Ω . However, when BtB_t is diverging, it suffers from an efficiency loss. Obtaining an efficient sample-averaged estimator for Q-learning is out of the scope of this paper. 4.2 Online inference via Random Scaling In this section, we propose an online algorithm based on Theorem 1 for constructing a confidence interval of ∗Q^*. Before proceeding, let us introduce the random scaling quantity: D^T=1T∑s=1T1mT∑t=1s(t−¯T)1mT∑t=1s(t−¯T)⊤, D_T= 1T _s=1^T \ 1m_T _t=1^s (Q_t- Q_T ) \ \ 1m_T _t=1^s (Q_t- Q_T ) \ , where mT=∑t=1TBt−1m_T= _t=1^TB_t^-1. If we further define a stochastic process M^(r):=mT−1∑t=1⌈rT⌉(t−∗) M(r):=m_T^-1 _t=1 rT (Q_t-Q^* ) it can be verified that M^(1)=TmT−1(¯T−∗) M(1)=Tm_T^-1 ( Q_T-Q^* ) and D^T=∫01(M^(r)−rM^(1))(M^(r)−rM^(1))⊤r. D_T= _0^1( M(r)-r M(1))( M(r)-r M(1)) dr. As a consequence of the continuous mapping theorem and Theorem 1, we obtain the following result, which can be easily shown using Theorem 1 and continuous mapping theorem. Theorem 2 Under our bounded reward assumption, it holds that T2mT2(¯T−∗)D^T−1(¯T−∗)⊤→M(1)∫01M¯(r)M¯⊤(r)r−1M⊤(1). T^2m_T^2 ( Q_T-Q^* ) D_T^-1 ( Q_T-Q^* ) LM(1) \ _0^1 M(r) M (r)dr \^-1M (1). Here M(r)M(r) is d-dimensional standard Brownian motion on [0,1][0,1], and M¯(r)=M(r)− M(r)=M(r)- rM(1)rM(1). As a consequence, it follows that κ^=T(¯T,j−j∗)mTD^T,jj→M1(1)(∫01M1(r)−rM1(1)2r)−1/2:=κ. κ= T ( Q_T,j-Q_j^* )m_T D_T,j LM_1(1) ( _0^1 \M_1(r)-rM_1(1) \^2dr )^-1/2:=κ. Here ¯T,j,j∗ Q_T,j,Q_j^* are the j-th entry of ¯T,∗,D^T,jj Q_T,Q^*, D_T,j is the j-th diagonal element of D^T D_T, and M1(r)M_1(r) is a one-dimensional standard Brownian motion. Theorem 2 shows that we can construct a statistic κ κ that is asymptotically pivotal. As a consequence, we can construct a (1−α)×100%(1-α)× 100\%-level confidence interval for j∗Q_j^* as follows: ¯T,j±κα/2mTTD^T,jj. Q_T,j± _α/2 m_TT D_T,j. Here κα/2 _α/2 is the upper α/2α/2-quantile of the random variable κ. As shown in ca5c88c-60e5-392c-ad0a-5a051a7c51f, the distribution of κ is a mixed normal and symmetric around zero. The values of κα _α can be found in Table 1 in ca5c88c-60e5-392c-ad0a-5a051a7c51f. 5 Numerical experiments In this section, we will conduct a computational study to assess the performance of our proposed sample-averaged Q-learning algorithm as compared to the vanilla Q-learning algorithm using the random scaling method. We will first use a grid world problem to illustrate the performance in a small state and action space. We will further provide a case study in the context of real-world dynamic supply-demand matching, where the states and corresponding actions are high-dimensional and their spaces are significantly larger. 5.1 Grid World Problem In this section, we consider synchronous Q-learning in a Grid World environment. The environment consists of 3 × 4 grids as its state space. At each grid, the agent can choose to go “up”, “down”, “left” or “right” into the next grid. If it touches the edge or the block (i.e., the black grid), then it stays still. It stops after arriving at the blue/orange grid. Each immediate reward is -1 at grey grids, and +10/ - 10 at the blue/orange grid, respectively. The discount factor is set to γ = 0.9. Under this deterministic reward setting, the optimal policy at each grid is represented by a red arrow in Figure 1. Now, we consider randomizing the immediate reward at each grid with a (0,σ2)N(0,σ^2) Gaussian noise. We set σ = 2 and the learning rate η = 0.1. The performance of the random scaling method for Vanilla Q-learning and sample-averaged Q-learning (batch) are compared in three aspects: the coverage rates for QηE_Q_ηQ and ∗Q^*, and the lengths of confidence intervals. Here, the expected Q-value ηE_Q_ηQ is approximated by 500,000 Monte Carlo simulations, and the true Q-value ∗Q^* is derived by Q-learning in the deterministic reward setting. The nominal coverage rate is chosen as 95%. We perform 10,000 iterations of both algorithms on this problem. It can be observed from Table 1 that the coverage rates for the random scaling (RS) method for vanilla Q-learning are consistently higher than the ones with sample-averaged Q-learning. It can be seen that the confidence interval lengths converge to approximately the same values for both cases. However, to draw more conclusions about both the sampling Q-learning methods, examples with more complexity need to be considered as the current grid world example has few states and action spaces and, therefore is not extensive enough to draw conclusive results. Hence, we next consider a non-trivial learning problem. Figure 1: Grid World Table 1: Statistical Inference for Q-learning for Grid World Problem n = 2000 n = 6000 n = 10000 η=0.1,σ=2η=0.1,σ=2 Cov. for ∗Q^* (%) RS for Vanilla QL 99.0 (0.054) 97.5 (0.021) 96.0 (0.0153) RS for Sample-averaged QL 99.0 (0.075) 99.0 (0.025) 99.0 (0.0158) Cov. for ηE_Q_ηQ (%) RS for Vanilla QL 99.0 (0.054) 98.0 (0.021) 97.5 (0.0153) RS for Sample-averaged QL 99.0 (0.075) 99.0 (0.025) 99.0 (0.0158) Length RS for Vanilla QL 0.735 0.285 0.21 RS for Sample-averaged QL 1.0 0.345 0.215 5.2 Dynamic Matching Problem Figure 2: Dynamic Resource-matching We consider Q-learning in a dynamic resource-matching problem represented in Figure2. For simplicity, the system consists of 2 demand and 2 supply types, that is, a 2x2 matching problem. The reward matrix R is chosen such that r11>r21>r12>r22r_11>r_21>r_12>r_22 and is given by R=[85;73]R=[8 5 ; 7 3]. Each immediate reward is the product of the quantity matched with the reward matrix. The possible demand quantities for both types are (0,1,2,3)(0,1,2,3) with probabilities (0.5,0.5,0,0)(0.5,0.5,0,0) for both type 1 and type 2 products. The discount factor is set to γ = 0.9. We consider randomizing the immediate reward for each matching with a (0,σ2)N(0,σ^2) Gaussian noise. We set σ = 2 and the learning rate η = 0.1. The performance of the random scaling method for Vanilla Q-learning and sample-averaged Q-learning (batch) with a sample size B=5B=5 are compared in three aspects: the coverage rates for ηE_Q_ηQ and ∗Q^*, and the lengths of confidence intervals. Here, the expected Q-value ηE_Q_ηQ is approximated by 5,000 Monte Carlo simulations, and the true Q-value ∗Q^* is derived by Q-learning in the deterministic reward setting. The nominal coverage rate is chosen as 95%. Since this problem contains larger state and action spaces, we perform 2,000 iterations of both algorithms on this problem. It can be observed from Table 2 that while the coverage rates for the random scaling (RS) method for both the Q-learning methods are approximately the same, the confidence interval lengths are much tighter for the sample-average case, indicating much better accuracy in the confidence measures for the dynamic resource-matching problem. Table 2: Statistical Inference for Q-learning for Dynamic Matching Problem n = 500 n = 1000 n = 2000 η=0.1,σ=2η=0.1,σ=2 Cov. for ∗Q^* (%) RS for Vanilla QL 99.9 99.9 99.9 RS for Sample-averaged QL 99.9 99.9 99.9 Cov. for ηE_Q_ηQ (%) RS for Vanilla QL 99.9 99.9 99.9 RS for Sample-averaged QL 99.9 99.9 99.9 Length RS for Vanilla QL 299.4 199.5 113.8 RS for Sample-averaged QL 49.6 33.7 19.1 6 Conclusion In this paper, we proposed a statistical inference procedure for a sample-averaged variant of Q-learning. Based on an FCLT in the context of Markov chains, we established a corresponding FCLT result for our proposed sample-averaged Q-learning. We conducted numerical experiments for both the Q-learning variants and showed higher accuracy for our sample-averaged Q-learning approach using random scaling. Some interesting extensions can be developing a random scaling method for the following variants: (i) an adaptive sample-averaged Q-learning algorithm where the batch size BtB_t changes adaptively with time; (i) a linear function approximation (LFA) of the proposed sample-averaged Q-learning. Extending the above approach to scheduled batch and LFA requires considering additional rate conditions and assumptions on the linearly independent functions representing the state, which can be regarded as future work. Acknowledgements This work is supported in part by the U.S. National Science Foundation under award 2305486. Appendix Appendix A Proof of Theorem 1 We will first verify that ^t T_t is an unbiased estimator of the Bellman operator T. By direct examination, (2) can be written as Qt+1(s,a)=Qt(s,a)+ηt^t+1(Qt)(s,a)−Qt(s,a)⏟W^t+1(Qt)(s,a). Q_t+1(s,a)=Q_t(s,a)+ _t \ T_t+1(Q_t)(s,a)-Q_t(s,a) \_ W_t+1(Q_t)(s,a). (6) Now, W^t+1(Qt)(s,a)|Qt(s,a) \ W_t+1(Q_t)(s,a)|Q_t(s,a) \ =^t+1(Q)(s,a)−Qt(s,a) =E\ T_t+1(Q)(s,a)-Q_t(s,a)\ =1Bt∑i=1Btrt,i(s,a)+γ1Bt∑i=1Btmaxai′Q(st,i,ai′)−Qt(s,a)|Qt(s,a) =E\ 1B_t _i=1^B_tr_t,i(s,a)+γ 1B_t _i=1^B_t _a _iQ(s_t,i,a _i)-Q_t(s,a)|Q_t(s,a)\ By linearity of expectation, =1Bt∑i=1Btrt,i(s,a)|Qt(s,a)+γBt∑i=1Btmaxai′Q(st,i,ai′)|Qt(s,a) = 1B_tE\ _i=1^B_tr_t,i(s,a)|Q_t(s,a)\+ γB_tE\ _i=1^B_t _a _iQ(s_t,i,a _i)|Q_t(s,a)\ −Qt(s,a)|Qt(s,a) -E\Q_t(s,a)|Q_t(s,a)\ =1Bt∑i=1Btrt,i(s,a)|Qt(s,a)+γBt∑i=1Btmaxai′Q(st,i,ai′)|Qt(s,a) = 1B_t _i=1^B_tE\r_t,i(s,a)|Q_t(s,a)\+ γB_t _i=1^B_tE\ _a _iQ(s_t,i,a _i)|Q_t(s,a)\ −Qt(s,a) -Q_t(s,a) Since the data is collected from a generative model, =rt(s,a)+γs′∼P(⋅|s,a)maxa′Q(s′,a′)−Qt(s,a) =r_t(s,a)+ _s P(·|s,a)\ _a Q(s ,a )\-Q_t(s,a) Using the definition of (Q)(s,a)T(Q)(s,a), =(Q)(s,a)−Qt(s,a) =T(Q)(s,a)-Q_t(s,a) Hence, from RHS we proved that ^t T_t is an unbiased estimator of T. Now, denote ℒ(X)L(X) as the distribution of the R.V. X. We need to prove that ℒ(Qt)t≥0\L(Q_t)\_t≥ 0 is a Cauchy sequence in the complete space ∞,1P_∞,1. Suppose Q0∼μQ_0 μ, and take any positive integer N>0N>0. For any k≥Nk≥ N and l≥0l≥ 0, we need to show that ∞,1(ℒ(Qk),ℒ(Qk+l))W_∞,1 (L(Q_k),L(Q_k+l) ) is bounded, where for p,q≥1p,q≥ 1, the Wasserstein distance p,qW_p,q induced from the Lp(ℝd)L^p (R^d ) space is defined by p,q(μ,ν)=infγ∈Γ(μ,ν)(∫ℝd×ℝd‖x−y‖pqdγ(x,y))1q,W_p,q(μ,ν)= _γ∈ (μ,ν) ( _R^d×R^d\|x-y\|_p^q~dγ(x,y) ) 1q, where Γ(μ,ν) (μ,ν) is the set of all couplings of μ and ν; and denote p,qP_p,q as its corresponding Wasserstein space. Consider the process (2) started from Q0(1)∼ℒ(Q0)Q_0^(1) (Q_0) and Q0(2)∼ℒ(Ql)Q_0^(2) (Q_l). In the first k iterations, we couple the two processes with the same randomness. From Lemma B.3 in xie2022statistical, ∞,1(ℒ(Qk),ℒ(Qk+l)) _∞,1 (L(Q_k),L(Q_k+l) ) =∞,1(ℒ(Qk(1)),ℒ(Qk(2))) =W_∞,1 (L(Q_k^(1)),L(Q_k^(2)) ) ≤(1−η−ηγ)k∞,1(ℒ(Q0(1)),ℒ(Q0(2))) ≤(1-η-ηγ)^kW_∞,1 (L(Q_0^(1)),L(Q_0^(2)) ) ≤(1−η−ηγ)N‖Ql−Q0‖∞. ≤(1-η-ηγ)^NE||Q_l-Q_0||_∞. Since 0≤rt(s,a)≤10≤ r_t(s,a)≤ 1, for any l≥0l≥ 0, ‖Ql+1‖∞ ||Q_l+1||_∞ =‖(1−η)Ql+η^l+1(Ql)‖∞ =E||(1-η)Q_l+η T_l+1(Q_l)||_∞ ≤‖(1−η)Ql‖∞+‖η^l+1(Ql)‖∞ \||(1-η)Q_l||_∞+||η T_l+1(Q_l)||_∞\ By linearity of expectation, =(1−η)||(Ql||∞+η||^l+1(Ql)||∞ =(1-η)E||(Q_l||_∞+ || T_l+1(Q_l)||_∞ Since the reward variable is bounded, ≤(1−η)||(Ql||∞+η+ηγB∑i=1Bmaxai′Ql(sl+1,i,ai′) ≤(1-η)E||(Q_l||_∞+η+ \ γB _i=1^B _a _iQ_l(s_l+1,i,a _i)\ By linearity of expectation, ≤(1−η)||(Ql||∞+η+ηγB∑i=1Bmaxai′Ql(sl+1,i,ai′) ≤(1-η)E||(Q_l||_∞+η+ ηγB _i=1^BE\ _a _iQ_l(s_l+1,i,a _i)\ Since the data is collected from a generative model, =(1−η)||(Ql||∞+η+ηγs′∼P(⋅|s,a)maxa′Ql(sl+1,a′) =(1-η)E||(Q_l||_∞+η+η _s P(·|s,a)\ _a Q_l(s_l+1,a )\ By the definition of ∞-norm, =(1−η)||(Ql||∞+η+ηγ||maxa′Ql(sl+1,a′)||∞ =(1-η)E||(Q_l||_∞+η+η || _a Q_l(s_l+1,a )||_∞ =(1−η+ηγ)‖Ql‖∞+η. =(1-η+ηγ)E||Q_l||_∞+η. By induction, we have for any l≥0l≥ 0, ‖Ql‖∞ ||Q_l||_∞ ≤(1−η−ηγ)lE‖Q0‖∞+η1−(1−eta+ηγ) ≤(1-η-ηγ)^lE||Q_0||_∞+ η1-(1-eta+ηγ) =(1−η−ηγ)lE‖Q0‖∞+11−γ, =(1-η-ηγ)^lE||Q_0||_∞+ 11-γ, and thus, ‖Ql‖∞E||Q_l||_∞ is uniformly bounded for all l≥0l≥ 0. As N→∞N ∞, we have ∞,1(ℒ(Qk),ℒ(Qk+l))→0W_∞,1 (L(Q_k),L(Q_k+l) ) 0, and therefore ℒ(Qt)t≥0\L(Q_t)\_t≥ 0 is a Cauchy sequence in ∞,1P_∞,1, and its limit ηQ_η exists. Uniqueness can be easily proven using Lemma B.3 from xie2022statistical. Furthermore, the remaining statements 2. and 3. can be verified similarly as provided in xie2022statistical. References