Fast local search methods for solving limited memory influence diagrams

Denis Deratani Mauá, Fábio Gagliardi CozmanInt. J. Approx. Reason 2016 · DOI · OpenReview

Abstract

Highlights • We show that k-local search on the space of strategies is W[1]-hard (hence unlikely to be polynomial). • We devise exact and approximate pruning schemes that allow for faster k-move when performing (stochastic) k-local search. • The approximate pruning is shown to be provably good in discarding strategies. • Experiments with artificial and realistic problems show that our solutions allow a trade-off in accuracy and runtime. Abstract Limited memory influence diagrams are graph-based models that describe decision problems with limited information such as planning with teams and/or agents with imperfect recall. Solving a (limited memory) influence diagram is an NP-hard problem, often approached through local search. In this work we give a closer look at k-neighborhood local search approaches. We show that finding a k-neighboring strategy that improves on the current solution is W[1]-hard and hence unlikely to be polynomial-time tractable. We also show that finding a strategy that resembles an optimal strategy (but may have low expected utility) is NP-hard. We then develop fast schema to perform approximate k-local search; experiments show that our methods improve on current local search algorithms both with respect to time and to accuracy.
BibTeX
@article{maua2016fast,
  author = {Denis Deratani Mauá and Fábio Gagliardi Cozman},
  title = {{Fast local search methods for solving limited memory influence diagrams}},
  journal = {Int. J. Approx. Reason.},
  year = {2016},
  doi = {10.1016/j.ijar.2015.05.003},
}

Loading related content...

Figure