Learning Team-Optimality for Decentralized Stochastic Control and Dynamic Games
Authors:
- Bora YongacogluBYBora Yongacoglu
- Gürdal ArslanGAGürdal Arslan
- Serdar YükselSYSerdar Yüksel
Preprint
Abstract
In the study of stochastic dynamic team problems, analytical methods for finding optimal policies are often inapplicable due to lack of prior knowledge of the cost function or the state dynamics. Reinforcement learning offers a possible solution to such coordination problems. Existing learning methods for coordinating play either rely on control sharing among controllers or otherwise, in general, do not guarantee convergence to optimal policies. In a recent paper, we provided a decentralized algorithm for finding equilibrium policies in weakly acyclic stochastic dynamic games, which contain team games as an important special case. However, stochastic dynamic teams can in general possess suboptimal equilibrium policies whose cost can be arbitrarily higher than a team optimal policy's cost. In this paper, we present a reinforcement learning algorithm and its refinements, and provide probabilistic guarantees for convergence to globally optimal policies in team games as well as a more general class of coordination games. The algorithms presented here are strictly decentralized in that they require only access to local information such as cost realizations, previous local actions, and state transitions.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Decentralized Q-Learning for Stochastic Teams and GamesIEEE Transactions on Automatic Control, 2016
- A stochastic games framework for verification and control of discrete time stochastic hybrid systemsAutomatica, 2013
- Payoff-Based Dynamics for Multiplayer Weakly Acyclic GamesSIAM Journal on Control and Optimization, 2009
- If multi-agent learning is the answer, what is the question?Artificial Intelligence, 2007
- Infinite horizon common interest games with perfect informationGames and Economic Behavior, 2005
- Stochastic imitation in finite gamesGames and Economic Behavior, 2004
- Convergence Results for Single-Step On-Policy Reinforcement-Learning AlgorithmsMachine Learning, 2000
- Non zero-sum stochastic games in admission, service and routing control in queueing systemsQueueing Systems, 1996
- Team decision theory and information structuresProceedings of the IEEE, 1980
- Central Limit Theorem for Nonstationary Markov Chains. ITheory of Probability & Its Applications, 1956