Dynamic Programming Approaches for Estimating and Applying Large-scale Discrete Choice Models

People go through their life making all kinds of decisions, and some of these decisions affect their demand for transportation, for example, their choices of where to live and where to work, how and when to travel and which route to take. Transport related choices are typically time dependent and characterized by large number of alternatives that can be spatially correlated. This thesis deals with models that can be used to analyze and predict discrete choices in large-scale networks. The proposed models and methods are highly relevant for, but not limited to, transport applications. We model decisions as sequences of choices within the dynamic discrete choice framework, also known as parametric Markov decision processes. Such models are known to be difficult to estimate and to apply to make predictions because dynamic programming problems need to be solved in order to compute choice probabilities. In this thesis we show that it is possible to explore the network structure and the flexibility of dynamic programming so that the dynamic discrete choice modeling approach is not only useful to model time dependent choices, but also makes it easier to model large-scale static choices. The thesis consists of seven articles containing a number of models and methods for estimating, applying and testing large-scale discrete choice models. In the following we group the contributions under three themes: route choice modeling, large-scale multivariate extreme value (MEV) model estimation and nonlinear optimization algorithms. Five articles are related to route choice modeling. We propose different dynamic discrete choice models that allow paths to be correlated based on the MEV and mixed logit models. The resulting route choice models become expensive to estimate and we deal with this challenge by proposing innovative methods that allow to reduce the estimation cost. For example, we propose a decomposition method that not only opens up for possibility of mixing, but also speeds up the estimation for simple logit models, which has implications also for traffic simulation. Moreover, we compare the utility maximization and regret minimization decision rules, and we propose a misspecification test for logit-based route choice models. The second theme is related to the estimation of static discrete choice models with large choice sets. We establish that a class of MEV models can be reformulated as dynamic discrete choice models on the networks of correlation structures. These dynamic models can then be estimated quickly using dynamic programming techniques and an efficient nonlinear optimization algorithm. Finally, the third theme focuses on structured quasi-Newton techniques for estimating discrete choice models by maximum likelihood. We examine and adapt switching methods that can be easily integrated into usual optimization algorithms (line search and trust region) to accelerate the estimation process. The proposed dynamic discrete choice models and estimation methods can be used in various discrete choice applications. In the area of big data analytics, models that can deal with large choice sets and sequential choices are important. Our research can therefore be of interest in various demand analysis applications (predictive analytics) or can be integrated with optimization models (prescriptive analytics). Furthermore, our studies indicate the potential of dynamic programming techniques in this context, even for static models, which opens up a variety of future research directions.

Sequential Machine learning Approaches for Portfolio Management

Cette thèse envisage un ensemble de méthodes permettant aux algorithmes d'apprentissage statistique de mieux traiter la nature séquentielle des problèmes de gestion de portefeuilles financiers. Nous débutons par une considération du problème général de la composition d'algorithmes d'apprentissage devant gérer des tâches séquentielles, en particulier celui de la mise-à-jour efficace des ensembles d'apprentissage dans un cadre de validation séquentielle. Nous énumérons les desiderata que des primitives de composition doivent satisfaire, et faisons ressortir la difficulté de les atteindre de façon rigoureuse et efficace. Nous poursuivons en présentant un ensemble d'algorithmes qui atteignent ces objectifs et présentons une étude de cas d'un système complexe de prise de décision financière utilisant ces techniques. Nous décrivons ensuite une méthode générale permettant de transformer un problème de décision séquentielle non-Markovien en un problème d'apprentissage supervisé en employant un algorithme de recherche basé sur les K meilleurs chemins. Nous traitons d'une application en gestion de portefeuille où nous entraînons un algorithme d'apprentissage à optimiser directement un ratio de Sharpe (ou autre critère non-additif incorporant une aversion au risque). Nous illustrons l'approche par une étude expérimentale approfondie, proposant une architecture de réseaux de neurones spécialisée à la gestion de portefeuille et la comparant à plusieurs alternatives. Finalement, nous introduisons une représentation fonctionnelle de séries chronologiques permettant à des prévisions d'être effectuées sur un horizon variable, tout en utilisant un ensemble informationnel révélé de manière progressive. L'approche est basée sur l'utilisation des processus Gaussiens, lesquels fournissent une matrice de covariance complète entre tous les points pour lesquels une prévision est demandée. Cette information est utilisée à bon escient par un algorithme qui transige activement des écarts de cours (price spreads) entre des contrats à terme sur commodités. L'approche proposée produit, hors échantillon, un rendement ajusté pour le risque significatif, après frais de transactions, sur un portefeuille de 30 actifs.

