AI: One Bellman backup

Compute the value of each action in one state.

What to build

A program that computes the expected value of every action in a state and picks the best.

Requirements

  • Each action has outcomes: a probability, the reward for that outcome and the value of the state it leads to. Q(a) = Σ p × (reward + γ × value).
  • Print Q(NAME) = X for each action in order (three decimal places), then best: NAME.

Input

Line 1: γ. Line 2: a. Then, for each action, a line NAME k followed by k lines p reward value.

Output

a + 1 lines.

Constraints

a ≤ 10, k ≤ 10.

Example

Input:

0.9
2
stay 1
1.0 0 10
go 2
0.8 1 20
0.2 -5 0

Output:

Q(stay) = 9.000
Q(go) = 14.200
best: go

Why it works

An action's worth is what it earns now plus the discounted value of where it leads, averaged over everything that can happen.

Examples

Example 1 · Input
0.9
2
stay 1
1.0 0 10
go 2
0.8 1 20
0.2 -5 0
Expected output
Q(stay) = 9.000
Q(go) = 14.200
best: go
Example 2 · Input
1.0
2
a 1
1 5 0
b 1
1 3 2
Expected output
Q(a) = 5.000
Q(b) = 5.000
best: a

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

For each action, add up probability × (reward + γ × value of the next state) over its outcomes.

Hint 2

The best action has the largest result; on a tie, keep the first.

Solution

Show one correct solution (try it yourself first)
gamma = float(input())
best_name, best_q = None, None
for _ in range(int(input())):
    name, k = input().split()
    q = 0.0
    for _ in range(int(k)):
        p, reward, value = map(float, input().split())
        q += p * (reward + gamma * value)
    print(f"Q({name}) = {q:.3f}")
    if best_q is None or q > best_q:
        best_name, best_q = name, q
print("best:", best_name)

Lesson: Markov decision processes →