Search papers, labs, and topics across Lattice.
This paper analyzes the convergence rate of asynchronous Q-learning with Polyak-Ruppert averaging and polynomial step sizes, proving a high-dimensional central limit theorem for the averaged iterates. The authors establish a convergence rate of up to $n^{-1/6} \log^{4} (nS A)$ for hyper-rectangles, assuming a uniformly geometrically ergodic Markov chain for the state-action transitions. They also derive bounds for high-order moments of the algorithm's last iterate, and present a high-dimensional central limit theorem for sums of martingale differences.
Asynchronous Q-learning converges faster than you thought, with rates up to $n^{-1/6} \log^{4} (nS A)$ now proven for high-dimensional settings.
In this paper, we derive rates of convergence in the high-dimensional central limit theorem for Polyak-Ruppert averaged iterates generated by the asynchronous Q-learning algorithm with a polynomial stepsize $k^{-蠅},\, 蠅\in (1/2, 1]$. Assuming that the sequence of state-action-next-state triples $(s_k, a_k, s_{k+1})_{k \geq 0}$ forms a uniformly geometrically ergodic Markov chain, we establish a rate of order up to $n^{-1/6} \log^{4} (nS A)$ over the class of hyper-rectangles, where $n$ is the number of samples used by the algorithm and $S$ and $A$ denote the numbers of states and actions, respectively. To obtain this result, we prove a high-dimensional central limit theorem for sums of martingale differences, which may be of independent interest. Finally, we present bounds for high-order moments for the algorithm's last iterate.
