On the complexity of solving polytree-shaped limited memory influence diagrams with binary variables

Influence diagrams are intuitive and concise representations of structured decision problems. When the problem is non-Markovian, an optimal strategy can be exponentially large in the size of the diagram. We can avoid the inherent intractability by constraining the size of admissible strategies, giving rise to limited memory influence diagrams. A valuable question is then how small do strategies need to be to enable efficient optimal planning. Arguably, the smallest strategies one can conceive simply prescribe an action for each time step, without considering past decisions or observations. Previous work has shown that finding such optimal strategies even for polytree-shaped diagrams with ternary variables and a single value node is NP-hard, but the case of binary variables was left open. In this paper we address such a case, by first noting that optimal strategies can be obtained in polynomial time for polytree-shaped diagrams with binary variables and a single value node. We then show that the same problem is NP-hard if the diagram has multiple value nodes. These two results close the fixed-parameter complexity analysis of optimal strategy selection in influence diagrams parametrized by the shape of the diagram, the number of value nodes and the maximum variable cardinality.

Solving Decision Problems with Limited Information

We present a new algorithm for exactly solving decision-making problems represented as an influence diagram. We do not require the usual assumptions of no forgetting and regularity, which allows us to solve problems with limited information. The algorithm, which implements a sophisticated variable elimination procedure, is empirically shown to outperform a state-of-the-art algorithm in randomly generated problems of up to 150 variables and 10^64 strategies.

Solving Limited Memory Influence Diagrams

We present a new algorithm for exactly solving decision making problems represented as influence diagrams. We do not require the usual assumptions of no forgetting and regularity; this allows us to solve problems with simultaneous decisions and limited information. The algorithm is empirically shown to outperform a state-of-the-art algorithm on randomly generated problems of up to 150 variables and 10^64 solutions. We show that these problems are NP-hard even if the underlying graph structure of the problem has low treewidth and the variables take on a bounded number of states, and that they admit no provably good approximation if variables can take on an arbitrary number of states.

Solving Limited Memory Influence Diagrams

We present a new algorithm for exactly solving decision making problems represented as influence diagrams. We do not require the usual assumptions of no forgetting and regularity; this allows us to solve problems with simultaneous decisions and limited information. The algorithm is empirically shown to outperform a state-of-the-art algorithm on randomly generated problems of up to 150 variables and 10^64 solutions. We show that the problem is NP-hard even if the underlying graph structure of the problem has small treewidth and the variables take on a bounded number of states, but that a fully polynomial time approximation scheme exists for these cases. Moreover, we show that the bound on the number of states is a necessary condition for any efficient approximation scheme.

The Complexity of Approximately Solving Influence Diagrams

Influence diagrams allow for intuitive and yet precise description of complex situations involving decision making under uncertainty. Unfortunately, most of the problems described by influence diagrams are hard to solve. In this paper we discuss the complexity of approximately solving influence diagrams. We do not assume no-forgetting or regularity, which makes the class of problems we address very broad. Remarkably, we show that when both the treewidth and the cardinality of the variables are bounded the problem admits a fully polynomial-time approximation scheme.

Rapid tryptophan depletion improves decision-making cognition in healthy humans without affecting reversal learning or set shifting

Rapid tryptophan (Trp) depletion (RTD) has been reported to cause deterioration in the quality of decision making and impaired reversal learning, while leaving attentional set shifting relatively unimpaired. These findings have been attributed to a more powerful neuromodulatory effect of reduced 5-HT on ventral prefrontal cortex (PFC) than on dorsolateral PFC. In view of the limited number of reports, the aim of this study was to independently replicate these findings using the same test paradigms. Healthy human subjects without a personal or family history of affective disorder were assessed using a computerized decision making/gambling task and the CANTAB ID/ED attentional set-shifting task under Trp-depleted (n=17; nine males and eight females) or control (n=15; seven males and eight females) conditions, in a double-blind, randomized, parallel-group design. There was no significant effect of RTD on set shifting, reversal learning, risk taking, impulsivity, or subjective mood. However, RTD significantly altered decision making such that depleted subjects chose the more likely of two possible outcomes significantly more often than controls. This is in direct contrast to the previous report that subjects chose the more likely outcome significantly less often following RTD. In the terminology of that report, our result may be interpreted as improvement in the quality of decision making following RTD. This contrast between studies highlights the variability in the cognitive effects of RTD between apparently similar groups of healthy subjects, and suggests the need for future RTD studies to control for a range of personality, family history, and genetic factors that may be associated with 5-HT function.