Answers.Body: <p>In laymen's terms, a non-expansive operator is a function that brings points closer together or at least no further apart.</p>
  
  <p>An example of a non-expansive operator is the function <span class="math-container">$f(x) = x/2$</span>. The two numbers <span class="math-container">$0$</span> and <span class="math-container">$5$</span> are a distance of <span class="math-container">$5$</span> apart. The two output numbers <span class="math-container">$f(0) = 0$</span> and <span class="math-container">$f(5) = 2.5$</span> are 2.5 apart (which is smaller than <span class="math-container">$5$</span> apart). It is easy to see that <span class="math-container">$f$</span> brings everything closer together except when the two input numbers are the same: in which case, the distance between the outputs of the function at those numbers is at least no further apart than distance between the two input numbers.</p>
  
  <p><span class="math-container">$\max$</span>  is a two-input function (or n-input, but the intuition should be clear from the 2-input case).  We can think of max as a function that maps <em>pairs</em> of numbers <span class="math-container">$(x, y)$</span> to single numbers (picking whichever of <span class="math-container">$x$</span> and <span class="math-container">$y$</span> is larger).</p>
  
  <p>Suppose that we chose to measure the distance between pairs using <a href="https://en.wikipedia.org/wiki/Euclidean_distance" rel="nofollow noreferrer">Euclidean distance</a>, and the distance between single numbers using the Euclidean distance as well. Here's an example:</p>
  
  <p>The distance between (0,0) and (3,3) is <span class="math-container">$\sqrt{3^2 + 3^2} = \sqrt{18}$</span>. The distance between <span class="math-container">$\max(0,0) = 0$</span> and <span class="math-container">$\max(3, 3) = 3$</span> is <span class="math-container">$\sqrt{{(\max(0,0) - \max(3, 3))}^2} = \sqrt{9} = 3$</span>.</p>
  
  <p>Let's consider the general case. The Euclidean distance between the 2D points <span class="math-container">$(a, b)$</span> and <span class="math-container">$(c, d)$</span> is <span class="math-container">$\sqrt{(a-c)^2 + (b-d)^2}$</span>. There are four cases to consider:</p>
  
  <ol>
  <li>Suppose that <span class="math-container">$a\geq b$</span> and <span class="math-container">$c \geq d$</span>. In this case, the distance between max(a,b) and max(c,d) is just |a-c|, which is clearly <em>at most</em> <span class="math-container">$\sqrt{(a-c)^2 + (b-d)^2}$</span>.</li>
  <li>Suppose that <span class="math-container">$a\leq b$</span> and <span class="math-container">$c \leq d$</span>. In this case, the distance is |b-d|, which is also at most the original distance.</li>
  <li>Suppose that <span class="math-container">$a\geq b$</span> but <span class="math-container">$c \leq d$</span>. Then the distance is |a-d|. Suppose that <span class="math-container">$a &gt; d$</span>. Since <span class="math-container">$d &gt; c$</span>, then <span class="math-container">$|a-d| &lt;= \sqrt{(a-c)^2 + (b-d)^2}$</span> since |a-d|&lt;=<span class="math-container">$\sqrt{(a-c)^2}$</span>, and a symmetric argument holds for the case <span class="math-container">$d &gt; a$</span>. </li>
  <li><span class="math-container">$a\leq b$</span> but <span class="math-container">$c \geq d$</span>, we can construct an argument identical to the one for case 3 above.</li>
  </ol>
  
  <p>Since max is always bringing things closer together, or at least, no further apart, it is a non-expansive operator.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-15T23:22:09.293Z
