TD state values

Temporal-Difference State values

Introduction

1. 本章要做的事情是在policy evaluation中的计算$v_{\pi }$
2. policy evaluation←>prediction, policy improvement←>control
3. 之前的方法是model-based的方法，通过不断迭代pi的第一个方程来得到可以评估$v_{\pi }$，现在的方法则是model-free的方法，但与every-visit MC有所不同，我们不需要一个完整的episode，只需要下一步的state和reward即可开始迭代计算$v_{\pi }$，这是一种非常优雅的incremental manner

Algorithm description

Notations

• given policy $\pi$, the aim is to estimate the state values $\{v_{\pi }(s){\}}_{s\in \mathcal{S}}$
• experience samples: $(s_0,r_1,s_1,\dots ,r_{t+1},s_{t+1},\dots )$ or $\{(s_t,r_{t+1},s_{t+1}){\}}_{t=0}^T$

Some notations of $v(s)$

• $v_{\pi }(s)$: the value of state $s$ under policy $\pi$
• $v_{\ast }(s)$: the value of state $s$ under the optimal policy
• $v(s)$: the true value of state $s$
• $v(s_t)$: the estimated value of state $s_t$
• $v_t(s_t)$: the estimated value of state $s_t$ at time $t$ (or iteration $t$) during the learning process

TD learning algorithm

$$\begin{array}{rl}{v}_{t+1}(s_t)& =v_t(s_t)-{\alpha }_t(s_t)\left[v_t(s_t)-\left[r_{t+1}+\gamma v_t(s_{t+1})\right]\right],\\ v_{t+1}(s_t)& =v_t(s_t),\forall s\ne s_t,\end{array}$$

where $t=0,1,2,...$

At time $t$:

• $v_t$ is the estimated state value of $v_{\pi }(s_t)$
  • the value of the visited state $s_t$ is updated by the following TD target $r_{t+1}+\gamma v_t(s_{t+1})$
  • the unvisited states $s\ne s_t$ are not updated
• ${\alpha }_t(s_t)$ is the learning rate for state $s_t$

Algorithm properties

$$\begin{array}{r}\underset{\text{new estimate}}{\underbrace{v_{t+1}(s_t)}}=\underset{\text{current estimate}}{\underbrace{v_t(s_t)}}-{\alpha }_t(s_t)[\stackrel{\text{TD error }{\delta }_t}{\overbrace{v_t(s_t)-[\underset{\text{TD target }{\bar{v}}_t}{\underbrace{r_{t+1}+\gamma v_t(s_{t+1})}}]}}]\end{array}$$

上面式子(3)中我们可以看到

• TD target: ${\bar{v}}_t\doteq r_{t+1}+\gamma v_t(s_{t+1})$
  • compared to MC target: $G_t\doteq r_{t+1}+\gamma G_{t+1}$
• TD error: ${\delta }_t\doteq v_t(s_t)-{\bar{v}}_t$
  • compared to MC error: ${\delta }_t\doteq v_t(s_t)-G_t$

$\doteq$的意思是“定义为”，参考Sutton书中符号的定义

TD target

实际上我们这里的TD learning的目的就是使得随着迭代次数$t$的增加，TD error ${\delta }_t$逐渐减小，最终收敛到0，即$v_t(s_t)\to {\bar{v}}_t$，所以${\bar{v}}_t$又叫做TD target；

简单证明如下：

$$\begin{array}{rl}{v}_{t+1}(s_t)& =v_t(s_t)-{\alpha }_t(s_t)[v_t(s_t)-{\bar{v}}_t]\\ ⟹v_{t+1}(s_t)-{\bar{v}}_t& =v_t(s_t)-{\bar{v}}_t-{\alpha }_t(s_t)[v_t(s_t)-{\bar{v}}_t]\\ ⟹v_{t+1}(s_t)-{\bar{v}}_t& =(1-{\alpha }_t(s_t))[v_t(s_t)-{\bar{v}}_t]\\ ⟹|v_{t+1}(s_t)-{\bar{v}}_t|& =|1-{\alpha }_t(s_t)||v_t(s_t)-{\bar{v}}_t|\\ ⟹|v_{t+1}(s_t)-{\bar{v}}_t|& \le |v_t(s_t)-{\bar{v}}_t|\end{array}$$

最后一个小于等于号成立的原因是 $0<1-{\alpha }_t(s_t)<1$，而且从最后一个式子可以看出${\delta }_t$是指数级逐渐减小的，最终收敛到0。

TD error

$${\delta }_t=\underset{\text{current estimate}}{\underbrace{v_t(s_t)}}-\underset{\text{better estimate: }{\bar{v}}_t}{\underbrace{\left[r_{t+1}+\gamma v_t(s_{t+1})\right]}}$$

• it reflects the difference between two time steps $v_{t+1}$ and $v_t$

