the other representations require the introduction of new variables and dummy time points
(Littman, 1997).

Definition 1 A succinct MDP is a 5-tuple M = hV, s0, A, t, ri, where V **is a set of Boolean**
variables, s0 is a propositional interpretation over V, A is a set of actions, t **is a circuit**
whose input is a pair of interpretations over V and an element of A, and r **is a circuit**
whose input is an interpretation over V.

In a succinct MDP, the set of states is factored, i.e., it is the Cartesian product of the possible values of the variables. This is why succinct MDPs have also been called "factored MDPs". The term "succinct", however, is more appropriate, as t and r **are not expressed**
as a product of something. It is also important to note that the set of actions A **is explicitly**
represented: this affects the complexity of checking the consistency of a value function, i.e., Theorem 8.

A succinct MDP M = hV, s0, A, t, ri represents the (explicit) MDP M′ = hS, s0, A, t′, r′i, where S is the set of propositional interpretations over variables V**; the transition function**
t
′is the function represented by the circuit t**; the reward function** r
′is the function represented by the circuit r**. In other words, the value of** t
′(s, s′, a**) is the output of the circuit** t when its inputs are s, s
′, and a Boolean representation of a. The same applies to r and r
′.

Planning in deterministic domains consists of finding a sequence of actions to reach a goal state. Nondeterminism introduces two complications: **first, the extent to which the**
goal is reached can only be probabilistically determined; second, the state at some time point cannot be uniquely determined from the initial state and the actions executed so far.

Planning in nondeterministic domains consists of finding the actions that lead to the best possible states (according to the reward function). Since the effects of actions are not known for sure, only an expected value of the reward can be determined. For example, if the result of applying a in the state s0 is s1 with probability 1/3 and s2 **with probability**
2/3, then the expected reward of executing a is given by r(s0) + 1/3 · r(s1**) + 2**/3 · r(s2),
since r(s0), r(s1), and r(s2) are the rewards of s0, s1, and s2**, respectively. Formally, the**
expected undiscounted reward is considered. This is the sum **of the reward of each state**
weighted by the probability of reaching it.

The second effect of nondeterminism is that the best action to **execute depends on the**
current state, which is not unambiguously determined from the initial state and the actions executed so far, as the effects of the actions are only probabilistically known. For example, executing a may lead to state s1 or s2. After a **is executed, the actual result is known. At**
this point, it may be that the best action to execute in s1 is a
′**, and is** a
′′ in s2**: the optimal**
choice depends on the current state, which cannot be unambiguously determined from the initial state and the previous actions. In the simplest case, a policy is a function that gives the best action to execute in each state. Such policies are called stationary. A policy may also depend on the past states; such policies are called history dependent.

The reward associated with a policy is the expected average reward obtained by executing, in each state, the associated action. The horizon is **assumed to be finite, i.e., only** what happens up to a given number of steps T is considered. The complexity of the problem changes according to whether the horizon T **is in unary or binary notation (Mundhenk**
et al., 2000). Informally, the assumption that the horizon is in unary notation means that the number of steps to consider is a polynomial in the size of the instance of the problem.