Theorem 2 (Markov optimality) — V*ₙ depends on the current state alone, Π_MD suffices, and the robust Bellman equation reduces to (16)

Let $V^*_n(h_n)=\sup_\pi V^\pi_n(h_n)$ be the robust value function of a finite horizon AMDP with horizon $N$, the supremum taken over all history dependent randomized policies, against the rectangular, history dependent adversary. Then there is a function $V^*_n(s)$ of the epoch and the state such that:

1. for all $n=0,\dots,N$ and every history $h_n$, $V^*_n(h_n)=V^*_n(s_n)$: the robust value function is a function of the current state alone;
2. for $n\in T=\{0,\dots,N-1\}$, the robust value $V^\pi_n(h_n)$ of a deterministic Markov policy depends on $h_n$ only through $s_n$, and

where $\Pi_{MD}$ is the set of deterministic Markov policies; 3. for $n\in T$ and every state $s$, the robust Bellman equation (11) reduces to

The recursion (16) is the basis of robust dynamic programming: once $V^*_{n+1}$ is known, computing $V^*_n$ reduces to the one-stage problems $\inf_{p\in\mathcal P_n(s,a)}E^p[v]$, and deterministic Markov policies lose nothing against the full class of history dependent randomized policies.

Formalization Note The state-only function is an existentially quantified $W(n,s)$; the theorem asserts that the history-based value $V^*_n(h_n)$ equals $W(n,s_n)$, rather than defining the value on states. Clause 2 makes explicit that the page's notation $V^\pi_n(s_n)$ for Markov policies is well defined. Rewards are bounded and the sets $\mathcal A_n(s)$, $\mathcal P_n(s,a)$ are nonempty (see the model definition); the sets $\mathcal P_n(s,a)$ need not be convex, and no supremum or infimum is assumed to be attained.