Exercise 4.1.1

First-visit and every-visit MC: values of A and B, with and without discounting

EasyWrittenCoding

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.

diagram
Figure 1: Diagram of the described MDP. Entering (or re-entering) state \(A\) gives a reward of \(+1\) and all other transitions have a reward of 0. An episode ends if the agent enters state \(T\).
Table 1: The sequence of random state transitions and received rewards.
\(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]

    Open (c) in the code workspace →