Algorithms for Large-Scale Adversarial Decision Problems

Abstract

Decision making in the presence of uncertainty received a major focus of traditional Artificial Intelligence (AI) research. In an adversarial environment with competing agents, this challenge is compounded by interdependence: a combination of the agents’ strategies determines their respective gains. Game theory provides a mathematical foundation to reason about competing strategic agents each pursuing their own interests. Recently, security games have seen tremendous success and actual deployment in homeland security, especially the models of interaction between the defender and the attacker as a Stackelberg (two player, one shot) game. This dissertation considers this conceptual idea of Stackelberg games as a natural modeling paradigm in domains beyond physical security; in cybersecurity and immunology, antibody design in particular. A key challenge is the enormous combinatorial search space corresponding to the strategy space of the players. This dissertation presents major algorithmic contributions for highly scalable decision-making in adversarial environments. It begins with the framework of plan interdiction games, motivated by attack plan models of the adversary in cybersecurity domains. While interdiction of deterministic plans is reasonably scalable, the approach scales poorly when modeling uncertainty with the at- tacker as a markov decision process (MDP). This research presents scalable algorithms using a) factored MDP solution approaches, b) value function approximation over Boolean space with Fourier representation, c) constraint generation in linear programs and d) model- free reinforcement learning. An interesting application of plan interdiction is in designing treatment therapies (vaccines) against infectious diseases, where a virus (adversary) plans to escape the antibody (defender) through a series of mutations. This dissertation presents algorithms for robust antibody design, with combinatorial optimization in the enormous protein sequence space, using data-driven graphical models of interaction and mixed integer linear programming approaches to solve the bi-level optimization problem corresponding to the game.