OsloMet – Oslo Metropolitan University, Oslo, Norway"/> Carleton University, Ottowa, Canada"/>
Search
  • All Journals
Advanced Search
Search articles by Title, Author, Keywords, DOI
Submit Manuscript
7.7CiteScore
2.0Impact Factor
Advanced Search
MAP  >  The Knowledge Engineering Review
2023 Volume 38
Article Contents
Next Previous
RESEARCH ARTICLE   Open Access    

Adaptive learning with artificial barriers yielding Nash equilibria in general games

  • OsloMet – Oslo Metropolitan University, Oslo, Norway

  • Carleton University, Ottowa, Canada

More Information
  • Corresponding author: Corresponding author: Ismail Hassan; Email: ismail@oslomet.no 
  • Abstract: Artificial barriers in Learning Automata (LA) is a powerful and yet under-explored concept although it was first proposed in the 1980s. Introducing artificial non-absorbing barriers makes the LA schemes resilient to being trapped in absorbing barriers, a phenomenon which is often referred to as lock in probability leading to an exclusive choice of one action after convergence. Within the field of LA and reinforcement learning in general, there is a sacristy of theoretical works and applications of schemes with artificial barriers. In this paper, we devise a LA with artificial barriers for solving a general form of stochastic bimatrix game. Classical LA systems possess properties of absorbing barriers and they are a powerful tool in game theory and were shown to converge to game’s of Nash equilibrium under limited information. However, the stream of works in LA for solving game theoretical problems can merely solve the case where the Saddle Point of the game exists in a pure strategy and fail to reach mixed Nash equilibrium when no Saddle Point exists for a pure strategy.Furthermore, we provide experimental results that are in line with our theoretical findings.
  • 加载中
  • Apostolopoulos , P. A., Tsiropoulou , E. E. & Papavassiliou , S. 2018. Game-theoretic learning-based QoS satisfaction in autonomous mobile edge computing. In 2018 Global Information Infrastructure and Networking Symposium (GIIS), 1–5. https://doi.org/10.1109/GIIS.2018.8635770.

    Google Scholar

    Bloembergen , D. et al. 2015. Evolutionary dynamics of multi-agent learning: A survey. Journal of Artificial Intelligence Research 53, 659–697.

    Google Scholar

    Cao , H. & Cai , J. 2018. Distributed opportunistic spectrum access in an unknown and dynamic environment: A stochastic learning approach. IEEE Transactions on Vehicular Technology 67(5), 4454–4465.

    Google Scholar

    De Jong , S., Uyttendaele , S. & Tuyls , K. 2008. Learning to reach agreement in a continuous ultimatum game. Journal of Artificial Intelligence Research 33, 551–574.

    Google Scholar

    Do , C. T., et al. 2017. Game theory for cyber security and privacy. ACM Computing Surveys (CSUR) 50(2), 1–37.

    Google Scholar

    Fielder , A. 2020. Modelling the impact of threat intelligence on advanced persistent threat using games. In From Lambda Calculus to Cybersecurity Through Program Analysis. Springer, 216–232.

    Google Scholar

    Gheisari , S. & Tahavori , E. 2019. CCCLA: A cognitive approach for congestion control in Internet of Things using a game of learning automata. Computer Communications 147, 40–49.

    Google Scholar

    Jia , L., et al. 2017. A distributed anti-jamming channel selection algorithm for interference mitigation-based wireless networks. In 2017 IEEE 17th International Conference on Communication Technology (ICCT), 151–155. https://doi.org/10.1109/ICCT.2017.8359621.

    Google Scholar

    John Oommen , B. 1986. Absorbing and ergodic discretized two-action learning automata. IEEE Transactions on Systems, Man, and Cybernetics 16(2), 282–293.

    Google Scholar

    Lakshmivarahan , S. and Narendra , K. S. 1982. Learning algorithms for two-person zerosum stochastic games with incomplete information: A unified approach. SIAM Journal on Control and Optimization 20(4), 541–552.

    Google Scholar

    Narendra , K. S. & Thathachar , M. A. L. 2012. Learning Automata: An Introduction. Courier Corporation.

    Google Scholar

    Narendra , K. S. & Thathachar , M. A. L. 1974. Learning automata – A survey. IEEE Transactions on Systems, Man, and Cybernetics SMC-4(4), 323–334. https://doi.org/10.1109/TSMC.1974.5408453.

    Google Scholar

    Norman , M. F. 1972. Markov Processes and Learning Models. Vol. 84. Academic Press.

    Google Scholar

    Papavassilopoulos , G. 1989. Learning algorithms for repeated bimatrix Nash games with incomplete information. Journal of Optimization Theory and Applications 62(3), 467–488.

    Google Scholar

    Rauniyar , A., et al. 2020. A reinforcement learning based game theoretic approach for distributed power control in downlink NOMA. In 2020 IEEE 19th International Symposium on Network Computing and Applications (NCA), 1–10. https://doi.org/10.1109/NCA51143.2020. 9306737.

    Google Scholar

    Saraydar , C. U., Mandayam , N. B. & Goodman , D. J. 2002. Efficient power control via pricing in wireless data networks. IEEE Transactions on Communications 50(2), 291–303.

    Google Scholar

    Sastry , P. S., Phansalkar , V. V. & Thathachar , M. A. L. 1994. Decentralized learning of Nash equilibria in multi-person stochastic games with incomplete information. IEEE Transactions on Systems, Man, and Cybernetics 24(5), 769–777.

    Google Scholar

    Schaerf , A., Shoham , Y. & Tennenholtz , M. 1994. Adaptive load balancing: A study in multi-agent learning. Journal of Artificial Intelligence Research 2, 475–500.

    Google Scholar

    Sokri , A. 2020. Game theory and cyber defense. In Games in Management Science 280, 335–352.

    Google Scholar

    Thapa , R., et al. 2017. A learning automaton-based scheme for scheduling domestic shiftable loads in smart grids. IEEE Access 6, 5348–5361.

    Google Scholar

    Tian , D., et al. 2017. Self-organized relay selection for cooperative transmission in vehicular ad-hoc networks. IEEE Transactions on Vehicular Technology 66(10), 9534–9549.

    Google Scholar

    Vadori , V., et al. 2015. Jamming in underwater sensor networks as a Bayesian zerosum game with position uncertainty. In 2015 IEEE Global Communications Conference (GLOBECOM). IEEE, 1–6.

    Google Scholar

    Viswanathan , R. & Narendra , K. S. 1974. Games of stochastic automata. IEEE Transactions on Systems, Man, and Cybernetics SMC-4(1), 131–135. https://doi.org/10.1109/TSMC.1974.5408539.

    Google Scholar

    Xing , Y. & Chandramouli , R. 2008. Stochastic learning solution for distributed discrete power control game in wireless data networks. IEEE/ACM Transactions on Networking 16(4), 932–944.

    Google Scholar

    Yang , Z., et al. 2020. Learning automata based Q-learning for content placement in cooperative caching. IEEE Transactions on Communications 68(6), 3667–3680.

    Google Scholar

    Yazidi , A., et al. 2022. Solving sensor identification problem without knowledge of the ground truth using replicator dynamics. IEEE Transactions on Cybernetics 52(1), 16–24. https://doi.org/10.1109/TCYB.2019.2958627.

    Google Scholar

    Zhang , Z., Wang , D. & Gao , J. 2020. Learning automata-based multiagent reinforcement learning for optimization of cooperative tasks. IEEE Transactions on Neural Networks and Learning Systems 32(10), 4639–4652.

    Google Scholar

  • Cite this article

    Ismail Hassan, B. John Oommen, Anis Yazidi. 2023. Adaptive learning with artificial barriers yielding Nash equilibria in general games. The Knowledge Engineering Review 38(1), doi: 10.1017/S0269888923000103
    Ismail Hassan, B. John Oommen, Anis Yazidi. 2023. Adaptive learning with artificial barriers yielding Nash equilibria in general games. The Knowledge Engineering Review 38(1), doi: 10.1017/S0269888923000103
    shu
