I am reading the book *"Stochastic Optimal Control: The Discrete Time Case", by Bertsekas and Shreve* (hereafter called "**the Book**"), and I recently observed that a statement made in page 10 of the book (Introduction) seems that can be stated somewhat more generally.


The statement under question is described in the following:


Let $\mathscr{B}\_\mathbb{R}$, $\mathscr{B}\_{\mathbb{R}^2}$ denote the Borel $\sigma$-algebras on $\mathbb{R}$, $\mathbb{R}^2$, and consider a Borel measurable function $g:\mathbb{R}^2\rightarrow\mathbb{R}$, such that


\begin{equation}
\inf\_{u\in\mathbb{R}}g\left(x,u\right)>-\infty,\quad \forall x\in \mathbb{R}.
\end{equation}


Consider also the set of all *Borel measurable functions (policies)* from $\mathbb{R}$ to $\mathbb{R}$ and denote it by $\cal{P}$. 


**I claim** that, for any $\varepsilon>0$, there exists a Borel measurable policy $\mu\_\varepsilon\in\cal{P}$, such that


\begin{equation}
g\left(x, \mu\_\varepsilon \left(x \right) \right) \le\inf\_{u\in\mathbb{R}}g\left(x,u\right) + \varepsilon,\quad \forall x\in \mathbb{R}.
\end{equation}


In the Book, on the other hand, it is claimed that the inequality above holds only almost everywhere, with respect to some given probability measure on $\mathscr{B}\_\mathbb{R}$.


The proof of **my claim** follows.




---


First, for any measurable policy $\mu\in\cal{P}$, it holds that


\begin{equation}
g\left(x,\mu \left( x \right) \right) \ge 
\inf\_{\mu\in\cal{P}}g\left(x, \mu \left( x \right) \right) \ge
\inf\_{u\in\mathbb{R}}g\left(x,u\right)>-\infty,\quad \forall x\in \mathbb{R}.
\end{equation}


Fix an $\varepsilon>0$. Then, there exists a Borel measurable policy $\mu\_\varepsilon\in\cal{P}$, such that


\begin{equation}
g\left(x, \mu\_\varepsilon \left(x \right) \right) \le
\inf\_{\mu\in\cal{P}}g\left(x, \mu \left( x \right) \right) + \varepsilon,\quad \forall x\in \mathbb{R}.
\end{equation}


Note that such a policy may be always found, since otherwise we would be led to a contradiction: If such a policy does not exist, then it would be true that


\begin{equation}
g\left(x, \mu \left(x \right) \right) >
\inf\_{\mu\in\cal{P}}g\left(x, \mu \left( x \right) \right) + \varepsilon,\quad \forall x\in \mathbb{R},
\end{equation}


for all $\mu\in\cal{P}$, contradicting the fact that $\inf\_{\mu\in\cal{P}}g\left(x, \mu \left( x \right) \right)$ is the infimum over $\mu\in\cal{P}$. 


Now, since $\cal{P}$ is the class of all Borel measurable functions from $\mathbb{R}$ to itself, the set containing all constant policies, defined as


\begin{equation}
\mu\_u \left( x \right) \triangleq u,\quad \forall x\in\mathbb{R},
\quad\text{for some } u\in\mathbb{R},
\end{equation}


will be a *subset* of $\cal{P}$, and, therefore,


\begin{equation}
\inf\_{\mu\in\cal{P}}g\left(x, \mu \left( x \right) \right) \le
g\left(x, \mu\_u \left( x \right) \right) = g\left(x, u \right)
\quad\forall x\in\mathbb{R}\quad\text{and}\quad \forall u\in\mathbb{R}.
\end{equation}


In particular, taking infima on both sides, it will also be true that


\begin{equation}
\inf\_{\mu\in\cal{P}}g\left(x, \mu \left( x \right) \right) \le
\inf\_{u\in\mathbb{R}}g\left(x, u \right)
\quad\forall x\in\mathbb{R}.
\end{equation}


This last inequality implies that there exists $\mu\_\varepsilon\in\cal{P}$, such that


\begin{equation}
g\left(x, \mu\_\varepsilon \left(x \right) \right) \le\inf\_{u\in\mathbb{R}}g\left(x,u\right) + \varepsilon,\quad \forall x\in \mathbb{R}.
\end{equation}


for any arbitrary chosen $\varepsilon>0$, which seems to prove **my claim**.




---


Have I done anything wrong in the above derivations?
Why is it claimed in the Book that this result holds only almost everywhere in $x$?


Thanks!



Existence of ε-optimal Borel measurable policies in stochastic control
Your claim isn't true.


It's known that there exists a Borel subset $A \subset \mathbb{R} \times \mathbb{R}^+$ whose projection onto the first coordinate $B = \pi\_1(A) = \{ x : \exists y ((x,y) \in A)\}$ is not Borel. Let $$g(x,y) = \begin{cases} 0, & y > 0, (x,y) \in A \\ 1, & y > 0, (x,y) \notin A \\ \frac{1}{2}, & y \le 0.\end{cases}$$
Then we have $$\inf\_{u \in \mathbb{R}} g(x, u) = \begin{cases}0, & x \in B \\ 1/2, &x \notin B. \end{cases}$$ 
Take $\epsilon < 1/4$. If $\mu$ satisfies $g(x,\mu(x)) < \inf\_{u \in \mathbb{R}} g(x,u) + \epsilon$, then for $x \in B$ we must have $g(x, \mu(x)) < 1/4$, which in particular means $\mu(x) > 0$. But if $x \notin B$ then $g(x,y) = 1$ for all $y > 0$, meaning that we must have $\mu(x) \le 0$. So $\mu^{-1}(\mathbb{R}^+) = B$ which is not Borel, hence $\mu$ is not a Borel function. 


The error is in your "contradiction" argument, where you have mixed up the $\forall x$ quantifier. The correct negation of your claimed statement is "for every $\mu$
there exists $x$ such that $g(x,\mu(x))>\inf\_\nu g(x,\nu(x))+ \epsilon$", and this is not absurd (and it is true for the $g$ described above).


The statement you can correctly conclude from your logic is that "for every $x$ there exists $\mu$ such that $g(x, \mu(x)) < \inf\_{\nu} g(x, \nu(x)) + \epsilon$", but this is trivial since $\mu$ can depend on $x$ and as you note you can take a constant $\mu$. You may not be able to find a single universal $\mu$ that works for every $x$.


