\begin{proof} Goal: Construct a $\gamma^{*}$ given $\gamma$ Let $u=\gamma(x,y)$.

To emphasize the random nature of the realizations $x,y,u$ we denote their corresponding rvs as $X,Y,U$.

Given some policy $\gamma$, we write for any Borel subset $D\subset \mathbb{U}$ and $x \in \mathbb{X}$, the following Stochastic Kernel $$\int\limits _{\mathbb{U}}\mathbb{1}_{\{ u\in D \}} \, \mathbb{P}(U\in du\mid x) =\mathbb{P}^{\gamma}(U\in D\mid x)=\mathbb{P}(\gamma(X,Y)\in D\mid X=x)=\int\limits _{\mathbb{Y}}\mathbb{1}_{\{ \gamma(x,y)\in D \}} \, \mathbb{P}(Y\in dy\mid X=x).$$We then have $$\begin{align*} \int\limits _{\mathbb{X}\times \mathbb{Y}}c(x,\gamma(x,y)) \, \mathbb{P}(dx,dy)&= \int\limits _{\mathbb{X}}\int\limits _{\mathbb{Y}}c(x,\gamma(x,y)) \, \mathbb{P}(dy\mid x) \, \mathbb{P}(dx) \\ &= \int\limits _{\mathbb{X}}\int\limits _{\mathbb{Y}} c(x,\gamma(x,y)) \, \mathbb{P}(Y\in dy\mid x)\, \mathbb{P}(dx)\\\\ &= \int\limits _{\mathbb{X}}\int\limits _{\mathbb{U}}c(x,u) \,\mathbb{P}^{\gamma}(U\in du\mid x) \, \mathbb{P}(dx)\\ &= \int\limits _{\mathbb{X}}\left( \int\limits _{\mathbb{U}}c(x,u) \, \mathbb{P}^{\gamma}(du\mid x) \right) \, \mathbb{P}(dx) \end{align*}$$We then denote the inner integral as follows: $$h^{\gamma}(x):=\int\limits _{\mathbb{U}}c(x,u) \, \mathbb{P}^{\gamma}(du\mid x) \tag{1}$$to get $$\int\limits _{\mathbb{X}}h^{\gamma}(x) \, \mathbb{P}(dx) .$$Now, consider the set $$D=\{ (x,u)\in \mathbb{X}\times \mathbb{U}:c(x,u)\le h^{\gamma}(x) \}$$and its $\mathbb{X}$-sections $$D_{x}:=\{ u\in\mathbb{U}:(x,u)\in D \}\quad\forall x \in \mathbb{X},$$then $$\mathbb{P}^{\gamma}(D_{x}\mid x)>0,\quad\forall x \in \mathbb{X}\tag{2}$$since otherwise we would have $$\begin{align*} \int\limits _{\mathbb{U}}c(x,u) \, \mathbb{P}^{\gamma}(du\mid x)&= \int\limits _{D_{x}^{c}}c(x,u) \, \mathbb{P}^{\gamma}(du\mid x)\\ &> h^{\gamma}(x)\int\limits _{D_{x}^{c}} \, \mathbb{P}^{\gamma}(du\mid x)\\ &= h^{\gamma}(x)\int\limits _{\mathbb{U}} \, \mathbb{P}^{\gamma}(du\mid x)\\ &= h^{\gamma}(x) \end{align*}$$which contradicts our definition in $(1)$. By some measurable selection theorem, $(2)$ implies that $\exists\gamma^{*}:\mathbb{X}\to \mathbb{U}$ such that $$\{ (x,\gamma^{*}(x)): x \in \mathbb{X} \}\subseteq D$$i.e. $c(x,\gamma^{*}(x))\le h^{\gamma}(x)$ for every $x \in \mathbb{X}$: $$\int\limits _{\mathbb{X}}c(x,\gamma^{*}(x)) \, \mathbb{P}(dx)\le \int\limits _{\mathbb{X}}h^{\gamma}(x) \, \mathbb{P}(dx)\equiv \int\limits _{\mathbb{X}\times \mathbb{Y}}c(x,\gamma(x,y)) \, \mathbb{P}(dx,dy)$$

\end{proof} >[!theorem] Ryll-Nardzewski Measurable Selection Theorem >Let $\mathbb{X},\mathbb{Y}$ be standard Borel. Let $\mathscr{A}$ be a countably-generated sub-σ-algebra of the Borel σ-algebra of $\mathbb{X}$ and let $\mathscr{B}$ be the class of Borel subsets of $\mathbb{Y}$. For any function $\mathbb{X}\times \mathscr{B}$ s.t. >1. $\mathbb{P}(x\mid\cdot)$ is for each $x$ a probability measure on $\mathscr{B}$ and >2. for each $B\in\mathscr{B}$, $\mathbb{P}(\cdot\mid B)$ is an $\mathscr{A}$-measurable function on $\mathbb{X}$, and any set $D\in\mathscr{A}\times \mathscr{B}$ s.t. $$\mathbb{P}(x,D_{x})>0,\quad \forall x \in \mathbb{X}$$where $D_{x}=\{ y:(x,y)\in D \}$. > >Then, there is a $\mathscr{A}$-measurable function $g:\mathbb{X}\to \mathbb{Y}$ whose ‘graph’ is a subset of $D$ (i.e. $(x,g(x))\in D,\forall x \in \mathbb{X}$).

Note

This is used to prove the Markov Policy is Good Enough theorem.