Arrow Research search

Author name cluster

Andrew Perrault

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

30 papers
2 author rows

Possible papers

30

AAAI Conference 2026 Conference Paper

Optimizing Urban Service Allocation with Time-Constrained Restless Bandits

  • Yi Mao
  • Andrew Perrault

Municipal inspections are an important part of maintaining the quality of goods and services. In this paper, we approach the problem of intelligently scheduling service inspections to maximize their impact, using the case of food establishment inspections in Chicago as a case study. The Chicago Department of Public Health (CDPH) inspects thousands of establishments each year, with a substantial fail rate (over 3,000 failed inspection reports in 2023). To balance the objectives of ensuring adherence to guidelines, minimizing disruption to establishments, and minimizing inspection costs, CDPH assigns each establishment an inspection window every year and guarantees that they will be inspected exactly once during that window. Meanwhile, CDPH also promises surprise public health inspections for unexpected food safety emergencies or complaints. These constraints create a challenge for a restless multi-armed bandit (RMAB) approach, for which there are no existing methods. We develop an extension to Whittle index-based systems for RMABs that can guarantee action window constraints and frequencies, and furthermore can be leveraged to optimize action window assignments themselves. Briefly, we combine MDP reformulation and integer programming-based lookahead to maximize the impact of inspections subject to constraints. A neural network-based supervised learning model is developed to model state transitions of real Chicago establishments using public CDPH inspection records, which demonstrates 10% AUC improvements compared with directly predicting establishments' failures. Our experiments not only show up to 24% (in simulation) or 33% (on real data) objective improvements resulting from our approach and robustness to surprise inspections, but also give insight into the impact of scheduling constraints.

PDF Details DOI

AAAI Conference 2025 Conference Paper

Cultivating Archipelago of Forests: Evolving Robust Decision Trees Through Island Coevolution

  • Adam Zychowski
  • Andrew Perrault
  • Jacek Mańdziuk

Decision trees are widely used in machine learning due to their simplicity and interpretability, but they often lack robustness to adversarial attacks and data perturbations. The paper proposes a novel island-based coevolutionary algorithm (ICoEvoRDF) for constructing robust decision tree ensembles. The algorithm operates on multiple islands, each containing populations of decision trees and adversarial perturbations. The populations on each island evolve independently, with periodic migration of top-performing decision trees between islands. This approach fosters diversity and enhances the exploration of the solution space, leading to more robust and accurate decision tree ensembles. ICoEvoRDF utilizes a popular game theory concept of mixed Nash equilibrium for ensemble weighting, which further leads to improvement in results. ICoEvoRDF is evaluated on 20 benchmark datasets, demonstrating its superior performance compared to state-of-the-art methods in optimizing both adversarial accuracy and minimax regret. The flexibility of ICoEvoRDF allows for the integration of decision trees from various existing methods, providing a unified framework for combining diverse solutions. Our approach offers a promising direction for developing robust and interpretable machine learning models.

PDF Details DOI

TMLR Journal 2025 Journal Article

Normality-Guided Distributional Reinforcement Learning for Continuous Control

  • Ju-Seung Byun
  • Andrew Perrault

Learning a predictive model of the mean return, or value function, plays a critical role in many reinforcement learning algorithms. Distributional reinforcement learning (DRL) has been shown to improve performance by modeling the value distribution, not just the mean. We study the value distribution in several continuous control tasks and find that the learned value distribution is empirically quite close to normal. We design a method that exploits this property, employing variances predicted from a variance network, along with returns, to analytically compute target quantile bars representing a normal for our distributional value function. In addition, we propose a policy update strategy based on the correctness as measured by structural characteristics of the value distribution not present in the standard value function. The approach we outline is compatible with many DRL structures. We use two representative on-policy algorithms, PPO and TRPO, as testbeds. Our method yields statistically significant improvements in 10 out of 16 continuous task settings, while utilizing a reduced number of weights and achieving faster training time compared to an ensemble-based method for quantifying value distribution uncertainty.

PDF Details

ICML Conference 2025 Conference Paper

Symmetric Reinforcement Learning Loss for Robust Learning on Diverse Tasks and Model Scales

  • Ju-Seung Byun
  • Andrew Perrault

