Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning

• URL: http://arxiv.org/abs/2002.00260v1
• Date: Sat, 1 Feb 2020 19:20:01 GMT
• Title: Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning
• Authors: Guannan Qu, Adam Wierman
• Abstract summary: We consider a general asynchronous Approximation scheme featuring a weighted infinity-norm contractive operator, and prove a bound on its finite-time convergence rate on a single trajectory. The resulting bound matches the sharpest available bound for synchronous $Q$-learning, and improves over previous known bounds for asynchronous $Q$-learning.
• Score: 12.91948651812873
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a general asynchronous Stochastic Approximation (SA) scheme featuring a weighted infinity-norm contractive operator, and prove a bound on its finite-time convergence rate on a single trajectory. Additionally, we specialize the result to asynchronous $Q$-learning. The resulting bound matches the sharpest available bound for synchronous $Q$-learning, and improves over previous known bounds for asynchronous $Q$-learning.

Related papers

• Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity [92.1840862558718]
  Ringmaster ASGD achieves optimal time complexity under arbitrarily heterogeneous computation times. This makes it the first Asynchronous SGD method to meet the theoretical lower bounds for time complexity in such scenarios.
  arXiv  Detail & Related papers  (2025-01-27T16:07:26Z)
• Quantized and Asynchronous Federated Learning [22.40154714677385]
  We develop a novel scheme, Quantized Federated AsynchronousQAL, to deal with the communication bottleneck. We prove that QAL achieves $mathtcalqr$dic convergence without requiring uniform client arrivals. We validate our theoretical findings by using standard benchmarks.
  arXiv  Detail & Related papers  (2024-09-30T21:22:41Z)
• DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
  We consider a setting in which $N$ agents aim to speedup a common Approximation problem by acting in parallel and communicating with a central server. To mitigate the effect of delays and stragglers, we propose textttDASA, a Delay-Adaptive algorithm for multi-agent Approximation.
  arXiv  Detail & Related papers  (2024-03-25T22:49:56Z)
• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  We study the non-asymptotic performance of approximation schemes with delayed updates under Markovian sampling. Our theoretical findings shed light on the finite-time effects of delays for a broad class of algorithms.
  arXiv  Detail & Related papers  (2024-02-19T03:08:02Z)
• Towards Understanding the Generalizability of Delayed Stochastic Gradient Descent [63.43247232708004]
  A gradient descent performed in an asynchronous manner plays a crucial role in training large-scale machine learning models. Existing generalization error bounds are rather pessimistic and cannot reveal the correlation between asynchronous delays and generalization. Our theoretical results indicate that asynchronous delays reduce the generalization error of the delayed SGD algorithm.
  arXiv  Detail & Related papers  (2023-08-18T10:00:27Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  We introduce an observation-matrix-based framework for fully asynchronous online Federated Learning with adversaries. Our main result is that the proposed algorithm almost surely converges to the desired mean $mu.$ We derive this convergence using a novel differential-inclusion-based two-timescale analysis.
  arXiv  Detail & Related papers  (2023-04-04T04:32:29Z)
• Predicting the State of Synchronization of Financial Time Series using Cross Recurrence Plots [75.20174445166997]
  This study introduces a new method for predicting the future state of synchronization of the dynamics of two financial time series. We adopt a deep learning framework for methodologically addressing the prediction of the synchronization state. We find that the task of predicting the state of synchronization of two time series is in general rather difficult, but for certain pairs of stocks attainable with very satisfactory performance.
  arXiv  Detail & Related papers  (2022-10-26T10:22:28Z)
• Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees [10.984101749941471]
  We introduce novel convergence results for asynchronous iterations that appear in the analysis of parallel and distributed optimization algorithms. Results are simple to apply and give explicit estimates for how the degree of asynchrony impacts the convergence rates of the iterates.
  arXiv  Detail & Related papers  (2021-09-09T19:08:56Z)
• Finite-Time Analysis for Double Q-learning [50.50058000948908]
  We provide the first non-asymptotic, finite-time analysis for double Q-learning. We show that both synchronous and asynchronous double Q-learning are guaranteed to converge to an $epsilon$-accurate neighborhood of the global optimum.
  arXiv  Detail & Related papers  (2020-09-29T18:48:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.