A New Bounding Scheme for Influence Diagrams

02/02/2021

A New Bounding Scheme for Influence Diagrams

Radu Marinescu, Junkyu Lee, Rina Dechter

Keywords:

Abstract Paper Similar Papers

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 and therefore is notoriously difficult for larger models. In this paper, we develop a new bounding scheme for MEU that applies partitioning based approximations on top of the decomposition scheme called a multi-operator cluster DAG for influence diagrams that is more sensitive to the underlying structure of the model than the classical join-tree decomposition of influence diagrams. Our bounding scheme utilizes a cost-shifting mechanism to tighten the bound further. We demonstrate the effectiveness of the proposed scheme on various hard benchmarks.

The video of this talk cannot be embedded. You can watch it here:

https://slideslive.com/38949234

(Link will open in new window)

0

0

0

0

Share

This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment

no comments yet

Similar Papers

06/12/2021

Iterative Amortized Policy Optimization

Joseph Marino, Alexandre Piche, Alessandro Davide Ialongo, Yisong Yue

Keywords Paper

optimization, reinforcement learning and planning, generative model

0

0

0

0

5:29

06/12/2021

Multi-Agent Reinforcement Learning in Stochastic Networked Systems

Yiheng Lin, Guannan Qu, Longbo Huang, Adam Wierman

Keywords Paper

reinforcement learning and planning, graph learning

0

0

0

0

11:20

07/06/2020

Influence Maximization Using Influence and Susceptibility Embeddings

George Panagopoulos, Fragkiskos D. Malliaros, Michalis Vazirgiannis

Keywords Paper

cascades, influences, learning, networks, nodes, political, relationships, representation learning, representations, spread, terms, traditional, viral marketing

0

0

0

0

9:57

18/07/2021

On Proximal Policy Optimization's Heavy-tailed Gradients

Saurabh Garg, Joshua Zhanson, Emilio Parisotto and
Adarsh Prasad, Zico Kolter, Zachary Lipton, Sivaraman Balakrishnan, Russ Salakhutdinov, Pradeep Ravikumar

Keywords Paper

Reinforcement Learning and Planning, Deep RL

0

0

0

0

5:34

06/12/2021

Local policy search with Bayesian optimization

Sarah Müller, Alexander von Rohr, Sebastian Trimpe

Keywords Paper

theory, optimization, reinforcement learning and planning, active learning

0

0

0

0

11:42

06/12/2020

Direct Policy Gradients: Direct Optimization of Policies in Discrete Action Spaces

Guy Lorberbom, Chris J. Maddison, Nicolas Heess and
Tamir Hazan, Daniel Tarlow

Keywords Paper

0

0

0

0

3:16

02/02/2021

Submodel Decomposition Bounds for Influence Diagrams

Junkyu Lee, Radu Marinescu, Rina Dechter

Keywords Paper

0

0

0

0

19:46

06/12/2021

Federated Linear Contextual Bandits

Ruiquan Huang, Weiqiang Wu, Jing Yang, Cong Shen

Keywords Paper

bandits

0

0

0

0

14:40

14/09/2020

Temporal Heterogeneous Interaction Graph Embedding For Next-Item Recommendation

Yugang Ji, Mingyang Yin, Hongxia Yang and
Xiangwei Wang, Chuan Shi, Tianrui Jia, Yuan Fang

Keywords Paper

temporal heterogeneous interaction graph, next-item recommendation, short-term demands, long-term habits

0

0

0

0

14:47

02/02/2021

Progression Heuristics for Planning with Probabilistic LTL Constraints

Ian Mallett, Sylvie Thiebaux, Felipe Trevizan

Keywords Paper

0

0

0

0

18:23

02/02/2021

Present-Biased Optimization

Fedor V. Fomin, Pierre Fraigniaud, Petr A. Golovach

Keywords Paper

0

0

0

0

19:38

18/07/2021

