# Why is the max a non-expansive operator?

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?

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.

• 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? – Philip Raeisghasem Mar 15 '19 at 23:22
• @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. – John Doucette Mar 15 '19 at 23:41

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