2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ I don't like the look of the $\forall x$ quantifiers on every line... $\endgroup$ – Nate Eldredge Sep 30 '16 at 3:18
  • $\begingroup$ 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$. $\endgroup$ – Nate Eldredge Sep 30 '16 at 3:21
  • $\begingroup$ 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. $\endgroup$ – Nate Eldredge Sep 30 '16 at 3:24
  • $\begingroup$ It's also worth noting that your argument appears to actually prove that there is a constant policy $\mu_\epsilon$... $\endgroup$ – Nate Eldredge Sep 30 '16 at 3:52
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! And so, why such result holds only almost everywhere? Maybe it needs considerably more work to prove? $\endgroup$ – underpi Sep 30 '16 at 4:01
  • $\begingroup$ Maybe. I don't know a proof or a reference off the top of my head. Do Bertsekas and Shreve not give one? $\endgroup$ – Nate Eldredge Sep 30 '16 at 4:07
  • 1
    $\begingroup$ 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... $\endgroup$ – underpi Sep 30 '16 at 4:12
  • $\begingroup$ It ought to be in some standard measure theory or descriptive set theory book. I looked in Bogachev and there are lots of "selection theorems" that have a similar flavor, but I didn't immediately see how any of them imply this result. Many are nontrivial "named theorems". $\endgroup$ – Nate Eldredge Sep 30 '16 at 4:19
  • $\begingroup$ Hmm... If it was a "named theorem", I think they should have mentioned it at that point. Many thanks anyway for clearing this up. $\endgroup$ – underpi Sep 30 '16 at 4:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.