Formulating Decision Theory as Program Search

While the idea of maximizing expected utility is clear, precisely how to implement this idea is contested, even in theory. A number of decision theories have been proposed in the literature, however all have deficiencies. Causal Decision Theory (CDT), arguably the leading theory, makes controversial and seemingly incorrect decisions in problems with logical dependence between choices and outcomes such as Newcomb's problem. Recently, Functional Decision Theory (FDT), has been proposed which corrects these difficulties but which is somewhat opaque and relies on an uncertain theory of counterfactuals. In this note, we provide a novel and clear formulation of FDT as a program search over potential policies where both policies and the environment are represented as Turing-complete programs. We demonstrate that this representation can handle probabilistic, causal and logical dependencies straightforwardly while also being simple and intuitive to understand and avoiding philosophical difficulties with counterfactuals. We give example formulations of Newcomb's problem and others in our framework and show that it provides insight into the differing underlying assumptions that FDT and CDT make about the environment.