# Existence of ε-optimal Borel measurable policies in stochastic control

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

$$\inf_{u\in\mathbb{R}}g\left(x,u\right)>-\infty,\quad \forall x\in \mathbb{R}.$$

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

$$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}.$$

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

$$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}.$$

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

$$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}.$$

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

$$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},$$

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

$$\mu_u \left( x \right) \triangleq u,\quad \forall x\in\mathbb{R}, \quad\text{for some } u\in\mathbb{R},$$

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

$$\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}.$$

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

$$\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}.$$

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

$$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}.$$

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!

• I don't like the look of the $\forall x$ quantifiers on every line... – Nate Eldredge Sep 30 '16 at 3:18
• Particularly, I believe all you can say is that for every $x$ there exists a $\mu_\epsilon$ such that $g(x, \mu_\epsilon(x)) \le \inf_\mu g(x, \mu(x))$. Note carefully the order of the quantifiers. You might need a different $\mu_\epsilon$ for different values of $x$. And then the statement is trivial, since you can just choose $\mu_\epsilon$ to be an appropriate constant for each $x$. – Nate Eldredge Sep 30 '16 at 3:21
• In your "contradiction" argument, 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))$", and this is not absurd. – Nate Eldredge Sep 30 '16 at 3:24
• It's also worth noting that your argument appears to actually prove that there is a constant policy $\mu_\epsilon$... – Nate Eldredge Sep 30 '16 at 3:52

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$.
• No, they do not actually. All they say is that "a weaker result is available whereby, given a probability measure $p$ on $\mathscr{B}_\mathbb{R}$, the existence of a Borel measurable selector $\mu_\varepsilon$ satisfying [the inequality] for $p$ almost every $x\in\mathbb{R}$ can be ascertained." Maybe they prove somewhere the result further in the book, but they do not give any reference at that point... – underpi Sep 30 '16 at 4:12