Reinforcement learning (RL) training is inherently unstable due to factors such as moving targets and high gradient variance. Reinforcement Learning from Human Feedback (RLHF) and Reinforcement Learning from AI Feedback (RLAIF) introduce additional challenges. For instance, diverse preferences complicate the alignment process, and prediction errors in a trained reward model can become more severe as the LLM generates unseen outputs. These RL challenges create confusion about whether the probability of an action for a given state should be increased or decreased, similar to the noise in labels for classification tasks. In this work, we focus on RL algorithms that share learning difficulties with cross-entropy loss, especially for low-probability predictions. To enhance stability, we adapt reverse cross-entropy (RCE) from supervised learning for noisy data, defining a symmetric RL loss. We demonstrate performance improvements across various tasks and scales. We conduct experiments in discrete action tasks (Atari games) and continuous action space tasks (MuJoCo benchmark and Box2D) using Symmetric A2C (SA2C) and Symmetric PPO (SPPO). Notably, SPPO shows strong performance across different hyperparameters. Furthermore, we validate the symmetric RL loss in the RLHF framework using PPO for natural language processing tasks such as IMDB positive sentiment and TL; DR summarization.

Details

AAAI Conference 2025 Conference Paper

The Distributional Reward Critic Framework for Reinforcement Learning Under Perturbed Rewards

  • Xi Chen
  • Zhihui Zhu
  • Andrew Perrault

The reward signal plays a central role in defining the desired behaviors of agents in reinforcement learning (RL). Rewards collected from realistic environments could be perturbed, corrupted, or noisy due to an adversary, sensor error, or because they come from subjective human feedback. Thus, it is important to construct agents that can learn under such rewards. Existing methodologies for this problem make strong assumptions, including that the perturbation is known in advance, clean rewards are accessible, or that the perturbation preserves the optimal policy. We study a new, more general, class of unknown perturbations, and introduce a distributional reward critic framework for estimating reward distributions and perturbations during training. Our proposed methods are compatible with any RL algorithm. Despite their increased generality, we show that they achieve comparable or better rewards than existing methods in a variety of environments, including those with clean rewards. Under the challenging and generalized perturbations we study, we win/tie the highest return in 44/48 tested settings (compared to 11/48 for the best baseline). Our results broaden and deepen our ability to perform RL in reward-perturbed environments.

PDF Details DOI

IS Journal 2025 Journal Article

The Next Wave of AI for Social Impact: Challenges and Opportunities

  • Milind Tambe
  • Fei Fang
  • Andrew Perrault
  • Bryan Wilder

The burgeoning field of artificial intelligence for social impact (AI4SI) represents a significant evolution in artificial intelligence, prioritizing measurable positive impact for vulnerable and under-resourced populations. This article examines the historical context and recent surge in AI4SI, driven by technological advancements and a growing awareness of societal challenges. It highlights the crucial role of interdisciplinary collaboration, ethical considerations, and the potential of emerging AI trends in addressing issues such as poverty, health, and environmental sustainability. Furthermore, the article delves into key research questions and challenges facing the field, including the need for contextually relevant AI design, overcoming data limitations, ensuring scalable and sustainable deployments in resource-constrained environments, and establishing robust evaluation frameworks. Realizing the full potential of AI to address pressing societal needs in the coming decade and beyond will hinge on effectively navigating these challenges and fostering a deeply impact-driven approach to research and development.

Details DOI

RLC Conference 2025 Conference Paper

Understanding Learned Representations and Action Collapse in Visual Reinforcement Learning

  • Xi Chen
  • Zhihui Zhu
  • Andrew Perrault

In contrast to deep learning models trained with supervised data, visual reinforcement learning (VRL) models learn to represent their environment implicitly via the process of seeking higher rewards. However, there has been little research on the specific representations VRL models learn. Using linear probing, we study the extent to which VRL models learn to linearly represent the ground truth vectorized state of an environment, on which layers these representations are most accessible, and how this relates to the reward achieved by the final model. We observe that poorly performing agents differ substantially from well-performing ones in the representation learned in their later MLP layers, but not their earlier CNN layers. When an agent is initialized by reusing the later layers of a poorly performing agent, the result is always poor. These poorly performing agents end up with no entropy in their actor network output, a phenomenon we call {\it action collapse}. Based on these observations, we propose a simple rule to prevent action collapse during training, leading to better performance on tasks with image observations with no additional computational cost. Code is available at: https: //github. com/cx441000319/action-collapse.

PDF Details

RLJ Journal 2025 Journal Article

Understanding Learned Representations and Action Collapse in Visual Reinforcement Learning

  • Xi Chen
  • Zhihui Zhu
  • Andrew Perrault