• it reflects the difference between $v_t$ and $v_{\pi }$

  $${\delta }_{\pi ,t}\doteq v_{\pi }(s_t)-\left[r_{t+1}+\gamma v_{\pi }(s_{t+1})\right]$$

  We know from Chapter 02 state value

  $$\begin{array}{rl}{v}_{\pi }(s)& ={\mathbb{E}}_{\pi }[G_t\mid S_t=s]\\ & ={\mathbb{E}}_{\pi }[R_{t+1}+\gamma G_{t+1}\mid S_t=s]\\ & ={\mathbb{E}}_{\pi }[R_{t+1}+\gamma v_{\pi }(S_{t+1})\mid S_t=s]\end{array}$$

  So we have

  $${\mathbb{E}}_{\pi }[{\delta }_{\pi ,t}|S_t=s_t]=v_{\pi }(s_t)-{\mathbb{E}}_{\pi }[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s_t]=0$$
  • if $v_t=v_{\pi }$, then ${\delta }_t=0$ (we want to achieve this)
  • if ${\delta }_t\ne 0$, then $v_t\ne v_{\pi }$

• the TD error means information-gap(innovation) obtained from the new experience sample $(s_t,r_{t+1},s_{t+1})$

MC error & TD error

这里直接参考了Sutton书里的一个非常直观的数学证明(6.6)：

Note that if the array V does not change during the episode (as it does not in Monte Carlo methods), the Monte Carlo error can be written as a sum of TD errors:

$$\begin{array}{rl}\underset{\text{MC error}}{\underbrace{G_t-V(S_t)}}& =\underset{G_t}{\underbrace{R_{t+1}+\gamma G_{t+1}}}-V(S_t)+\underset{0}{\underbrace{\gamma V(S_{t+1})-\gamma V(S_{t+1})}}\\ & =\underset{\text{TD error }{\delta }_t}{\underbrace{R_{t+1}+\gamma V(S_{t+1})-V(S_t)}}+\gamma \underset{\text{next MC error}}{\underbrace{(G_{t+1}-V(S_{t+1}))}}\\ & ={\delta }_t+\gamma \left({\delta }_{t+1}+\gamma (G_{t+2}-V(S_{t+2}))\right)\\ & ={\delta }_t+\gamma {\delta }_{t+1}+{\gamma }^2{\delta }_{t+2}^2+\cdots +{\gamma }^{T-t}\underset{\text{final MC error=0}}{\underbrace{(G_T-V(S_T))}}=\sum _{k=t}^T{\gamma }^{k-t}{\delta }_k.\end{array}$$

注意这里的${\delta }_t$跟上面的${\delta }_t$的意思不一样

Others

• the TD(0) in (3) is also called one-step TD
• only estimate the state value of a given policy $\pi$
  • does not estimate the action values like MC methods(TODO LATER⇒Sarsa)
  • does not search for optimal policies like DP(PI,VI) methods(TODO LATER⇒Qlearning)

The idea of TD learning

Q: TD algorithm在做什么mathematically

A: Given a policy $\pi$, to solve the Bellman equation use model-free method.

回顾之前出现过的几种解贝尔曼方程的算法closed-form solution&iterative solution，我们之前用过迭代的方式来逐渐逼近$v_{\pi }$，TD也是采取迭代的方式来做，只不过和之前有所不同：

1. 这里的迭代是incremental的，每次只需要一个新的experience sample $(s_t,r_{t+1},s_{t+1})$，然后就可以更新$v_t(s_t)$，这样就可以逐渐逼近$v_{\pi }$
   • 和MC不同，MC需要一个完整的episode，然后才能get mean expectation，从而更新$v(s)$, MC is non-incremental
2. 这里的迭代是model-free的，不需要知道环境的具体模型，只需要知道下一步的state和reward即可
   • 和DP不同，DP需要知道环境的具体模型，然后才能通过迭代来逼近$v_{\pi }$，DP is model-based

Use RM to solve Bellman Equation

By definition of state value of a policy $\pi$:

$$\begin{array}{rl}{v}_{\pi }(s)& ={\mathbb{E}}_{\pi }[G_t\mid S_t=s]\\ & ={\mathbb{E}}_{\pi }[R+\gamma G_{t+1}\mid S_t=s],\forall s\in \mathcal{S}\end{array}$$

Where $G$ is the discounted return of the next state $S^{\prime }$:

$$\begin{array}{rl}{\mathbb{E}}_{\pi }[G_{t+1}\mid S_t=s]& =\sum _a\pi (a|s)\sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })\\ & =\mathbb{E}[v_{\pi }(S_{t+1})\mid S_t=s]\end{array}$$

• for derivation of the first equation, see here

So we have

$$v_{\pi }(s)=\mathbb{E}[R+\gamma v_{\pi }(S_{t+1})\mid S_t=s]$$

• sometimes called the Bellman expectation equation

Solve the Bellman equation by RM:

