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

机器学习中 Stackelberg 博弈的数学：构建强大算法的类别

• 批准号: EP/X040909/1
• 负责人: Alain Zemkoho
• 金额: $ 10.34万
• 依托单位: University of Southampton
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2023
• 资助国家: 英国
• 起止时间: 2023 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FX040909%2F1
• 关键词: mathematics; Stackelberg; games; machine; learning

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.

Stackelberg游戏是一种由两个玩家组成的分层游戏，称为领导者(上层玩家)和追随者(下级玩家)。Stackelberg游戏的关键特征之一是它涉及到一种游戏顺序，即假设领导者先走一步，在观察到上层玩家的选择后，追随者通过选择一个动作来做出反应，以优化他们的支付功能。追随者的决定可能有利于领导者，这意味着两个参与者之间存在合作。然而，如果较低级别的玩家的行动不利于领导者，我们就有一个非合作的Stackelberg游戏。总体而言，这意味着要在数值上解决Stackelberg问题，我们通常需要处于以下四个类别之一：(A)隐式函数模型，其中追随者对于领导者的每个决策只有一个选择。(B)乐观模型，其中追随者可以对领导者的某些行为有多个选择，但仍然做出有利于上层参与者的选择。(C)悲观模型，其中追随者处于这样的位置，其中他们可以对领导者的一些选择有多个选择并且决定做出不利于领导者的选择。(D)部分合作模型，这也是基于这样的假设，即追随者对于领导者的一些选择具有多个选项，但不同的是，为了让另一个参与者部分满意，两个参与者都对不一定是他们最好的选择做出了妥协。在过去的10到15年里，Stackelberg游戏在机器学习领域的应用呈指数级增长。压倒性地，理论和算法的发展依赖于上面的(A)类。然而，这一类别所需的基本假设是，追随者对领导者所做的任何决定都只有唯一的选择。这太强烈了，显然，这意味着较低级别的球员没有选择的自由。这个框架对于许多机器学习问题是不可行的。例如，在对抗性学习中，主要关注的是用于训练模型的数据可能会被恶意代理攻击，以实现不一定是相应分类任务真正导致的预测目标，因此假设任何参与者都会做出有利于另一方的选择是没有意义的，无论是领导者(resp.追随者)是培训模式(分别为恶意代理)或反之亦然，因为这两种观点都是可能的，并且已经在文献中考虑过。显然，在这种情况下，(C)和(D)类似乎更容易处理。更广泛地说，在目前的文献中，没有太多的注意力致力于彻底评估类别(A)-(D)对Stackelberg基于游戏的机器学习问题的影响。这样做的一个后果是，现有的算法可能会导致决策不能准确地反映建模现实。因此，该项目的总体目标是进行可行性研究，以开发一个框架来开发强大的算法来解决基于Stackelberg游戏范式的机器学习问题。为了实现这一目标，我们围绕四个目标组织了工作；即，(1)对Stackelberg游戏在机器学习中的应用进行详细的调查；(2)研究(A)-(D)类别在机器学习中Stackelberg游戏的实际有效性；(3)为机器学习中的Stackelberg模型构造类别(包括存在结果)并构建相应的单层重构；以及(4)基于前面三个目标的分析，建立拨款提案的初稿，以资助为机器学习中的Stackelberg程序开发强大的算法的广泛研究。