  Motivated by learning of correlated equilibria in non-cooperative games, we
perform a large deviations analysis of a regret minimizing stochastic
approximation algorithm. The regret minimization algorithm we consider
comprises multiple agents that communicate over a graph to coordinate their
decisions. We derive an exponential decay rate towards the algorithm's stable
point using large deviations theory. Our analysis leverages the variational
representation of the Laplace functionals and weak convergence methods to
characterize the exponential decay rate.
