In a fully-observable Markov decision process, the agent gets to observe its current state before deciding which action to carry out. For now, assume that the Markov decision process is fully observable. A policy for an MDP specifies what the agent should do as a function of the state it is in. A stationary policy is a function $\pi :S\to A$. In a non-stationary policy the action is a function of the state and the time; we assume policies are stationary.

Given a reward criterion, a policy has an expected return, often referred to as the expected value, for every state. Let $V^{\pi }(s)$ be the expected value of following $\pi$ in state $s$. This is the utility an agent that is in state $s$ and following policy $\pi$ receives, on average. Policy $\pi$ is an optimal policy if for every policy ${\pi }^{\prime }$ and state $s$, $V^{\pi }(s)\ge V^{{\pi }^{\prime }}(s)$. That is, an optimal policy is at least as good as any other policy for every state.

For infinite-horizon problems, a stationary MDP always has an optimal stationary policy. However, for finite-stage problems, a non-stationary policy might be better than all stationary policies. For example, if the agent had to stop at time $n$, for the last decision in some state, the agent would act to get the largest immediate reward without considering the future actions, but for earlier decisions it may decide to get a lower reward immediately to obtain a larger reward later.

Value iteration is a method of computing an optimal policy for an MDP and its value.

Value iteration starts at the “end” and then works backward, refining an estimate of either $Q^{\ast }$ or $V^{\ast }$. There is really no end, so it uses an arbitrary end point. Let $V_k$ be the value function assuming there are $k$ stages to go, and let $Q_k$ be the $Q$-function assuming there are $k$ stages to go. These can be defined recursively. Value iteration starts with an arbitrary function $V_0$. For subsequent stages, it uses the following equations to get the functions for $k+1$ stages to go from the functions for $k$ stages to go:

Value iteration can either save a $V[S]$ array or a $Q[S,A]$ array. Saving the $V$ array results in less storage, but it is more difficult to determine an optimal action, and one more iteration is needed to determine which action results in the greatest value.

Figure 12.17 shows the value iteration algorithm when the $V$ array is stored. This procedure converges no matter what the initial value function $V_0$ is. An initial value function that approximates $V^{\ast }$ converges quicker than one that does not. The basis for many abstraction techniques for MDPs is to use some heuristic method to approximate $V^{\ast }$ and to use this as an initial seed for value iteration.

The value iteration algorithm of Figure 12.17 has an array for each stage, but it really only needs to store the current and previous arrays. It can update one array based on values from the other.

A common refinement of this algorithm is asynchronous value iteration. Rather than sweeping through the states to create a new value function, asynchronous value iteration updates the states one at a time, in any order, and stores the values in a single array. Asynchronous value iteration can store either the $Q[s,a]$ array or the $V[s]$ array. Figure 12.18 shows asynchronous value iteration when the $Q$-array is stored. It converges faster than value iteration and is the basis of some of the algorithms for reinforcement learning. Termination can be difficult to determine if the agent must guarantee a particular error, unless it is careful about how the actions and states are selected. Often, this procedure is run indefinitely as an anytime algorithm, where it is always prepared to give its best estimate of the optimal action in a state when asked.

Asynchronous value iteration could also be implemented by storing just the $V[s]$ array. In that case, the algorithm selects a state $s$ and carries out the update

Although this variant stores less information, it is more difficult to extract the policy. It requires one extra backup to determine which action $a$ results in the maximum value. This can be done using

Policy iteration starts with a policy and iteratively improves it. It starts with an arbitrary policy ${\pi }_0$ (an approximation to the optimal policy works best) and carries out the following steps, starting from $i=0$.

• •

  Policy evaluation: determine $V^{{\pi }_i}(S)$. The definition of $V^{\pi }$ is a set of $|S|$ linear equations in $|S|$ unknowns. The unknowns are the values of $V^{{\pi }_i}(S)$. There is an equation for each state. These equations can be solved by a linear equation solution method (such as Gaussian elimination) or they can be solved iteratively.

• •

  Policy improvement: choose ${\pi }_{i+1}(s)=\arg {\max }_a{Q}^{{\pi }_i}(s,a)$, where the $Q$-value can be obtained from $V$ using Equation 12.2. To detect when the algorithm has converged, it should only change the policy if the new action for some state improves the expected value; that is, it should set ${\pi }_{i+1}(s)$ to be ${\pi }_i(s)$ if ${\pi }_i(s)$ is one of the actions that maximizes $Q^{{\pi }_i}(s,a)$.

