The Action Replay Process

Preface

A commonly used inequality

$$-x>\ln (1-x),0<x<1$$

Proof: Let $f(x)=\ln (1-x)+x$, for $0<x<1$. Then $f(0)=0$.

$$f^{\prime }(x)=\frac{-1}{1-x}+1=\frac{x}{x-1}<0$$

Hence, $-x>\ln (1-x),0<x<1$. Q.E.D.

---

Fundamental Theorem
If $a_n>-1$, then

$$\prod _{n=1}^{\infty }(1+a_n)=0\iff \sum _{n=1}^{\infty }\ln (1+a_n)=-\infty$$

Proof: Let $P_k={\prod }_{n=1}^k(1+a_n)$, then

$$\ln P_k=\ln \left(\prod _{n=1}^k(1+a_n)\right)=\sum _{n=1}^k\ln (1+a_n)$$

Thus,

$$\sum _{n=1}^{\infty }\ln (1+a_n)=-\infty \iff \underset{k\to \infty }{\lim }\sum _{n=1}^k\ln (1+a_n)=-\infty \iff \underset{k\to \infty }{\lim }\ln P_k=-\infty \iff \underset{k\to \infty }{\lim }{P}_k=0$$

Q.E.D.

---

Corollary
If $0\le b_n<1$ and ${\sum }_{n=1}^{\infty }{b}_n=+\infty$, then

$$\prod _{n=1}^{\infty }(1-b_n)=0$$

Proof: Consider the subsequence { b n k } \{b_{n_k}\} {bnk​​} consisting of non-zero $b_n$. Since $-b_{n_k}>-1$, and applying the fundamental theorem, we have:

$$\prod _{n=1}^{\infty }(1-b_n)=\prod _{k=1}^{\infty }(1-b_{n_k})=0\iff \sum _{k=1}^{\infty }\ln (1-b_{n_k})=-\infty$$

We now show ${\sum }_{k=1}^{\infty }\ln (1-b_{n_k})=-\infty$.
Given $0<1-b_{n_k}<1$, we have $\ln (1-b_{n_k})<0$, and ${\sum }_{k=1}^{\infty }{b}_{n_k}=+\infty$. It’s not immediately obvious, so we proceed by contradiction:

Assume ${\sum }_{k=1}^{\infty }\ln (1-b_{n_k})\ne -\infty$. Since each term is negative, this implies convergence, i.e.,

$$\sum _{k=1}^{\infty }\ln (1-b_{n_k})>-\infty$$

But ${\sum }_{k=1}^{\infty }(-b_{n_k})=-\infty \ge {\sum }_{k=1}^{\infty }\ln (1-b_{n_k})>-\infty$, a contradiction.
Therefore, ${\sum }_{k=1}^{\infty }\ln (1-b_{n_k})=-\infty$, and so

$$\prod _{n=1}^{\infty }(1-b_n)=0$$

Q.E.D.

---

The Essence of Mathematical Truth: Induction
Observe a linear-looking relation, fantasize wildly, then coldly examine whether it is truly valid.

Given $X_1$ and the recursive formula:

$$X_{n+1}=X_n+{\beta }_n({\xi }_n-X_n)=(1-{\beta }_n)X_n+{\beta }_n{\xi }_n$$

Show that

$$X_{n+1}=\sum _{j=1}^n{\xi }_j{\beta }_j\prod _{i=j}^{n-1}(1-{\beta }_{i+1})+X_1\prod _{i=1}^n(1-{\beta }_i)$$

Proof:

1. Base case: $n=1$

   $$X_2=(1-{\beta }_1)X_1+{\beta }_1{\xi }_1={\xi }_1{\beta }_1+X_1(1-{\beta }_1)$$

   holds.

2. Inductive step: assume true for $n$, prove for $n+1$:

   $$X_{n+2}=(1-{\beta }_{n+1})X_{n+1}+{\beta }_{n+1}{\xi }_{n+1}$$

   Plug in inductive hypothesis:

   $$=(1-{\beta }_{n+1})\left[\sum _{j=1}^n{\xi }_j{\beta }_j\prod _{i=j}^{n-1}(1-{\beta }_{i+1})+X_1\prod _{i=1}^n(1-{\beta }_i)\right]+{\beta }_{n+1}{\xi }_{n+1}$$

   $$=\sum _{j=1}^{n+1}{\xi }_j{\beta }_j\prod _{i=j}^n(1-{\beta }_{i+1})+X_1\prod _{i=1}^{n+1}(1-{\beta }_i)$$

3. By induction, the formula holds for all positive integers $n$. Q.E.D.

---

