Year: 2019

Abstract:
Discrete choice models with unobserved heterogeneity are commonly used Econometric models for dynamic Economic behavior which have been adopted in practice to predict behavior of individuals and firms from schooling and job choices to strategic decisions in market competition. These models feature optimizing agents who choose among a finite set of options in a sequence of periods and receive choice-specific payoffs that depend on both variables that are observed by the agent and recorded in the data and variables that are only observed by the agent but not recorded in the data. Existing work in Econometrics assumes that optimizing agents are fully rational and requires finding a functional fixed point to find the optimal policy. We show that in an important class of discrete choice models the value function is globally concave in the policy. That means that simple algorithms that do not require fixed point computation, such as the policy gradient algorithm, globally converge to the optimal policy. This finding can both be used to relax behavioral assumption regarding the optimizing agents and to facilitate Econometric analysis of dynamic behavior. In particular, we demonstrate significant computational advantages in using a simple implementation policy gradient algorithm over existing “nested fixed point” algorithms used in Econometrics.

text: Discrete choice models with unobserved heterogeneity are commonly used Econometric models for dynamic Economic behavior which have been adopted in practice to predict behavior of individuals and firms from schooling and job choices to strategic decisions in market competition. These models feature optimizing agents who choose among a finite set of options in a sequence of periods and receive choice-specific payoffs that depend on both variables that are observed by the agent and recorded in the data and variables that are only observed by the agent but not recorded in the data. Existing work in Econometrics assumes that optimizing agents are fully rational and requires finding a functional fixed point to find the optimal policy. We show that in an important class of discrete choice models the value function is globally concave in the policy. That means that simple algorithms that do not require fixed point computation, such as the policy gradient algorithm, globally converge to the optimal policy. This finding can both be used to relax behavioral assumption regarding the optimizing agents and to facilitate Econometric analysis of dynamic behavior. In particular, we demonstrate significant computational advantages in using a simple implementation policy gradient algorithm over existing “nested fixed point” algorithms used in Econometrics.

heading: 1 INTRODUCTION
text: Dynamic discrete choice model with unobserved heterogeneity is, arguably, the most popular model that is currently used for Econometric analysis of dynamic behavior of individuals and firms in Economics and Marketing (e.g. see surveys in Eckstein and Wolpin (1989), Dubé et al. (2002) Abbring and Heckman (2007), Aguirregabiria and Mira (2010)). Even most recent Econometric papers on single-agent dynamic decision-making use this setup to showcase their results (e.g. Arcidiacono and Miller, 2011; Aguirregabiria and Magesan, 2016; Müller and Reich, 2018).In this model, pioneered in Rust (1987), the agent chooses between a discrete set of options (typically 2) in a sequence of discrete time periods to maximize the expected cumulative discounted payoff. The reward in each period is a function of the state variable which follows a Markov process and is observed in the data and also a function of an idiosyncratic random variable that is only observed by the agent but is not reported in the data. The unobserved idiosyncratic component is designed to reflect heterogeneity of agents that may value the same choice differently.
Despite significant empirical success in prediction of dynamic economic behavior under uncertainty, dynamic discrete choice models frequently lead to seemingly unrealistic optimization problems that economic agents need to solve. For instance, Hendel and Nevo (2006) features an elaborate functional fixed point problem with constraints, which is computationally intensive, especially in continuous state spaces, for consumers to buy laundry detergent in the supermarket. Common approach for this functional fixed point problem is value function iteration (See Section 2.3 for more discussion).
At the same time, rich literature on Markov Decision Processes (cf. Sutton and Barto, 2018) have developed several effective optimization algorithms, such as the policy gradient algorithm and its variants, that do not require solving for a functional fixed point. However, the drawback of the policy gradient is that the value function in a generic Markov Decision problem is not concave in the policy. This means that gradient-based algorithms have no guarantees for global convergence for a generic MDP. While for some specific and simple models where closed-form characterizations exist, the
convergence results are shown by model-specific technique which is hard to generalize (e.g. Fazel et al., 2018, for linear quadratic regulator).
In this paper our main goal is to resolve the dichotomy in empirical social science literature that the rationality of consumers requires for them to be able to solve the functional fixed point problem which is computationally intensive. Our main theoretic contribution is the proof that, in the class of dynamic discrete choice models with unobserved heterogeneity, the value function of the optimizing agent is globally concave in the policy. This implies that a large set of policy gradient algorithms that have a modest computational power requirement for the optimizing agents have a fast convergence guarantee in our considered class of dynamic discrete choice models. The importance of this result is twofold.
First, it gives a promise that seemingly complicated dynamic optimization problems faced by consumers can be solved by relatively simple algorithms that do not require fixed point computation or functional optimization. This means that the policy gradient-style methods have an important behavioral interpretation. As a result, consumer behavior following policy gradient can serve as a behavioral assumption for estimating consumer preferences from data which is more natural for consumer choice settings than other assumptions that have been used in the past for estimation of preferences (e.g. -regret learning in Nekipelov et al. (2015)). Second, more importantly, our result showing fast convergence of the policy gradient algorithm makes it an attractive alternative to the search for the functional fixed point in this class of problems. While the goal of the Econometric analysis of the data from dynamically optimizing consumers is to estimate consumer preferences by maximizing the likelihood function, it requires to sequentially solve the dynamic optimization problem for each value of utility parameters along the parameter search path. Existing work in Economics prescribes to use fixed point iterations for the value function to solve the dynamic optimization problem (see Rust (1987), Aguirregabiria and Mira (2007)). The replacement of the fixed point iterations with the policy gradient method significantly speeds up the maximization of the likelihood function. This makes the policy gradient algorithm our recommended approach for use in Econometric analysis, and establishes practical relevance of many newer reinforcement learning algorithms from behavioral perspective for social sciences.

heading: 2 PRELIMINARIES
text: In this section, we introduce the concepts of the Markov decision process (MDP) with choice-specific payoff heterogeneity, the conditional choice probability (CCP) representation and the policy gradient algorithm.