• •

  Stop if there is no change in the policy, if ${\pi }_{i+1}={\pi }_i$, otherwise increment $i$ and repeat.

The algorithm is shown in Figure 12.19. Note that it only keeps the latest policy and notices if it has changed. This algorithm always halts, usually in a small number of iterations. Unfortunately, solving the set of linear equations is often time consuming.

A variant of policy iteration, called modified policy iteration, is obtained by noticing that the agent is not required to evaluate the policy to improve it; it can just carry out a number of backup steps using Equation 12.2 and then do an improvement.

Policy iteration is useful for systems that are too big to be represented explicitly as MDPs. One case is when there is a large action space, and the agent does not want to enumerate all actions at each time. The algorithm also works as long as an improving action is found, and it only needs to find an improving action probabilistically, for example, by testing some promising actions, rather than all.

Suppose a controller has some parameters that can be varied. An estimate of the derivative of the cumulative discounted reward of a parameter $a$ in some context $s$, which corresponds to the derivative of $Q(a,s)$, can be used to improve the parameter. Such an iteratively improving controller can get into a local maximum that is not a global maximum. Policy iteration for state-based MDPs does not result in non-optimal local maxima, because it is possible to improve an action for a state without affecting other states, whereas updating parameters can affect many states at once.

A Markov decision process is a state-based representation. Just as in classical planning, where reasoning in terms of features can allow for more straightforward representations and more efficient algorithms, planning under uncertainty can also take advantage of reasoning in term of features. This forms the basis for decision-theoretic planning.

A dynamic decision network (DDN) can be seen in a number of different ways:

• •

  a factored representation of MDPs, where the states are described in terms of features

• •

  an extension of decision networks to allow repeated structure for indefinite or infinite-horizon problems

• •

  an extension of dynamic belief networks to include actions and rewards

• •

  an extension of the feature-based representation of actions or the CSP representation of planning to allow for rewards and for uncertainty in the effect of actions.

A dynamic decision network consists of

• •

  a set of state features

• •

  a set of possible actions

• •

  a two-stage decision network with chance nodes $F_0$ and $F_1$ for each feature $F$ (for the features at time 0 and time 1, respectively) and decision node $A_0$, such that

  • –

    the domain of $A_0$ is the set of all actions

  • –

    the parents of $A_0$ are the set of time 0 features (these arcs are often not shown explicitly)

  • –

    the parents of time 0 features do not include $A_0$ or time 1 features, but can include other time 0 features as long as the resulting network is acyclic

  • –

    the parents of time 1 features can contain $A_0$ and other time 0 or time 1 features as long as the graph is acyclic

  • –

    there are probability distributions for $P(F_0\mid parents(F_0))$ and $P(F_1\mid parents(F_1))$ for each feature $F$

  • –

    the reward function depends on any subset of the action and the features at times 0 or 1.

As in a dynamic belief network, a dynamic decision network can be unfolded into a decision network by replicating the features and the action for each subsequent time. For a time horizon of $n$, there is a variable $F_i$ for each feature $F$ and for each time $i$ for $0\le i\le n$. For a time horizon of $n$, there is a variable $A_i$ for each time $i$ for . The horizon, $n$, can be unbounded, which allows us to model processes that do not halt.

Thus, if there are $k$ features for a time horizon of $n$, there are $k\ast (n+1)$ chance nodes (each representing a random variable) and $k$ decision nodes in the unfolded network.

The parents of $A_i$ are random variables $F_i$ (so that the agent can observe the state). Each $F_{i+1}$ depends on the action $A_i$ and the features at time $i$ and $i+1$ in the same way, with the same conditional probabilities, as $F_1$ depends on the action $A_0$ and the features at time $0$ and $1$. The $F_0$ variables are modeled directly in the two-stage decision network.

If the reward comes only at the end, variable elimination for decision networks, shown in Figure 12.14, can be applied directly. Variable elimination for decision networks corresponds to value iteration. Note that in fully observable decision networks, variable elimination does not require the no-forgetting condition. Once the agent knows the state, all previous decisions are irrelevant. If rewards are accrued at each time step, the algorithm must be augmented to allow for the addition (and discounting) of rewards. See Exercise 12.19.

A partially observable Markov decision process (POMDP) is a combination of an MDP and a hidden Markov model (HMM). Whereas the state in an MPD is assumed to be fully observable, the environment state in a POMDP is partially observable, which means the agent receives partial and/or noisy observations of the environment before it has to act.

