DASA: Aproximación Estocástica Multi-Agente Adaptativa al Retraso

Consideramos un escenario en el que N agentes buscan acelerar un problema común de Aproximación Estocástica (AE) actuando en paralelo y comunicándose con un servidor central. Suponemos que las transmisiones de enlace ascendente al servidor están sujetas a retrasos asíncronos y potencialmente no acotados. Para mitigar el efecto de los retrasos y de los rezagados mientras aprovechamos los beneficios del cálculo distribuido, proponemos DASA, un algoritmo Adaptativo al Retraso para la Aproximación Estocástica multi-agente. Proporcionamos un análisis en un tiempo finito de DASA asumiendo que los procesos de observación estocástica de los agentes son cadenas de Markov independientes. Avanzando significativamente los resultados existentes, DASA es el primer algoritmo cuya tasa de convergencia depende únicamente del tiempo de mezcla y del retraso promedio ₀ₕ₆, logrando a la vez una aceleración de la convergencia en N veces bajo muestreo markoviano. Nuestro trabajo es relevante para varias aplicaciones de AE, incluyendo el aprendizaje por diferencia temporal (TD) multi-agente y distribuido, aprendizaje Q y optimización estocástica con datos correlacionados.