2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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<L<1$ 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$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – YHH May 31 at 14:28

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.