# Measurable $\epsilon$-optimal selection with an analytically measurable stochastic kernel

Let $(X, \mathcal{X})$ and $(A, \mathcal{A})$ be standard Borel spaces, $D \subseteq X \times A$ be an analytic set, and $D_x := \{a \in A : (x, a) \in D\}$ denote the $x$-section of $D$ at $x \in X$.

Also, let $c:D \rightarrow [0, \infty]$ be lower semianalytic (i.e. $\{(x, a) \in D : c(x, a) < \lambda\}$ is an analytic set for every $\lambda \geq 0$), and $p(\cdot|\cdot)$ be such that (i) $(x,a) \mapsto p(B | x, a)$ is lower semianalytic for each $B \in \mathcal{X}$, and (ii) $B \mapsto p(B | x, a)$ is a probability measure on $(X, \mathcal{X})$ for each $(x, a) \in D$.

For a lower semianalytic $u:X \rightarrow [0, \infty]$ and $(x, a) \in D$, define

$$\eta_u(x, a) := c(x, a) + \int_X u(y)p(dy | x, a).$$

Finally, let $\text{proj}_X(D) := \{x \in X : \exists a \in A \ \text{such that} \ (x, a) \in D\}$ denote the projection of $D$ into $X$, and define $\eta^*: \text{proj}_X(D) \rightarrow [0, \infty]$ for $x \in X$ by

$$\eta^*_u(x) := \inf_{a \in D_x}\eta_u(x, a).$$

Question: Given $\epsilon > 0$, does there exist a universally measurable function $\varphi:\text{proj}_X(D) \rightarrow A$ such that $\varphi(x) \in D_x$ for all $x \in X$ and, for all $x \in \text{proj}_X(D)$,

$$\eta_u(x, \varphi(x)) \leq \eta_u^*(x) + \epsilon \ \ ?$$

Comments: The answer is yes if $\eta_u$ is lower semianalytic; see e.g. Proposition 7.50(a) in this book. According to Proposition 7.48 in that same book, $\eta_u$ is lower semianalytic if $p$ is a Borel-measurable stochastic kernel. I'm wondering what else may be needed if $p$ is only analytically measurable.

Some thoughts. It does not seem likely that you can achieve existence for non-analytic $\eta$, hence I'd suggest trying to show that it is - or finding a counterexample. Let's say $c = 0$ and $u = 1_B$ where $B$ is analytic. Can you show that $p(B|x,a)$ is l.s.a.? If I am not mistaken, Proposition 7.43 of Bertsekas and Shreve suggests that $\{(x,a): p(B|x,a) \ge c\}$ is analytic for all $c$, hence your $\eta$ has co-analytic sub-level sets (as complements of analytic sets) in this case, and my guess would be lack of measurable selectors.