Encrypted Linear Contextual Bandit
Contextual bandit is a general framework for online learning in sequential decision-making problems that has found application in a wide range of domains, including recommendation systems, online advertising, and clinical trials. A critical aspect of bandit methods is that they require to observe the contexts --i.e., individual or group-level data-- and rewards in order to solve the sequential problem. The large deployment in industrial applications has increased interest in methods that preserve the users' privacy. In this paper, we introduce a privacy-preserving bandit framework based on homomorphic encryption{\color{violet} which allows computations using encrypted data}. The algorithm \textit{only} observes encrypted information (contexts and rewards) and has no ability to decrypt it. Leveraging the properties of homomorphic encryption, we show that despite the complexity of the setting, it is possible to solve linear contextual bandits over encrypted data with a $\widetilde{O}(d\sqrt{T})$ regret bound in any linear contextual bandit problem, while keeping data encrypted.
Code (0)
등록된 구현이 없습니다.
Tasks
Decision MakingMulti-Armed BanditsPrivacy PreservingRecommendation SystemsSequential Decision MakingSimilar Papers 제목 키워드 기반
Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms
In this paper, we address the stochastic contextual linear bandit problem, where a decision maker is provided a context (a random set of actions drawn from a distribution). The expected reward of each action is specified…
Multi-Armed BanditsOSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits
We consider the stochastic linear (multi-armed) contextual bandit problem with the possibility of hidden simple multi-armed bandit structure in which the rewards are independent of the contextual information. Algorithms …
Multi-Armed BanditsOn the Optimal Regret of Locally Private Linear Contextual Bandit
Contextual bandit with linear reward functions is among one of the most extensively studied models in bandit and online learning research. Recently, there has been increasing interest in designing \emph{locally private} …
Contextual Bandits with Random Projection
Contextual bandits with linear payoffs, which are also known as linear bandits, provide a powerful alternative for solving practical problems of sequential decisions, e.g., online advertisements. In the era of big data, …
Multi-Armed BanditsRobust Stochastic Linear Contextual Bandits Under Adversarial Attacks
Stochastic linear contextual bandit algorithms have substantial applications in practice, such as recommender systems, online advertising, clinical trials, etc. Recent works show that optimal bandit algorithms are vulner…
Multi-Armed BanditsRecommendation Systems