A Theoretical Comparison Between Integrated and Realized Volatilies

In this paper, we provide both qualitative and quantitative measures of the cost of measuring the integrated volatility by the realized volatility when the frequency of observation is fixed. We start by characterizing for a general diffusion the difference between the realized and the integrated volatilities for a given frequency of observations. Then, we compute the mean and variance of this noise and the correlation between the noise and the integrated volatility in the Eigenfunction Stochastic Volatility model of Meddahi (2001a). This model has, as special examples, log-normal, affine, and GARCH diffusion models. Using some previous empirical works, we show that the standard deviation of the noise is not negligible with respect to the mean and the standard deviation of the integrated volatility, even if one considers returns at five minutes. We also propose a simple approach to capture the information about the integrated volatility contained in the returns through the leverage effect.

A model of dynamic liquidity contracts

I study long-term financial contracts between lenders and borrowers in the absence of perfect enforceability and when both parties are credit constrained. Borrowers repeatedly have projects to undertake and need external financing. Lenders can commit to contractual agreements whereas borrowers can renege any period. I show that equilibrium contracts feature interesting dynamics: the economy exhibits efficient investment cycles; absence of perfect enforcement and shortage of capital skew the cycles toward states of liquidity drought; credit is rationed if either the lender has too little capital or if the borrower has too little collateral. This paper's technical contribution is its demonstration of the existence and characterization of financial contracts that are solutions to a non-convex dynamic programming problem.

Approches générales de résolution pour les problèmes multi-attributs de tournées de véhicules et confection d'horaires

Thèse réalisée en cotutelle entre l'Université de Montréal et l'Université de Technologie de Troyes

A dynamic sequential route choice model for micro-simulation

Dans les études sur le transport, les modèles de choix de route décrivent la sélection par un utilisateur d’un chemin, depuis son origine jusqu’à sa destination. Plus précisément, il s’agit de trouver dans un réseau composé d’arcs et de sommets la suite d’arcs reliant deux sommets, suivant des critères donnés. Nous considérons dans le présent travail l’application de la programmation dynamique pour représenter le processus de choix, en considérant le choix d’un chemin comme une séquence de choix d’arcs. De plus, nous mettons en œuvre les techniques d’approximation en programmation dynamique afin de représenter la connaissance imparfaite de l’état réseau, en particulier pour les arcs éloignés du point actuel. Plus précisément, à chaque fois qu’un utilisateur atteint une intersection, il considère l’utilité d’un certain nombre d’arcs futurs, puis une estimation est faite pour le restant du chemin jusqu’à la destination. Le modèle de choix de route est implanté dans le cadre d’un modèle de simulation de trafic par événements discrets. Le modèle ainsi construit est testé sur un modèle de réseau routier réel afin d’étudier sa performance.

Étude de cas sur l’ajout de vecteurs d’enregistrements typés dans Gambit Scheme

Dans le but d’optimiser la représentation en mémoire des enregistrements Scheme dans le compilateur Gambit, nous avons introduit dans celui-ci un système d’annotations de type et des vecteurs contenant une représentation abrégée des enregistrements. Ces derniers omettent la référence vers le descripteur de type et l’entête habituellement présents sur chaque enregistrement et utilisent plutôt un arbre de typage couvrant toute la mémoire pour retrouver le vecteur contenant une référence. L’implémentation de ces nouvelles fonctionnalités se fait par le biais de changements au runtime de Gambit. Nous introduisons de nouvelles primitives au langage et modifions l’architecture existante pour gérer correctement les nouveaux types de données. On doit modifier le garbage collector pour prendre en compte des enregistrements contenants des valeurs hétérogènes à alignements irréguliers, et l’existence de références contenues dans d’autres objets. La gestion de l’arbre de typage doit aussi être faite automatiquement. Nous conduisons ensuite une série de tests de performance visant à déterminer si des gains sont possibles avec ces nouvelles primitives. On constate une amélioration majeure de performance au niveau de l’allocation et du comportement du gc pour les enregistrements typés de grande taille et des vecteurs d’enregistrements typés ou non. De légers surcoûts sont toutefois encourus lors des accès aux champs et, dans le cas des vecteurs d’enregistrements, au descripteur de type.

