Title: GLOBAL CONCAVITY AND OPTIMIZATION IN A CLASS OF DYNAMIC DISCRETE CHOICE MODELS Anonymous

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.

1. INTRODUCTION:

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.

2. PRELIMINARIES:

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.

2.1. MARKOV DECISION PROCESS:

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 s t based on the Markov transition P given the state-action pair (s t-1 , a t-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 s 1 , the agent's long-term payoff is E 1 ,s2, 2,... ∞ t=1 β t-1 r(s t , a t ) + 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 space A 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 [R min , R max ]. 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 × R A → 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 σ (s 1 ) = E 1,s2, 2,... ∞ t=1 β t-1 r(s t , σ(s t , 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, ) + β E s [V σ (s )|s, σ(s, )]

for all policies σ (1)

2.2. CONDITIONAL CHOICE PROBABILITY REPRESENTATION:

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 + β E s [V σ (s )|s, a] ≥ r(s, a ) + a + β E s [V σ (s )|s, a ] , ∀a }]

The optimal policy σ can, therefore, be equivalently characterized by threshold function π(s, a) = r(s, a)

+ β E s [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 † = argmax a {π(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

EQUATION

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,

Pr s [s ≤ ŝ|s, 1] ≤ Pr 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).

2.3. MDP IN ECONOMICS AND POLICY GRADIENT:

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.

3. WARM-UP: LOCAL CONCAVITY OF THE VALUE FUNCTION AT THE OPTIMAL:



POLICY:

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 D 2 V δ (•). 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., D 2 V δ (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

EQUATION

and

EQUATION

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.,D 2 V δ (s) ≤ 0.

The Bellman equation ( 9) of the second Fréchet derivative suggests that

D 2 V δ (s) ≤ 0 for all states s if 1 δ(s)(1 -δ(s)) + 2β(E s [DV δ (s )|s, 1] -E s [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.

4. GLOBAL CONCAVITY OF THE VALUE FUNCTION:

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.

4.1. LIPSCHITZ MARKOV DECISION PROCESS:

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 L 1 -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 f d(p -q) : f is 1-Lipschitz continuous Definition 4.2 (Lipschitz MDP). A Markov decision process is (L r , L p )-Lipschitz if ∀s, s ∈ S |r(s) -r(s )| ≤ L r |s -s | ∀s, s ∈ S, a, a ∈ A K(p(•|s, a), p(•|s , a )) ≤ L p (|s -s | + |a -a |)

4.2. CHARACTERIZATION OF THE OPTIMAL POLICY:

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., E s [DV δ (s )|s, 0] -E s [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 (L r , L p )-Lipschitz MDP, the optimal policy δ satisfies

log 1 -δ(s) δ(s) -log 1 -δ(s † ) δ(s † ) ≤ L r + 2βR max L p 1 -β s -s †

for all state s, s † ∈ S where R max = max s∈S r(s) is the maximum of the immediate reward r over S.

4.3. CONCAVITY OF THE VALUE FUNCTION WITH RESPECT TO LIPSCHITZ POLICIES:

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 (L r , L p )-Lipschitz MDP, define its Lipschitz policy space ∆ as

∆ = {δ : δ(s) ≤ δ(s) ∀s ∈ S and log 1 -δ(s) δ(s) -log 1 -δ(s † ) δ(s † ) ≤ L r + 2βR max L p 1 -β 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 (L r , L p )-Lipschitz MDP satisfies the sufficient condition for global convergence if

EQUATION

)

Theorem 4.2. Given (L r , L p )-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., D 2 V δ (s) ≤ 0 for all s ∈ S, δ ∈ ∆.

4.4. THE RATE OF GLOBAL CONVERGENCE OF THE POLICY GRADIENT ALGORITHM:

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-β R max -β 2 R min .

Note that Bellman equation ( 7) implies that V (s) is between Rmin 2 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 (L r , L p )-Lipschitz MDP, define its bounded Lipschitz policy space ∆ as ∆ = {δ : δ(s) ≤ δ(s) ≤ δ(s) ∀s ∈ S and

log 1 -δ(s) δ(s) -log 1 -δ(s † ) δ(s † ) ≤ L r + 2βR max L p 1 -β s -s † ∀s, s † ∈ S .

For simplicity of notation, we introduce constants m and M which only depend on β, R min , R max , L r and L p , whose exact expressions are deferred to the supplementary material for this paper. Theorem 4.3. Given a (L r , L p )-Lipschitz MDP, which satisfies the condition for global convergence (6) and constants m and M defined above, for any step size α ≤1 M , 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(R min ) + 1) 2 at all s ∈ S.

5. EMPIRICAL APPLICATION:

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 s t 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(s t , a, θ 1 ) = -RC + t1 , if a = 1 -c(s t , θ 1 ) + t0 , if a = 0

where RC is the cost of replacing the engine, c(s t , θ 1 ) is the cost of operating a bus that has s t miles.

Following Rust (1987) , we take c(s t , θ 1 ) = θ 1 s t . 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[s t+1 = s t + j|s t , 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 method 1 .

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 (s 1 , . . . , s N ). It is initialized at the myopic policy, i.e. π (0) 1 = u(s 1 ), . . . , π (0) N = u(s N ). At step k the algorithm updates the thresholds to the value π

(k * ) i = π (k-1) i -αD δ (k-1) V (s i )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 ad- justed to the closest monotone set of values π (k) 1 ≤ π (k) 2 ≤ . . . ≤ π (k)

N . The algorithm terminates at step k where the norm max i |DV δ (k) (s i )| ≤ τ 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 max i |DV δ (s i )|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. Theorem 4.1. Given an (L r , L p )-Lipschitz MDP, the optimal policy δ satisfies

log 1 -δ(s) δ(s) -log 1 -δ(s † ) δ(s † ) ≤ L r + 2βR max L p 1 -β s -s †

for all state s, s † ∈ S where R max = max s∈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) + β (E s V δ (s )|s, 1 -E s V δ (s )|s, 0 )

Thus, for all states s, s † ∈ S,

E s V δ (s )|s, a -E s V δ (s )|s † , a = s ∈S V δ (s )(p(s |s, a) -p(s |s † , a))ds = R max 1 -β s ∈S (1 -β) R max V δ (s )(p(s |s, a) -p(s |s † , a))ds ≤ R max 1 -β sup f L ≤1 s ∈S f (s )(p(s |s, a) -p(s |s † , a))ds = R max 1 -β K(p(•|s, a), p(•|s † , a)) ≤ R max L p 1 -β s -s †

where we use upper bounds sup s∈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 † ) + β (E s V δ (s )|s, 1 -E s V δ (s )|s, 0 ) -β (E s V δ (s )|s † , 1 -E s V δ (s )|s † , 0 )| ≤ r(s) -r(s † ) + β E s V δ (s )|s, 1 -E s V δ (s )|s † , 1 + β E s V δ (s )|s, 0 -E s V δ (s )|s † , 0 ≤ L r + 2βR max L p 1 -β s -s † B.2 OMITTED PROOF OF THEOREM 4.2

Theorem 4.2. Given an (L r , L p )-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., D 2 V δ (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 (L r , L p )-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 † ) ≤ 2L r + 4βRmaxLp 1-β 1 -2βL p 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) + β (E s [V δ (s )|s, 0] -E s [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) . Thus, consider states s, s † ∈ S,

δ(s) -r(s) + β (E s [V δ (s )|s, 0] - E s [V δ (s )|s, 1]) + β E ,

T (x)(s) -T (x)(s † ) ≤ log 1 -δ(s) δ(s) -log 1 -δ(s † ) δ(s † ) + r(s) -r(s † ) + β E s [V δ (s )|s, 0] -E s V δ (s )|s † , 0 + β E s [V δ (s )|s, 1] -E s V δ (s )|s † , 1 + β E s [x(s )|s, 0] δ(s) -E s x(s )|s † , 0 δ(s † ) + β E s [x(s )|s, 1] (1 -δ(s)) -E s x(s )|s † , 1 (1 -δ(s † ))

where

log 1 -δ(s) δ(s) -log 1 -δ(s † ) δ(s † ) ≤ L r + 2βR max L p 1 -β s -s † r(s) -r(s † ) ≤ L r s -s †

by the same calculation in the proof of Theorem 4.1, for a = 0, 1, 

β E s [V δ (s )|s, a] -E s V δ (s )|s † , a ≤ L r + 2βR max L p 1 -β s -s † and E s [x(s )|s, 0] δ(s) -E s x(s )|s † , 0 δ(s † ) = s ∈S (δ(s) -δ(s † ))x(s )(p(

We bound both sides separately. Since the policy satisfies δ(s) ≤ δ(s) for all states s, and δ(s) = it follows that the inequality ( 10) is satisfied and the Bellman equation ( 9) implies that D 2 V δ (s) ≤ 0 for all states s ∈ S.

D 2 V δ (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 Msmooth (i.e., M -Lipschitz gradient) functions (cf. Bansal and Gupta, 2017) .

C MORE RESULTS IN SECTION 5:

Algorithm 1 "Lazy projection", (π 1 , . . . , π N ): thresholds corresponding to discretized state space (s 1 , . . . , s N ); L(•): logistic function; policy δ j = L(π j ); α: step size; τ : termination tolerance 1: π (0)

1 ← u(s 1 ), . . . , π

N ← u(s N ) // Initialize π ( 0) at the myopic policy 2: while max i |DV δ (k) (s i )| ≤ τ do 3:

π (k * ) i ← π (k-1) i -α D δ (k-1) V δ (k-1) (s i )L(π (k-1) i )(1 -L(π (k-1) i

)) for all i ∈ [N ] We list the convergence of gradient descent and its derivative, second derivative at smaller discount factor β = 0.9. 

:

We 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.

To 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.

The particular tolerance value used was 0.03 for illustrative purposes.

When 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

Figures and Tables:

Figure 1: Convergence of gradient descent, discount factor β = 0.99

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 L DV -Lipschitz continuous x, T δ (x) is also L DV -Lipschitz continuous, where L DV =

s |s, a) -p(s |s † , a))ds =L DV s ∈S (δ(s) -δ(s † ))x(s ) L DV (p(s |s, a) -p(s |s † , a))ds ≤L DV sup f L ≤1 s ∈S f (s )(p(s |s, a) -p(s |s † , a))ds=L DV K(p(•|s, a), p(•|s † , a)) ≤ L DV L p s -s †where we use the bound δ(s) -δ(s † ) ≤ 1 and thus (δ(s)-δ(s † ))x(s )L DV L ≤ 1. Similarly, E s [x(s )|s, 1] (1 -δ(s)) -E s x(s )|s † , 1 (1 -δ(s † )) ≤ L DV L p s -s †Combining all the bounds, we obtain thatT (x)(s) -T (x)(s † ) ≤ 2L r + 4βR max L p 1 -β + 2βL DV L p s -s † . of the Lemma.Proof of Theorem 4.2. From the Bellman equation (9), it is sufficient to show1 δ(s)(1 -δ(s)) ≥ 2β(E s [DV δ (s )|s, 1] -E s [DV δ (s )|s, 0])

min )Meanwhile, the righthand side can be bounded from above by Lemma B.1. LetL DV = 2β |E s [DV δ (s )|s, 1] -E s [DV δ (s )|s, 0]| =2β s ∈S DV δ (s )(p(s |s, 1) -p(s |s, s |s, 1) -p(s |s, 0))ds ≤2βL DV sup f L ≤1 s ∈S f (s )(p(s |s, 1) -p(s |s, 0))ds =2βL DV K(p(•|s, 1), p(•|s, 0)) ≤ 2βL p 1 -2βL p 2L r + 4βR max L p 1 -βFrom the condition of global convergence2βL p 1 -2βL p 2L r + 4βR max L p 1 -β ≤ exp(R min ) + 1 2 exp(R min )

Figure 3: Convergence of gradient descent, discount factor β = 0.9

parameter values in fromRust (1987).

Table content: <table><tr><td>Parameter</td><td>Value</td></tr><tr><td>RC</td><td>11.7257</td></tr><tr><td>θ 1</td><td>0.001× 2.45569</td></tr><tr><td colspan="2">(θ 20 , θ 21 , θ 22 , θ 23 ) (0.0937, 0.4475, 0.4459, 0.0127)</td></tr><tr><td>β</td><td>0.99</td></tr></table>

Peer review (iclr2020):
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 is well written. The most important and novel result is the concavity of the value function with respect to the policy. My major concerns are: 1. How restrictive the assumptions are in Definition 1.4? In particular, R_min is defined from Assumption 2.2 as “the immediate reward … is bounded between [R_min, R_max]”. So if we set R_min to negative infinity, the right-hand side of Eq 6 will be infinity, and so the condition is always met. Is this really true? At least, does the experiment satisfy Definition 1.4? 2. The experiment is on a relatively small problem. Solving value/policy iteration with 2571 states and 2 actions is really not so hard, and many efficient algorithms exist other than value/policy iteration. For example, a variant of policy iteration where policy evaluation is not solved exactly, but instead approximated by applying a small number of Bellman iterations. Or directly optimize the Bellman residual by, e.g., LBFGS, which also guarantees global optimality and is often very fast. See http://www.leemon.com/papers/1995b.pdf . An empirical comparison is necessary.