We study the problem of preserving privacy while still providing high utility in sequential decision making scenarios in a changing environment. We consider abruptly changing environment: the environment remains constant during periods and it changes at unknown time instants. To formulate this problem, we propose a variant of multi-armed bandits called non-stationary stochastic corrupt bandits. We construct an algorithm called SW-KLUCB-CF and prove an upper bound on its utility using the performance measure of regret. The proven regret upper bound for SW-KLUCB-CF is near-optimal in the number of time steps and matches the best known bound for analogous problems in terms of the number of time steps and the number of changes. Moreover, we present a provably optimal mechanism which can guarantee the desired level of local differential privacy while providing high utility.

研究了在序列决策场景中如何在保持隐私的同时提供高效用性的问题。我们提出了一种非平稳随机腐败老虎机并构建了一个叫做SW-KLUCB-CF的算法，并证明了它的效用的上界。我们提供了一种可证明最优的机制，可以在提供高效用性的同时保证期望的本地差分隐私水平。

在动态环境下的序列决策中使用本地差分隐私