Estimate state values from experience, one step at a time.
What to build
A program that runs TD(0) value updates over recorded episodes.
Requirements
- Each episode is
s0 r1 s1 r2 s2 … sT. All values start at 0. For each step in order, apply V(sₜ) ← V(sₜ) + α (rₜ₊₁ + γ V(sₜ₊₁) − V(sₜ)); the last state of an episode is terminal with value 0 and never appears anywhere else. - Print
STATE VALUEfor every non-terminal state, sorted by name, with four decimal places.
Input
Line 1: α and γ. Line 2: e. Then e episodes.
Output
One line per state.
Constraints
e ≤ 50; episodes have at most 50 steps.
Example
Input:
0.5 1
2
A 0 B 1 T
A 0 B 1 T
Output:
A 0.2500
B 0.7500
Why it works
Each update moves an estimate towards what actually followed, using the current estimate of the next state in place of the unknown future, so values improve after every single step.
Examples
Example 1 · Input
0.5 1 2 A 0 B 1 T A 0 B 1 T
Expected output
A 0.2500 B 0.7500
Example 2 · Input
0.1 0.9 1 S 5 T
Expected output
S 0.5000
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Walk through each episode pair by pair: state, reward, next state.
Hint 2
V(s) += α × (r + γ × V(next) − V(s)), where the episode's last state is terminal and always worth 0.
Solution
Show one correct solution (try it yourself first)
alpha, gamma = map(float, input().split())
V, terminal = {}, set()
episodes = [input().split() for _ in range(int(input()))]
for parts in episodes:
terminal.add(parts[-1])
for parts in episodes:
for i in range(0, len(parts) - 1, 2):
s, r, s2 = parts[i], float(parts[i + 1]), parts[i + 2]
nxt = 0.0 if s2 in terminal else V.get(s2, 0.0)
V[s] = V.get(s, 0.0) + alpha * (r + gamma * nxt - V.get(s, 0.0))
for s in sorted(V):
print(f"{s} {V[s]:.4f}")