Combinatorial Bandits under Strategic Manipulations
  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(m\log T + m B_{max})$ under strategic manipulations, where $T$ is the time
horizon, $m$ is the number of arms, and $B_{max}$ 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.
