Secure Best Arm Identification in the Presence of a Copycat

Consider the problem of best arm identification with a security constraint. Specifically, assume a setup of stochastic linear bandits with K arms of dimension d. In each arm pull, the player receives a reward that is the sum of the dot product of the arm with an unknown parameter vector and independent noise. The player's goal is to identify the best arm after T arm pulls. Moreover, assume a copycat Chloe is observing the arm pulls. The player wishes to keep Chloe ignorant of the best arm. While a minimax--optimal algorithm identifies the best arm with an Omegaleft(fracTlog(d)right) error exponent, it easily reveals its best-arm estimate to an outside observer, as the best arms are played more frequently. A naive secure algorithm that plays all arms equally results in an Omegaleft(fracTdright) exponent. In this paper, we propose a secure algorithm that plays with coded arms. The algorithm does not require any key or cryptographic primitives, yet achieves an Omegaleft(fracTlog2(d)right) exponent while revealing almost no information on the best arm.