DP‑NCB: Privacy Preserving Fair Bandits

Dhruv Sarkar, Nishant Pandey, Sayak Ray Chowdhury · 2025

Read DP‑NCB: Privacy Preserving Fair Bandits by Dhruv Sarkar, Nishant Pandey, Sayak Ray Chowdhury (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-03836.txt.

Introduction

Dhruv Sarkar, Nishant Pandey, and Sayak Ray Chowdhury design in 2025 a decision algorithm that guards privacy and fairness at the same time. Bandit methods learn by trial, picking among options round by round, and now serve in trials and personal services. Past work handled privacy or fairness alone, leaving open whether both fit together.

Their method keeps user data under a formal privacy shield while scoring rounds by a fairness minded regret that punishes lopsided rewards. The bounds match known limits up to small factors. It works under both central and local privacy rules and needs no fixed horizon.

Catalog record

CREATORDhruv Sarkar, Nishant Pandey, Sayak Ray Chowdhury
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE144 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-03836

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

DP‑NCB: Privacy Preserving Fair Bandits Dhruv Sarkar, Nishant Pandey, Sayak Ray Chowdhury Abstract Multi-armed bandit algorithms are fundamental tools for sequential decision-making under uncertainty, with widespread applications across domains such as clinical trials and personalized decision-making. As bandit algorithms are increasingly deployed in these socially sensitive settings, it becomes critical to protect user data privacy and ensure fair treatment across decision rounds. While prior work has independently addressed privacy and fairness in bandit settings, the question of whether both objectives can be achieved simultaneously has remained largely open. Existing privacy-preserving bandit algorithms typically optimize average regret, a utilitarian measure, whereas fairness-aware approaches focus on minimizing Nash regret, which penalizes inequitable reward distributions, but often disregard privacy concerns. To bridge this gap, we introduce Differentially Private Nash Confidence Bound (DP-NCB)—a novel and unified algorithmic framework that simultaneously ensures ϵ \epsilon -differential privacy and achieves order-optimal Nash regret, matching known lower bounds up to logarithmic factors. The framework is sufficiently general to operate under both global and local differential privacy models, and is anytime, requiring no prior knowledge of the time horizon. We support our theoretical guarantees with simulations on synthetic bandit instances, showing that DP-NCB incurs substantially lower Nash regret than state-of-the-art baselines. Our results offer a principled foundation for designing bandit algorithms that are both privacy-preserving and fair, making them suitable for high-stakes, socially impactful applications. 1 Introduction The multi-armed bandit framework ( Bubeck et al. 2012 ; Lattimore and Szepesv´ari 2020 ) is a foundational model for sequential decision-making under uncertainty. It has been widely applied across domains such as online advertising and product recommendations ( Li et al. 2010 ; Schwartz et al. 2017 ) , education and tutoring systems ( Clement et al. 2015 ) , and healthcare and clinical trials ( Tewari and Murphy 2017 ; Villar et al. 2015 ) . Given its growing use in socially sensitive areas, there is increasing interest in integrating principles of privacy and fairness into bandit algorithms. Privacy concerns arise from the reliance on user feedback, which can inadvertently reveal sensitive information ( Pan et al. 2019 ) . Fairness is motivated by social welfare considerations — ensuring that all users perceive the system as treating them equitably ( Moulin 2004 ) . To highlight the importance of privacy and fairness in bandit problems, consider a clinical trial scenario originally proposed by Thompson 1933 : given k drugs and T patients, the decision maker selects one drug to administer to the t -th patient in each round t\leq T . The treatment outcome is inherently private and sensitive i.e. patients may not wish to disclose their medical conditions publicly post-trial. However, since future drug assignments are based on prior outcomes, an individual patient’s response can influence subsequent decisions. This means that even if outcomes are not explicitly revealed, they may still be inferred from changes in the drug selection policy. Therefore, the learning algorithm must ensure that individual patient data (e.g., treatment outcomes) remains private while taking future decisions (e.g., drug choices). At the same time, it is crucial to ensure that no patient is ex-ante disadvantaged by the learner, i.e., fairness must be maintained across rounds. A fair learning algorithm should guarantee that patients participating in different rounds of the trial benefit from progressively better drug choices, while still permitting sufficient exploration to accurately identify the most effective drug. Achieving privacy in isolation is straightforward, for example, the learner could ignore treatment outcomes entirely and always administer a fixed, publicly announced drug. However, such an approach would likely lead to poor treatment efficacy. This highlights the need to carefully balance privacy with utility. Differential Privacy (DP) offers a principled way to do so by providing strong guarantees even against adversaries with access to arbitrary auxiliary information. It achieves this by adding calibrated random noise to obscure any individual’s influence on the algorithm’s output, ensuring that no single user’s data significantly alters the outcome ( Dwork and Roth 2014 ) . Importantly, DP includes a tunable parameter \epsilon>0 that allows explicit control over the privacy-utility trade-off: smaller \epsilon yields stronger privacy but reduced utility, and vice versa. In recent years, DP has been effectively incorporated into the design of privacy-preserving bandit algorithms ( Mishra and Thakurta 2015 ; Tossou and Dimitrakakis 2016 ; Azize and Basu 2022 ) , typically using average reward (e.g., treatment outcome) or, equivalently, regret, as the measure of utility. Minimizing average regret , which is defined as the difference between the (a priori unknown) highest expected reward and the arithmetic mean of the expected rewards obtained by the algorithm—is equivalent to maximizing social welfare in a utilitarian sense ( Moulin 2004 ) . While this objective promotes overall efficiency, it may inadvertently favor short-term reward maximization, potentially resulting in inequities across decision rounds. For example, achieving a high average treatment efficacy does not preclude some patients from receiving highly ineffective treatments. To address this limitation, Nash social welfare (NSW) considers the geometric mean of expected rewards, promoting a more equitable distribution across rounds in an ex-ante sense ( Moulin 2004 ) . The associated metric, Nash regret —the gap between the highest expected reward and the NSW offers a fairness-aware alternative to average regret. It penalizes disparities in individual rewards and has gained recent attention as a foundation for designing fair bandit algorithms ( Barman et al. 2023 ; Sawarni et al. 2023 ; Krishna et al. 2025 ) . While prior work has extensively explored privacy and fairness in multi-armed bandits, these concerns have been addressed in isolation. The fundamental question of whether these concerns can be simultaneously addressed in bandit settings remains largely unresolved. In this work, we address this gap by introducing a novel differentially private Nash regret minimization framework that combines controlled noise addition of DP mechanisms with fairness-aware reward aggregation. This ensures a learning process that is both private and fair, making it well-suited for high stakes, sensitive applications like healthcare and personalized decision-making. Our Contributions • We propose a general framework — Differentially Private Nash Confidence Bound (DP-NCB) — that guarantees \epsilon -differential privacy for any \epsilon , while achieving order-optimal Nash regret that vanishes as the number of rounds T\to\infty . • In the global model of differential privacy, where the learner is trusted and has access to raw user data, Algorithm 1 (GDP-NCB) achieves a Nash regret 1 1 1 \widetilde{O} hides constant and polylogarithmic factors in T and k . of \widetilde{O}\Big(\sqrt{\frac{k}{T}}+\frac{k}{\epsilon\,T}\Big) . In the stronger local privacy model, where the learner is not trusted and has access to only randomized user data, Algorithm 2 (LDP-NCB) achieves the Nash regret \widetilde{O}\Big(\sqrt{\frac{k}{T}}+\frac{1}{\epsilon}\sqrt{\frac{k}{T}}\Big) . • Since Nash regret is a stricter benchmark than average regret (see Remark 2.1 ), existing lower bounds for average regret also apply to Nash regret. In particular, the known minimax lower bounds— \Omega\Big(\max\big\{\sqrt{\frac{k}{T}},\frac{k}{\epsilon\,T}\big\}\Big) in the global privacy model and \Omega\Big(\frac{1}{\epsilon}\sqrt{\frac{k}{T}}\Big) in the local model—serve as fundamental performance limits. This implies that our upper bound on Nash regret is nearly optimal (up to logarithmic factors), as it matches the best-known lower bounds even for the easier benchmark of average regret. • We further extend our algorithms to the anytime setting, where prior knowledge

Read the complete text