No-regret Sample-efficient Bayesian Optimization for Finding Nash Equilibria with Unknown Utilities

Sebastian Shenghong Tay, Quoc Phong Nguyen, Chuan Sheng Foo, Bryan Kian Hsiang Low
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:3591-3619, 2023.

Abstract

The Nash equilibrium (NE) is a classic solution concept for normal-form games that is stable under potential unilateral deviations by self-interested agents. Bayesian optimization (BO) has been used to find NE in continuous general-sum games with unknown costly-to-sample utility functions in a sample-efficient manner. This paper presents the first no-regret BO algorithm that is sample-efficient in finding pure NE by leveraging theory on high probability confidence bounds with Gaussian processes and the maximum information gain of kernel functions. Unlike previous works, our algorithm is theoretically guaranteed to converge to the optimal solution (i.e., NE). We also introduce the novel setting of applying BO to finding mixed NE in unknown discrete general-sum games and show that our theoretical framework is general enough to be extended naturally to this setting by developing a no-regret BO algorithm that is sample-efficient in finding mixed NE. We empirically show that our algorithms are competitive w.r.t. suitable baselines in finding NE.

Cite this Paper

BibTeX
@InProceedings{pmlr-v206-tay23a, title = {No-regret Sample-efficient Bayesian Optimization for Finding Nash Equilibria with Unknown Utilities}, author = {Tay, Sebastian Shenghong and Nguyen, Quoc Phong and Foo, Chuan Sheng and Low, Bryan Kian Hsiang}, booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {3591--3619}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/tay23a/tay23a.pdf}, url = {https://proceedings.mlr.press/v206/tay23a.html}, abstract = {The Nash equilibrium (NE) is a classic solution concept for normal-form games that is stable under potential unilateral deviations by self-interested agents. Bayesian optimization (BO) has been used to find NE in continuous general-sum games with unknown costly-to-sample utility functions in a sample-efficient manner. This paper presents the first no-regret BO algorithm that is sample-efficient in finding pure NE by leveraging theory on high probability confidence bounds with Gaussian processes and the maximum information gain of kernel functions. Unlike previous works, our algorithm is theoretically guaranteed to converge to the optimal solution (i.e., NE). We also introduce the novel setting of applying BO to finding mixed NE in unknown discrete general-sum games and show that our theoretical framework is general enough to be extended naturally to this setting by developing a no-regret BO algorithm that is sample-efficient in finding mixed NE. We empirically show that our algorithms are competitive w.r.t. suitable baselines in finding NE.} }
Endnote
%0 Conference Paper %T No-regret Sample-efficient Bayesian Optimization for Finding Nash Equilibria with Unknown Utilities %A Sebastian Shenghong Tay %A Quoc Phong Nguyen %A Chuan Sheng Foo %A Bryan Kian Hsiang Low %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-tay23a %I PMLR %P 3591--3619 %U https://proceedings.mlr.press/v206/tay23a.html %V 206 %X The Nash equilibrium (NE) is a classic solution concept for normal-form games that is stable under potential unilateral deviations by self-interested agents. Bayesian optimization (BO) has been used to find NE in continuous general-sum games with unknown costly-to-sample utility functions in a sample-efficient manner. This paper presents the first no-regret BO algorithm that is sample-efficient in finding pure NE by leveraging theory on high probability confidence bounds with Gaussian processes and the maximum information gain of kernel functions. Unlike previous works, our algorithm is theoretically guaranteed to converge to the optimal solution (i.e., NE). We also introduce the novel setting of applying BO to finding mixed NE in unknown discrete general-sum games and show that our theoretical framework is general enough to be extended naturally to this setting by developing a no-regret BO algorithm that is sample-efficient in finding mixed NE. We empirically show that our algorithms are competitive w.r.t. suitable baselines in finding NE.
APA
Tay, S.S., Nguyen, Q.P., Foo, C.S. & Low, B.K.H.. (2023). No-regret Sample-efficient Bayesian Optimization for Finding Nash Equilibria with Unknown Utilities. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:3591-3619 Available from https://proceedings.mlr.press/v206/tay23a.html.

Related Material