TD Convergence Analysis
Intermediate
Analyze TD(0) convergence on a simple environment: track how V estimates converge to true values as episodes increase.
The problem, from first principles
TD learns online by bootstrapping. Does it converge? How fast? This question asks you to implement TD(0) and measure convergence rate, comparing to known ground truth values.
From theory to code
Implement td_convergence_analysis(episodes, true_values, gamma, alpha) which:
- Takes episodes (list of (state, reward, next_state) tuples)
- Takes dict of true_values {state: true_value}
- Runs TD(0) with given gamma and alpha
- Returns (V_estimates, mse_per_episode) where MSE is mean squared error vs true values
Constraints
- episodes are a list of complete episode sequences
- true_values is ground truth for comparison
- alpha is learning rate
- Return both final estimates and MSE trajectory
Hints
Hint 1: Run TD incrementally
Process episodes one by one, tracking MSE after each.Hint 2: Compute MSE
For each state visited, compute (V_estimate - true_value)^2 and average.Hint 3: Track convergence
Record MSE after each episode in a list.Keywords
rltemporal-differenceconvergenceanalysis
Python
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.