KL-regularization Itself is Differentially Private in Bandits and RLHF

Yizhou Zhang, Kishan Panaganti, Laixi Shi, Juba Ziani, Adam Wierman · 2025

Read KL-regularization Itself is Differentially Private in Bandits and RLHF by Yizhou Zhang, Kishan Panaganti, Laixi Shi, Juba Ziani, Adam Wierman (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-2505-18407.txt.

Introduction

Yizhou Zhang and co-authors find privacy hiding in a common trick in a 2025 theory paper. Differential privacy promises that one person's data cannot be spotted in an algorithm's output. Usually that promise is bought by adding noise on purpose.

A different route may cost nothing. Many learning methods already keep their answers close to a safe prior, a restraint called KL regularization. The authors prove that this restraint alone delivers the privacy promise in three settings: simple bandit choices, contextual bandits, and learning from human feedback in offline data. Free privacy could ease the tension between learning from data and guarding it.

Catalog record

CREATORYizhou Zhang, Kishan Panaganti, Laixi Shi, Juba Ziani, Adam Wierman
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE121 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-18407

Browse the full library · About the Tower of Babel

Full text

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

KL-regularization Itself is Differentially Private in Bandits and RLHF Yizhou Zhang, Kishan Panaganti, Laixi Shi, Juba Ziani, Adam Wierman Abstract Differential Privacy (DP) provides a rigorous framework for privacy, ensuring the outputs of data-driven algorithms remain statistically indistinguishable across datasets that differ in a single entry. While guaranteeing DP generally requires explicitly injecting noise either to the algorithm itself or to its outputs, the intrinsic randomness of existing algorithms presents an opportunity to achieve DP “for free”. In this work, we explore the role of regularization in achieving DP across three different decision-making problems: multi-armed bandits, linear contextual bandits, and reinforcement learning from human feedback (RLHF), in offline data settings. We show that adding KL-regularization to the learning objective (a common approach in optimization algorithms) makes the action sampled from the resulting stochastic policy itself differentially private. This offers a new route to privacy guarantees without additional noise injection, while also preserving the inherent advantage of regularization in enhancing performance. 1 Introduction Data-driven methods are becoming an increasingly central part of our society. Online and user data now fuels ad auctions, recommender systems, credit scoring, and many other high-impact applications ( Federal Trade Commission, 2024 ; Fu et al., 2025 ; Federal Reserve Board, 2024 ) . Often, such data is private or sensitive, and the volume of personal data driving today’s algorithms has increased by orders of magnitude. This makes strong privacy protections—capable of preventing the exposure of sensitive personal information—more crucial than ever ( Dinur and Nissim, 2003 ) . To address this challenge, Differential Privacy (DP) ( Dwork et al., 2006 ) offers a rigorous mathematical framework with precise, quantifiable privacy guarantees. DP has been largely used across various high-stake domains, including government statistics and in particular the 2020 decennial release of the U.S. Census ( Boyd et al., 2019 ) , online user data (e.g., Google, Apple, Meta, LinkedIn all use DP in several of their products) ( Desfontaines, 2021 ) , finance ( Maniar et al., 2021 ) , cyber-physical systems ( Hassan et al., 2019 ) , healthcare ( Dankar and El Emam, 2013 ) , energy data ( Desfontaines, 2021 ) , and client services ( Erlingsson et al., 2014 ) . Intuitively, DP provides an information-theoretic guarantee that ensures that the outputs of data-driven solutions remain (nearly) statistically indistinguishable whether or not any individual’s data is included. As an example, when a foundation model is fine-tuned via reinforcement learning with human feedback (RLHF) using human labels, it risks memorizing and revealing sensitive personal details. DP guarantees that the model trained with and without a given individual’s data are (almost) the same, which implies that the model does not memorize and output such sensitive data ( Zhang et al., 2025 ; Wu et al., 2023 ) . Differential Privacy (DP) inherently requires randomness in the output to prevent identifiable changes when the training data of a single agent varies. Achieving DP in various decision-making tasks usually relies on two main techniques. One is adding calibrated random noise (e.g., Laplace or Gaussian noise) to the training dataset, algorithm, or model parameters to obscure individual data contributions ( Dwork et al., 2006 ; Dwork et al., 2014 ) . The other one, when it comes to loss minimization and utility maximization, is to sample a parameter with some probability that depends on how well this parameter performs—otherwise known as the Exponential Mechanism . However, the introduction of either noise or sampling inevitably leads to accuracy and performance degradation, as the injected noise can obscure true data patterns, making it more difficult for algorithms to learn accurate models from the data ( Chaudhuri et al., 2011 ) . This creates significant challenges in balancing privacy and performance. The goal of our work is to highlight a natural setting in which existing randomness in commonly used algorithms is already sufficient to obtain Differential Privacy , and additional noise or sampling techniques may either not be needed, or may require adding less noise than previously believed. In particular, we focus on the role of KL-regularization in machine learning. KL-regularization is a widely used technique in optimization and decision-making. It is naturally integrated into many such algorithms to improve performance by reducing computational costs or increasing the stability of the learning process ( Schulman et al., 2017b ; Schulman et al., 2015 ; Haarnoja et al., 2018 ; Cuturi, 2013 ) . In RL settings, for example, absent regularization, optimal policies tend to be deterministic, yet including regularization induces policies that are inherently stochastic and randomized. In this work, we investigate whether, and to what extent, sampling from the optimal policy resulting from optimizing a KL-regularized objective naturally and intrinsically yields Differential Privacy (DP) on its own and without the need for further randomization . Thus, our goal is not to design a new mechanism for ensuring privacy; instead, we aim to understand the extent to which an existing algorithmic tool (KL-regularization) ensures privacy as an unintended byproduct. We characterize the level of DP that is intrinsically obtained when sampling from a KL-regularized policy across three types of problems: multi-armed bandits, linear contextual bandits, and reinforcement learning from human feedback (RLHF), within the offline data collection setting. These problems have broad applications in online learning and advertising ( Li et al., 2010 ) , healthcare ( Villar et al., 2015 ) , and large language model alignment ( Bai et al., 2022 ) . We summarize our contributions as follows: • We show a parallel between KL-regularization and the celebrated Exponential Mechanism . We provide \epsilon_{0} -pure DP guarantees for all three settings we consider under certain dataset coverage assumptions. Additionally, we provide (\epsilon,\delta) -approximate DP guarantees that are not provided by the Exponential Mechanism. Our results show that, within the practical range \delta\ll 1 ,we obtain an exponential \epsilon - \delta trade-off: one can choose any c\in(0,1) and obtain \epsilon=c\epsilon_{0} with \delta\sim O\left(\exp(-\sqrt{c})\right) in multi-armed bandits, and with \delta\sim O\left(\exp(-c)\right) in linear bandits and RLHF. Notably, our bound achieves DP for multi-armed bandits with partial dataset coverage, outperforming the Exponential Mechanism’s requirement of full coverage. • We propose a novel approach to obtaining approximate DP guarantees that combines KL-regularization with the idea of pessimism in offline reinforcement learning. We give a refined approximate DP analysis for the Exponential Mechanism through a separate consideration of high-probability and low-probability arms, leveraging pessimism to show a refined bound on the sensitivity of high-probability arms, as well as an exponentially small upper bound on the probability of pulling low-probability arms. • We conduct numerical simulations to illustrate the applicability of our bounds under both pure DP (under better coverage assumptions) and approximate DP (under weaker coverage assumptions). We also show that KL-regularization hence our privacy guarantee do not necessarily lead to empirical performance degradation. 2 Related works In this section we provide a detailed discussion on related works. Our work inscribes itself in a line of work that aims to show that existing randomized algorithms commonly used in machine learning inherently satisfy Differential Privacy ( Ou et al., 2024 ; Blocki et al., 2012 ) . This allows us, in certain cases, to use existing machine learning pipelines as is, without need

Read the complete text