Tesseract: Tensorised Actors for Multi-Agent Reinforcement Learning

Anuj Mahajan, Mikayel Samvelyan, Lei Mao and
Viktor Makoviychuk, Animesh Garg, Jean Kossaifi, Shimon Whiteson, Yuke Zhu, Anima Anandkumar

Keywords Paper

Reinforcement Learning and Planning, Multi-Agent RL

0

0

0

0

5:16

26/08/2020

Discrete Action On-Policy Learning with Action-Value Critic

Yuguang Yue, Yunhao Tang, Mingzhang Yin, Mingyuan Zhou

Keywords Paper

0

0

0

0

14:23

06/12/2021

Unifying Gradient Estimators for Meta-Reinforcement Learning via Off-Policy Evaluation

Yunhao Tang, Tadashi Kozuno, Mark Rowland and
Remi Munos, Michal Valko

Keywords Paper

reinforcement learning and planning, meta learning

0

0

0

0

12:45

26/08/2020

DYNOTEARS: Structure Learning from Time-Series Data

Roxana Pamfil, Nisara Sriwattanaworachai, Shaan Desai and
Philip Pilgerstorfer, Konstantinos Georgatzis, Paul Beaumont, Bryon Aragam

Keywords Paper

0

0

0

0

14:45

06/12/2021

Towards Robust Bisimulation Metric Learning

Mete Kemertas, Tristan Aumentado-Armstrong

Keywords Paper

reinforcement learning and planning, robustness, representation learning

0

0

0

0

12:24

02/02/2021

Bayesian Optimized Monte Carlo Planning

John Mern, Anil Yildiz, Zachary Sunberg and
Tapan Mukerji, Mykel J. Kochenderfer

Keywords Paper

0

0

0

0

18:24

06/12/2021

Learning Equilibria in Matching Markets from Bandit Feedback

Meena Jagadeesan, Alexander Wei, Yixin Wang and
Michael Jordan, Jacob Steinhardt

Keywords Paper

bandits

0

0

0

0

15:04

18/07/2021

Discovering symbolic policies with deep reinforcement learning

Mikel Landajuela Larma, Brenden Petersen, Sookyung Kim and
Claudio Santiago, Ruben Glatt, Nathan Mundhenk, Jacob Pettit, Daniel Faissol

Keywords Paper

Reinforcement Learning and Planning, Deep RL

0

0

0

0

4:55

12/07/2020

Structured Policy Iteration for Linear Quadratic Regulator

Youngsuk Park, Ryan Rossi, Zheng Wen and
Gang Wu, Handong Zhao

Keywords Paper

Reinforcement Learning - General

0

0

0

0

16:08

06/12/2021

Score-based Generative Neural Networks for Large-Scale Optimal Transport

Grady Daniels, Tyler Maunu, Paul Hand

Keywords Paper

deep learning, optimization, generative model, optimal transport

0

0

0

0

13:48

18/07/2021

On the Implicit Bias of Initialization Shape: Beyond Infinitesimal Mirror Descent

Shahar Azulay, Edward Moroshko, Mor Shpigel Nacson and
Blake Woodworth, Nati Srebro, Amir Globerson, Daniel Soudry

Keywords Paper

, Probabilistic Methods, MCMC, Theory, Deep learning Theory

0

0

0

0

15:38

06/12/2021

On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method

Junyu Zhang, Chengzhuo Ni, zheng Yu and
Csaba Szepesvari, Mengdi Wang

Keywords Paper

theory, reinforcement learning and planning

0

0

0

0

14:49

02/02/2021

Implicit Kernel Attention

Kyungwoo Song, Yohan Jung, Dongjun Kim, Il-Chul Moon

Keywords Paper

0

0

0

0

17:22

12/07/2020

Deep Coordination Graphs

Wendelin Boehmer, Vitaly Kurin, Shimon Whiteson

Keywords Paper

Reinforcement Learning - Deep RL

0

0

0

0

12:16

