Why is the max a non-expansive operator?

Question

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 (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?

Answer 1

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

Answer 2

Suppose that $X$ and $Y$ are metric spaces. 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). 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) 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).