We want to discuss making several decisions over time.

Let $A^{1}$ be a set of actions and $\mathcal{O}^1 = \set{O^{1}_a}$ a family of outcome sets. Define $H^1 = \Set*{(a, o)}{a \in A^1, o \in O^{1}_a}$. Let $\mathcal{A} ^2 = \set{A^{2}_{h^1}}_{h^1 \in H^1}$ be a family of action sets. Define

\[ \tilde{H}^{2} = \Set*{(a_1, o_1, a_2)}{(a_1, o_1) \in H^1, a_2 \in A^{2}_{a_1o_1}}. \]

Let $\mathcal{C}^2 = \set{O^{2}_{h}}_{h \in \tilde{H}^2}$ be a family of outcome sets. Define\[ H^2 = \Set{(a_1, o_1, a_2, o_2)}{h = (a_1, o_1, a_2) \in \tilde{H}^2, o_2 \in O_{h}}. \]

Let $\preceq$ be a total order on $H^2$. Then we call the sequence $((A^1, \mathcal{A} ^2), (\mathcal{O}^1, \mathcal{O}^2), \preceq)$ a two-stage decision problem.In general, let $\mathcal{A} ^{i} = \set{A^i_{h}}_{h \in H^{i-1}}$ be a family of action sets, define $\tilde{H}^i$ by

\[ \Set*{(a_1, \dots , o_{i-1}, a_i)}{h = (a_1, \dots , o_{i-1}) \in H^{i-1}, a_i \in A^i_{h}}. \]

Let $\mathcal{O}^{i+1} = \set{O^{i+1}_{h}}_{h \in \tilde{H}^{i}}$ be a family of outcome sets. Define $H^{i}$ by\[ \Set*{(a_1, \dots , a_i, o_i)}{h = (a_1, \dots , a_i) \in \tilde{H}^{i}, o_i \in O^i_{h}}. \]

For $i = 3, \dots , n$. Let $\preceq$ be a total order on $H^{n}$. We call $H^i$ the histories until time $i$. In this case we identify $\mathcal{A} ^1 = A^1$ and call $((\mathcal{A} ^i)_{i = 1}^{n}, (\mathcal{O}^i)_{i = 1}^{n}, \preceq)$ an $n$-stage decision problem (or multi-stage decision problem or sequential decision problem).Discussing $n$-stage decision problems is complicated, as the notation indicates. How can we simplify thinking about them?

One simplification occurs when the outcome sets at stage $i$ do not depend on the action taken, or on the history of actions. In this case, we may discuss outcome sets $O^i$ for $i = 1, \dots , n$.

Another simplification occurs when the decisions to be made at each stage do not depend on the action taken or on the history of actions. In this case, we may discuss action sets $A^i$ for $i = 1, \dots , n$.

An even greater simplification occurs when the
outcome and actions sets do not depend on the
stage $i$.
In this case, we speak of *the* action
set and *the* outcome set.

Often we can summarize the history $H^i$ with a set $\mathcal{X} _i$. In this case, we speak of the set of states $S_i$ for $i = 1, \dots , n$. In this case, we can associate the history $H^1$ with an element of $S^1$. We can associate the history $H^2$ with an element of $S^2$. And so on.

Naturally, the current action affects the future
states, but not the current or past states,
since the state is a “summary” of the history,
of the “past”.^{3}

In this way, the state is a “link” between the “past” and the “future.” The idea is that the current action affects the future state, but not current or past states.

- Future editions will clarify these definitions. ↩︎
- Future editions will move this toState Representations. ↩︎
- Other language includes “sufficient statistic , but we will avoid this for now. Future sheets may modify.” ↩︎