Learn action values from a log of experience, the way replay buffers work in deep reinforcement learning.
What to build
A program that applies Q-learning updates to a list of recorded transitions and prints the learned values and greedy policy.
Requirements
- Each transition is
s a r s′;endis a terminal state with no actions. Apply Q(s, a) ← Q(s, a) + α (target − Q(s, a)) for every transition in order, repeating the whole list the given number of times. - For every state that appears (other than
end), sorted by name, printS: A1 Q1 A2 Q2 … | best Awith Q-values to three decimal places, in the order the actions are listed; the best action is the first with the largest Q.
Input
Line 1: α, γ and the number of passes. Line 2: the actions. Line 3: t. Then t transitions.
Output
One line per state.
Constraints
t ≤ 100, passes ≤ 50.
Example
Input:
0.5 0.9 1
left right
2
A right 0 B
B right 1 end
Output:
A: left 0.000 right 0.000 | best left
B: left 0.000 right 0.500 | best right
Why it works
Each update moves Q(s, a) towards the reward plus the value of acting best from the next state, so repeated passes spread the value of rewards backwards through the states.
Examples
0.5 0.9 1 left right 2 A right 0 B B right 1 end
A: left 0.000 right 0.000 | best left B: left 0.000 right 0.500 | best right
0.5 0.9 2 left right 2 A right 0 B B right 1 end
A: left 0.000 right 0.225 | best right B: left 0.000 right 0.750 | best right
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Keep a dictionary Q[(state, action)], 0 by default; the target is r + γ × max over actions of Q[(s′, a)], or just r when s′ is `end`.
Hint 2
Replay the whole list of transitions as many times as asked, in order, before printing.
Solution
Show one correct solution (try it yourself first)
alpha, gamma, passes = input().split()
alpha, gamma, passes = float(alpha), float(gamma), int(passes)
actions = input().split()
log = [input().split() for _ in range(int(input()))]
Q = {}
states = set()
for s, a, r, s2 in log:
states.update([s, s2])
states.discard("end")
for _ in range(passes):
for s, a, r, s2 in log:
target = float(r) if s2 == "end" else float(r) + gamma * max(Q.get((s2, b), 0.0) for b in actions)
Q[(s, a)] = Q.get((s, a), 0.0) + alpha * (target - Q.get((s, a), 0.0))
for s in sorted(states):
values = [Q.get((s, a), 0.0) for a in actions]
best = actions[values.index(max(values))]
print(f"{s}: " + " ".join(f"{a} {v:.3f}" for a, v in zip(actions, values)) + f" | best {best}")