提出一种无需加密的编码机制，让博弈者在不暴露最优臂的情况下高效识别最佳选项。
Secure Best Arm Identification in the Presence of a Copycat
- 用编码策略混合选择各臂，避免频繁重复试探最优臂
- 误差指数达 Ω(T/log²(d))，显著优于均匀随机的 Ω(T/d)
- 适合对隐私敏感的在线决策场景，如金融或医疗推荐
研究带安全约束的最优臂识别问题。在包含 K 个动作、维度为 d 的随机线性老虎机中，玩家在 T 次动作后需识别出最优臂。假设存在一个观察者 Chloe，会监控所有动作选择。玩家希望使 Chloe 无法推断出最优臂。已知最小最大最优算法虽能实现 Ω(T/log(d)) 的误差指数，但因高频选择最优臂而泄露信息；而简单均匀采样仅能达到 Ω(T/d) 的指数。本文提出一种基于‘编码动作’的安全算法，无需密钥或密码原语，却可实现 Ω(T/log²(d)) 的误差指数，同时几乎不向外部观察者透露最优臂的信息。
原文摘要 · Abstract (English)
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 $Ω\left(\frac{T}{\log(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 $Ω\left(\frac{T}{d}\right)$ exponent. In this paper, we propose a secure algorithm that plays with \emph{coded arms}. The algorithm does not require any key or cryptographic primitives, yet achieves an $Ω\left(\frac{T}{\log^2(d)}\right)$ exponent while revealing almost no information on the best arm.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。