In contrast to deep learning models trained with supervised data, visual reinforcement learning (VRL) models learn to represent their environment implicitly via the process of seeking higher rewards. However, there has been little research on the specific representations VRL models learn. Using linear probing, we study the extent to which VRL models learn to linearly represent the ground truth vectorized state of an environment, on which layers these representations are most accessible, and how this relates to the reward achieved by the final model. We observe that poorly performing agents differ substantially from well-performing ones in the representation learned in their later MLP layers, but not their earlier CNN layers. When an agent is initialized by reusing the later layers of a poorly performing agent, the result is always poor. These poorly performing agents end up with no entropy in their actor network output, a phenomenon we call {\it action collapse}. Based on these observations, we propose a simple rule to prevent action collapse during training, leading to better performance on tasks with image observations with no additional computational cost. Code is available at: https://github.com/cx441000319/action-collapse.

PDF Details

AAAI Conference 2024 Conference Paper

Coevolutionary Algorithm for Building Robust Decision Trees under Minimax Regret

  • Adam Żychowski
  • Andrew Perrault
  • Jacek Mańdziuk

In recent years, there has been growing interest in developing robust machine learning (ML) models that can withstand adversarial attacks, including one of the most widely adopted, efficient, and interpretable ML algorithms—decision trees (DTs). This paper proposes a novel coevolutionary algorithm (CoEvoRDT) designed to create robust DTs capable of handling noisy high-dimensional data in adversarial contexts. Motivated by the limitations of traditional DT algorithms, we leverage adaptive coevolution to allow DTs to evolve and learn from interactions with perturbed input data. CoEvoRDT alternately evolves competing populations of DTs and perturbed features, enabling construction of DTs with desired properties. CoEvoRDT is easily adaptable to various target metrics, allowing the use of tailored robustness criteria such as minimax regret. Furthermore, CoEvoRDT has potential to improve the results of other state-of-the-art methods by incorporating their outcomes (DTs they produce) into the initial population and optimize them in the process of coevolution. Inspired by the game theory, CoEvoRDT utilizes mixed Nash equilibrium to enhance convergence. The method is tested on 20 popular datasets and shows superior performance compared to 4 state-of-the-art algorithms. It outperformed all competing methods on 13 datasets with adversarial accuracy metrics, and on all 20 considered datasets with minimax regret. Strong experimental results and flexibility in choosing the error measure make CoEvoRDT a promising approach for constructing robust DTs in real-world applications.

PDF Details DOI

AAAI Conference 2024 Conference Paper

Leaving the Nest: Going beyond Local Loss Functions for Predict-Then-Optimize

  • Sanket Shah
  • Bryan Wilder
  • Andrew Perrault
  • Milind Tambe

Predict-then-Optimize is a framework for using machine learning to perform decision-making under uncertainty. The central research question it asks is, "How can we use the structure of a decision-making task to tailor ML models for that specific task?" To this end, recent work has proposed learning task-specific loss functions that capture this underlying structure. However, current approaches make restrictive assumptions about the form of these losses and their impact on ML model behavior. These assumptions both lead to approaches with high computational cost, and when they are violated in practice, poor performance. In this paper, we propose solutions to these issues, avoiding the aforementioned assumptions and utilizing the ML model's features to increase the sample efficiency of learning loss functions. We empirically show that our method achieves state-of-the-art results in four domains from the literature, often requiring an order of magnitude fewer samples than comparable methods from past work. Moreover, our approach outperforms the best existing method by nearly 200% when the localness assumption is broken.

PDF Details DOI

AAMAS Conference 2024 Conference Paper

Time-Constrained Restless Multi-Armed Bandits with Applications to City Service Scheduling

  • Yi Mao
  • Andrew Perrault

Municipalities maintain critical infrastructure through inspections, both proactive and in response to complaints. For example, the Chicago Department of Public Health (CDPH) periodically inspects 7000 food establishments to maintain the safety of food bought, sold, or prepared for public consumption. Restless multi-armed bandits (RMABs) appear to be a useful tool for optimizing the scheduling of inspections, as the schedule aims to keep as many establishments in the “passing” state subject to an action limit per period. However, a key challenge arises: satisfying timing and frequency constraints. Municipal agencies often provide an inspection window to each establishment (e. g. , a two-week period where an inspection will occur) and guarantee the minimum frequency of inspection (e. g. , once per year). We develop an extension to Whittle index-based systems for RMABs that can guarantee both action window constraints and minimum frequencies. Briefly, we take a Whittle index-based view, enforcing window constraints by integrating the window structure into individual MDPs, and frequency constraints through a higherlevel scheduling algorithm that aims to maximize the Whittle index. We demonstrate our methods’ performance and scalability in experiments using synthetic and real data (with 7000 establishments inspected per year). Not only does our approach enforce constraints more effectively than naive methods, but it also achieves higher rewards, up to 20%.