heading: 2.1 MARKOV DECISION PROCESS
text: A discrete-time Markov decision process (MDP) with choice-specific heterogeneity is defined as a 5-tuple 〈S,A, r, ,P, β〉, where S is compact convex state space with diam(S) ≤ S̄ <∞, A is the set of actions, r : S×A → R+ is the reward function, such that r(s, a) is the immediate non-negative reward for the state-action pair (s, a), are independent random variables, P is a Markov transition model where where p(s′|s, a) defines the transition density between state s and s′ under action a, and β ∈ [0, 1) is the discount factor for future payoff. We assume that random variables are observed by the optimizing agent and not recorded in the data. These variables reflect idiosyncratic differences in preferences of different optimizing agents over choices. In the following discussion we refer to these variables as “random choice-specific shocks."
In each period t = 1, 2, . . . ,∞, the nature realizes the current state st based on the Markov transition P given the state-action pair (st−1, at−1) in the previous period t− 1, and the choice-specific shocks t = { t,a}a∈A drawn i.i.d. from distribution . The optimizing agent chooses an action a ∈ A, and her current period payoff is sum of the immediate reward and the choice-specific shock, i.e., r(s, a) + t,a. Given initial state s1, the agent’s long-term payoff is E 1,s2, 2,... [∑∞ t=1 β t−1r(st, at) + t,at ] . This expression makes it clear that random shocks play a crucial role in this model by allowing us to define the ex ante value function of the optimizing agent which reflects the expected reward from agent’s choices before the agent observes realization of t. When the distribution of shocks is sufficiently smooth (differentiable), the corresponding ex ante value function is smooth (differentiable)
as well. This allows us to characterize the impact of agent’s policy on the expected value by considering functional derivatives of the value function with respect to the policy.
In the remainder of the paper, we rely on the following assumptions. Assumption 2.1. The state space S is compact in R and the action spaceA is binary, i.e.,A = {0, 1}. Assumption 2.2. For all states s, the immediate reward r(s, 0) for the state-action pair (s, 0) is zero i.e., r(s, 0) = 0, and the immediate reward r(s, 1) for the state-action pair (s, 1) is bounded between [Rmin, Rmax]. Assumption 2.3. Choice-specific shocks are Type I Extreme Value random variables with location parameter 0 (cf. Hotz and Miller, 1993) which are independent over choices and time periods.
Assumption 2.1, 2.2, 2.3 are present in most of the papers on dynamic decision-making in economics, marketing and finance, (e.g. Dubé et al., 2002; Aguirregabiria and Mira, 2010; Arcidiacono and Miller, 2011; Aguirregabiria and Magesan, 2016; Müller and Reich, 2018)
The policy and the value function A stationary Markov policy is a function σ : S × RA → A which maps the current state s and choice-specific shock to an action. In our further discussion we will show that there is a natural more restricted definition of the set of all feasible policies in this model.
Given any stationary Markov policy σ, the value function Vσ : S → R is a mapping from the initial state to the long-term payoff under policy σ, i.e.,
Vσ(s1) = E 1,s2, 2,... [ ∞∑ t=1 βt−1 { r(st, σ(st, t)) + t,σ(st, t) }] .
Since the reward is non-negative and bounded, and the discount β ∈ [0, 1), value function Vσ is well-defined and the optimal policy σ̃ (i.e., Vσ̃(s) ≥ Vσ(s) for all policies σ and states s) exists. Furthermore, the following Bellman equation holds
Vσ(s) = E [ r(s, σ(s, )) + σ(s, ) + β Es′ [Vσ(s′)|s, σ(s, )] ] for all policies σ (1)

heading: 2.2 CONDITIONAL CHOICE PROBABILITY REPRESENTATION
text: Based on the Bellman equation (1) evaluated at the optimal policy, the optimal Conditional Choice Probability δ̃(a|s) (i.e., the probability of choosing action a given state s in the optimal policy σ̃) can be defined as
δ̃(a|s) = E [1{r(s, a) + a + β Es′ [Vσ̃(s′)|s, a] ≥ r(s, a′) + a′ + β Es′ [Vσ̃(s′)|s, a′] , ∀a′}] The optimal policy σ̃ can, therefore, be equivalently characterized by threshold function π̃(s, a) = r(s, a) + β Es′ [Vσ̃(s′)|s, a], such that the optimizing agent chooses action a† which maximizes the sum of the threshold and the choice-specific shock, i.e., a† = argmaxa{π̃(s, a) + a}. Similarly, all non-optimal policies can be characterized by the corresponding threshold functions denoted π. Under Assumption 2.3 the conditional choice probability δ can be explicitly expressed in terms of the respective threshold π as (cf. Rust, 1996)
δ(a|s) = exp(π(s, a)) /(∑ a′∈A exp(π(s, a ′)) ) .
We note that this expression induces a one-to-one mapping from the thresholds to the conditional choice probabilities. Therefore, all policies are fully characterized by their respective conditional choice probabilities. For notational simplicity, since we consider the binary action space A = {0, 1}, and the reward r(s, 0) is normalized to 0 we denote the immediate reward r(s, 1) as r(s); denote the conditional choice probability δ(0|s) as δ(s); and denote π(s, 1) as π(s). In the subsequent discussion given that the characterization of policy σ via its threshold is equivalent to its characterization by conditional choice probability δ, we interchangeably refer to δ as the “policy." Then we rewrite the Bellman equation for a given policy δ as
Vδ(s) =(1− δ(s)) r(s)− δ(s) log (δ(s)) − (1− δ(s)) log(1− δ(s)) + β E ,s′ [ Vδ(s)(s ′) ∣∣∣s] (2)
Now we make two additional assumptions that are compatible with standard assumptions in the Econometrics literature.
Assumption 2.4. For all states s ∈ S, the conditional distribution of the next period Markov state p(·|s, 1) first-order stochastically dominates distribution p(·|s, 0), i.e., for all ŝ ∈ S, Prs′ [s′ ≤ ŝ|s, 1] ≤ Prs′ [s′ ≤ ŝ|s, 0]. Assumption 2.5. Under the optimal policy δ̃, the value function is non-decreasing in states, i.e., Vδ̃(s) ≤ Vδ̃(s′) for all s, s′ ∈ S s.t. s < s′.
Consider a myopic policy δ̄(s) = (exp(r(s)) + 1)−1 which uses threshold π̄(s) = r(s). This policy corresponds to agent optimizing the immediate reward without considering how current actions impact future rewards. Under Assumption 2.4 and Assumption 2.5, the threshold for optimal policy is at least the threshold of myopic policy, i.e., π̃(s) ≥ π̄(s). Hence, Lemma 2.1 holds. Lemma 2.1. The optimal policy δ̃ chooses action 0 with weakly lower probability than the myopic policy δ̄ in all states s ∈ S, i.e., δ̃(s) ≤ δ̄(s).

