Policies and Value Functions

Formally, given a Markov decision process with state space $\mathcal{S}$ and action space $\mathcal{A}$, a policy is a function

satisfying $\sum_{a \in \mathcal{A}(s)} \pi(a \mid s) = 1$ for every state $s$. This says: whenever the agent finds itself in state $s$, it samples its next action $A$ from the distribution $\pi(\cdot \mid s)$. A policy is stationary if this mapping does not change with time step $t$; unless otherwise stated, we always mean stationary policies, since for MDPs with an infinite or indefinite horizon, stationary policies suffice to achieve optimal behavior (a fact justified later via the Bellman optimality equations). Two important special cases deserve names. A policy is deterministic if for every state $s$ there is a single action $a = \pi(s)$ with $\pi(a \mid s) = 1$; we then abuse notation and write $\pi(s)$ directly as an action rather than a distribution. A policy is stochastic if it assigns positive probability to more than one action in at least one state — useful for exploration, for handling partial observability, and for games with adversaries where randomized behavior is provably necessary for optimality (as in rock-paper-scissors-like MDPs). A policy alone does not determine what happens; it interacts with the environment's transition function $p(s' \mid s, a)$ and reward function to generate a stochastic process. Starting from state $S_0$, we draw $A_0 \sim \pi(\cdot \mid S_0)$, the environment responds with reward $R_1$ and next state $S_1 \sim p(\cdot \mid S_0, A_0)$, then we draw $A_1 \sim \pi(\cdot \mid S_1)$, and so on. This produces a random trajectory

The return $G_t$ from time $t$ is the (typically discounted) sum of future rewards,

for discount factor $\gamma \in [0,1)$ (or a finite sum in episodic tasks with $\gamma = 1$). Because both the policy and the transition dynamics are stochastic, $G_t$ is a random variable even conditional on the starting state. The single most important derived quantity in reinforcement learning is the expectation of this return, which is exactly what a value function measures:

This equation is the bridge between "a rule for acting" (the policy) and "a number worth optimizing" (the value). Everything that follows — the Bellman equations that make this expectation recursively computable, and the split into state-value versus action-value functions — is built on exactly this definition.

Mechanically, evaluating what a policy is worth means simulating (or analytically solving for) the expected return it produces. There are two complementary ways to think about "how it works": generating trajectories under a fixed policy, and computing the expectation of return in closed form for small, fully known MDPs.

Trajectory generation. Given an explicit policy and a known MDP, we can sample rollouts directly. This is the operational meaning of "following a policy," and it is exactly what a simulator or robot does at run time. ``` function GENERATE_EPISODE(policy π, MDP M, start_state s0, max_steps T): trajectory = [] s = s0 for t = 0 to T-1: sample a ~ π(· | s) # stochastic action choice sample (s', r) ~ M.step(s, a) # environment dynamics p(s', r | s, a) trajectory.append((s, a, r)) s = s' if M.is_terminal(s): break return trajectory function MONTE_CARLO_RETURN(trajectory, γ): G = 0 for (s, a, r) in reversed(trajectory): G = r + γ * G # accumulate discounted return backward return G ``` Running many episodes from a fixed start state and averaging the resulting $G$ values gives a Monte Carlo estimate of $v_\pi(s_0)$ — a direct, simulation-based reading of the definition $v_\pi(s) = \mathbb{E}_\pi[G_t \mid S_t = s]$.

Exact evaluation for small, known MDPs. When the transition and reward functions are fully known and the state space is small, we don't need sampling at all. The definition of $v_\pi$ satisfies a self-consistency condition — the seed of the Bellman equation, though we state it here only as a direct consequence of expectations, not yet as the general recursive machinery: ``` function EVALUATE_POLICY_EXACTLY(policy π, MDP M, γ, tol):

# v is a table indexed by state, initialized arbitrarily (e.g., all zeros) v = { s: 0.0 for s in M.states } repeat: Δ = 0 for s in M.states: if M.is_terminal(s): continue old_v = v[s] total = 0 for a in M.actions(s): action_prob = π(a | s) expected_next = 0 for (s_next, r, p) in M.transitions(s, a): # p = p(s',r|s,a) expected_next += p (r + γ v[s_next]) total += action_prob * expected_next v[s] = total Δ = max(Δ, abs(old_v - v[s])) if Δ < tol: break return v ``` This is iterative policy evaluation: it repeatedly applies the expectation implied by $\pi$ and the MDP dynamics until the value estimates stop changing meaningfully. It is not yet the full Bellman equation (that formalism and its contraction-mapping proof of convergence belong to a dedicated treatment), but it is a direct computational unpacking of $v_\pi(s) = \mathbb{E}_\pi[G_t \mid S_t = s]$: each state's value is the probability-weighted average, over the policy's action choices and the environment's transition randomness, of immediate reward plus discounted value of what comes next.

Space. Storing a general stochastic policy over a finite MDP requires $O(|\mathcal{S}| \cdot |\mathcal{A}|)$ numbers — one probability per state-action pair. A deterministic policy needs only $O(|\mathcal{S}|)$ since one action index per state suffices. Storing the value table used in evaluation requires $O(|\mathcal{S}|)$ real numbers.

