EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
4210. Algorithmic Advances for Influence Diagrams
Invited abstract in session WA-34: Decision problems represented as influence diagrams, stream Stochastic, Robust and Distributionally Robust Optimization.
Wednesday, 8:30-10:00Room: 43 (building: 303A)
Authors (first author is the speaker)
| 1. | Radu Marinescu
|
| DRL AI, IBM Research Europe | |
| 2. | Junkyu Lee
|
| IBM Research | |
| 3. | Rina Dechter
|
| University of California Irvine | |
| 4. | Bobak Pezeshki
|
| University of California Irvine | |
| 5. | Alex Ihler
|
| University of California Irvine |
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. Computing the maximum expected utility (MEU) and the optimizing policy is exponential in the constrained induced width of the model and it has been long recognized as one of the most difficult probabilistic inference tasks, especially for larger problem instances. We will overview a suite of exact and approximate inference algorithms for IDs developed over the past years, starting with variable elimination (VE) schemes that use local computations to solve IDs exactly, and continuing with variational approaches based on message-passing over join-graph decompositions and weighted mini-buckets that yield variational bounds on the MEU and sub-optimal decision policies. We will also show that the latter bounding schemes can be used as heuristics generators that can guide efficient search strategies such as AND/OR search for solving IDs exactly that exploit the underlying structure of the model. We will provide experimental results on various synthetic and real-world benchmarks for IDs to highlight the performance of the inference methods presented. Finally, we will discuss recent extensions of IDs for decision making with imprecise information, multiple objectives and the potential of augmenting IDs with causal semantics.
Keywords
- Artificial Intelligence
- Decision Theory
- Algorithms
Status: accepted
Back to the list of papers