Aspiration-based Perturbed Learning Automata

Conference object, Preprint English OPEN
Chasparis, Georgios C. (2018)
  • Related identifiers: doi: 10.5281/zenodo.1186661, doi: 10.5281/zenodo.1186662
  • Subject: Computer Science - Computer Science and Game Theory | Learning automata, distributed optimization, coordination games
    acm: TheoryofComputation_GENERAL | ComputingMilieux_PERSONALCOMPUTING
    arxiv: Computer Science::Computer Science and Game Theory

This paper introduces a novel payoff-based learning scheme for distributed optimization in repeatedly-played strategic-form games. Standard reinforcement-based learning exhibits several limitations with respect to their asymptotic stability. For example, in two-player coordination games, payoff-dominant (or efficient) Nash equilibria may not be stochastically stable. In this work, we present an extension of perturbed learning automata, namely aspiration-based perturbed learning automata (APLA) that overcomes these limitations. We provide a stochastic stability analysis in multi-player coordination games. In the case of two-player coordination games, we show that the payoff-dominant Nash equilibrium is the unique stochastically stable state.
  • References (17)
    17 references, page 1 of 2

    [1] W. B. Arthur, “On designing economic agents that behave like human agents,” J. Evolutionary Econ., vol. 3, pp. 1-22, 1993.

    [2] M. Tsetlin, Automaton Theory and Modeling of Biological Systems. Academic Press, 1973.

    [3] K. Narendra and M. Thathachar, Learning Automata: An introduction. Prentice-Hall, 1989.

    [4] J. Hu and M. P. Wellman, “Nash Q-learning for general-sum stochastic games,” J. Machine Learning Research, vol. 4, no. Nov, pp. 1039- 1069, 2003.

    [5] M. Thathachar and P. Sastry, Networks of Learning Automata: Techniques for Online Stochastic Optimization. Kluwer Academic Publishers, 2004.

    [6] G. Chasparis and J. Shamma, “Distributed dynamic reinforcement of efficient outcomes in multiagent coordination and network formation,” Dynamic Games and Applications, vol. 2, no. 1, pp. 18-50, 2012.

    [7] G. Chasparis, A. Arapostathis, and J. Shamma, “Aspiration learning in coordination games,” SIAM J. Control and Optim., vol. 51, no. 1, 2013.

    [8] G. C. Chasparis, “Stochastic Stability of Perturbed Learning Automata in Positive-Utility Games,” arXiv:1709.05859 [cs], Sept. 2017.

    [9] G. C. Chasparis, J. S. Shamma, and A. Rantzer, “Nonconvergence to saddle boundary points under perturbed reinforcement learning,” Int. J. Game Theory, vol. 44, no. 3, pp. 667-699, 2015.

    [10] J. C. Harsanyi and R. Selten, A General Theory of Equilibrium Selection in Games. Cambridge, MA: MIT Press, 1988.

  • Metrics
    No metrics available
Share - Bookmark