A Weighted Mini-Bucket Bound for Solving Influence Diagram

Junkyu Lee, Radu Marinescu, Alexander Ihler, Rina Dechter
Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, PMLR 115:1159-1168, 2020.

Abstract

Influence diagrams provide a modeling and inference framework for sequential decision problems, representing the probabilistic knowledge by a Bayesian network and the preferences of an agent by utility functions over the random variables and decision variables. The time and space complexity of computing the maximum expected utility (MEU) and its maximizing policy are exponential in the induced width of the underlying graphical model, which is often prohibitively large. In this paper, we develop a weighted mini-bucket approach for bounding the MEU. These bounds can be used as a stand-alone approximation that can be improved as a function of a controlling i-bound parameter, or as a heuristic function to guide subsequent search. We evaluate the scheme empirically against the current state of the art, illustrating its potential.

Cite this Paper

BibTeX
@InProceedings{pmlr-v115-lee20c, title = {A Weighted Mini-Bucket Bound for Solving Influence Diagram}, author = {Lee, Junkyu and Marinescu, Radu and Ihler, Alexander and Dechter, Rina}, booktitle = {Proceedings of The 35th Uncertainty in Artificial Intelligence Conference}, pages = {1159--1168}, year = {2020}, editor = {Adams, Ryan P. and Gogate, Vibhav}, volume = {115}, series = {Proceedings of Machine Learning Research}, month = {22--25 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v115/lee20c/lee20c.pdf}, url = {https://proceedings.mlr.press/v115/lee20c.html}, abstract = {Influence diagrams provide a modeling and inference framework for sequential decision problems, representing the probabilistic knowledge by a Bayesian network and the preferences of an agent by utility functions over the random variables and decision variables. The time and space complexity of computing the maximum expected utility (MEU) and its maximizing policy are exponential in the induced width of the underlying graphical model, which is often prohibitively large. In this paper, we develop a weighted mini-bucket approach for bounding the MEU. These bounds can be used as a stand-alone approximation that can be improved as a function of a controlling i-bound parameter, or as a heuristic function to guide subsequent search. We evaluate the scheme empirically against the current state of the art, illustrating its potential.} }
Endnote
%0 Conference Paper %T A Weighted Mini-Bucket Bound for Solving Influence Diagram %A Junkyu Lee %A Radu Marinescu %A Alexander Ihler %A Rina Dechter %B Proceedings of The 35th Uncertainty in Artificial Intelligence Conference %C Proceedings of Machine Learning Research %D 2020 %E Ryan P. Adams %E Vibhav Gogate %F pmlr-v115-lee20c %I PMLR %P 1159--1168 %U https://proceedings.mlr.press/v115/lee20c.html %V 115 %X Influence diagrams provide a modeling and inference framework for sequential decision problems, representing the probabilistic knowledge by a Bayesian network and the preferences of an agent by utility functions over the random variables and decision variables. The time and space complexity of computing the maximum expected utility (MEU) and its maximizing policy are exponential in the induced width of the underlying graphical model, which is often prohibitively large. In this paper, we develop a weighted mini-bucket approach for bounding the MEU. These bounds can be used as a stand-alone approximation that can be improved as a function of a controlling i-bound parameter, or as a heuristic function to guide subsequent search. We evaluate the scheme empirically against the current state of the art, illustrating its potential.
APA
Lee, J., Marinescu, R., Ihler, A. & Dechter, R.. (2020). A Weighted Mini-Bucket Bound for Solving Influence Diagram. Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, in Proceedings of Machine Learning Research 115:1159-1168 Available from https://proceedings.mlr.press/v115/lee20c.html.

Related Material