Multi-Armed Bandits with Minimum Aggregated Revenue Constraints
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912646875316224 |
|---|---|
| author | Yahmed, Ahmed Ben Ferchichi, Hafedh El Abeille, Marc Perchet, Vianney |
| author_facet | Yahmed, Ahmed Ben Ferchichi, Hafedh El Abeille, Marc Perchet, Vianney |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_12523 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Multi-Armed Bandits with Minimum Aggregated Revenue Constraints Yahmed, Ahmed Ben Ferchichi, Hafedh El Abeille, Marc Perchet, Vianney Machine Learning Optimization and Control 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. |
| title | Multi-Armed Bandits with Minimum Aggregated Revenue Constraints |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2510.12523 |