Each policy has an expected utility for an agent that follows the policy. A rational agent should adopt the policy that maximizes its expected utility.

A possible world specifies a value for each random variable and each decision variable. A possible world $\omega$ satisfies policy $\pi$ if for every decision variable $D$, $D(\omega )$ has the value specified by the policy given the values of the parents of $D$ in the possible world.

A possible world corresponds to a complete history and specifies the values of all random and decision variables, including all observed variables. Possible world $\omega$ satisfies policy $\pi$ if $\omega$ is one possible unfolding of history given that the agent follows policy $\pi$.

The expected utility of policy $\pi$ is

where $P(\omega )$, the probability of world $\omega$, is the product of the probabilities of the values of the chance nodes given their parents’ values in $\omega$, and $u(\omega )$ is the value of the utility $u$ in world $\omega$.

An optimal policy is a policy ${\pi }^{*}$ such that $ℰ(u\mid {\pi }^{*})\ge ℰ(u\mid \pi )$ for all policies $\pi$. That is, an optimal policy is a policy whose expected utility is maximal over all policies.

Suppose a binary decision node has $n$ binary parents. There are $2^n$ different assignments of values to the parents and, consequently, there are $2^{2^n}$ different possible decision functions for this decision node. The number of policies is the product of the number of decision functions for each of the decision variables. Even small examples can have a huge number of policies. An algorithm that simply enumerates the policies looking for the best one will be very inefficient.