EAGER: Exploiting a myopic opponent in imperfect-information games: Toward medical applications

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

Living organisms adapt to challenges through evolution and adaptation. These survival mechanisms have proven to be a key difficulty in developing therapies, since the challenged organisms develop resistance. It would be desirable to be able to harness evolution and adaptation for therapeutic and technological goals. For example, through a sequence of appropriate manipulations, could we get a heterogeneous population of cancer cells to evolve to benign ones? Or, could we steer the evolution of the population to a state where we can destroy it? Could we evolve bacteria that eat toxins from the environment? The PI proposes this to be done using computational game theory approaches. Biological opponents have a distinct weakness that can be exploited: evolution and adaptation is myopic - it does not look ahead in the game tree. The PI proposes to develop techniques for exploiting opponents that cannot look ahead in imperfect-information games. This project will set the stage for opponent-exploitation approaches to battling diseases in a broad range of context by computationally exploiting the diseases' myopic evolution/adaptation. This applies to basically an unlimited number of diseases (at the population, individual, and drug design levels), to synthetic biology (without inserting foreign genetic material), and to asking fundamental questions in our ability to steer evolution/adaptation. The work thus has the potential to pave the way for exceptionally broad impact. The proposed work has significant educational impact as well, beyond training and mentoring a PhD student working on this project. The PI will incorporate some of the most important results from the proposed research into his PhD-level courses Advanced AI and Foundations of Electronic Marketplaces. He also proposes to give talks and tutorials on these topics. Living organisms adapt to challenges through evolution and adaptation. These survival mechanisms have proven to be a key difficulty in developing therapies, since the challenged organisms develop resistance. It would be desirable to be able to harness evolution and adaptation for therapeutic and technological goals. For example, through a sequence of appropriate manipulations, could we get a heterogeneous population of cancer cells to evolve to benign ones? Or, could we steer the evolution of the population to a state where we can destroy it? Could we evolve bacteria that eat toxins from the environment? The PI proposes this to be done using computational game theory approaches. Biological opponents have a distinct weakness that can be exploited: evolution and adaptation is myopic - it does not look ahead in the game tree. The PI proposes to develop techniques for exploiting opponents that cannot look ahead in imperfect-information games. The proposed work has three intellectual foci. First, extending an IJCAI-15 paper by Kroer and Sandholm to handle the setting where the myopic opponent's node evaluation is not known exactly, but rather with uncertainty. Second, developing game abstraction techniques that leverage the opponent's myopia. Third, developing game representations that are tractable in settings where the opponent is a population (e.g., of cells) rather than an individual.