# Multi-Armed Bandits with Minimum Aggregated Revenue Constraints

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 35 references that are in the map.
- First posted on arXiv 14 Oct 2025.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Linear Stochastic Bandits Under Safety Constraints](https://mlsanity.com/paper/1908.05814/) (2019)
- [Combinatorial Sleeping Bandits with Fairness Constraints](https://mlsanity.com/paper/1901.04891/) (2019)
- [Stochastic Bandits with Linear Constraints](https://mlsanity.com/paper/2006.10185/) (2020)
- [Conservative Bandits](https://mlsanity.com/paper/1602.04282/) (2016)
- [Resourceful Contextual Bandits](https://mlsanity.com/paper/1402.6779/) (2014)
- [An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives](https://mlsanity.com/paper/1506.03374/) (2015)
- [Fairness of Exposure in Stochastic Bandits](https://mlsanity.com/paper/2103.02735/) (2021)
- [Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression](https://mlsanity.com/paper/2211.07484/) (2022)
- [Online Bidding Algorithms for Return-on-Spend Constrained Advertisers](https://mlsanity.com/paper/2208.13713/) (2022)
- [Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Risk](https://mlsanity.com/paper/2204.00706/) (2022)
- [Safe Linear Bandits over Unknown Polytopes](https://mlsanity.com/paper/2209.13694/) (2022)
- [Non-monotonic Resource Utilization in the Bandits with Knapsacks Problem](https://mlsanity.com/paper/2209.12013/) (2022)
- [Optimal Contextual Bandits with Knapsacks under Realizability via Regression Oracles](https://mlsanity.com/paper/2210.11834/) (2022)
- [Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints](https://mlsanity.com/paper/2405.16118/) (2024)
- [Conservative Contextual Bandits: Beyond Linear Representations](https://mlsanity.com/paper/2412.06165/) (2024)
- [Small Total-Cost Constraints in Contextual Bandits with Knapsacks, with Application to Fairness](https://mlsanity.com/paper/2305.15807/) (2023)
- [Strategic Multi-Armed Bandit Problems Under Debt-Free Reporting](https://mlsanity.com/paper/2501.16018/) (2025)

## Abstract (arXiv)

We examine a multi-armed bandit problem with contextual information, where the objective is to ensure that each arm receives a minimum aggregated reward across contexts while simultaneously maximizing the total cumulative reward. This framework captures a broad class of real-world applications where fair revenue allocation is critical and contextual variation is inherent. The cross-context aggregation of minimum reward constraints, while enabling better performance and easier feasibility, introduces significant technical challenges -- particularly the absence of closed-form optimal allocations typically available in standard MAB settings. We design and analyze algorithms that either optimistically prioritize performance or pessimistically enforce constraint satisfaction. For each algorithm, we derive problem-dependent upper bounds on both regret and constraint violations. Furthermore, we establish a lower bound demonstrating that the dependence on the time horizon in our results is optimal in general and revealing fundamental limitations of the free exploration principle leveraged in prior work.