Econometrics bridge: Markov chains, dynamic choice, stochastic control, and policy-dependent sampling
Estimated time: 120 min
Lab: Open browser lab
Code: Python - R
From Markov chains and dynamic economic choice to MDPs
An econometrician may already know Markov processes, dynamic choice, discounted utility, and perhaps Bellman equations from economics, finance, or operations research. A Markov chain models changes of state without an explicit decision-maker. A Markov decision process (MDP) additionally models the effect of actions on the next state and the reward received. Think of sequential inventory control, investment timing, or deciding when to service a machine.
For a Markov chain we might specify \(P(s'\mid s)\). In an MDP, the transition law is conditional on an action:
\[ P(s'\mid s,a). \]The distinction is not that every MDP must be learned: a fully known MDP can be solved by planning. Reinforcement learning (RL) becomes relevant when values, policies, or aspects of the environment must be learned from sampled interaction. The course’s next module builds on this separation when introducing policy optimization and value baselines.
States, actions, transitions, rewards, and policies
An MDP specifies states \(s\in\mathcal S\), available actions \(a\in\mathcal A(s)\), a transition probability \(P(s'\mid s,a)\), an immediate transition reward \(r(s,a,s')\), and a discount factor \(0\le\gamma<1\). A policy \(\pi(a\mid s)\) chooses an action distribution given the state.
For a discounted continuing problem, the value of a policy is
\[ V^\pi(s)=\mathbb E_\pi\!\left[\sum_{t=0}^{\infty}\gamma^tR_{t+1}\mid S_0=s\right]. \]For the finite episodic example below, the sum stops on termination. Crucially, the reward earned when entering a terminal state appears on that transition; the terminal state has continuation value zero. This timing convention will be shared by the prose and every lab implementation.
A policy induces its own Markov transition matrix:
\[ P^\pi(s'\mid s)=\sum_a\pi(a\mid s)P(s'\mid s,a). \]So two policies operating in the same environment can produce different state visitation distributions and thus different observed datasets.
Bellman equations: solve a known decision problem
For a specified policy, the Bellman expectation equation is
\[ V^\pi(s)=\sum_a\pi(a\mid s)\sum_{s'}P(s'\mid s,a) \big[r(s,a,s')+\gamma V^\pi(s')\big]. \]Optimality replaces averaging over the specified policy with maximization:
\[ V^*(s)=\max_a\sum_{s'}P(s'\mid s,a) \big[r(s,a,s')+\gamma V^*(s')\big]. \]The associated optimal action value is
\[ Q^*(s,a)=\sum_{s'}P(s'\mid s,a) \big[r(s,a,s')+\gamma V^*(s')\big]. \]Policy evaluation asks how good a given policy is. Policy improvement asks whether another action produces higher expected value. Value iteration repeatedly applies the Bellman optimality backup when the transition and reward model are available. The Bellman residual, the difference between a current value estimate and its backup, checks approximate convergence; a fixed iteration count alone does not.
A small line world with a genuine discounting choice
The lab has six states, numbered 0 through 5. State 2 is the start. State 0 pays a terminal bonus of 0.4 and state 5 pays a terminal bonus of 1.0. From state 2, reaching the left terminal takes two steps; reaching the right terminal takes three. Each move pays a step cost \(c\le0\), and entering a terminal also pays its bonus. There are no actions after termination.
The return along the direct left and right paths is therefore
\[ G_L=c+\gamma(c+0.4), \qquad G_R=c+\gamma\big[c+\gamma(c+1)\big]. \]At \(c=-0.02\), the paths have equal return when \(\gamma(0.98)=0.4\), or \(\gamma\approx0.4082\). Lower discount factors favor the closer reward; higher discount factors favor the farther, larger reward. Unlike a symmetric environment with equal distances, this example actually produces the promised center-state policy switch. The terminal bonuses are transition rewards, not fixed terminal-state values.
Reinforcement learning: estimate values from sampled interactions
Suppose the environment can be interacted with but its reward and transition table are not provided to the learner. A model-free Q-learner updates an action value using only an observed transition \((s,a,r,s')\):
\[ Q(s,a)\leftarrow Q(s,a)+\alpha\Big[r+\gamma\max_{a'}Q(s',a')-Q(s,a)\Big]. \]At termination, \(\max_{a'}Q(s',a')\) is defined as zero. The learning rate \(\alpha\) controls the size of the update. Value iteration performs backups using the known environment; Q-learning approximates the relevant values from experienced transitions. With suitable conditions, tabular Q-learning can approach optimal action values; a short toy run is not a general convergence guarantee.
A typical exploratory behavior policy is \(\varepsilon\)-greedy: with probability \(\varepsilon\), choose a random action; otherwise choose the currently highest-valued action. The lab deliberately initializes all Q-values to zero and breaks ties toward Left. With \(\varepsilon=0\), optimistic zero initialization can cause a small number of initial trials, but this particular learner rarely revisits the better route and fails to establish adequate support. Exploration provides a way to collect missing evidence, but it also changes the rewards experienced during training.
Exploration, endogenous experience, and off-policy evaluation
Under behavior policy \(\mu\), recorded trajectories are distributed according to that policy and the environment. The data are policy-dependent:
\[ (S_t,A_t,R_{t+1},S_{t+1})\sim d^\mu. \]An action never tried in a state is not identified from the observed transitions in that state without further modeling assumptions. The absence of support is different from a low estimated reward. This is analogous to familiar selection and overlap questions in econometrics, complicated by the fact that actions influence future states and opportunities to observe rewards.
Off-policy evaluation asks about a target policy while using data collected under another behavior policy. Valid conclusions depend on support, observed state information, assumptions, and estimation method—not merely on a high training return. Exploration does not automatically solve confounding or partial observability.
Partial observability and reward specification
The Markov property concerns the underlying state, which may not be fully observed. A partially observable MDP uses a belief state such as
\[ b_t(s)=P(S_t=s\mid O_{1:t},A_{1:t-1}), \]updating beliefs as observations and actions arrive. This connects to latent-state filtering in Module 01 and recurrent representations in Module 08.
The reward is also a specified objective, not a guarantee of business or social value. An agent rewarded only for closed support tickets might close them prematurely. If the reward omits resolution quality, optimization may succeed against the formula while failing the operational goal.
Value-based learning estimates \(Q\) or \(V\); policy-based approaches parameterize and optimize \(\pi_\theta\) directly. Deep RL may use neural networks to approximate either. Module 13 will discuss policy gradients and language-model post-training without collapsing them into tabular Q-learning.
Econometrics-to-AI translation
| Module 0 question | Answer in this module |
|---|---|
| What is the familiar statistical object? | Markov chains, dynamic choice, discounted utility, stochastic control, and sampling/selection problems. |
| What became learnable? | Environment models, state values, action values, and policies; the present Q-learning lab learns action values. |
| What objective is optimized? | Expected discounted cumulative reward, not a one-step predictive likelihood. |
| What generates the evidence? | Action-conditioned transitions and trajectories gathered by a behavior policy. |
| Where does the analogy break? | The policy changes the observed state-action distribution; lack of support prevents simple counterfactual comparison. |
Interactive browser lab
Work through three experiments in the offline browser lab:
- Bellman planning. Change the discount factor and step cost; inspect the center-state policy switch, per-state action values, optimal path returns, and Bellman residual.
- Q-learning. Change the exploration rate and number of episodes; inspect updates, learned action values, and a learned-versus-planned policy comparison.
- Policy-dependent data. Compare a deterministic greedy learner against an exploring learner; inspect state-action visitation counts and actions never tried.
The planning solver is the reference calculation. The Q-learning simulation receives only sampled transition outcomes for its updates. Its reproducible random draws and fixed tie-breaking convention make the support issue visible, not universally representative of RL training.
Python and R lab
Run the same deterministic line-world specification and calculations in Python and base R. Check the reward-on-entry timing, verify the Bellman residual, compare direct-path returns, and run Q-learning with identical seeded pseudorandom sampling. Compare the training visitation table and learned start-state policy to the planning benchmark. The scripts include assertions for the mathematical invariants; identical output relies on the explicitly shared toy pseudorandom generator.
Practice:
- Derive the two direct-path returns from state 2, including the terminal reward on the final transition. Solve for the discount factor at which they tie when \(c=-0.02\).
- Explain why the Bellman planning result is not evidence that an agent learned from experience.
- For a sampled transition, write the Q-learning update and explain why the bootstrap term vanishes on termination.
- Which state-action pairs were never visited by the greedy learner, and which were visited only once? What can its data alone establish about those actions?
- Show how a stationary policy induces a Markov chain. Why can changing the policy change the distribution of future observations?
- Explain why higher exploratory coverage need not imply higher reward collected during training, and why training reward is not automatically a valid off-policy evaluation.
- Give an example of a reward function whose optimization could harm the underlying business objective.
Learner output
Produce a short comparison containing (i) the known-MDP Bellman benchmark and policy switch, (ii) a sampled Q-learning estimate and its visitation counts, and (iii) a discussion of what conclusions are and are not justified by the resulting policy-dependent data.
Sources and Further Reading
Core references
- Russell, S. J., and Norvig, P. Artificial Intelligence: A Modern Approach, 4th ed. Sections on sequential decisions, MDPs, and reinforcement learning.
- Sutton, R. S., and Barto, A. G. Reinforcement Learning: An Introduction, 2nd ed. Chapters on finite MDPs, dynamic programming, temporal-difference learning, and exploration. Free author-hosted book: https://incompleteideas.net/book/the-book-2nd.html
Optional bridges
- Puterman, M. L. Markov Decision Processes: Discrete Stochastic Dynamic Programming (1994). For the control and optimization connection.
- Watkins, C. J. C. H., and Dayan, P. “Q-learning” (1992). For the classical model-free action-value update.