Imitation Learning (IL) has made significant strides recently, finding applications in diverse fields like robotics, healthcare, and games. This thesis hones in on two domains with their respective challenges. Firstly, we enhance mixed-integer linear programming (MILP) solvers by learning from an accurate but computationally inefficient heuristic, introducing architectures that balance expressivity and computation. We also address the "lookback" phenomenon, improving model runtime by up to 15%. Secondly, in response to the global challenge posed by COVID-19, we developed the Proactive Contact Tracing (PCT) framework for digital contact tracing apps. Going beyond a binary quarantine response, it communicates varying risk levels, achieving a better balance between public health and economic activity. Utilizing deep learning for risk assessment, we optimized set transformers and leveraged domain randomization for robustness. Ultimately, our work not only advances IL but offers refined solutions in applied domains, concluding with a blueprint for the real-world deployment of our PCT framework.

@inproceedings{gupta2023thesis,
  title = {PhD Thesis: Imitation Learning for Combinatorial Optimization and Contact Tracing},
  author = {Gupta, Prateek},
  journal = {University of Oxford},
  _venue = {University of Oxford},
  year = {2023},
  _link = {https://ora.ox.ac.uk/objects/uuid:815241f7-1754-443f-a4d7-f82e3634815e},
  _image = {images/publications/thesis.png}
}

The COVID-19 pandemic has spurred an unprecedented demand for interventions that can reduce disease spread without excessively restricting daily activity, given negative impacts on mental health and economic outcomes. Digital contact tracing (DCT) apps have emerged as a component of the epidemic management toolkit. Existing DCT apps typically recommend quarantine to all digitally-recorded contacts of test-confirmed cases. Over-reliance on testing may, however, impede the effectiveness of such apps, since by the time cases are confirmed through testing, onward transmissions are likely to have occurred. Furthermore, most cases are infectious over a short period; only a subset of their contacts are likely to become infected. These apps do not fully utilize data sources to base their predictions of transmission risk during an encounter, leading to recommendations of quarantine to many uninfected people and associated slowdowns in economic activity. This phenomenon, commonly termed as “pingdemic,” may additionally contribute to reduced compliance to public health measures. In this work, we propose a novel DCT framework, Proactive Contact Tracing (PCT), which uses multiple sources of information (e.g. self-reported symptoms, received messages from contacts) to estimate app users’ infectiousness histories and provide behavioral recommendations. PCT methods are by design proactive, predicting spread before it occurs. We present an interpretable instance of this framework, the Rule-based PCT algorithm, designed via a multi-disciplinary collaboration among epidemiologists, computer scientists, and behavior experts. Finally, we develop an agent-based model that allows us to compare different DCT methods and evaluate their performance in negotiating the trade-off between epidemic control and restricting population mobility. Performing extensive sensitivity analysis across user behavior, public health policy, and virological parameters, we compare Rule-based PCT to i) binary contact tracing (BCT), which exclusively relies on test results and recommends a fixed-duration quarantine, and ii) household quarantine (HQ). Our results suggest that both BCT and Rule-based PCT improve upon HQ, however, Rule-based PCT is more efficient at controlling spread of disease than BCT across a range of scenarios. In terms of cost-effectiveness, we show that Rule-based PCT pareto-dominates BCT, as demonstrated by a decrease in Disability Adjusted Life Years, as well as Temporary Productivity Loss. Overall, we find that Rule-based PCT outperforms existing approaches across a varying range of parameters. By leveraging anonymized infectiousness estimates received from digitally-recorded contacts, PCT is able to notify potentially infected users earlier than BCT methods and prevent onward transmissions. Our results suggest that PCT-based applications could be a useful tool in managing future epidemics.