Answers.Text: I haven't gone through your whole answer in detail, but you consider only the L2 norm, the Euclidean distance metric. Is the $\max$ operation non-expansive for other notions of distance?
Answers.UserDisplayName: Philip Raeisghasem
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-15T23:41:19.037Z
Answers.Text: @PhilipRaeisghasem That's a good question. I tried to keep the answer closer to laymen's terms. In fact, I think the analysis will hold for any metric (it requires the triangle inequality). The more formal definition of a non-expansive operator does state that it holds only for functions between metric spaces, so I think that is correct.
Answers.UserDisplayName: John Doucette
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-15T14:49:37.053Z
Answers.LastActivityDate: 2019-03-15T15:53:00.423Z
Answers.LastEditDate: 2019-03-15T15:53:00.423Z
Answers.UserDisplayName: John Doucette
Answers.Body: <p>Suppose that <span class="math-container">$X$</span> and <span class="math-container">$Y$</span> are <a href="https://en.wikipedia.org/wiki/Metric_space" rel="nofollow noreferrer">metric spaces</a>. A metric space is a set equipped with a <em>metric</em>, which is a function that defines the intuitive notion of <em>distance</em> between the elements of the set. For example, the set of real numbers, <span class="math-container">$\mathbb{R}$</span>, equipped with the <a href="https://math.stackexchange.com/a/1893295/168764">metric induced by the absolute value function (which is a norm)</a>. More precisely, the metric <span class="math-container">$d$</span> can be defined as <span class="math-container">$$d(x,y)=|x - y|, \forall x, y \in \mathbb{R} \tag{1}\label{1}.$$</span></p>
  
  <p>Let <span class="math-container">$f$</span> be a function from the metric space <span class="math-container">$X$</span> to the metric space <span class="math-container">$Y$</span>, that is, <span class="math-container">$f: X \rightarrow Y$</span>. Then, <span class="math-container">$f$</span> is a <em>non-expansive map</em> (also known as <a href="https://en.wikipedia.org/wiki/Metric_map" rel="nofollow noreferrer">metric map</a>) <em>if and only if</em></p>
  
  <p><span class="math-container">$$d_{Y}(f(x),f(y)) \leq d_{X}(x,y) \tag{2} \label{2}$$</span></p>
  
  <p>where the subscript <span class="math-container">$_X$</span> in <span class="math-container">$d_X$</span> means that the metric <span class="math-container">$d_X$</span> is the metric associated with the metric space <span class="math-container">$X$</span>. Therefore, any function <span class="math-container">$f$</span> between two metric spaces that satisfies \ref{2} is a non-expansive operator. </p>
  
  <p>To show that the max operator is non-expansive, consider the set of real numbers, <span class="math-container">$\mathbb{R}$</span>, equipped with the absolute value metric defined in \ref{1}. Then, in this case, <span class="math-container">$f=\operatorname{max}$</span>, <span class="math-container">$d(x, y) = |x - y|$</span> and <span class="math-container">$X = Y = \mathbb{R}$</span>, so \ref{2} becomes</p>
  
  <p><span class="math-container">$$|\operatorname{max}(x) - \operatorname{max}(y)| \leq | x - y | \tag{3} \label{3}$$</span></p>
  
  <p>Given that <span class="math-container">$\operatorname{max}(x) = x, \forall x$</span>, then \ref{3} trivially holds, that is</p>
  
  <p><span class="math-container">\begin{align}
  |\operatorname{max}(x) - \operatorname{max}(y)| &amp;\leq | x - y | \iff \\
  |x - y| &amp;\leq | x - y | \iff \\
  |x - y| &amp;= | x - y | \tag{4} \label{4}
  \end{align}</span></p>
  
  <p>For example, suppose that <span class="math-container">$x=6$</span> and <span class="math-container">$y=9$</span>, then \ref{4} becomes </p>
  
  <p><span class="math-container">\begin{align}
  |\operatorname{max}(6) - \operatorname{max}(9)| &amp;\leq | 6 - 9 | \iff \\
  |6 - 9| &amp;\leq | -3 | \iff \\
  |-3| &amp;= 3
  \end{align}</span></p>
  
  <p>There are other examples of non-expansive maps. For example, <span class="math-container">$f(x) = k x$</span>, for <span class="math-container">$0 \leq k \leq 1$</span>, where <span class="math-container">$f : \mathbb{R} \rightarrow \mathbb{R}$</span>. </p>
  
  <p>See also <a href="https://en.wikipedia.org/wiki/Contraction_mapping" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Contraction_mapping</a> and <a href="https://en.wikipedia.org/wiki/Contraction_(operator_theory)" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Contraction_(operator_theory)</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-15T14:38:46.567Z