A POMDP can be expressed as the infinite extension of the decision network of Figure 12.23, which explicitly shows the belief state of the agent. The network extends indefinitely to the right.

A POMDP consists of the following variables and factors defining the external behavior of the agent:

• •

  $S$, a set of states of the world

• •

  $A$, a set of actions

• •

  $O$, a set of possible observations

• •

  $P(S_0)$, the probability distribution of the starting state

• •

  $P(S^{\prime }\mid S,A)$, the dynamics of the environment, is the probability of getting to state $S^{\prime }$ by doing action $A$ from state $S$

• •

  $R(S,A)$, the expected reward of starting in state $S$, doing action $A$

• •

  $P(O\mid S,A,R)$, the probability of observing $O$ given the state is $S$, the previous action is $A$, and the reward is $R$.

$P(S^{\prime }\mid S,A)$ and $R(S,A)$ are the same as in an MDP. The arc from $S_i$ to $O_i$ means that what the agent observes can depend on the state. The arc from $A_{i-1}$ to $O_i$ allows the agent to have actions that don’t affect the environment, but affect its observations, such as paying attention to some part of the environment. The arc from $R_{i-1}$ to $O_i$ indicates that the agent’s observation can depend on the reward received; the agent is not assumed to observe the reward directly, as sometimes the rewards are only seen in retrospect. Observing the reward can often provide hints about the state that the agent might not actually be able to observe.

Internally, an agent has

• •

  $B$, the set of possible belief states

• •

  $T(B,A,O)$, a belief state transition function, which specifies the agent’s new belief state given the previous belief state $B$, the action the agent did, $A$, and the observation, $O$; the belief state at stage $i$ is $B_i=T(B_{i-1},A_{i-1},O_i)$.

• •

  $\pi (A_i\mid B_i,O_i)$, a command function or policy, which specifies a conditional plan defining what the agent will do as a function of the belief state and the observation.

A policy might be stochastic to allow for exploration or to confound other agents. The belief-state transition function is typically deterministic, representing probability distributions, that are updated based on the action and new observations.

Planning in a POMDP involves creating both a belief state transition function and a command function. The $B_i$ variables are special in that the world does not specify the domain or structure of these variables; an agent or its designer gets to choose the structure of a belief state, and how the agent acts based on its belief state, previous action, and latest observations. The belief state encodes all that the agent has remembered about its history.

There are a number of ways to represent a belief state and to find the optimal policy:

• •

  The decision network of Figure 12.23 can be solved using variable elimination for decision networks, shown in Figure 12.14, extended to include discounted rewards. Adding the no-forgetting arcs is equivalent to a belief state being the sequence of observations and actions; $B_i$ is $A_{i-1}$ and $O_i$ appended to the sequence $B_{i-1}$. The problem with this approach is that the history is unbounded, and the size of a policy is exponential in the length of the history. This is only practical when the history is short or is deliberately cut short.

• •

  The belief state can be a probability distribution over the states of the environment. Maintaining the belief state is then the problem of filtering in the associated hidden Markov model. The problem with this approach is that, with $n$ world states, the set of belief states is an $(n-1)$-dimensional real space. The agent then needs to find the optimal function from this multidimensional real space into the actions. The value of a sequence of actions only depends on the world states; as the belief state is a probability distribution over world states, the expected value of a belief state is a linear function of the values of the world states. Not all points in ${\mathrm{\Re }}^{n-1}$ are possible belief states, only those resulting from sequences of observations are possible. Policies can be represented as a decision tree with conditions being (functions of) the observations. The observations dictate which path in the tree the agent will follow. The value function for an agent choosing the best policy for any finite look-ahead is piecewise linear and convex. Although this is simpler than a general ${\mathrm{\Re }}^{n-1}$ function, the number of conditional policies grows like $O^t$, where $O$ is the set of possible observations, and $t$ is the stage.

• •

  In general, the belief state can be anything. A belief state can include probability distributions over some of the variables, and remembered observations and actions. The agent can search over the space of controllers for the best controller. Thus, the agent searches over what to remember (the belief state) and what to do based on its belief state. Note that the first two proposals are instances of this approach: the agent’s belief state is all of its history, or the agent’s belief state is a probability distribution over world states, both of which are intractable. Because the general case is unconstrained over what to remember, the search space is enormous.