Dynamic programming in in uence diagrams with decision circuits
This work provides an incremental improvement for researchers and practitioners in decision analysis and probabilistic graphical models.
The paper tackles the problem of constructing compact decision circuits for dynamic programming in influence diagrams with separable value functions and conditionally independent subproblems, resulting in more efficient evaluation and sensitivity analysis.
Decision circuits perform efficient evaluation of influence diagrams, building on the ad- vances in arithmetic circuits for belief net- work inference [Darwiche, 2003; Bhattachar- jya and Shachter, 2007]. We show how even more compact decision circuits can be con- structed for dynamic programming in influ- ence 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 "lo- cal" structure for efficient evaluation and sen- sitivity analysis.