# Is the following function Lipschitz?

Given a vector $$Q \in \mathbb{R}^{S\times A}$$ where $$S$$ and $$A$$ are sets of finite cardinality, for $$0<\gamma<1$$ define the function $$H_{w}:\mathbb{R}^{S\times A} \rightarrow \mathbb{R}^{S\times A}$$ as $$H_{w}Q(s,a) := w\left(r(s,a)+ \gamma \sum_{s' \in S}p(s'|s,a)\displaystyle\max_{a \in A} Q(s',a)\right)+(1-w)\displaystyle\max_{a \in A}Q(s,a).$$ Here $$|r(s,a)| \leq R ~ \forall ~ (s,a) \in S \times A$$ and $$p(\_|s,a)$$ is a probability mass function on $$S$$ for any given $$(s,a) \in S \times A$$ and $$0 with $$w^*=\displaystyle\max_{(i,a)}\left\{\frac{1}{1-p(i|i,a)}\right\}.$$

Note:

1. $$H_w$$ is a contraction with respect to the max-norm/infinity-norm on $$\mathbb{R}^{S\times A}$$ with contraction factor $$(1-w+\gamma w)$$
2. Note the possibility of $$w>1$$.

Is the function $$H_wQ$$ jointly Lipschitz in $$w$$ and $$Q$$?

In view of your Note 1, it appears that the definition of $$H_w Q(s,a)$$ has to corrected as follows: $$H_w Q(s,a):=\gamma w\left(r(s,a)+\sum_{s'\in S}p(s'|s,a)\max_{a\in A}Q(s',a)\right) +(1-w)\max_{a\in A}Q(s,a).$$ (Your definition is missing $$\gamma$$.)
Now it is clear that $$H_w Q$$ is not Lipschitz in $$(w,Q)$$, because $$H_w Q$$ is "of degree $$2$$" (rather than "of degree $$\le1$$") in $$(w,Q)$$. In fact, $$H_w Q$$ is not Lipschitz even in $$w$$. Indeed, taking $$Q$$ to be an arbitrary real constant $$q$$ and letting $$r=0$$, we have $$H_w Q(s,a)=h(w,q):=\gamma wq+(1-w)q=(1-(1-\gamma)w)q.$$ The partial derivative of $$h(w,q)$$ in $$w$$ is $$(1-\gamma)q$$, which can be however large for large $$q$$. So, indeed $$H_w Q$$ is not Lipschitz even in $$w$$.
Note 1: $$h(w,q)$$ is a polynomial in $$(w,q)$$ of degree $$2$$.
Note 2: With your current definition, too, $$H_w Q$$ will not in general be Lipschitz even in $$w$$. In that case, we can let $$Q(s,a)$$ take two distinct values, depending on $$s$$.
• Thank you. You are correct, there is a typo. Edited the statement accordingly. We agree with your solution. The function is not Lipschitz with respect to $w$. We also carried out a similar calculation and obtained the same Commented Sep 3, 2020 at 3:22