Multiplicative Regret Penalties in Private Sequential Decision Making

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2123 papers225 conceptsfrozen 2026-10-04

In online learning and reinforcement learning (RL), an agent learns by interacting with an environment, receiving rewards, and updating its strategy. However, these rewards often contain sensitive information—medical outcomes, financial transactions, or personal preferences. The challenge of Differentially Private (DP) Sequential Decision Making is to maximize cumulative rewards (minimize "regret") while ensuring that the presence or absence of any single user's data does not significantly alter the algorithm's behavior.

The core tension in this field is the "Price of Privacy": the unavoidable performance gap between private and non-private learners.

The Privacy Tax: Multiplicative vs. Additive Regret

In standard online learning, regret typically scales with the square root of time ($\sqrt{T}$). When we introduce privacy, we must add noise to the observations. Early conjectures suggested this might only add a constant overhead. However, Debabrota Basu, Christos Dimitrakakis, and Aristide C. Y. Tossou proved in Differential Privacy for Multi-armed Bandits: What Is It and What Is Its Cost? that privacy often imposes a multiplicative penalty.

This means privacy doesn't just add a fixed error; it fundamentally slows down the learning rate. The agent is forced to explore suboptimal choices more frequently to "mask" the influence of any single data point. Roshan Shariff and Or Sheffet showed in Differentially Private Contextual Linear Bandits that under standard DP, this penalty can even lead to "linear regret"—where the algorithm fails to learn at all—unless the privacy definitions are carefully relaxed.

The Trust Spectrum: Local, Joint, and Shuffle Privacy

The "price" of privacy depends heavily on where the noise is added.

  1. Local Differential Privacy (LDP): Users add noise to their data before sending it to the learner. This is the most secure but most difficult regime. Kai Zheng and colleagues demonstrated in Locally Differentially Private (Contextual) Bandits Learning that LDP regret scales much worse than central DP, often requiring $1/\epsilon^2$ more data to achieve the same utility.
  2. Joint Differential Privacy (JDP): This is tailored for recommendation systems. The learner ensures that the recommendations given to User A do not leak the private data of User B. Roshan Shariff used this to achieve sub-linear regret in contextual bandits, bypassing the "impossibility" of standard DP in that setting.
  3. Shuffle Privacy: An intermediate model where user data is anonymized by a "shuffler" before reaching the server. Matteo Pirotta and Evrard Garcelon showed in Privacy Amplification via Shuffling for Linear Contextual Bandits that shuffling provides a "sweet spot," achieving better utility than LDP while requiring less trust than a centralized server.

Algorithmic Strategy: The Power of Laziness

To maintain privacy, an algorithm must limit its sensitivity—how much its output changes based on one input. In sequential settings, if an agent updates its policy every single round, every round's data leaks into the public record.

The solution is often Laziness. By only updating the policy in infrequent batches, the learner reduces the number of times it "reveals" information.

Handling the Real World: Heavy Tails and Adversaries

Real-world data is rarely bounded and well-behaved. When rewards are heavy-tailed (prone to extreme outliers), the sensitivity of the mean increases, making privacy much harder to guarantee.

Youming Tao and Di Wang showed in Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits that for heavy-tailed data, the price of privacy becomes even steeper, scaling with the number of available moments in the distribution. To combat this, researchers like Vasileios Charisopoulos and Hossein Esfandiari have developed robust private algorithms that use reward truncation and spectral filtering to protect against both privacy leaks and adversarial data corruption simultaneously.

Closing the Theoretical Gap

For years, it was believed that private algorithms must "forget" old data to remain private. However, recent work by Achraf Azize, Yulian Wu, and Junya Honda in Optimal Regret of Bandits under Differential Privacy has debunked this. By using a new "DP-Chernoff" concentration inequality, they proved that we can achieve optimal regret without deliberate forgetfulness, finally aligning the theoretical lower bounds with achievable algorithmic performance.

Papers in this version

Showing 60 of 123 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 104 papers
  2. Version 1 · 2026-10-04 · 123 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_regret_privacy_gap_2d4c91e6,
  title = {regret-privacy gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/regret-privacy-gap/rdr_2d4c91e650f34178ab72f72fc076267d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_multiplicative_regret_penalties_in_priva_2d4c91e6_v1,
  title = {Multiplicative Regret Penalties in Private Sequential Decision Making},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multiplicative-regret-penalties-in-private-sequential-decision-making/rdr_2d4c91e650f34178ab72f72fc076267d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}