Exercise 4.1.1
First-visit and every-visit MC: values of A and B, with and without discounting
Consider an MDP with two non-terminal states \(A\) and \(B\) and a terminal state \(T\). An episode ends if the agent enters state \(T\). Let the reward be +1 if the agent ends up in state \(A\) (so either from \(B\) to \(A\), or from \(A\) to \(A\)). All other transitions have a reward of 0. The allowed transitions (denoted by arrows) and a sketch of the dynamics can be found in Figure 1. Let \(\gamma=1\) and suppose we observe a sequence of states and rewards, given in Table 1.
| \(t\) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| \(S_t\) | A | A | A | B | A | A | A | B | T |
| \(R_t\) | - | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 |
-
(a) What are the first-visit and every-visit estimators of the value of \(A\) and \(B\), assuming arbitrary initialization \(v(s)=0\) for all \(s \in \mathcal{S}\)?
-
(b) Considering an unknown discount factor \(\gamma\) and the given numerical values for the rewards, what are the algebraic expressions for \(G_0\) and \(G_3\)?
-
(c) Changing to \(\gamma = 0.95\), what are the first-visit and every-visit estimators of the value of \(A\) and \(B\), assuming arbitrary initialization \(v(s)=0\) for all \(s \in \mathcal{S}\)?
Hint: If you decide to write code, feel free to use this as input. Be careful about the indices (you can check if the implementation is correct with \(\gamma=1\) from the previous part).
visited_states = ["A", "A", "A", "B", "A", "A", "A", "B"] rewards = [1, 1, 0, 1, 1, 1, 0, 0]