Milind  Tambe

Milind Tambe

Milind Tambe is Principal Scientist and Director of "AI for Social Good" at Google Deepmind; concurrently, he is also Gordon McKay Professor of Computer Science and Director of Center for Research in Computation and Society at Harvard University. He is recipient of the AAAI (Association for Advancement of AI) Award for Artificial Intelligence for the Benefit of Humanity, IJCAI (International Joint Conference on AI) John McCarthy Award, AAAI Feigenbaum prize, ACM/SIGAI Autonomous Agents Research Award from AAMAS (Autonomous Agents and Multiagent Systems Conference), AAAI Robert S Engelmore Memorial Lecture award, INFORMS Wagner prize, the MORS (Military Operations Research Society) Rist Prize. He is a fellow of AAAI and ACM. For his work in AI and public safety, he has received the Columbus Foundation Homeland Security Award, and meritorious Team Commendation from the US Coast Guard and LA Airport Police, and Certificate of Appreciation from US Federal Air Marshals Service for pioneering real-world deployments of security games. Prof. Tambe's papers have received either best paper awards or best paper finalist recognition 30 times at conferences such as AAAI, AAMAS, IJCAI and others. Prof. Tambe and his team have developed pioneering AI systems that deliver real-world impact in public health (e.g., maternal and child health), public safety, and wildlife conservation.

Research Areas

Authored Publications
Sort By
  • Title
  • Title, descending
  • Year
  • Year, descending
