Optimal Gap-Dependent Regret for Private Stochastic Decision-Theoretic Online Learning

Tommaso Cesari; Roberto Colomboni

cs.LGMay 27, 2026

Optimal Gap-Dependent Regret for Private Stochastic Decision-Theoretic Online Learning

Authors: Tommaso Cesari, Roberto Colomboni

Abstract

We study stochastic decision-theoretic online learning with full information and event-level pure differential privacy. A COLT open problem of Hu and Mehta asks to determine the optimal gap-dependent regret rate for stochastic decision-theoretic online learning under pure event-level differential privacy. For $K$ actions, losses in $[0,1]$ , and a unique best action separated from the second-best action by gap $Δ_{\min}$ , the known lower bound is of order $\frac{\log K}{\min\{Δ_{\min},\varepsilon\}},$ or equivalently, up to universal constants, of order

\frac{\log K}{Δ_{\min}}+\frac{\log K}{\varepsilon}.

We give a horizon-free pure-DP algorithm and prove the explicit regret bound

\operatorname{Reg}_T \le 1000 \cdot \left(\frac{\log K}{Δ_{\min}}+\frac{\log K}{\varepsilon}\right)

for every horizon $T$ . The numerical constant is not optimized. The algorithm partitions time into blocks of exponentially increasing size, plays a single action throughout each block, and chooses the next action by an exponential mechanism applied to a data-independent random prefix of the previous block. The random prefix converts block regret into a sum, over all prefix lengths, of softmax selection errors. A single entropy-potential argument controls all privacy-dominated large-gap actions at cost $\log K/\varepsilon$ .

Explore similar work

May 6, 2026cs.CR

Differential Privacy in the Extensive-Form Bandit Problem

We consider the extensive-form bandit problem, where on each trial the learner (a user coordinated by a server) plays an extensive-form game against an oblivious adversary, observing the information sets it finds itself in as well as the resulting payoff/loss. We give an algorithm for this problem that satisfies

ε

-local differential privacy and attains a regret of

\tilde{O}(\sqrt{A\ln(S)T}/ε)

, where

A

is the total number of actions that the learner can possibly take,

S

is the number of the learner's possible reduced strategies, and

T

is the number of trials. On each trial, the time complexity of our algorithm is, up to a factor logarithmic in the maximum number of actions at an infoset, equal to the time required for the server to transmit the reduced strategy to the user. We note that local differential privacy is the strongest version of differential privacy and, to the best of our knowledge, this is the first work to study differential privacy of any form in the extensive-form bandit problem.

Stephen Pasteris, Rahul Savani, Theodore Turocy

Differential Privacy Imperfect-Information Games Optimal Sample Complexity Privacy Risks and Protection

Ask PDF

May 7, 2026cs.LG

Towards Differentially Private Reinforcement Learning with General Function Approximation

We present the first theoretical guarantees for differentially private online reinforcement learning (RL) with general function approximation, extending beyond prior work restricted to tabular and linear settings. Our approach combines a batched policy update scheme with the exponential mechanism, together with a novel regret analysis. We show that, even under general function approximation, the regret in the model-free setting under differential privacy matches the state of the art for the linear case, scaling as

\widetilde{O}(K^{3/5})

, where

K

denotes the number of episodes. As an important by-product, we also establish the first regret bound for online RL with batch update that depends on the standard complexity measure of coverability, complementing existing results based on a newly introduced Eluder-Condition class. In addition, we uncover fundamental gaps in recent results for private RL with linear function approximation, thereby clarifying its landscape.

Yi He, Xingyu Zhou

Offline Safe Reinforcement Learning Differential Privacy Plan Regret

Ask PDF

Aug 28, 2026cs.LG

Performative Privacy: When Differential Privacy Maximizes Utility

Privacy-preserving learning is often motivated by the idea that protecting users' data can preserve trust and thus participation, improving utility in the long term. However, this claim has not been formalized so far. In parallel, performative learning provides a framework for studying learning systems whose deployment affects the data they later observe. In this work, we bring these two perspectives together and introduce performative privacy, where data leakage reduces future participation. We study a simple model where agents repeatedly contribute data for mean estimation but may leave the system when their data is leaked. Privacy is implemented through differentially private mechanisms, creating a trade-off between estimation noise and future participation. We show, through a theoretical study of the dynamics and numerical experiments, that a finite privacy budget can outperform non-private estimation in the long term when the feedback loop between leakage and participation is sufficiently strong. This provides first evidence that differential privacy can be optimal not only as a protection mechanism, but also from the perspective of long-term utility.

Uddalak Mukherjee, Edwige Cyffers, Yann Chevaleyre

Differential Privacy Privacy-Preserving Framework Privacy Risks and Protection Long-Term

Ask PDF