@inproceedings{gupta2023pct,
  title = {Proactive Contact Tracing},
  author = {Gupta, Prateek and Maharaj, Tegan and Rahaman, Nasim and Weiss, Martin and others},
  journal = {PLOS Digital Health},
  _venue = {PLOS Digital Health},
  year = {2023},
  _link = {https://doi.org/10.1371/journal.pdig.0000199},
  _image = {images/publications/pct23.png},
  blog = {/blog/2021/ct-0/}
}

The expressive and computationally inexpensive bipartite Graph Neural Networks (GNN) have been shown to be an important component of deep learning based Mixed-Integer Linear Program (MILP) solvers. Recent works have demonstrated the effectiveness of such GNNs in replacing the branching (variable selection) heuristic in branch-and-bound (B&B) solvers. These GNNs are trained, offline and on a collection of MILPs, to imitate a very good but computationally expensive branching heuristic, strong branching. Given that B&B results in a tree of sub-MILPs, we ask (a) whether there are strong dependencies exhibited by the target heuristic among the neighboring nodes of the B&B tree, and (b) if so, whether we can incorporate them in our training procedure. Specifically, we find that with the strong branching heuristic, a child node’s best choice was often the parent’s second-best choice. We call this the "lookback" phenomenon. Surprisingly, the typical branching GNN of Gasse et al. (2019) often misses this simple "answer". To imitate the target behavior more closely by incorporating the lookback phenomenon in GNNs, we propose two methods: (a) target smoothing for the standard cross-entropy loss function, and (b) adding a Parent-as-Target (PAT) Lookback regularizer term. Finally, we propose a model selection framework to incorporate harder-to-formulate objectives such as solving time in the final models. Through extensive experimentation on standard benchmark instances, we show that our proposal results in up to 22% decrease in the size of the B&B tree and up to 15% improvement in the solving times.

@inproceedings{gupta2022lookback,
  title = {Lookback for Learning to Branch},
  author = {Gupta, Prateek and Khalil, Elias B and Chet{\'e}lat, Didier and Gasse, Maxime and Bengio, Yoshua and Lodi, Andrea and Pawan Kumar, M},
  year = {2022},
  _venue = {TMLR},
  arxiv = {2206.14987},
  _image = {images/publications/gupta2022lookback.png}
}

Insufficient Social Cost of Carbon (SCC) estimation methods and short-term decision-making horizons have hindered the ability of carbon emitters to properly correct for the negative externalities of climate change, as well as the capacity of nations to balance economic and climate policy. To overcome these limitations, we introduce Retrospective Social Cost of Carbon Updating (ReSCCU), a novel mechanism that corrects for these limitations as empirically measured evidence is collected. To implement ReSCCU in the context of carbon taxation, we propose Retroactive Carbon Pricing (ReCaP), a market mechanism in which polluters offload the payment of ReSCCU adjustments to insurers. To alleviate systematic risks and minimize government involvement, we introduce the Private ReCaP (PReCaP) prediction market, which could see real-world implementation based on the engagement of a few high net-worth individuals or independent institutions.

@inproceedings{bengio2022private,
  title = {(Private)-Retroactive Carbon Pricing [(P) ReCaP]: A Market-based Approach for Climate Finance and Risk Assessment},
  author = {Bengio, Yoshua and Gupta, Prateek and Radovic, Dylan and P. Scholl, Maarten and Williams, Andrew and Schroeder de Witt, Christian and Zhang, Tianyu and Zhang, Yang},
  year = {2022},
  arxiv = {2205.00666},
  _link = {https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4093252},
  _image = {images/publications/bengio2022private.png}
}

Comprehensive global cooperation is essential to limit global temperature increases while continuing economic development, e.g., reducing severe inequality or achieving long-term economic growth. Achieving long-term cooperation on climate change mitigation with n strategic agents poses a complex game-theoretic problem. For example, agents may negotiate and reach climate agreements, but there is no central authority to enforce adherence to those agreements. Hence, it is critical to design negotiation and agreement frameworks that foster cooperation, allow all agents to meet their individual policy objectives, and incentivize long-term adherence. This is an interdisciplinary challenge that calls for collaboration between researchers in machine learning, economics, climate science, law, policy, ethics, and other fields. In particular, we argue that machine learning is a critical tool to address the complexity of this domain. To facilitate this research, here we introduce RICE-N, a multi-region integrated assessment model that simulates the global climate and economy, and which can be used to design and evaluate the strategic outcomes for different negotiation and agreement frameworks. We also describe how to use multi-agent reinforcement learning to train rational agents using RICE-N. This framework underpinsAI for Global Climate Cooperation, a working group collaboration and competition on climate negotiation and agreement design. Here, we invite the scientific community to design and evaluate their solutions using RICE-N, machine learning, economic intuition, and other domain knowledge.

@inproceedings{zhang2022ai,
  title = {AI for Global Climate Cooperation: Modeling Global Climate Negotiations, Agreements, and Long-Term Cooperation in RICE-N},
  author = {Zhang, Tianyu and Williams, Andrew and Phade, Soham and Srinivasa, Sunil and Zhang, Yang and Gupta, Prateek and Bengio, Yoshua and Zheng, Stephan},
  journal = {arXiv preprint arXiv:2208.07004},
  _venue = {AAAI Climate Change Symposium},
  year = {2022},
  arxiv = {2208.07004},
  _link = {https://arxiv.org/abs/2208.07004},
  _image = {images/publications/ai4gcc-paper.png}
}

The COVID-19 pandemic has spread rapidly worldwide, overwhelming manual contact tracing in many countries and resulting in widespread lockdowns for emergency containment. Large-scale digital contact tracing (DCT) has emerged as a potential solution to resume economic and social activity while minimizing spread of the virus. Various DCT methods have been proposed, each making trade-offs between privacy, mobility restrictions, and public health. The most common approach, binary contact tracing (BCT), models infection as a binary event, informed only by an individual’s test results, with corresponding binary recommendations that either all or none of the individual’s contacts quarantine. BCT ignores the inherent uncertainty in contacts and the infection process, which could be used to tailor messaging to high-risk individuals, and prompt proactive testing or earlier warnings. It also does not make use of observations such as symptoms or pre-existing medical conditions, which could be used to make more accurate infectiousness predictions. In this paper, we use a recently-proposed COVID-19 epidemiological simulator to develop and test methods that can be deployed to a smartphone to locally and proactively predict an individual’s infectiousness (risk of infecting others) based on their contact history and other information, while respecting strong privacy constraints. Predictions are used to provide personalized recommendations to the individual via an app, as well as to send anonymized messages to the individual’s contacts, who use this information to better predict their own infectiousness, an approach we call proactive contact tracing (PCT). We find a deep-learning based PCT method which improves over BCT for equivalent average mobility, suggesting PCT could help in safe re-opening and second-wave prevention.

@inproceedings{bengio2020predicting,
  title = {Predicting Infectiousness for Proactive Contact Tracing},
  author = {Bengio, Yoshua and Gupta, Prateek and Maharaj, Tegan and Rahaman, Nasim and Weiss, Martin and Deleu, Tristan and Muller, Eilif and Qu, Meng and Schmidt, Victor and St-Charles, Pierre-Luc and others},
  year = {2021},
  arxiv = {2010.12536},
  booktitle = {International Conference on Learning Representation},
  code = {https://github.com/mila-iqia/COVI-ML},
  _link = {https://arxiv.org/abs/2010.12536},
  _venue = {ICLR},
  _website = {https://mila.quebec/en/project/covi/},
  _image = {images/publications/pctOverview.png},
  blog = {/blog/2021/ct-0/}
}

A recent Graph Neural Network (GNN) approach for learning to branch has been shown to successfully reduce the running time of branch-and-bound algorithms for Mixed Integer Linear Programming (MILP). While the GNN relies on a GPU for inference, MILP solvers are purely CPU-based. This severely limits its application as many practitioners may not have access to high-end GPUs. In this work, we ask two key questions. First, in a more realistic setting where only a CPU is available, is the GNN model still competitive? Second, can we devise an alternate computationally inexpensive model that retains the predictive power of the GNN architecture? We answer the first question in the negative, and address the second question by proposing a new hybrid architecture for efficient branching on CPU machines. The proposed architecture combines the expressive power of GNNs with computationally inexpensive multi-layer perceptrons (MLP) for branching. We evaluate our methods on four classes of MILP problems, and show that they lead to up to 26% reduction in solver running time compared to state-of-the-art methods without a GPU, while extrapolating to harder problems than it was trained on.

@inproceedings{Gupta20hybrid,
  title = {Hybrid Models for Learning to Branch},
  author = {Gupta, Prateek and Gasse, Maxime and Khalil, Elias B and Kumar, M Pawan and Lodi, Andrea and Bengio, Yoshua},
  year = {2020},
  arxiv = {2006.15212},
  code = {https://github.com/pg2455/Hybrid-learn2branch},
  booktitle = {Advances in Neural Information Processing Systems 33},
  _link = {https://arxiv.org/abs/2006.15212},
  _venue = {NeurIPS},
  _image = {images/publications/gupta2020hybrid.png}
}

The rapid global spread of COVID-19 has led to an unprecedented demand for effective methods to mitigate the spread of the disease, and various digital contact tracing (DCT) methods have emerged as a component of the solution. In order to make informed public health choices, there is a need for tools which allow evaluation and comparison of DCT methods. We introduce an agent-based compartmental simulator we call COVI-AgentSim, integrating detailed consideration of virology, disease progression, social contact networks, and mobility patterns, based on parameters derived from empirical research. We verify by comparing to real data that COVI-AgentSim is able to reproduce realistic COVID-19 spread dynamics, and perform a sensitivity analysis to verify that the relative performance of contact tracing methods are consistent across a range of settings. We use COVI-AgentSim to perform cost-benefit analyses comparing no DCT to: 1) standard binary contact tracing (BCT) that assigns binary recommendations based on binary test results; and 2) a rule-based method for feature-based contact tracing (FCT) that assigns a graded level of recommendation based on diverse individual features. We find all DCT methods consistently reduce the spread of the disease, and that the advantage of FCT over BCT is maintained over a wide range of adoption rates. Feature-based methods of contact tracing avert more disability-adjusted life years (DALYs) per socioeconomic cost (measured by productive hours lost). Our results suggest any DCT method can help save lives, support re-opening of economies, and prevent second-wave outbreaks, and that FCT methods are a promising direction for enriching BCT using self-reported symptoms, yielding earlier warning signals and a significantly reduced spread of the virus per socioeconomic cost.

@article{gupta2020covi,
  title = {COVI-AgentSim: an Agent-based Model for Evaluating Methods of Digital Contact Tracing},
  arxiv = {2010.16004},
  author = {Gupta, Prateek and Maharaj, Tegan and Weiss, Martin and Rahaman, Nasim and Alsdurf, Hannah and Sharma, Abhinav and Minoyan, Nanor and Harnois-Leblanc, Soren and Schmidt, Victor and Charles, Pierre-Luc St and others},
  journal = {arXiv preprint arXiv:2010.16004},
  year = {2020},
  code = {https://github.com/mila-iqia/COVI-AgentSim},
  _link = {https://arxiv.org/abs/2010.16004},
  _website = {https://mila.quebec/en/project/covi/},
  _image = {images/publications/episimSeries.png},
  blog = {/blog/2021/ct-0/}
}

The SARS-CoV-2 (Covid-19) pandemic has caused significant strain on public health institutions around the world. Contact tracing is an essential tool to change the course of the Covid-19 pandemic. Manual contact tracing of Covid-19 cases has significant challenges that limit the ability of public health authorities to minimize community infections. Personalized peer-to-peer contact tracing through the use of mobile apps has the potential to shift the paradigm. Some countries have deployed centralized tracking systems, but more privacy-protecting decentralized systems offer much of the same benefit without concentrating data in the hands of a state authority or for-profit corporations. Machine learning methods can circumvent some of the limitations of standard digital tracing by incorporating many clues and their uncertainty into a more graded and precise estimation of infection risk. The estimated risk can provide early risk awareness, personalized recommendations and relevant information to the user. Finally, non-identifying risk data can inform epidemiological models trained jointly with the machine learning predictor. These models can provide statistical evidence for the importance of factors involved in disease transmission. They can also be used to monitor, evaluate and optimize health policy and (de)confinement scenarios according to medical and economic productivity indicators. However, such a strategy based on mobile apps and machine learning should proactively mitigate potential ethical and privacy risks, which could have substantial impacts on society (not only impacts on health but also impacts such as stigmatization and abuse of personal data). Here, we present an overview of the rationale, design, ethical considerations and privacy strategy of ‘COVI,’ a Covid-19 public peer-to-peer contact tracing and risk awareness mobile application developed in Canada.

@article{alsdurf2020covi,
  title = {COVI White Paper},
  author = {Alsdurf, Hannah and Bengio, Yoshua and Deleu, Tristan and Gupta, Prateek and Ippolito, Daphne and Janda, Richard and Jarvie, Max and Kolody, Tyler and Krastev, Sekoul and Maharaj, Tegan and others},
  arxiv = {2005.08502},
  year = {2020},
  _link = {https://arxiv.org/abs/2005.08502},
  _website = {https://mila.quebec/en/project/covi/},
  _image = {images/publications/alsdurf2020covi.png},
  blog = {/blog/2021/ct-0/}
}

Deep Metric Learning (DML) is arguably one of the most influential lines of research for learning visual similarities with many proposed approaches every year. Although the field benefits from the rapid progress, the divergence in training protocols, architectures, and parameter choices make an unbiased comparison difficult. To provide a consistent reference point, we revisit the most widely used DML objective functions and conduct a study of the crucial parameter choices as well as the commonly neglected mini-batch sampling process. Under consistent comparison, DML objectives show much higher saturation than indicated by literature. Further based on our analysis, we uncover a correlation between the embedding space density and compression to the generalization performance of DML models. Exploiting these insights, we propose a simple, yet effective, training regularization to reliably boost the performance of ranking-based DML models on various standard benchmark datasets.

@inproceedings{roth2020revisiting,
  title = {Revisiting Training Strategies and Generalization Performance in Deep Metric Learning},
  author = {Roth, Karsten and Milbich, Timo and Sinha, Samarth and Gupta, Prateek and Ommer, Bjoern and Cohen, Joseph Paul},
  year = {2020},
  arxiv = {2002.08473},
  code = {https://github.com/Confusezius/Revisiting_Deep_Metric_Learning_PyTorch},
  booktitle = {International Conference on Machine Learning},
  pages = {8242--8252},
  organization = {PMLR},
  _link = {https://arxiv.org/abs/2002.08473},
  _venue = {NeurIPS}
}

Traditionally gears are designed using design standards such as AGMA, ISO, etc. These design standards include a large number of “design factors” accounting for various uncertainties related to geometry, load and material uncertainties. As the knowledge about these uncertainties increases, it becomes possible to include them systematically in the gear design procedure, thereby reducing the number of empirical design factors. In this paper a method is proposed to eliminate two design factors (viz., factor of safety in contact and reliability factor) used in standard AGMA-based design procedures through the formal introduction of uncertainty in the magnitude of load and material properties. The proposed method is illustrated via the design of an automotive gear with a desired reliability, cost, and robustness. The solutions obtained are encouraging and in-line with the existing knowledge about gear design, and thus reinforces the possibility of schematically reducing the aforementioned design factors.

@conference{bp2013,
  title = {Robust {D}esign of {G}ears With {M}aterial and {L}oad {U}ncertainties},
  year = {2013},
  author = {Gautham, B. P. and Gupta, Prateek and Kulkarni, Nagesh H. and Panchal, Jitesh H. and Allen, Janet K. and Mistree, Farrokh},
  doi = {10.1115/DETC2013-12170},
  pdf = {https://www.researchgate.net/profile/Farrokh_Mistree/publication/245437216_Robust_Design_of_Gears_With_Material_and_Load_Uncertainties/links/53fa20780cf2e3cbf562cfa7.pdf},
  booktitle = {Proceedings of the ASME 2013 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. Volume 3B: 39th Design Automation Conference},
  _venue = {39th Design Automation Conference, ASME},
  _link = {https://www.researchgate.net/profile/Farrokh_Mistree/publication/245437216_Robust_Design_of_Gears_With_Material_and_Load_Uncertainties/links/53fa20780cf2e3cbf562cfa7.pdf},
  _image = {images/publications/gearDesign.png}
}