Publication

Differentially Private Anonymous Bandits for Multi-User Systems

2026

Abstract

In this work, we develop a unified multi-user multi-armed bandit framework that integrates differential privacy (DP) with anonymous feedback across three privacy models: (1) a centralized DP model, where a trusted server adds noise; (2) a Local DP model, where users randomize their own data; and (3) a novel Semi-Central DP model, in which a trusted anonymity agent aggregates and perturbs rewards before passing them to an untrusted server. Our algorithms enable N users to collaborate in an ϵ-differentially private and C-anonymous manner, while maintaining low regret. We establish regret bounds of Õ(NC √KTα)/ϵ) under the Local DP model, Õ(NC √KTα) + N(Cα)3/4 T1/4 K/ϵ) under the Central DP model, and Õ(NC √KTα) + N √CKTα)/ϵ) under the Semi-Central DP model, where T denotes the time horizon, K denotes the number of arms, and α represents a decomposition overhead factor. Our results provide the first unified treatment of privacy and anonymity in multi-user multi-armed bandit learning, revealing the trade-offs between collaboration, privacy protection, and learning efficiency.

Official source

https://infoscience.epfl.ch/entities/publication/96cf6b9c-d1a2-4456-aa8a-0994d04e4dfd

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

2026

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/96cf6b9c-d1a2-4456-aa8a-0994d04e4dfd

About this result

Related concepts (18)

Multi-armed bandit

In probability theory and machine learning, the multi-armed bandit problem (sometimes called the K- or N-armed bandit problem) is a problem in which a fixed limited set of resources must be allocated between competing (alternative) choices in a way that maximizes their expected gain, when each choice's properties are only partially known at the time of allocation, and may become better understood as time passes or by allocating resources to the choice. This is a classic reinforcement learning problem that exemplifies the exploration–exploitation tradeoff dilemma.

Multi-user software

Multi-user software is computer software that allows access by multiple users of a computer. Time-sharing systems are multi-user systems. Most batch processing systems for mainframe computers may also be considered "multi-user", to avoid leaving the CPU idle while it waits for I/O operations to complete. However, the term "multitasking" is more common in this context. An example is a Unix or Unix-like system where multiple remote users have access (such as via a serial port or Secure Shell) to the Unix shell prompt at the same time.

Anonymity

Anonymity describes situations where the acting person's identity is unknown. Some writers have argued that namelessness, though technically correct, does not capture what is more centrally at stake in contexts of anonymity. The important idea here is that a person be non-identifiable, unreachable, or untrackable. Anonymity is seen as a technique, or a way of realizing, a certain other values, such as privacy, or liberty.