TD Control

Sarsa

Sarsa is the implementation of On-Policy TD Control. Off-policy implementation of TD Control is Q-Learning.

It is very similar to the idea we do with Monte-Carlo Control, (replace policy evaluation with TD-Learning, use the same policy improvement method with epsilon greedy).

$Q^{\pi }(s_t,a_t)\leftarrow r_t+\gamma Q^{\pi }(s_{t+1},a_{t+1})$

Pseudocode

title:Convergence of Sarsa Theorem
Sarsa converges to the optimal action-value function, under the follow conditions:
- [[Greedy in the Limit with Infinite Exploration|GLIE]] sequence of policies
- Robbins-Monro sequence of step-sizes $\alpha_t$
 
$$\sum_{t=1}^\infty{\alpha_t = \infty}$$
$$\sum_{t=1}^\infty{\alpha_t^2 < \infty}$$
 
 
In practice, we don't worry about this.

How does SARSA actually converge?

Like if you start from a very shitty policy, SARSA is just going to learn $Q^{\pi }(s,a)$, not $Q^{\ast }(s,a)$, so how are you going to get a good policy?

• The answer lies in the Policy Improvement image above, Generalized Policy Iteration

Sarsa ($\lambda$)

Okay, I don’t understand this, just like I don’t quite understand TD($\lambda$).