PDF

AAAI Conference 2022 Conference Paper

Coordinating Followers to Reach Better Equilibria: End-to-End Gradient Descent for Stackelberg Games

  • Kai Wang
  • Lily Xu
  • Andrew Perrault
  • Michael K. Reiter
  • Milind Tambe

A growing body of work in game theory extends the traditional Stackelberg game to settings with one leader and multiple followers who play a Nash equilibrium. Standard approaches for computing equilibria in these games reformulate the followers’ best response as constraints in the leader’s optimization problem. These reformulation approaches can sometimes be effective, but make limiting assumptions on the followers’ objectives and the equilibrium reached by followers, e. g. , uniqueness, optimism, or pessimism. To overcome these limitations, we run gradient descent to update the leader’s strategy by differentiating through the equilibrium reached by followers. Our approach generalizes to any stochastic equilibrium selection procedure that chooses from multiple equilibria, where we compute the stochastic gradient by back-propagating through a sampled Nash equilibrium using the solution to a partial differential equation to establish the unbiasedness of the stochastic gradient. Using the unbiased gradient estimate, we implement the gradient-based approach to solve three Stackelberg problems with multiple followers. Our approach consistently outperforms existing baselines to achieve higher utility for the leader.

PDF Details

NeurIPS Conference 2022 Conference Paper

Decision-Focused Learning without Decision-Making: Learning Locally Optimized Decision Losses

  • Sanket Shah
  • Kai Wang
  • Bryan Wilder
  • Andrew Perrault
  • Milind Tambe

Decision-Focused Learning (DFL) is a paradigm for tailoring a predictive model to a downstream optimization task that uses its predictions in order to perform better \textit{on that specific task}. The main technical challenge associated with DFL is that it requires being able to differentiate through the optimization problem, which is difficult due to discontinuous solutions and other challenges. Past work has largely gotten around this this issue by \textit{handcrafting} task-specific surrogates to the original optimization problem that provide informative gradients when differentiated through. However, the need to handcraft surrogates for each new task limits the usability of DFL. In addition, there are often no guarantees about the convexity of the resulting surrogates and, as a result, training a predictive model using them can lead to inferior local optima. In this paper, we do away with surrogates altogether and instead \textit{learn} loss functions that capture task-specific information. To the best of our knowledge, ours is the first approach that entirely replaces the optimization component of decision-focused learning with a loss that is automatically learned. Our approach (a) only requires access to a black-box oracle that can solve the optimization problem and is thus \textit{generalizable}, and (b) can be \textit{convex by construction} and so can be easily optimized over. We evaluate our approach on three resource allocation problems from the literature and find that our approach outperforms learning without taking into account task-structure in all three domains, and even hand-crafted surrogates from the literature.

PDF Details

ICLR Conference 2022 Conference Paper

Training Transition Policies via Distribution Matching for Complex Tasks

  • Ju-Seung Byun
  • Andrew Perrault

Humans decompose novel complex tasks into simpler ones to exploit previously learned skills. Analogously, hierarchical reinforcement learning seeks to leverage lower-level policies for simple tasks to solve complex ones. However, because each lower-level policy induces a different distribution of states, transitioning from one lower-level policy to another may fail due to an unexpected starting state. We introduce transition policies that smoothly connect lower-level policies by producing a distribution of states and actions that matches what is expected by the next policy. Training transition policies is challenging because the natural reward signal---whether the next policy can execute its subtask successfully---is sparse. By training transition policies via adversarial inverse reinforcement learning to match the distribution of expected states and actions, we avoid relying on task-based reward. To further improve performance, we use deep Q-learning with a binary action space to determine when to switch from a transition policy to the next pre-trained policy, using the success or failure of the next subtask as the reward. Although the reward is still sparse, the problem is less severe due to the simple binary action space. We demonstrate our method on continuous bipedal locomotion and arm manipulation tasks that require diverse skills. We show that it smoothly connects the lower-level policies, achieving higher success rates than previous methods that search for successful trajectories based on a reward function, but do not match the state distribution.

