Global Concavity and Optimization in a Class of Dynamic Discrete Choice Models
Authors: Yiding Feng
Ekaterina Khmelnitskaya
Denis Nekipelov
Venue:  (2020)
Keywords: Reinforcement learning
Policy Gradient
Global Concavity
Dynamic Discrete Choice Model

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.

Under review as a conference paper at ICLR 2020
GLOBAL CONCAVITY AND OPTIMIZATION IN A CLASS OF DYNAMIC DISCRETE CHOICE MODELS
A Anonymous authors
Paper under double-blind review
ABSTRACT
Discrete choice models with unobserved heterogeneity are commonly used Econo- metric 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 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 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 be- havioral assumption regarding the optimizing agents and to facilitate Econometric analysis of dynamic behavior. In particular, we demonstrate significant computa- tional advantages in using a simple implementation policy gradient algorithm over existing "nested fixed point" algorithms used in Econometrics.
INTRODUCTION
Dynamic discrete choice model with unobserved heterogeneity is, arguably, the most popular model that 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 22077), 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) (018).n this model, pioneered in Rust (1987), the agent chooses between 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 Markov process and is observed in the data and also function of an idiosyneratic random variable that is only observed by the agent but is not reported in the data. The unobserved idiosyneratic component 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 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 drawbet trawback of the policy gradient is that the value function in 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

---

Under review as a conference paper at ICLR 2020
convergence results are shown by model-specific technique which is hard to generalize (e.g. Fazel iet al. 2018 for linear quadratic regulator).
In this paper 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 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 con- sumers 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. e-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 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 opti- mization problem (see Rust (1987), Aguirregabiria and Miral (2007)). The replacement of the fixed point iterations with the policy gradient method significanlly 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 bchavioral perspective for social sciences.
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
discrete-time Markov decision process (MDP) with choice-specific heterogeneity is defined as 5-tuple AS, r; E, P, P, where S is compact convex state space with dSam(S) < S < xc, A is the set of actions, r S x A + R, is the reward function, such that r(s, a) is the immediate nog-nieet reward for the state-action pair (s, a), are independent random variables. P is a Markov transition model where where p(s'|s (esss.00 defines the transition density between state 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 "random choice-specific shocks."
In each period t = 1,2,... oc, the nature realizes the current state s; based on the Markov transition P given the state-action pair (st-1. 0x-1) 1) in the previous period t - 1, and the choice-specific shocks & = {Et.aaae. drawn i..dd from distribution e. The optimizing agent chooses an action a E A, and her current period payoff is sum of the immediate reward and the choice-specific shock, i.e., r(s, a)
ér.a- Given initial state 81, the agent's 's long-term payoff is Eey.:2.f2.... ->=- g 04) + ex, 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 's choices before the agent observes realization of &, When the distribution of shocks e is sufficiently smooth (differentiable), the corresponding ex ante value function is smooth (differentiable)
2

---