$$\begin{array}{rl}g(v(s))& =v(s)-\mathbb{E}[R+\gamma v_{\pi }(S^{\prime })\mid s]=0\\ \tilde{g}(v(s))& =v(s)-[r+\gamma v_{\pi }(s^{\prime })]\\ & =\underset{g(v(s))}{\underbrace{\left(v(s)-\mathbb{E}[R+\gamma v_{\pi }(S^{\prime })\mid s]\right)}}+\underset{\eta }{\underbrace{\left(\mathbb{E}[R+\gamma v_{\pi }(S^{\prime })\mid s]-[r+\gamma v_{\pi }(s^{\prime })]\right)}}\end{array}$$

Then we can use the RM to solve $g(v(s))=0$ by the following iterative update:

$$\begin{array}{rl}{v}_{k+1}(s)& =v_k(s)-{\alpha }_k\tilde{g}(v_k(s))\\ & =v_k(s)-{\alpha }_k\left(v_k(s)-\left[r_k+\gamma v_{\pi }(s_k^{\prime })\right]\right),k=1,2,3,\dots \end{array}$$

where

• $v_k(s)$ is the estimated state value of $v_{\pi }(s)$ at $k$th step;
• $r_k,s_k^{\prime }$ samples from $R$ and $S^{\prime }$ at $k$th step;
• ${\alpha }_k$ is the learning rate at $k$th step.

Modify RM and we get TD learning algorithm

1. 从上面RM形式我们可以看出如果希望求解出$v_{\pi }(s)$，即$v_k(s)\to v_{\pi }(s)$，就需要获得一系列sample, $\{(s,r_k,s_k^{\prime }){\}}_{k=1}^K$，然后通过迭代的方式来逐渐逼近$v_{\pi }(s)$，当然这里还要加一个条件$\forall s\in \mathcal{S}$，即需要对所有的state都要有对应的samples才能迭代求解；
2. 很自然的，我们在轻松地与环境多次只进行一步交互，并采集大量的这种sample；但是如果只是一步，为什么我们不交互到结束为止呢？这样我们就可以利用一个完整的episode所有的visit了(就像MC episode by episode一样来更新)，那么我们获得的sample就可以写成这种形式$\{(s_t,r_{t+1},s_{t+1}){\}}_{t=1}^{T-1}$
3. 对数据采集做完修改之后，那么我们上面几个变量也可以做几个修改：
   • $v_k(s)\to v_k(s_t)$
   • $r_k\to r_{t+1}$
   • $s_k^{\prime }\to s_{t+1}$
4. 再根据TD error，我们可以用$v_k(s_{t+1})$替换$v_{\pi }(s_{t+1})$
5. 至此我们一步一步用RM来解BE，最后推出了TD learning algorithm $$\begin{array}{rl}{v}_{k+1}(s_t)& =v_k(s_t)-{\alpha }_k(s_t)\left[v_k(s_t)-\left[r_{t+1}+\gamma v_k(s_{t+1})\right]\right],\\ v_{k+1}(s_t)& =v_k(s_t),\forall s\ne s_t,\end{array}$$ where $k=0,1,2,...$

Convergence of TD learning

By the TD learning algorithm, $v_t(s)$ converges w.p.1 to $v_{\pi }(s)$ for all $s\in \mathcal{S}$ as $t\to \infty$ if:

1. ${\sum }_t^{\infty }{\alpha }_t(s)=\infty$ for all $s\in \mathcal{S}$ $$\{\begin{array}{l}{\alpha }_t(s)>0,\text{if }s=s_t,\\ {\alpha }_t(s)=0,\text{if }s\ne s_t.\end{array}\Rightarrow \sum _t^{\infty }{\alpha }_t(s)=\infty$$ requires every state is visited infinitely(or sufficiently many many times) often
2. ${\sum }_t^{\infty }{\alpha }_t^2(s)<\infty$ for all $s\in \mathcal{S}$
   • In practice, we can use a small constant learning rate ${\alpha }_t(s)=\alpha$ for all $s\in \mathcal{S}$, though it may not satisfy the above conditions.

TD learning vs. MC learning

这一节其实可以放在学完简单的Sarsa之后再来看

TD/Sarsa learning	MC learning
Online: TD learning is online. It can update the state/action values immediately after receiving a reward.	Offline: MC learning is offline. It has to wait until an episode has been completely collected.
Continuing tasks: Since TD learning is online, it can handle both episodic and continuing tasks.	Episodic tasks: Since MC learning is offline, it can only handle episodic tasks that has terminate states.
Bootstrapping: TD bootstraps because the update of a value relies on the previous estimate of this value. Hence, it requires initial guesses.	Non-bootstrapping: MC is not bootstrapping, because it can directly estimate state/action values without any initial guess.
Low estimation variance: TD has lower than MC because there are fewer random variables. For instance, Sarsa requires $R_{t+1},S_{t+1},A_{t+1}$.	High estimation variance: To estimate $q_{\pi }(s_t,a_t)$, we need samples of $R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots$. Suppose the length of each episode is $L$. There are $\Vert \mathcal{A}{\Vert }^L$ possible episodes.

bootstrapping的意思是“自举”，即通过已有的估计值来估计新的值，有点像递归的意思，而non-bootstrapping则是直接用sample来估计值，不依赖于已有的估计值