AI: Temporal-difference learning

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 VALUE for 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}")

Lesson: Reinforcement learning →