Answers.LastActivityDate: 2019-09-15T14:38:46.567Z
Answers.UserDisplayName: nbro
Body: <p>In certain reinforcement learning (RL) proofs, the operators involved are assumed to be <em>non-expansive</em>. For example, on page 6 of the paper <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.71.1316&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">Generalized Markov Decision Processes: Dynamic-programming and Reinforcement-learning Algorithms</a> (1997), Csaba Szepesvari and Michael L. Littman state</p>
  
  <blockquote>
    <p>When <span class="math-container">$0 \leq \gamma &lt; 1$</span> and <span class="math-container">$\otimes$</span> and <span class="math-container">$\oplus$</span> are non-expansions, the generalized Bellman equations have a unique optimal solution, and therefore, the optimal value function is well defined.</p>
  </blockquote>
  
  <p>On page 7 of the same paper, the authors say that max is non-expansive. Moreover, on page 33, the authors assume <span class="math-container">$\otimes$</span> and <span class="math-container">$\oplus$</span> are non-expansions.</p>
  
  <p>What is a non-expansive operator? Why is the <span class="math-container">$\max$</span> (and the <span class="math-container">$\min$</span>), which is, for example, used in Q-learning, a non-expansive operator?</p>
  
Tags: <reinforcement-learning><q-learning><math><proofs><papers>
Title: Why is the max a non-expansive operator?
UserDisplayName: nbro
ThreadText: # Why is the max a non-expansive operator?
  
  (Asked by: username_0 on 2019-03-14)
  
  In certain reinforcement learning (RL) proofs, the operators involved are assumed to be *non-expansive*. For example, on page 6 of the paper [Generalized Markov Decision Processes: Dynamic-programming and Reinforcement-learning Algorithms](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.71.1316&rep=rep1&type=pdf) (1997), Csaba Szepesvari and Michael L. Littman state
  
  > When $0 \leq \gamma < 1$ and $\otimes$ and $\oplus$ are non-expansions, the generalized Bellman equations have a unique optimal solution, and therefore, the optimal value function is well defined.
  
  On page 7 of the same paper, the authors say that max is non-expansive. Moreover, on page 33, the authors assume $\otimes$ and $\oplus$ are non-expansions.
  
  What is a non-expansive operator? Why is the $\max$ (and the $\min$), which is, for example, used in Q-learning, a non-expansive operator?
  
  **Tags:** reinforcement-learning, q-learning, math, proofs, papers
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2019-03-15. Score: 2
  
  In laymen's terms, a non-expansive operator is a function that brings points closer together or at least no further apart.
  
  An example of a non-expansive operator is the function $f(x) = x/2$. The two numbers $0$ and $5$ are a distance of $5$ apart. The two output numbers $f(0) = 0$ and $f(5) = 2.5$ are 2.5 apart (which is smaller than $5$ apart). It is easy to see that $f$ brings everything closer together except when the two input numbers are the same: in which case, the distance between the outputs of the function at those numbers is at least no further apart than distance between the two input numbers.
  
  $\max$ is a two-input function (or n-input, but the intuition should be clear from the 2-input case). We can think of max as a function that maps *pairs* of numbers $(x, y)$ to single numbers (picking whichever of $x$ and $y$ is larger).
  
  Suppose that we chose to measure the distance between pairs using [Euclidean distance](https://en.wikipedia.org/wiki/Euclidean_distance), and the distance between single numbers using the Euclidean distance as well. Here's an example:
  
  The distance between (0,0) and (3,3) is $\sqrt{3^2 + 3^2} = \sqrt{18}$. The distance between $\max(0,0) = 0$ and $\max(3, 3) = 3$ is $\sqrt{{(\max(0,0) - \max(3, 3))}^2} = \sqrt{9} = 3$.
  
  Let's consider the general case. The Euclidean distance between the 2D points $(a, b)$ and $(c, d)$ is $\sqrt{(a-c)^2 + (b-d)^2}$. There are four cases to consider:
  
  1. Suppose that $a\geq b$ and $c \geq d$. In this case, the distance between max(a,b) and max(c,d) is just |a-c|, which is clearly *at most* $\sqrt{(a-c)^2 + (b-d)^2}$.
  2. Suppose that $a\leq b$ and $c \leq d$. In this case, the distance is |b-d|, which is also at most the original distance.
  3. Suppose that $a\geq b$ but $c \leq d$. Then the distance is |a-d|. Suppose that $a > d$. Since $d > c$, then $|a-d| <= \sqrt{(a-c)^2 + (b-d)^2}$ since |a-d|<=$\sqrt{(a-c)^2}$, and a symmetric argument holds for the case $d > a$.
  4. $a\leq b$ but $c \geq d$, we can construct an argument identical to the one for case 3 above.
  
  Since max is always bringing things closer together, or at least, no further apart, it is a non-expansive operator.
  
  > **Comments:**
  > **username_2**: I haven't gone through your whole answer in detail, but you consider only the L2 norm, the Euclidean distance metric. Is the $\max$ operation non-expansive for other notions of distance?  
  > **username_1**: @PhilipRaeisghasem That's a good question. I tried to keep the answer closer to laymen's terms. In fact, I think the analysis will hold for any metric (it requires the triangle inequality). The more formal definition of a non-expansive operator does state that it holds only for functions between metric spaces, so I think that is correct.  
  
  ---
  
  ### Answer by username_0 on 2019-09-15. Score: 1
  
  Suppose that $X$ and $Y$ are [metric spaces](https://en.wikipedia.org/wiki/Metric_space). A metric space is a set equipped with a *metric*, which is a function that defines the intuitive notion of *distance* between the elements of the set. For example, the set of real numbers, $\mathbb{R}$, equipped with the [metric induced by the absolute value function (which is a norm)](https://math.stackexchange.com/a/1893295/168764). More precisely, the metric $d$ can be defined as $$d(x,y)=|x - y|, \forall x, y \in \mathbb{R} \tag{1}\label{1}.$$
  
  Let $f$ be a function from the metric space $X$ to the metric space $Y$, that is, $f: X \rightarrow Y$. Then, $f$ is a *non-expansive map* (also known as [metric map](https://en.wikipedia.org/wiki/Metric_map)) *if and only if*
  
  $$d\_{Y}(f(x),f(y)) \leq d\_{X}(x,y) \tag{2} \label{2}$$
  
  where the subscript $\_X$ in $d\_X$ means that the metric $d\_X$ is the metric associated with the metric space $X$. Therefore, any function $f$ between two metric spaces that satisfies \ref{2} is a non-expansive operator.
  
  To show that the max operator is non-expansive, consider the set of real numbers, $\mathbb{R}$, equipped with the absolute value metric defined in \ref{1}. Then, in this case, $f=\operatorname{max}$, $d(x, y) = |x - y|$ and $X = Y = \mathbb{R}$, so \ref{2} becomes
  
  $$|\operatorname{max}(x) - \operatorname{max}(y)| \leq | x - y | \tag{3} \label{3}$$
  
  Given that $\operatorname{max}(x) = x, \forall x$, then \ref{3} trivially holds, that is
  
  \begin{align}
  |\operatorname{max}(x) - \operatorname{max}(y)| &\leq | x - y | \iff \\
  |x - y| &\leq | x - y | \iff \\
  |x - y| &= | x - y | \tag{4} \label{4}
  \end{align}
  
  For example, suppose that $x=6$ and $y=9$, then \ref{4} becomes
  
  \begin{align}
  |\operatorname{max}(6) - \operatorname{max}(9)| &\leq | 6 - 9 | \iff \\
  |6 - 9| &\leq | -3 | \iff \\
  |-3| &= 3
  \end{align}
  
  There are other examples of non-expansive maps. For example, $f(x) = k x$, for $0 \leq k \leq 1$, where $f : \mathbb{R} \rightarrow \mathbb{R}$.
  
  See also <https://en.wikipedia.org/wiki/Contraction_mapping> and <https://en.wikipedia.org/wiki/Contraction_(operator_theory)>.
  
  
  ---
  
  