Now, let’s relax for a while — it’s movie time.

---

1. Definition of Action Replay Process

Given an $n$-step finite MDP with a possibly varying learning rate $\alpha$, in step $i$, the agent is in state $x_i$, takes action $a_i$, receives random reward $r_i$, and transitions to a new state $y_i$.

Action Replay Process (ARP) is a re-examination of state $x$ and action $a$ within a given MDP.

Suppose we focus on state $x$ and action $a$, and consider an MDP consisting of $n$ steps.

We add a step 0 in which the agent immediately terminates and receives reward $Q_0(x,a)$.

During steps 1 to $n$, due to MDP randomness, the agent may take action $a$ in state $x$ at time steps $1\le n^{i_1},n^{i_2},...,n^{i_{\ast }}\le n$.

If action $a$ is never taken at $x$ in this episode, the only opportunity for it is at step 0.

When $i_{\ast }\ge 1$, to determine ARP’s next reward and state, we sample an index $n^{i_e}$ as follows:

$$n^{i_e}=\{\begin{array}{ll}{n}^{i_{\ast }},& \text{with probability }{\alpha }_{n^{i_{\ast }}}\\ n^{i_{\ast -1}},& \text{with probability }(1-{\alpha }_{n^{i_{\ast }}}){\alpha }_{n^{i_{\ast -1}}}\\ ⋮& \\ 0,& \text{with probability }{\prod }_{i=1}^{i_{\ast }}(1-{\alpha }_{n^i})\end{array}$$

Then, after one ARP step, the state $<x,n>$ transitions to $<y_{n^{i_e}},n^{i_e}-1>$, and the reward is $r_{n^{i_e}}$.
Clearly, $n^{i_e}-1<n$, so ARP terminates with probability 1. Thus, ARP is a finite process almost surely.

To summarize, the core transition formula is:

$$<x,n>\stackrel{a}{\to }<y_{n^{i_e}},n^{i_e}-1>,\text{reward }{r}_{n^{i_e}}$$

---

2. Properties of the Action Replay Process

We now examine ARP’s properties, particularly in comparison to MDPs. Given an MDP rule and a (non-terminating) instance, we can construct an ARP accordingly.

Property 1

$$\forall n,x,a,Q_{ARP}^{\ast }(<x,n>,a)=Q_n(x,a)$$

Proof:
Using mathematical induction on $n$:

1. Base case $n=1$:

   • If the MDP did not take $a$ at $x$ in step 1, ARP gives reward $Q_0(x,a)=0=Q_1(x,a)$

   • If $(x,a)=(x_1,a_1)$, then:

     $$Q_{ARP}^{\ast }(<x,1>,a)={\alpha }_1{r}_1+(1-{\alpha }_1)Q_0(x,a)={\alpha }_1{r}_1=Q_1(x,a)$$

2. Inductive step: Assume $Q_{ARP}^{\ast }(<x,k-1>,a)=Q_{k-1}(x,a)$, show for $k$:

   • If $(x,a)\ne (x_k,a_k)$, then:

     $$Q_k(x,a)=Q_{k-1}(x,a)=Q_{ARP}^{\ast }(<x,k>,a)$$

   • If $(x,a)=(x_k,a_k)$, then:

     $$Q_{ARP}^{\ast }(<x,k>,a)={\alpha }_k[r_k+\gamma \underset{a}{\max }{Q}_{k-1}(y_k,a)]+(1-{\alpha }_k)Q_{k-1}(x,a)=Q_k(x,a)$$

3. Therefore, $Q_{ARP}^{\ast }(<x,n>,a)=Q_n(x,a)$. Q.E.D.

---

Property 2 In the ARP ${<x_i,n_i>}$, for all $l,s,ϵ>0$, there exists $h>l$ such that for all $n_1>h$,

$$P(n_{s+1}<l)<ϵ$$

Proof:

Let us first consider the final step, that is, the case where $n^{i_e}<n^{i_l}$ or even lower.
Given in the ARP, starting from $<x,h>$, after taking action $a$, the probability of reaching a level lower than $l$ in one step is:

$$\sum _{j=0}^{i_l-1}\left[{\alpha }_{n^j}\prod _{k=j+1}^{i_h}(1-{\alpha }_{n^k})\right]=\sum _{j=0}^{i_l-1}\left[{\alpha }_{n^j}\prod _{k=j+1}^{i_l-1}(1-{\alpha }_{n^k})\right]\left[\prod _{i=i_l}^{i_h}(1-{\alpha }_{n^i})\right]=\left[\prod _{i=i_l}^{i_h}(1-{\alpha }_{n^i})\right]\sum _{j=0}^{i_l-1}\left[{\alpha }_{n^j}\prod _{k=j+1}^{i_l-1}(1-{\alpha }_{n^k})\right]$$

But note that:

$$\sum _{j=0}^{i_l-1}\left[{\alpha }_{n^j}\prod _{k=j+1}^{i_l-1}(1-{\alpha }_{n^k})\right]=1$$

Therefore,

$$\sum _{j=0}^{i_l-1}\left[{\alpha }_{n^j}\prod _{k=j+1}^{i_h}(1-{\alpha }_{n^k})\right]=\prod _{i=i_l}^{i_h}(1-{\alpha }_{n^i})<e^{-{\sum }_{i=i_l}^{i_h}{\alpha }_{n^i}}$$

As long as every subsequence of { α n } \{\alpha_n\} {αn​} diverges, then as $h\to \infty$:

$$\sum _{j=0}^{i_l-1}\left[{\alpha }_{n^j}\prod _{k=j+1}^{i_h}(1-{\alpha }_{n^k})\right]=\prod _{i=i_l}^{i_h}(1-{\alpha }_{n^i})<e^{-{\sum }_{i=i_l}^{i_h}{\alpha }_{n^i}}\to 0$$

Moreover, since the MDP is finite, we have:

$$\forall l_j\in {\mathbb{N}}^{\ast },\forall {\eta }_j>0,\exists M_j>0,\forall n_j>M_j,\forall X_j,a_j,$$

starting from $<X_j,n_j>$, after taking action $a_j$,

$$P(n_{j+1}\ge l_j)=1-{\eta }_j$$

Using the index $j$, we recursively apply this conclusion from step $s$ back to step 1. Then, the probability of reaching at least $l=l_s$ is at least:

$$\prod _{j=1}^s(1-{\eta }_j)=1-ϵ$$

where $n_{j+1}\ge l_j$, and $<X_{j+1},n_{j+1}>$ is reached from $<x_j,n_j>$ after executing $a_j$. Q.E.D.

Now, define:

$$P_{xy}^{(n)}[a]=\sum _{m=1}^{n-1}{P}_{<x,n>,<y,m>}^{ARP}[a]$$

Lemma:
Let ${\xi }_n$ be a sequence of bounded random variables with expectation $\mathfrak{E}$, and let $0\le {\beta }_n<1$ satisfy ${\sum }_{i=1}^{\infty }{\beta }_i=+\infty$ and ${\sum }_{i=1}^{\infty }{\beta }_i^2<+\infty$.
Define the sequence $X_{n+1}=X_n+{\beta }_n({\xi }_n-X_n)$. Then:

$$P\left(\underset{n\to \infty }{\lim }{X}_n=\mathfrak{E}\right)=1$$

My attempt:

$$X_{n+1}=X_n+{\beta }_n({\xi }_n-X_n)=(1-{\beta }_n)X_n+{\beta }_n{\xi }_n$$

By induction, we obtain:

$$X_{n+1}=\sum _{j=1}^n{\xi }_j{\beta }_j\prod _{i=j}^{n-1}(1-{\beta }_{i+1})+X_1\prod _{i=1}^n(1-{\beta }_i)$$

From a corollary of a fundamental theorem:

$$\prod _{i=1}^{\infty }(1-{\beta }_i)=0$$

Hence:

$$\underset{n\to \infty }{\lim }{X}_n=\underset{n\to \infty }{\lim }\sum _{j=1}^n{\xi }_j{\beta }_j\prod _{i=j+1}^n(1-{\beta }_i)=\frac{{\lim }_{n\to \infty }{\sum }_{j=1}^n{\xi }_j{\beta }_j{\prod }_{i=j+1}^n(1-{\beta }_i)}{1-0}$$

$$=\frac{{\lim }_{n\to \infty }{\sum }_{j=1}^n{\xi }_j{\beta }_j{\prod }_{i=j+1}^n(1-{\beta }_i)}{1-{\prod }_{i=1}^{\infty }(1-{\beta }_i)}=\underset{n\to \infty }{\lim }\sum _{j=1}^n{\xi }_j\frac{{\beta }_j{\prod }_{i=j+1}^n(1-{\beta }_i)}{1-{\prod }_{i=1}^n(1-{\beta }_i)}$$

Property 3

$$P\left\{\underset{n\to \infty }{\lim }{P}_{xy}^{(n)}[a]=P_{xy}[a]\right\}=1,P\left[\underset{n\to \infty }{\lim }{\mathfrak{R}}_x^{(n)}(a)={\mathfrak{R}}_x(a)\right]=1$$