Andrew Drucker (UChicago) - Accelerating Search for Decision-Making Under Uncertainty

I will discuss my research in CS theory, with a focus on decision-making under uncertainty. A broad variety of decision-making tasks can be modeled as “games against Nature”, in which a player alternates moves with an opponent (“Nature”) who plays randomly.

For general binary-move games, I have provided an algorithm yielding rigorous exponential computational savings over brute-force search—with no assumption of bounded state-space. This provides, for the first time, a search technique in this setting of power comparable to alpha/beta-style pruning for games against adversarial opponents. I will discuss the ideas involved, which are new and much more subtle than in the adversarial setting, and which hold promise for further work.