State-Value and Action-Value Functions

A <span class="wiki-link-missing">Markov decision process</span> (MDP) consists of states $s \in \mathcal{S}$, actions $a \in \mathcal{A}$, a transition function giving $p(s', r \mid s, a)$, and a discount factor $\gamma \in [0,1]$. A policy $\pi$ is a mapping from states to probabilities over actions: $\pi(a \mid s)$ is the probability of choosing action $a$ while in state $s$. Given a trajectory that starts at time $t$, the return is the discounted sum of future rewards,

The return is a random variable: it depends on the random sequence of states, actions, and rewards that unfold after time $t$, which in turn depend on both the policy's randomness and the environment's randomness. The state-value function for policy $\pi$ is the expected return starting from state $s$ and following $\pi$ thereafter:

The action-value function (also called the Q-function) is the expected return starting from state $s$, taking action $a$ immediately, and then following $\pi$:

The subtlety that separates the two definitions is the fate of the first action. In $v_\pi(s)$, the first action is chosen by the policy according to $\pi(\cdot \mid s)$. In $q_\pi(s,a)$, the first action is pinned to $a$ regardless of what the policy would normally do, and only the actions afterward obey $\pi$. This is why $q_\pi$ is strictly more informative: it tells you the consequence of every possible first move, not just the moves the policy happens to favor. Because $v_\pi(s)$ averages over the policy's own choice of first action, and $q_\pi(s,a)$ is the value conditional on that first action, the two are related by a simple expectation:

This identity is not an approximation or a modeling choice — it follows directly from the law of total expectation applied to the random variable $A_t$, conditioned on $S_t = s$. Symmetrically, $q_\pi$ can be expressed using $v_\pi$ evaluated one step into the future, by conditioning on the immediate reward and next state produced by the environment's dynamics $p(s', r \mid s, a)$:

Together these two identities form a tight loop: $v_\pi$ is built from $q_\pi$ by averaging over the policy, and $q_\pi$ is built from $v_\pi$ by averaging over the environment's transition dynamics. Substituting one into the other produces the recursive self-referential equation known as the Bellman equation for $v_\pi$, which is the natural next object of study, along with its action-value counterpart and, eventually, the optimality equations that characterize the best possible policy.

Since $v_\pi$ and $q_\pi$ are defined as expectations over an infinite (or long) random trajectory, computing them exactly requires either (a) an explicit model of the environment's dynamics, solved analytically or by dynamic programming, or (b) empirical estimation by sampling many trajectories and averaging observed returns — the Monte Carlo approach. Because this article's prerequisite level assumes only the definitions of policies and value functions (not yet the Bellman machinery), the cleanest way to compute — rather than merely define — these quantities without a model is direct Monte Carlo estimation. This also builds the right intuition: $v_\pi(s)$ and $q_\pi(s,a)$ are just averages of empirical returns, and dynamic-programming methods later on will simply find faster ways to compute the same averages using the recursive identities above.

Step-by-step mechanism for Monte Carlo estimation of $v_\pi$ and $q_\pi$: 1. Fix the policy $\pi$ to be evaluated. It does not change during this process — we are only measuring it, not improving it. 2. Generate an episode: starting from some state, repeatedly sample an action from $\pi(\cdot \mid S_t)$, let the environment produce $R_{t+1}$ and $S_{t+1}$, and continue until a terminal state (or a fixed horizon). 3. For each time step $t$ visited in the episode, compute the realized return $G_t = \sum_{k \geq 0} \gamma^k R_{t+k+1}$ by summing forward from that point to the end of the episode. 4. Attribute that sampled return $G_t$ as one observation of $v_\pi(S_t)$, and also as one observation of $q_\pi(S_t, A_t)$ (since the true action taken at $t$ was $A_t$). 5. Maintain running averages, per state (for $v_\pi$) and per state-action pair (for $q_\pi$), across many episodes. 6. As the number of episodes grows, the law of large numbers guarantees these running averages converge to the true $v_\pi(s)$ and $q_\pi(s,a)$. ``` function MONTE_CARLO_EVALUATE(policy π, environment env, num_episodes N, discount γ):

# Running sums and counts for state-value and action-value estimates V_sum = dictionary(default 0.0) # state -> cumulative return V_count = dictionary(default 0) # state -> number of visits Q_sum = dictionary(default 0.0) # (state, action) -> cumulative return Q_count = dictionary(default 0) # (state, action) -> number of visits for episode in 1..N: states, actions, rewards = [], [], [] s = env.reset() while not env.is_terminal(s): a = sample_action(π, s) # a ~ π(· | s) s_next, r = env.step(s, a) states.append(s) actions.append(a) rewards.append(r) s = s_next T = length(rewards) G = 0.0

# Walk backward through the episode to build returns cheaply:

# G_t = R_{t+1} + γ G_{t+1}, computed from the end of the episode. for t in (T-1) down to 0: G = rewards[t] + γ * G # this G is now G_t s_t, a_t = states[t], actions[t] V_sum[s_t] += G V_count[s_t] += 1 Q_sum[(s_t, a_t)] += G Q_count[(s_t, a_t)] += 1

# Final estimates: sample averages of observed returns v_hat = { s: V_sum[s] / V_count[s] for s in V_sum } q_hat = { (s,a): Q_sum[(s,a)] / Q_count[(s,a)] for (s,a) in Q_sum } return v_hat, q_hat ``` Two implementation notes matter for correctness. First, computing $G_t$ by walking backward through the episode (as shown) costs $O(1)$ work per time step via the recursion $G_t = R_{t+1} + \gamma G_{t+1}$, rather than $O(T)$ work per time step from a naive forward sum — this is a standard trick, not a shortcut that changes the answer. Second, if a state is visited multiple times within one episode, one may choose first-visit Monte Carlo (only the first occurrence contributes) or every-visit Monte Carlo (every occurrence contributes); both converge to $v_\pi$ and $q_\pi$ under mild conditions, though their variance and bias properties in finite samples differ slightly. The diagram below shows how $v_\pi$ and $q_\pi$ interlock in a single decision step: the state-value at $s$ is a $\pi$-weighted blend over actions of the action-values, and each action-value is a probability-weighted blend over the environment's stochastic outcomes of "reward plus discounted next-state value."

