Exercise 8.1.1

Batch MC vs batch TD(0) with real and simulated experience (Dyna-Q)

MediumWritten

Place yourself in the role of the predictor of returns for an unknown Markov reward process. Suppose you observe the following eight episodes:

Table 1: Batch of Real Experience
Episode 1 Episode 2 Episode 3 Episode 4 Episode 5 Episode 6 Episode 7 Episode 8
A, 1, B, 0 B, 1 B, 1 B, 0 B, 1 B, 0 B, 1 B, 0

We call this batch a result of “real experiences". This means that the first episode started in state A, and transitioned to B with a reward of \(1\), and then transitioned from B to the terminal state with a reward of \(0\). The other seven episodes were even shorter, starting from B and terminating immediately.

  • 1) Draw the Markov process that can be inferred from this data.

  • 2) What is the state-value estimate of \(V(A)\) and \(V(B)\) when using: (a)Batch Monte Carlo, (b)Batch TD(0)? Consider \(\gamma = 1\).

  • 3) With the model created in item (1), inspired by Dyna-Q, you decided to generate a batch of simulated experiences. You collected the following batch:

    Table 2: Batch of Simulated Experience
    Episode 1 Episode 2 Episode 3 Episode 4 Episode 5 Episode 6 Episode 7 Episode 8
    B, 0 B, 1 B, 1 A, 0, B, 1 B, 1 A, 0, B, 0 B, 1 B, 1

    Considering the simulated experience and the real experience combined, what is the state-value estimate of \(V(A)\) and \(V(B)\) when using: (a)Batch Monte Carlo, (b)Batch TD(0)?

  • 4) Describe an advantage and disadvantage of using a model to improve the estimation of the state-value function.

Adapted from Sutton & Barto (2018), Reinforcement Learning: An Introduction, 2nd ed., Example 6.4. Licensed CC BY-NC-ND 2.0.