# A Multi-Arm Bandit Approach To Subset Selection Under Constraints

arXiv: https://arxiv.org/abs/2102.04824 · HTML: https://mlsanity.com/paper/2102.04824/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 47 references that are in the map.
- First posted on arXiv 9 Feb 2021.

## Builds on (most cited first, 7 of 7)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014)
- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [Resourceful Contextual Bandits](https://mlsanity.com/paper/1402.6779/) (2014)
- [Designing Truthful Contextual Multi-Armed Bandits based Sponsored Search Auctions](https://mlsanity.com/paper/2002.11349/) (2020)

## Built on by (most cited first, 3 of 3)

- [Budgeted Combinatorial Multi-Armed Bandits](https://mlsanity.com/paper/2202.03704/) (2022)
- [Differentially Private Federated Combinatorial Bandits with Constraints](https://mlsanity.com/paper/2206.13192/) (2022)
- [Fairness and Privacy Guarantees in Federated Contextual Bandits](https://mlsanity.com/paper/2402.03531/) (2024)

## Abstract (arXiv)

We explore the class of problems where a central planner needs to select a subset of agents, each with different quality and cost. The planner wants to maximize its utility while ensuring that the average quality of the selected agents is above a certain threshold. When the agents' quality is known, we formulate our problem as an integer linear program (ILP) and propose a deterministic algorithm, namely dpss that provides an exact solution to our ILP. We then consider the setting when the qualities of the agents are unknown. We model this as a Multi-Arm Bandit (MAB) problem and propose newalgo to learn the qualities over multiple rounds. We show that after a certain number of rounds, τ, newalgo outputs a subset of agents that satisfy the average quality constraint with a high probability. Next, we provide bounds on τ and prove that after τ rounds, the algorithm incurs a regret of O(ln T), where T is the total number of rounds. We further illustrate the efficacy of newalgo through simulations. To overcome the computational limitations of dpss, we propose a polynomial-time greedy algorithm, namely greedy, that provides an approximate solution to our ILP. We also compare the performance of dpss and greedy through experiments.