Lutte intégrée au roseau commun : prévention, confinement et éradication

Les plantes envahissantes menacent la biodiversité ainsi que les activités humaines. Afin de les maîtriser, la pulvérisation d'herbicides est une méthode fréquemment employée en Amérique du Nord. Cette approche ne fait pas toujours consensus et est même parfois interdite ou restreinte, ce qui justifie le recours à d'autres options. Les alternatives peuvent toutefois s'avérer rares, comporter d'importantes limitations ou sont peu documentées. Cette étude vise à tester l’efficacité de méthodes permettant de maîtriser et de prévenir les invasions de roseau commun (Phragmites australis), l'une des plantes envahissantes les plus problématiques sur le continent nord-américain, tout en limitant au minimum l'utilisation d'herbicides. Le potentiel de quatre méthodes de lutte aux petites populations de roseau bien établies a d'abord été évalué : l’excavation avec enfouissement sur place, le bâchage, l’excavation avec enfouissement sur place combinée au bâchage, et la fauche répétée. Les résultats ont montré que l'excavation avec enfouissement sur place, avec ou sans bâchage, a entraîné une élimination presque totale des populations visées, ce qui est comparable ou supérieur à l'effet généralement obtenu avec la pulvérisation d'herbicide. Le bâchage avec des toiles opaques, maintenues pendant un an, a pour sa part entraîné une maîtrise partielle du roseau, suggérant qu'une application prolongée serait nécessaire pour l'éradication de la plante. La fauche répétée, exécutée à raison de cinq fauches par été pendant deux ans, a fourni une efficacité mitigée. Les résultats suggèrent néanmoins que la fauche pendant plusieurs années contribue à affaiblir la plante, ce qui pourrait aider à son confinement. Une méthode additionnelle a été expérimentée afin de traiter les tiges éparses de roseau tout en limitant les risques d'effets hors cibles, soit le badigeonnage manuel d’herbicide. Suite à ces tests, les résultats ont montré une diminution importante de la densité des tiges, ce qui suggère que la méthode est efficace afin d'éliminer les repousses après un traitement initial, et pourrait également être employée sur de jeunes populations clairsemées. L'effet d'un ensemencement préventif de plantes herbacées sur l'établissement de semis de roseau a également été étudié, suite à des traitements sur de vastes parcelles de sol nu. Les résultats suggèrent que la méthode est efficace afin de limiter la propagation du roseau par semences et qu'un suivi périodique suite à l'intervention serait suffisant afin de maintenir l'effet préventif.

The management of innovation under ambiguity

De récents développements en théorie de la decision ont largement enrichi notre connaissance de la notion d'incertitude knightienne, usuellement appelée ambiguïté. Néanmoins ces dévelopement tardent à être intégrés au coeur de la théorie économique. Nous suggérons que l'analyse de phénonèmes économiques tel que l'innovation et la Recherche et Développement gagnerait à intégrer les modèles de décision en situation d'ambiguïté. Nous étayons notre propos en analysant l'allocation des droits de propriété d'une découverte. Les deux premières parties de la présentation s'inspire d'un modèle d'Aghion et de Tirole, The Management of Innovation, portant sur l'allocation des droits de propriété entre une unité de recherche et un investisseur. Il est démontré qu'un désaccord entre les agents sur la technologie de recherche affecte leur niveau d'effort, l'allocation des droits de propriété et l'allocation des revenus subséquents. Finalement, nous examinons une situation où plusieurs chercheurs sont en compétition en s'inspirant du traitement de l'incertitude de Savage. La présence d'ambuïgité affecte le comportement des agents et l'allocation des droits de propriétés de manière qui n'est pas captée en assumant l'hypothèse de risque.