# Combinatorial Bandits under Strategic Manipulations

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 52 references that are in the map.
- First posted on arXiv 25 Feb 2021.

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

- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [Better Algorithms for Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/1902.08647/) (2019)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Stochastic Linear Bandits Robust to Adversarial Attacks](https://mlsanity.com/paper/2007.03285/) (2020)
- [Adversarial Attacks on Stochastic Bandits](https://mlsanity.com/paper/1810.12188/) (2018)
- [Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously](https://mlsanity.com/paper/1901.08779/) (2019)
- [Data Poisoning Attacks on Stochastic Bandits](https://mlsanity.com/paper/1905.06494/) (2019)
- [PAC-Learning for Strategic Classification](https://mlsanity.com/paper/2012.03310/) (2020)
- [The Strategic Perceptron](https://mlsanity.com/paper/2008.01710/) (2020)
- [Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers](https://mlsanity.com/paper/1703.04940/) (2017)
- [Improved Algorithm on Online Clustering of Bandits](https://mlsanity.com/paper/1902.09162/) (2019)
- [Adversarial Attacks on Linear Contextual Bandits](https://mlsanity.com/paper/2002.03839/) (2020)
- [Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency](https://mlsanity.com/paper/1404.0900/) (2014)
- [Top-k Combinatorial Bandits with Full-Bandit Feedback](https://mlsanity.com/paper/1905.12624/) (2019)
- [Best Arm Identification for Contaminated Bandits](https://mlsanity.com/paper/1802.09514/) (2018)
- [Combinatorial Semi-Bandits with Knapsacks](https://mlsanity.com/paper/1705.08110/) (2017)
- [Online Influence Maximization under Linear Threshold Model](https://mlsanity.com/paper/2011.06378/) (2020)
- [Multi-armed Bandit Problems with Strategic Arms](https://mlsanity.com/paper/1706.09060/) (2017)
- [The Intrinsic Robustness of Stochastic Bandits to Strategic Manipulation](https://mlsanity.com/paper/1906.01528/) (2019)
- [Adversarial Combinatorial Bandits with General Non-linear Reward Functions](https://mlsanity.com/paper/2101.01301/) (2021)
- [Stochastic Online Learning with Probabilistic Graph Feedback](https://mlsanity.com/paper/1903.01083/) (2019)
- [Linear Regression from Strategic Data Sources](https://mlsanity.com/paper/1309.7824/) (2013)
- [Combining Crowd and Machines for Multi-predicate Item Screening](https://mlsanity.com/paper/1904.00714/) (2019)

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

- [Adversarial Attacks on Adversarial Bandits](https://mlsanity.com/paper/2301.12595/) (2023)
- [Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendation](https://mlsanity.com/paper/2311.15647/) (2023)
- [Strategic Linear Contextual Bandits](https://mlsanity.com/paper/2406.00551/) (2024)
- [Adversarial Attacks on Combinatorial Multi-Armed Bandits](https://mlsanity.com/paper/2310.05308/) (2023)
- [COBRA: Contextual Bandit Algorithm for Ensuring Truthful Strategic Agents](https://mlsanity.com/paper/2505.23720/) (2025)
- [CoCoB: Adaptive Collaborative Combinatorial Bandits for Online Recommendation](https://mlsanity.com/paper/2505.03840/) (2025)

## Abstract (arXiv)

Strategic behavior against sequential learning methods, such as "click framing" in real recommendation systems, have been widely observed. Motivated by such behavior we study the problem of combinatorial multi-armed bandits (CMAB) under strategic manipulations of rewards, where each arm can modify the emitted reward signals for its own interest. This characterization of the adversarial behavior is a relaxation of previously well-studied settings such as adversarial attacks and adversarial corruption. We propose a strategic variant of the combinatorial UCB algorithm, which has a regret of at most O(mlog T + m Bmax) under strategic manipulations, where T is the time horizon, m is the number of arms, and Bmax is the maximum budget of an arm. We provide lower bounds on the budget for arms to incur certain regret of the bandit algorithm. Extensive experiments on online worker selection for crowdsourcing systems, online influence maximization and online recommendations with both synthetic and real datasets corroborate our theoretical findings on robustness and regret bounds, in a variety of regimes of manipulation budgets.