3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Philip Raeisghasem Mar 15 at 23:22
  • 1
    $\begingroup$ @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. $\endgroup$ – John Doucette Mar 15 at 23:41
1
$\begingroup$

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

$\endgroup$

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.