Name
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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.ijar.2015.05.003 | International Journal of Approximate Reasoning |
Keywords | Field | DocType |
Influence diagrams,Probabilistic graphical models,Decision making,Local search,Parameterized complexity | Mathematical optimization,Decision problem,Parameterized complexity,Polynomial,Expected utility hypothesis,Beam search,Influence diagram,Artificial intelligence,Local search (optimization),Graphical model,Machine learning,Mathematics | Journal |
Volume | Issue | ISSN |
68 | 1 | 0888-613X |
Citations | PageRank | References |
0 | 0.34 | 19 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Denis Deratani Mauá | 1 | 165 | 24.64 |
| Fábio Cozman | 2 | 18 | 10.16 |