Download PDF

Article Metrics

Article views(59) PDF downloads(137)

Other Articles By Authors

RESEARCH ARTICLE   Open Access    

Adaptive learning with artificial barriers yielding Nash equilibria in general games

  • OsloMet – Oslo Metropolitan University, Oslo, Norway

  • Carleton University, Ottowa, Canada

  • Corresponding author: Corresponding author: Ismail Hassan; Email: ismail@oslomet.no 
  • Received: 22 February 2023
  • Revised: 22 October 2023
  • Accepted: 23 October 2023
  • Published online: 29 November 2023
The Knowledge Engineering Review  38,  2023, 38(1)  |  Cite this article

Abstract: Abstract: Artificial barriers in Learning Automata (LA) is a powerful and yet under-explored concept although it was first proposed in the 1980s. Introducing artificial non-absorbing barriers makes the LA schemes resilient to being trapped in absorbing barriers, a phenomenon which is often referred to as lock in probability leading to an exclusive choice of one action after convergence. Within the field of LA and reinforcement learning in general, there is a sacristy of theoretical works and applications of schemes with artificial barriers. In this paper, we devise a LA with artificial barriers for solving a general form of stochastic bimatrix game. Classical LA systems possess properties of absorbing barriers and they are a powerful tool in game theory and were shown to converge to game’s of Nash equilibrium under limited information. However, the stream of works in LA for solving game theoretical problems can merely solve the case where the Saddle Point of the game exists in a pure strategy and fail to reach mixed Nash equilibrium when no Saddle Point exists for a pure strategy.Furthermore, we provide experimental results that are in line with our theoretical findings.

    HTML

    • A preliminary version of this paper appeared in the 35th International FLAIRS Conference, Florida, USA, May 15–18, 2022. Also, during the course of this work, the Second Author was an Adjunct Professor with University of Agder, in Grimstad, Norway.

    • The mean is taken over the last 10% of the total number of iterations.

    Rights and permissions
    • This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.
References (27)
  • About this article
    Cite this article
    Ismail Hassan, B. John Oommen, Anis Yazidi. 2023. Adaptive learning with artificial barriers yielding Nash equilibria in general games. The Knowledge Engineering Review 38(1), doi: 10.1017/S0269888923000103
    Ismail Hassan, B. John Oommen, Anis Yazidi. 2023. Adaptive learning with artificial barriers yielding Nash equilibria in general games. The Knowledge Engineering Review 38(1), doi: 10.1017/S0269888923000103
    shu

    • Catalog

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return