Q-Values from State Values

mediumPRODynamic ProgrammingReinforcement LearningRL 1: Foundations

Problem Statement

Given state values V, recover the action values for one state. Each action a provides reward[a] and a next-state distribution P[a] (P[a][s']):

$Q(s,a) = reward[a] + \gamma \sum_{s'} P[a][s']\, V(s')$

Implement q_from_v(reward, P, gamma, V) returning the list of Q-values, one per action.

Example

Input

q_from_v([1.0, 0.0], [[1.0, 0.0], [0.0, 1.0]], 0.9, [0.0, 10.0])

Output

[1.0, 9.0]

Reasoning

Action 0 Calculation: For the first action, the immediate reward is $1.0$ . The expected value of the next state is computed by weighting the state values $V = [0.0, 10.0]$ by the transition probabilities $P[0] = [1.0, 0.0]$ , resulting in $1.0 \times 0.0 + 0.0 \times 10.0 = 0.0$ .
Action 0 Q-Value: The Q-value is the sum of the immediate reward and the discounted expected future value: $1.0 + 0.9 \times 0.0 = 1.0$ .
Action 1 Calculation: For the second action, the immediate reward is $0.0$ . The expected value of the next state is computed using the transition probabilities $P[1] = [0.0, 1.0]$ , resulting in $0.0 \times 0.0 + 1.0 \times 10.0 = 10.0$ .
Action 1 Q-Value: The Q-value is the sum of the immediate reward and the discounted expected future value: $0.0 + 0.9 \times 10.0 = 9.0$ .
The final output is [1.0, 9.0]

Constraints

len(reward) == len(P) (one row per action).
Each P[a] aligns with V and sums to 1.
Return a list of floats.

More from RL 1: Foundations

GAE Over a Full Trajectoryhard PPO Clipped Objective (Single Sample)medium TD Residuals for GAEmedium Return Standardization Baselinemedium REINFORCE Loss Termmedium

Concept primerPREVIEW

1. Background Knowledge

In reinforcement learning, the state-value function $V(s)$ estimates the expected return starting from state $s$ and following a policy $\pi$ . The action-value function $Q(s,a)$ estimates the expected return starting from state $s$ , taking action $a$ , and then following $\pi$ . These two functions are linked by the Bellman expectation equation:

Q(s,a) = R(s,a) + \gamma \sum_{s'} P(s' \mid s,a)\, V(s')

Here, $R(s,a)$ is the immediate reward, $\gamma \in [0,1]$ is the discount factor, and $P(s' \mid s,a)$ is the probability of transitioning to next state $s'$ . The sum represents the expected discounted value of all possible next states under the transition distribution for action $a$ .

This relationship is foundational in dynamic programming methods for RL. Given a fixed policy (or a fixed $V$ ), you can compute $Q$ directly via this expectation. Conversely, given $Q$ , you can recover $V(s) = \sum_a \pi(a \mid s)\, Q(s,a)$ . The problem you are solving is the forward direction: from a known $V$ , compute $Q$ for every action in a single state.

2. Algorithm Approach

The core pattern is a weighted sum over next states. For each action $a$ :

Start with the immediate reward $R(a)$ .
Compute the expected next-state value: $\sum_{s'} P(a, s') \cdot V(s')$ . This is a dot product between the transition probability vector for action $a$ and the state-value vector $V$ .
Multiply that expectation by $\gamma$ and add it to the immediate reward.

The result is $Q(a)$ . Repeat for every action. There is no iterative procedure or matrix inversion needed—this is a single-pass computation over the action list.

3. Step-by-Step Strategy

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results