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)
MediumWritten

Consider the dynamic programming algorithms and their update equations, shown in Table 1.

Table 1: Dynamic programming algorithms and their update equations.
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?