Top

Published in:

2020 | OriginalPaper | Chapter

An Online Learning Approach to a Multi-player N-armed Functional Bandit

Authors : Sam O’Neill, Ovidiu Bagdasar, Antonio Liotta

Published in: Numerical Computations: Theory and Algorithms

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Congestion games possess the property of emitting at least one pure Nash equilibrium and have a rich history of practical use in transport modelling. In this paper we approach the problem of modelling equilibrium within congestion games using a decentralised multi-player probabilistic approach via stochastic bandit feedback. Restricting the strategies available to players under the assumption of bounded rationality, we explore an online multiplayer exponential weights algorithm for unweighted atomic routing games and compare this with a \(\epsilon \)-greedy algorithm.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter On Linear Spline Wavelets with Shifted Supports

next chapter The Singular Value Decomposition of the Operators of the Dynamic Ray Transforms Acting on 2D Vector Fields

\((a_i; a_{-i})\) is commonly used to refer to player i’s strategy given the strategy profile \(\mathbf {a}=(a_1,\cdots ,a_i, \cdots ,a_N)\).

In general an unweighted traffic rate routes the same quantity \(k_i =k \quad \forall i \in \mathcal {N}\).

The source code is available at https://github.com/samtoneill/congestionbanditgames.

Belmega, E.V., Mertikopoulos, P., Negrel, R., Sanguinetti, L.: Online convex optimization and no-regret learning: algorithms, guarantees and applications (2018). http://arxiv.org/abs/1804.04529

Cesa-Bianchi, N., Lugosi, G.: Prediction, Learning, and Games. Cambridge University Press, Cambridge (2006)CrossRef

Cohen, J., Héliou, A., Mertikopoulos, P.: Learning with bandit feedback in potential games (2017). https://hal.archives-ouvertes.fr/hal-01643352

Gigerenzer, G., Selten, R.: Bounded Rationality: The Adaptive Toolbox. MIT Press, Cambridge (2001)

Patriksson, M.: The Traffic Assignment Problem: Models and Methods. Dover Publications, Mineola (1994)

Rosenthal, R.W.: A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2(1), 65–67 (1973). https://doi.org/10.1007/BF01737559MathSciNetCrossRefMATH

Roughgarden, T.: Routing games. In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V. (eds.) Algorithmic Game Theory, pp. 461–486. Cambridge University Press, Cambridge (2007). https://doi.org/10.1017/CBO9780511800481.020CrossRef

Vinitsky, E., et al.: Benchmarks for reinforcement learning in mixed-autonomy traffic. In: Billard, A., Dragan, A., Peters, J., Morimoto, J. (eds.) Proceedings of the 2nd Conference on Robot Learning. Proceedings of Machine Learning Research, vol. 87, pp. 399–409. PMLR (2018). http://proceedings.mlr.press/v87/vinitsky18a.html

Title: An Online Learning Approach to a Multi-player N-armed Functional Bandit
Authors: Sam O’Neill
Ovidiu Bagdasar
Antonio Liotta
Publisher: Springer International Publishing
Book: Numerical Computations: Theory and Algorithms
Print ISBN: 978-3-030-40615-8

Electronic ISBN: 978-3-030-40616-5

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-40616-5_41

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner