Multi-armed Bandit Algorithm against Strategic Replication
This addresses a security and fairness issue in bandit algorithms for systems with strategic agents, offering a novel solution to prevent exploitation.
The paper tackles the problem of strategic replication in multi-armed bandit settings, where agents submit duplicate arms to exploit algorithms, and proposes Hierarchical UCB (H-UCB) and Robust Hierarchical UCB (RH-UCB) algorithms that achieve O(ln T) and sublinear regret, respectively, as verified by experiments.
We consider a multi-armed bandit problem in which a set of arms is registered by each agent, and the agent receives reward when its arm is selected. An agent might strategically submit more arms with replications, which can bring more reward by abusing the bandit algorithm's exploration-exploitation balance. Our analysis reveals that a standard algorithm indeed fails at preventing replication and suffers from linear regret in time $T$. We aim to design a bandit algorithm which demotivates replications and also achieves a small cumulative regret. We devise Hierarchical UCB (H-UCB) of replication-proof, which has $O(\ln T)$-regret under any equilibrium. We further propose Robust Hierarchical UCB (RH-UCB) which has a sublinear regret even in a realistic scenario with irrational agents replicating careless. We verify our theoretical findings through numerical experiments.