This post accompanies Crisp Supra-Decision Processes and contains the proof of the following proposition.

Proposition 1 [Alexander Appel (@Diffractor), Vanessa Kosoy (@Vanessa Kosoy)]: Let $M=(S,s_0,A,O,T,B,L,\gamma )$ be a crisp supra-MDP with geometric time discount such that $S$ and $A$ are finite. Then there exists a stationary optimal policy.

Proof: We first recall some notation. Let $A$ denote the set of actions, and let $S$ denote the set of states. Let $(A\times S{)}^{\ast }$ denote the set of histories and $(A\times S{)}^n\subset (A\times S{)}^{\ast }$ denote the set of histories of length $n$. For $h\in (A\times S{)}^{\ast }$, let $h(A\times S{)}^{\omega }$ denote the set of destinies with prefix $h.$

Throughout, we assume that $L^{\gamma }:(A\times S{)}^{\omega }\to [0,1]$ is the sum of the momentary losses at each time-step with geometric time discount $\gamma \in [0,1).$ More specifically, given $d\in (A\times S{)}^{\omega },$ we write $d=a_0{\prod }_{t=1}^{\infty }{s}_t{a}_t.$ Then $L^{\gamma }\left(d\right)$ is given by  $L^{\gamma }\left(d\right)=(1-\gamma ){\sum }_{t=0}^{\infty }{\gamma }^{t}L(s_t,a_t).$

Fix $n\in N.$ Recall that $(A\times S{)}^{\omega }$ can be written as the finite disjoint union 

This fact, together with Fubini's theorem, implies that the expected loss can be written as an iterated expectation. More concretely, let $\theta \in \Delta (A\times S{)}^{\omega }.$ Then the (classical) expected loss with respect to $\theta$ can be written as 

Equation (1) implies the following claim. Let $\Lambda$ denote a crisp causal law. Given a policy $\pi$, let ${\pi }^n$ denote the partial policy obtained by restricting $\pi$ to the first $n$ time steps. More specifically, let $(A\times O{)}^{\le n}$ denote the set of histories of length at most $n.$ Then ${\pi }^n=\pi {|}_{(A\times O{)}^{\le n}}.$ Furthermore, let ${}^h\pi$ denote the continuation of $\pi$ after a history $h,$ i.e. ${}^h\pi =\pi {|}_{h(A\times S{)}^{\ast }}$ where $h(A\times S{)}^{\ast }$ denotes the set of histories with prefix $h.$  Given a policy $\pi \in \Pi$, let $\Lambda \left({\pi }^n\right)\in \square (A\times S{)}^n$ and $\Lambda {(}^h\pi )\in \square (h(A\times S{)}^{\omega })$ denote the credal sets induced by ${\pi }^n$ and ${}^h\pi$ by restricting $\Lambda$ in the natural way.^[1]

Then using the decomposition above, the supra-expectation can be written (in a manner reminiscent of Fubini's Theorem) as

To prove (2), we use (1) and observe that

We now prove the key claim, which states that given any policy, the expected loss can only decrease by switching at some time to the policy that is optimal for the current state.

Claim: Given a policy $\pi$, let ${\pi }_n^{†}$ denote the policy obtained by following $\pi$ for the first $n$ time steps and then following the policy that is optimal for the state observed at time $n.$ Then for all $n\in N,$ 

Proof of claim: By Equation (2), 

Note that $E_{\Lambda {(}^h\pi )}\left[\right(1-\gamma \left){\sum }_{t=0}^{n-1}{\gamma }^{t}L\right(s_t,a_t\left)\right]=(1-\gamma ){\sum }_{t=0}^{n-1}{\gamma }^{t}L(s_t,a_t).$ Thus,

Since ${\pi }_n^{†}$ is optimal for the state observed at time $n,$

By monotonicity, we then have

Repeating the same argument as above,

By construction, the partial policy obtained by restricting ${\pi }_n^{†}$ to the first $n$ time steps is equal to ${\pi }^n,$ i.e. ${\pi }^n=({\pi }_n^{†}{)}^n.$ Then by Equation (2), 

Therefore,

We now apply the claim to finish the proof of the proposition. For ease of notation, let $†(\pi ,n):={\pi }_n^{†}.$ Let ${\pi }_{\ast }$ denote a given optimal policy. Define the sequence of policies $\{{\overline{\pi }}_n{\}}_{n\in N}$ recursively as follows: ${\overline{\pi }}_0:=†({\pi }_{\ast },0)$ and ${\overline{\pi }}_n=†({\overline{\pi }}_{n-1},n).$ The limit of this sequence is a stationary policy, which is optimal by the claim above. $\square$

1. ^{^}

   For ease of notation, we drop the superscripts on $\Lambda$ that appear in the main post.