Exercise 5.3.5
DP vs sampled updates: model-free counterparts, no sampled value iteration
Reinforcement Learning › Exercises › Lecture 5 · Model-Free Control › 5.3 Q-learning (off-policy learning)
Consider the dynamic programming algorithms and their update equations, shown in Table 1.
| Algorithm | Update Equation |
|---|---|
| Policy Evaluation | \(v_{k+1}(s) = \mathbb{E}[R_{t+1} + \gamma v_k(S_{t+1}) \mid S_t = s, A_t \sim \pi(S_t)]\) |
| Value Iteration | \(v_{k+1}(s) = \max_a \mathbb{E}[R_{t+1} + \gamma v_k(S_{t+1}) \mid S_t = s, A_t = a]\) |
| Policy Evaluation | \(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]\) |
| Value Iteration | \(q_{k+1}(s, a) = \mathbb{E}[R_{t+1} + \gamma \max_{a'} q_k(S_{t+1}, a') \mid S_t = s, A_t = a]\) |
-
(a) For each dynamic programming algorithm, state its equivalent sampled version, with the exception of value iteration for the state-value function.
-
(b) Why is there no sampling-based algorithm that corresponds directly to value iteration for the state-value function? What conditions would need to be satisfied for such an algorithm to exist?