Monte Carlo Policy Evaluation

TD learning updates its estimates from its own guesses. Monte Carlo evaluation refuses to guess: it plays whole episodes to the end, measures what actually happened, and averages.

Task: write mc_evaluate(episodes, gamma) returning a dictionary mapping each state to its estimated value, rounded to 4 decimal places.

• episodes is a list of episodes. Each episode is a list of [state, reward] steps, in the order they happened.
• For each step, its return is everything collected from there to the end of the episode, discounted:

• Use first-visit averaging: within one episode, if a state appears more than once, only its earliest occurrence contributes a return. Later visits in that same episode are skipped.
• A state's value is the mean of all the returns collected for it, across every episode.
• Only include states that actually appear.

The neat way to get the returns is to walk the episode backwards with a running total: g = reward + gamma * g, starting from g = 0. One pass, no powers of gamma to track.

First-visit is the rule that makes the averaging statistically clean — counting both visits of a repeated state would give that episode two correlated samples pretending to be independent ones, and bias the estimate.