Details

AAMAS Conference 2021 Conference Paper

Beyond "To Act or Not to Act": Fast Lagrangian Approaches to General Multi-Action Restless Bandits

  • Jackson A. Killian
  • Andrew Perrault
  • Milind Tambe

This paper presents new algorithms and theoretical results for solutions to Multi-action Multi-armed Restless Bandits, an important but insufficiently studied generalization of traditional Multi-armed Restless Bandits (MARBs). Though MARBs are popular for modeling many problems, they are restricted to binary actions, i. e. , "to act or not to act". This renders them unable to capture critical complexities faced by planners in real domains, such as a system manager balancing maintenance, repair, and job scheduling, or a health worker deciding among treatments for a given patient. Limited previous work on Multi-action MARBs has only been specialized to subproblems. Here we derive multiple algorithms for use on general Multi-action MARBs using Lagrangian relaxation techniques, leading to the following contributions: (i) We develop BLam, a bound optimization algorithm which leverages problem convexity to quickly and provably converge to the well-performing Lagrange policy; (ii) We develop SampleLam, a fast sampling technique for estimating the Lagrange policy, and derive a concentration bound to investigate its convergence properties; (iii) We derive best and worst case computational complexities for our algorithms as well as our main competitor; (iv) We provide experimental results comparing our algorithms to baselines on simulated distributions, including one motivated by a real-world community health intervention task. Our approach achieves significant, up to ten-fold speedups over more general methods without sacrificing performance and is widely applicable across general Multi-action MARBs. Code is available at https: //github. com/killian-34/MAMARB-Lagrange-Policies.

PDF

AAAI Conference 2021 Conference Paper

Dual-Mandate Patrols: Multi-Armed Bandits for Green Security

  • Lily Xu
  • Elizabeth Bondi
  • Fei Fang
  • Andrew Perrault
  • Kai Wang
  • Milind Tambe

Conservation efforts in green security domains to protect wildlife and forests are constrained by the limited availability of defenders (i. e. , patrollers), who must patrol vast areas to protect from attackers (e. g. , poachers or illegal loggers). Defenders must choose how much time to spend in each region of the protected area, balancing exploration of infrequently visited regions and exploitation of known hotspots. We formulate the problem as a stochastic multi-armed bandit, where each action represents a patrol strategy, enabling us to guarantee the rate of convergence of the patrolling policy. However, a naive bandit approach would compromise short-term performance for long-term optimality, resulting in animals poached and forests destroyed. To speed up performance, we leverage smoothness in the reward function and decomposability of actions. We show a synergy between Lipschitzcontinuity and decomposition as each aids the convergence of the other. In doing so, we bridge the gap between combinatorial and Lipschitz bandits, presenting a no-regret approach that tightens existing guarantees while optimizing for short-term performance. We demonstrate that our algorithm, LIZARD, improves performance on real-world poaching data from Cambodia.

PDF Details

NeurIPS Conference 2021 Conference Paper

Learning MDPs from Features: Predict-Then-Optimize for Sequential Decision Making by Reinforcement Learning

  • Kai Wang
  • Sanket Shah
  • Haipeng Chen
  • Andrew Perrault
  • Finale Doshi-Velez
  • Milind Tambe

In the predict-then-optimize framework, the objective is to train a predictive model, mapping from environment features to parameters of an optimization problem, which maximizes decision quality when the optimization is subsequently solved. Recent work on decision-focused learning shows that embedding the optimization problem in the training pipeline can improve decision quality and help generalize better to unseen tasks compared to relying on an intermediate loss function for evaluating prediction quality. We study the predict-then-optimize framework in the context of sequential decision problems (formulated as MDPs) that are solved via reinforcement learning. In particular, we are given environment features and a set of trajectories from training MDPs, which we use to train a predictive model that generalizes to unseen test MDPs without trajectories. Two significant computational challenges arise in applying decision-focused learning to MDPs: (i) large state and action spaces make it infeasible for existing techniques to differentiate through MDP problems, and (ii) the high-dimensional policy space, as parameterized by a neural network, makes differentiating through a policy expensive. We resolve the first challenge by sampling provably unbiased derivatives to approximate and differentiate through optimality conditions, and the second challenge by using a low-rank approximation to the high-dimensional sample-based derivatives. We implement both Bellman-based and policy gradient-based decision-focused learning on three different MDP problems with missing parameters, and show that decision-focused learning performs better in generalization to unseen tasks.

