2025/07/25 by Cohen, Asaf, Günlü, Onur
#FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.2507.18975
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 Ω((T)/(log(d))) 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 Ω((T)/(d)) 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 Ω((T)/(log2(d))) exponent while revealing almost no information on the best arm.