State Value from Action Values

1. Background Knowledge

In Reinforcement Learning, the state value function $V^\pi(s)$ represents the expected return starting from state $s$ and following policy $\pi$ thereafter. The action value function $Q^\pi(s, a)$ represents the expected return starting from state $s$, taking action $a$, and then following $\pi$. The relationship between them is fundamental: the state value is simply the expectation of the action value under the policy distribution.

Mathematically, if $\pi(a \mid s)$ is the probability of taking action $a$ in state $s$, then:

$$V^\pi(s) = \sum_{a} \pi(a \mid s) \, Q^\pi(s, a)$$

This is a weighted average where the weights are the policy probabilities. Note that $\sum_a \pi(a \mid s) = 1$ for a valid probability distribution, so $V^\pi(s)$ lies within the range of the $Q^\pi(s, a)$ values. This concept is central to policy evaluation and policy improvement algorithms like Policy Iteration and Q-Learning.

2. Algorithm Approach

The problem reduces to computing a dot product between two vectors: the policy vector $\pi$ and the action value vector $Q$. Since both vectors are aligned by action index, the $i$-th element of $\pi$ corresponds to the $i$-th element of $Q$.

The general pattern is:

1. Verify that the inputs are valid (same length, non-negative probabilities, probabilities sum to 1).
2. Compute the element-wise product of $\pi$ and $Q$.
3. Sum the resulting products.

This is a standard expectation calculation for a discrete random variable, where $Q$ is the variable and $\pi$ is its probability mass function.

3. Step-by-Step Strategy

1. Input Validation:

• Check that pi and q have the same length.
• Optionally, verify that pi is a valid probability distribution (all elements $\geq 0$ and $\sum \pi = 1$). This helps catch bugs early but may not be required by the problem.