TD example

Example of Temporal-Difference

Revisit the mean estimation problem

$$w=\mathbb{E}[X]$$

based on some i.i.d. samples $\{x\}$ of $X$.

1. reformulate to root-finding problem: $g(w)=w-\mathbb{E}[X]=0$ is the equation to solve;
2. sample $x$ from $X$, obtain noisy observation $$\begin{array}{rl}\tilde{g}(w,\eta )& =w-x\\ & =(w-\mathbb{E}[X])+(\mathbb{E}[X]-x)\\ & =g(w)+\eta \end{array}$$
3. update $w$ by RM $$w_{k+1}=w_k-{\alpha }_k\tilde{g}(w_k,{\eta }_k)=w_k-{\alpha }_k(w_k-x_k)$$

To estimate mean of a function $v(X)$

$$w=\mathbb{E}[v(X)]$$

based on some i.i.d. random samples $\{x\}$ of $X$.

1. reformulate: $$\begin{array}{rl}g(w)& =w-\mathbb{E}[v(X)]=0\\ \tilde{g}(w,\eta )& =w-v(x)\\ & =(w-\mathbb{E}[v(X)])+(\mathbb{E}[v(X)]-v(x))\\ & =g(w)+\eta \end{array}$$
2. update $w$ by RM: $$w_{k+1}=w_k-{\alpha }_k\tilde{g}(w_k,{\eta }_k)=w_k-{\alpha }_k(w_k-v(x_k))$$

To estimate mean of a function $R+\gamma v(X)$

$$w=\mathbb{E}[R+\gamma v(X)]$$

where $R,X$ are random variables, constant $\gamma \in [0,1]$, and $v(\cdot )$ is a function.

1. suppose we can obtain samples $\{r\},\{x\}$ of $R,X$ respectively: $$\begin{array}{rl}g(w)& =w-\mathbb{E}[R+\gamma v(X)]=0\\ \tilde{g}(w,\eta )& =w-[r+\gamma v(x)]\\ & =(w-\mathbb{E}[R+\gamma v(X)])+(\mathbb{E}[R+\gamma v(X)]-[r+\gamma v(x)])\\ & =g(w)+\eta \end{array}$$
2. update $w$ by RM: $$w_{k+1}=w_k-{\alpha }_k\tilde{g}(w_k,{\eta }_k)=w_k-{\alpha }_k(w_k-[r_k+\gamma v(x_k)])$$

TLDR

上面三个例子都是用来估计expectation的，都是用RM来写成迭代的相似形式，下面我们就要正式引入state value的TD learning了。