19/08/2021

The Parameterized Complexity of Connected Fair Division

Argyrios Deligkas, Eduard Eiben, Robert Ganian and
Thekla Hamm, Sebastian Ordyniak

Keywords Paper

Agent-based and Multi-agent Systems, Computational Social Choice, Resource Allocation

0

0

0

0

12:59

19/08/2021

Variational Model-based Policy Optimization

Yinlam Chow, Brandon Cui, Moonkyung Ryu, Mohammad Ghavamzadeh

Keywords Paper

Machine Learning, Reinforcement Learning

0

0

0

0

15:31

06/12/2020

Variational Policy Gradient Method for Reinforcement Learning with General Utilities

Junyu Zhang, Alec Koppel, Amrit Bedi and
Csaba Szepesvari, Mengdi Wang

Keywords Paper

0

0

0

0

3:20

06/12/2021

Settling the Variance of Multi-Agent Policy Gradients

Jakub Grudzien Kuba, Muning Wen, Linghui Meng and
shangding gu, Haifeng Zhang, David Mguni, Jun Wang, Yaodong Yang

Keywords Paper

deep learning, reinforcement learning and planning

0

0

0

0

13:12

18/07/2021

Active Feature Acquisition with Generative Surrogate Models

Yang Li, Junier Oliva

Keywords Paper

Deep Learning, Generative Models, Applications, Computational Biology and Bioinformatics, Reinforcement Learning and Planning, Deep RL

0

0

0

0

5:44

04/08/2021

Adaptivity in Adaptive Submodularity

Hossein Esfandiari, Amin Karbasi, Vahab Mirrokni

Keywords Paper

0

0

0

0

13:54

02/02/2021

Ranking Sets of Defeasible Elements in Preferential Approaches to Structured Argumentation: Postulates, Relations, and Characterizations

Jan Maly, Johannes P. Wallner

Keywords Paper

0

0

0

0

19:08

03/08/2020

Distributed computation and reconfiguration in actively dynamic networks

Othon Michail, George Skretas, Paul G. Spirakis

Keywords Paper

polylogarithmic time, distributed algorithms, edge complexity, transformation, reconfiguration, dynamic networks

0

0

0

0

24:10

02/02/2021

Improved Knowledge Modeling and Its Use for Signaling in Multi-Agent Planning with Partial Observability

Shashank Shekhar, Ronen I. Brafman, Guy Shani

Keywords Paper

0

0

0

0

18:22

13/04/2021

Stochastic bandits with linear constraints

Aldo Pacchiano, Mohammad Ghavamzadeh, Peter Bartlett, Heinrich Jiang

Keywords Paper

0

0

0

0

3:02

06/12/2021

Factored Policy Gradients: Leveraging Structure for Efficient Learning in MOMDPs

Thomas Spooner, Nelson Vadori, Sumitra Ganesh

Keywords Paper

bandits

0

0

0

0

14:40

18/07/2021

A Wasserstein Minimax Framework for Mixed Linear Regression

Theo Diamandis, Yonina Eldar, Alireza Fallah and
Farzan Farnia, Asuman Ozdaglar

Keywords Paper

Algorithms, Multimodal Learning

0

0

0

0

25:41

06/12/2020

SurVAE Flows: Surjections to Bridge the Gap between VAEs and Flows

Didrik Nielsen, Priyank Jaini, Emiel Hoogeboom and
Ole Winther, Max Welling

Keywords Paper

0

0

0

0

3:17

09/07/2020

Adaptive Submodular Maximization under Stochastic Item Costs

Srinivasan Parthasarathy

Keywords Paper

Combinatorial optimization, Approximation algorithms, Non-convex optimization, Stochastic optimization

0

0

0

0

13:24

26/08/2020

Learning Hierarchical Interactions at Scale: A Convex Optimization Approach

Hussein Hazimeh, Rahul Mazumder

Keywords Paper

0

0

0

0

15:07