Efficient Kernelized Learning in Polyhedral Games beyond Full Information: From Colonel Blotto to Congestion Games

Gabriele Farina (Massachusetts Institute of Technology) · Andreas Kontogiannis (National Technical University of Athens & Archimedes AI) · Vasilis Pollatos (National Technical University of Athens) · Panayotis Mertikopoulos (CNRS (French National Center for Scientific Research) and Archimedes Research Unit / NKUA) · Ioannis Panageas (UC Irvine)

coarse correlated equilibriacolonel blotto gamecombinatorial structurecomputational efficiencycongestion gamesgraphic matroidkernelizationlearning algorithmsnetwork congestion gamesnormal-form gamespartial information settingpayoff-based learningper-iteration complexitypolyhedral gamesregret runtime complexity

We examine the problem of efficiently learning coarse correlated equilibria (CCE) in polyhedral games, that is, normal-form games with an exponentially large number of actions per player and an underlying combinatorial structure—such as the classic Colonel Blotto game or congestion games. Achieving computational efficiency in this setting requires learning algorithms whose regret and per-iteration complexity scale at most polylogarithmically with the size of the players’ action sets. This challenge has recently been addressed in the full-information setting, primarily through the use of kernelization; however, in the more realistic partial information setting, the situation is much more challenging, and existing approaches result in suboptimal and impractical runtime complexity to learn CCE. We address this gap via a novel kernelization-based framework for payoff-based learning in polyhedral games, which we then apply to certain key classes of polyhedral games—namely Colonel Blotto, graphic matroid and network congestion games. In so doing, we obtain a range of computationally efficient payoff-based learning algorithms which significantly improve upon prior work in terms of the runtime for learning CCE.