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.
107,832 characters · 11 sections · 134 citation commands
Reinforcement Learning Based Computationally Efficient Conditional Choice Simulation Estimation of Dynamic Discrete Choice Models
\thispagestyle{empty}
\doublespacing \pagenumbering{arabic}
Since their introduction to marketing research with pioneering applications that include consumer learning about brand quality erdem1996decision, response to promotions gonul1996estimating, and catalog mailing decisions gonul1998optimal, dynamic discrete choice (DDC) models in a Markov Decision Process (MDP) framework have found widespread application in studying fundamental marketing problems.\footnote{See for example, work related to optimal intertemporal pricing strategy in durable goods markets nair2007intertemporal, demand in reward programs hartmann2008frequency, household behavior when brand attributes are uncertain but price and advertising signal quality erdem2008dynamic, replacement and purchase decisions in technology industry gordon2009dynamic,sriram2010investigating, observational learning in US kidney market zhang2010sound, sales-force compensation strategies misra2011structural,chung2014bonuses,kim2022structural, endogenizing market structure and long-run innovation to understand the relationship between competition and innovation GoettlerGordon2011,GoettlerGordon2014, framing service channel allocation as a dynamic programming problem based on customer preferences SunLi2011, firm's cross-selling strategies to maximize long-term profit LiSunMontgomery2011, consumer behavior in seasonal goods markets soysal2012demand, decision-making between products and bundles derdenger2013dynamic, seller reputations in freelance sites yoganarasimhan2013value, adoption and usage decisions of ATM cards yang2014dynamics, ability of consumers to optimally allocate usage under multipart tariffs gopalakrishnan2015consumer, dynamic model of addiction to cigarettes to evaluate how consumers respond to price changes GordonSun2015, thirst management huang2015short, evolution of brand preferences of new consumers che2015consumer, effectiveness of green technology adoption policies bollinger2015green, scheduling detailing activities in pharmaceutical markets liu2016empirical, insurance plan decisions mehta2017dynamic, effectiveness of reward programs in travel industry rossi2018lower, monitoring costs and consumer dissatisfaction associated with overdraft fees liu2018analyzing, dynamic oligopoly pricing model in the presence of switching costs cosguner2018dynamic, adverse selection in car insurance markets jeziorski2019skimming, intertemporal price discrimination in e-readers and e-books li2019intertemporal, and owner decisions in peer-to-peer sharing marketplaces yao2023dynamic.} DDC models are well-suited to studying many marketing problems because these are inherently dynamic as the decisions are sequential and depend on past experiences, present conditions and expectations about future consequences. For example, consumer choices about brand adoption and loyalty, or switching providers are based not only on previous experience, and current benefits and costs but also on expectations about these in the future. Firms, in turn, design pricing, promotion, and retention strategies with the explicit goal of shaping these dynamic decisions. Accounting for such dynamic aspects of consumer and firm decisions is therefore essential for understanding long-term customer value creation and for evaluating the effectiveness of various marketing strategies.
While DDC models provide insights about decision-theoretic primitives and counter-factual policy analysis lucas1976econometric,\footnote{Seminal applications in economics include research related to decisions about employee retention gotz1984dynamic, occupational matching miller1984job, fertility wolpin1984estimable,montgomery1988dynamic, patent renewal pakes1986patents, engine replacement rust1987optimal and job search, employment and retirement wolpin1987estimating,gonul1989dynamic,eckstein1989dynamic,berkovec1991job. For excellent reviews and critiques of applications in economics see e.g., eckstein1989specification, wolpin1996public, blundell2006advances, aguirregabiria2010dynamic, keane2010perspective, keane2010structural, rust2010comments, keane2011structural, arcidiacono2011practical, wolpin2013limits, low2017use and blundell2017have.} their estimation becomes prohibitively costly and infeasible, limiting their application to problems of practical interest as the state space and number of choices grow. This is particularly true with the availability of bigger and more granular data sets naik2008challenges, chintagunta2016marketing. This is because traditional DDC model estimation approaches, like the Nested Fixed Point (“NFXP”) algorithm rust1987optimal, solve the full dynamic programming (DP) problem to compute value functions accurately but suffer from the “curse of dimensionality.” The “computationally lighter” two-step “forward simulation” Conditional Choice Simulation (CCS) estimator hotz1994simulation, and its companion Conditional Choice Probability (CCP) estimator hotz1993conditional, eliminate the demanding step of repeated state-action space sweeps for fixed point computation as in NXFP by exploiting the mapping between normalized value functions and CCPs.\footnote{For an excellent review of CCP-based estimation of DDC models see e.g., arcidiacono2011practical.} However, both these, and the CCS especially, rely on sufficiently long simulation paths for accurate computation of value functions that may not be most computationally efficient. Although simplifying such problems can improve scalability, it often comes at the cost of accuracy and rigor, both of which are essential for generating reliable insights naik2008challenges, chintagunta2016marketing.
We propose algorithms that integrate Reinforcement Learning (RL) with two-step CCS estimation to improve computational efficiency without compromising accuracy. RL has emerged as one of the most powerful tools in Artificial Intelligence (AI) for automating decision-making and control. It has been successfully applied to a wide range of complex tasks, from self-learning systems that master games like Go silver2018general to fine-tuning Large Language Models to better align with human preferences, factual accuracy, and safety christiano2017deep, ouyang2022training. Like DDC models, RL addresses sequential decision-making problems using the MDP framework. However, while RL assumes the reward function is known and focuses on learning optimal policies, the DDC approach estimates reward functions (model primitives) from observed behavior, assuming optimal policies.
Our algorithms rely on three insights: (1) we first show that the CCS (“forward simulation”) approach is a special case of RL “Monte Carlo” and “Temporal Difference” algorithms, (2) starting from an initial state-action pair CCS updates the corresponding value function only after each simulation path has terminated, whereas RL methods may update the value functions for all the state-action pairs that are visited along a simulated path, and (3) although the RL and DDC approaches have different inferential goals, both focus on accurate computation of value functions. We develop two versions: (1) RLMC-CCS based on RL's “Monte Carlo” (MC) singh1996reinforcement, and (2) RLTD-CCS based on Temporal Difference (TD) sutton1988learning algorithms.
The main intuition behind our methods is that within each forward simulated path, a sequence of states and actions are visited, often multiple times. By treating these visits as the initial nodes (state-action pair) for computing the value functions as well, many more updates can be made in each simulated path. As the number of forward simulation paths increase, the number of different state-action visits also increases. The first algorithm, RLMC-CCS, treats each full path as a set of multiple sub-paths, each starting from individual state-action pairs visited along the path. However, when simulated paths are kept short to reduce the computational effort, terminating after only a few time steps, the estimates are shown to be less accurate. The second, more promising, RLTD-CCS algorithm provides highly accurate estimates even for shorter paths. Just like CCS, RLTD-CCS computes value functions over forward simulated paths. However, instead of relying on the total discounted returns from the entire length of a path, RLTD-CCS looks one or more steps ahead and uses the most recent value function update of the next state-action pair (or of the state-action pair encountered after simulating a few steps ahead). This converts the value function computation into an iterative update process, where value function update for a state-action pair is related (or, “bootstrapped" in RL jargon) to the latest value function of the future state-action pair(s), which is similar to fixed-point iterations in NFXP. The large number of bootstrapped updates help to converge to accurate estimates of value functions. Within the RLTD-CCS algorithm, by using a value function “learning” parameter, the value function updates get naturally linked to the general class of stochastic machine learning algorithms (robbins1951stochastic, kiefer1952stochastic).
Using Monte Carlo studies, we assess our approach in two settings: (i) a canonical machine replacement model rust1987optimal, and (ii) a consumer food choice model huang2015short. For both the models, we use the root-mean-square error (RMSE) between the modeled and estimated structural parameters as a metric to compare the estimation accuracy between the different algorithms. The RLTD-CCS outperforms both RLMC-CCS and CCS, achieving up to 3-4 orders of magnitude greater estimation accuracy using simulation paths that are upto ten times shorter than CCS. The performance remains robust even for large state-action spaces (about 5.77 million states), with RLTD-CCS surpassing CCS by a speed factor of 6 to 14 times. We also demonstrate that RLTD-CCS is less sensitive to discount ($\beta$), achieving a 70 factor speed advantage over CCS in estimation accuracy when the discount factor approaches one.
Our work contributes to the literature that is focused on estimating single agent DDC models in an MDP framework (although, it may also indirectly contribute to the literature on multi-agent models such as games of interaction between strategic agents).\footnote{For example, aguirregabiria2007sequential, bajari2007estimating, pakes2007simple and pesendorfer2008asymptotic build on the CCP and CCS formulations to introduce methods for estimating dynamic games of strategic interactions. See e.g., aguirregabiria2013recent and aguirregabiria2021dynamic for comprehensive reviews of the literature on estimating dynamic games.} There has been tremendous progress in this field over the last several decades since the work of rust1987optimal introduced the NXFP algorithm, and several approaches have been suggested to overcome this computational challenge. In addition to the CCP hotz1993conditional and CCS hotz1994simulation methods, these include computing value functions employing the Gittins Index miller1984job,eckstein1988empirical, using Monte Carlo integration over a sub-set of states and then interpolating using a regression function keane1994solution, using random Bellman Operators on a sub-set of grid-points rust1997using, iterating over policy functions instead of value functions aguirregabiria2002swapping, use of Bayesian Markov Chain Monte Carlo based algorithms imai2009bayesian, norets2009inference, relying on the properties of finite dependence or renewal arcidiacono2011conditional, using (equilibrium) constrained optimization su2012constrained, approximation using artificial neural networks norets2012estimation, using the Endogenous Grid-point Method (EGM) iskhakov2017endogenous, and using data driven state-space partitioning barzegary2022recursive. Most often, these methods provide an exact solution only for a sub-set of the state-space and assign an approximate value to the remaining (excluded) states. However, it is unclear whether these methods are generally applicable when the state and action space becomes large and the models more complex in being high-dimensional britton2021revisiting. In contrast, our approach is different as we do not approximate the value functions by using a subset of either the value functions or the state-action space, but rather use more computationally efficient simulation-based algorithms that like CCS operate on the entire observed state-action space. Our work extends the CCS based estimation methods by proposing new two-step forward simulation estimators. Another advantage of our approach is that it can be combined with any existing estimation method which is appropriate for CCP or CCS based estimation.\footnote{For example, our algorithms work well within the EM algorithm extension introduced by arcidiacono2011conditional for estimating DDC models with unobserved heterogeneity.}
Further, we contribute to the growing literature that uses machine-learning (ML) to estimate structural parameters (see e.g., iskhakov2020machine). These include using a non-parametric causal forest based approach to estimating heterogeneous treatment effects wager2018estimation, decision-trees for model selection schwartz2014model, and neural-networks for estimating (static) discrete choice models wei2025estimating. Our approach bridges the gap between the DDC and RL literatures and leverages on the similarities in value function computation in the two domains. As we focus on integrating computationally efficient machine learning (RL in our case) into DDC models, we propose fast, scalable algorithms to estimate structural models that are inherently transparent, interpretable, and explainable, rather than attempting to make machine learning models themselves more interpretable rudin2019stop.
Our work also contributes to the growing Inverse Reinforcement Learning (IRL) russell1998learning, ng2000algorithms literature, where the central objective is to infer a reward function from observed expert behavior and then derive an optimal policy. IRL can be viewed as a form of Imitation or Apprenticeship Learning abbeel2004apprenticeship,ciosek2021imitation, but differs from direct imitation in its attempt to recover the underlying preferences driving observed choices. A well-known challenge in IRL is identifiability: the problem is ill-posed, as multiple reward functions can explain the same behavior. One influential approach, Maximum Entropy IRL ziebart2008maximum, partially addresses this be selecting the reward function that explains the behavior while maximizing entropy over the policy space. Building on this and the “Behavioral Cloning” torabi2018bco approach, kang2025gradients use “anchor action” with fixed reward to regularize estimation, and report a scalable algorithm that doesn't require knowledge of transition dynamics. However, the estimated reward functions in these approaches are not structural. Separately, lee2025prep apply Adversarial IRL fu2018airl to high-dimensional content consumption data, and use computationally intensive simulated roll-outs to closely align the predicted and observed behavior. In contrast, our work embeds RL algorithms in CCS and estimates structural DDC models in a computationally efficient way from observed behavior. This hybrid approach retains the interpretability and policy structure of DDC models while gaining the scalability of RL, offering novel and practical alternative within the IRL landscape.
The work most closely related to ours is adusumilli2019temporal. In this work, function approximation of value functions within a linear semi-gradient algorithm is used to solve continuous state space models. This approach was adapted from the semi-gradient TD(0) algorithm (sutton2018reinforcement). In a similar work, basis function approximation was used to minimize the TD approximation error to estimate DDC models imaizumi2015approximation. However, methods that use function approximation and TD learning converge to a unique “TD fixed point,” the asymptotic error of which is $\frac{1}{1-\beta}$ times the smallest error that one could obtain using function approximation with an unbiased MC (e.g., CCS) method sutton2018reinforcement. As $\beta$ becomes close to 1, this error increases. Our method, on the other hand, does not approximate value functions, but computes value functions by using CCS simulations in a more computationally efficient way. We report that the estimation accuracy of our methods hold even when $\beta$ approaches 1, while getting even better speed and memory advantage than CCS.
The remainder of the paper is organized as follows. In the next section, we introduce reinforcement learning of value functions. We then present Monte Carlo studies, and finally, we conclude with a summary of our findings.
We use a canonical single agent DDC model in the MDP framework rust1987optimal to illustrate our method that we briefly describe next.
An agent takes sequential decisions in periods $t=1,2,...,T \leq \infty$. In the period $t$, the agent observes a discrete state $s_t\in \mathcal{S} = \left\lbrace 1,2,...,S_t \right\rbrace$ and then chooses a discrete action $a_t \in \mathcal{A} = \left\lbrace 1,2,...,J \right\rbrace$. All the actions are assumed to be mutually exclusive in any period. Before choosing an action, the agent is assumed to also observe a vector of states (unobservable to the researcher) which are denoted by $\epsilon_t = \left( \epsilon(a_t=1),\epsilon(a_t=2),...,\epsilon(a_t=J) \right)$.\footnote{In the absence of the unobservable (to researcher) state $\epsilon_t$, the agent's decisions will be a deterministic function of the observed (by both agent and researcher) state variable $s_t$. This implies that two agents, in the identical state $s_t$, will take same decision. However, this is seldom the case in the data. Including an unobserved random utility component $\epsilon_t$ allows the model to rationalize the data by permitting different decisions by agents in the identical state $s_t$. For example, in the engine replacement model of rust1987optimal, the model will imply that the superintendent will take the identical decision to replace the engine (or not) for all the buses in the same state (mileage). However, the data will clearly contradict this.} Upon taking an action, the agent receives an immediate payoff or utility, $U(s_t,\epsilon(a_t),a_t; \theta_u)$ where $\theta_u$ are the structural parameters of the utility function that need to be estimated. The objective of the agent in any period is to maximize the present discounted value (PDV) of the future expected utility stream:
where $\mathbb{E}$ is the expectation operator with expectations over future observable and unobservable states. The $\beta \in (0,1)$ is the discount-factor, and $(\theta_u, \theta_F)=\theta$ are the parameters to be estimated, where $\theta_F$ are parameters related to state transitions.
Several assumptions have been made in the literature to make the dynamic discrete-choice model rust1987optimal empirically tractable. We begin by briefly discussing these.
\noindentAssumption 1 Markovian policy: Only current states are relevant for current action and summarize any relevant information from past actions and states. However, this is not as restrictive an assumption as the information from the previous periods can also be accommodated in modeling the decision process by modifying the definition of the state space. As rust1994structural quoting 10.5555/26970 states, “the well-known trick of `expanding the state space' can be used to transform an $N$\textsuperscript{th} order Markov process into a 1\textsuperscript{st} order Markov process.”
\noindentAssumption 2 Conditional Independence: The joint transition probability can be factored as following:
This condition imposes restriction on the dynamics of the decision process by implying that the occurrence of $s_{t+1}$ depends only on the current state $s_t$ and action $a_t$. This condition further implies that the unobserved states are serially independent across periods and conditional only on the current state. While this is a strong restriction, it can be relaxed to allow for serial correlation.
\noindentAssumption 3 Additive separability: Each single-period utility is assumed to be additive separable in its deterministic and stochastic components, such that:
To maximize the PDV of the stream of utilities, the agent follows an optimal policy comprising a sequence of actions, $\left\lbrace a_\tau(s_\tau,\epsilon_\tau; \theta)\right\rbrace_{a_\tau\in \mathcal{A}, \tau=1,...,\infty}$, in each period. The PDV of the expected utility stream at each state when the agent follows an optimal policy is represented by the state's value function:
The optimal decision-rule can be expressed as:
For notational simplicity we drop the $t$ subscript unless indicated. Following convention we use $s^{\prime},\epsilon^{\prime}$, and $a^\prime$ to indicate the states and action in the next period. The value function can be simplified into a single period representation by using the Bellman Equation and the additive separability assumption on the single-period utility as follows:
Further, the choice-specific value function can be defined as:
The value function can be written in terms of the choice-specific value functions as follows:
We can extend the additive separability assumption to the choice-specific value functions by decomposing it into deterministic and stochastic components:
The decomposed choice-specific value function formulation can be used to derive the conditional choice probability (CCP), $\pi(\cdot)$, for selecting a particular action $m$ in state $s$ by integrating out the stochastic unobserved states:
where, the $J$-dimensional integral is taken over the joint density of the vector $\epsilon$.
The computational burden of evaluating the integral, when combined with the expectation operation over the entire state-action space comprising $\left(s, \epsilon \right)$ is extreme. While defining a finite $\mathcal{S}$ relieves some of the computation challenge, integrating over the stochastic unobserved states is still resource consuming.
\noindentAssumption 4 Error Distribution: In order to make the model more tractable, the convention has been to assume that the unobserved states are IID across choices and periods and given by the Type-1 Multivariate Extreme Value (MEV) distribution mcfadden1973conditional,rust1987optimal.\footnote{We follow the long literature starting with mcfadden1973conditional in using the MEV distribution as do hotz1993conditional, hotz1994simulation and rust1987optimal. See e.g., keane1997career for a model that uses the normal distribution for the unobserved states.} This assumption, when combined with the conditional independence assumption, reduces the CCP into a familiar logit-style expression:
However, unlike the static case where the logit expression only includes the current single-period utility, the “dynamic logit” expression includes the deterministic component of the choice specific value function (Equation (ref)) that depends on the PDV of the expected future utilities thereby making CCPs more complicated to compute.
CCS is predicated on the insight that instead of solving the dynamic programming problem to compute the value functions as the fixed point of a Bellman equation (NFXP) these may be computed directly using a “forward simulation” approach hotz1994simulation.
The “two-step" CCS estimation procedure involves a first step of obtaining non-parametric estimates of both the transition probability, $\hat{\mathit{p}}(s_{t+1} \vert s_t, a_t; \hat{\theta}_F)$, and CCPs, $\hat{\pi}(a_t \vert s_t)$, directly from the data. In the second step, for a given guess $\hat{\theta}_u$, the corresponding value functions are computed using “forward simulations” (based on $\hat{\mathit{p}}(s_{t+1} \vert s_t, a_t; \hat{\theta}_F)$ and $\hat{\pi}(a_t \vert s_t)$) that are in turn used to compute “simulated (or predicted)” CCPs, $\tilde{\pi}(a_t \vert s_t; \hat{\theta}_u)$.
A Minimum Distance Estimator (MDE) may then be used for inferring parameters that minimize the distance between the “simulated” and “directly estimated” choice probabilities (alternatively, for value functions):
where, $i$ denotes the iteration index and $\hat{\theta}_F$ represents first stage estimates. We follow bajari2007estimating and a related stream of work that uses an MDE estimator. In their study, hotz1994simulation used a Method of Simulated Moments estimator McFadden1989.
Each forward simulated path consists of a sequence of state-action pairs and, in the case of infinite time-horizon problems, has a length of $T_{\text{end}}$ beyond which, due to discounting and averaging, the simulation errors are insignificant (see e.g., bajari2007estimating, footnote 9, p.1343.). For each (forward) simulated path $k$ starting from an initial state-action pair $(s,a)$, the path-specific deterministic component of the choice-specific value function can then be computed after simulating the full path using the following expression:
where, the notation $^\prime, ^{\prime\prime}, ...$ represents the sequence of forward simulation-steps using $\hat{\mathit{p}}(\cdot; \hat{\theta}_F)$ and $\hat{\pi}(\cdot)$ following the initial $(s,a)$. The average value after computing the returns from $K$ paths can then be written as:
This CCS approach is “computationally lighter” than the NFXP as it skips the fixed-point iterations. A complementary discussion on value function computation and estimation steps in NFXP and CCS is provided in the online appendix. The main computational burden in the CCS approach arises from the forward simulations and the subsequent averaging operation. The pseudocodes for CCS, and our proposed RLMC-CCS and RLTD-CCS algorithms are provided in the online appendix.
First Insight: The first insight is that CCS “forward simulation” approach is a special case of RL “Monte Carlo” and “Temporal Difference” algorithms.
Second Insight: A second insight is that RL “Monte Carlo” and “Temporal Difference” algorithms compute the value functions for not only the initial state-action pair but also for the subsequently visited state-action pairs along the path.
To demonstrate this and also how choice-specific value functions can be “learned” and updated efficiently, we begin by showing how CCS can be re-interpreted in the RL framework.\footnote{A brief discussion on RL methods and their comparison with DDC modeling is provided in the online appendix.}
In CCS, $k=1,\ldots,K$ paths are simulated starting from $(s,a)$ and for each path a value function is computed and then averaged over the $K$ stored values. We can break the process of computing the overall mean into individual “update” steps:
where, $[\Lambda+1], [\Lambda], ...$ are the global computer times when the value from a new forward simulated path is calculated. Equivalently this entails weighting the difference between the most recent (at $[\Lambda+1]$) path-specific value ($\tilde{v}^K(s,a; \hat{\theta}_u^i, \hat{\theta}_F)[\Lambda+1]$) and the “old” (at $[\Lambda]$) mean value ($\bar{v}(s,a; \hat{\theta}_u^i, \hat{\theta}_F)[\Lambda]$), and then adding this “error” to the “old” mean value. Hence, we learn the “new” mean value as a forward simulated path value becomes available. This is more memory efficient as instead of storing $K$ values to compute the mean, only $2$ memory units are needed, one to maintain the mean value and the other to store the latest simulated path value. Thus, CCS can be re-interpreted in a step-wise learning formulation that is the underlying foundation of several RL algorithms.
The weight $1/K$ ensures that as $K \rightarrow \infty$, asymptotically the impact of the update error on the mean value becomes negligible. The step-wise updates can be formalized as the key learning equation in RL:
where, $\alpha(k)$ is called the learning parameter or the step-size parameter. For example, in Equation (ref), $\alpha(k) = 1/k$. This is also the fundamental building block of various machine learning methods like the stochastic gradient descent algorithm. The rationale for the learning equation, and the value of the learning parameter, comes from the convergence properties of iterative stochastic approximation processes that were first proposed by robbins1951stochastic and later extended by dvoretzky1956stochastic. Provided the learning parameter has the following two properties: (1) $\sum_k \alpha(k) = \infty$, and (2) $\sum_k \alpha^2(k) < \infty$, then the iterative update procedure converges with probability 1. Instead of a varying learning rate, we can have a small constant value ($\alpha \in (0,1)$) that ensures that all the update errors are given the same weight. While a dynamic learning parameter that diminishes with each time-step satisfies both the conditions, a constant parameter only strictly satisfies the first condition. This might result in a noisy convergence with the mean getting affected by every new update. However, a constant learning parameter has been shown to accelerate the rate of convergence. Using a constant learning parameter is particularly useful for non-stationary MDPs, as commonly assumed in RL applications sutton2018reinforcement.
To provide more intuition that CCS is a special case of RL Monte Carlo, consider an infinite-horizon MDP with two actions, $a_t = 0,1$, and finite states $s_t=1,\ldots,S$. A sample forward path starting from the initial state-action pair $(1,0)$ could be:
Here, the symbol $\dagger$ in the superscript represents the initial state-action pair while the numbers in the subscript indicate the simulation step. Using CCS the path-specific choice-specific value function can be computed using Equation (ref) as:
Second Insight (RLMC): This leads to our second insight, that our RLMC-CCS algorithm, premised on the RL Every-Visit MC algorithm, computes the value function for not only the initial state-action pair $(1,0)$ but also value functions for all subsequently visited state-action pairs along the path, $(2,0),(3,1),\ldots$. In RLMC-CCS, a forward path can be thought to be made up of several sub-paths (i.e., a total of $T_{\text{end}}$ sub-paths), each originating at different simulation-steps, $t=1,2,\ldots,T_{\text{end}}$. The discounted returns corresponding to each sub-path can be used to compute value functions. If a state-action pair is visited multiple times in a path, then the sub-path specific value functions from each of the sub-paths can be used to update the mean value multiple times. To illustrate with the sample path example above, it is seen that the path can be further sub-divided into possible sub-paths:
For each sub-path, an equivalent choice-specific value function can be computed:
The RLMC-CCS algorithms updates can be formally written as:
where, $\tilde{v}^{k,l}(s,a; \hat{\theta}_u^i,\hat{\theta}_F)$ is computed for the $l$\textsuperscript{th} sub-path (with its first state-action pair as $(s,a)$) derived from the $k$\textsuperscript{th} simulated path. The learning parameter $\alpha$ is $\frac{1}{\kappa+1}$ where $\kappa$ is the number of times $(s,a)$ has been visited across all the previous paths.
First Insight (RLMC): Hence, RLMC-CCS is equivalent to CCS if we only compute the value function corresponding to the initial starting state-action pair and ignore the other states that are visited within a path. Thus, CCS is a special case of RL Monte Carlo algorithms.
A practical challenge in applying these methods to infinite-horizon problems arises because the paths are terminated after a finite time step beyond which the simulation errors are insignificant. In the case of RLMC-CCS, for each forward simulated path, apart from the first sub-path, all the other associated sub-paths have decreasing lengths, leading to a larger bias compared to CCS when total number of simulated paths for each state-action pair is finite. In the case of finite-horizon problems, however, the RLMC-CCS algorithm will give an unbiased estimate as the paths need not be artificially terminated.
TD methods sutton1988learning have become foundational building blocks of RL. The core idea behind TD algorithms is to update the value of the current state-action pair by simulating one or a few steps ahead, rather than waiting for the entire path to complete before making updates. Our proposed RLTD-CCS algorithm is grounded on this fundamental principle.
To describe our approach, let us start by writing the choice-specific value function of the 1\textsuperscript{st} sub-path of the $k$\textsuperscript{th} full path in terms of the 2\textsuperscript{nd} sub-path:
The sequence of forward-simulated state-action pairs is given by $(s_1, a_1), (s_2, a_2), \ldots, (s_{T_{\text{end}}}, a_{T_{\text{end}}})$. To compute the value function for the 1\textsuperscript{st} sub-path, it is necessary to first compute the value of the 2\textsuperscript{nd} sub-path, which in turn requires accumulating the returns up to $T_{\text{end}}$. Instead of traversing till the end of the path to compute $\tilde{v}^{k,2}(s_2,a_2;\hat{\theta}_u^i, \hat{\theta}_F)$, we can replace it with the most recent value function update for the state-action pair $(s_2,a_2)$ and simplify the computation of $\tilde{v}^{k,1}(s_1,a_1;\hat{\theta}_u^i, \hat{\theta}_F)$:
In this approach, we are not explicitly accumulating the discounted rewards beyond the first simulation step but substituting it using the most recent value of $\tilde{v}(s_2,a_2;\hat{\theta}_u^i, \hat{\theta}_F)$ that was available at $[\Lambda]$ computer time. Using the general simulation step notation introduced in Equation (ref), and omitting the sub-path index in the superscript for brevity, the RLTD-CCS update error (similar to as described in Equation (ref)) can be expressed as follows:
Here, the subscript “1” in $\Delta$ indicates that the update error results from a one-step forward simulation. The corresponding “1-step” RLTD-CCS update is then obtained by substituting this error into the learning equation presented in Equation (ref):
Essentially, we need to simulate one step forward and then use the latest entry in a choice-specific value function look-up table for the next state-action pair. Multiple updates can be done while advancing through the simulation-steps. For a simulated path, we can either update the choice-specific value functions with the most recent look-up table entries (also called on-line learning in RL) or update the value functions in one-go after the path is terminated (also called batch learning). The pseudocode for the on-line version of “1-step” RLTD-CCS is provided in the online appendix.
In Equation (ref), if we set the learning rate $\alpha$ to 1 and replace the choice-specific value function $\tilde{v}(s^\prime, a^\prime; \hat{\theta}_u^i, \hat{\theta}_F)$ with the “expected” value function, the update closely resembles the value iteration step commonly used in the inner loop of the “polyalgorithm” within the NFXP approach.\footnote{Although not well recognized, rust1987optimal implemented a polyalgorithm that initially uses value iteration to converge toward the neighborhood of the fixed point, and then transitions to “policy iteration” to accelerate convergence particularly when the discount factor $\beta$ is close to one rust1994structural.} However, in the case of RLTD-CCS, we are instead using a value that has been approximated (“predicted” in RL vocabulary) using previous forward simulations. Such approximation methods are sometimes called stochastic Dynamic Programming in RL jaakkola1993convergence.
It might be useful to accumulate discounted rewards for a few steps before computing the update error. This is expected to reduce the bias, albeit at the cost of more processing time. This could be done by using the “n-step” RLTD-CCS algorithm. The n-step RLTD-CCS update error in terms of CCS formulation can be written as:
The n-step RLTD-CCS update rule then becomes:
First Insight (RLTD): Note RLMC-CCS is a special case of n-step RLTD-CCS algorithm when $n$ is extended to the full length of the simulated path and the learning rate $\alpha$ is set according to Equation (ref). Hence, CCS is a special case of RLTD-CCS.
Second Insight (RLTD): Similar to RLMC-CCS, in 1-step RLTD-CCS, value function updates are performed for all state-action pairs along a forward simulated path, except for the final state-action pair at the end of the path. For the n-step RLTD-CCS case, value function updates are applied to the first $T_{\text{end}} - n$ state-action pairs within the path.
We assess the performance of our proposed algorithms using two Monte Carlo studies: (1) a canonical machine replacement problem (the bajari2007estimating version of rust1987optimal), and (2) a consumer food choice model huang2015short.
In each period $t=1,2,...,T\leq \infty$, a decision-making superintendent observes a discrete state $s_t \in S = \left\lbrace1, 2, ..., N \right\rbrace$ of a machine. She also observes certain information about the machine (e.g., component failure, technician's report, batch, etc.) denoted by $\epsilon_{t}$ that is unobserved to the researcher. After observing $\left\lbrace s_{t}, \epsilon_{t} \right\rbrace$, she decides whether to replace the machine ($a_t=1$) or not ($a_t=0$). The superintendent has the following beliefs about the evolution of the machine's state conditional on the action taken:
Thus, when a machine is replaced its state is reset to 1 and the machine starts anew. This is referred to as the regenerative optimal stopping property of the stochastic process by rust1987optimal. Also, $N$ is the absorbing state in this specification, that is, once this state is reached it doesn't change until an action to replacement is taken.
Each action has an associated cost with the cost of replacement ($a_t=1$) assumed to be larger than that of maintenance ($a_t=0$), with the probability of failure increasing with usage. The current utility due to each action is given by:
where, $\theta_u = (\theta_{\text{MC}}, \theta_{\text{RC}})$, $c(\cdot)$ is some cost function for the observed state $s_t$ and maintenance cost parameter $\theta_{\text{MC}}$, and $\theta_{\text{RC}}$ is the replacement cost parameter.
The superintendent's objective is to minimize the present discounted value (PDV) of the stream of costs. The value function can be written as:
Writing in terms of the choice-specific value function, we get:
The deterministic component of the choice-specific function can then be written as:
Assuming Type-1 MEV distribution for the unobserved error terms, we can express the CCPs for each state-action pair in terms of choice-specific value functions as :
The estimation using the CCS and RL algorithms is done in two steps: (1) directly estimating the transition and choice probabilities from the (synthetic) data (which is the same for all algorithms), followed by (2) a value function computation (forward simulation) step which is embedded within an outer optimization loop to estimate the structural parameters $\theta_u$ using the MDE procedure.
In this Monte Carlo study, we used a small state-space machine replacement model with the maximum number of states, $N$, equal to 5 and two actions at the superintendent's disposal in every period, either maintenance or replacement of the machine. The size of the state-action space was $N \times |\mathcal{A}| = 10$. The state transitions followed the rule specified in Equation (ref). The costs associated with the actions were fixed to $\Bar{\theta}_u = (\Bar{\theta}_\text{MC}, \Bar{\theta}_{RC}) = (1, 4)$. The discount factor $\beta$ was assumed to be $.90$. The choice-specific value-functions, $v(s_t, a_t; \Bar{\theta}_{u})$, were computed using the fixed-point algorithm (the inner loop of NFXP rust1987optimal). The choice-specific value functions were then input into Equation (ref) to obtain the corresponding CCPs. Then using the transition probabilities and the computed CCPs, a synthetic dataset for 10,000 machines over a period of 100 weeks was generated through the Monte Carlo procedure.
Given the objective of accelerating value function computation and brevity of space, our discussion below is focused on the second step as that is the main difference between the CCS and RL-based estimation procedures. The outer parameter search loop was kept common across all the algorithms. For computing the choice-specific value functions, we pre-simulated a set of paths using the already estimated transition and choice probabilities. Each path was terminated after a period $T_{\text{end}}$. Since our RL-based algorithms can update the value functions intermittently, often every time a state-action pair is visited in a path, we wanted to test how the choice of $T_{\text{end}}$ affects the accuracy and speed of estimation. We varied $T_{\text{end}}$ from 4 to 200, and for each termination length, we pre-simulated 50 sets of 500 paths ($N_{\text{path}}$). All computations were performed on a university's High Performance Computing (HPC) cluster. For every individual estimation process, we allocated a single CPU core. We avoided parallelization to compare the default computation speeds. For each unique $T_{\text{end}}$ case, we estimated the model for all the 50 sets of paths separately. From these runs, we computed the mean, standard deviation, and root mean square error (RMSE) of the parameter estimates. The RMSE was calculated relative to the modeled structural utility, \( \bar{\theta}_u \). Additionally, we tracked the number of times the outer optimizer evaluated the distance (measured using the Euclidean norm or \( \ell^2 \)-norm) between the estimated and predicted CCPs (denoted as “\#fevals”) and recorded the final minimized distance at convergence.
As expected, the number of value functions updates during a single inner loop execution was much higher for the RL algorithms. For example, when $T_{\text{end}}$ was 50, for each guess $\hat{\theta}_u$, the value functions corresponding to each state-action pair were updated roughly 50 times in CCS. In 1-step RLTD-CCS, the choice-specific value function for the state-action pair (1,0) was updated more than 8000 times, for (1,1) more than 1200 times, and so on for each optimization loop (the online appendix provides more details).
The accuracy of the estimates and computation times are illustrated in Figure (ref). As is evident from the top row of the figure, for CCS, the RMSEs of the replacement cost parameter ($\hat{\theta}_\text{RC}$) improved if the simulated paths were longer, reaching the best possible values around a $T_{\text{end}}$ equal to 50. Simulating and using longer paths did not improve the accuracy of the estimates. Interestingly, the literature (e.g. hotz1994simulation), uses simulated path lengths with a $T_{\text{end}}$ equal to 50 which seems appropriate based on our findings.
In the case of RLMC-CCS, the estimation accuracy was limited. This is to be expected, as in the infinite-horizon case, sub-paths with decreasing termination lengths introduce larger errors, leading to less accurate estimates.
We provide results for 1-step and 3-step RLTD-CCS algorithms for three different values of step-size parameters ($\alpha$ equal to .1, .5, and .9). When $\alpha$ was equal to .5 and .9, the RMSE of the replacement cost parameter reached its best value even for much shorter paths ($T_{\text{end}}$ less than or equal to 10). This was a significant improvement over CCS. For the smaller step-size parameter case ($\alpha$ equal to .1), the RMSE improvement with the increasing length of the simulated paths was gradual. This is as expected as a smaller $\alpha$ meant a smaller weight was given to every update. However, this resulted in smoother convergence. On the other hand, when $\alpha$ was equal to .9, the RMSE increased for several path lengths, indicating that the estimation routine was not able to converge for these lengths. Using even larger step-size parameter values resulted in nosier and poorer convergence. The mid-range $\alpha$ of .5 performed the best so we make it the default for the rest of the analysis.
In the bottom row of the figure, we've plotted the total mean computation times. RLMC-CCS was the fastest for most $T_\text{end}$ cases. This was because the optimizer was not able to minimize the cost function beyond a few iterations (due to poor estimates) and exited faster than the other algorithms. For the smaller $T_{\text{end}}$ cases, the computation times for CCS, 1-step RLTD-CCS, and 3-step RLTD-CCS were similar. However, for the cases when the simulated paths were longer, CCS took longer time. Between 1-step and 3-step RLTD-CCS, 1-step RLTD-CCS was faster. This is as expected, as more processing steps are involved while computing the value functions in the inner loop of the 3-step version of RLTD-CCS.
Table (ref) includes the results for estimation runs when $T_{\text{end}}$ was equal to 10 and 50. For $T_{\text{end}}$ equal to 10, the RMSEs using CCS were one to two orders of magnitude worse compared to RLTD-CCS. Additionally, the minimized $\ell^2$-norm values indicate that the predicted CCPs using RLTD-CCS methods better matched the estimated CCPs with values roughly an order of magnitude smaller than those from CCS. This suggests a closer fit to the data.
This improvement is also reflected in the number of function evaluations required before the optimizer exits. On average, RLMC-CCS exits after approximately 60 iterations, CCS after 66, while RLTD-CCS variants typically run over 80 iterations, indicating a better convergence behavior.
For longer paths ($T_{\text{end}}$ equal to 50), the differences narrow significantly. CCS and RLTD-CCS algorithms achieve similar RMSEs, $\ell^2$-norms, and optimizer iteration counts. These results suggest that RLTD-CCS can achieve high estimation accuracy even with shorter simulation paths without sacrificing performance.
Comparing the computation times for CCS ($T_{\text{end}}$ equal to 50) and 1-step RLTD-CCS ($T_{\text{end}}$ less than or equal to 10), the 1-step RLTD-CCS reached the same accuracy compared to CCS but in 1/10\textsuperscript{th} time.
In sum, the RL based methods are as accurate as CCS but require shorter sample paths and less memory for the canonical machine replacement model. The next section investigates these properties for a large state-action space model.
To evaluate the performance of our algorithms in large state-action space problems, we introduce an infinite-horizon consumer food choice model that builds on huang2015short.\footnote{This problem is inspired by a separate project with an online recipe box retailer. For alternative models of demand for food products see e.g., dube2004multiple, allcott2019food..} A consumer, in every period $t = 1,2,...,T \leq \infty$, chooses between $M$ different mutually exclusive recipes from an online platform for home cooking. The action $a_{t} = m$ if the recipe $m$ is chosen from the online menu and zero if the individual foregoes ordering ($a_t = 0$).
Each recipe varies in the content of three attributes, salt ($SLT_m$), sugar ($SUG_m$), and saturated fat ($SAT_m$). For the outside option ($a_t=0$), these attributed are assumed zero. Based on previous consumption decisions the consumer accumulates stocks of these attributes given by ${SLT}_t^{\text{stock}}$, ${SUG}_t^{\text{stock}}$ and ${SAT}_t^{\text{stock}}$ respectively. We impose a maximum limit to the stock values ($STOCK_\text{max}$) of these attributes. The dynamics of the stock variables are given by:
where $\delta_0$ and $\delta_1$ denote the stock depreciation factors when the consumer forgoes ordering and when they order a recipe from the menu, respectively grossman1972health,benkard2000learning. In order to allow for a regenerative property to make it comparable to the machine replacement model as in rust1987optimal, we set $\delta_0 = 1$ (complete depreciation). This implies that that the stock levels reset to zero if the consumer skips ordering. We set $\delta_1 = 0$ (no depreciation), meaning that consumers fully carry over their previous stock levels when they place an order. In principle, as in grossman1972health, $\delta_{0}$ and $\delta_{1}$ can be equal taking a value between 0 and 1.
Given parameters $\theta_{SLT}, \theta_{SUG}, \theta_{SAT}$, the disutility, $r_{t}^{\text{stock}}$, from the accumulated stocks of these attributes is expressed as:
Each recipe is assigned a fixed parameter, $r_m^{\text{fixed}}$, capturing intrinsic recipe-specific preferences such as cuisine type, dish category, and other non-nutritional characteristics. We assume these parameters are known to the researcher. Here we focus solely on the nutritional attributes of recipes.
To model variety-seeking behavior, where consumers derive disutility from repeated selections of the same recipe across consecutive periods, we introduce the state variable $h_t^{\text{variety}}$. Its evolution is defined by:
where, $H_{\text{max}}$ is the maximum level of accumulated disutility from repeated choices. Given a parameter $\theta_{\text{variety}}$, the disutility from lack of variety at time $t$ is specified as:
Foregoing ordering leads to a disutility which is assumed to be fixed at $-\theta_{\text{skip}}$. This could be imagined as time spent in arranging ingredients and limited preference for self-assembled and cooked food, etc. For simplicity, skipping consumption resets the stock variables.
The single-period utility received in period $t$ is given by:
where, $\epsilon_{t}(a_t)$ is the random utility component (unoberved by the researcher) associated with the action $a_t$, and $\theta_u = (\theta_{SLT}, \theta_{SUG}, \theta_{SAT}, \theta_{\text{variety}}, \theta_{\text{skip}})$ are the structural utility parameters of interest. The consumer's objective is to maximize the PDV of the stream of utility.
The observable state variables for the consumer's problem are:
The deterministic component of the choice-specific function can then be written as:
Hence, the choice-probability for the selecting the $m$\textsuperscript{th} recipe in period $t$ is:
The synthetic data generation procedure for the food choice model is provided in the online appendix. We estimated eight versions of the food choice model, with state-action space ranging from 3,891 to 5.77 million (see Table (ref) for details on each version). For each version of the food choice model, we first generated 50 sets of forward simulation paths, with each set containing paths of similar lengths ($T_{\text{end}}$ equal to 5, 10 and 50). For each version of the model, the number of forward simulated paths was roughly kept 20 to 25 times the size of the state-action space. We randomized the starting states of each path by drawing with replacement from the observed states seen in the synthetic dataset. In the second stage, we estimated the structural parameters using CCS and 1-step RLTD-CCS algorithm. We also estimated a few smaller state-action space food choice models using 3-step RLTD-CCS. However, as estimating these took longer than the 1-step RLTD-CCS without substantial improvement in accuracy, we have not included these results here. For RLTD-CCS, $\alpha$ was fixed to .5.
The estimation results are provided in Table (ref)--(ref). When very short paths were used ($T_{\text{end}}$ equal to 5), 1-step RLTD-CCS achieved substantially better performance than CCS across most models. Specifically, RLTD-CCS estimated the utility parameter $\theta_{u}$ with RMSE values that were three to four orders of magnitude smaller than those obtained using CCS. The $\ell^2$-norm values exhibit a similar pattern, where the minimized values using CCS were approximately three orders of magnitude larger than those from RLTD-CCS. This indicates a significantly poorer fit to the observed conditional choice probabilities. Additionally, the number of function evaluations required for convergence suggests that the optimizer typically performs about two and a half times more iterations under RLTD-CCS than under CCS, reflecting the optimizer's ability to more effectively minimize the objective.
When long paths were used ($T_{\text{end}}$ equal to 50), CCS achieved estimation accuracy for the utility parameters that was roughly comparable to RLTD-CCS (which remained about the same for all the three path lengths). However, the corresponding $\ell^2$-norm values remained about an order of magnitude larger, which suggests that CCS may require even longer forward-simulated paths to reduce estimation bias. This interpretation is further supported by the slightly lower number of function evaluations observed for CCS, which indicates that the optimization routine often terminates earlier before reaching a better minimum.
These results are consistent with observations from the machine replacement model, where achieving comparable RMSE performance with CCS required forward-simulated paths that were approximately ten times longer than those used by RLTD-CCS.
Generating and storing longer paths is both time consuming and memory intensive. For example, in the case of the smallest state-space model (Model: `Case 1a' with a state-action space size of 3,891), generating a set of $25 \times 3891$ paths with a $T_{\text{end}}$ equal to 5 took around 2 seconds and a memory space of roughly 385 kilobytes was required to store the paths. On the other hand, generating paths with a $T_{\text{end}}$ equal to 50 roughly took 22 seconds and the paths occupied about 4.2 megabytes of memory space. While these numbers might look trivial in the case of the small state-space model, when the state-space increased the speed and memory problem became exponentially challenging. For example, in the case of the largest state-space models, the path generation process took several hours and had to be done on multiple computing cores to avoid runtime memory issues. Considering memory requirements, for the model with the state-space size of 1.14 million, paths with a $T_{\text{end}}$ equal to 5 required almost 310 megabytes of memory, while paths with a $T_{\text{end}}$ equal to 50 required almost 3.1 gigabytes of memory. The memory figures quoted here are when the path data was stored in the most compressed, MATLAB compatible `.mat' format. Storing data as in a more commonly used `comma-separated value' or `.csv' format takes about 3.5 to 4 times more memory.
CCS was generally faster than the 1-step RLTD-CCS for the shorter path lengths. However, this was at the expense of a poorer estimation accuracy. In a few cases, CCS even estimated the wrong sign for the $\theta_{\text{variety}}$ parameter. The mean of the estimated $\theta_{\text{variety}}$ parameter was -.0002 and -.0455 for models with state-action space size of 30,001 (Table (ref)) and 62,211 (Table (ref)) respectively. On the other hand, using 1-step RLTD-CCS, the mean of the estimates were +.1000 and +.0999, which were extremely close to the modeled value ($\bar{\theta}_{\text{variety}}$) of +.1.
In the case of the largest state-action space size model (5.77 million states, Table (ref)), the estimation routines with longer paths ($T_{\text{end}}$ equal to 50) were terminated by the HPC scheduler as these overran the allowed 24 hours limit. While these could be estimated in principle on a different cluster/PC where the time limits are more relaxed, it provided a good indication of the practical limits. As we were able to estimate the same model comfortably within the time limit using 1-step RLTD-CCS on shorter paths, the RL algorithm provide a higher ceiling on the state-action space size of the models that could be easily estimated.
Comparing the mean estimation computation times for CCS (when $T_{\text{end}}$ was equal to 50) with 1-step RLTD-CCS (when $T_{\text{end}}$ was equal to 5), RLTD-CCS was found to be 6 to 14 times faster than the CCS algorithm across the eight models. The computation times for both the algorithms are graphically illustrated in Figure (ref). The much steeper slope of CCS compared to RLTD-CCS underscores the latter's superior computational performance in estimating larger state-action space models in a fraction of the time without using large amounts of memory.
We also found that RLTD-CCS was less sensitive to the discount factor, $\beta$. As $\beta$ increases, longer paths need to be simulated so that the impact of $\beta^{T_{\text{end}}}$ on the computed value functions becomes smaller than the simulation errors observed after averaging all the paths originating from a state. In RLTD-CCS, since the value functions are updated by looking one/$n$-steps ahead and as long as many iterative updates for all the states are performed, the sensitivity to $\beta$ is expected to be smaller than CCS. To confirm this, we estimated the smallest state-action space food choice model (3,891 states) for a $\beta$ of .995 and $T_{\text{end}}$ equal to 5, 10, and 500.
The estimation results are presented in Table (ref). The impact of a higher discount factor on the estimates from both the CCS and RLTD-CCS algorithms is clearly evident when compared to the results obtained with $\beta = .90$ (Table (ref)). The estimates for all the path lengths for both the algorithms were a little worse for the higher $\beta$ value. However, even at this higher discount factor, the 1-step RLTD-CCS algorithm achieved better RMSE performance for paths with $T_{\text{end}}$ equal to 10 than CCS achieves for paths that are 500 periods long. While the RMSE using CCS improves gradually as the path length increases, the RLTD-CCS algorithm achieves significant improvement when increasing the path length from 5 to 10, with only gradual gains beyond that point.
In addition, the memory requirements for storing paths of 500 periods were approximately 50 times greater than those for 10-period paths. These findings highlight that RLTD-CCS is less sensitive to $\beta$.
Overall, the results demonstrate that 1-step RLTD-CCS achieves comparable estimation accuracy while requiring shorter path lengths than CCS, resulting in significantly lower computation times even as the state-action space grows or the discount factor approaches one. These computational advantages suggest that RLTD-CCS can effectively extend the practical limits of “forward simulation” CCS estimation of DDC models to larger and more high-dimensional decision problems (e.g., incorporating more nutritional and non-nutritional attributes of recipes in the food choice model that could lead to more nuanced insights and granular counterfactual policy analysis).
As DDC models become even more high-dimensional, there is a pressing need for estimation methods that handle large state-action spaces efficiently. Simulations-based two-step CCS-like estimators, that are based on the CCP representation of the choice value functions, offer computational advantages over traditional full-solution approaches like NFXP. In this paper, we introduced a set of two-step forward simulation estimation algorithms, RLMC-CCS and RLTD-CCS that are inspired by the RL literature. These algorithms exploit visits to multiple state-action pairs during forward simulations to improve the efficiency of value function computation, addressing limitations of CCS. We showed that CCS is a special case of the RLMC-CCS algorithm and the CCS value function updates can be represented a geometric sums of RLTD-CCS updates. We provided Monte Carlo evidence to show the comparative advantage of the RL algorithms over CCS. Using a small state-space machine replacement model and large state-space food choice models (up to 5.77 million states), we showed that RLTD-CCS algorithms only need short simulation paths to reach the same level of estimation accuracy that was obtained from CCS on longer simulation paths. Using shorter paths for estimations helped speed up the computation by up to 14 times. We showed that the RL algorithms are less sensitive to discount factor than CCS. In one case, when when the discount factor was set to .995, RLTD-CCS was able to get accurate estimates 70 times faster than CCS.
Our work has implications for researchers in marketing, economics and computer science, as well as policy-makers, and practitioners. For researchers, our work provides computationally-light CCS-like estimation approaches for estimating large state-action space dynamic discrete-choice models. For practitioners, particularly who are working for eCommerce platforms where the state-action space within which consumers navigate is naturally large, we provide computationally faster methods to recovering consumer preferences and for carrying out counter-factual experiments. When the state-action space becomes extremely large (from millions to several billions), the step of pre-simulating and storing forward paths will quickly become impractical. In these scenarios, using a functional approximation strategy (both polynomial approximation and Deep Learning) might be better suited. Combining our proposed method with these functional approximation approaches may also be a worthwhile avenue to explore to seek further computational gains. Although, not the focus of our paper, in future it may be worthwhile to extend these algorithms to allow for unobserved heterogeneity. Another potential natural extension of our work is in the estimation of multi-agent DDC models, i.e., dynamic games.
In summary, we believe our extension of the CCS method using the RL algorithms is a promising step in overcoming computational challenges to estimating high-dimensional DDC models in a MDP framework, especially when the state-action space starts to become large. Our work draws on the synergy between the DDC and RL literatures. We hope this will help bridge the work in these two domains to help researchers combine their knowledge in advancing what are very similar research agendas.