# How will fixed point change if the mapping changes?

Generally, the question is we have a contraction mapping $$M:\mathbb{R}^n\rightarrow\mathbb{R}^n$$. Define a new mapping $$\tilde{M}:\mathbb{R}^n\rightarrow\mathbb{R}^n$$ where $$\tilde{M}:Mx+c$$ where $$c$$ is a constant vector. We know $$\tilde{M}$$ is also a contraction mapping. Thus, we know there exists a unique fixed point $$x^*\in\mathbb{R}^n$$ that solves $$Mx^*=x^*$$ and a unique $$\tilde{x}\in\mathbb{R}^n$$ such that $$\tilde{M}\tilde{x}=\tilde{x}$$. How the fixed point $$x^*$$ will differ from $$\tilde{x}$$? How the change of $$c$$ affect the change of the fixed point.

To be more specific, in reinforcement learning, we define $$Q$$ functions where $$Q\in\mathbb{R}^{S\times A}$$. The optimal $$Q$$ function denoted by $$Q^*$$ has to satisfy the Bellman equation given as follows: $$Q^*(i,a)=c(i,a) + \beta \sum_j p(i,j,a)\min_b Q^*(j,b),\ \ i\in \mathcal{S}, a\in \mathcal{A},$$ where $$c:\mathcal{S}\times\mathcal{A}\rightarrow \mathbb{R}$$ and $$p(i,j,a)$$ is the probability that given state $$i$$ and action $$a$$, the next state is $$j$$.

Define $$F:\mathbb{R}^{S\times A}\rightarrow \mathbb{R}^{S\times A}$$ by $$[F(Q)]_{i,a}=c(i,a) + \beta \sum_j p(i,j,a)\min_b Q^*(j,b)$$ for $$i\in\mathcal{S},a\in\mathcal{A}$$.

We know that $$F$$ is a contraction mapping. Thus, we can apply iterative algorithm to find the fixed point $$Q^*$$ which is unique.

But I was wondering how the fixed point $$Q^*$$ would change as we change $$c(i,a)$$ a little bit. Is the mapping $$c\mapsto Q^*$$ continuous? If we want the fixed point $$Q^*$$ to be the values that we desire, how should we select $$c$$.

I don't know what theories I can reply on to solve my problems. Do you know any papers that provide tools for solving my problems?

## 1 Answer

If $$c$$ is a small perturbation, then the fixed point will be a small perturbation of the original fixed point, whose size is in fact quite explicitly controlled by $$c$$. This is a feature known as stability that is observed in many problems that are resolved using contraction mapping. To see this, let $$0 < L < 1$$ be the constant in the contraction mapping definition of $$M$$, so that $$\|Mx - My\| \leq L\|x-y\|$$. Let $$x$$ be a fixed point of $$M$$, so that $$x = Mx$$, and let $$y$$ be a fixed point of $$\tilde{M}$$, so that $$y = My + c$$. Then the difference is $$y-x = (My - Mx) + c.$$ By the triangle inequality and the contraction hypothesis, $$\|y-x\| \leq L\|y-x\| + \|c\|.$$ Rearranging, $$(1-L)\|y-x\| \leq \|c\|,$$ and since $$0 the constant factor is positive, so we can divide through to conclude that $$\|y-x\| \leq \frac{1}{1-L}\|c\|.$$ Therefore if $$c$$ is small, then $$y-x$$ is also small. In fact, taking this argument just slightly further, one concludes that the fixed points $$x_c$$ of the maps $$x\mapsto Mx + c$$ depend in a Lipschitz continuous way on the perturbation $$c$$.

• Thanks. It is a clear and helpful answer. I do care about the change in magnitude. But I also want to study the change in direction. The local behavior of the function $c\mapsto y$ where $y$ is a fixed point that solves $\tilde{M}y=y$. I know the local behavior really depends on what $M$ is. I was wondering if there is any reference that discusses this kind of problem. I'm now looking at implicit function theorem and hoping it can help. – YHH May 31 at 14:28