Random Walk: TD vs Monte Carlo

MediumReinforcement Learning

Example:

Input:

episodes = [
    [(2, 0, 3, False), (3, 0, 4, False), (4, 1, -1, True)],
    [(2, 0, 1, False), (1, 0, 0, False), (0, 0, -1, True)]
]
n_states = 5, gamma = 1.0, alpha = 0.1

Output:

([0.0, 0.0, 0.0, 0.0, 0.1], [0.0, 0.0, 0.5, 1.0, 1.0])

Reasoning:

TD(0) processes transitions online. In episode 1: transitions (2->3), (3->4), (4->terminal with reward 1). Since all values start at 0, only V[4] gets a nonzero update: V[4] = 0 + 0.1*(1 - 0) = 0.1. In episode 2: transitions (2->1), (1->0), (0->terminal with reward 0). No values change since all targets are 0.

For first-visit MC, episode 1 yields return G=1 for all visited states (2,3,4) since gamma=1 and the only reward is 1 at the end. Episode 2 yields return G=0 for states (2,1,0). State 2 appears in both episodes, so its MC value is (1+0)/2 = 0.5. States 3 and 4 only appear in episode 1 with return 1. States 0 and 1 only appear in episode 2 with return 0.

Learn About topic

Contributors:

Deep-ML

Contribute

Random Walk: TD vs Monte Carlo

MediumReinforcement Learning

Intuition

Implement a function random_walk_td_mc that runs both TD(0) and first-visit Monte Carlo prediction on a set of random walk episodes and returns the value estimates from each method.

The random walk environment has n_states non-terminal states indexed from 0 to n_states-1. Two terminal states exist implicitly: one to the left of state 0 and one to the right of state n_states-1. Episodes are provided as pre-generated sequences of transitions.

Parameters:

episodes: A list of episodes. Each episode is a list of (state, reward, next_state, done) tuples. When done=True, the episode has terminated (the agent reached a terminal state). Non-terminal states are indexed 0 to n_states-1. Terminal next_states can be any value and should be ignored for value computation.
n_states: Integer, the number of non-terminal states.
gamma: Float, the discount factor (default 1.0).
alpha: Float, the learning rate for TD(0) (default 0.1).

Requirements:

Both methods should initialize all state values to 0.0.
TD(0) should process episodes in order, updating values online after each transition. When a transition is terminal, the successor value is treated as 0.
First-visit Monte Carlo should track returns only for the first visit to each state within an episode. After processing all episodes, the value for each state is the average of returns across all episodes where it was first visited.
Episodes should be processed in order for both methods.

Returns:

A tuple (td_values, mc_values) where each is a list of floats of length n_states representing the estimated values for states 0 through n_states-1.