publication . Article . Preprint . Other literature type . 2018

Stochastic Stability Of Perturbed Learning Automata In Positive-Utility Games

Chasparis, Georgios;
Open Access English
  • Published: 01 Jan 2018
  • Publisher: Zenodo
Abstract
This paper considers a class of reinforcement-based learning (namely, perturbed learning automata) and provides a<br> stochastic-stability analysis in repeatedly-played, positive-utility, strategic-form games. Prior work in this class of learning dynamics primarily analyzes asymptotic convergence through stochastic approximations, where convergence can be associated with the limit points of an ordinary-differential equation (ODE). However, analyzing global convergence through an ODE-approximation requires the existence of a Lyapunov or a potential function, which naturally restricts the analysis to a fine class of games. To overcome these limitations, this pa...
Subjects
free text keywords: Learning automata, distributed optimization, stochastic stability, Computer Science - Computer Science and Game Theory
Funded by
EC| RePhrase
Project
RePhrase
REfactoring Parallel Heterogeneous Resource-Aware Applications - a Software Engineering Approach
  • Funder: European Commission (EC)
  • Project Code: 644235
  • Funding stream: H2020 | RIA
35 references, page 1 of 3

[1] G. C. Chasparis, “Stochastic stability analysis of perturbed learning automata with constant step-size in strategic-form games,” in American Control Conference, Seattle, USA, 2017, pp. 4607-4612. [OpenAIRE]

[2] B. G. Chun, R. Fonseca, I. Stoica, and J. Kubiatowicz, “Characterizing selfishly constructed overlay routing networks,” in Proc. of IEEE INFOCOM 04, Hong-Kong, 2004.

[3] R. Komali, A. B. MacKenzie, and R. P. Gilles, “Effect of selfish node behavior on efficient topology design,” IEEE Transactions on Mobile Computing, vol. 7, no. 9, pp. 1057-1070, 2008.

[4] G. Wei, A. V. Vasilakos, Y. Zheng, and N. Xiong, “A game-theoretic method of fair resource allocation for cloud computing services,” The Journal of Supercomputing, vol. 54, no. 2, pp. 252-269, Nov. 2010.

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

[6] T. Bo¨rgers and R. Sarin, “Learning through reinforcement and replicator dynamics,” J. Econ. Theory, vol. 77, no. 1, pp. 1-14, 1997.

[7] I. Erev and A. Roth, “Predicting how people play games: reinforcement learning in experimental games with unique, mixed strategy equilibria,” Amer. Econ. Rev., vol. 88, pp. 848-881, 1998. [OpenAIRE]

[8] E. Hopkins and M. Posch, “Attainability of boundary points under reinforcement learning,” Games Econ. Behav., vol. 53, pp. 110-125, 2005.

[9] A. Beggs, “On the convergence of reinforcement learning,” J. Econ. Theory, vol. 122, pp. 1-36, 2005.

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

[11] 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.

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

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

[14] 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.

[15] D. Leslie, “Reinforcement learning in games,” Ph.D. dissertation, School of Mathematics, University of Bristol, 2004.

35 references, page 1 of 3
Abstract
This paper considers a class of reinforcement-based learning (namely, perturbed learning automata) and provides a<br> stochastic-stability analysis in repeatedly-played, positive-utility, strategic-form games. Prior work in this class of learning dynamics primarily analyzes asymptotic convergence through stochastic approximations, where convergence can be associated with the limit points of an ordinary-differential equation (ODE). However, analyzing global convergence through an ODE-approximation requires the existence of a Lyapunov or a potential function, which naturally restricts the analysis to a fine class of games. To overcome these limitations, this pa...
Subjects
free text keywords: Learning automata, distributed optimization, stochastic stability, Computer Science - Computer Science and Game Theory
Funded by
EC| RePhrase
Project
RePhrase
REfactoring Parallel Heterogeneous Resource-Aware Applications - a Software Engineering Approach
  • Funder: European Commission (EC)
  • Project Code: 644235
  • Funding stream: H2020 | RIA
35 references, page 1 of 3

[1] G. C. Chasparis, “Stochastic stability analysis of perturbed learning automata with constant step-size in strategic-form games,” in American Control Conference, Seattle, USA, 2017, pp. 4607-4612. [OpenAIRE]

[2] B. G. Chun, R. Fonseca, I. Stoica, and J. Kubiatowicz, “Characterizing selfishly constructed overlay routing networks,” in Proc. of IEEE INFOCOM 04, Hong-Kong, 2004.

[3] R. Komali, A. B. MacKenzie, and R. P. Gilles, “Effect of selfish node behavior on efficient topology design,” IEEE Transactions on Mobile Computing, vol. 7, no. 9, pp. 1057-1070, 2008.

[4] G. Wei, A. V. Vasilakos, Y. Zheng, and N. Xiong, “A game-theoretic method of fair resource allocation for cloud computing services,” The Journal of Supercomputing, vol. 54, no. 2, pp. 252-269, Nov. 2010.

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

[6] T. Bo¨rgers and R. Sarin, “Learning through reinforcement and replicator dynamics,” J. Econ. Theory, vol. 77, no. 1, pp. 1-14, 1997.

[7] I. Erev and A. Roth, “Predicting how people play games: reinforcement learning in experimental games with unique, mixed strategy equilibria,” Amer. Econ. Rev., vol. 88, pp. 848-881, 1998. [OpenAIRE]

[8] E. Hopkins and M. Posch, “Attainability of boundary points under reinforcement learning,” Games Econ. Behav., vol. 53, pp. 110-125, 2005.

[9] A. Beggs, “On the convergence of reinforcement learning,” J. Econ. Theory, vol. 122, pp. 1-36, 2005.

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

[11] 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.

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

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

[14] 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.

[15] D. Leslie, “Reinforcement learning in games,” Ph.D. dissertation, School of Mathematics, University of Bristol, 2004.

35 references, page 1 of 3
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Article . Preprint . Other literature type . 2018

Stochastic Stability Of Perturbed Learning Automata In Positive-Utility Games

Chasparis, Georgios;