In sequential decision-making, an agent must balance "exploitation" (choosing the best-known action) with "exploration" (trying new actions to gather information). Standard algorithms like Upper Confidence Bound (UCB) manage this by maintaining an uncertainty bonus: they prefer actions that either have high average rewards or have not been tried enough.
However, when the rewards involve sensitive user data—such as medical outcomes or personal preferences—we must protect individual privacy using Differential Privacy (DP). DP typically requires adding statistical noise to the rewards. This noise creates a fundamental problem: if an algorithm sees a low reward, it cannot tell if the action is truly bad or if the "privacy noise" just happened to be negative. Without adjustment, the agent might prematurely abandon the optimal action, leading to high regret.
Accounting for the Privacy Noise Floor
The core insight across this research direction is that privacy noise should be treated as a known source of epistemic uncertainty. In a non-private UCB algorithm, the confidence interval around an arm's mean reward shrinks as we collect more samples. In a private setting, Nikita Mishra and Abhradeep Thakurta demonstrated that algorithms must implement a more aggressive exploration phase to "see through" this noise.
To do this, researchers modify the exploration bonus to include a privacy-adjusted term. Aristide C. Y. Tossou and Christos Dimitrakakis introduced DP-UCB-INT, which adds a term to the uncertainty bonus specifically scaled to the privacy budget ($\epsilon$). By widening the confidence interval to account for the variance of the injected noise, the algorithm remains "optimistic" even when the privatized feedback is temporarily misleading.
Local vs Central Privacy Constraints
The "privacy tax" on learning performance depends heavily on where the noise is added:
- Central DP: A trusted curator collects raw data and adds noise before publishing results. Tossou and Dimitrakakis showed that in this setting, the cost of privacy can be reduced to a near-constant additive term in the regret.
- Local DP (LDP): Users add noise to their own data before the agent ever sees it. This is much more secure but significantly noisier. Jia Liu and colleagues established that LDP imposes a much steeper multiplicative cost on regret.
In the LDP setting, the agent's confidence intervals must be even wider. Yuheng Ma and Yi Yu showed that for complex, nonparametric rewards, these adjusted bounds must incorporate both the standard sampling variance and the specific distribution of the local Laplacian noise to maintain near-optimal performance.
Widening the Posterior in Thompson Sampling
While UCB uses explicit intervals, Thompson Sampling explores by sampling from a posterior distribution of rewards. To make this private, Tianchi Zhao and Ming Li proposed intentionally shifting and widening these posterior distributions.
By inflating the variance of the posterior to match the scale of the privacy noise, the agent is prevented from converging too quickly on a suboptimal arm. Bingshan Hu and Nidhi Hegde further refined this with "lazy and forgetful" updates, ensuring that the agent doesn't overreact to the high-variance noisy signals received in early rounds.
Scaling to Reinforcement Learning
The challenge intensifies in Reinforcement Learning (RL), where the agent must learn transition dynamics in addition to rewards. Evrard Garcelon and Vianney Perchet developed LDP-OBI, which extends the privacy-aware confidence interval logic to state-action transitions.
In linear environments, Dung Daniel Ngo and Zhiwei Steven Wu showed that agents can maintain exploration by adding a privacy bonus to value estimates derived from a "noisy Gram matrix." This ensures that the injected noise does not obscure the "epistemic uncertainty" needed to discover new states. Interestingly, Dan Qiao and Yu-Xiang Wang found that the architectural rigors required for private RL—such as variance-aware pessimism—can sometimes make the algorithms more robust than their non-private counterparts.
Privacy as a Statistical Safeguard
Beyond just protecting data, differential privacy can actually improve the validity of the data gathered. Adaptive algorithms (like bandits) usually bias the data they collect because they stop trying arms that look bad. Seth Neel and Aaron Roth demonstrated that the noise required for DP naturally bounds this adaptive bias. By integrating DP into the exploration process, the gathered samples remain statistically reliable for downstream analysis, effectively using privacy as a tool to prevent the agent from "overfitting" to its own exploration path.