2019/02/19 by Axel Parmentier, Parmentier, Axel, Victor Cohen +7
Computer Science · #Bayesian Modeling and Causal Inference #FOS: Mathematics #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.1902.07039
openalex publication_date 2019/02/19 · openalex created_date 2019/03/02 · openalex updated_date 2026/07/28
Influence Diagrams (ID) are a flexible tool to represent discrete stochastic\noptimization problems, including Markov Decision Process (MDP) and Partially\nObservable MDP as standard examples. More precisely, given random variables\nconsidered as vertices of an acyclic digraph, a probabilistic graphical model\ndefines a joint distribution via the conditional distributions of vertices\ngiven their parents. In ID, the random variables are represented by a\nprobabilistic graphical model whose vertices are partitioned into three types :\nchance, decision and utility vertices. The user chooses the distribution of the\ndecision vertices conditionally to their parents in order to maximize the\nexpected utility. Leveraging the notion of rooted junction tree, we present a\nmixed integer linear formulation for solving an ID, as well as valid\ninequalities, which lead to a computationally efficient algorithm. We also show\nthat the linear relaxation yields an optimal integer solution for instances\nthat can be solved by the "single policy update", the default algorithm for\naddressing IDs.\n