Abstract
ベストアーム同定（BAI）問題は、適応的臨床試験の設計、ハイパーパラメータの調整、ユーザ研究の実施といったデータに敏感なアプリケーションで、次第に用いられるようになっている。これらのアプリケーションによって生じるデータプライバシー上の懸念に動機づけられ、局所モデルと中央モデルの両方において固定の信頼度のもとでのBAI問題、すなわち
-localおよび
-globalの差分プライバシー（DP）を研究する。まず、プライバシーのコストを定量化するために、
-global DPまたは
-local DPを満たす任意の
-correct BAIアルゴリズムのサンプル複雑性について下界を導出する。我々の下界は、2つのプライバシー・レジーム（領域）の存在を示唆している。高プライバシー・レジームでは、困難さは、プライバシーと、全変動（Total Variation）に関わる新しい情報理論的量の結合効果に依存する。低プライバシー・レジームでは、下界は非プライベートの下界に還元される。Top Twoアルゴリズムの
-local DPおよび
-global DPの変種として、それぞれCTB-TTとAdaP-TT*を提案する。
-local DPにおいて、CTB-TTは、Randomised Responseに基づく手段のためのプライベート推定量を差し込むことで漸近的に最適となる。$$-global DPにおいて、平均の我々のプライベート推定量は、アーム依存の適応的エピソードで動作し、良好なプライバシー-効用のトレードオフを保証するためにラプラスノイズを加える。輸送コスト（transportation costs）を適応させることで、AdaP-TT*の期待サンプル複雑性は、乗法定数の範囲で漸近的下界に到達する。