PDF Details

AAMAS Conference 2021 Conference Paper

Risk-Aware Interventions in Public Health: Planning with Restless Multi-Armed Bandits

  • Aditya Mate
  • Andrew Perrault
  • Milind Tambe

Community Health Workers (CHWs) form an important component of health-care systems globally, especially in low-resource settings. CHWs are often tasked with monitoring the health of and intervening on their patient cohort. Previous work has developed several classes of Restless Multi-Armed Bandits (RMABs) that are computationally tractable and indexable, a condition that guarantees asymptotic optimality, for solving such health monitoring and intervention problems (HMIPs). However, existing solutions to HMIPs fail to account for risk-sensitivity considerations of CHWs in the planning stage and may run the danger of ignoring some patients completely because they are deemed less valuable to intervene on. Additionally, these also rely on patients reporting their state of adherence accurately when intervened upon. Towards tackling these issues, our contributions in this paper are as follows: (1) We develop an RMAB solution to HMIPs that allows for reward functions that are monotone increasing, rather than linear, in the belief state and also supports a wider class of observations. (2) We prove theoretical guarantees on the asymptotic optimality of our algorithm for any arbitrary reward function. Additionally, we show that for the specific reward function considered in previous work, our theoretical conditions are stronger than the state-of-the-art guarantees. (3) We show the applicability of these new results for addressing the three issues pertaining to: risk-sensitive planning, equitable allocation and reliance on perfect observations as highlighted above. We evaluate these techniques on both simulated as well as real data from a prevalent CHW task of monitoring adherence of tuberculosis patients to their prescribed medication in Mumbai, India and show improved performance over the state-of-the-art. Full paper and code is available at: https: //github. com/AdityaMate/risk-aware-bandits.

PDF

UAI Conference 2021 Conference Paper

Robust reinforcement learning under minimax regret for green security

  • Lily Xu
  • Andrew Perrault
  • Fei Fang 0001
  • Haipeng Chen 0001
  • Milind Tambe

Green security domains feature defenders who plan patrols in the face of uncertainty about the adversarial behavior of poachers, illegal loggers, and illegal fishers. Importantly, the deterrence effect of patrols on adversaries’ future behavior makes patrol planning a sequential decision-making problem. Therefore, we focus on robust sequential patrol planning for green security following the minimax regret criterion, which has not been considered in the literature. We formulate the problem as a game between the defender and nature who controls the parameter values of the adversarial behavior and design an algorithm MIRROR to find a robust policy. MIRROR uses two reinforcement learning–based oracles and solves a restricted game considering limited defender strategies and parameter values. We evaluate MIRROR on real-world poaching data.

Details

NeurIPS Conference 2020 Conference Paper

Automatically Learning Compact Quality-aware Surrogates for Optimization Problems

  • Kai Wang
  • Bryan Wilder
  • Andrew Perrault
  • Milind Tambe

Solving optimization problems with unknown parameters often requires learning a predictive model to predict the values of the unknown parameters and then solving the problem using these values. Recent work has shown that including the optimization problem as a layer in the model training pipeline results in predictions of the unobserved parameters that lead to higher decision quality. Unfortunately, this process comes at a large computational cost because the optimization problem must be solved and differentiated through in each training iteration; furthermore, it may also sometimes fail to improve solution quality due to non-smoothness issues that arise when training through a complex optimization layer. To address these shortcomings, we learn a low-dimensional surrogate model of a large optimization problem by representing the feasible space in terms of meta-variables, each of which is a linear combination of the original variables. By training a low-dimensional surrogate model end-to-end, and jointly with the predictive model, we achieve: i) a large reduction in training and inference time; and ii) improved performance by focusing attention on the more important variables in the optimization and learning in a smoother space. Empirically, we demonstrate these improvements on a non-convex adversary modeling task, a submodular recommendation task and a convex portfolio optimization task.

PDF Details

NeurIPS Conference 2020 Conference Paper

Collapsing Bandits and Their Application to Public Health Intervention

  • Aditya Mate
  • Jackson Killian
  • Haifeng Xu
  • Andrew Perrault
  • Milind Tambe

