Fast local search methods for solving limited memory influence diagrams |
| |
Institution: | 1. Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, São Paulo 05508-090, Brazil;2. Escola Politécnica, Universidade de São Paulo, Av. Prof. Mello Moraes, 2231, São Paulo 05508-030, Brazil |
| |
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 W1]-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. |
| |
Keywords: | Influence diagrams Probabilistic graphical models Decision making Local search Parameterized complexity |
本文献已被 ScienceDirect 等数据库收录! |
|