Dynamic Choice and Forward Simulation

Conceptual map

IV-08.01States, transitions, and rewards
IV-08.02Bellman equations
IV-08.03Policies and deviations
IV-08.04State compression
IV-08.05A labor-market example

1. Dynamic choice couples rewards and transitions

A Bellman solution is tied to a declared state. A compressed state is structural only when rewards and transition probabilities are constant on its cells in the required sense.

Let finite state space $\mathcal{X}$ and feasible actions $\mathcal{A}(x)$ be nonempty. With bounded reward $$r(x,a)$$ , row-stochastic transition $P(x^{\prime}|x,a)$ , and discount $\beta \in[0,1)$ , the Bellman operator is

\[(TV)(x)=\operatorname{max}_{a\in \mathcal{A}(x)}\{r(x,a)+\beta \sum _{x^{\prime}}P(x^{\prime}|x,a)V(x^{\prime})\}.\](1)

Proposition 1 · Discounted value uniqueness

$$T$$ is a contraction in the sup norm with modulus $\beta$ . It has a unique fixed point, and value iteration converges to it from every bounded initial vector.

Proof. For every action, the difference of expected continuation values is bounded by $\beta \lVert V-W\rVert_{\infty}$ . Taking maxima preserves that bound. Apply the contraction mapping theorem. ∎

2. A partition closes only under reward and transition invariance

Let $q:\mathcal{X}\to \mathcal{C}$ partition microstates. For each action available throughout a cell, exact aggregation requires equal rewards for states in that cell and equal transition probability into every destination cell:

\[\sum _{z:q(z)=c^{\prime}}P(z|x,a)=\sum _{z:q(z)=c^{\prime}}P(z|x^{\prime},a)\](2)

for every $x,x^{\prime}$ in the same source cell and every destination cell $c^{\prime}$ . Then the Bellman equation and forward distribution update are well defined on cells.

3. Equal counts can have different next counts

Microstates one and two belong to cell $$G$$ ; state three belongs to $$B$$ . From state one, transition probability to $$B$$ is 0.1; from state two it is 0.5. Two populations concentrated respectively on states one and two both report aggregate counts ( $$G,B$$ )=(1,0), yet their next-period expected $$B$$ counts are 0.1 and 0.5.

The aggregate count predicts imperfectly because within- $$G$$ composition matters. Adding the share in microstate two repairs this example.

4. Discount and invariant-distribution boundaries

Failure case · Predictive count treated as a closed state

A count can forecast outcomes while violating (2). Forward simulation from an estimated count-only transition then averages over an implicit composition law that can change under policy.

At $\beta=1$ the contraction proof ends; average-reward or undiscounted models need recurrence and normalization conditions. Reducible or periodic policy transitions can have multiple invariant distributions or nonconvergent distribution paths. Empty action sets leave (1) undefined, and policy-dependent feasibility must be carried into every cell.

5. Implementation, exercises, and sources

Enumerate state-action pairs, verify transition rows sum to one, solve the Bellman fixed point, and report the sup-norm residual. For each proposed partition, compare rewards and destination-cell transition sums across all states in a cell before simulating compressed dynamics.

Download the volume verification script →

Exercises

Construct the full three-state transition matrix for Section 3 and reproduce both next counts.
Modify the first two rows to satisfy (2) and write the two-cell transition.
Give a periodic two-state policy transition with no convergent distribution path from a point mass.

Partial solutions

1. Use rows (0.9,0,0.1), (0,0.5,0.5), and any stochastic row for state three. 2. Give the first two rows the same total probability of entering $$G$$ and $$B$$ . 3. The transition $\begin{bmatrix}0 & 1 \\ 1 & 0\end{bmatrix}$ alternates point masses.

Martin L. Puterman, Markov Decision Processes, chapters on discounted finite models.Bellman contractions and stationary policies.
John G. Kemeny and J. Laurie Snell, Finite Markov Chains, chapters on lumpability.Exact aggregation of Markov chains.
George Stachurski, Economic Dynamics.Dynamic programming and distribution evolution.

6. Audit checkpoint

State microstates, feasible actions, rewards, discount, transition orientation, initial distribution, horizon, policy tie rule, Bellman residual, proposed partition, within-cell reward and transition tests, recurrence, and invariant-distribution claim.

7. Scope boundary

The chapter covers finite discounted Markov decision processes and exact partition closure. Dynamic games and continuous-state approximation require further theory.