TD Sarsa

Temporal-Difference Sarsa

Introduction

• TD algorithm introduced before to estimate state values
• now we intoduce Sarsa to directly estimate action values
• aim is to estimate the action values of a given policy $\pi$

Algorithm

Suppose we hava some experience $\{(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})\}$

We can use the following Sarsa algorithm to estimate the action values of a given policy $\pi$:

$$\begin{array}{rl}{q}_{k+1}(s_t,a_t)& =q_k(s_t,a_t)-{\alpha }_k(s_t,a_t)\left[q_k(s_t,a_t)-\left[r_{t+1}+\gamma q_k(s_{t+1},a_{t+1})\right]\right],\\ q_{k+1}(s,a)& =q_k(s,a),\forall (s,a)\ne (s_t,a_t).\end{array}$$

where $k=0,1,2,\dots$

• $q_k(s_t,a_t)$ is an estimate of $q_{\pi }(s_t,a_t)$
• ${\alpha }_k(s_t,a_t)$ is the learning rate depending on $s_t,a_t$

一些问题

1. 为什么这个算法叫做Sarsa？$\text{Sarsa}$ is $\text{State-Action-Reward-State-Action}$, 因为算法的每一步都要包含$(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})$
2. Sarsa和之前的TD learning的relationship是什么呢？sarsa用action value来估计，而TD learning用state value来估计，换言之，sarsa 其实是 action-value version of TD learning
3. What does Sarsa do mathematically? Sarsa is a stochastic approximation algorithm to solve the following equation(another expression of the Bellman equation in terms of action values): $$q_{\pi }(s,a)={\mathbb{E}}_{\pi }\left[R+\gamma q_{\pi }(S^{\prime },A^{\prime })\right|s,a],\forall s,a.$$

Convergence

By the Sarsa algorithm, $q_t(s,a)$ converges with probability 1 to the action value $q_{\pi }(s,a)$ as $t\to \infty$ for all $(s,a)$ if ${\sum }_t{\alpha }_t(s,a)=\infty$ and ${\sum }_t{\alpha }_t^2(s,a)<\infty$ for all $(s,a)$.

Remarks

Just say that the action values can be found by Sarsa for a given policy $\pi$ if the learning rates satisfy the conditions.

Implementation

可以对比Algorithm的实现来看这里的改进

$$\boxed{\begin{array}{rl}& \text{Algorithm}\text{Policy Search by SARSA(on-policy TD) with }\epsilon \text{-Greedy}\\ & \text{Initialization: }\text{Initial policy }{\pi }_0(a|s)\text{, value function }q(s,a)\text{ for all }(s,a).\text{ Step size }\alpha \in (0,1].\\ & \text{For each episode, do:}\\ & \text{Initialize state }{s}_0.\\ & \text{Select action }{a}_0\text{ using }{\pi }_0(s_0).\\ & \text{While }{s}_t\text{ is not the target state, do:}\\ & \text{Execute }{a}_t\text{, observe }{r}_{t+1},s_{t+1}.\\ & \text{Select }{a}_{t+1}\text{ using }{\pi }_t(s_{t+1}).\\ & \text{Update }q(s_t,a_t):\\ & q(s_t,a_t)\leftarrow q(s_t,a_t)-\alpha \left[q(s_t,a_t)-\left[r_{t+1}+\gamma q(s_{t+1},a_{t+1})\right]\right]\\ & \text{Update policy for }{s}_t:\\ & {\pi }_{t+1}(a|s_t)\leftarrow \{\begin{array}{ll}1-\epsilon +\frac{\epsilon }{|\mathcal{A}(s_t)|},& \text{if }a=\arg {\max }_{a^{\prime }}q(s_t,a^{\prime })\\ \frac{\epsilon }{|\mathcal{A}(s_t)|},& \text{otherwise}\end{array}\\ & s_t\leftarrow s_{t+1},a_t\leftarrow a_{t+1}\end{array}}$$

n-step Sarsa

n-step Sarsa Core Idea

非常自然的，受之前的BGD>MBGD>SGD(batch size的折中)和PI>TPI>VI(policy evaluation iteration的折中)，我们这里也可以对MC(一个完整的episode)和Sarsa(一个episode中的一步)进行折中(需要n-step)

The definition of action value is

$$q_{\pi }(s,a)=\mathbb{E}[G_t\mid S_t=s,A_t=a]$$

The discounted return $G_t$ can be rewritten in different form as

$$\begin{array}{rl}\text{Sarsa}\leftarrow G_t^{(1)}& =R_{t+1}+\gamma q_{\pi }(S_{t+1},A_{t+1})\\ G_t^{(2)}& =R_{t+1}+\gamma R_{t+2}+{\gamma }^2{q}_{\pi }(S_{t+2},A_{t+2})\\ ⋮& \\ \text{n-step Sarsa}\leftarrow G_t^{(n)}& =R_{t+1}+\gamma R_{t+2}+\cdots +{\gamma }^n{q}_{\pi }(S_{t+n},A_{t+n})\\ ⋮& \\ \text{MC}\leftarrow G_t^{(\infty )}& =R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+2}+\cdots \end{array}$$

注意

这里的$G_t=G_t^{(1)}=G_t^{(2)}=G_t^{(n)}=G_t^{(\infty )}$，这里只是写成不同的展开形式，可能还有点疑惑为什么是这样：此时应该注意观察这个$q_{\pi }$，这个是真实的action value，并不等同于$q_t$，所以这里的所有$G_t$都是一样的，只不过是前瞻的步数不同。

n-step Sarsa Algorithm