Time for Monte Carlo estimation. Each simulated episode of length $T$ costs $O(T)$ to generate and $O(T)$ to compute its return, so $N$ episodes cost $O(NT)$. The estimator of $v_\pi(s)$ from $N$ independent episodic returns starting at $s$ has variance shrinking as $O(1/N)$ by the standard concentration of sample means — this is a direct consequence of $\mathrm{Var}[\bar G] = \mathrm{Var}[G]/N$ for i.i.d. samples, so Monte Carlo evaluation is unbiased but requires many episodes for tight estimates, especially when returns have high variance (long horizons, large $\gamma$, or high-variance rewards all increase the number of episodes needed for a fixed confidence interval).

Time for exact iterative evaluation. One full sweep over all states costs $O(|\mathcal{S}| \cdot |\mathcal{A}| \cdot B)$ where $B$ bounds the branching factor (number of possible next states per state-action pair), since for each state we loop over actions and, for each action, over possible outcomes. The number of sweeps required to reach a fixed tolerance is where the deeper correctness argument lives.

Why iterative evaluation converges — the core argument. Define the update in the evaluation pseudocode as an operator $T^\pi$ acting on any candidate value table $v$:

Two facts, both provable directly from this definition, guarantee correctness: 1. $v_\pi$ is the unique fixed point of $T^\pi$. Substituting the true expected-return function into the right-hand side and using linearity of expectation over the one-step decomposition of $G_t = R_{t+1} + \gamma G_{t+1}$ shows $T^\pi v_\pi = v_\pi$ exactly — this is the content of what becomes the Bellman equation for $v_\pi$, and uniqueness follows because $T^\pi$ is a contraction (next point). 2. $T^\pi$ is a $\gamma$-contraction in the max-norm. For any two value tables $u, v$,

because the difference $(T^\pi u)(s) - (T^\pi v)(s)$ is a $\pi$- and $p$-weighted average of terms $\gamma\big(u(s') - v(s')\big)$, each bounded in magnitude by $\gamma \|u-v\|_\infty$, and a weighted average of numbers cannot exceed the largest one in magnitude. Since $\gamma < 1$, the Banach fixed-point theorem guarantees that repeated application of $T^\pi$ from any starting table converges to the unique fixed point $v_\pi$, and the error shrinks geometrically: after $k$ sweeps, $\|v^{(k)} - v_\pi\|_\infty \le \gamma^k \|v^{(0)} - v_\pi\|_\infty$. This geometric shrinkage is what justifies stopping the loop once successive updates differ by less than a small tolerance — the true error is bounded by a known multiple of the observed change, so the number of sweeps needed for a target accuracy $\varepsilon$ is $O\!\left(\log(1/\varepsilon) / \log(1/\gamma)\right)$, giving a total time complexity of

Tradeoffs. Exact evaluation requires full knowledge of $p(s',r\mid s,a)$ and scales poorly as $|\mathcal{S}|$ grows (the "curse of dimensionality"), while Monte Carlo evaluation needs no model of the environment at all but pays in variance and sample count. Both approaches, however, are computing the same mathematically well-defined object, $v_\pi(s) = \mathbb{E}_\pi[G_t \mid S_t = s]$ — the distinction is purely about how the expectation is realized, not what it means.

Consider a tiny two-state MDP: a "Study" state $S$ and a "Rest" state $R$, both non-terminal, with $\gamma = 0.9$. From each state the agent can choose action stay or switch. Dynamics (deterministic for simplicity):

Consider the stochastic policy $\pi$: in state $S$, choose stay with probability 0.8 and switch with probability 0.2; in state $R$, choose stay with probability 0.5 and switch with probability 0.5. We run `EVALUATE_POLICY_EXACTLY` by hand. Initialize $v(S) = v(R) = 0$.

Sweep 1:

Sweep 2: using $v(S)=1.6,\ v(R)=0.0$ from sweep 1,

Sweep 3: using $v(S) = 2.752,\ v(R) = 0.72$,

The table below shows the trend over sweeps, converging geometrically (each error term shrinking by roughly the contraction factor $\gamma = 0.9$ per step, consistent with the correctness argument above):

Continuing the recursion (or solving the two linear fixed-point equations directly, $v(S) = 0.8(2+0.9v(S)) + 0.2(0.9 v(R))$ and $v(R) = 0.5(1+0.9v(R)) + 0.5(-1+0.9v(S))$) gives the exact fixed point around $v_\pi(S) \approx 6.30$, $v_\pi(R) \approx 5.07$. This confirms concretely: $v_\pi(S)$ is strictly the expectation of discounted return starting in $S$ and always sampling actions from $\pi$ — no single trajectory realizes this exact number, but it is what a Monte Carlo average over many trajectories would converge to as well.

Every reinforcement learning algorithm — from tabular Q-learning to deep policy-gradient methods used in large-scale robotics and game-playing systems — is ultimately manipulating one of two objects: a policy or a value function derived from one. Recommendation systems at scale formalize "which content to show" as a policy over user states, and evaluate candidate policies via estimated expected long-term engagement, directly mirroring $v_\pi(s)$. Autonomous driving stacks encode driving behavior as a policy over perceptual states and must certify that its expected return (safety-weighted) exceeds some threshold before deployment. Industrial control systems, from HVAC optimization to data-center cooling, are tuned by comparing policies through exactly the expected-return criterion introduced here. The distinction between policies (how to act) and value functions (how good acting that way is) is also the organizing principle behind actor-critic architectures in deep reinforcement learning, where one neural network represents $\pi$ and another approximates $v_\pi$ or a related quantity.

Ask the tutor: How does policy improvement use the value function v_π to construct a strictly better policy π′?