Exercise 5.2.2
SARSA: derive sampled policy-evaluation update, role of alpha and gamma
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.