Search

A number of deep reinforcement-learning (RL) approaches propose to control traffic signals. In this work, we study the robustness of such methods along two axes. First, sensor failures and GPS occlusions create missing-data challenges and we show that recent methods remain brittle in the face of these missing data. Second, we provide a more systematic study of the generalization ability of RL methods to new networks with different traffic regimes. Again, we identify the limitations of recent approaches. We then propose using a combination of distributional and vanilla reinforcement learning through a policy ensemble. Building upon the state-of-the-art previous model which uses a decentralized approach for large-scale traffic signal control with graph convolutional networks (GCNs), we first learn models using a distributional reinforcement learning (DisRL) approach. In particular, we use implicit quantile networks (IQN) to model the state-action return distribution with quantile regression. For traffic signal control problems, an ensemble of standard RL and DisRL yields superior performance across different scenarios, including different levels of missing sensor data and traffic flow patterns. Furthermore, the learning scheme of the resulting model can improve zero-shot transferability to different road network structures, including both synthetic networks and real-world networks (e.g., Luxembourg, Manhattan). We conduct extensive experiments to compare our approach to multi-agent reinforcement learning and traditional transportation approaches. Results show that the proposed method improves robustness and generalizability in the face of missing data, varying road networks, and traffic flows.

Throughout its history, Operational Research has evolved to include a variety of methods, models and algorithms that have been applied to a diverse and wide range of contexts. This encyclopedic article consists of two main sections: methods and applications. The first aims to summarise the up-to-date knowledge and provide an overview of the state-of-the-art methods and key developments in the various subdomains of the field. The second offers a wide-ranging list of areas where Operational Research has been applied. The article is meant to be read in a nonlinear fashion. It should be used as a point of reference or first-port-of-call for a diverse pool of readers: academics, researchers, students, and practitioners. The entries within the methods and applications sections are presented in alphabetical order. The authors dedicate this paper to the 2023 Turkey/Syria earthquake victims. We sincerely hope that advances in OR will play a role towards minimising the pain and suffering caused by this and future catastrophes.

Bayesian causal structure learning aims to learn a posterior distribution over directed acyclic graphs (DAGs), and the mechanisms that define the relationship between parent and child variables. By taking a Bayesian approach, it is possible to reason about the uncertainty of the causal model. The notion of modelling the uncertainty over models is particularly crucial for causal structure learning since the model could be unidentifiable when given only a finite amount of observational data. In this paper, we introduce a novel method to jointly learn the structure and mechanisms of the causal model using Variational Bayes, which we call Variational Bayes-DAG-GFlowNet (VBG). We extend the method of Bayesian causal structure learning using GFlowNets to learn not only the posterior distribution over the structure, but also the parameters of a linear-Gaussian model. Our results on simulated data suggest that VBG is competitive against several baselines in modelling the posterior over DAGs and mechanisms, while offering several advantages over existing methods, including the guarantee to sample acyclic graphs, and the flexibility to generalize to non-linear causal mechanisms.

Cutting planes are essential for solving mixed-integer linear problems (MILPs), because they facilitate bound improvements on the optimal solution value. For selecting cuts, modern solvers rely on manually designed heuristics that are tuned to gauge the potential effectiveness of cuts. We show that a greedy selection rule explicitly looking ahead to select cuts that yield the best bound improvement delivers strong decisions for cut selection - but is too expensive to be deployed in practice. In response, we propose a new neural architecture (NeuralCut) for imitation learning on the lookahead expert. Our model outperforms standard baselines for cut selection on several synthetic MILP benchmarks. Experiments with a B&C solver for neural network verification further validate our approach, and exhibit the potential of learning methods in this setting., ICML 2022

