ترجمه فارسی مقاله راهزنان تصادفی قوی به حملات مخالف

چکیده

This paper investigates stochastic multi-armed bandit algorithms that are robust to adversarial attacks, where an attacker can first observe the learner’s action and {then} alter their reward observation. We study two cases of this model, with or without the knowledge of an attack budget $C$, defined as an upper bound of the summation of the difference between the actual and altered rewards. For both cases, we devise two types of algorithms with regret bounds having additive or multiplicative $C$ dependence terms. For the known attack budget case, we prove our algorithms achieve the regret bound of ${O}((K/Δ)\log T + KC)$ and $\tilde{O}(\sqrt{KTC})$ for the additive and multiplicative $C$ terms, respectively, where $K$ is the number of arms, $T$ is the time horizon, $Δ$ is the gap between the expected rewards of the optimal arm and the second-best arm, and $\tilde{O}$ hides the logarithmic factors. For the unknown case, we prove our algorithms achieve the regret bound of $\tilde{O}(\sqrt{KT} + KC^2)$ and $\tilde{O}(KC\sqrt{T})$ for the additive and multiplicative $C$ terms, respectively. In addition to these upper bound results, we provide several lower bounds showing the tightness of our bounds and the optimality of our algorithms. These results delineate an intrinsic separation between the bandits with attacks and corruption models [Lykouris et al., 2018].

چکیده به فارسی (ترجمه ماشینی)

در این مقاله به بررسی الگوریتم های راهزن چند مسلح تصادفی که در برابر حملات مخالف قوی هستند ، جایی که یک مهاجم می تواند ابتدا عملکرد یادگیرنده را رعایت کند و {سپس مشاهده پاداش خود را تغییر دهد.ما دو مورد از این مدل را با یا بدون اطلاع بودجه حمله $ c $ ، که به عنوان مرز بالایی از جمع بندی تفاوت بین پاداش های واقعی و تغییر یافته تعریف شده است ، مطالعه می کنیم.برای هر دو مورد ، ما دو نوع الگوریتم را با محدودیت های پشیمانی با اصطلاحات وابستگی افزودنی یا چند برابر $ C $ ابداع می کنیم.برای مورد بودجه حمله شناخته شده ، ما ثابت می کنیم که الگوریتم های ما به حد پشیمانی $ {o} ((k/δ) \ log t + kc) $ و $ \ tilde {o} (\ sqrt {ktc}) $ برایافزودنی و ضرب $ C $ به ترتیب ، به ترتیب ، که در آن $ k $ تعداد اسلحه است ، $ t $ افق زمانی است ، $ δ $ شکاف بین پاداش های مورد انتظار بازوی بهینه و بازوی دوم است و$ \ tilde {o} $ عوامل لگاریتمی را پنهان می کند.برای مورد ناشناخته ، ما ثابت می کنیم که الگوریتم های ما به پشیمانی از $ \ tilde {o} (\ sqrt {kt} + kc^2) $ و $ \ tilde {o} (kc \ sqrt {t}) $ برایاصطلاحات افزودنی و چند برابر به ترتیب C $ C $.علاوه بر این نتایج حد بالایی ، ما چندین مرز پایین تر ارائه می دهیم که نشان دهنده سفتی مرزهای ما و بهینه بودن الگوریتم های ما است.این نتایج ، جدایی ذاتی بین راهزنان با حملات و مدل های فساد را مشخص می کند [لیکوریس و همکاران ، 2018].