A Resilience Framework for Bi-Criteria Combinatorial Optimization with Bandit Feedback
Not on the map. Why?
Abstract (arXiv)
We study bi-criteria combinatorial optimization under noisy function evaluations. While resilience and black-box offline-to-online reductions have been studied in single-objective settings, extending these ideas to bi-criteria problems introduces new challenges due to the coupled degradation of approximation guarantees for objectives and constraints. We introduce a notion of (α,β,δ,textttN)-resilience for bi-criteria approximation algorithms, capturing how joint approximation guarantees degrade under bounded (possibly worst-case) oracle noise, and develop a general black-box framework that converts any resilient offline algorithm into an online algorithm for bi-criteria combinatorial multi-armed bandits with bandit feedback. The resulting online guarantees achieve sublinear regret and cumulative constraint violation of order tildeO(δ2/3textttN1/3T2/3) without requiring structural assumptions such as linearity, submodularity, or semi-bandit feedback on the noisy functions. We demonstrate the applicability of the framework by establishing resilience for several classical greedy algorithms in submodular optimization.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 20 of its 40 references that are in the map. First posted on arXiv 15 Mar 2025.
Builds on
20 of 40 references.
References · 20
- 2018Thompson Sampling for Combinatorial Semi-Banditscited by 78
- 2019Combinatorial Sleeping Bandits with Fairness Constraintscited by 68
- 2016Combinatorial Multi-Armed Bandit with General Reward Functionscited by 56
- 2013Submodular Optimization with Submodular Cover and Submodular Knapsack Constraintscited by 40
- 2021Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimizationcited by 40
- 2023A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedbackcited by 19
- 2023Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedbackcited by 19
- 2023Combinatorial Stochastic-Greedy Banditcited by 18
- 2014Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applicationscited by 16
- 2020Submodular Bandit Problem Under Multiple Constraintscited by 15
- 2021Adversarial Combinatorial Bandits with General Non-linear Reward Functionscited by 14
- 2024Federated Combinatorial Multi-Agent Multi-Armed Banditscited by 11
8 more
- 2019Submodular Cost Submodular Cover with an Approximate Oraclecited by 7
- 2021The Hardness Analysis of Thompson Sampling for Combinatorial Semi-bandits with Greedy Oraclecited by 7
- 2023Nearly Minimax Optimal Submodular Maximization with Bandit Feedbackcited by 7
- 2023Bicriteria Approximation Algorithms for the Submodular Cover Problemcited by 6
- 2024Fair Submodular Covercited by 6
- 2016An Efficient Streaming Algorithm for the Submodular Cover Problemcited by 3
- 2024Stochastic k-Submodular Bandits with Full Bandit Feedbackcited by 3
- 2017Cost-Effective Seed Selection in Online Social Networkscited by 1
Built on by
Not cited yet.
Similar, not cited
Close in wording, no citation either way
- 2026Offline Local Search for Online Stochastic Bandits
- 2021Combinatorial Bandits without Total Order for Arms
- 2026On the Complexity of Preference-Based Bandits
- 2026Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions
- 2026Offline-to-Online Learning in Linear Bandits
- 2024Is Offline Decision Making Possible with Only Few Samples? Reliable Decisions in Data-Starved Bandits via Trust Region Enhancement
- 2021Adapting to Misspecification in Contextual Bandits with Offline Regression Oracles
- 2023Oracle-Efficient Pessimism: Offline Policy Optimization in Contextual Bandits