Problems

1 / 1

Monte Carlo Policy Evaluation

Reinforcement Learning

Easy

Estimate the value function using Monte Carlo first-visit returns from episode data.

Mathematical Definition

Return from time t:

G_t = r_t + \gamma r_{t+1} + \gamma^{2} r_{t+2} + \cdots

First-Visit MC Value:

V(s) = \text{average of all first-visit returns for state } s

Function Arguments

episodes: list of episodes - each episode is list of (state, reward) tuples
gamma: float - discount factor
n_states: int - number of states (labeled 0..n_states-1)

Loading visualization...

Examples

Input: episodes=[[(0,1),(1,2),(2,3)]], γ=1, n_states=3

Output: V = [6.0, 5.0, 3.0]

Input: episodes=[[(0,1),(0,-5),(0,2)]], γ=1, n_states=1

Output: V = [-2.0] (only first visit counts)

Hint 1

Process each episode backward to compute returns: G_t=r_t+γG_t+1.

Hint 2

Use a set to track visited states per episode to ensure first-visit only.

Requirements

Use first-visit: only count first occurrence of each state per episode
Maintain running sum and count of returns per state
Return V as NumPy array of shape (n_states,)
States never visited should have value 0.0

Constraints

Number of episodes ≤ 1,000
Episode length ≤ 500
n_states ≤ 10,000
NumPy only
Time limit: 300ms

Try Similar Problems

Td Value Update Value Iteration Step Q Learning Update Sarsa Update Discount Returns

Prev Next