heading: 2.3 MDP IN ECONOMICS AND POLICY GRADIENT
text: Our motivation in this paper comes from empirical work in Economics and Marketing where optimizing agents are consumers or small firms who make dynamic decisions while observing the current state s and the reward r(s, a) for their choice a. These agents often have limited computational power making it difficult for them to solve the Bellman equation to find the optimal policy. They also may have only sample access to the distribution of Markov transition which further complicates the computation of the optimal policy. In this context we contrast the value function iteration method which is based on solving the fixed point problem induced by the Bellman equation and the policy gradient method.
Value function iteration In the value function iterations, e.g., discussed in Jaksch et al. (2010); Haskell et al. (2016), the exact expectation in the Bellman equation (1) is replaced by an empirical estimate and then functional iteration uses the empirical Bellman equation to find the fixed point, i.e., the optimal policy. Under certain assumptions on MDPs, one can establish convergence guarantees for the value function iterations, e.g., Jaksch et al. (2010); Haskell et al. (2016). However, to run these iterations may require significant computation power which may not be practical when optimizing agents are consumers or small firms.
Policy gradient In contrast to value function iterations, policy gradient algorithm and its variations are model-free sample-based methods. At a high level, policy gradient parametrizes policies {δθ}θ∈Θ by θ ∈ Θ and computes the gradient of the value function with respect to the current policy δθ and update the policy in the direction of the gradient, i.e., θ ← θ + α∇θVδθ . Though the individuals considered in the Economic MDP models may not compute the exact gradient with respect to a policy due to having only sample access to the Markov transition, previous work has provided approaches to produce an unbiased estimator of the gradient. For example, REINFORCE (Williams, 1992) updates the policy by θ ← θ + αR∇θ log(δθ(a|s)) where R is the long-term payoff on path. Notice that this updating rule is simple comparing with value function iteration. The caveat of the policy gradient approach is the lack of its global convergence guarantee for a generic MDP. In this paper we show that such guarantee can be provided for the specific class of MDPs that we consider.

heading: 3 WARM-UP: LOCAL CONCAVITY OF THE VALUE FUNCTION AT THE OPTIMAL POLICY
text: To understand the convergence of the policy gradient, in this section we introduce our main technique and show that the concavity of the value function with respect to policies is satisfied in a fixed neighborhood around the optimal policy. We rely on the special structure of the value function induced by random shocks which essentially “smooth it" making it differentiable. We then use Bellman equation (7) to compute strong Fréchet functional derivatives of the value functions and argue that the respective second derivative is negative at the optimal policy. We use this approach in Section 4 to show the global concavity of the value function with respect to policies.
By ∆ we denote the convex compact set that contains all continuous functions δ : S → [0, 1] such that 0 ≤ δ(·) ≤ δ̄(·). The Bellman equation (7) defines the functional Vδ(·). Recall that Fréchet derivative of functional Vδ(·), which maps bounded linear space ∆ into the space of all continuous bounded functions of s, at a given δ(·) is a bounded linear functional DVδ(·) such that for all continuous h(·) with ‖h‖2 ≤ H̄: Vδ+h(·)− Vδ(·) = DVδ(·)h(·) + o(‖h‖2). When functional DVδ(·) is also Fréchet differentiable, we refer to its Fréchet derivative as the second Fréchet derivative of functional Vδ(·) and denote it D2Vδ(·). Theorem 3.1. Value function Vδ is twice Freéchet differentiable with respect to δ at the choice probability δ̃ corresponding to optimal policy and its Fréchet derivative is negative at δ̃ in all states s, i.e., D2Vδ̃(s) ≤ 0.
We sketch the proof idea of Theorem 3.1 and defer its formal proof to Appendix A. Start with the Bellman equation (7) of the value function, the Fréchet derivative of the value function is the fixed point of the following Bellman equation
DVδ(s) = (log(1− δ(s))− log(δ(s))− r(s)) + β (Es′ [Vδ(s′)|s, 0]− Es′ [Vδ(s′)|s, 1]) + β E ,s′ [DVδ(s′)|s] ,
(3)
and
D2Vδ(s) = − 1
δ(s)(1− δ(s)) − 2β(Es′ [DVδ(s′)|s, 1]− Es′ [DVδ(s′)|s, 0]) + β Es′ [ D2Vδ(s ′)|s ] .
(4)
A necessary condition for its optimum yielding δ̃ is DVδ̃(s) = 0 for all states s. As a result, equation (9) implies that its second Fréchet derivative is negative for all states, i.e.,D2Vδ̃(s) ≤ 0.
The Bellman equation (9) of the second Fréchet derivative suggests that D2Vδ(s) ≤ 0 for all states s if
1
δ(s)(1− δ(s)) + 2β(Es′ [DVδ(s′)|s, 1]− Es′ [DVδ(s′)|s, 0]) ≥ 0 (5)
The first term in the inequality (5) is always positive for all policies in ∆, but the second term can be arbitrary small. In the next section, we will introduce a nature smoothness assumption on MDP (i.e., Lipschitz MDP) and show that the local concavity can be extended to global concavity, which implies that the policy gradient algorithm for our problem converges globally under this assumption.

heading: 4 GLOBAL CONCAVITY OF THE VALUE FUNCTION
text: In this section, we introduce the notion of the Lipschitz Markov decision process, and Lipschitz policy space. We then restrict our attention to this subclass of MDPs. Our main result shows the optimal policy belongs to the Lipschitz policy space and the policy gradient globally converges in that space. We defer all the proofs of the results in this section to Appendix B.

