Dynamic programming in inuence diagrams with decision circuits

Decision circuits perform efficient evaluation of inuence diagrams, building on the ad- vances in arithmetic circuits for belief net- work inference [Darwiche, 2003; Bhattacharjya and Shachter, 2007]. We show how even more compact decision circuits can be con- structed for dynamic programming in inuflence diagrams with separable value functions and conditionally independent subproblems. Once a decision circuit has been constructed based on the diagram's "global" graphical structure, it can be compiled to exploit "local" structure for efficient evaluation and sensitivity analysis.