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

Convergence of Sarsa Theorem

Sarsa converges to the optimal action-value function, under the follow conditions:

• 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$)

I guess there’s a Sarsa ($\lambda$) version similar to how there’s a TD-Lambda version.