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.
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.
License type:
Publisher Copyright
Funding Info:
This research / project is supported by the National Research Foundation - Campus for Research Excellence and Technological Enterprise (CREATE)
Grant Reference no. : NA