Monte Carlo Policy Evaluation

Reinforcement Learning

Easy

Estimate a state-value function with first-visit Monte Carlo evaluation. Each episode is a list of [state, reward] pairs. For time step $t$ , the discounted return is:

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

For each state, use only its earliest occurrence in each episode and average those first-visit returns across episodes. States that are never visited retain value zero. Return all state values as a NumPy array of length n_states, rounded to four decimals.

Loading visualization...

Examples

Input: episodes = [[[0, 1], [1, 2], [2, 3]]], gamma = 1, n_states = 3

Output: [6, 5, 3]

Explanation: With no discounting, returns from the three positions are 6, 5, and 3.

Input: episodes = [[[0, 1], [0, -5], [0, 2]]], gamma = 1, n_states = 1

Output: [-2]

Hint 1

Fill a return array backward with running = reward + gamma * running.

Hint 2

Scan the episode forward with a set so only the first occurrence contributes.

Requirements

Compute every episode return backward
Use only the earliest occurrence of each state per episode
Average collected returns independently for each state
Return a NumPy array rounded to four decimals

Constraints

State indices range from zero through n_states - 1
0 <= gamma <= 1
Use NumPy only

Try Similar Problems

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

Prev Next