Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
100,640 characters · 27 sections · 59 citation commands
-3cm Dynamic Discrete Choice Model and Finite Dependence CCP Estimator
\newgeometry{top=1.4in, bottom=1.4in, left=1.25in, right=1.25in}
Many decisions are made in a forward-looking way. For example, a firm may make an entry decision in a market concerning all future rewards and entry costs. When a household makes consumption or savings decisions, all future consumptions are considered. To model the forward-looking nature of decision-making, economists often use dynamic discrete choice models (DDC) in many areas of economic research. \footnote{ For example, in industrial organizations, Berry2006, Aguirregabiria2012, Sweeting2013, CollardWexler2013, Ellickson2015, Yakovlev2016; in health economics, Gowrisankaran1997, Gowrisankaran2011, Gaynor2012, Beauchamp2015; in the marketing,Dube2005, Doganoglu2006, Doraszelski2007; and in labor economics, researchers use dynamic discrete choice to model the forward-looking nature of employment choice, school choice, and mammography choices Todd2006, Keane2011, Fang2015.}
The paper by Rust1987, Rust1994 pioneered the estimation of dynamic discrete choice (DDC) models by identifying optimal decision rules and modeling future events' expectations. However, standard maximum likelihood estimation (MLE) for infinite-horizon discrete games can be computationally expensive due to the need for solving fixed-point problems in large state spaces. To address this issue, Hotz1993 proposed a method that represents the value function as a product of inverse CCP-weighted transition matrices and expected CCP-weighted payoffs. aguirregabiria2007sequential proposed a recursive algorithm that implements the Hotz-Miller estimators in each iteration.
Economists have utilized the finite dependence property to tackle the curse of dimensionality, where the costs of inversion of the matrix or solving value functions recursively through forward simulation grow significantly with the size of the state space. The finite dependence property allows continuation value differences between decisions to be expressed as a summation of the payoffs of finite periods. arcidiacono2011conditional discusses finite dependence and proposes a class of estimators based on it, demonstrating their computational benefits. These estimators are time-efficient when estimating recursive models. \footnote{finite dependence estimators provide substantial efficiency gains, especially in models incorporating unobservable heterogeneity and the EM algorithm. These estimators are time-efficient for recursive estimation. arcidiacono2011conditional proposes an estimator combining the EM algorithm and the infinite dependence to address unobservable heterogeneity in dynamic discrete choice problems. Despite the complexity and increased computational burden of finite mixture models, these estimators help to make the problem tractable.} Empirical researchers have used dynamic games to model and analyze models with infinite dependence, including oligopolistic competition estimation_jeziorski_2014, unobserved_igami_2016, maican2018entry, salz2020estimating, dynamic pricing decisions ellickson2012repositioning, salesforce compensation dynamics bonuses_chung_2014, misra2011structural, migration bishop2012dynamic, coate2013parental, ma2019learning, housing market outcomes economics_kuminoff_2013, dynamic_murphy_2018, school matching outcomes cupids_galichon_2015, preschool education intergenerational_heckman_2016, female labor supply Altuug1998, gayle2012, gayle2015accounts, mammography choice Fang2015, and kidney donations agarwal2021equilibrium.
The class of estimators is not always applicable to models that do not exhibit finite dependence. arcidiacono2011conditional discuss the sufficient condition for a model to display the finite dependence, which arises when there is a terminal or absorbing state. Upon reaching this state, previous actions become irrelevant, allowing future payoffs to be represented as the sum of finite-period payoffs. However, determining whether certain models possess the finite dependence property is not always straightforward. For example, when considering a firm making entry and exit decisions in a market, the finite dependence property presumes that the firm's past entry history in a specific market has no impact on its subsequent entry decision. This assumption may not be valid in all cases.
In this paper, we demonstrate that the dynamic discrete choice problem can be reformulated as an equivalent probability mapping problem under standard identification assumptions magnac2002identifying, Aguirregabiria2002. This alternative formulation has agents selecting a probability mapping which links the distribution of state variables to choice probabilities.
This paper presents a two-fold contribution. Firstly, we make a conceptual contribution by reformulating decisions and states within the probability space, allowing us to derive the Euler equation that characterizes optimal decision rules using first-order necessary conditions. If the model exhibits 1-period finite dependence, this equation captures the trade-off between two consecutive periods. We demonstrate that the expected value of future utilities resulting from optimal decision making can always be expressed as a function of flow payoffs and conditional choice probabilities (CCPs) for any sequence of future choices, regardless of the optimality of the decisions. We show that in a discrete choice problem, the CCPs are equivalent to the optimal probability mapping in the probability problem, making the two problems equivalent.
Building on this reformulation, our second contribution is the introduction of a class of estimators that can be used for models with and without the finite dependence property. These estimators maintain the same time efficiency as the finite dependence estimator proposed by arcidiacono2011conditional. If a weight vector exists that leads to a zero norm for the weighted forward transition matrix, the model exhibits the finite dependence property. When the norm of the weighted-forward-transition matrix is close to zero, the model can be regarded as having an almost finite dependence. We propose a systematic approach to identify such weight vectors and present computational evidence that the norm of the weighted forward transition matrix approaches zero when applying the method to a $(\rho+1)$ period forward. With the estimated weight, we introduce a class of estimators similar to the finite dependence estimator described by arcidiacono2011conditional. We demonstrate that this class of estimators offers a time advantage compared to the Hotz-Miller estimator and maintains consistency for models with or without the finite dependence property.
This paper discusses the estimation of single-agent dynamic discrete choice problems. Standard estimation methods involve calculating the value function using backward recursion or fixed point algorithmsRust1987,Rust1994, which require repeated model solutions for each parameter trial value. CCP estimators, proposed by Hotz1993, map value functions to probabilities of decisions, making the two-step estimator computationally efficient and logit-like. aguirregabiria2007sequential extended this by proposing a recursive algorithm based on the two-step estimator, addressing finite-sample bias.
However, the computational burden of these models increases significantly with state-space size. The literature on finite dependence expands the range of models for which CCP estimation can be applied, benefiting from computational cost savings by eliminating matrix inversion or simulation. This approach relies on specific assumptions about the model's transition density. arcidiacono_miller_2019nonstationary propose a class of estimators based on the finite dependence property, which incorporates unobserved population heterogeneity and avoids matrix inversion when computing the likelihood. However, the algorithm only applies to models with finite dependence property.
This paper proposes a class of estimators that are similar to arcidiacono_miller_2019nonstationary's but can be applied to models without the finite dependence property. This paper also connects to the emerging literature on Euler equation characterization for dynamic discrete choice problems. Building on Aguirregabiria2013, Aguirregabiria2016, we redefine the discrete choice problem as a continuous choice problem in probability space, defining states by probability distributions and choices as probability vectors. Our key difference from Aguirregabiria2013, Aguirregabiria2016 is in modeling both state and decision variables in the probability space, while they only model choices in this space. We show that the optimal choice probabilities of the model can be described through the intertemporal trade-offs spanning a finite number of periods, provided that the model possesses the finite dependence property.
The rest of the paper is organized as follows. Section (ref) describes the dynamic discrete choice and the framework used to estimate the model.
Section (ref) proposes a general approach to search for optimal weight vectors. Section (ref) describes the estimator derived under characterization. Section (ref) presents the results of the Monte Carlo experiments.
An agent chooses among $J$ mutually exclusive discrete actions in each period to sequentially maximize the expected discounted sum of utilities $$E\left[ \sum_{j=0}^{T}\beta ^{j} [ u_t(z_t,d_t) + \epsilon_t(d_t)] \mid d_{t},z_{t}\right],$$ where the expectation is taken over the future value of $\{z_{t+j},\boldsymbol \epsilon_{t+j} \}_{j=1}^T$. The time horizon $T$ can be finite or infinite. Here, $\beta\in (0,1)$ is a discount factor, $[ u_t(z_t,d_t) + \epsilon_t(d_t)]$ is the time-separable payoff at time $t$ for discrete action $d_t\in \mathcal{D}:= \{0,1,2,\ldots, J-1\}$ given the state variable $z_t$ and an idiosyncratic choice-specific shock, $\epsilon_t(d_t)$.
The vector of choice-specific shocks $\boldsymbol{\epsilon_t}:= (\epsilon_{1t},...,\epsilon_{Jt})^\top $ has continuous support and is assumed to be independently and identically distributed over time with density function $g(\boldsymbol {\epsilon}_t)$. The state variable $z_t$ is decomposed as $z=(x_t,s)$, where $x_t$ is observed but $s$ is unobserved to the econometrician. We assume that an unobserved state variable $s\in \mathcal{S}:= \{1,2,...,K\}$ takes one of $K$ possible values and their values are fixed over time, representing an agent's permanent unobserved heterogeneity. The state variable $x_t$ follows a Markov process with finite discrete support $\mathcal{X} = \{ 1,\ldots, |\mathcal{X}|\}$, $|\mathcal{X}|<\infty$. The probability of $z_{t+1}$ occurring in time $t+1$ given $(d_t,z_t)$ is denoted by $f_t(z_{t+1} |z_t, d_t)$ for $z_t\in \mathcal{Z}:=\mathcal{X}\times\mathcal{S}$.
Let $D_t(z_t,\boldsymbol\epsilon_t)$ be the optimal decision rule at time $t$ given by $$ D_t(z_t,\boldsymbol\epsilon_t)=\arg\max_{d \in \mathcal{D}} \left\{ u_t(z_t,d) + \epsilon_t(d) + \beta \sum_{z_{t+1} \in \mathcal{Z}} V_{t+1}(z_{t+1}) f_t(z_{t+1}|z_t,d)\right\}, $$ where the integrated value function $ V_t(x_t)$ is recursively defined via Bellman equation as
The integrated value function is represented by a vector as $\mathbf V_t := (V_t(1),...,V_t(|\mathcal{Z}|))^\top$.
We define the choice-specific value function $ v_t(z_t,d_t)$ as the sum of the per-period payoff flow and the discounted continuation value
Taking the choice of $d = 0$ as the baseline, we define the value differences as $\tilde{ v}_t(z_t,d_t) = v_t(z_t,d_t) - v_t(0,z_t)$ and collect them as $\tilde{\boldsymbol v}_t(z_t) = (\tilde{v}_t(1,z_t),...,\tilde{ v}_t(J-1,z_t))^{\top}$ and $\tilde{\boldsymbol v}_t=\{\tilde{\boldsymbol v}_t(z_t): z_t\in \mathcal{Z}\}$. Then, the probability of choosing $d_t$ given $z_t$ at time $t$ can be expressed as a function of the vector of value differences denoted by $\boldsymbol {\Lambda}_t$ as
We collect conditional choice probabilities across different choices into a vector as $\boldsymbol p_t(z_t) = (p_t(z_t,0),...,p_t(z_t,J-1))^\top$ and let $\boldsymbol p_t = \{\boldsymbol p_t(z_t): z_t\in \mathcal{Z}\}$. Proposition 1 of Hotz1993 established that the function $\boldsymbol {\Lambda}_t$ is invertible so that, given the conditional choice probabilities $\boldsymbol p_t$, there exists a unique vector of value differences $\tilde{\boldsymbol v}_t$. This invertibility result has been exploited to develop a computationally attractive two-step estimator of dynamic discrete choice models [Add citations here].
We now derive a representation of the choice-specific value functions based on the analysis of arcidiacono2011conditional and arcidiacono_miller_2019nonstationary. The following theorem shows that the difference between the value function $V_t(x_t)$ and the conditional value function $ v_t(z_t,d_t)$ is expressed as a function of the conditional choice probabilities.
The function $\psi_d(\boldsymbol p_t)$ has an analytical expression or is straightforward to evaluate when $\epsilon_t$ follows the Generalized Extreme Value (GEV) distribution, of which special cases include T1EV distribution and nested logit arcidiacono2011conditional. Moreover, the mass transport approach by chiong2016duality can be used to evaluate $\psi_d$ for general distributions beyond the GEV.
For each triple $(z_t,z_{t+1},d_t)\in \mathcal{Z}^2\times\mathcal{D}$, consider a vector of weights $$\boldsymbol w_{t+1}(z_t,z_{t+1},d_{t}):= ( w_{1,t+1}(z_t,z_{t+1},d_{t}),...,w_{J,t+1}(z_t,z_{t+1},d_{t}) )^\top$$ that satisfy $\sum_{d'\in \mathcal{D}}w_{d',t+1}(z_t,z_{t+1},d_{t})=1$ and $||\boldsymbol w_{t+1}(z_t,z_{t+1},d_{t})||<\infty$. Evaluating equation ((ref)) at $t+1$, substituting equation ((ref)) at $t+1$ into the resulting equation, and taking their weighted averages across $J$ choices give
By substituting equation ((ref)) into the right-hand side of equation ((ref)), we obtain the following representation of choice-specific value functions:
where
The representation ((ref)) follows from equation (2.6) in Theorem 1 of arcidiacono_miller_2019nonstationary. Importantly, however, we choose the decision weights $\boldsymbol w_{t+1}$ for each triple $(z_t,z_{t+1},d_t)$ while arcidiacono_miller_2019nonstationary consider the weights that depend only on the value of $(z_{t+1},d_t)$. With this modification, we generalize their definition of 1-period dependence as follows.
Because we allow the decision weights to depend on not only $(z_{t+1},d_t)$ but also $z_t$, a class of models that exhibit 1-period dependence under our definition is broader than those under the definition of arcidiacono_miller_2019nonstationary. Furthermore, we exploit this additional flexibility to develop a numerical method to find the decision weights that lead to a model with finite dependence.
Under 1-period dependence, value differences in choice-specific value functions between choices do not depend on the integrated value function $V_{t+2}$ as
where
The above analysis can be extended to finite dependence over multiple periods. Given a triple $(z_t,z_{t+\tau},d_t)\in \mathcal{Z}^{2}\times \mathcal{D}$ for $\tau=1,...,\mathcal{T}$, let $$\boldsymbol w_{t+\tau}(z_t,z_{t+\tau},d_t) := ( w_{1,{t+\tau}}(z_t,z_{t+\tau},d_t),...,w_{J,{t+\tau}}(z_t,z_{t+\tau},d_t))^\top$$ be a vector of weights that satisfy $\sum_{d'\in \mathcal{D}}w_{d',{t+\tau}}(z_t,z_{t+\tau},d_t)=1$ and $||\boldsymbol w_{{t+\tau}}||<\infty$, and let
Define $\kappa_{t+\tau}^{\boldsymbol W_{t+\tau}}(z_{t+\tau+1}|z_t,d_t)$ recursively by
where the dependency of $\boldsymbol W_{t+\tau}$ and $\boldsymbol w_{t+\tau}$ on $(z_t,...,z_{t+\tau},d_t)$ is subsumed for brevity. Then, we define $\rho$-period dependence as follows.
Then, by applying induction to equation ((ref)) together with equation ((ref)), we obtain the following representation of value differences under $\rho$-period dependence:
where $\tilde\kappa_{t+\tau-1}^{\boldsymbol W_{t+\tau-1}}(z_{t+\tau}|z_t,d_t):= \kappa_{t+\tau-1}^{\boldsymbol W_{t+\tau-1}}(z_{t+\tau}|z_t,d_t)- \kappa_{t+\tau-1}^{\boldsymbol W_{t+\tau-1}}(z_{t+\tau}|z_t,0) $.
We develop a computationally attractive estimator for non-stationary models by using the representation of value differences in equation ((ref)) together with the mapping from value differences to the conditional choice probabilities in ((ref)).
We assume that $z_t$ is written in a vector form with $K$ variables as $z_t=(z_{1t},...,z_{Kt})^\top$, where each element $z_t^k$ for $k=1,...,K$ has a finite support. For identification, we impose normalization condition that $u_t{z_t,0}=0$ for all $z_t\in\mathcal{Z}$ and we further assume that the instantaneous utility function is a linear function of $(z_{1t},...,z_{Kt})$: \[ \tilde u_t(z_t,d) = u_t(z_t,d) = \theta_0^d + \theta_1^d z_{1t} + ... + \theta_K^d z_{Kt}:= z_t^\top \theta^d \]` with $\theta^d = (\theta_1^d,...,\theta_K^d)^\top$ for $d=1,...,J-1$.
Suppose that we estimate the conditional choice probabilities $\boldsymbol p_t$ and transition functions $f_t(z_{t+1}|z_t,d_t)$ in the first stage, of which estimators are denoted by $\hat{\boldsymbol p}_t$ and $\hat f_t(z_{t+1}|z_t,d_t)$, respectively. Furthermore, suppose that, given $\hat f_t(z_{t+1}|z_t,d_t)$, we have estimated the decision weights $\boldsymbol W_{t+\tau}$ under which a model exhibits $\rho$-period dependence, following a procedure discussed in next section. Let $\hat{\boldsymbol W}_{t+\tau}(z_t,...,z_{t+\tau},d_t)=(\hat{\boldsymbol w}_{t}(z_t,z_{t+1},d_t),...,\hat{\boldsymbol w}_{t+\tau}(z_t,z_{t+\tau},d_t))$ be the estimated weights.
Define
In this subsection, for brevity, we assume that both the transition function and the decision weights $\boldsymbol W_{t+\tau}$ under which a model exhibits $\rho$-period dependence are known to econometricians. Furthermore, for identification, we assume that $u_t(z_t,0)=0$ for all $z_t\in\mathcal{Z}$ and the utility function is specified in linear in parameters as:
The guess and verify method is predominantly the sole approach to ascertain finite dependence in the existing research. Consequently, nearly all empirical applications of finite dependence have focused on two particular instances of one-period dependence: models with either a terminal choice or a renewal choice arcidiacono_miller_2019nonstationary.
To extend
We propose solving the decision weights that nearly satisfy the conditions for finite dependence property given by equations ((ref)) and ((ref)). Then, using these weights, we develop a conditional choice probabilities estimator under near-finite dependence for non-stationary models.
We aim to estimate structural parameters: preferences, transition probabilities, and the discount factor $\beta$. We have a short-panel data for $N$ individuals, consisting of their actions $d_t$ and a subset $x_t$ of the state variable vector $s_t$. We distinguish between two subsets of state variables: $s_t = (x_t, \epsilon_t)$. Public information variables $x_t$ are observable by both agents and researchers, while private information variables $\epsilon_t$ are only visible to the agent.
Agents have preferences over state variables $s_t$ and actions $d_t$. Actions belong to a discrete set $\mathcal{D}=\{1,2,...,|\mathcal{D}|\}$. The time horizon can be finite or infinite. The utility is time-separable with a one-period function $ U_t(d_t,s_t)$. Preferences are expressed as discounted sums of utilities. Agents maximize expected utility considering a Markovian transition probability $p_t(s_{t+1}|d_t, s_t)$.
We aim to estimate structural parameters: preferences, transition probabilities, and the discount factor $\beta$. We have panel data for $N$ individuals, consisting of their actions $d_t$ and a subset $x_t$ of the state variable vector $s_t$. We distinguish between two subsets of state variables: $s_t = (x_t, \epsilon_t)$. Public information variables $x_t$ are observable by both agents and researchers, while private information variables $\epsilon_t$ are only visible to the agent.
Let $\theta$ be the vector of structural parameters. To derive an estimation criterion for the model and the data, we make the following two assumptions concerning the role of public information and private information state variables throughout the paper.
Under Assumption (ref) to Assumption (ref), we define the integrated value function $ V(x_t)$ by integrating the optimal choice of the agents under the Bellman equations over the private information state variable:
Under the above assumptions, the integrated value function $\mathbf V := \{ V_t(x): x \in \mathcal{X} \} \in \mathcal{B}_V \subset \mathbb{R}^{X}$ is a vector of size $X$.
We define the choice-specific value function $ v_t(z_t,d_t)$ as the discounted sum of future values of choosing alternative $d_t$:
Taking the choice option $d = 0$ as the baseline option, we define the value differences as $\tilde{ v}_t(z_t,d_t) = v_t(z_t,d_t) - v_t(z_t,d_t)$ and collect them as $\tilde{\boldsymbol v}_t(x_t) = \{ {v}_t(d,x_t): d \in \mathcal{D} \backslash \{ 0\} \} \in \mathbb{R}^{D}$. The conditional choice probabilities of the action $d_t$ given the public information state $x_t$ are defined as
We refer to $\boldsymbol {\Lambda}(\tilde{\boldsymbol v}_t(x_t))(d_t,x_t)$ as the optimal conditional choice probability (OCP) mapping. We collect leave-one-out conditional choice probabilities into a vector as $\boldsymbol p_t(x_t) = \{ p_t(d,x_t) : d \in \mathcal{D} \backslash \{ 0\} \} \in \mathbb{R}^{D}$. If agent $i$ makes an optimal choice for each current state $(x_t, \epsilon_t)$ and all future states, then $\boldsymbol p_t(x_t) = \boldsymbol {\Lambda}_t(\tilde{\boldsymbol v}_t(x_t))$.
Following the result of Hotz1993, we introduce the inversion of the OCP mapping.
Lemma 1 of arcidiacono2011conditional shows that the difference between the value function $V_t(x_t)$ and the conditional value function $ v_t(z_t,d_t)$ is expressed as a function of the conditional choice probabilities. This lemma plays a central role in developing our finite dependence estimator.
The function $\psi_d(\boldsymbol p_t)$ has an analytical expression or is straightforward to evaluate when $\epsilon_t$ follows the Generalized Extreme Value (GEV) distribution, of which special cases include Type-I value distribution and nested logit arcidiacono2011conditional. Moreover, the mass transport approach by chiong2016duality can be used to evaluate $\psi_d$ for general distributions beyond the GEV.
[Provide examples with the GEV and nested logit.]
Following the discussion of arcidiacono2011conditional and arcidiacono_miller_2019nonstationary, we define the general finite dependence property as follows.
We now introduce the proposition that if we can find a weight vector that sums up to 1, then the model displays finite dependece property. Note that we do not require the weights to be between 0 and 1. We let $\tilde{\boldsymbol f}(d,x)$ be the row vector of $[\tilde f(x^\dagger | d, x)]$ for all $x^\dagger \in \mathcal{X}$, and we let $\boldsymbol f(0,x)$ be the row vector of $[f(x^\dagger|0,x)]$. For any weight vector $\boldsymbol w \in \mathcal{B}_w := \{ \boldsymbol w \in \mathcal{R}^{XD} : \sum_{d \in \mathcal{D}} w(d,x) = 1 ~ \forall x \in \mathcal{X} \}$, define the $\boldsymbol w$-weighted transition matrix and the difference in transition probability,
Proposition (ref) demonstrates that if a model exhibits the finite dependence property, the optimal choice probabilities can be represented as a mapping of one-period forward choice probabilities. In such cases, given an initial estimate for $\{\boldsymbol p_{t+\tau}:\tau=1,\ldots,\rho\}$, the conditional choice probabilities can be evaluated without solving the Bellman equation.
Proposition (ref) provides an alternative characterization of value function differences $\tilde{v}(d,x)$ using the finite dependence property: a model exhibits finite dependence if there exists a finite-period sequence of weight vectors, $\{\boldsymbol w_{\tau}^*\}_{\tau=1}^{\rho}$, such that the value function differences $\tilde {v}(d,x)$ can be represented by $\rho$ periods of payoffs. Models not exhibiting finite dependence are considered to have non-finite dependence properties. Corollary (ref) presents a special case of finite dependence, where a sequence of actions exists such that if the agent follows it, the value differences can be represented by a finite number of future payoffs, as shown by arcidiacono2011conditional.
In this section, we present an estimator for a dynamic discrete choice model with an infinite horizon. This model does not exhibit finite dependence property, even under the stationarity assumption. The data observed by the researcher includes $\{ x_t, d_t \}: i = 1,\ldots,N, t = 1,\ldots, T_{ {data}}$. The primary objective of the researcher is to provide a reliable estimator of the structural parameter $\boldsymbol \theta$.
We define $\boldsymbol {V}$, $\tilde{\boldsymbol {v}}$, $\boldsymbol {u}_d$, $\boldsymbol {e}^{\boldsymbol {p}}_d$, $\boldsymbol {F}_d$, $ \bar{\boldsymbol {U}} ^{\boldsymbol {p} } $, $\bar{\boldsymbol {F}} ^{\boldsymbol {p}} $ etc. similarly to $\boldsymbol {V}_t$, $\tilde{\boldsymbol {v}}_t$, $\boldsymbol {u}_{d,t}$, $\boldsymbol {e}^{\boldsymbol {p}}_{d,t}$, $\boldsymbol {F}_{d,t}$, $ \bar{\boldsymbol {U}}_t ^{\boldsymbol {p}_t } $, $\bar{\boldsymbol {F}}_t ^{\boldsymbol {p}_t} $ etc. but using $u(d,x) $ and $f(x' | x,d)$ in place of $u_t(d,x) $ and $f_t(x' | d,x)$ under Assumption (ref). Then, the integrated Bellman equation in probability space is given by \(\boldsymbol {V} = \max_{\boldsymbol {p} \in \mathcal{P}}\ \bar{\boldsymbol {U}} ^{\boldsymbol {p} } + \beta \bar{\boldsymbol {F}} ^{\boldsymbol {p}} \boldsymbol {V}.\) Define $ \boldsymbol {u}(\{d_{i}\}_{i=1}^{X}):= [ {u}_t(d_1,1), \ldots, {u}_t(d_{X},X)]^{\top}$, $\boldsymbol {e}^{\boldsymbol {p}}(\{d_{i}\}_{i=1}^{X}) : = [{e}^{\boldsymbol {p}(1)}(d_1,1), \ldots, {e}^{\boldsymbol {p}(X)}(d_{X},X) ]^{\top}$ and $ \boldsymbol {F}(\{d_{i}\}_{i=1}^{X}) : = [(\boldsymbol {f}(d_1,1) )^{\top}, \ldots, (\boldsymbol {f}(d_{X},X) )^{\top} ]^{\top}$ With this notation, we have $\boldsymbol {u}_d=\boldsymbol {u}(\{d_{i}\}_{i=1}^{X})$, $\boldsymbol {e}^{\boldsymbol {p}}_d=\boldsymbol {e}^{\boldsymbol {p}}(\{d_{i}\}_{i=1}^{X})$, and $\boldsymbol {F}_d=\boldsymbol {F}(\{d_{i}\}_{i=1}^{X}) $ when $d_i=d$ for all $i=1,\ldots,X$.
The characterization of finite dependence discussed in Section (ref) can be numerically exploited to develop a computationally attractive estimator. Define the vector of transition density of decision $d$ at state $x$ as $\mathbf f(d,x) = [f(1|d,x),f(2|d,x),\ldots,f(X|d,x)]^{\top}$. The $\mathbf w \in \mathcal{B}_w $ be an arbitrary weight function and we define the $\mathbf w $-weighted transition matrix $\mathbf F(\mathbf w)$ as defined in (ref).
The idea is to choose $\boldsymbol {w}_{t+1}$ such that $(\tilde {\boldsymbol {f}}_{t}(d,x))^{\top} {\boldsymbol {F}} (\boldsymbol {w}_{t+1} )$ is close to zero for all $d\in\mathcal{D}$ and all $x \in \mathcal{X}$; then the conditional choice probabilities are approximated by ((ref)) which is easy to compute.
Define $r(d, x; \boldsymbol {w}_{t+1}) = \lVert(\tilde {\boldsymbol {f}}_{t}(d,x))^{\top} {\boldsymbol {F}} (\boldsymbol {\tilde w}_{t+1} ) \rVert$ be the norm of the forward transition matrix starting the state action pair $(d,x)$ at time $t$. We find the weight that minimizes the sum of the norm of the forward transition matrix across all initial state-action pair $(d,x)$
We estimate $\theta$ by minimizing the log-likelihood function. \[\hat \theta_{ {AFD}} = \arg\max \sum_{i=1}^N\sum_{t=1}^{T_{ {data}}} \log \boldsymbol {\Lambda}(\tilde{\boldsymbol {v}}_{ {AFD}}(x_t;\boldsymbol\theta))(d_t, x_t), \] where $\boldsymbol {\Lambda}(\cdot)$ is the OCP mapping and $\tilde{\boldsymbol {v}}_{ {AFD}}(x_t)$ is a vector of almost-finite-dependent characterization of value difference: $\tilde{\boldsymbol {v}}_{ {AFD}}(x_t) =\{ \tilde{ {v}}_{ {AFD}}(d, x): d \in \mathcal{D} / \{ 0\} \}$. The almost-finite-dependent characterization of value difference is defined as
With $r(d, x; \boldsymbol {w}_{t+1})$ close to 0, $\tilde{v}_{ {AFD}}(d, x) \approx \tilde{ {v}}_{\hat{\boldsymbol {w}}_t(x),t}(d,x)$. Then the almost-finite-dependent characterization minimizes the impact of omitting the value function two periods ahead.
In practice, it may be computationally costly to solve the minimization problem ((ref)) across different values of $x$. Then, we choose the same value of $\boldsymbol {w}_{t+1}(x)$ across $x$ by solving the following minimization problem: \[ \boldsymbol {w}_{t+1} = \operatorname*{arg\,min}_{\boldsymbol {\tilde w}_{t+1} \in \mathcal{B}_w } \sum_{x \in \mathcal{X}} \sum_{d\in\mathcal{D}} \lambda(d,x) r(d, x; \boldsymbol {w}_{t+1}), \] where $\lambda(d, x)$ is the weight on each initial state-action pair. We can use the empirical frequency of $x$ for the weight $\lambda(d, x)$.
The two-step estimators suffer from finite sample bias and one way to overcome such a problem is by applying the estimator recursively. The literature is rich for applying the Hotz-Miller estimator sequentially, known as the nested pseudo-likelihood estimator aguirregabiria2007sequential. This class of estimators estimates structural parameters and uses the structural parameters to update the CCPs and value functions in each iteration. For each iteration, the value function computation involves inverting a matrix of the probability-weighted transition matrix of size $X \times X$, and henceforth is computationally costly when the state space size $X$ is large. The computational cost of inverting a matrix grows cubical in the dimension of the matrix. The alternative characterization we have gives us contraction mapping that can be used to avoid the repetitive matrix inversion and therefore provides a time-efficient sequential estimator.
We define the Bellman operator given the parameter $\boldsymbol\theta$ as $\Gamma(\mathbf{V};\boldsymbol\theta)$, and at the fixed point, the value function is a solution to $\boldsymbol V = \Gamma(\boldsymbol V;\boldsymbol\theta)$, where \[ \Gamma(\boldsymbol V;\boldsymbol\theta) = \log \left( \sum_{d \in \mathcal{D}} \exp \left\{ \boldsymbol u_d(\boldsymbol\theta) + \beta \boldsymbol F_d \boldsymbol V \right\}\right). \] Suppose we find we sequence of weights $\boldsymbol w_1, \boldsymbol w_2 ,\ldots, \boldsymbol w_p$ such that $r_p(\boldsymbol w_1, \boldsymbol w_2 ,\ldots, \boldsymbol w_p) = \lVert \mathbf{\tilde F} \mathbf{F}(\mathbf{w}_{1}) \ldots \mathbf{F}(\mathbf{w}_{p}) \rVert $ is sufficiently small. We then define the $(\rho+1)$period almost finite dependent estimator with $q$-fold myopic Bellman update $\boldsymbol{\theta}^{ {AFD-Seq}}_{p,q}$ as follows. For each iteration $k$, with previously estimated parameters $\hat{\boldsymbol\theta}^{(k-1)}$ and value function $\boldsymbol V^{(k-1)}$, we proceed the following steps. \\\noindentStep 1: Update the value functions with $q$-fold myopic Bellman operator: \[ \boldsymbol V^{(k)} = \underbrace{\Gamma( \ldots \Gamma( V^{(k)}; \hat{\boldsymbol\theta}^{(k-1)} ) \ldots ; \hat{\boldsymbol\theta}^{(k-1)})}_{q\text{-fold}}. \] \\\noindentStep 2: Estimate the structural parameter with the $(\rho+1)$period almost finite dependence estimator while plugging in the updated value function: \[ \hat{\boldsymbol\theta}^{(k)} = \arg\max \sum_{i=1}^N\sum_{t=1}^{T_{ {data}}} \log \boldsymbol{\Lambda}( \boldsymbol {\tilde v}_{ {AFD}_p}(x_t;\boldsymbol\theta) )(d_t,x_t), \] where \[
\]
For the sequential estimator using AFD mapping, we update the Value Function using the Bellman contraction mapping. To get the equivalence to the full solution, it is sufficient to update $q^{ {BE}}$ times, where $(1 - \beta)^{q^{ {BE}}} = \lVert \tilde{\boldsymbol F} \boldsymbol {F}^{\boldsymbol w^1} \rVert$. In the simulation, we compute the iterations it takes to achieve a full solution as $q^{ {BE}} = \log(1 - \lVert \tilde{\boldsymbol F} \boldsymbol {F}^{\boldsymbol w^1} \rVert) / \log(\beta) $.
In this section, we explore the optimal weight-searching process for models with or without finite dependence properties, focusing on the one-period optimal weight.
The objective is to minimize the $L-2$ norm of $\tilde{\mathbf{F}} \mathbf F(\mathbf w)$ for all $d \in \mathcal{D} / \{0\}$, with respect to $\mathbf w$. In order to derive the condition for the minimization, we first write $\tilde{\mathbf{F}} (d) \mathbf F(\mathbf w) $ as a linear function of $\mathbf w$.
For any action $d \in \mathcal{D} / \{ 0 \}$, the $ij$-th element of $\tilde{\mathbf{F}} (d) \mathbf F(\mathbf w) $ is \[
.\]
Let $\mathbf{w}^+ = [ w(1,1) , \ldots, w(1,X) ,\ldots , w(D,1) , \ldots, w(D,X)]^{\top}$ be a $ \big(DX\big) \times 1$ row vector such that for each state $x$, we leave $w(0,x)$ one out. The problem of minimizing
which sums over $D X X$ conditions, and the rows of $\mathbf{G}$ and elements of column vector $\mathbf{g}$ are defined as \[\mathbf{g}(d,i,j) = [\tilde f ( 1 | d,i ) \tilde f ( j | 1,1 ) , \ldots, \tilde f ( X | d,i ) \tilde f ( j | D,X )], \quad g^0(d,i,j) = \sum_{k \in \mathcal{X}} \tilde f(k|d,i) f(j| 0,k). \]
We outline approaches to find the weight that minimizes the Frobenius norm of the transition matrix, reducing the impact of future value on current value differences. This method applies to both one-period and two-period weight solutions, as their objective functions are linear functions of weights. We use the one-period weight solution as an example. Given the linear system in (ref), we could solve $\mathbf{w}$ using ordinary least squares, but the large dimensions of the $\mathbf{G}$ matrix may cause memory constraints. To address memory and time constraints, we propose two alternatives: a direct solution using partial constraints and an SGD approach.
The benchmark solution incorporates all constraints. The computation involves finding a solution for $\mathbf{G}^{\top} \mathbf{G} \mathbf{w}^+ = \mathbf{G}^{\top} \mathbf{g}$, where $\mathbf{G}$ and $\mathbf{g}$ are the matrix and vector created by stacking all $\mathbf{g}(d,i,j)$ and $ {g}^0(d,i,j)$ over $d \in \mathcal{D} / {0}$ and $i,j \in \mathcal{X}$. Observe that $\mathbf{G}^{\top} \mathbf{G}$ has dimensions of $(XXD) \times (XD)$, whereas $\mathbf{G}^{\top} \mathbf{G}$ has dimensions of $(XD) \times (XD)$. Consequently, computing and storing $\mathbf{G}^{\top} \mathbf{G}$ and $\mathbf{G}^{\top} \mathbf{g}$ beforehand requires considerably less memory compared to $\mathbf{G}$.
An alternative approach takes into account that some rows in $\mathbf{G}$ are very close to 0 and, as a result, may be redundant in the optimization process. Using only a subset of constraints can produce similar minimization results when solving for $\mathbf{w}$, as pointed out by lee2020econometric. Since $\mathbf{G}$ has $XXD$ rows, we assign the index $(d,i,j)$ to each row of $\mathbf{G}$. Let $\mathcal{I}$ be the set of $(d, i,j)$ used, and $\mathbf{G}_{(\mathcal{I})}$ and $\mathbf{g}_{(\mathcal{I})}$ be the corresponding matrix and vectors that stacks these conditions. The alternative specification involves solving $\mathbf{G}_{(\mathcal{I})}^{\top} \mathbf{G}_{(\mathcal{I})} \mathbf{w}^+ = \mathbf{G}_{(\mathcal{I})}^{\top} \mathbf{g}_{(\mathcal{I})}$.
A time-inefficient method for selecting the set $\mathcal{I}$ is to calculate the values for each row $\mathbf{g}(d, i,j)$, compare the norms of $\lVert\mathbf{g}(d, i,j) \rVert$ across all rows, and choose a subset of rows above a certain threshold. Alternatively, the norm of the row $\mathbf{g}(d, i,j)$ is highly correlated with the absolute value of $\tilde f(j|d, i)$, based on its definition.
In this subsection, we investigate the minimization of the sum of squares using the stochastic gradient descent (SGD) approach. This method approximates the problem's gradient with a random subset in each iteration. The algorithm is implemented as follows:
For iterations $k = 1,\ldots, K$ we randomly draw ${(d^{(k)},i^{(k)}) }$. Let the weight estimates from the previous round be $\mathbf{w}^+_{(k-1)}$, and let the batch of conditions used be $\mathcal{B}^{(k)} = { (d^{(k)},i^{(k)},j), \quad j \in \mathcal{X} }$. We then construct the approximated gradient $\sum_{ (d, i,j) \in \mathcal{B}^{(k)} } \frac{\partial}{\partial (\mathbf{w}^+)^{\top} }\big( \mathbf{g}(d, i,j) \mathbf{w}^+ + {g}^0(d, i,j) \big)^2.$\footnote{Note that we use a modified version of a stochastic gradient, in contrast to the standard one, where for each draw of $(d, i)$, we construct $X$ conditions.}
We update the weight estimation as follows:
\[ \mathbf{w}^+_{(k)} = \mathbf{w}^+_{(k-1)} - \frac{\alpha^{(k)} }{\sqrt{\xi_{k} + \boldsymbol \epsilon}} \odot \sum_{d,i,j \in \mathcal{B}_t } \frac{\partial \big( \mathbf{g}(d,i,j) \mathbf{w}^+ + {g}^0(d,i,j) \big)^2 }{\partial (\mathbf{w}^+)^{\top}} ,\]
where $\alpha^{(k)} = \alpha^{(k-1)}/ {decay~rate}$ represents the step length, $\odot$ denotes the element-wise matrix-vector multiplication operator, and $\xi_{k}$ is a diagonal matrix at iteration $k$ with each diagonal element $(i, i)$ being the sum of the squares of the first-order derivative of $\big( \mathbf{g}(d, i,j) \mathbf{w}^+ + {g}^0(d, i,j) \big)^2$ concerning $(\mathbf w)_i$ up to iteration $k$.
We employ the AdaGrad method, as discussed in ruder2016overview, section 4.3, and define $\xi_{k}$ as $\xi_{k} = \sum_{s = 0}^{k} \sum_{d,i,j \in \mathcal{B}_s } \frac{\partial \big( \mathbf{g}(d,i,j) \mathbf{w}^+ + {g}^0(d,i,j) \big)^2}{\partial (\mathbf{w}^+)^{\top}}$. In the SGD approach, the selection of the initial learning rate $\alpha^{(0)}$ and the number of epochs $(K)$ is crucial. If the learning rate is set too high, the algorithm may experience oscillations during the initial stages, making it difficult to find the optimal solution. On the other hand, if the learning rate is chosen too low, the algorithm converges slowly, which can lead to a longer training time and potentially getting stuck in local minima. Therefore, selecting an appropriate initial learning rate is essential to balance the trade-off between convergence speed and stability. The number of epochs is an important parameter in the training algorithms. If set too small, the algorithm may not have enough iterations to achieve the desired level of accuracy or performance, resulting in an underfit model. Conversely, if the number of epochs is set too large, the algorithm may take an excessive amount of time to complete, leading to increased computational costs without significant improvements in performance. We present the simulation results for various choices of learning rates and the number of epochs (see Figure (ref) and Table (ref)). For the estimation, we find that setting $\alpha^{(0)} = 0.01$, $ {decay~rate} = 1.0$, and $\epsilon = 10^{-8}$ yields satisfactory minimization results. \footnote{Relevant paper for further understanding of these parameters are bottou2010large, bottou2012stochastic.}
The primary advantage of Stochastic Gradient Descent (SGD) is its time efficiency. With SGD, we can extend the weight search for a $(\rho+1)$-period forward as follows: \[ \mathbf{w}_1,\mathbf{w}_2,\ldots,\mathbf{w}_{\rho} = \arg \min{\mathbf{\tilde{w}}_1,\mathbf{\tilde{w}}_2,\ldots,\mathbf{\tilde{w}}_{\rho} } \lVert \tilde{\mathbf{F}} \mathbf{F}(\mathbf{\tilde{w}}_1),\ldots, \mathbf{F}(\mathbf{\tilde{w}}_{\rho}) \rVert. \] Solving this problem involves complex interactions between weight vectors, which may be computationally intractable.
One approach to address this issue is the sequential estimation of weight vectors $\mathbf{w}_1, \mathbf{w}_2,\ldots, \mathbf{w}_5$. Initially, we find $\mathbf{w}_1$ such that $\mathbf{w}_1 = \arg \min{\mathbf{\tilde{w}}^1} \lVert \mathbf{\tilde F} \mathbf F (\mathbf{\tilde w}_1) \rVert$. Using the estimated weight vector for a one-period forward transition $\mathbf{w}_1$, we determine the weight vector for the second forward period transition: $\mathbf{w}_2 = \arg \min{\mathbf{\tilde{w}}_2} \lVert \mathbf{\tilde F} \mathbf F (\mathbf{w}_1) \mathbf F(\mathbf{\tilde w}_2) \rVert$. This process continues sequentially up to $\rho$.
The remaining steps follow by generalizing these steps to multiple $(\rho+1)$-periods. With the sequence of vectors $\mathbf{w}_1,\ldots, \mathbf{w}_{\rho}$, the Frobenius norm of the forward-transition matrix is computed as:
\[ \rho_{\rho} = \lVert \tilde{\mathbf{F}} \underbrace{ \mathbf F (\mathbf{w}_1) \cdots \mathbf F(\mathbf{w}_\rho) }_{p - \text{periods}} \rVert. \]
Alternatively, we can simultaneously estimate the weights for multiple periods, resulting in a smaller value $\rho$. However, this approach significantly increases computational complexity. Table (ref) shows the differences in computation time.
The baseline firm entry-exit model, inspired by Aguirregabiria (2016) Aguirregabiria2016, accounts for increased profitability as a result of past entry. The firm's structural vector is represented as $\theta = (\theta_0^{ { {VP}}}, \theta_1^{ { {VP}}}, \theta_2^{ { {VP}}},\theta_0^{ {FC}},\theta_1^{ {FC}},\theta_0^{ {EC}},\theta_1^{ {EC}})$. We adapt this model by incorporating the effect of lagged productivity, as demonstrated by Example 3 in kasahara2018estimation. However, the inclusion of the lagged productivity effect breaks the finite dependence assumption of the model.
The observed state variables are $x = (z_1,z_2,z_3,z_4,\omega,y)$, with $y$ representing the firm's current market entry status. The unobserved state variable, $\epsilon$, introduces heterogeneity among firms. Firms observe state variables $(x,\epsilon)$ and make decisions $d \in { 0,1 }$, where $d = 1$ indicates market operation and $d = 0$ indicates non-operation.
At time $t$, the firm's state variable is $(z_{1,t},\ldots,z_{4,t},\omega_t,y_t,\epsilon_t)$, with $y_t = a_{t-1}$. The firm's flow payoff is defined in equation ((ref)), containing three components: variable profit ($ {VP}$), fixed cost ($ {FC}$) for market operation, and entry cost ($ {EC}$) for market entry.
If $y_{t-1} = 1$ and $a_t = 1$, the firm pays only the fixed cost to operate. If $y_{t-1} = 0$ and $a_t = 1$, the firm incurs an additional entry cost to operate in the market.
The exogenous shocks $(z_1,z_2,z_3,z_4,\omega)$ follow independent $AR(1)$ processes. To discretize the state space, we use tauchen1986finite's method to construct transition probabilities for discrete state variables. Let $K$ denote the number of grids for exogenous state variables. Each $z_{j}$ takes $K_z$ values, and the productivity shock $\omega$ takes $K_o$ values. The state space dimension is $X = X * |\mathcal{Y}| = 2 * K_z^4 * K_o$.
Let $\{z_j^{(k)}: k = 1,\ldots,K \}$ be the support for state variable $z_j$, and define width values $w_j^{(k)} = z_j^{(k+1)} - z_j^k$. Let $\tilde{z}_{jt}$ be a continuous latent variable following the $AR(1)$ process $\tilde{z}_{jt} = \gamma_0^j + \gamma_1^j \tilde{z}_{j,t-1} + e_{jt}$, where $e_{jt} \overset{i.i.d}{\sim} N(0,\sigma_j^2)$.
With the result of a proposition (ref), the transition density function determines whether the model shows finite dependence property: the model is $(\rho+1)$-period finite dependent if there exists a sequence of weight vectors $\mathbf{w}_1^{+}, \mathbf{w}_2^{+}, \ldots, \mathbf{w}_{\rho}^{+}$ such that $\lVert \boldsymbol {\tilde F} \boldsymbol F (\mathbf{w}_1) \cdots \boldsymbol F(\mathbf{w}_\rho) \rVert = 0$. We assume the transition probability for the entry cost shocks and fixed cost shocks $z_{jt}$'s are not dependent on the action chosen; and the transition probability of the productivity shock $\omega_{jt}$ depends on the action:
The magnitude of $\gamma_a$ governs how much a firm's entrance decision on a market affects the firm's productivity. If $\gamma_a > 0$, the entry decision increases a firm's productivity permanently. Note that with $\gamma_a = 0$, this model's transitioned density satisfies 1-period single-action finite-dependent. The entry decision $(d_t = 1)$ and the exit decision $(d_t = 0)$ are both absorbing states and therefore the model satisfies the finite dependence assumption. If $\gamma_a > 0$, the model does not display a finite dependence property. We summarized the parameters used in the Monte Carlo simulations in table (ref).
In non-finite dependent models, obtaining the optimal weight when estimating with Average Finite Dependent (AFD) estimators is crucial. Directly estimating the weight that minimizes the forward transition matrix L2 norm using built-in functions can be computationally expensive, as the norm is a non-linear function of the weight vector. Instead, we find the optimal weight that minimizes the Frobenius norm of the forward transition matrix, closely approximating the L2 norm. The minimization of the Frobenius norm can be formulated as finding a solution to a linear function system of the weight vector, as discussed in Section (ref). In this section, we demonstrate that estimating weight sequentially reduces the Frobenius norm of the $(\rho+1)$-period forward-transition matrix.
First, we compare the algorithms proposed in Section (ref), which use all constraints, a subset of constraints, and Stochastic Gradient Descent (SGD). Table (ref) reports the one-period forward transition matrix Frobenius norm $\rho_1$, evaluated with the estimated weight under different specifications. We consider various state space sizes ($X = 64, 324, 486, 648, 1024, 1536$) and levels of impact of entry on productivity ($\gamma_a = 0, 1$).
Compared to the direct solution approach using all constraints or partial constraints, SGD sometimes does not reach the optimal level. For instance, when $\gamma_a = 0$ and $X = 64$, the direct solution minimizes the norm $\rho_1$ sufficiently close to 0 ($0.0143$), while the SGD estimates the weight at a higher norm ($0.0222$).
However, the full solution approach encounters memory constraints. On a Windows desktop computer with 32 GiB memory, the full solution approach cannot be directly applied, as the computer cannot allocate the memory required for the linear problem defined in Equation (ref). Employing only part of the constraints significantly reduces the computation time; however, it remains considerably more time-consuming compared to SGD.
While using SGD, choosing the learning rate and the number of epochs to run is a problem. The learning rate measures the step length for the iterative optimization process. When the step length is small, the convergence of the optimization is slow. When the learning rate is large, the optimization process may overshoot so that convergence does not happen. By using the AdaGrad in the SGD process, the algorithm adjusts the step length automatically. However, we still need to choose the initial learning rate(see Section (ref) for discussion). Figure (ref) and (ref) shows the performance of SGD algorithm with different learning rates ($0.01$, $0.1$ and $1$) with difference specification $\gamma_a=1$ and $\gamma_a=3$. With a small learning rate(such as $0.01$), the learning is very slow and the estimated $\rho$ decrease slowly as the number of epochs increases. With a large learning rate (such as $1$), the estimated $\rho$ performs unstable when the number of epochs is small and converges to a smaller value when the number of epochs increases.
In Table (ref), we report the estimated $\rho$ with a learning rate of 0.01 and different numbers of epochs. For varying state space sizes, the estimated $\rho$ decreases slightly as the number of epochs increases. However, the time used also increases as the number of epochs increases. For computational time efficiency, we choose to use 10 epochs for optimization.
Estimating only one period of weight does not yield a sufficiently small forward transition matrix norm under all specifications. For example, as the state space increases (as shown in Table (ref)), with the same value of $\gamma_a > 0$, the minimum one-period-forward transition matrix norm increases. To reduce the norm of the forward transition matrix, we estimate $(\rho+1)$-period optimal weight sequentially.
Table (ref) reports the estimated Frobenius norm under different specifications with state space sizes ($X = 64, 192, 5184, 15552$), finite-dependent ($\gamma_a=0$) and non-finite-dependent models ($\gamma_a = 1, 3$).\footnote{For the SGD approach, we fix the starting point for the weight estimation. For the estimation of the first-period weight $\boldsymbol w^1$, we start from a weight $\boldsymbol w_0$ where the probability is to choose action 1 for all states ($\boldsymbol w_0(1,x)=1$ for all $x \in \mathcal{X}$). When estimating the second-period weight $\boldsymbol w^2$, we start the algorithm from the estimated first-period weight $\boldsymbol w^1$.} When the model displays the finite-dependent property, this sequential algorithm generates the norm of a 1-period forward transition matrix with norm $\rho_1$ close to $0$.
With the non-finite dependence property ($\gamma_a = 1$ and $\gamma_a = 3$), the sequential estimation of $(\rho+1)$-period weights reduces the forward transition matrix norm as $\rho$ increases. The magnitude of the norm reduction depends on the model: the value of the productivity shock parameter $\gamma_a$ and how much we discretize the state space ($K_z$ and $K_o$).
For large state spaces ($X=15552$) and some values of the productivity shock parameter ($\gamma_a = 1$), with the first-stage SGD weight estimator, the norm for a 1-period forward transition matrix is greater than 1 ($\rho_1^{ {Sequential}}=1.3758$). The sequential weight estimator reduces the 1-period forward-looking transition norm to $\rho_2^{ {Sequential}}=0.3762$ and the 2-period forward-looking transition norm to $\rho_3^{ {Sequential}}=0.0893$.
When comparing with simultaneously estimated weight vectors, the sequential estimation of weight vectors has advantages in time, as shown in table (ref). Although simultaneously estimating $\mathbf w^1$ and $\mathbf w^2$ reduce the norm of the two-period forward-looking transition matrix more compared to sequentially estimating the weight vectors, it is much more time-consuming compared to the sequential approach. For a model with $X=1024$, the sequential approach takes $0.03$ seconds while the simultaneous approach takes over $1000$ seconds.
We now demonstrate the efficiency of the estimators using the proposed $AFD$ estimators with simulated data. As shown in Table (ref), we consider a case with the state space size $X=7500$, and we compare our proposed almost-finite-dependent ($ {AFD}$) estimator to the benchmark Hotz and Miller estimator ($\boldsymbol{\theta}^{ {HM}}$) in terms of performance and time efficiency.
$\boldsymbol{\theta}^{ {AFD}}{1,0}$ uses the estimated 1-period weight vector to compute $\boldsymbol F^{\boldsymbol w^1}$ and ignores the value function; $\boldsymbol{\theta}^{ {AFD}}{1,q^{ {BE}}}$\footnote{To get the equivalence to the full solution, it is sufficient to update $q^{ {BE}}$ times, where $\beta^{q^{ {BE}}} = 1 - \lVert \tilde{\boldsymbol F} \boldsymbol {F}^{\boldsymbol w^1} \rVert$. In the simulation, we compute the iterations it takes to achieve a full solution as the minimum integer that satisfies the condition $q^{ {BE}} > \log(1 - \lVert \tilde{\boldsymbol F} \boldsymbol {F}^{\boldsymbol w^1} \rVert) / \log(\beta) $.} uses the $\boldsymbol{\theta}^{ {AFD}}{1,0}$ estimator to myopically update the value function $q^{ {BE}}$ times and estimate the parameters plugging in the updated value function; $\boldsymbol{\theta}^{ {AFD}}{2,0}$, $\boldsymbol{\theta}^{ {AFD}}{3,0}$, $\boldsymbol{\theta}^{ {AFD}}{5,0}$ estimate the model with $(\rho+1)$-period almost finite dependent estimator while ignoring the future value function. We consider the estimators for both the finite-dependent model ($\gamma_a = 0$) and the non-finite-dependent model ($\gamma_a = 1$). With more than a 2-period weight-finding, the almost finite dependent estimator performs relatively close to the Hotz-Miller estimator.
One advantage of the AFD estimator is the computational time. When the state space is $X=7500$, the two-step estimator takes only 10% of that of the Hotz-Miller estimator.
Figure (ref) shows the time used to conduct sequential estimator with the recursive nested pseudo-likelihood estimator (NPL) aguirregabiria2007sequential and the proposed almost finite dependent estimator with 1-period (AFD2-SEQ). The time of NPL estimator increases with the cubic term of the state space size because of the time for matrix inversion in each iteration. We consider both finite-dependent($\gamma_a = 0$) and non-finite-dependent models ($\gamma_a = 1$). For finite-dependent models, AFD2-SEQ has time advantage over the NPL. The estimated forward-transition norm ($\rho_2$) is close to 0 and therefore we do not update the value function. For non-finite-dependent models, the estimated forward-transition norm ($\rho_2$) increases with the state space size. Therefore we update the value function during the iteration, but with a finite $q$-fold Bellman operator. Overall, when estimation is recursive, the AFD2-SEQ is more time efficient compared to HM estimation. To show the advantage, we consider a two-type finite mixture dynamic discrete choice model.
In this section, we present the sequential estimator that we use to estimate a two-type mixture model, where each firm belongs to one of the two types and the type is invariant over time. Each type, indexed by $m$, is summarized by the flow payoff parameter $\boldsymbol \theta_m$, for $m \in \{1,2\}$. To estimate the finite mixture model, we employ the Expectation-maximization(EM) algorithm, which is a sequential estimator. We compare the performance of the nested pseudo-likelihood(NPL) estimator aguirregabiria2007sequential with the AFD estimators, where the NPL estimator applies the Hotz-Miller estimator recursively with updated value functions. Table (ref) presents the averaged estimated parameters, the average squared mean squared errors, and the time used across Monte Carlo simulations with state space $X=7500$. The NPL estimator takes a much longer time (on average 424.667 seconds across 20 simulations) compared to ADF(ADF1 takes 30.307 seconds on average and ADF 3 takes 115.60 seconds). All NPL and AFD estimators report consistent estimation of the parameters. The NPL estimator has better efficiency compared to the AFD estimators. According to table (ref), NPL estimators have lower mean square errors than all AFD estimators. When we estimate with three periods AFD_3, the mean square errors are reduced compared to that of ADF_1.