Convergence of heterogeneous distributed learning in stochastic routing games

Syrine Krichene, Walid Krichene, Roy Dong, Alexandre Bayen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We study convergence properties of distributed learning dynamics in repeated stochastic routing games. The game is stochastic in that each player observes a stochastic vector, the conditional expectation of which is equal to the true loss (almost surely). In particular, we propose a model in which every player m follows a stochastic mirror descent dynamics with Bregman divergence Dψm and learning rates ηtm = θmt-αm. We prove that if all players use the same sequence of learning rates, then their joint strategy converges almost surely to the equilibrium set. If the learning dynamics are heterogeneous, that is, different players use different learning rates, then the joint strategy converges to equilibrium in expectation, and we give upper bounds on the convergence rate. This result holds for general routing games (no smoothness or strong convexity assumptions are required). These results provide a distributed learning model that is robust to measurement noise and other stochastic perturbations, and allows flexibility in the choice of learning algorithm of each player. The results also provide estimates of convergence rates, which are confirmed in simulation.

Original languageEnglish (US)
Title of host publication2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages480-487
Number of pages8
ISBN (Electronic)9781509018239
DOIs
StatePublished - Apr 4 2016
Externally publishedYes
Event53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015 - Monticello, United States
Duration: Sep 29 2015Oct 2 2015

Publication series

Name2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015

Other

Other53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015
CountryUnited States
CityMonticello
Period9/29/1510/2/15

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Computer Science Applications
  • Control and Systems Engineering

Fingerprint Dive into the research topics of 'Convergence of heterogeneous distributed learning in stochastic routing games'. Together they form a unique fingerprint.

Cite this