• Sarsa aims to solve: $$q_{\pi }(s,a)=\mathbb{E}[G_t^{(1)}|s,a]=\mathbb{E}[R_{t+1}+\gamma q_{\pi }(S_{t+1},A_{t+1})|s,a]$$
• MC aims to solve: $$q_{\pi }(s,a)=\mathbb{E}[G_t^{(\infty )}|s,a]=\mathbb{E}[R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+2}+\cdots |s,a]$$
• n-step Sarsa aims to solve: $$q_{\pi }(s,a)=\mathbb{E}[G_t^{(n)}|s,a]=\mathbb{E}[R_{t+1}+\gamma R_{t+2}+\cdots +{\gamma }^n{q}_{\pi }(S_{t+n},A_{t+n})|s,a]$$
• n-step Sarsa algorithm $$q_{k+1}(s_t,a_t)=q_k(s_t,a_t)-{\alpha }_k(s_t,a_t)\left[q_k(s_t,a_t)-G_t^{(n)}\right]$$
  • becomes Sarsa when $n=1$
  • becomes MC when $n=\infty$

Remarks

1. n-step Sarsa needs data $(s_t,a_t,r_{t+1},s_{t+1},a_{t+1},\cdots ,r_{t+n},s_{t+n},a_{t+n})$
2. 这里的n-step Sarsa就是在policy evaluation做了一点小小改进
3. 再n-th step之前我们都是不能update q value的，必须等他收集完
4. if n is large, more like MC(large variance, small bias); if n is small, more like Sarsa(small variance, large bias due to initial guess)

Expected Sarsa

Expected Sarsa Core Idea

回顾当时学习Bellman Equation的三条公式，我们可以写出下面两条公式：

1. $v_{\pi }=\pi @q_{\pi }=\pi @(P_{r}R+\gamma P_s{v}_{\pi })$
2. $q_{\pi }=P_{r}R+\gamma P_s{v}_{\pi }=P_{r}R+\gamma P_s\pi @q_{\pi }$

受之启发，我们有了几个算法：

• 由第一条公式(state value的bootstrapping)，我们推出了上一节TD state values $$q_{\pi }(s)={\mathbb{E}}_{\pi }[R_{t+1}+\gamma v_{\pi }(S_{t+1})\mid S_t=s]$$
• 由第二条公式(action value的bootstrapping)，我们推出了Sarsa $$q_{\pi }(s,a)={\mathbb{E}}_{\pi }\left[R_{t+1}+\gamma q_{\pi }(S_{t+1},A_{t+1})\mid S_t=s,A_t=a\right]$$
• 但Sarsa的缺点是只考虑了next state一个action的q，我们这里其实可以考虑next state所有action的q的期望（也即$\pi @q_{\pi }$，恰好就是我的next state value），用q的期望去代替原本的一个q显然更精确（low variance），在编程中也很容易实现，向量相乘$@$就可以了。于是我们推出了Expeceted Sarsa $$\begin{array}{rl}{q}_{\pi }(s,a)& ={\mathbb{E}}_{\pi }\left[R_{t+1}+\gamma {\mathbb{E}}_{\pi }[q_{\pi }(S_{t+1},A)]\mid S_t=s,A_t=a\right]\\ & ={\mathbb{E}}_{\pi }\left[R_{t+1}+\gamma \pi (S_{t+1})@q_{\pi }(S_{t+1})\mid S_t=s,A_t=a\right]\end{array}$$
• Later, 可以看到我们进一步的把取平均的操作继续去掉，改成直接取最大值（相当于令policy为greedy policy），这样就得到了Qlearning $$q_{\pi }(s,a)={\mathbb{E}}_{\pi }\left[R_{t+1}+\gamma \underset{a^{\prime }}{\max }{q}_{\pi }(S_{t+1},a^{\prime })\mid S_t=s,A_t=a\right]$$

Expected Sarsa Algorithm

与Sarsa对比，Expected Sarsa做出的主要改进在于：

$$q_k(s_{t+1},a_{t+1})\to {\mathbb{E}}_{\pi }[q_k(s_{t+1},A)]$$

Expected Sarsa algorithm

$$\begin{array}{rl}{q}_{k+1}(s_t,a_t)& =q_k(s_t,a_t)-{\alpha }_k(s_t,a_t)\left[q_k(s_t,a_t)-\left[r_{t+1}+\gamma {\mathbb{E}}_{\pi }[q_k(s_{t+1},A)]\right]\right],\\ q_{k+1}(s,a)& =q_k(s,a),\forall (s,a)\ne (s_t,a_t).\end{array}$$

Note that

$${\mathbb{E}}_{\pi }[q_k(s_{t+1},A)]=\sum _a{\pi }_k(a|s_{t+1})q_k(s_{t+1},a)\doteq v_k(s_{t+1})$$

Features:

• need more computation than Sarsa
• less variance than Sarsa because it reduces random varibles $$\{s_t,a_t,r_{t+1},s_{t+1},a_{t+1}\}\to \{s_t,a_t,r_{t+1},s_{t+1}\}$$

Sutton书中是如何评价Expected Sarsa的

“For example, suppose $\pi$ is the greedy policy while behavior is more exploratory; then Expected Sarsa is exactly Q-learning. In this sense Expected Sarsa subsumes and generalizes Q-learning while reliably improving over Sarsa. Except for the small additional computational cost, Expected Sarsa may completely dominate both of the other more-well-known TD control algorithms.”

也就是说，Expected Sarsa是一个很好的折中（关于greedy policy和exploratory policy的折中），可以同时包含Q-learning（Qlearning也有折中，但它是靠off-policy去解决这个事情的，也都是希望behavior policy more exploratory and target policy more greedy）和Sarsa，而且在很多情况下都会优于这两个算法（书中Figure 6.3说明了这个事实）。