First-Visit Monte Carlo Prediction

First-Visit Monte Carlo prediction estimates the value of a state by averaging returns from episodes, counting only the first visit to that state in each episode.

The problem, from first principles

Given episodes (trajectories) from a fixed policy π, estimate V^π(s) for each state s. Unlike bootstrapping, MC uses full episode returns without a model. The "first-visit" constraint ensures independence: each episode contributes at most one return for state s.

From theory to code

Implement estimate_state_values(episodes, gamma) which:

• Takes a list of episodes (each is a list of (state, reward) tuples)
• Takes discount factor γ
• Returns a dict {state: estimated_value}

Use first-visit semantics and unbiased averaging.

Constraints

• Each episode is a list of (state, reward) pairs
• Only count the first visit to each state per episode
• Return a dict mapping states to float values
• If a state never appears, it doesn't appear in the dict (or value 0.0)

Hints