Limit of $\arg\max$ equals $\arg\max$ of limit?

570 Views Asked by At

Let $X$ be some set such as $\{a,b,c\}$ or $\mathbb R^n$. We want to choose a vector $x=(x_0,x_1,...)\in X^\infty$ that maximizes the sum below. Interpret this as a value $x_t$ for each time period $t$. (Assume the sum exists for all $x$).

My question is, under what conditions can we "move the argmax inside the limit operator", as follows?

$$\arg\max_{x\in X^\infty}\lim_{T\to \infty}\sum_{t=0}^T \gamma^tf(x_t)=\lim_{T\to \infty}\arg\max_{x\in X^\infty}\sum_{t=0}^T \gamma^tf(x_t)$$

With $\gamma\in (0,1)$. This is essentially a "limit of a set" equation. I'm not sure where to start to find out an answer to this question.

EDIT: I don't necessarily want to assume that $f:X\to \mathbb R$ is continuous, or even that $X$ is an infinite set.

EDIT: I just realized that I mistyped the equation at first... I was too hasty, and now understand people's comments... I forgot to add the $\gamma$. Sorry for wasting people's time.

1

There are 1 best solutions below

4
On

For finite sums, if $\max_{x\in X^T} \sum_{t=1}^{T-1} \gamma^t f(x_t)$ exists, we must have that $f$ assumes its maximum $M$ in a set $N=\arg\max_{x\in X} f$. The expression $\sum_{t=0}^{T-1} \gamma^t f(x_t)$ is maximal if each of the terms is maximal, so $\arg\max_{x\in X^T}\sum_{t=1}^{T-1} \gamma^t f(x_t)=N^T$ (if any of the entries is not in the argmax, then you can find a way to make the sum larger).

Now we consider the infinite sum. As $f(x)\le M$ on $X$, we have $$\sum_{t=0}^\infty \gamma^t f(x_t) \le M\sum_{t=0}^\infty \gamma^t=\frac{M}{1-\gamma}. $$ If we have a sequence $(x_t)$ such that $f(x_t)=M$ for every $t$, we have equality. If $f(x_t)<M$ for one $t$, then $\sum_{t=0}^\infty \gamma^t f(x_t) < M$. So $$\arg\max_{x\in X^\infty} \sum_{t=0}^\infty \gamma^t f(x_t) = N^\infty. $$ At the same time, as the finite sum only cares about the first terms, $$\arg\max_{x\in X^\infty} \sum_{t=0}^{T-1} \gamma^t f(x_t) = N^{T}\times \prod_{t=T}^\infty X \simeq N^T\times X^\infty. $$ All we need now is a sense of convergence of sets where $N^T\times X^\infty\to N^\infty$ as $T\to\infty$. My set / category theory are rusty, but I think this is an inverse limit that we can write as the intersection $$N^\infty = \bigcap_{T=0}^\infty \{(x_0,\dots, x_T,y_{T+1}, y_{T+2}, \dots) : x_i \in N, y_j\in X\}\subset X^\infty. $$