Preview abstract Restless multi-arm bandits, a class of resource allocation problems involving multiple agents with a resource constraint, have applications in healthcare, machine maintenance, and anti-poaching. For such high stake use cases, decisions must ensure equity among groups. Prior RMAB research suffers from several limitations, e.g., it fails to address equitable RMABs with guarantees on resources given to different groups, or fails to consider practical settings where transition dynamics are unknown. We address these limitations by developing a decision-focused-learning pipeline to solve equitable RMABs, using a novel budget allocation algorithm to prevent disparity between groups. Our results on both synthetic data and real-world public health data demonstrate that our approach greatly improves equity without sacrificing utility. View details
Adherence Bandits
Jackson A. Killian*
Arshika Lalan*
Aditya Mate*
Manish Jain
The Workshop on Artificial Intelligence for Social Good at AAAI 2023 (2023)
Preview abstract We define a new subclass of the restless multi-armed bandit framework, that we name Adherence Bandits, designed to capture the dynamics prevalent in many public health intervention problems. We discuss key properties of Adherence Bandits, their real-world motivations, how structures lead to both technical and computational advantages, and natural extensions that have been or can be made to the subclass. We summarise key research works that have contributed to the growing sub-area and finish by highlighting future directions of research View details
Preview abstract Restless Multi-Armed Bandits (RMABs) are an important model that enable optimizing allocation of limited resources in sequential decision-making settings. Typical RMABs assume the budget --- the number of arms pulled --- per round to be fixed for each step in the planning horizon. However, when planning in real-world settings, resources are not necessarily limited at each planning step; we may be able to distribute surplus resources in one round to an earlier or later round. Often this flexibility in budget is constrained to within a subset of consecutive planning steps. In this paper we define a general class of RMABs with flexible budget, which we term F-RMABs, and provide an algorithm to optimally solve for them. Additionally, we provide heuristics that tradeoff solution quality for efficiency and present experimental comparisons of different F-RMAB solution approaches. View details
Deployed SAHELI: Field Optimization of Intelligent RMAB for Maternal and Child Care
Shresth Verma
Aditya S. Mate
Paritosh Verma
Sruthi Gorantala
Neha Madhiwalla
Aparna Hegde
Manish Jain
Innovative Applications of Artificial Intelligence (IAAI) (2023) (to appear)
Preview abstract Underserved communities face critical health challenges due to lack of access to timely and reliable information. Non-governmental organizations are leveraging the widespread use of cellphones to combat these healthcare challenges and spread preventative awareness. The health workers at these organizations reach out individually to beneficiaries; however such programs still suffer from declining engagement. We have deployed SAHELI, a system to efficiently utilize the limited availability of health workers for improving maternal and child health in India. SAHELI uses the Restless Multi-armed Bandit (RMAB) framework to identify beneficiaries for outreach. It is the first deployed application for RMABs in public health, and is already in continuous use by our partner NGO, ARMMAN. We have already reached ∼ 100K beneficiaries with SAHELI, and are on track to serve 1 million beneficiaries by the end of 2023. This scale and impact has been achieved through multiple innovations in the RMAB model and its development, in preparation of real world data, and in deployment practices; and through careful consideration of responsible AI practices. Specifically, in this paper, we describe our approach to learn from past data to improve the performance of SAHELI’s RMAB model, the real-world challenges faced during deployment and adoption of SAHELI, and the end-to-end pipeline View details
Analyzing and Predicting Low-Listenership Trends in a Large-Scale Mobile Health Program: A Preliminary Investigation
Arshika Lalan
Shresth Verma
Kumar Madhu Sudan
Amrita Mahale
Aparna Hegde
The Workshop in Data Science for Social Good, KDD 2023 (2023)
Preview abstract Mobile health programs are becoming an increasingly popular medium for dissemination of health information among beneficiaries in less privileged communities. Kilkari is one of the world’s largest mobile health programs which delivers time sensitive audio-messages to pregnant women and new mothers. We have been collaborating with ARMMAN, a non-profit in India which operates the Kilkari program, to identify bottlenecks to improve the efficiency of the program. In particular, we provide an initial analysis of the trajectories of benefi- ciaries’ interaction with the mHealth program and examine elements of the program that can be potentially enhanced to boost its success. We cluster the cohort into different buckets based on listenership so as to analyze listenership patterns for each group that could help boost program success . We also demonstrate preliminary results on using historical data in a time-series prediction to identify benefi- ciary dropouts and enable NGOs in devising timely interventions to strengthen beneficiary retention. View details
Preview abstract We study the problem of planning restless multi-armed bandits (RMABs) with multiple actions. This is a popular model for multi-agent systems with applications like multi-channel communication, monitoring and machine maintenance tasks, and healthcare. Whittle index policies, which are based on Lagrangian relaxations, are widely used in these settings due to their simplicity and near-optimality under certain conditions. In this work, we first show that Whittle index policies can fail in simple and practically relevant RMAB settings, even when the RMABs are indexable. We further discuss why the Whittle index policies can provably fail in these settings, despite indexability and how even asymptotic optimality does not translate well to practically relevant planning horizons. We then propose an alternate planning algorithm based on the mean-field method, which borrows ideas from existing research with some improvements. This algorithm can provably and efficiently obtain near-optimal policies when the number of arms, $N$, is large without the stringent structural assumptions required by Whittle index policies. Our approach is hyper-parameter free, and we provide an improved non-asymptotic analysis which has a) a better dependence on problem dependent parameters b) high probability upper bounds which show that the reward of the policy is reliable c) matching lower bounds for this algorithm, thus demonstrating the tightness of our bounds. Our extensive experimental analysis shows that the mean-field approach matches or outperforms other baselines. View details
Preview abstract We consider the task of effect estimation of resource allocation algorithms through clinical trials. Such algorithms are tasked with optimally utilizing severely limited intervention resources, with the goal of maximizing their overall benefits derived. Evaluation of such algorithms through clinical trials proves difficult, notwithstanding the scale of the trial, because the agents’ outcomes are inextricably linked through the budget constraint controlling the intervention decisions. Towards building more powerful estimators with improved statistical significance estimates, we propose a novel concept involving retrospective reshuffling of participants across experimental arms at the end of a clinical trial. We identify conditions under which such reassignments are permissible and can be leveraged to construct counterfactual clinical trials, whose outcomes can be accurately ‘observed’ without uncertainty, for free. We prove theoretically that such an estimator is more accurate than common estimators based on sample means — we show that it returns an unbiased estimate and simultaneously reduces variance. We demonstrate the value of our approach through empirical experiments on both, real case studies as well as synthetic and realistic data sets and show improved estimation accuracy across the board. View details
Reflections from the Workshop on AI-Assisted Decision-Making for Conservation
Robert Heilmayr
Paul Moorcroft
Millie Chapman
Tanya Berger-Wolf
Esther Rolf
Sara Beery
Joseph Bennett
Konstantin Klemmer
Lily Xu
Justin Brashares
David Thau
Hannah Kerner
Angela Gaylard
Elizabeth Bondi
Lester Mackey
Jonathan Palmer
Anthony Corso
Tanya Birch
Claire Monteleoni
Vipin Kumar
Andrew Perrault
Nikhil Garg
ArXiv (2023)
Preview abstract The following is not an abstract, rather an introduction. -------- The world has lost one-third of global forests [Williams 2008] and one million species face extinction due to human activities [Tollefson 2019]. To reverse these trends, conservation decision-makers are tasked with managing protected areas [Watson et al. 2014; Coad et al. 2015], prioritizing endangered species [Chadès et al. 2008; Schuster et al. 2019; Ball et al. 2009], and navigating opportunity cost trade-offs in conservation vs. economic development [Fox et al. 2019; Sacre et al. 2020; Dowd et al. 2022], often in the face of uncertainty, complex constraints, and long planning horizons [Visconti et al. 2010; Carvalho et al. 2017; Pressey et al. 2013; Tulloch et al. 2013]. Simultaneously, recent years have seen rapid advances in artificial intelligence (AI), including deep learning to uncover patterns in high-dimensional datasets [LeCun et al. 2015], tractable approaches to navigate exponentially large problem spaces [Browne et al. 2012], and statistical inference to learn causal effects of actions [Pearl 2019]. Much existing work at the intersection of AI and conservation focuses on extracting basic information from primary data, often in the form of computer vision for biodiversity monitoring, such as supervised learning approaches to identify animals or classify land cover [Tuia et al. 2022; Weinstein et al. 2017; Qin et al. 2022]. Gathering and interpreting this data is critical to monitor the state of the environment to inform conservation decision making. There also exist a wide range of AI methods that enable optimization, sequential planning, and inference to draw causal conclusions from observational data [CITE or forward reference sections to come]. To this end, the AI-Assisted Decision-Making for Conservation workshop convened to explore the opportunities to expand the breadth of AI methods — particularly for optimization, planning, and evaluation — that are being developed for and applied to conservation. In this report, we summarize the challenges raised during the workshop in conservation area management; methods discussed in AI, earth observation, and causality; and limitations in the application of AI for conservation. First, we synthesize key conservation priorities. For effective conservation area management, the primary steps are to: Understand the world. To inform conservation decision making, managers must first have a basic understanding of animal populations [CITE], species distribution [Beery et al. 2021], land cover [Qin et al. 2022], and human activity [CITE]. Act in the world. Using their best understanding of the world, managers are tasked with designating new conservationprotected areas, allocating ranger patrols, implementing human–wildlife conflict deterrence programs, intervening in the illegal wildlife trade, setting sustainable harvest targets, supporting sustainable economies, and countless other decisions — almost always in the face of limited resources and uncertainty. Evaluate impact. Managers want to evaluate the impact of their actions, preferably to learn causal effects of these decisions, as well as better understand causal relationships between elements of the environment, such as the effect of elephant populations on carbon stocks in savannas [Davies and Asner 2019]. AI methods have the potential to aid in each of these three components of conservation management. Some approaches have already been in use for years; other approaches are not yet deployable but are growing in promise. Algorithmic approaches can help: Understand the world. AI for earth observation can help across scales, from studying planet-level changes using remote sensing imagery [Brodick et al. 2019; Lobell et al. 2015; Hansen et al. 2013; Rolf et al. 2021; Khandelwal et al. 2022; Brown et al. 2022; Reichstein et al. 2019] to monitoring individual animal movement with photographs [Lahiri et al. 2011], acoustic monitoring, and GPS tracking. Act in the world. AI methods can help plan across a range of contexts relevant to conservation, including sequential settings, under model uncertainty, and in the presence of multiple agents [Kochenderfer et al. 2022]. Evaluate impact. Causal inference techniques can help understand the causal effect of conservation actions, including scenarios where randomized controlled trials are too expensive or infeasible to conduct [Beyers 1998; Ferraro et al. 2018; Kimmel et al. 2021]. In this white paper, we recollect and synthesize key points made during presentations and discussions from the 2022 AI-Assisted Decision Making for Conservation workshop . In particular, we identify key open research questions in resource allocation, planning, and interventions for biodiversity conservation. WIn particular, we pinpoint conservation challenges that not only require AI solutions, but require novel methodological advances. We hope that this document serves as a call-to-action to encourage ecologists and land-useconservation decision-makers to consider adopting algorithmic decision-making approaches, and encourage AI researchers to look to conservation challenges to help prioritize which methods to advance in their future research. The AI-Assisted Decision-Making for Conservation workshop was hosted by the Center for Research on Computation Society (CRCS) at Harvard University in October 2022. The co-authors of this paper were the workshop participants, coming from across academia, industry, and non-profits with expertise in computation, conservation, and deploying research. View details
Preview abstract This paper studies restless multi-armed bandit (RMAB) problems with unknown arm transition dynamics but with known correlated arm features. The goal is to learn a model to predict transition dynamics given features, where the Whittle index policy solves the RMAB problems using predicted transitions. However, prior works often learn the model by maximizing the predictive accuracy instead of final RMAB solution quality, causing a mismatch between training and evaluation objectives. To address this shortcoming, we propose a novel approach for decision-focused learning in RMAB that directly trains the predictive model to maximize the Whittle index solution quality. We present three key contributions: (i) we establish differentiability of the Whittle index policy to support decision-focused learning; (ii) we significantly improve the scalability of decision-focused learning approaches in sequential problems, specifically RMAB problems; (iii) we apply our algorithm to a previously collected dataset of maternal and child health to demonstrate its performance. Indeed, our algorithm is the first for decision-focused learning in RMAB that scales to real-world problem sizes. View details
Robust Planning over Restless Groups: Engagement Interventions for a Large-Scale Maternal Telehealth Program
Jackson Killian
Lily Xu
Arpita Biswas
Shresth Verma
Vineet Nair
Aparna Hegde
Neha Madhiwalla
Paula Rodriguez Diaz
Sonja Johnson-Yu
AAAI 2023 (to appear)
Preview abstract In 2020, maternal mortality in India was estimated to be as high as 130 deaths per 100K live births, nearly twice the UN’s target. To improve health outcomes, the non-profit ARMMAN sends automated voice messages to expecting and new mothers across India. However, 38% of mothers stop listening to these calls, missing critical preventative care information. To improve engagement, ARMMAN employs health workers to intervene by making service calls, but workers can only call a fraction of the 100K enrolled mothers. Partnering with ARMMAN, we model the problem of allocating limited interventions across mothers as a restless multi-armed bandit (RMAB), where the realities of large scale and model uncertainty present key new technical challenges. We address these with GROUPS, a double oracle–based algorithm for robust planning in RMABs with scalable grouped arms. Robustness over grouped arms requires several methodological advances. First, to adversarially select stochastic group dynamics, we develop a new method to optimize Whittle indices over transition probability intervals. Second, to learn group level RMAB policy best responses to these adversarial environments, we introduce a weighted index heuristic. Third, we prove a key theoretical result that planning over grouped arms achieves the same minimax regret–optimal strategy as planning over individual arms, under a technical condition. Finally, using real world data from ARMMAN, we show that GROUPS produces robust policies that reduce minimax regret by up to 50%, halving the number of preventable missed voice messages to connect more mothers with life saving maternal health information. View details
×