Space complexity. Storing $v_\pi$ requires $O(|\mathcal{S}|)$ numbers, one per state. Storing $q_\pi$ requires $O(|\mathcal{S}| \cdot |\mathcal{A}|)$ numbers, one per state-action pair. This is the fundamental storage tradeoff: $q_\pi$ is a strictly larger table but carries strictly more decision-relevant information, since it separates out the consequence of each candidate action instead of blending them under the current policy.

Time complexity of Monte Carlo estimation. For one episode of length $T$, generating the trajectory costs $O(T)$ environment interactions. Computing all returns $G_t$ for $t = 0, \dots, T-1$ via the backward recursion costs $O(T)$ total (each $G_t$ is $O(1)$ given $G_{t+1}$), not $O(T^2)$ as a naive forward summation would cost. Updating running averages for $v_\pi$ and $q_\pi$ costs $O(1)$ per visited state or state-action pair. So one episode costs $O(T)$ overall, and $N$ episodes cost $O(N \cdot T_{\text{avg}})$, where $T_{\text{avg}}$ is the average episode length. This is efficient — linear in the total amount of simulated experience — but the statistical efficiency (how many episodes are needed for accurate estimates) is separate from this computational cost, and is governed by the variance of returns, discussed below.

Correctness of the Monte Carlo estimator. The estimator's correctness rests on the definition of $v_\pi(s)$ and $q_\pi(s,a)$ as expectations, combined with the law of large numbers. Fix a state $s$. Every episode that visits $s$ at some time $t$ contributes an independent (or, for every-visit, weakly dependent) sample of the random variable $G_t \mid S_t = s$, whose expectation is $v_\pi(s)$ by definition. As the number of such samples $n \to \infty$,

by the strong law of large numbers, provided the returns have finite variance (guaranteed when rewards are bounded and $\gamma < 1$, or when episodes terminate with probability 1 under $\gamma = 1$). The identical argument, replacing the conditioning event $S_t = s$ with the joint event $(S_t, A_t) = (s,a)$, establishes convergence of the running average to $q_\pi(s,a)$.

Correctness of the $v_\pi \leftrightarrow q_\pi$ identities. These are not estimated quantities but exact algebraic consequences of the definitions, provable by the law of total expectation. For the first identity:

where the middle step is exactly the tower property of conditional expectation, conditioning first on $A_t$ and then averaging over its distribution $\pi(\cdot \mid s)$. For the second identity, split the return as $G_t = R_{t+1} + \gamma G_{t+1}$, and condition on $(S_{t+1}, R_{t+1})$:

and the inner expectation is exactly $v_\pi(s')$ by definition, using the Markov property to note that the future beyond $S_{t+1}$ depends only on $S_{t+1}$, not on the earlier history. This step is the one place the Markov assumption is doing real work — without it, $\mathbb{E}_\pi[G_{t+1} \mid S_{t+1} = s']$ could differ depending on how the process arrived at $s'$.