Continual learning (CL) enables the development of models and agents that learn from a sequence of tasks while addressing the limitations of standard deep learning approaches, such as catastrophic forgetting. In this work, we investigate the factors that contribute to the performance differences between task-agnostic CL and multi-task (MTL) agents. We pose two hypotheses: (1) task-agnostic methods might provide advantages in settings with limited data, computation, or high dimensionality, and (2) faster adaptation may be particularly beneficial in continual learning settings, helping to mitigate the effects of catastrophic forgetting. To investigate these hypotheses, we introduce a replay-based recurrent reinforcement learning (3RL) methodology for task-agnostic CL agents. We assess 3RL on a synthetic task and the Meta-World benchmark, which includes 50 unique manipulation tasks. Our results demonstrate that 3RL outperforms baseline methods and can even surpass its multi-task equivalent in challenging settings with high dimensionality. We also show that the recurrent task-agnostic agent consistently outperforms or matches the performance of its transformer-based counterpart. These findings provide insights into the advantages of task-agnostic CL over task-aware MTL approaches and highlight the potential of task-agnostic methods in resource-constrained, high-dimensional, and multi-task environments.

Rapid development of large-scale pre-training has resulted in foundation models that can act as effective feature extractors on a variety of downstream tasks and domains. Motivated by this, we study the efficacy of pre-trained vision models as a foundation for downstream continual learning (CL) scenarios. Our goal is twofold. First, we want to understand the compute-accuracy trade-off between CL in the raw-data space and in the latent space of pre-trained encoders. Second, we investigate how the characteristics of the encoder, the pre-training algorithm and data, as well as of the resulting latent space affect CL performance. For this, we compare the efficacy of various pre-trained models in large-scale benchmarking scenarios with a vanilla replay setting applied in the latent and in the raw-data space. Notably, this study shows how transfer, forgetting, task similarity and learning are dependent on the input data characteristics and not necessarily on the CL algorithms. First, we show that under some circumstances reasonable CL performance can readily be achieved with a non-parametric classifier at negligible compute. We then show how models pre-trained on broader data result in better performance for various replay sizes. We explain this with representational similarity and transfer properties of these representations. Finally, we show the effectiveness of self-supervised pre-training for downstream domains that are out-of-distribution as compared to the pre-training domain. We point out and validate several research directions that can further increase the efficacy of latent CL including representation ensembling. The diverse set of datasets used in this study can serve as a compute-efficient playground for further CL research. The codebase is available under https://github.com/oleksost/latent_CL.

Combinatorial optimization is a well-established area in operations research and computer science. Until recently, its methods have focused on solving problem instances in isolation, ignoring that they often stem from related data distributions in practice. However, recent years have seen a surge of interest in using machine learning as a new approach for solving combinatorial problems, either directly as solvers or by enhancing exact solvers. Based on this context, the ML4CO aims at improving state-of-the-art combinatorial optimization solvers by replacing key heuristic components. The competition featured three challenging tasks: finding the best feasible solution, producing the tightest optimality certificate, and giving an appropriate solver configuration. Three realistic datasets were considered: balanced item placement, workload apportionment, and maritime inventory routing. This last dataset was kept anonymous for the contestants., Neurips 2021 competition. arXiv admin note: text overlap with arXiv:2112.12251 by other authors

Despite artificial intelligence (AI) having transformed major aspects of our society, less than a fraction of its potential has been explored, let alone deployed, for education. AI-powered learning can provide millions of learners with a highly personalized, active and practical learning experience, which is key to successful learning. This is especially relevant in the context of online learning platforms. In this paper, we present the results of a comparative head-to-head study on learning outcomes for two popular online learning platforms (n=199 participants): A MOOC platform following a traditional model delivering content using lecture videos and multiple-choice quizzes, and the Korbit learning platform providing a highly personalized, active and practical learning experience. We observe a huge and statistically significant increase in the learning outcomes, with students on the Korbit platform providing full feedback resulting in higher course completion rates and achieving learning gains 2 to 2.5 times higher than both students on the MOOC platform and students in a control group who don't receive personalized feedback on the Korbit platform. The results demonstrate the tremendous impact that can be achieved with a personalized, active learning AI-powered system. Making this technology and learning experience available to millions of learners around the world will represent a significant leap forward towards the democratization of education., 9 pages, 6 figures

