AI: Q-learning from experience

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′; end is 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, print S: A1 Q1 A2 Q2 … | best A with 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

Example 1 · Input
0.5 0.9 1
left right
2
A right 0 B
B right 1 end
Expected output
A: left 0.000 right 0.000 | best left
B: left 0.000 right 0.500 | best right
Example 2 · Input
0.5 0.9 2
left right
2
A right 0 B
B right 1 end
Expected output
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}")

Lesson: Reinforcement learning →