We propose and study Collapsing Bandits, a new restless multi-armed bandit (RMAB) setting in which each arm follows a binary-state Markovian process with a special structure: when an arm is played, the state is fully observed, thus“collapsing” any uncertainty, but when an arm is passive, no observation is made, thus allowing uncertainty to evolve. The goal is to keep as many arms in the “good” state as possible by planning a limited budget of actions per round. Such CollapsingBandits are natural models for many healthcare domains in which health workers must simultaneously monitor patients and deliver interventions in a way that maximizes the health of their patient cohort. Our main contributions are as follows: (i) Building on the Whittle index technique for RMABs, we derive conditions under which the Collapsing Bandits problem is indexable. Our derivation hinges on novel conditions that characterize when the optimal policies may take the form of either“forward” or “reverse” threshold policies. (ii) We exploit the optimality of threshold policies to build fast algorithms for computing the Whittle index, including a closed-form. (iii) We evaluate our algorithm on several data distributions including data from a real-world healthcare task in which a worker must monitor and deliver interventions to maximize their patients’ adherence to tuberculosis medication. Our algorithm achieves a 3-order-of-magnitude speedup compared to state-of-the-art RMAB techniques, while achieving similar performance. The code is available at: https: //github. com/AdityaMate/collapsing_bandits

PDF Details

AAAI Conference 2020 Conference Paper

End-to-End Game-Focused Learning of Adversary Behavior in Security Games

  • Andrew Perrault
  • Bryan Wilder
  • Eric Ewing
  • Aditya Mate
  • Bistra Dilkina
  • Milind Tambe

Stackelberg security games are a critical tool for maximizing the utility of limited defense resources to protect important targets from an intelligent adversary. Motivated by green security, where the defender may only observe an adversary’s response to defense on a limited set of targets, we study the problem of learning a defense that generalizes well to a new set of targets with novel feature values and combinations. Traditionally, this problem has been addressed via a two-stage approach where an adversary model is trained to maximize predictive accuracy without considering the defender’s optimization problem. We develop an end-to-end game-focused approach, where the adversary model is trained to maximize a surrogate for the defender’s expected utility. We show both in theory and experimental results that our game-focused approach achieves higher defender expected utility than the two-stage alternative when there is limited data.

PDF Details

UAI Conference 2020 Conference Paper

Robust Spatial-Temporal Incident Prediction

  • Ayan Mukhopadhyay
  • Kai Wang 0040
  • Andrew Perrault
  • Mykel J. Kochenderfer
  • Milind Tambe
  • Yevgeniy Vorobeychik

Spatio-temporal incident prediction is a central issue in law enforcement, with applications in fighting crimes like poaching, human trafficking, illegal fishing, burglaries and smuggling. However, state of the art approaches fail to account for evasion in response to predictive models, a common form of which is spatial shift in incident occurrence. We present a general approach for incident forecasting that is robust to spatial shifts. We propose two techniques for solving the resulting robust optimization problem: first, a constraint generation method guaranteed to yield an optimal solution, and second, a more scalable gradient-based approach. We then apply these techniques to both discrete-time and continuous-time robust incident forecasting. We evaluate our algorithms on two different real-world datasets, demonstrating that our approach is significantly more robust than conventional methods.

Details

AAMAS Conference 2019 Conference Paper

Experiential Preference Elicitation for Autonomous Heating and Cooling Systems

  • Andrew Perrault
  • Craig Boutilier

AI systems that act on behalf of users require knowledge of user preferences, which can be acquired by preference elicitation. In many settings, users can respond more easily and accurately to preference queries reflecting their current, or recently experienced, context (e. g. , state of the environment), than to those reflecting contexts further removed. We develop and study a formal model of experiential elicitation (EE) in which query costs and response noise are state-dependent. EE settings tightly couple the problems of control and elicitation. We provide some analysis of this abstract model, and illustrate its applicability in household heating/cooling management. We propose the use of relative value queries, asking the user to compare the immediate utility of two states, whose difficulty is related to the degree and recency of a user’s experience with those states. We develop a Gaussian process-based approach for modeling user preferences in dynamic EE domains and show that it accrues higher reward than several natural baselines.

PDF

AAMAS Conference 2017 Conference Paper

Multiple-Profile Prediction-of-Use Games

  • Andrew Perrault
  • Craig Boutilier

Prediction-of-use (POU) games were developed by Vinyals et al. [4] to address the mismatch between the costs of energy suppliers and the incentives imposed on consumers by a fixed-rate electricity tariff. However, the POU games framework does not address the question of how consumers should coordinate to maximize social welfare. To address this, we develop an extension to POU games, which we term MPOU games, where agents report multiple acceptable electricity use profiles. We show that MPOU games have many of the same properties that make POU games attractive, e. g. , convexity. Despite this, MPOU games introduce new incentive issues that prevent the consequences of convexity from being exploited directly, a problem we analyze and resolve. We validate our approach with experimental results using utility models learned from real electricity use data.

