Exercise 5.2.2

SARSA: derive sampled policy-evaluation update, role of alpha and gamma

Reinforcement Learning › Exercises › Lecture 5 · Model-Free Control › 5.2 SARSA: on-policy TD control
EasyWritten

Dynamic programming algorithms are based on expectation equations for updates. These equations require full knowledge of the model, such as the transition function, to compute a single iteration. One way to iterate over the equation while avoiding the need to know the full model is by using a sampled version of the expectation equation. This sampled version is referred to as the model-free version of the expectation equation.

Consider the Policy Evaluation dynamic programming update equation:

\[q_{k+1}(s, a) = \mathbb{E}[R_{t+1} + \gamma q_k(S_{t+1}, A_{t+1}) \mid S_t = s, A_t = a],\] where \(q_{k+1}(s, a)\) represents the value of a Q-table at state \(s\) and action \(a\) at iteration \(k+1\), and \(t\) is the time-step.

  • (a) Convert the equation above into its sampled version.

  • (b) Which model-free algorithm does this equation represent?

  • (c) Why do we use a learning rate in the sampled version of the equation? What is its role?

  • (d) What is the role of the discount factor \(\gamma\)?

  • (e) Under what conditions is convergence to the optimal Q-values guaranteed in the sampled version of the update equation you found? Does using the greedy policy as the behavior policy provide this guarantee?

  • (f) Your sampled equation relies on bootstrapping for its updates. Describe a possible limitation of this approach, particularly in the early stages of learning.