Nous avons étudié la dynamique de Glauber sur les pavages de domaines finies du plan par des losanges ou par des dominos de taille 2 × 1. Ces pavages sont naturellement associés à des surfaces de R^3, qui peuvent être vues comme des interfaces dans des modèles de physique statistique. En particulier les pavages par des losanges correspondent au modèle d'Ising tridimensionnel à température nulle. Plus précisément les pavages d'un domaine sont en bijection avec les configurations d'Ising vérifiant certaines conditions au bord (dépendant du domaine pavé). Ces conditions forcent la coexistence des phases + et - ainsi que la position du bord de l'interface. Dans la limite thermodynamique où L, la longueur caractéristique du système, tend vers l'infini, ces interfaces obéissent à une loi des grand nombre et convergent vers une forme limite déterministe ne dépendant que des conditions aux bord. Dans le cas où la forme limite est planaire et pour les losanges, Caputo, Martinelli et Toninelli [CMT12] ont montré que le temps de mélange Tmix de la dynamique est d'ordre O(L^{2+o(1)}) (scaling diffusif). Nous avons généralisé ce résultat aux pavages par des dominos, toujours dans le cas d'une forme limite planaire. Nous avons aussi prouvé une borne inférieure Tmix ≥ cL^2 qui améliore d'un facteur log le résultat de [CMT12]. Dans le cas où la forme limite n'est pas planaire, elle peut être analytique ou bien contenir des parties "gelées" où elle est en un sens dégénérée. Dans le cas où elle n'a pas de telle partie gelée, et pour les pavages par des losanges, nous avons montré que la dynamique de Glauber devient "macroscopiquement proche" de l'équilibre en un temps L^{2+o(1)}

Le temps de mélange de la chaîne de Markov induite par une politique limite ses performances dans les scénarios réels d'apprentissage continu. Pourtant, l'effet des temps de mélange sur l'apprentissage dans l'apprentissage par renforcement (RL) continu reste peu exploré. Dans cet article, nous caractérisons des problèmes qui sont d'un intérêt à long terme pour le développement de l'apprentissage continu, que nous appelons processus de décision markoviens (MDP) « extensibles » (scalable), à travers le prisme des temps de mélange. En particulier, nous établissons théoriquement que les MDP extensibles ont des temps de mélange qui varient de façon polynomiale avec la taille du problème. Nous démontrons ensuite que les temps de mélange polynomiaux présentent des difficultés importantes pour les approches existantes, qui souffrent d'un biais myope et d'estimations à base de ré-échantillonnage avec remise ensembliste (bootstrapping) périmées. Pour valider notre théorie, nous étudions la complexité des temps de mélange en fonction du nombre de tâches et de la durée des tâches pour des politiques très performantes déployées sur plusieurs jeux Atari. Notre analyse démontre à la fois que des temps de mélange polynomiaux apparaissent en pratique et que leur existence peut conduire à un comportement d'apprentissage instable, comme l'oubli catastrophique dans des contextes d'apprentissage continu. / The mixing time of the Markov chain induced by a policy limits performance in real-world continual learning scenarios. Yet, the effect of mixing times on learning in continual reinforcement learning (RL) remains underexplored. In this paper, we characterize problems that are of long-term interest to the development of continual RL, which we call scalable MDPs, through the lens of mixing times. In particular, we theoretically establish that scalable MDPs have mixing times that scale polynomially with the size of the problem. We go on to demonstrate that polynomial mixing times present significant difficulties for existing approaches, which suffer from myopic bias and stale bootstrapped estimates. To validate our theory, we study the empirical scaling behavior of mixing times with respect to the number of tasks and task duration for high performing policies deployed across multiple Atari games. Our analysis demonstrates both that polynomial mixing times do emerge in practice and how their existence may lead to unstable learning behavior like catastrophic forgetting in continual learning settings.