Proceedings of Machine Learning Research, 162, ISSN:2640-3498, Proceedings of the 39th International Conference on Machine Learning

Progress in the field of machine learning has been fueled by the introduction of benchmark datasets pushing the limits of existing algorithms. Enabling the design of datasets to test specific properties and failure modes of learning algorithms is thus a problem of high interest, as it has a direct impact on innovation in the field. In this sense, we introduce Synbols -- Synthetic Symbols -- a tool for rapidly generating new datasets with a rich composition of latent features rendered in low resolution images. Synbols leverages the large amount of symbols available in the Unicode standard and the wide range of artistic font provided by the open font community. Our tool's high-level interface provides a language for rapidly generating new distributions on the latent features, including various types of textures and occlusions. To showcase the versatility of Synbols, we use it to dissect the limitations and flaws in standard learning algorithms in various learning setups including supervised learning, active learning, out of distribution generalization, unsupervised representation learning, and object counting.

Recent statistical methods fitted on large-scale GPS data can provide accurate estimations of the expected travel time between two points. However, little is known about the distribution of travel time, which is key to decision-making across a number of logistic problems. With sufficient data, single road-segment travel time can be well approximated. The challenge lies in understanding how to aggregate such information over a route to arrive at the route-distribution of travel time. We develop a novel statistical approach to this problem. We show that, under general conditions, without assuming a distribution of speed, travel time {divided by route distance follows a Gaussian distribution with route-invariant population mean and variance. We develop efficient inference methods for such parameters and propose asymptotically tight population prediction intervals for travel time. Using traffic flow information, we further develop a trip-specific Gaussian-based predictive distribution, resulting in tight prediction intervals for short and long trips. Our methods, implemented in an R-package, are illustrated in a real-world case study using mobile GPS data, showing that our trip-specific and population intervals both achieve the 95\% theoretical coverage levels. Compared to alternative approaches, our trip-specific predictive distribution achieves (a) the theoretical coverage at every level of significance, (b) tighter prediction intervals, (c) less predictive bias, and (d) more efficient estimation and prediction procedures. This makes our approach promising for low-latency, large-scale transportation applications., 27 main pages (38 total). This version includes stylistic changes to the previous one

Continual learning studies agents that learn from streams of tasks without forgetting previous ones while adapting to new ones. Two recent continual-learning scenarios have opened new avenues of research. In meta-continual learning, the model is pre-trained to minimize catastrophic forgetting of previous tasks. In continual-meta learning, the aim is to train agents for faster remembering of previous tasks through adaptation. In their original formulations, both methods have limitations. We stand on their shoulders to propose a more general scenario, OSAKA, where an agent must quickly solve new (out-of-distribution) tasks, while also requiring fast remembering. We show that current continual learning, meta-learning, meta-continual learning, and continual-meta learning techniques fail in this new scenario. We propose Continual-MAML, an online extension of the popular MAML algorithm as a strong baseline for this scenario. We empirically show that Continual-MAML is better suited to the new scenario than the aforementioned methodologies, as well as standard continual learning and meta-learning approaches.

Combinatorial optimization problems are typically tackled by the branch-and-bound paradigm. We propose a new graph convolutional neural network model for learning branch-and-bound variable selection policies, which leverages the natural variable-constraint bipartite graph representation of mixed-integer linear programs. We train our model via imitation learning from the strong branching expert rule, and demonstrate on a series of hard problems that our approach produces policies that improve upon state-of-the-art machine-learning methods for branching and generalize to instances significantly larger than seen during training. Moreover, we improve for the first time over expert-designed branching rules implemented in a state-of-the-art solver on large problems. Code for reproducing all the experiments can be found at https://github.com/ds4dm/learn2branch., Accepted paper at the NeurIPS 2019 conference

Generating high-quality text with sufficient diversity is essential for a wide range of Natural Language Generation (NLG) tasks. Maximum-Likelihood (MLE) models trained with teacher forcing have consistently been reported as weak baselines, where poor performance is attributed to exposure bias (Bengio et al., 2015; Ranzato et al., 2015); at inference time, the model is fed its own prediction instead of a ground-truth token, which can lead to accumulating errors and poor samples. This line of reasoning has led to an outbreak of adversarial based approaches for NLG, on the account that GANs do not suffer from exposure bias. In this work, we make several surprising observations which contradict common beliefs. First, we revisit the canonical evaluation framework for NLG, and point out fundamental flaws with quality-only evaluation: we show that one can outperform such metrics using a simple, well-known temperature parameter to artificially reduce the entropy of the model's conditional distributions. Second, we leverage the control over the quality / diversity trade-off given by this parameter to evaluate models over the whole quality-diversity spectrum and find MLE models constantly outperform the proposed GAN variants over the whole quality-diversity space. Our results have several implications: 1) The impact of exposure bias on sample quality is less severe than previously thought, 2) temperature tuning provides a better quality / diversity trade-off than adversarial training while being easier to train, easier to cross-validate, and less computationally expensive. Code to reproduce the experiments is available at github.com/pclucas14/GansFallingShort

Recurrent Neural Networks (RNNs) with attention mechanisms have obtained state-of-the-art results for many sequence processing tasks. Most of these models use a simple form of encoder with attention that looks over the entire sequence and assigns a weight to each token independently. We present a mechanism for focusing RNN encoders for sequence modelling tasks which allows them to attend to key parts of the input as needed. We formulate this using a multi-layer conditional sequence encoder that reads in one token at a time and makes a discrete decision on whether the token is relevant to the context or question being asked. The discrete gating mechanism takes in the context embedding and the current hidden state as inputs and controls information flow into the layer above. We train it using policy gradient methods. We evaluate this method on several types of tasks with different attributes. First, we evaluate the method on synthetic tasks which allow us to evaluate the model for its generalization ability and probe the behavior of the gates in more controlled settings. We then evaluate this approach on large scale Question Answering tasks including the challenging MS MARCO and SearchQA tasks. Our models shows consistent improvements for both tasks over prior work and our baselines. It has also shown to generalize significantly better on synthetic tasks as compared to the baselines., To appear at ICML 2018

A major drawback of backpropagation through time (BPTT) is the difficulty of learning long-term dependencies, coming from having to propagate credit information backwards through every single step of the forward computation. This makes BPTT both computationally impractical and biologically implausible. For this reason, full backpropagation through time is rarely used on long sequences, and truncated backpropagation through time is used as a heuristic. However, this usually leads to biased estimates of the gradient in which longer term dependencies are ignored. Addressing this issue, we propose an alternative algorithm, Sparse Attentive Backtracking, which might also be related to principles used by brains to learn long-term dependencies. Sparse Attentive Backtracking learns an attention mechanism over the hidden states of the past and selectively backpropagates through paths with high attention weights. This allows the model to learn long term dependencies while only backtracking for a small number of time steps, not just from the recent past but also from attended relevant past states.

In this paper, we study two aspects of the variational autoencoder (VAE): the prior distribution over the latent variables and its corresponding posterior. First, we decompose the learning of VAEs into layerwise density estimation, and argue that having a flexible prior is beneficial to both sample generation and inference. Second, we analyze the family of inverse autoregressive flows (inverse AF) and show that with further improvement, inverse AF could be used as universal approximation to any complicated posterior. Our analysis results in a unified approach to parameterizing a VAE, without the need to restrict ourselves to use factorial Gaussians in the latent real space., 2 figures, 5 pages, submitted to ICML Principled Approaches to Deep Learning workshop

Planning can often be simpli ed by decomposing the task into smaller tasks arranged hierarchically. Charlin et al. [4] recently showed that the hierarchy discovery problem can be framed as a non-convex optimization problem. However, the inherent computational di culty of solving such an optimization problem makes it hard to scale to realworld problems. In another line of research, Toussaint et al. [18] developed a method to solve planning problems by maximumlikelihood estimation. In this paper, we show how the hierarchy discovery problem in partially observable domains can be tackled using a similar maximum likelihood approach. Our technique rst transforms the problem into a dynamic Bayesian network through which a hierarchical structure can naturally be discovered while optimizing the policy. Experimental results demonstrate that this approach scales better than previous techniques based on non-convex optimization., Appears in Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence (UAI2008)

L'apprentissage auto-surveillé (AAS), c'est-à-dire l'apprentissage de connaissances en exploitant la structure intrinsèque présente dans un ensemble de données non étiquettées, a beaucoup fait progresser l'apprentissage automatique dans la dernière décennie, et plus particulièrement dans les dernières deux années en vision informatique. Dans cet ouvrage, nous nous servons de l'AAS comme outil dans deux champs applicatifs: Pour interpréter efficacement les ensembles de données et les décisions prises par des modèles statistiques, et pour pré-entrainer un modèle d'apprentissage par renforcement pour grandement augmenter l'efficacité de son échantillonnage dans son contexte d'entraînement. Le Chapitre 1 présente les connaissances de fond nécessaires à la compréhension du reste du mémoire. Il offre un aperçu de l'apprentissage automatique, de l'apprentissage profond, de l'apprentissage auto-surveillé et de l'apprentissage par renforcement (profond). Le Chapitre 2 se détourne brièvement du sujet de l'auto-surveillance pour étudier comment le phénomène de la mémorisation se manifeste dans les réseaux de neurones profonds. Les observations que nous ferons seront alors utilisées comme pièces justificatives pour les travaux présentés dans le Chapitre 3. Ce chapitre aborde la manière dont l'auto-surveillance peut être utilisée pour découvrir efficacement les régularités structurelles présentes dans un ensemble de données d'entraînement, estimer le degré de mémorisation de celui-ci par le modèle, et l'influence d'un échantillon d'entraînement sur les résultats pour un échantillon-test. Nous passons aussi en revue de récents travaux touchant à l'importance de mémoriser la ``longue traîne'' d'un jeu de données. Le Chapitre 4 fait la démonstration d'une combinaison d'objectifs de pré-entraînement AAS axés sur les caractéristiques des données en apprentissage par renforcement, de ce fait élevant l'efficacité d'échantillonnage à un niveau comparable à celui d'un humain. De plus, nous montrons que l'AAS ouvre la porte à de plus grands modèles, ce qui a été par le passé un défi à surmonter en apprentissage par renforcement profond. Finalement, le Chapitre 5 conclut l'ouvrage avec un bref survol des contributions scientifiques et propose quelque avenues pour des recherches poussées dans le futur., Self-Supervised Learning (SSL), or learning representations of data by exploiting inherent structure present in it without labels, has driven significant progress in machine learning over the past decade, and in computer vision in particular over the past two years. In this work, we explore applications of SSL towards two separate goals - first, as a tool for efficiently interpreting datasets and model decisions, and second, as a tool for pretraining in reinforcement learning (RL) to greatly advance sample efficiency in that setting. Chapter 1 introduces background material necessary to understand the remainder of this thesis. In particular, it provides an overview of Machine Learning, Deep Learning, Self-Supervised Representation Learning, and (Deep) Reinforcement Learning. Chapter 2 briefly detours away from this thesis' focus on self-supervision, to examine how the phenomena of memorization manifests in deep neural networks. These results are then used to partially justify work presented in Chapter 3, which examines how self-supervision can be used to efficiently uncover structural regularity in training datasets, and to estimate training memorization and the influence of training samples on test samples. Recent experimental work on understanding the importance of memorizing the long-tail of data is also revisited. Chapter 4 demonstrates how a combination of SSL pretraining objectives designed for the structure of data in RL can greatly improve sample efficiency to nearly human-level performance. Furthermore, it is shown that SSL enables the use of larger models, which has historically been a challenge in deep RL. Chapter 5 concludes by reviewing the contributions of this work, and discusses future directions.

In a world of globalization, where offers continues to grow, the ability to direct people to their specific need is essential. After being key differentiating factors for Netflix and Amazon, Recommender Systems in general are no where near a downfall. Still, one downside of the basic recommender systems is that they are mainly based on indirect feedback (our behaviour, mainly form the past) as opposed to explicit demand at a specific time. Recent development in machine learning brings us closer to the possibility for a user to express it’s specific needs in natural language and get a machine generated reply. This is what Conversational Recommendation is about. Conversational recommendation encapsulates several machine learning sub-tasks. In this work, we focus our study on methods for the task of item (in our case, movie) recommendation from conversation. To explore this setting, we use, adapt and extend state of the art transformer based neural language modeling techniques to the task of recommendation from dialogue. We study the performance of different methods using the ReDial dataset [24], a conversational- recommendation dataset for movies. We also make use of a knowledge base of movies and measure their ability to improve performance for cold-start users, items, and/or both. This master thesis is divided as follows. First, we review all the basics concepts and the previous work necessary to to this lecture. When then dive deep into the specifics our data management, the different models we tested, the set-up of our experiments and the results we got. Follows the original a paper we submitted at RecSys 2020 Conference. Note that their is a minor inconsistency since throughout the thesis, we use v to represent items but in the paper, we used i. Overall, we find that pre-trained transformer models outperform baselines even if the baselines have access to the user preferences manually extracted from their utterances., Dans un monde de mondialisation, où les offres continuent de croître, la capacité de référer les gens vers leurs besoins spécifiques est essentiel. Après avoir été un facteur de différenciation clé pour Netflix et Amazon, les systèmes de recommandation en général ne sont pas près de disparaître. Néanmoins, l’un des leurs inconvénients est qu’ils sont principalement basés sur des informations indirects (notre comportement, principalement du passé) par opposition à une demande explicite à un moment donné. Le développement récent de l’apprentissage automatique nous rapproche de la possibilité d’exprimer nos besoins spécifiques en langage naturel et d’obtenir une réponse générée par la machine. C’est ce en quoi consiste la recommandation conversationnelle. La recommandation conversationnelle englobe plusieurs sous-tâches d’apprentissage automatique. Dans ce travail, nous concentrons notre étude sur les méthodes entourant la tâche de recommandation d’item (dans notre cas, un film) à partir d’un dialogue. Pour explorer cette avenue, nous adaptons et étendons les techniques de modélisation du langage basées sur les transformeurs à la tâche de recommandation à partir du dialogue. Nous étudions les performances de différentes méthodes à l’aide de l’ensemble de données ReDial [24], un ensemble de données de recommandation conversationnelle pour les films. Nous utilisons également une base de connaissances de films et mesurons sa capacité à améliorer les performances lorsque peu d’information sur les utilisateurs/éléments est disponible. Ce mémoire par article est divisé comme suit. Tout d’abord, nous passons en revue tous les concepts de base et les travaux antérieurs nécessaires à cette lecture. Ensuite, nous élaborons les spécificités de notre gestion des données, les différents modèles que nous avons testés, la mise en place de nos expériences et les résultats que nous avons obtenus. Suit l’article original que nous avons soumis à la conférence RecSys 2020. Notez qu’il y a une incohérence mineure puisque tout au long du mémoire, nous utilisons v pour représenter les éléments mais dans l’article, nous avons utilisé i. Dans l’ensemble, nous constatons que les modèles de transformeurs pré-entraînés surpassent les modèles de bases même si les modèles de base ont accès aux préférences utilisateur extraites manuellement des dialogues.