Under review as a conference paper at ICLR 2020
well. This allows 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, rely the following assumptions.
Assumption 2.1. The state space is compact R. and the action space A is binary, i.., A= = {0, 1}.
Assumption 2.2. For all states s, the immediate reward r(s, 0) for the state-action pair (s, is zero ie.. r(..0) = 0, and the immediate reward r(s, for the state-actis catte-action pair (s, 1) is bounded between [Bminn Rmax]-
Assumption 2.3, Choice-specity shocks are Type I Extreme Value random variables with location
parameter (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 a function S R- A which maps the current state and choice-specific shock to an action. In our further discussion we will show that there natural more restricted definition of the of all feasible policies in this model.
Given any stationary Markov policy d, the value function Vg S + R is mapping from the initial state to the long-term payoff under policy a, i.e.
(81)) = E (2 ge-1 o((e; + ((,o())))))
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., (s) 2 Vs(s) for all policies a and states s) exists. Furthermore, the following Bellman equation holds
Vo ( E. (r(s. c)) + Ca(s,e) + E. (Vo(')ss ((s,
for all policies o
2.2 CONDITIONAL CHOICE PROBABILITY REPRESENTATION
Based on the Bellman equation [ evaluated at the optimal policy, the optimal Conditional Choice Probability B(als) s) (i.e., the probability of choosing action a given state in the optimal policy ā) can be defined as
3(als) F. [1 (r(s,a) + + + (V [|saa a) r(s,a') a') + ea' + + E.. (Va (s')),,'a) Va')]
The optimal policy 7 can, therefore, be equivalently characterized by threshold function # a(, a) r(s, + 3 E.. [V' [s')ss)ss, al]. such that the optimizing agent chooses action at which maximizes the sum of the threshold and the choice-specific shock, i.e., al = argmax, (T(s, a) + e.). Similarly, all non-optimal policies can be characterized by the corresponding threshold functions denoted Under Assumption 2.3 the conditional choice probability 5 can be explicitly expressed in terms the respective threshold æ as (ef. Rust 1996)
6(als) exp(a(s, a)) / (EWEA (iiiesxxp(((ss
We note that this expression induces a one-to-one mapping from the thresholds 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 = (0, 1}. and the reward r(s, 0) is normalized to we denote the immediate reward r(s, 1) as rss); denote the conditional choice probability 6(0]s) 8) as 5(s); and denote T(s, 1) as T(s).
In the subsequent discussion given that the characterization of policy via its threshold is equivalent
to its characterization by conditional choice probability 8, we interchangeably refer to as the "policy." Then rewrite the Bellman equation for given policy as
Vi(s) =(1 8(s)) rs)) 6(s) log (6(s)
(2)
(1 5(s)) log(1 (1g 5(s)) BE Vo(s)(s')
3

---

Under review as a conference paper at ICLR 2020
Now we make two additional assumptions that are compatible with standard assumptions in the Econometrics literature.
Assumption 2.4. For all states 8 E S, the conditional distribution of the next period Markov state p(-|s, 1) first-order stochastically dominates distribution p(-1s, 0), i.e, for all å E S. Præ(s'
[s' $ $|s, 1| & Pros(s'= S $.
Assumption 2.5. Under the optimal policy 8, the value function is non-decreasing in states, i.e. V3(5) S Vy(s") for all 8, s' E S s.t. s < s'.
Consider myopic policy 8(8)= (exp(r(s)) + +)= which uses threshold #(s) rs)). This policy corresponds 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
at least the threshold of myopic policy, i... ((s) 2 (()). Hence, Lemmma 2.1 holds.
Lemma 2.1. The optimal policy 8 chooses action 0 with weakly lower probability than the myopic policy 8 in all states & E S, i... 8(s) < 0(5).
2.3 MDP IN ECONOMICS AND POLICY GRADIENT
Our motivation in this paper comes from empirical work in Economics and Marketing where optimizing agents consumers 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 (L) is replaced by an empirical estimate and then functional iteration uses the empirical Bellman equation 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., e.g.,.Jasee Daksch 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 0 E @ and computes the gradient of the value function with respect to the current policy dg and update the policy in the direction of the gradient, i.e., + B + a VeVa,. Though the individuals considered in the Economic MDP models may not compute the exact gradient with respect 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 0 + 0 + aR V log(Ep de (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 satisfied in a fixed neighborhood around the optimal policy. We rely on the special structure of the value function induced by random shocks e which essentially "smooth it" making it differentiable. We then use Bellman equation 77) 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.
4

---

Under review as a conference paper at ICLR 2020
By A we denote the convex compact set that contains all continuous functions 8 - [0, 1] such that 0 S 6(.) & 6()). The Bellman equation (7) defines the functional Va(-). Recall that Fréchet derivative of functional V-),), which maps bounded linear space A into the space of all continuous bounded functions of 8, at a given 5(-) is bounded linear functional DV&(+) such that for all continuous (()) with |||]| H: V.++(.) V.(+) DV&(.) ) h(-) + o[|] When functional (V 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-V)(-).
Theorem 3.1. Value function V8 is twice Freéchet differentiable with respect to at the choice probability 8 corresponding to optimal policy and its Fréchet derivative is negative at ô in all states s. i.e. D2 (2
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
(v) = (log(1 8())) - log()(s)) - r(s)) + 3 (E (V('')s E. (ss 1)) + E,,y (DVa())))))
(3)
and
Vs 8(s) 8(s)
(4)
(DV3 1] E. (DVV(''))ss BB (s'Vs (
A necessary condition for its optimum yielding ō is (V) = 0 for all states s. As result, equation
(9) implies that its second Fréchet derivative is negative for all states, V (s) < 0.
The Bellman equation 9 of the second Fréchet derivative suggests that (²Vs(() < 0 for all states
if
(s) - ((s)) + 28
(DVs E. (VV((ss)))s >
The first term in the inequality (5) is always positive for all policies in A, but the second term can be arbitrary small. 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.
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 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 Lassseerstnin metric. Kantorovich metric is. arguable. the most common metric used used in the analysis of MDPs (cf. Hindererr 2005; Rachelson and Lagoudakis 2010, Pirotta et al. 2013).
Definition 4.1 (Kantorovich metric). For any two probability measures p, 9, the Kantorovich metric between them is
{1 fdlp /dlp-a) v) f 1-Lipschitz continuous f
K(p, g) = sup
Definition 4.2 (Lipschitz MDP). A Markov decision process is (Ir, I.p L.p.)-Lipshhizz if (r(s) r(s')) < T,p 8'1 K(p(-Is,a), ,a))) < Lp (|s oil +
Vs, E Vs,s' E S,a, EA
+|a+ la- a'l)
5

---

Under review as a conference paper at ICLR 2020
4.2 CHARACTERIZATION OF THE OPTIMAL POLICY
Our result in Section 3/ demonstrates that the second Fréchet derivative of Vs with respect to is negative for a given policy 8 when inequality (5) holds. To bound the second term of ( from below, i.e. (DVV s, 0j e (DV((>)))) I], it sufficient to show that Fréchet derivative (V²(.) is Even though we already assume that the Markov transition is Lipschitz. is still possible that DV& is not Lipschitz: Bellman equation (8) for DV₂ depends on policy 8(s) via log(1- 8()) log(6 (s)), which can be non-Lipschitz in state s for general policies 8. Therefore, to guarantee Lipschitznes, 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.
Lipschitz-continuoon
Theorem 4.1. Given (Lr, Lpp) Lipschitzz MDP, the optimal policy 5 satisfies
(-)(s)
1- Ö(s)
(1-8(12)
1 1- 8((5)
(L,, (
25BmaxxLp 1-3 |s-
log
log
((s)
8(s
for all state s, E S where Rmax = maxses r(s) is the maximum of the immediate reward r over S.
4.3 CONCAVITY 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 (Lr, Lp) Lipschitz MDP, define its Lipschitz policy space A as {6 :(5) s ö(5) E and
log 1 (1-8(s) 8(s) - log
(1- (1-8(57) 8(s1)
< (Lr 2/ Rmax
) |s |s-s") s²| Vs s).
8(s)
3
where 8 is the myopic policy.
Theorem 4.1 and Lemma 2.1 imply that the optimal policy ō lies in this Lipschitz policy space A for any Lipschitz MDP.
Definition 4.4 (Condition for global convergence). We say that (L,, Lp) Lipschittz MDP satisfies the sufficient condition for global convergence if
2
2L, + 43RmazLp)
(exp(Rminn) 1)
2BLp < 1 and 1-28L,
(6)
1-3
exp(Rmmin)
Theorem 4.2. Given (Le, -ippscicctitzz MDP which satisfies the condition for global convergence
(6. value function Va is concave with respect to policy in the Lipschitz policy space A, i.e., Vss) I for all A.
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 the policy gradient algorithm assuming oracle access the Fréchet derivative of the value function. While this analysis provides only theoretical guarantee, as discussed in /ection 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 8 with threshold (ss) = r(s), which is in the Lipschitz policy space A. From Lemma 2.1 follows that the myopie policy is pointwise S greater than the optimal policy, i.e., 8(s) < 6(s). Consider policy 8 with threshold ((s) r(s) + T Rmax
& Rmin Note that Bellman equation implies that V(s) is between Rawin and Roax for all states Thus, policy 1-9
å pointwise bounds the optimal policy from below, i.e., 8(s) < 5(s). Our convergence rate result applies the policy gradient within the bounded Lipschitz policy set Å.

---

Under review as a conference paper at ICLR 2020
Definition 4.5. Given (L,, Lipischhttt MDP, define its bounded Lipschitz policy space Å as Á {6 (s)) S 6(s) 1 8s)
vs E
S
and
log 1 (1-8(s) 6(5)
1 - Thr (Tr++ 23 23.
[-=- Vs, E E
log
8(s)
8(st)
1-
For simplicity of notation, we introduce constants m and M which only depend on B3 Rmin- Rmax. L, and Lp. whose exact expressions are deferred the supplementary material for this paper.
Theorem 4.3. Given a (Lr, Lp) -Lipschitit MDP, which satisfies the condition for global convergence (6) and constants m. and M defined above, for any step size a S 28. the policy gradient initialized at the myopic policy ō and updating 8 <- VV in the bounded Lipschitz policy space A after k iterations, it produces policy 8(k) satisfying
(1aam) (exp( Rmin) + 1)²
Vg(s) Viui
at all E S.
5 EMPIRICAL APPLICATION
To demonstrate the performance of the algorithm, we use the data from Rust (987) 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 1974-May, 1985). The data contains monthly observations on the mileage of each bus as well as the dates of major maintenance events (such bus engine replacement).
Rust 1987 assumes that the engine replacement decisions follow an optimal stopping policy derived from solving dynamic discrete choice model of the type that 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 is the running total mileage of the bus accumulated by the end of period t. The immediate reward is specified as function of the running mileage as:
r(st, a 01) {
RC + Exi, -c((s, 01) + Eoo, if
if
where RC is the cost of replacing the engine, c(se, 01) is the cost of operating bus that has 8, miles.
Following Rust 1987). we take c(st, (1) = 01 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, [ust 1987) assumes that transitions on the grid can only be of increments 0, 2,3 and 4. Therefore, transition process for discretized mileage fully specified by just four parameters 82 Pr[s:41 = + jlst, = 0), j = 0, 0.3. Table describes parameter values that we use directly from Rust (1887).
Table I: parameter values in from Rust 1987
Parameter
Value
RC
11.7257
0.001 x 2.45569
(0zo, O21, Ozz O23) 3
(0.0937, 0.4475, 0.4459, 0.0127) 0.99
We use the gradient descent algorithm to update the policy threshold π + h 2 60 + a 1, where a = denotes the decision to replace the engine. We set the learning rate using the RMSprop m
We standard parameter values for RMSProp method: B = 0.1, 0.001 and 10-5, The performance of the the method was very similar to that when used ADAM update the threshold values.
7

---

Under review as a conference paper at ICLR 2020
We use "the lazy projection" method to guarantee the search over Lipschitz policy space.
The policy space is parametrized by the vector of thresholds (TI,...; corresponding to discretized state space (s1....,8N) It is initialized the myopie policy, i.e. . (0)
u(81).....,T, NN 1 = u(sN). At step & the algorithm updates the thresholds to the value TH
(k))
where L(.) is the logistic function and policy t; (k-1) - -DD gth (mT (1(() ((m:--))
5/4) = [(T) for j.j = ......... ... To make the theylazy projection" updated values (k*)) are ad-
justed to the closest monotone set of values T| I 22 (k) .... S T
(k) The algorithm terminates at
step k where the norm max, (V [s:)] S T for a given tolerance T projection can be found in Appendix C
The formal definition of lazy
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
T (s)) = RC + c(x,0) with the convergence criterion set to based on the value max; [DV
In the original model in Rust (987). the discount factor used when estimating parameters of the cost function was very close to I. 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-speciffe In all the follow-up analysis by the same author (e.g. Rust (1996)) the discount factor is set to more moderate values of .999 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.99 For the same convergence criterion, the algorithm converges much faster.
Canergance the puling scliire for the Besge (ert21))
Cenvergrane the pallcy Poacticn for overagr lnnge b-100)
Converper no get tey wotten sarol Meage tootig
Eor
6.0
130
24000
Figure I: Convergence of gradient descent, discount factor / = 0.99
2000
Evatution derivative, factor
Thanodadi
-10+.0
-2e1 06
400
-Ga 00
000
400
5000
10000
18000
20000
24026
A0T0
15000
(ADE0 25000 24576
Horation number
Figure 2: Performance of the norm max; [sV)(s:) and the second derivative max; [DV)(ss)), discount factor 3 = 0.99
"To optimize the performance of the method it is also possible consider mixed norm of the form (s:)]
max, (x(() - (x-))) + À max, (DV (sx))oc S for some calibrated weight X. 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
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Abbring, J. H. and Heckman, J. J. (2007). Econometric evaluation of social programs, part iii: Distributional treatment effects, dynamic treatment effects, dynamic discrete choice, and general cquilibrium policy evaluation. Handbook of econometrics, 6:5145-5303.
Aguirregabiria, V. and Magesan, A. (2016). Solution and estimation of dynamic discrete choice structural models using euler equations. Available at SSRN 2860973.
Aguirregabiria, V. and Mira, (2007). Sequential estimation dynamic discrete games. Economet- rica, 75(1):1-53.
Aguirregabiria, V. and Mira, P. (2010). Dynamic discrete choice structural models: A survey. Journal of Econometrics, 156:3)38-67
Arcidiacono, P. and Miller, R. A. (2011). Conditional choice probability estimation of dynamic discrete choice models with unobserved heterogeneity. Econometrica, 1966):1823-187.
Bajari, P., Hong, H., and Nekipelov, D. (2013). Game theory and econometries: survey of some recent research. In Advances in economics and econometrics, 10th world congress, volume 3, pages 3-52.
Bansal, N. and Gupta, A. (2017). Potential-function proofs for first-order methods. arXiv preprint arXiv:1712.0444 1.0581..
Dubé, J.P.., Chintagunta, P., Petrin, A., Bronnenberg, B., Goettler, R., Seetharaman, P., Sudhir, K., Thomadsen, R., and Zhao, Y. (2002). Structural applications of the discrete choice model. Marketing Letters, 1373)2207-220.
Dunford, N. and Schwartz, T. (1957). Linear Operators. Part General Theory. New York Interscience.
Eckstein, Z. and Wolpin, K. I. (1989). The specification and estimation of dynamic stochastic discrete choice models: A survey, The Journal of Human Resources, 24(4):562-598.
Fazel, M., Ge, R., Kakade, S., and Mesbahi, M. (2018). Global convergence of policy gradient methods for the linear quadratic regulator. In International Conference on Machine Learning. pages 1475.
Haskell, W. B., Jain, R., and Kalathil, D. (2016). Empirical dynamic programming. Mathematics of Operations Research, 41 41(2):402-429,
Hendel, I. and Nevo, A. (2006). Measuring the implications of sales and consumer inventory behavior. Econometrica, 1436))1637-1673,
Hinderer, K. (2005). Lipschitz continuity of value functions in markovian decision processes. Mathematical Methods of Operations Research, 62(1):3-22.
Hotz, J. and Miller, R. A. (1993). Conditional choice probabilities and the estimation of dynamic models. The Review of Economic Studies, 60(3):497-529.
Jaksch, T., Ortner, R., and Auer, P. (2010). Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 163311))553311600
Müller, P. and Reich, G. (2018). Structural estimation using parametric mathematical programming with equilibrumm constraints and homotopy path continuation, Available SSRN 3303999.
Nekipelov, D., Syrgkanis, V., and Tardos, E. (2015). Econometrics for learning agents. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, pages 1-18. ACM.
Pirotta, M., Restelli, M., and Bascetta, L. (2015). Policy gradient in lipschitz markov decision processes. Machine Learning, 10052-3):25--28.
Rachelson, E. and Lagoudakis, M. G. (2010). On the locality action domination in sequential decision making.

---

Under review as a conference paper at ICLR 2020
Rust, J. (1987). Optimal replacement of gme bus engines: An empirical model of harold zurcher. Econometrica: Journal of the Econometric Society, pages 999-1033.
Rust, (1996). Numerical dynamic programming in economies. Handbook of computational economics, 1:619-729.
Sutton, R. S. and Barto. A. G. (2018). Reinforcement learning: An introduction. MIT press.
Williams, R. (1992). Simple statistical gradient- foolwing algorithms for connectionist reinforce- ment learning. Machine learning, 8(3-4):229-25 256.
APPENDIX
A OMITTED PROOF FOR THEOREM 3.1
Theorem 3.1. Value function Vg is twice Freéchet differentiable with respect to at the choice
probability 5 corresponding to optimal policy and its Fréchet derivative is negative at ó in all states s, i.e., ( O.
Proof. We start with the Bellman equation of the value function.
Vi(s) = - (()) r(s) - ((s) log (6(s))
- -11 (0) log - 6(s)) + B. [V(())(s){
First of all, note that in (7) the first three terms on the right hand side of the equation simple nonlinear functions 8(.) and thus the directional derivative with respect to 8(.) can be taken as an ordinary derivative with respect to
parameter. Next note that if functional Ja(-) is directionally differentiable with respect to d and for all h(-). J847 (0))== is invariant, then Js(+) is Fréchet differentiable with respect to 8 and the obove ratio is its Fréchet derivative. As a result, the Fréchet derivative of simple functional (1 5(s)) r(s) 5(s) log (8(s)) - (1 8(s)) log(1 - 8(s)) r(s). This expression is itself functional with Fréchet derivative equal to -1/((s) 8(s))), meaning
with respect to 8(-) exists and equal to log(1 - log(6(s))
Treéchet-differentiie that the original functional (1 8()) r(x) d(x) log (8(x) (1-8(s)) ((())))(s))) is twice
Fréchet diffcrentiable with the second Fréchet derivative -1/(((s((1 Whenever the state transition is affected by the individual decision we need to consider decomposition of the conditional
expectation with respect the future state:
E (5 [s} (1
8(s) E. (Va 1] 5(s) E. (V) 8, O,
Under standard technical conditions that allow the swap of the derivative and the integral
DE (Vs( (E. (V [) 0J E. (V )s,, 1]) + E. (DVs
Thus, the Fréchet derivative of the value function should be the fixed point of the following Bellman equation
DVa(s) (log(1 5(s) - log()(s)) - r(s))
(8)
+ 3 (E, (V.(:VV(''))ss0000 E, - 1J) + (DV3's)))))
and
D2Vs(8) 5(x)(1 8(s))
(9)
2DV |s, E. E=/(DVa(s')ss +
(DVVsss) (
Given that both these equations are Type II Fredholm integral equations for DVs(.) and (.))(.) which have unique solutions whenever < that are bounded and continuous (see Dunford and Schwartz 1957 and, thus, unique solutions for both equations exist and V-(-) is indeed Fréchet- differentiable. This means that the necessary condition for its optimum yielding ă is DV₃(s) for all states s. As a result, equation (9) implies that its second Fréchet derivative is negative for all states, V.e.DD2V 5 O.
10

---

Under review as a conference paper at ICLR 2020
B
OMITTED PROOFS IN SECTION 4
B.1 OMITTED PROOF OF THEOREM 4.
Theorem
Given an (Lr; Lip) Lipschiiz MDP, the optimal policy å satisfies
1 - 8(s) (1)(s)
1 (1-8(s))
(L,,
25 Lap 1- |s-
log
log
8(s)
8(st)
for all state s, E where Rmax max.es r(8) is the maximum of the immediate reward r over S.
Proof. At the optimal policy 8, the Fréchet derivative of the value function is zero, i.e., DVg(s) 0 for all state s. Therefore, from the Bellman equation we establish that
1 1- 8(s) 118(s) 8(s)
log
r(s) + (E, 18, E. (V)
Thus, for all states st S,
- E. - (v
I Va(s')(pss\ls,e) 1a:p0pp(ps1pp a))dss
Rmax
I R V26') p(61ss aa)dds
Ranxx
Rmax
{/L ((5))((''1sss)) -p(s's' a))ds sup 1111..1
Rmax
Rmax Lap 1s s²1
1-
where we use upper bounds supses Vg(s) S Bmax and
(2-9)
Vy(3')ll= $1. Thus,
Rmnax
1 1- 5(8) log
1 1
log
8(8)
8(st)
-|((s) - r(s") + 3 (E./ [V)(s')ss,))))))))))))))))))(( ]1,,1]] E. (v)
- 3 (E, [Vg(s') - E,, [Vg(s') 0))
< [r(s) r(s!) + E. [Vg(s']ss.1 E (V(s''s) 1]
+ 3 E. [V [V3(6))ss))]
Lr + 2 Rmax Lp ss-s
B.2 OMITTED PROOF OF THEOREM 4.2
Theorem 4.2 Given an (Iep -iipschttt MDP which satisfies the condition for global convergence
(6) the value function V3 is concave with respect policy in the Lipschitz policy space A, i.e., (.))(s)) < for all s E 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 (Lr, Lipschitt MDP, for all policies in the the Lipschitz policy space
A, the Fréchet derivative of the respective value function DV₂(.) 21, 40Rmsshp
1-8
-Lipschitz
1-28kp
11

---

Under review as a conference paper at ICLR 2020
continuous, i.e., for all states st S.
2L, + 43 Iee
DV - DVV(ss))
1-8
8 - s!|
- 23L
Proof. We begin with the Bellman equation ( for the Fréchet derivative of value function.
1 (1-8(3) )(s) r(s)
DVs(s) log
5(5)
+ + (Eg (Va(s))s (Va('ssss)s 1)) 3 E (VV
We use the concept of the contraction mapping to prove the result of the Lemma.
Definition B.1. Let T x + X be mapping from metric space X to itself,
T' is a contraction mapping (with modulus 7 E I, y E X,, where p is metric on X.
S vp(x, y) for all
x is fixed point of ifT(x)
Lemma B.2. Suppose that is a complete metric space and that - X is contraction mapping with modulus "y. Then,
T has a unique fixed point x².
X' S X is closed subset for which T(X') S X', then x² E X'.
Consider the contraction mapping (s())(s) log
8(x) r()) + 3 (E.
o(s)
E. [Vs{s')ss, 1]) (x(s))((s') then the Bellman equation implies that DV's the fixed point of contraction mapping Tg. Since the Lipschitz continuity property forms a closed subset, by Lemma B.2 it is sufficient show for any LDv continuous x. (x(x) is also -iv-Lisschiz continuous,
2L, 488may
where LDV
Thus, consider states st S,
1-20L
(s) - T(z)(s!)
1 56)(s) log
1 (1-((s))
log
(r(s)) r((t)]
8(s)
8(st)
+.3 3 E. (Va || - E, (Vo(s')ss o]1
+.8 3 (Va(')sss) [|, - [v(('))ss.1]]
+ 3 [z(2(s')sss0) 0(ss) E. [ ((s))
+ 3 [=(x((s)]s
(())) E. [x('')))) 1] 5(s)))
where
1 - 6(s)
1 (1-0(s))
23 2. Lip ) 8!
log
log
L, (r(s) r(8)) ITp st
8(8)
5(st)
3
by the same calculation in the proof of Theorem 4.1 for a = 0,
L, 2,3 2.3 Lip |s stl
E (V(s'))) E. (Vo(s))
12

---

Under review as a conference paper at ICLR 2020
and
[x(a(s)]|s,000(() E. [ 8(s))
1 (8(s) ((5)) p(s'ss p(s
p(s'ss =LDV 1/1e (ō(s) (()1))=((5)) (p(6'ls,a) p a))ds'
LDV
U (16))((8'(s,0)) p(s'ls' .a))dd 11/1ISS1
<Lov sup
-LDyK(pp(-ss,,))) p(-lsps.0)) a)) s LDv Lp |s st
where we use the bound [8(s) 8(s²) < 1 and thus (6()) ( 1|2. S 1. Similarly,
LDV
[x((((s') 1] (1 - 8(s) E. [s) , ,1] (1 (1-5(s))) S Lov s Combining all the bounds, we obtain that
48RmaxLp + +23L.D 11p s²1.
(s)) - T(x)()))) 2T,
1-3
Rama 2b,
Substitution LDv
1
yields the statement of the Lemma.
2
Proof of Theorem 4.2
From the Bellman equation 9 it sufficient to show
1
2 (BV
1] (DV
(10)
- (1)((15(s))
We bound both sides separately. Since the policy satisfies d(s) < 8(s) for all states s, and 0(s) exp(r(s))++ I 2- the left hand side can be bounded from below as
(exp( (Bmin) + +1)² exp(Rmin))
(1s) 8()) ((s)(1
Meanwhile, the righthand side can be bounded from above by Lemma B.I
Let LDv =
48 4.Raay 2h.
1-3
25L
2/ [ (DVs 0Jl
[
22
J.ss (V6(s')(p(s))) 1) p(s'ls 0))
-2lLnv 1 DVs(
(p(6'18, 0))ds'
JUES LDV
{1le
<2BLDV sup I1
((d)((()(sss)) - -p(sslss,)))) ())ss)))sss
2BLp
4,3 4.3
-28LnyK(p(lss, 11, 1),((11s,0)
2T,
23I
$
From the condition of global convergence
1- 1-2,L, 2L, + 43Rmmx Lop
2
(exp(Rmin) + 1)² expl (Rmin))
1-
it follows that the inequality (10) is satisfied and the Bellman equation 9 implies that D2V)(s) 00 for all states S.
13

---

Under review as a conference paper at ICLR 2020
B.3
OMITTED PROOF OF TEOORMM 4.3
For notation simplicity, we introduce notations m and M such that
1
(exp(Bmin) + +1)
2
43 4. Lip
m
2L, +
1-3
exp(Rmii)
1 p
3
exp 1-B Ranax
Rmin +1
1
M
(1 -)
(1 - 3)2
exp(
1-1 Rinx
Rmiu)
1
+28 exp
1 1- Ramax
Ruinn
+ 1
Rmaax - (1 + (3 3
2
Theorem Given a (Ly, Lpp--iischitz MDP, which satisfies the condition for global convergence
6 and constants m and M defined above, for any step size a S M.. the policy gradient initialized at
the myopic policy 8 and updating 8 <- & in the bounded Lipschitz policy space Å after iterations, it produces policy 8(k) satisfying
Vi((s) Visi (8) v (1- crm)*
(exp( (mmin)) + 1)²
at all 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/8 with respect to the policy 8 from above and from below by m and M respectively.
Lemma B.3. Given a (Lr, -iiscchtt MDP, which satisfies the condition for global convergence 6). for all policies 5 in the bounded Lipschitz policy space Á. for all states E S, the second Fréchet derivative of the value function Va with respect to the policy is upperbounded as
D²v S m.
Proof. The Bellman equation implies that
max (s) S 1 min 8(s) 5(s))
+ 23 max (DVss) -
E,, Ev,("V(('')ss
By the same argument as in Theorem 4.2
min 1 ((s)(1-86)) 2
(xp((mmi)) + 1)² exp(Rmin)
23Lp
2L, + 4. Lop
(DV E, [DV 1 13LL,
1
Thus, for state E S,
D2Vs(8) < -m.
Lemma B.4. Given a (Le, Lp) Lipschiiz, MDP, which satisfies the condition for global convergence, for all policy in the bounded Lipschitz policy space Å, for all state the second derivative of the value function Va with respect to the policy ó is is lowerbounded as
D²Vo(s) 2 -M.
Proof. The Bellman equation (9) implies that
1 max 8(s)(1 8(s))
1
min DiV(ss)(()
1-8
23 min (V) max (VV)))
14

---

Under review as a conference paper at ICLR 2020
By restricting policy to the bounded Lipschitz policy space Å bound
exp
1-B Rmax
Runin
+1)
max 0(s)(1 8(5)) S max 0(s) 2(s))
exp(
I-B
| Rmax 2 Rmin)
Provided
min Va(8) 2 Rmin
2
R
max Vo(s) v
1 B
- ((s)
1 - 1--(s)
min log
r(s)
2 min log
- -r(s) = 0
6(s)
8(s)
1 - 1-8(s)
1- ((s)
max log
- r(s)
s max log
min r(s)
8(s)
8(s)
8
S exp
Rmaax
Rmin
Ramin
B
2
follows from Bellman equation 8 that
8(s)
min DVs(s) 2 - 8
min
log
- r(s) + 3(min Vo(s) max Vi(())
8(s)
Rmin
Remxx
- B
2
1
3
8(s)
max (V)(s) S
max
log
-(()) 3(max Vo(s) min Va (x())
B
((s)
B
2 Rmin
exp
R Rmax
Rmin
+
Rmax
B
8
2
1
Thus, for all state E S,
D²Va(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-LLipschizz ) functions (cf. Bansal and Gupta 2017).
L
C MORE RESULTS IN SECTION 5
Algorithm "Lazy projection", (II,..., Nx): thresholds corresponding to discretized state space Sl,...,8N): ((-): logistic function; policy d5 L(Tz); step size; 7: termination tolerance
1: m <- u(s1)..... N u(8x) // Initialize (0) at the myopic policy (8t) S do
2: while max; [DV g(k)
(Ko)
(k-1)
D D V (s:) [(T (( )1 L(m,
(k-1) (((((=11)) for all E [N]
3:
(k)
(k))
the closest monotone thresholds of (M (k+) x (ke)) // Lazy projection
4:
(T)
T
5: return (T
We list the convergence of gradient descent and its derivative, second derivative at smaller discount factor 3 0.9.
15

---

Under review as a conference paper at ICLR 2020
Commaag Uio aecig dug... 2001
Denvegees of palky
5 mmme
2
2 19m9
0:00
339000
23000
030300
C30.00
Figure Convergence of gradient descent, discount factor 3 0.9
-100000
Velue Po Secord Desivetive
300000
N217
000050
-100000
2000
.800000
Ilorttion
Figure 4: Performance of the norm max; [DV((s:) and the second derivative max; (DV)(ss)), discount factor 3 = 0.9
16


Reviews:
[{"review_id": "ryg-vTdpKB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper is consider dynamic discrete choice models. It shows in an important class of discrete choice models the value function is globally concave in the policy, implying that for example policy gradients are globally convergent and are likely to converge faster in practice compared to fix-point approaches. \n\nThe paper is very well written and structured. It present convergence results together with a sanity check implementation. However, as an informed outsider, I am also a little bit confused. As far as I understand, Rust (1987) is also using gradient descent. Indeed the problem might not be convex/concave and hence this might get trapped in local minima. Moreover, Ermon et al. (AAAI 2015) have already shown that Dynamic Discrete Choice models are equivalent to Maximum Entropy IRL models under some conditions. Then they provide an algorithm that is kind of close (at least in spirit) to policy gradient. The propose to \"simultaneously update the current parameter estimate θ (Learning) while we iterate over time steps t to fill columns of the DP table (Planning)\". Indeed, this is still not giving guarantees, but the together with Ho et al. (ICML 2016) it suggests that the take-away message \"use police gradients\" for dynamic discrete choice models is actually known in the literature. This should bee clarified. Generally, the paper is providing a lot of focus on the economics literature. While this is of course fine, the authors should clarify what is already known in the AI and ML literature (including the work described above). \n\nNevertheless, the proof that there are convergent policy gradients for some dynamic discrete choice models appears interesting, at least to an informed outsider. However, this results heavily hinges on e.g. (Pirotta 2015). So the main novelty seems to be in Sections 4.3 and 4.4. Here is where they make use of their assumption. So, the only point, in my opinion, that should be clarified is the usefulness of the considered class. For an informed outsider, this is not easy to see. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "r1lqaMWaqB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThis class of models, modelled as a MDP with choice-specific heterogeneity, is challenging as not all the payoffs received by the agents is externally observable. One solution in this case is finding a balance condition and a functional fixed point to find the optimal policy (closely related to value function iteration), and this is apparently the key idea behind ‘nested fixed point’ methods used in Econometrics.\n\nThe paper proposes an alternative. First it identifies a subclass of discrete choice models (essentially MDP with stochastic rewards) where the value function is globally concave in the policy. The consequence of this observation is that a direct method, such as the policy gradient that circumvents explicitly estimating the value function, can (at least in principle) converge to the optimal policy without calculating a fixed point. The authors illustrate computational advantages of this direct approach. Moreover, the generality of the policy gradient method enables the relaxation of extra assumptions regarding the behaviour of agents while facilitating a wider applicability/econometric analysis. \n\nThe key contribution claimed by the paper is the observation that in the class of dynamic discrete choice models with unobserved heterogeneity, the value function is globally concave in the policy. This enables using computationally efficient policy gradient algorithms with convergence guarantees for this class of problems. The authors also claim that the simplicity of policy gradient makes it also a viable model for understanding economic behaviour in econometric analysis, and more broadly for social sciences.\n\nThe paper deals with Discrete choice models with unobserved heterogeneity as a special class of MDP’s and is relevant to ICLR. However, the writing style is quite technical and terse -- while I could appreciate the rigour, the authors develop the basic material until page 5 -- Notation is also somewhat non-standard at places (alternating using delta or sigma for a policy and pi for thresholds of an exponential softmax distribution) and makes it harder to see the additional structure from generic MDPs more familiar in RL. I suspect that a reader more familiar with the relevant econometric, marketing and finance literature could follow the model description more easily. \n\nThere are a number of assumptions in the paper, especially 2.4 and 2.5 that relate to the monotonicity and ordering of the states. These assumptions seem to be important in subsequent developments for showing the concavity but they seem to be coming from out of the blue. Unfortunately the authors do not provide any intuition/discussion -- an example problem with these properties would make these assumptions more concrete. I was hoping to find such an example in the empirical application however this section does not make the necessary connections with the theoretical development. There are not even references to basic claims \ndone in the abstract, for example, I am not able to find an illustration of ‘significant computational advantages in using a simple implementation policy gradient algorithm over existing “nested fixed point” algorithms used in Econometrics’. The lack of any conclusions makes it also hard for me to appreciate the contributions.\n\n\nMinor:\n\nAbstract:  \n.. Existing work in Econometrics assumes that optimizing agents are fully rational and requires finding a functional fixed point to find the optimal policy. …\n\nAmbiguous sentence: Existing work in Econometrics [...] requires finding a functional fixed point to find the optimal policy.\n\nTheorem 3.1 and elsewhere  Freéchet =>  Fréchet\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "H1x72FypKB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThis 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:\n\n1. 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?\n\n2. 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.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors develop theoretical results showing that policy gradient methods converge to the globally optimal policy for a class of MDPs arising in econometrics. The authors show empirically that their methods perform on a standard benchmark.

The paper contains interesting theoretical results. However, the reviewers were concerned about some aspects:
1) The paper does not explain to a general ML audience the significance of the models considered in the paper - where do these arise in practical applications? Further, the experiments are also limited to a small MDP - while this may be a standard benchmark in econometrics, it would be good to study the algorithm's scaling properties to larger models as is standard practice in RL.

2) The implications of the assumptions made in the paper are not explained clearly, nor are the relative improvements of the authors' work relative to prior work. In particular, one reviewer was concerned that the assumptions could be trivially satisfied and the authors' rebuttal did not clarify this sufficiently.

Thus, I recommend rejection but am unsure since none of the reviewers nor I am an expert in this area.
Decision: Reject