Nous avons étudié la dynamique de Glauber sur les pavages de domaines finies du plan par des losanges ou par des dominos de taille 2 × 1. Ces pavages sont naturellement associés à des surfaces de R^3, qui peuvent être vues comme des interfaces dans des modèles de physique statistique. En particulier les pavages par des losanges correspondent au modèle d'Ising tridimensionnel à température nulle. Plus précisément les pavages d'un domaine sont en bijection avec les configurations d'Ising vérifiant certaines conditions au bord (dépendant du domaine pavé). Ces conditions forcent la coexistence des phases + et - ainsi que la position du bord de l'interface. Dans la limite thermodynamique où L, la longueur caractéristique du système, tend vers l'infini, ces interfaces obéissent à une loi des grand nombre et convergent vers une forme limite déterministe ne dépendant que des conditions aux bord. Dans le cas où la forme limite est planaire et pour les losanges, Caputo, Martinelli et Toninelli [CMT12] ont montré que le temps de mélange Tmix de la dynamique est d'ordre O(L^{2+o(1)}) (scaling diffusif). Nous avons généralisé ce résultat aux pavages par des dominos, toujours dans le cas d'une forme limite planaire. Nous avons aussi prouvé une borne inférieure Tmix ≥ cL^2 qui améliore d'un facteur log le résultat de [CMT12]. Dans le cas où la forme limite n'est pas planaire, elle peut être analytique ou bien contenir des parties “gelées” où elle est en un sens dégénérée. Dans le cas où elle n'a pas de telle partie gelée, et pour les pavages par des losanges, nous avons montré que la dynamique de Glauber devient “macroscopiquement proche” de l'équilibre en un temps L^{2+o(1)} / We studied the Glauber dynamics on tilings of finite regions of the plane by lozenges or 2 × 1 dominoes. These tilings are naturally associated with surfaces of R^3, which can be seen as interfaces in statistical physics models. In particular, lozenge tilings correspond to three dimensional Ising model at zero temperature. More precisely, tilings of a finite regions are in bijection with Ising configurations with some boundary conditions (depending on the tiled domain). These boundary conditions impose the coexistence of the + and - phases, together with the position of the boundary of the interface. In the thermodynamic limit where L, the characteristic length of the system, tends toward infinity, these interface follow a law of large number and converge to a deterministic limit shape depending only on the boundary condition. When the limit shape is planar and for lozenge tilings, Caputo, Martinelli and Toninelli [CMT12] showed that the mixing time of the dynamics is of order (L^{2+o(1)}) (diffusive scaling). We generalized this result to domino tilings, always in the case of a planar limit shape. We also proved a lower bound Tmix ≥ cL^2 which improve on the result of [CMT12] by a log factor. When the limit shape is not planar, it can either be analytic or have some “frozen” domains where it is degenerated in a sense. When it does not have such frozen region, and for lozenge tilings, we showed that the Glauber dynamics becomes “macroscopically close” to equilibrium in a time L^{2+o(1)}

La première partie de cette thèse concerne l'inférence de modèles statistiques non normalisés. Nous étudions deux méthodes d'inférence basées sur de l'échantillonnage aléatoire : Monte-Carlo MLE (Geyer, 1994), et Noise Contrastive Estimation (Gutmann et Hyvarinen, 2010). Cette dernière méthode fut soutenue par une justification numérique d'une meilleure stabilité, mais aucun résultat théorique n'avait encore été prouvé. Nous prouvons que Noise Contrastive Estimation est plus robuste au choix de la distribution d'échantillonnage. Nous évaluons le gain de précision en fonction du budget computationnel. La deuxième partie de cette thèse concerne l'échantillonnage aléatoire approché pour les distributions de grande dimension. La performance de la plupart des méthodes d’échantillonnage se détériore rapidement lorsque la dimension augmente, mais plusieurs méthodes ont prouvé leur efficacité (e.g. Hamiltonian Monte Carlo, Langevin Monte Carlo). Dans la continuité de certains travaux récents (Eberle et al., 2017 ; Cheng et al., 2018), nous étudions certaines discrétisations d’un processus connu sous le nom de kinetic Langevin diffusion. Nous établissons des vitesses de convergence explicites vers la distribution d'échantillonnage, qui ont une dépendance polynomiale en la dimension. Notre travail améliore et étend les résultats de Cheng et al. pour les densités log-concaves. / The first part of this thesis concerns the inference of un-normalized statistical models. We study two methods of inference based on sampling, known as Monte-Carlo MLE (Geyer, 1994), and Noise Contrastive Estimation (Gutmann and Hyvarinen, 2010). The latter method was supported by numerical evidence of improved stability, but no theoretical results had yet been proven. We prove that Noise Contrastive Estimation is more robust to the choice of the sampling distribution. We assess the gain of accuracy depending on the computational budget. The second part of this thesis concerns approximate sampling for high dimensional distributions. The performance of most samplers deteriorates fast when the dimension increases, but several methods have proven their effectiveness (e.g. Hamiltonian Monte Carlo, Langevin Monte Carlo). In the continuity of some recent works (Eberle et al., 2017; Cheng et al., 2018), we study some discretizations of the kinetic Langevin diffusion process and establish explicit rates of convergence towards the sampling distribution, that scales polynomially fast when the dimension increases. Our work improves and extends the results established by Cheng et al. for log-concave densities.