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) = Xfor each action in order (three decimal places), thenbest: 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)