Honest tradeoffs. Monte Carlo estimation is unbiased and model-free, but it has two costs. First, it requires episodes to terminate (or a very long finite horizon), so it converges slowly in environments with long or highly variable episode lengths — the variance of $G_t$ compounds over every step, since each reward $R_{t+k+1}$ is itself random. Second, it wastes information: an episode that visits a state only once contributes only one sample, ignoring the rich structure the Bellman identities exploit — namely that $v_\pi(s')$ for a nearby state can be reused to estimate $v_\pi(s)$ without waiting for whole episodes to finish. This inefficiency is precisely the gap that dynamic-programming and bootstrapping methods, built directly on the Bellman equations, are designed to close.

Consider a tiny two-state MDP: states $\{A, B\}$, with $B$ terminal (reward-then-done). From $A$, two actions are available: stay (loop back to $A$) and go (move to terminal $B$). Rewards: staying yields reward $2$ and looping back to $A$; going yields reward $5$ and terminates at $B$. Discount factor $\gamma = 0.5$. The policy $\pi$ chooses stay with probability $0.3$ and go with probability $0.7$ in state $A$.

Exact computation using the identities (ground truth). First compute $q_\pi(A, \text{go})$. Taking "go" yields reward $5$ and transitions to terminal state $B$, where $v_\pi(B) = 0$ since no further reward is possible:

Next compute $q_\pi(A, \text{stay})$. Taking "stay" yields reward $2$ and transitions back to $A$, so it depends on $v_\pi(A)$ itself:

Now use the other identity to write $v_\pi(A)$ in terms of both $q$-values:

This is a single linear equation in $v_\pi(A)$:

Substituting back gives $q_\pi(A,\text{stay}) = 2 + 0.5 \cdot 4.8235 = 4.4118$, and we already have $q_\pi(A,\text{go}) = 5$. Sanity check with the identity:

Monte Carlo estimate, for comparison. Simulate 4 short episodes starting at $A$ under $\pi$ (stay 0.3 / go 0.7), truncated once terminal $B$ is reached:

Averaging these four sampled returns for state $A$: $\hat v_\pi(A) = (5 + 4.5 + 5 + 4.25)/4 = 4.6875$. This is close to the exact value $4.8235$, and with only 4 episodes some estimation error is expected — the gap would shrink toward zero as more episodes are averaged, exactly as the law of large numbers predicts. Note episode 1 and 3 also contribute directly to the running average for $q_\pi(A,\text{go})$ (both sampled a return of $5$ starting with action "go"), while episodes 2 and 4 contribute to $q_\pi(A,\text{stay})$.

The state-value and action-value functions arose from the marriage of two independent lines of work: Richard Bellman's theory of dynamic programming for sequential decision problems under uncertainty, and the later formalization of trial-and-error learning as an approximation to that theory.

Every reinforcement learning algorithm that improves a policy needs some way to judge how good the current policy is, and $v_\pi$ and $q_\pi$ are exactly that judgment mechanism. Policy iteration and value iteration, the classical dynamic-programming algorithms for solving MDPs, alternate between evaluating $v_\pi$ (or $q_\pi$) and improving the policy based on those values — this is the direct ancestor of modern actor-critic methods. Q-learning and Deep Q-Networks (DQN), used in landmark results such as Atari-playing agents, learn an approximation of the optimal action-value function directly, using a neural network to represent $q(s,a)$ over enormous state spaces such as raw pixel frames. Actor-critic methods, including A3C, PPO, and modern robotics controllers, maintain an explicit "critic" network estimating $v_\pi(s)$ to reduce the variance of policy-gradient updates. In recommendation systems, $q_\pi(s,a)$-style estimates are used to score candidate recommendations against a user's simulated future engagement. In finance and operations research, dynamic-programming solutions to inventory and portfolio problems rest on value functions defined exactly as they are here, decades before "reinforcement learning" was a common term. Any system that must trade off immediate reward against long-term consequence — game-playing agents, autonomous vehicles, dialogue systems — ultimately relies on some computational stand-in for $v_\pi$ or $q_\pi$.

:::quiz[Why does the identity $q_\pi(s,a) = \sum_{s',r} p(s',r|s,a)[r + \gamma v_\pi(s')]$ rely on the Markov property?]

• It doesn't; the identity holds for any stochastic process
• Because it assumes $\mathbb{E}_\pi[G_{t+1} \mid S_{t+1}=s']$ depends only on $s'$, not on the path taken to reach it ✓
• Because Markov chains never terminate
• Because the discount factor must be state-dependent

Ask the tutor: How does substituting the $q_\pi$-to-$v_\pi$ identity into the $v_\pi$-to-$q_\pi$ identity produce the full Bellman equation for $v_\pi$?