  Stochastic dynamic teams and games are rich models for decentralized systems
and challenging testing grounds for multi-agent learning. Previous work that
guaranteed team optimality assumed stateless dynamics, or an explicit
coordination mechanism, or joint-control sharing. In this paper, we present an
algorithm with guarantees of convergence to team optimal policies in teams and
common interest games. The algorithm is a two-timescale method that uses a
variant of Q-learning on the finer timescale to perform policy evaluation while
exploring the policy space on the coarser timescale. Agents following this
algorithm are "independent learners": they use only local controls, local cost
realizations, and global state information, without access to controls of other
agents. The results presented here are the first, to our knowledge, to give
formal guarantees of convergence to team optimality using independent learners
in stochastic dynamic teams and common interest games.

Optimization and Control