Simplifying assumptions and notation

It is standard to impose the following simplifying assumptions and notation of the dynamic decision problem:

1. Flow utility is additively separable and linear in parameters

The flow utility can be written as an additive sum, consisting of deterministic and stochastic elements. The deterministic component can be written as a linear function of the structural parameters.

${\displaystyle {\begin{alignedat}{5}U_{nit}\left(x_{nt},\varepsilon _{nit}\right)&&\;=\;&&u_{nit}&&\;+\;&&\varepsilon _{nit}\\&&\;=\;&&X_{nt}\alpha _{i}&&\;+\;&&\varepsilon _{nit}\end{alignedat}}}$

2. The optimization problem can be written as a Bellman equation

Define by ${\displaystyle V_{nt}(x_{nt})}$ the ex ante value function for individual ${\displaystyle n}$ in period ${\displaystyle t}$ just before ${\displaystyle \varepsilon _{nt}}$ is revealed:

${\displaystyle V_{nt}(x_{nt})=\mathbb {E} \max _{i}\left\{u_{nit}(x_{nt})+\varepsilon _{nit}+\beta \int _{x_{t+1}}V_{nt+1}(x_{nt+1})\,dF\left(x_{t+1}\mid x_{t}\right)\right\}}$

where the expectation operator ${\displaystyle \mathbb {E} }$ is over the ${\displaystyle \varepsilon }$'s, and where ${\displaystyle dF\left(x_{t+1}\mid x_{t}\right)}$ represents the probability distribution over ${\displaystyle x_{t+1}}$ conditional on ${\displaystyle x_{t}}$. The expectation over state transitions is accomplished by taking the integral over this probability distribution.

It is possible to decompose ${\displaystyle V_{nt}(x_{nt})}$ into deterministic and stochastic components:

${\displaystyle V_{nt}(x_{nt})=\mathbb {E} \max _{i}\left\{v_{nit}(x_{nt})+\varepsilon _{nit}\right\}}$

where ${\displaystyle v_{nit}}$ is the value to choosing alternative ${\displaystyle i}$ at time ${\displaystyle t}$ and is written as

${\displaystyle v_{nit}(x_{nt})=u_{nit}\left(x_{nt}\right)+\beta \int _{x_{t+1}}\mathbb {E} \max _{j}\left\{v_{njt+1}(x_{nt+1})+\varepsilon _{njt+1}\right\}\,dF(x_{t+1}\mid x_{t})}$

where now the expectation ${\displaystyle \mathbb {E} }$ is taken over the ${\displaystyle \varepsilon _{njt+1}}$.

3. The optimization problem follows a Markov decision process

The states ${\displaystyle x_{t}}$ follow a Markov chain. That is, attainment of state ${\displaystyle x_{t}}$ depends only on the state ${\displaystyle x_{t-1}}$ and not ${\displaystyle x_{t-2}}$ or any prior state.

Full-solution methods

The foremost example of a full-solution method is the nested fixed point (NFXP) algorithm developed by John Rust in 1987.^[2] The NFXP algorithm is described in great detail in its documentation manual.^[3]

A recent work by Che-Lin Su and Kenneth Judd in 2012^[4] implements another approach (dismissed as intractable by Rust in 1987), which uses constrained optimization of the likelihood function, a special case of mathematical programming with equilibrium constraints (MPEC). Specifically, the likelihood function is maximized subject to the constraints imposed by the model, and expressed in terms of the additional variables that describe the model's structure. This approach requires powerful optimization software such as Artelys Knitro because of the high dimensionality of the optimization problem. Once it is solved, both the structural parameters that maximize the likelihood, and the solution of the model are found.

In the later article^[5] Rust and coauthors show that the speed advantage of MPEC compared to NFXP is not significant. Yet, because the computations required by MPEC do not rely on the structure of the model, its implementation is much less labor intensive.

Despite numerous contenders, the NFXP maximum likelihood estimator remains the leading estimation method for Markov decision models.^[5]

Non-solution methods

An alternative to full-solution methods is non-solution methods. In this case, the researcher can estimate the structural parameters without having to fully solve the backwards recursion problem for each parameter guess. Non-solution methods are typically faster while requiring more assumptions, but the additional assumptions are in many cases realistic.

