The mathematics of Stackelberg games in machine learning: constructing categories towards powerful algorithms

点击翻译按钮获取中文摘要

A Stackelberg game is a hierarchical game of two players known as the leader (upper-level player) and follower (lower-level player). One of the key characteristics of a Stackelberg game is that it involves an order of play, which assumes that the leader makes the first move, and after observing the choice of the upper-level player, the follower reacts by selection an action that optimizes their payoff function. The decision of the follower could be in favour of the leader, which would imply that there is cooperation between the two players. However, if the lower-level player's action is not in favour of the leader, we have a non-cooperative Stackelberg game. Overall, this means that to numerically solve a Stackelberg problem, we typically need to be in one of the following four categories:(A) The implicit function model, where the follower has only a single choice for each decision of the leader.(B) The optimistic model, where the follower could have multiple options for some actions of the leader, but nevertheless makes choices that are in favour of the upper-level player.(C) The pessimistic model, in which the follower is in a position where they could have multiple options for some selections of the leader and decides to make choices that do not favour the leader.(D) The partial cooperation model, which is also based on the assumption that the follower has multiple options for some selections of the leader, but with the difference that both players make a compromise with choices that are not necessarily their best ones, in order to let the other player partially satisfied. In the last 10 to 15 years, there has been an exponential rise of applications of Stackelberg games in the field of machine learning. Overwhelmingly, the theoretical and algorithmic developments have relied on category (A) above. However, the basic assumption required for this category is that the follower only has a unique choice for any decision made by the leader. This is too strong, and obviously, implies that there is no freedom of choice for the lower-level player. This framework is not feasible for many machine learning problems. For example, in adversarial learning, where a major concern is that data used for training a model could be attacked by a malicious agent to achieve a prediction goal that is not necessarily the one that the corresponding classification task would genuinely lead to, it does not make sense to assume that any of the players would make choices that would favour the other, whether the leader (resp. follower) is that training model (resp. malicious agent) or vice-versa, as both viewpoints are possible and have been considered in the literature. Clearly, in such a case, categories (C) and (D) seem to be more tractable. More broadly, in the current literature, not much attention has been dedicated to thoroughly assess the implications of categories (A)-(D) for Stackelberg game-based machine learning problems. A consequence of this is that potentially, existing algorithms could lead to decision-making that does not accurately reflect the modelling reality. Therefore, the overall goal of this project is to conduct a feasibility study that will lead to a framework to develop powerful algorithms to solve machine learning problems that are based on the Stackelberg game paradigm. To achieve this goal, we organize the work around four objectives; i.e., (1) conduct a detailed survey on applications of Stackelberg games in machine learning; (2) study the practical validity of categories (A)-(D) in the context of Stackelberg games in machine learning; (3) construct categories for Stackelberg models in machine learning (including existence results) and build the corresponding single-level reformulations; and (4) based on the analysis from the previous three objectives, build the first draft of a grant proposal to fund an extensive study to develop powerful algorithms for Stackelberg programs in machine learning.