Author name cluster

Avinandan Bose

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.

6 papers

2 author rows

NeurIPS Conference 2024 Conference Paper

Initializing Services in Interactive ML Systems for Diverse Users

Avinandan Bose
Mihaela Curmei
Daniel L. Jiang
Jamie Morgenstern
Sarah Dean
Lillian J. Ratliff
Maryam Fazel

This paper investigates ML systems serving a group of users, with multiple models/services, each aimed at specializing to a sub-group of users. We consider settings where upon deploying a set of services, users choose the one minimizing their personal losses and the learner iteratively learns by interacting with diverse users. Prior research shows that the outcomes of learning dynamics, which comprise both the services' adjustments and users' service selections, hinge significantly on the initial conditions. However, finding good initial conditions faces two main challenges: (i) \emph{Bandit feedback: } Typically, data on user preferences are not available before deploying services and observing user behavior; (ii) \emph{Suboptimal local solutions: } The total loss landscape (i. e. , the sum of loss functions across all users and services) is not convex and gradient-based algorithms can get stuck in poor local minima. We address these challenges with a randomized algorithm to adaptively select a minimal set of users for data collection in order to initialize a set of services. Under mild assumptions on the loss functions, we prove that our initialization leads to a total loss within a factor of the \textit{globally optimal total loss, with complete user preference data}, and this factor scales logarithmically in the number of services. This result is a generalization of the well-known $k$-means++ guarantee to a broad problem class which is also of independent interest. The theory is complemented by experiments on real as well as semi-synthetic datasets.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

Tackling Stackelberg Network Interdiction against a Boundedly Rational Adversary

Tien Mai
Avinandan Bose
Arunesh Sinha
Thanh Nguyen
Ayushman Kumar singh

This work studies Stackelberg network interdiction games --- an important class of games in which a defender first allocates (randomized) defense resources to a set of critical nodes on a graph while an adversary chooses its path to attack these nodes accordingly. We consider a boundedly rational adversary in which the adversary's response model is based on a dynamic form of classic logit-based (quantal response) discrete choice models. The resulting optimization is non-convex and additionally, involves complex terms that sum over exponentially many paths. We tackle these computational challenges by presenting new efficient algorithms with solution guarantees. First, we present a near optimal solution method based on path sampling, piece-wise linear approximation and mixed-integer linear programming (MILP) reformulation. Second, we explore a dynamic programming based method, addressing the exponentially-many-path challenge. We then show that the gradient of the non-convex objective can also be computed in polynomial time, which allows us to use a gradient-based method to solve the problem efficiently. Experiments based on instances of different sizes demonstrate the efficiency of our approach in achieving near-optimal solutions.

PDF Details DOI

AAAI Conference 2023 Conference Paper

A Fair Incentive Scheme for Community Health Workers

Avinandan Bose
Tracey Li
Arunesh Sinha
Tien Mai

Community health workers (CHWs) play a crucial role in the last mile delivery of essential health services to underserved populations in low-income countries. Many nongovernmental organizations (NGOs) provide training and support to enable CHWs to deliver health services to their communities, with no charge to the recipients of the services. This includes monetary compensation for the work that CHWs perform, which is broken down into a series of well defined tasks. In this work, we partner with a NGO D-Tree International to design a fair monetary compensation scheme for tasks performed by CHWs in the semi-autonomous region of Zanzibar in Tanzania, Africa. In consultation with stakeholders, we interpret fairness as the equal opportunity to earn, which means that each CHW has the opportunity to earn roughly the same total payment over a given T month period, if the CHW reacts to the incentive scheme almost rationally. We model this problem as a reward design problem for a Markov Decision Process (MDP) formulation for the CHWs’ earning. There is a need for the mechanism to be simple so that it is understood by the CHWs, thus, we explore linear and piecewise linear rewards in the CHWs’ measured units of work. We solve this design problem via a novel policy-reward gradient result. Our experiments using two real world parameters from the ground provide evidence of reasonable incentive output by our scheme.

PDF Details DOI

ECAI Conference 2023 Conference Paper

On Sustainable Ride Pooling Through Conditional Expected Value Decomposition

Avinandan Bose
Hao Jiang
Pradeep Varakantham
Zichang Ge

Centralized Multi-Agent Reinforcement Learning (MARL) presents itself as an ideal framework for aggregation companies (e. g. , Uber, Lyft, Deliveroo) that have to take a sequential set of centralized decisions on assigning individual agents (typically resources like taxis, food delivery personnel) to customer requests online in the presence of demand uncertainty. However, centralized learning is especially challenging in such very large scale environments, with thousands of agents/resources and hundreds of thousands of requests coming in each day. In this paper, we provide a novel value decomposition mechanism that is able to tackle the scale and provide high quality (matching) decisions at each time step. We show that our value decomposition approach, Conditional Expectation based Value Decomposition (CEVD) is more sustainable (requires 9. 9% fewer vehicles to serve equal number of requests) and more efficient (serves 9. 76% more requests, while traveling 13. 32% lesser distance) than the current best approach over two different city scale (New York and Chicago) benchmarks for ride pooling using taxis.

Details

AAAI Conference 2022 Conference Paper

Multiscale Generative Models: Improving Performance of a Generative Model Using Feedback from Other Dependent Generative Models

Changyu Chen
Avinandan Bose
Shih-Fen Cheng
Arunesh Sinha

Realistic fine-grained multi-agent simulation of real-world complex systems is crucial for many downstream tasks such as reinforcement learning. Recent work has used generative models (GANs in particular) for providing high-fidelity simulation of real-world systems. However, such generative models are often monolithic and miss out on modeling the interaction in multi-agent systems. In this work, we take a first step towards building multiple interacting generative models (GANs) that reflects the interaction in real world. We build and analyze a hierarchical set-up where a higher-level GAN is conditioned on the output of multiple lower-level GANs. We present a technique of using feedback from the higherlevel GAN to improve performance of lower-level GANs. We mathematically characterize the conditions under which our technique is impactful, including understanding the transfer learning nature of our set-up. We present three distinct experiments on synthetic data, time series data, and image domain, revealing the wide applicability of our technique.

PDF Details

NeurIPS Conference 2022 Conference Paper

Scalable Distributional Robustness in a Class of Non-Convex Optimization with Guarantees

Avinandan Bose
Arunesh Sinha
Tien Mai

Distributionally robust optimization (DRO) has shown a lot of promise in providing robustness in learning as well as sample-based optimization problems. We endeavor to provide DRO solutions for a class of sum of fractionals, non-convex optimization which is used for decision making in prominent areas such as facility location and security games. In contrast to previous work, we find it more tractable to optimize the equivalent variance regularized form of DRO rather than the minimax form. We transform the variance regularized form to a mixed-integer second-order cone program (MISOCP), which, while guaranteeing global optimality, does not scale enough to solve problems with real-world datasets. We further propose two abstraction approaches based on clustering and stratified sampling to increase scalability, which we then use for real-world datasets. Importantly, we provide global optimality guarantees for our approach and show experimentally that our solution quality is better than the locally optimal ones achieved by state-of-the-art gradient-based methods. We experimentally compare our different approaches and baselines and reveal nuanced properties of a DRO solution.

PDF Details