heading: 4.1 LIPSCHITZ MARKOV DECISION PROCESS
text: Lipschitz Markov decision process has the property that for two state-action pairs that are close with respect to Euclidean metric in S, their immediate rewards r and Markovian transition P should be close with respect to the Kantorovich or L1-Wasserstein metric. Kantorovich metric is, arguable, the most common metric used used in the analysis of MDPs (cf. Hinderer, 2005; Rachelson and Lagoudakis, 2010; Pirotta et al., 2015). Definition 4.1 (Kantorovich metric). For any two probability measures p, q, the Kantorovich metric between them is
K(p, q) = sup f {∣∣∣∣∫ X fd(p− q) ∣∣∣∣ : f is 1-Lipschitz continuous}
Definition 4.2 (Lipschitz MDP). A Markov decision process is (Lr, Lp)-Lipschitz if ∀s, s′ ∈ S |r(s)− r(s′)| ≤ Lr |s− s′| ∀s, s′ ∈ S, a, a′ ∈ A K(p(·|s, a), p(·|s′, a′)) ≤ Lp (|s− s′|+ |a− a′|)

heading: 4.2 CHARACTERIZATION OF THE OPTIMAL POLICY
text: Our result in Section 3, demonstrates that the second Fréchet derivative of Vδ with respect to δ is negative for a given policy δ when inequality (5) holds. To bound the second term of (5) from below, i.e., Es′ [DVδ(s′)|s, 0]− Es′ [DVδ(s′)|s, 1], it is sufficient to show that Fréchet derivative DVδ(·) is Lipschitz-continuous. Even though we already assume that the Markov transition is Lipschitz, it is still possible that DVδ is not Lipschitz: Bellman equation (8) for DVδ depends on policy δ(s) via log(1− δ(s))− log(δ(s)), which can be non-Lipschitz in state s for general policies δ. Therefore, to guarantee Lipschitzness of the Fréchet derivative of the value function it is necessary to restrict attention to the space of Lipschitz policies. In this subsection, we show that this restriction is meaningful since the optimal policy is Lipschitz. Theorem 4.1. Given (Lr, Lp)-Lipschitz MDP, the optimal policy δ̃ satisfies∣∣∣∣∣log ( 1− δ̃(s) δ̃(s) ) − log ( 1− δ̃(s†) δ̃(s†) )∣∣∣∣∣ ≤ ( Lr + 2βRmaxLp 1− β
) ∣∣s− s†∣∣ for all state s, s† ∈ S where Rmax = maxs∈S r(s) is the maximum of the immediate reward r over S.

heading: 4.3 CONCAVITY OF THE VALUE FUNCTION WITH RESPECT TO LIPSCHITZ POLICIES
text: In this subsection, we present our main result showing the global concavity of the value function for our specific class of Lipschitz MDPs with unobserved heterogeneity over the space of Lipschitz policies. Definition 4.3. Given (Lr, Lp)-Lipschitz MDP, define its Lipschitz policy space ∆ as
∆ = {δ :δ(s) ≤ δ̄(s) ∀s ∈ S and∣∣∣∣log(1− δ(s)δ(s) ) − log ( 1− δ(s†) δ(s†) )∣∣∣∣ ≤ (Lr + 2βRmaxLp1− β ) ∣∣s− s†∣∣ ∀s, s† ∈ S} ,
where δ̄ is the myopic policy.
Theorem 4.1 and Lemma 2.1 imply that the optimal policy δ̃ lies in this Lipschitz policy space ∆ for any Lipschitz MDP. Definition 4.4 (Condition for global convergence). We say that (Lr, Lp)-Lipschitz MDP satisfies the sufficient condition for global convergence if
2βLp < 1 and 2βLp
1− 2βLp
( 2Lr +
4βRmaxLp 1− β
) ≤ ( exp(Rmin) + 1 )2
exp(Rmin) . (6)
Theorem 4.2. Given (Lr, Lp)-Lipschitz MDP which satisfies the condition for global convergence (6), value function Vδ is concave with respect to policy δ in the Lipschitz policy space ∆, i.e., D2Vδ(s) ≤ 0 for all s ∈ S, δ ∈ ∆.

heading: 4.4 THE RATE OF GLOBAL CONVERGENCE OF THE POLICY GRADIENT ALGORITHM
text: In this subsection, we establish the rate of global convergence a simple version of the policy gradient algorithm assuming oracle access to the Fréchet derivative of the value function. While this analysis provides only a theoretical guarantee, as discussed in Section 2.3, in practice the individuals are able to produce an unbiased estimator of the exact gradient. As a result, the practical application of the policy gradient algorithm would only need to adjust for the impact of stochastic noise in the estimator.
Since we assume that individuals know the immediate reward function r, the algorithm can be initialized at the myopic policy δ̄ with threshold π̄(s) = r(s), which is in the Lipschitz policy space ∆. From Lemma 2.1 it follows that the myopic policy is pointwise in S greater than the optimal policy, i.e., δ̄(s) ≤ δ̃(s). Consider policy δ with threshold π(s) = r(s) + β1−βRmax − β 2Rmin. Note that Bellman equation (7) implies that V (s) is between Rmin2 and Rmax 1−β for all states s. Thus, policy δ pointwise bounds the optimal policy δ̃ from below, i.e., δ(s) ≤ δ̃(s). Our convergence rate result applies to the policy gradient within the bounded Lipschitz policy set ∆̂.
Definition 4.5. Given (Lr, Lp)-Lipschitz MDP, define its bounded Lipschitz policy space ∆̂ as ∆̂ = {δ :δ(s) ≤ δ(s) ≤ δ̄(s) ∀s ∈ S and∣∣∣∣log(1− δ(s)δ(s) ) − log ( 1− δ(s†) δ(s†) )∣∣∣∣ ≤ (Lr + 2βRmaxLp1− β ) ∣∣s− s†∣∣ ∀s, s† ∈ S} .
For simplicity of notation, we introduce constants m and M which only depend on β, Rmin, Rmax, Lr and Lp, whose exact expressions are deferred to the supplementary material for this paper. Theorem 4.3. Given a (Lr, Lp)-Lipschitz MDP, which satisfies the condition for global convergence (6) and constants m and M defined above, for any step size α ≤ 1M , the policy gradient initialized at the myopic policy δ̄ and updating as δ ← α∇δVδ in the bounded Lipschitz policy space ∆̂ after k iterations, it produces policy δ(k) satisfying
Vδ̃(s)− Vδ(k)(s) ≤ (1− αm)k
(exp(Rmin) + 1) 2 at all s ∈ S.