PDF

IJCAI Conference 2017 Conference Paper

Multiple-Profile Prediction-of-Use Games

  • Andrew Perrault
  • Craig Boutilier

Prediction-of-use (POU) games (Robu et al. , 2017) address the mismatch between energy supplier costs and the incentives imposed on consumers by a fixed-rate electricity tariff. However, the framework does not address how consumers should coordinate to maximize social welfare. To address this, we develop MPOU games, an extension of POU games in which agents report multiple acceptable electricity use profiles. We show that MPOU games share many attractive properties with POU games (e. g. , convexity). Despite this, MPOU games introduce new incentive issues that prevent the consequences of convexity from being exploited directly, a problem we analyze and resolve. We validate our approach with experimental results using utility models learned from real electricity use data.

PDF Details

AAMAS Conference 2016 Conference Paper

Strategy-Proofness in the Stable Matching Problem with Couples

  • Andrew Perrault
  • Joanna Drummond
  • Fahiem Bacchus

Stable matching problems (SMPs) arising in real-world markets often have extra complementarities in the participants’ preferences. These complementarities break many of the theoretical properties of SMP and make it computationally hard to find a stable matching. A common complementarity is the introduction of couples in labor markets, which gives rise to the stable matching problem with couples (SMP-C). A major concern in markets is strategy-proofness since markets that are easily manipulated often unravel. In this paper we provide some key insights into the issue of strategyproofness in SMP-C. We provide theoretical results that relate the set of resident Pareto optimal stable matchings (RPopt ) admitted by an SMP-C instance to the ability of the residents to manipulate. We show that a mechanism returning an RPopt matching is, in certain cases, strategyproof against residents attempting to manipulate by truncating their preference lists. We provide an algorithm for finding an RPopt matching when one exists. And finally, we study empirically the frequency of multiple stable and multiple RPopt matchings as the market sizes grows, and under different proportions of couples in the market. Our empirical results indicate that SMP-C becomes less susceptible to manipulation as both the size of the market grows and the fraction of couples in the market shrinks. General Terms Economics, Algorithms, Theory

PDF

IJCAI Conference 2015 Conference Paper

Approximately Stable Pricing for Coordinated Purchasing of Electricity

  • Andrew Perrault
  • Craig Boutilier

Matching markets are often used in exchange settings (e. g. , supply chain) to increase economic efficiency while respecting certain global constraints on outcomes. We investigate their application to pricing and cost sharing in group purchasing of electricity in smart grid settings. The task is complicated by the complexities of producer cost functions due to constraints on generation from different sources (they are sufficiently complex that welfare-optimal matchings are not usually in equilibrium). We develop two novel cost sharing schemes: one based on Shapley values that is “fair, ” but computationally intensive; and one that captures many of the essential properties of Shapley pricing, but scales to large numbers of consumers. Empirical results show these schemes achieve a high degree of stability in practice and can be made more stable by sacrificing small amounts (< 2%) of social welfare.

PDF Details

IJCAI Conference 2015 Conference Paper

SAT Is an Effective and Complete Method for Solving Stable Matching Problems with Couples

  • Joanna Drummond
  • Andrew Perrault
  • Fahiem Bacchus

Stable matchings can be computed by deferred acceptance (DA) algorithms. However such algorithms become incomplete when complementarities exist among the agent preferences: they can fail to find a stable matching even when one exists. In this paper we examine stable matching problems arising from labour market with couples (SMP-C). The classical problem of matching residents into hospital programs is an example. Couples introduce complementarities under which DA algorithms become incomplete. In fact, SMP-C is NP-complete. Inspired by advances in SAT and integer programming (IP) solvers we investigate encoding SMP-C into SAT and IP and then using state-of-the-art SAT and IP solvers to solve it. We also implemented two previous DA algorithms. After comparing the performance of these different solution methods we find that encoding to SAT can be surprisingly effective, but that our encoding to IP does not scale as well. Using our SAT encoding we are able to determine that the DA algorithms fail on a non-trivial number of cases where a stable matching exists. The SAT and IP encodings also have the property that they can verify that no stable matching exists, something that the DA algorithms cannot do.

PDF Details
v2026.09.13