Initial Encounter Value Estimation from Episodic Experience

In reinforcement learning, one fundamental challenge is estimating how valuable it is to be in a particular state—known as the state value function. The Initial Encounter Value Estimation method is a model-free technique that learns these values directly from complete episodes of experience, without requiring knowledge of the environment's dynamics.

The core principle is elegantly simple: to estimate the value of a state, we observe what happens after visiting that state and compute the cumulative discounted return—the sum of all future rewards, with distant rewards weighted less than immediate ones.

The Initial Encounter Rule: When a state appears multiple times within a single episode, we only consider the return from its first appearance. Subsequent visits to the same state within that episode are ignored for value estimation purposes. This approach provides unbiased estimates and is particularly useful when states can be revisited during an episode.

Mathematical Foundation:

For each episode, given a trajectory of state-reward pairs: (S₀, R₀), (S₁, R₁), ..., (Sₜ, Rₜ), the return from time step k to the end of the episode is:

$$G_k = R_k + \gamma R_{k+1} + \gamma^2 R_{k+2} + ... + \gamma^{T-k} R_T = \sum_{i=0}^{T-k} \gamma^i R_{k+i}$$

Where:

• γ (gamma) is the discount factor (0 ≤ γ ≤ 1)
• T is the final time step of the episode
• Rₖ is the reward received at time step k

Value Estimation Process:

1. For each episode, identify the first occurrence of each unique state
2. Calculate the discounted return from that first visit to the episode's end
3. After processing all episodes, compute the average return for each state across all episodes where it was visited

The estimated value of state s is:

$$V(s) = \frac{1}{N(s)} \sum_{\text{first visits to } s} G_s$$

Where N(s) is the number of episodes containing a first visit to state s.

Your Task: Implement a function that processes a collection of episodes and computes the estimated value for each state encountered. The output should be formatted as a string showing each state's value rounded to 2 decimal places, sorted by state number.