Central Limit Theorems for Asynchronous Averaged Q-Learning
Xingtu Liu · 2025
Read Central Limit Theorems for Asynchronous Averaged Q-Learning by Xingtu Liu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-18964.txt.
Introduction
Xingtu Liu, writing alone, proves limit theorems for a workhorse method of reinforcement learning called Q-learning. In Q-learning an agent learns the value of each action in each state from rewards it collects. The version studied here updates entries at uneven times, as data arrives, and then averages the results over time, a scheme tied to the names Polyak and Ruppert.
Liu proves a central limit theorem for the averaged values, the kind of result that says errors settle into a bell-shaped distribution. The proof gives an explicit rate that depends on the number of steps, the size of the state-action space, the discount factor, and how well the agent explores. A second result shows the running sums of the process behave like Brownian motion, the standard model of a random walk.
Catalog record
| CREATOR | Xingtu Liu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-18964
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Central Limit Theorems for Asynchronous Averaged Q-Learning Xingtu Liu Abstract This paper establishes central limit theorems for Polyak–Ruppert averaged Q-learning under asynchronous updates. We present a non-asymptotic central limit theorem, where the convergence rate in Wasserstein distance explicitly reflects the dependence on the number of iterations, state–action space size, the discount factor, and the quality of exploration. In addition, we derive a functional central limit theorem, showing that the partial-sum process converges weakly to a Brownian motion. \optauthor Simon Fraser University 1 Introduction Reinforcement Learning (RL) has emerged as a powerful paradigm in artificial intelligence, achieving successes in various applications such as Atari Mnih et al. 2015 , Go Silver et al. 2016 , robot manipulation Tan et al. 2018 ; Zeng et al. 2020 , and aligning large language models to human preferences Shao et al. 2024 ; Ouyang et al. 2022 . Q-learning Watkins and Dayan 1992 , which directly learns the optimal action-value function (Q-function) from experience trajectories, is one of the most widely used RL algorithms. Stochastic approximation (SA) Benveniste et al. 2012 ; Borkar and Borkar 2008 is a general iterative framework to solve fixed-point equation problems. Since the Bellman operator in RL is a contraction map with a unique fixed point, many RL algorithms can be interpreted as instances of SA. For example, TD learning Sutton and Barto 1998 can be viewed as an instance of linear SA. Synchronous Q-learning, by contrast, is a special case of nonlinear SA with martingale noise. The asynchronous Q-learning algorithm studied in this work, however, is a nonlinear SA problem with Markovian noise. There is a growing line of work on finite-sample analysis of SA with applications to RL algorithms Wainwright 2019 ; Srikant and Ying 2019 ; Bhandari et al. 2018 ; Chen et al. 2022 ; Chen et al. 2020b ; Qu and Wierman 2020 ; Khodadadian and Zubeldia 2025 ; Chandak et al. 2025 ; Chandak 2025 . Polyak-Ruppert averaging is a classical variance-reduction technique to stabilize and accelerate SA algorithms. In this paper, we are interested in establishing central limit theorems (CLTs) for Polyak-Ruppert averaged Q-learning under asynchronous updates. Building CLTs provides a foundational understanding of the algorithm’s statistical properties. This asymptotic normality is crucial for uncertainty quantification and statistical inference in RL. Building on the seminal work by Polyak and Juditsky Polyak and Juditsky 1992 , a non-asymptotic CLT for Polyak-Ruppert averaged SGD was established Anastasiou et al. 2019 . Mou et al. 2020 ; Samsonov et al. 2025 derive non-asymptotic CLTs for linear SA with Polyak–Ruppert averaged iterates. Similar results for two-time-scale SA are also studied Han et al. 2024 ; Hu et al. 2024 ; Kong et al. 2025 . Recently, CLTs for SA with applications to RL algorithms are studied Borkar et al. 2025 . As a special case linear SA, Srikant 2024 ; Samsonov et al. 2024 derive non-asymptotic CLTs for TD-learning with averaging. However, non-asymptotic CLTs for Q-learning remain unexplored. As a special case of nonlinear SA, Q-learning is substantially more challenging to analyze than linear SA and TD learning. Functional CLTs for Polyak–Ruppert averaged synchronous Q-learning was established in Xie and Zhang 2022 ; Li et al. 2023 ; Panda et al. 2025 . Synchronous Q-learning only considers martingale noises. By contrast, asynchronous Q-learning updates a single state–action pair based on one transition sample at each iteration, which involves Markovian noises that are non-IID. Moreover, the empirical Bellman operator in synchronous Q-learning is smooth, whereas in asynchronous Q-learning, it is non-smooth. Thus, the challenges in analyzing asynchronous Q-learning come from nonlinearity, Markovian samples, and a non-smooth operator. Recently, Zhang and Xie 2024 established a functional CLT for asynchronous Q-learning with a constant stepsize. Constant stepsize does not satisfy the necessary conditions for establishing a non-asymptotic CLT, which we detail in Section 3 . To the best of our knowledge, no non-asymptotic CLT is currently known for Q-learning, even in the synchronous setting. In this work, we close this gap and prove both a non-asymptotic CLT and a functional CLT for asynchronous averaged Q-learning with decaying stepsizes. 2 Preliminaries An infinite-horizon discounted Markov decision process (MDP) is denoted by \mathcal{M} , and is defined by the tuple \langle\mathcal{S},\mathcal{A},P,r,\gamma\rangle where \mathcal{S} is the set of states, \mathcal{A} is the action set, P:\mathcal{S}\times\mathcal{A}\rightarrow\Delta_{\mathcal{S}} is the transition probability function, and \gamma\in[0,1) is the discount factor. Let \Delta_{\mathcal{A}} denotes the simplex over the action space. The action-value function (Q-function) of a stationary and stochastic policy \pi:\mathcal{S}\rightarrow\Delta_{\mathcal{A}} is defined as Q^{\pi}(s,a)=\mathbb{E}\Big[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})|s_{0}=s,a_{0}=a\Big] , where a_{t}\sim\pi(\cdot|s_{t}) and s_{t+1}\sim P(\cdot|s_{t},a_{t}) . The optimal Q-function is defined as Q^{*}:=\max_{\pi}Q^{\pi} . The value function is defined as V^{\pi}=\pi Q^{\pi} , where (\pi Q)(s):=\langle\pi(\cdot|s),Q(s,\cdot)\rangle . We also define P^{\pi}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|\times|\mathcal{S}||\mathcal{A}|} such that P^{\pi}Q=P(\pi Q) . We make the following Lipschitz assumption over a specific optimal policy. Assumption 1 . There exists an optimal policy \pi^{*} such that for Q\in\mathbb{R}^{|\mathcal{S}|\times|\mathcal{A}|} we have \|(P^{\pi}-P^{\pi^{*}})(Q-Q^{*})\|_{\infty}\leq L\|Q-Q^{*}\|^{2}_{\infty} where \pi(s):=\argmax_{a\in\mathcal{A}}Q(s,a) . The asynchronous Q-learning algorithm maintains a Q-function estimator Q_{k} and the update rule is the following: \displaystyle Q_{k+1}=Q_{k}+\alpha_{k}(F_{k}-Q_{k}) (1) where we let F_{k}=F(Q_{k},y_{k}) , y_{k}=(s_{k},a_{k},s_{k+1}) , \displaystyle[F(Q_{k},s_{k},a_{k},s_{k+1})](s,a)=\mathbbm{1}_{\{(s_{k},a_{k})=(s,a)\}}\Gamma(Q_{k},s_{k},a_{k},s_{k+1})+Q_{k}(s,a), (2) and \displaystyle\Gamma(Q_{k},s_{k},a_{k},s_{k+1})=r_{k}(s_{k},a_{k})+\gamma\max_{a}Q_{k}(s_{k+1},a)-Q_{k}(s_{k},a_{k}). \Gamma is the temporal difference in the Q-function iterate. The sample trajectory \{(s_{k},a_{k})\} is collected by the MDP under a behavior policy \pi_{b} . We define V_{k}(s):=\max_{a}Q_{k}(s,a) . Now we make the following assumption on the Markov chain, which is standard in the literature Zhang and Xie 2024 ; Zhang et al. 2022 ; Chen et al. 2021 ; Li et al. 2020 ; Qu and Wierman 2020 . Assumption 2 . \{y_{k}\}_{k\geq 0} is an irreducible and aperiodic finite state Markov chain \mathcal{M} . Under Assumption 2 , the Markov chain \mathcal{M} admits a unique stationary distribution \tilde{\mu} . We denote \tilde{S} as the state-space and \tilde{P} as the transition kernel. Next, we define the Bellman operator for the Q-function: \displaystyle[\mathcal{T}(Q)](s,a)=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim P(\cdot|s,a)}\max_{a^{\prime}\in\mathcal{A}}Q(s^{\prime},a^{\prime}). Define \pi_{k} such that \mathcal{T}(Q_{k})=r+\gamma\pi_{k}Q_{k} . Denote by \bar{F}_{k} the expected value of F(Q_{k},y_{k}) , i.e. \bar{F}_{k}:=\bar{F}(Q_{k}):=\mathbb{E}_{y_{k}\sim\tilde{\mu}}[F(Q_{k},y_{k})] . Further, denote by D\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|\times|\mathcal{S}||\mathcal{A}|} the diagonal matrix with \{p(s,a)\}_{(s,a)\in\mathcal{S}\times\mathcal{A}} on its diagonal, where p(s,a) is the stationary visitation probability of the state-action pair (s,a) . We denote \rho:=\underset{(s,a)\in\mathcal{S}\times\mathcal{A}}{\min}p(s,a) , which captures the quality of exploration. The following lemma is a consequence of Assumption 2 . Lemma 3 (Proposition 3.1 in Chen et al. 2021 ) . Suppose that Assumption 2 holds, we have \bar{F}(Q)=D\mathcal{T}(Q)+(I-D)Q. We denote the Markov chain mixing time at iteration k as t_{k} . Formally, the mixing time t_{k} of the Markov chain \mathcal{M} is defined as t_{k}:=\min\{i\geq 0:\max_{s\in\tilde{S}}\|\tilde{P}^{i}(s,\cdot)-\tilde{\mu}(\cdot)\|_{\text{TV}}\leq\alpha_{k}\} . 3 Main Results In this section, we present our main results. We first establish a non-asymptotic CLT for the averaged Q-learning iterates, providing an explicit rate at which their distribution approaches a normal distribution. The deviation is measured by using the 1-Wasserstein distance. We then derive a functional central limit theorem (FCLT), showing that the partial-sum process converges weakly to a Brownian motion. 3.1 Non-Asymptotic Central Limit Theorem Let \Delta_{k}=Q_{k}-Q^{*} . Our goal is to study the rate at which \frac{1}{\sqrt{K}}\sum_{k=1}^{K}\Delta_{k} converges in distribution to normality. We present the main result as follows, where we use big O notation to hide all constants. Theorem 4 . Let \alpha_{k}=\alpha(k+b)^{-\beta} for some constants \alpha,b>0 and \beta\in(0.5,1) . Under Assumption 1 and 2