heading: 5 EMPIRICAL APPLICATION
text: To demonstrate the performance of the algorithm, we use the data from Rust (1987) which made the standard benchmark for the Econometric analysis of MDPs. The paper estimates the cost associated with maintaining and replacing bus engines using data from maintenance records from Madison Metropolitan Bus City Company over the course of 10 years (December, 1974—May, 1985). The data contains monthly observations on the mileage of each bus as well as the dates of major maintenance events (such as bus engine replacement).
Rust (1987) assumes that the engine replacement decisions follow an optimal stopping policy derived from solving a dynamic discrete choice model of the type that we described earlier. Using this assumption and the data, he estimates the cost of operating a bus as a function of the running mileage as well as the cost of replacing the bus engine. We use his estimates of the parameters of the return function and the state transition probabilities (bus mileage) to demonstrate convergence of the gradient descent algorithm.
In Rust (1987) the state st is the running total mileage of the bus accumulated by the end of period t. The immediate reward is specified as a function of the running mileage as:
r(st, a, θ1) = { −RC + t1, if a = 1 −c(st, θ1) + t0, if a = 0
where RC is the cost of replacing the engine, c(st, θ1) is the cost of operating a bus that has st miles.
Following Rust (1987), we take c(st, θ1) = θ1st. Further, as in the original paper, we discretize the mileage taking values in the range from 0 to 175 miles into an even grid of 2,571 intervals. Given the observed monthly mileage, Rust (1987) assumes that transitions on the grid can only be of increments 0, 1, 2, 3 and 4. Therefore, transition process for discretized mileage is fully specified by just four parameters θ2j = Pr[st+1 = st + j|st, a = 0], j = 0, 1, 2, 3. Table 1 describes parameter values that we use directly from Rust (1987).
We use the gradient descent algorithm to update the policy threshold π : 1 + π ≥ 0 ⇒ a = 1, where a = 1 denotes the decision to replace the engine. We set the learning rate using the RMSprop method1.
1We use standard parameter values for RMSProp method: β = 0.1, ν = 0.001 and = 10−8. The performance of the the method was very similar to that when we used ADAM to update the threshold values.
We use “the lazy projection" method to guarantee the search over Lipschitz policy space. The policy space is parametrized by the vector of thresholds (π1, . . . , πN ) corresponding to discretized state space (s1, . . . , sN ). It is initialized at the myopic policy, i.e. π (0) 1 = u(s1), . . . , π (0) N = u(sN ). At step k the algorithm updates the thresholds to the value π (k∗) i = π (k−1) i − αDδ(k−1)V (si)L(π (k−1) i )(1− L(π (k−1) i )), where L(·) is the logistic function and policy δ (k) j = L(π (k−1) j ) for i, j = 1, . . . , N. To make the“lazy projection" updated values π (k∗) i are adjusted to the closest monotone set of values π(k)1 ≤ π (k) 2 ≤ . . . ≤ π (k) N . The algorithm terminates at step k where the norm maxi |DVδ(k)(si)| ≤ τ for a given tolerance τ .2 The formal definition of lazy projection can be found in Appendix C.
Figure 3 demonstrates convergence properties of our considered version of the policy gradient algorithm. We used the “oracle" versions of the gradient and the value function that were obtained by solving the corresponding Bellman equations. We initialized the algorithm using the myopic threshold π̄(s) = −RC + c(s, θ1); with the convergence criterion set to be based on the value maxi |DVδ(si)|3. In the original model in Rust (1987), the discount factor used when estimating parameters of the cost function was very close to 1. However, performance of the algorithm improves drastically when the discount factor is reduced. This feature is closely related to the Hadamard stability of the solution of the Bellman equation (e.g. observed in Bajari et al. (2013)) and is not algorithm-specific. In all of the follow-up analysis by the same author (e.g. Rust (1996)) the discount factor is set to more moderate values of .99 or .9 indicating that these performance issues were indeed observed with the settings in Rust (1987). Figure 3 illustrates the performance of the algorithm for the case where the discount factor is set to 0.994. For the same convergence criterion, the algorithm converges much faster.
2To optimize the performance of the method it is also possible to consider a mixed norm of the form maxi |π(k)(si)− π(k−1)(si)|+ λmaxi |DVδ(k)(si)|∞ ≤ τ for some calibrated weight λ. This choice would control both the rate of decay of the gradient and the advancement of the algorithm in adjusting the thresholds.
3The particular tolerance value used was 0.03 for illustrative purposes. 4When we reduce the cost of replacing the engine along with the discount factor, which ensures that there is
significant variation in threshold values across states, convergence is improved even further

heading: A OMITTED PROOF FOR THEOREM 3.1
text: Theorem 3.1. Value function Vδ is twice Freéchet differentiable with respect to δ at the choice probability δ̃ corresponding to optimal policy and its Fréchet derivative is negative at δ̃ in all states s, i.e., D2Vδ̃(s) ≤ 0.
Proof. We start with the Bellman equation of the value function.
Vδ(s) =(1− δ(s)) r(s)− δ(s) log (δ(s)) − (1− δ(s)) log(1− δ(s)) + β E ,s′ [ Vδ(s)(s ′) ∣∣∣s] (7)
First of all, note that in (7) the first three terms on the right hand side of the equation simple nonlinear functions δ(·) and thus the directional derivative with respect to δ(·) can be taken as an ordinary derivative with respect to δ as a parameter. Next note that if functional Jδ(·) is directionally differentiable with respect to δ and for all h(·), ddτ Jδ+τ h(·)|τ=0/h(·) is invariant, then Jδ(·) is Fréchet differentiable with respect to δ and the obove ratio is its Fréchet derivative. As a result, the Fréchet derivative of simple functional (1− δ(s)) r(s)− δ(s) log (δ(s))− (1− δ(s)) log(1− δ(s)) with respect to δ(·) exists and equal to log(1− δ(s))− log(δ(s))− r(s). This expression is itself a Freéchet-differentiable functional with Fréchet derivative equal to −1/(δ(s)(1 − δ(s))), meaning that the original functional (1 − δ(s)) r(s) − δ(s) log (δ(s)) − (1 − δ(s)) log(1 − δ(s)) is twice Fréchet differentiable with the second Fréchet derivative −1/(δ(s)(1− δ(s))). Whenever the state transition is affected by the individual decision we need to consider decomposition of the conditional expectation with respect to the future state:
E ,s′ [Vδ(s′)|s] = (1− δ(s)) Es′ [Vδ(s′)|s, 1] + δ(s) Es′ [Vδ(s′)|s, 0] .
Under standard technical conditions that allow the swap of the derivative and the integral
DEs′ [Vδ(s′)|s] = (Es′ [Vδ(s′)|s, 0]− Es′ [Vδ(s′)|s, 1]) + Es′ [DVδ(s′)|s] Thus, the Fréchet derivative of the value function should be the fixed point of the following Bellman equation
DVδ(s) = (log(1− δ(s))− log(δ(s))− r(s)) + β (Es′ [Vδ(s′)|s, 0]− Es′ [Vδ(s′)|s, 1]) + β E ,s′ [DVδ(s′)|s] ,
(8)
and
D2Vδ(s) = − 1
δ(s)(1− δ(s)) − 2β(Es′ [DVδ(s′)|s, 1]− Es′ [DVδ(s′)|s, 0]) + β Es′ [ D2Vδ(s ′)|s ] .
(9)
Given that both these equations are Type II Fredholm integral equations for DVδ(·) and D2Vδ(·) which have unique solutions whenever β < 1 that are bounded and continuous (see Dunford and Schwartz (1957)) and, thus, unique solutions for both equations exist and Vδ(·) is indeed Fréchetdifferentiable. This means that the necessary condition for its optimum yielding δ̃ is DVδ̃(s) = 0 for all states s. As a result, equation (9) implies that its second Fréchet derivative is negative for all states, i.e.,D2Vδ̃(s) ≤ 0.

heading: B OMITTED PROOFS IN SECTION 4
text: B.1 OMITTED PROOF OF THEOREM 4.1
Theorem 4.1. Given an (Lr, Lp)-Lipschitz MDP, the optimal policy δ̃ satisfies∣∣∣∣∣log ( 1− δ̃(s) δ̃(s) ) − log ( 1− δ̃(s†) δ̃(s†) )∣∣∣∣∣ ≤ ( Lr + 2βRmaxLp 1− β ) ∣∣s− s†∣∣ for all state s, s† ∈ S where Rmax = maxs∈S r(s) is the maximum of the immediate reward r over S.
Proof. At the optimal policy δ̃, the Fréchet derivative of the value function is zero, i.e., DVδ̃(s) = 0 for all state s. Therefore, from the Bellman equation (8) we establish that
log ( 1− δ̃(s) δ̃(s) ) = r(s) + β (Es′ [ Vδ̃(s ′)|s, 1 ] − Es′ [ Vδ̃(s ′)|s, 0 ] )
Thus, for all states s, s† ∈ S,∣∣Es′[Vδ̃(s′)|s, a]− Es′[Vδ̃(s′)|s†, a]∣∣ =
∣∣∣∣∫ s′∈S Vδ̃(s ′)(p(s′|s, a)− p(s′|s†, a))ds′ ∣∣∣∣ = Rmax 1− β ∣∣∣∣∫ s′∈S (1− β) Rmax Vδ̃(s ′)(p(s′|s, a)− p(s′|s†, a))ds′
∣∣∣∣ ≤Rmax
1− β sup ‖f‖L≤1 {∣∣∣∣∫ s′∈S f(s′)(p(s′|s, a)− p(s′|s†, a))ds′ ∣∣∣∣}
= Rmax 1− β K(p(·|s, a), p(·|s†, a)) ≤ RmaxLp 1− β ∣∣s− s†∣∣ where we use upper bounds sups∈S Vδ̃(s) ≤ Rmax 1−β and ‖ (1−β) Rmax
Vδ̃(s ′)‖L ≤ 1. Thus,∣∣∣∣∣log ( 1− δ̃(s) δ̃(s) ) − log ( 1− δ̃(s′) δ̃(s†) )∣∣∣∣∣ =|r(s)− r(s†) + β (Es′ [ Vδ̃(s ′)|s, 1 ] − Es′ [ Vδ̃(s ′)|s, 0 ] )
− β (Es′ [ Vδ̃(s ′)|s†, 1 ] − Es′ [ Vδ̃(s ′)|s†, 0 ] )|
≤ ∣∣r(s)− r(s†)∣∣+ β ∣∣Es′[Vδ̃(s′)|s, 1]− Es′[Vδ̃(s′)|s†, 1]∣∣
+ β ∣∣Es′[Vδ̃(s′)|s, 0]− Es′[Vδ̃(s′)|s†, 0]∣∣
≤ ( Lr +
2βRmaxLp 1− β ) ∣∣s− s†∣∣ B.2 OMITTED PROOF OF THEOREM 4.2
Theorem 4.2. Given an (Lr, Lp)-Lipschitz MDP which satisfies the condition for global convergence (6), the value function Vδ is concave with respect to policy δ in the Lipschitz policy space ∆, i.e., D2Vδ(s) ≤ 0 for all s ∈ S, δ ∈ ∆.
To show Theorem 4.2, we first introduce the following lemma establishing Lipschitz continuity of the Fréchet derivative of the value function.
Lemma B.1. Given a (Lr, Lp)-Lipschitz MDP, for all policies δ in the the Lipschitz policy space ∆, the Fréchet derivative of the respective value function DVδ(·) is ( 2Lr+ 4βRmaxLp
1−β 1−2βLp
) -Lipschitz
continuous, i.e., for all states s, s† ∈ S,
∣∣DVδ(s)−DVδ(s†)∣∣ ≤ (2Lr + 4βRmaxLp1−β 1− 2βLp )∣∣s− s†∣∣ . Proof. We begin with the Bellman equation (8) for the Fréchet derivative of value function.
DVδ(s) = log ( 1− δ(s) δ(s) ) − r(s)
+ β (Es′ [Vδ(s′)|s, 0]− Es′ [Vδ(s′)|s, 1]) + β E ,s′ [DVδ(s′)|s]
We use the concept of the contraction mapping to prove the result of the Lemma.
Definition B.1. Let T : X → X be a mapping from a metric space X to itself,
• T is a contraction mapping (with modulus γ ∈ [0, 1)) if ρ(T (x), T (y)) ≤ γρ(x, y) for all x, y ∈ X , where ρ is a metric on X .
• x is a fixed point of T if T (x) = x.
Lemma B.2. Suppose that X is a complete metric space and that T : X → X is a contraction mapping with modulus γ. Then,
• T has a unique fixed point x∗.
• If X ′ ⊆ X is a closed subset for which T (X ′) ⊆ X ′, then x∗ ∈ X ′.
Consider the contraction mapping Tδ(x)(s) = log ( 1−δ(s) δ(s) ) − r(s) + β (Es′ [Vδ(s′)|s, 0] − Es′ [Vδ(s′)|s, 1]) + β E ,s′ [x(s′)|s], then the Bellman equation implies that DVδ is the fixed point of contraction mapping Tδ . Since the Lipschitz continuity property forms a closed subset, by Lemma B.2, it is sufficient to show for any LDV -Lipschitz continuous x, Tδ(x) is also LDV -Lipschitz continuous,
where LDV = 2Lr+
4βRmaxLp 1−β
1−2βLp . Thus, consider states s, s † ∈ S,∣∣T (x)(s)− T (x)(s†)∣∣
≤ ∣∣∣∣log(1− δ(s)δ(s) ) − log ( 1− δ(s†) δ(s†) )∣∣∣∣+ ∣∣r(s)− r(s†)∣∣ + β
∣∣Es′ [Vδ(s′)|s, 0]− Es′[Vδ(s′)|s†, 0]∣∣ + β
∣∣Es′ [Vδ(s′)|s, 1]− Es′[Vδ(s′)|s†, 1]∣∣ + β
∣∣Es′ [x(s′)|s, 0] δ(s)− Es′[x(s′)|s†, 0] δ(s†)∣∣ + β
∣∣Es′ [x(s′)|s, 1] (1− δ(s))− Es′[x(s′)|s†, 1] (1− δ(s†))∣∣ where ∣∣∣∣log(1− δ(s)δ(s) ) − log ( 1− δ(s†) δ(s†)
)∣∣∣∣ ≤ (Lr + 2βRmaxLp1− β ) ∣∣s− s†∣∣∣∣r(s)− r(s†)∣∣ ≤ Lr ∣∣s− s†∣∣
by the same calculation in the proof of Theorem 4.1, for a = 0, 1,
β ∣∣Es′ [Vδ(s′)|s, a]− Es′[Vδ(s′)|s†, a]∣∣ ≤ (Lr + 2βRmaxLp
1− β
) ∣∣s− s†∣∣
and ∣∣Es′ [x(s′)|s, 0] δ(s)− Es′[x(s′)|s†, 0] δ(s†)∣∣ =
∣∣∣∣∫ s′∈S (δ(s)− δ(s†))x(s′)(p(s′|s, a)− p(s′|s†, a))ds′ ∣∣∣∣
=LDV ∣∣∣∣∫ s′∈S (δ(s)− δ(s†))x(s′) LDV (p(s′|s, a)− p(s′|s†, a))ds′ ∣∣∣∣
≤LDV sup ‖f‖L≤1 {∣∣∣∣∫ s′∈S f(s′)(p(s′|s, a)− p(s′|s†, a))ds′ ∣∣∣∣}
=LDVK(p(·|s, a), p(·|s†, a)) ≤ LDV Lp ∣∣s− s†∣∣
where we use the bound ∣∣δ(s)− δ(s†)∣∣ ≤ 1 and thus ‖ (δ(s)−δ(s†))x(s′)LDV ‖L ≤ 1. Similarly,∣∣Es′ [x(s′)|s, 1] (1− δ(s))− Es′[x(s′)|s†, 1] (1− δ(s†))∣∣ ≤ LDV Lp ∣∣s− s†∣∣
Combining all the bounds, we obtain that∣∣T (x)(s)− T (x)(s†)∣∣ ≤ (2Lr + 4βRmaxLp 1− β + 2βLDV Lp ) ∣∣s− s†∣∣ . Substitution LDV = 2Lr+ 4βRmaxLp
1−β 1−2βLp yields the statement of the Lemma.
Proof of Theorem 4.2. From the Bellman equation (9), it is sufficient to show
1
δ(s)(1− δ(s)) ≥ 2β(Es′ [DVδ(s′)|s, 1]− Es′ [DVδ(s′)|s, 0]) (10)
We bound both sides separately. Since the policy satisfies δ(s) ≤ δ̄(s) for all states s, and δ̄(s) = 1 exp(r(s))+1 ≤ 1 2 , the left hand side can be bounded from below as
1 δ(s)(1− δ(s)) ≥ 1 δ̄(s)(1− δ̄(s))
≥ ( exp(Rmin) + 1 )2
exp(Rmin)
Meanwhile, the righthand side can be bounded from above by Lemma B.1. Let LDV = 2Lr+ 4βRmaxLp 1−β
1−2βLp ,
2β |Es′ [DVδ(s′)|s, 1]− Es′ [DVδ(s′)|s, 0]|
=2β ∣∣∣∣∫ s′∈S DVδ(s ′)(p(s′|s, 1)− p(s′|s, 0))ds′ ∣∣∣∣ =2βLDV ∣∣∣∣∫ s′∈S DVδ(s ′) LDV (p(s′|s, 1)− p(s′|s, 0))ds′
∣∣∣∣ ≤2βLDV sup
‖f‖L≤1 {∣∣∣∣∫ s′∈S f(s′)(p(s′|s, 1)− p(s′|s, 0))ds′ ∣∣∣∣}
=2βLDVK(p(·|s, 1), p(·|s, 0)) ≤ 2βLp
1− 2βLp
( 2Lr +
4βRmaxLp 1− β ) From the condition of global convergence
2βLp 1− 2βLp
( 2Lr +
4βRmaxLp 1− β
) ≤ ( exp(Rmin) + 1 )2
exp(Rmin)
it follows that the inequality (10) is satisfied and the Bellman equation (9) implies that D2Vδ(s) ≤ 0 for all states s ∈ S.
B.3 OMITTED PROOF OF THEOREM 4.3
For notation simplicity, we introduce notations m and M such that
m = 1
1− β
(( exp(Rmin) + 1 )2 exp(Rmin) − 2βLp 1− 2βLp ( 2Lr + 4βRmaxLp 1− β ))
M = 1
(1− β)2
(1− β) ( exp ( 1 1−βRmax − β 2Rmin ) + 1 )2
exp( 11−βRmax − β 2Rmin)
+2β ( exp ( 1
1− β Rmax −
β 2 Rmin
) + 2β
1− β Rmax − (1 + β)Rmin )) Theorem 4.3. Given a (Lr, Lp)-Lipschitz MDP, which satisfies the condition for global convergence (6) and constants m and M defined above, for any step size α ≤ 1M , the policy gradient initialized at the myopic policy δ̄ and updating as δ ← α∇δVδ in the bounded Lipschitz policy space ∆̂ after k iterations, it produces policy δ(k) satisfying
Vδ̃(s)− Vδ(k)(s) ≤ (1− αm)k
(exp(Rmin) + 1) 2
at all s ∈ S.
Our analysis follows the standard steps establishing convergence of the conventional gradient descent algorithm which bounds the second Fréchet derivative of the value function Vδ with respect to the policy δ from above and from below by m and M respectively. Lemma B.3. Given a (Lr, Lp)-Lipschitz MDP, which satisfies the condition for global convergence (6), for all policies δ in the bounded Lipschitz policy space ∆̂, for all states s ∈ S , the second Fréchet derivative of the value function Vδ with respect to the policy δ is upperbounded as
D2Vδ(s) ≤ −m.
Proof. The Bellman equation (9) implies that
max s
D2Vδ(s) ≤ 1
1− β
( −min
s
1
δ(s)(1− δ(s))
+ 2βmax s
(Es′ [DVδ(s′)|s, 0]− Es′ [DVδ(s′)|s, 1]) )
By the same argument as in Theorem 4.2,
min s
1 δ(s)(1− δ(s)) ≥ ( exp(Rmin) + 1 )2
exp(Rmin)
max s
(Es′ [DVδ(s′)|s, 1]− Es′ [ DVδ(s ′)|s†, 0 ] ) ≤ 2βLp
1− 2βLp
( 2Lr +
4βRmaxLp 1− β ) Thus, for all state s ∈ S,
D2Vδ(s) ≤ −m. Lemma B.4. Given a (Lr, Lp)-Lipschitz MDP, which satisfies the condition for global convergence, for all policy δ in the bounded Lipschitz policy space ∆̂, for all state s ∈ S , the second derivative of the value function Vδ with respect to the policy δ is is lowerbounded as
D2Vδ(s) ≥ −M.
Proof. The Bellman equation (9) implies that
min s
D2Vδ(s) ≥ 1
1− β
( −max
s
1
δ(s)(1− δ(s)) + 2β (
min s DVδ(s)−max s
DVδ(s) ))
By restricting policy to the bounded Lipschitz policy space ∆̂ we bound
max s
1
δ(s)(1− δ(s)) ≤ max s
1
δ(s)(1− δ(s)) ≤
( exp ( 1
1−βRmax − β 2Rmin
) + 1 )2
exp( 11−βRmax − β 2Rmin)
Provided
min s Vδ(s) ≥ Rmin 2
max s Vδ(s) ≤ Rmax 1− β
min s
( log ( 1− δ(s) δ(s) ) − r(s) ) ≥ min s ( log ( 1− δ̄(s) δ̄(s) ) − r(s) ) = 0
max s
( log ( 1− δ(s) δ(s) ) − r(s) ) ≤ max s log ( 1− δ(s) δ(s) ) −min s r(s)
≤ exp ( 1
1− β Rmax −
β 2 Rmin
) −Rmin
it follows from Bellman equation (8) that
min s
DVδ(s) ≥ 1
1− β ( min s ( log ( 1− δ(s) δ(s) ) − r(s) ) + β(min s Vδ(s)−max s Vδ(s)) ) ≥ β
1− β
( Rmin
2 − Rmax 1− β ) max s DVδ(s) ≤ 1 1− β ( max s ( log ( 1− δ(s) δ(s) ) − r(s) ) + β(max s Vδ(s)−min s Vδ(s))
) ≤ 1
1− β
( exp ( 1
1− β Rmax −
β 2 Rmin
) + β
1− β Rmax −
2 + β
2 Rmin ) Thus, for all state s ∈ S,
D2Vδ(s) ≥ −M.
Proof of Theorem 4.3. The convergence rate guarantee follows from Lemma B.3 and Lemma B.4, under the standard arguments for the gradient descent algorithm for m-strongly concave and M - smooth (i.e., M -Lipschitz gradient) functions (cf. Bansal and Gupta, 2017).