The leading non-solution method is conditional choice probabilities, developed by V. Joseph Hotz and Robert A. Miller.^[6]

Bus engine replacement model

The bus engine replacement model developed in the seminal paper Rust (1987) is one of the first dynamic stochastic models of discrete choice estimated using real data, and continues to serve as classical example of the problems of this type.^[4]

The model is a simple regenerative optimal stopping stochastic dynamic problem faced by the decision maker, Harold Zurcher, superintendent of maintenance at the Madison Metropolitan Bus Company in Madison, Wisconsin. For every bus in operation in each time period Harold Zurcher has to decide whether to replace the engine and bear the associated replacement cost, or to continue operating the bus at an ever raising cost of operation, which includes insurance and the cost of lost ridership in the case of a breakdown.

Let ${\displaystyle x_{t}}$ denote the odometer reading (mileage) at period ${\displaystyle t}$, ${\displaystyle c(x_{t},\theta )}$ cost of operating the bus which depends on the vector of parameters ${\displaystyle \theta }$, ${\displaystyle RC}$ cost of replacing the engine, and ${\displaystyle \beta }$ the discount factor. Then the per-period utility is given by

${\displaystyle U(x_{t},\xi _{t},d,\theta )={\begin{cases}-c(x_{t},\theta )+\xi _{t,{\text{keep}}},&\\-RC-c(0,\theta )+\xi _{t,{\text{replace}}},&\end{cases}}=u(x_{t},d,\theta )+{\begin{cases}\xi _{t,{\text{keep}}},&{\textrm {if}}\;\;d={\text{keep}},\\\xi _{t,{\text{replace}}},&{\textrm {if}}\;\;d={\text{replace}},\end{cases}}}$

where ${\displaystyle d}$ denotes the decision (keep or replace) and ${\displaystyle \xi _{t,{\text{keep}}}}$ and ${\displaystyle \xi _{t,{\text{replace}}}}$ represent the component of the utility observed by Harold Zurcher, but not John Rust. It is assumed that ${\displaystyle \xi _{t,{\text{keep}}}}$ and ${\displaystyle \xi _{t,{\text{replace}}}}$ are independent and identically distributed with the Type I extreme value distribution, and that ${\displaystyle \xi _{t,\bullet }}$ are independent of ${\displaystyle \xi _{t-1,\bullet }}$ conditional on ${\displaystyle x_{t}}$.

Then the optimal decisions satisfy the Bellman equation

${\displaystyle V(x,\xi ,\theta )=\max _{d={\text{keep}},{\text{replace}}}\left\{u(x,d,\theta )+\xi _{d}+\iint V(x',\xi ',\theta )q(d\xi '\mid x',\theta )p(dx'\mid x,d,\theta )\right\}}$

where ${\displaystyle p(dx'\mid x,d,\theta )}$ and ${\displaystyle q(d\xi '\mid x',\theta )}$ are respectively transition densities for the observed and unobserved states variables. Time indices in the Bellman equation are dropped because the model is formulated in the infinite horizon settings, the unknown optimal policy is stationary, i.e. independent of time.

Given the distributional assumption on ${\displaystyle q(d\xi '\mid x',\theta )}$, the probability of particular choice ${\displaystyle d}$ is given by

${\displaystyle P(d\mid x,\theta )={\frac {\exp\{u(x,d,\theta )+\beta EV(x,d,\theta )\}}{\sum _{d'\in D(x)}\exp\{u(x,d',\theta )+\beta EV(x,d',\theta )\}}}}$

where ${\displaystyle EV(x,d,\theta )}$ is a unique solution to the functional equation

${\displaystyle EV(x,d,\theta )=\int \left[\log \left(\sum _{d={\text{keep}},{\text{replace}}}\exp\{u(x,d',\theta )+\beta EV(x',d',\theta )\}\right)\right]p(x'\mid x,d,\theta ).}$

It can be shown that the latter functional equation defines a contraction mapping if the state space ${\displaystyle x_{t}}$ is bounded, so there will be a unique solution ${\displaystyle EV(x,d,\theta )}$ for any ${\displaystyle \theta }$, and further the implicit function theorem holds, so ${\displaystyle EV(x,d,\theta )}$ is also a smooth function of ${\displaystyle \theta }$ for each ${\displaystyle (x,d)}$.