heading: C MORE RESULTS IN SECTION 5
text: Algorithm 1 “Lazy projection”, (π1, . . . , πN ): thresholds corresponding to discretized state space (s1, . . . , sN ); L(·): logistic function; policy δj = L(πj); α: step size; τ : termination tolerance
1: π(0)1 ← u(s1), . . . , π (0) N ← u(sN ) // Initialize π(0) at the myopic policy 2: while maxi |DVδ(k)(si)| ≤ τ do 3: π(k∗)i ← π (k−1) i − αDδ(k−1)Vδ(k−1)(si)L(π (k−1) i )(1− L(π (k−1) i )) for all i ∈ [N ] 4: (π(k)1 , . . . , π (k) N )← the closest monotone thresholds of (π (k∗) 1 , . . . , π (k∗) N ) // Lazy projection 5: return (π(k)1 , . . . , π (k) N )
We list the convergence of gradient descent and its derivative, second derivative at smaller discount factor β = 0.9.

Review summaries:
This paper considers reinforcement learning for discrete choice models with unobserved heterogeneity, which is useful for analyzing dynamic Economic behavior.  Random choice-specific shocks in reward is accommodated, which are only observed by the agent but not recorded in the data. Existing optimization approaches rely on finding a functional fixed point, which is computationally expensive.  The main contribution of the paper lies in formulating discrete choice models into an MDP, and showing that the value function is concave with respect to the policy (represented by conditional choice probability).  So policy gradient algorithm can provably converge to the global optimal.  Conditions on the parameters for global concavity are identified and rates of convergences are established.  Finally, significant advantages in computation were demonstrated on the data from Rust (1987), compared with “nested fixed point” algorithms that is commonly used in Econometrics.

This paper deals with a certain class of models, known as discrete choice models. These models are popular in econometrics, and aim at modelling the complex behavioural patterns of individuals or firms. Entities in these models are typically modelled as rational agents, that behave optimally for reaching their goal of maximizing a certain objective function such as maximizing expected cumulative discounted payoff over a fixed period.