PaperlayerView exact revision on arXiv

Source-linked AI summary

Differentially Private Contextual Linear Bandits

Roshan Shariff, Or Sheffet

arXiv:1810.00068v1cs.LGstat.ML

TL;DR

Standard differential privacy under continual observation leads contextual-bandit learners to essentially ignore context and incur linear regret. The paper develops a joint differentially private LinUCB framework using a tree-based mechanism and Gaussian or Wishart noise. It gives regret bounds for the private contextual-bandit algorithms and an additional-regret lower bound for private MABs.

  • Problem

    Under continual observation, standard differential privacy requires contextual-bandit learners to essentially ignore context and incur linear regret, despite contexts containing sensitive information that predicts purchases.

    Source: §1 · p. 1

  • Method

    The paper combines LinUCB with a tree-based privacy mechanism and uses Gaussian or Wishart perturbations to obtain joint differential privacy.

    Source: §1.2 · p. 3, §4 · p. 6, §4.1 · p. 6

  • Results

    ˜O(√n · d3/4/√ε) is the main term in both private contextual-bandit regret bounds, while private MAB algorithms incur additional Ω(k log(n)/ε) regret.

    Source: §1.2 · p. 3

  • Takeaways & Limitations

    The privacy guarantee is joint rather than full for the current round: an action may depend on that round's context because it is revealed to that user.

    Source: §4 · p. 6

    A private version of the action-set-aware algorithm proposed in recent work remains an open question.

    Source: §1.2 · p. 3

Abstract

from arXiv · show

We study the contextual linear bandit problem, a version of the standard stochastic multi-armed bandit (MAB) problem where a learner sequentially selects actions to maximize a reward which depends also on a user provided per-round context. Though the context is chosen arbitrarily or adversarially, the reward is assumed to be a stochastic function of a feature vector that encodes the context and selected action. Our goal is to devise private learners for the contextual linear bandit problem. We first show that using the standard definition of differential privacy results in linear regret. So instead, we adopt the notion of joint differential privacy, where we assume that the action chosen on day $t$ is only revealed to user $t$ and thus needn't be kept private that day, only on following days. We give a general scheme converting the classic linear-UCB algorithm into a joint differentially private algorithm using the tree-based algorithm. We then apply either Gaussian noise or Wishart noise to achieve joint-differentially private algorithms and bound the resulting algorithms' regrets. In addition, we give the first lower bound on the additional regret any private algorithms for the MAB problem must incur.

1 Introduction

The introduction frames privacy-preserving contextual bandits as a way to learn across users while protecting sensitive contexts and rewards. It presents joint differential privacy, a LinUCB-based framework, regret bounds, and a lower bound for private MABs.

1 Introduction

  • Contextual linear bandits map each context-action pair to a feature vector and assume a shared unknown linear reward function across users.This modeling choice avoids ignoring user-preference variation or learning each user's preferences separately.Source: §1 · p. 1
  • Under continual observation, standard differential privacy forces contextual-bandit learners to essentially ignore context and incur linear regret, motivating joint differential privacy.Joint differential privacy protects a user's information in later users' interactions while allowing that user's own action to reflect her preferences.Source: §1 · pp. 1–2

1.2 Our Contributions and Paper Organization

  • The framework combines tree-based privacy with LinUCB and uses Wishart or Gaussian perturbations, with both private regret bounds having main term ˜O(√n · d3/4/√ε).The introduction also gives a polylog(n)/∆ bound when optimal and suboptimal actions are separated by a reward gap ∆.Source: §1.2 · p. 3
  • Any ε-differentially private MAB algorithm must incur additional regret of Ω(k log(n)/ε), proved using a coupling argument that requires substantial exploration of suboptimal arms.The authors distinguish this stochastic-input proof from standard packing arguments used for adversarial inputs.Source: §1.2 · p. 3

1.3 Related Work

  • The related-work discussion describes a tree-based continual-observation mechanism and notes prior contextual-bandit work without PSD maintenance, analysis, or lower bounds.It also cites partial utility analysis in a reward-privacy model that does not guarantee context privacy.Source: §1.3 · p. 3

2 Preliminaries and Notation

This section establishes matrix and probability notation used in the analysis, including Gram matrices, PSD matrices, Gaussian and chi-squared distributions, and problem parameters.

2 Preliminaries and Notation

  • For a matrix M, its Gram matrix is M⊤M; a symmetric matrix is PSD when x⊤Mx ≥ 0 for every vector x.PSD matrices define the matrix-weighted norm used in the paper.Source: §2 · p. 4
  • The notation defines the Gaussian distribution, the χ2(d) distribution for squared norms of standard Gaussian vectors, and total variation distance between distributions.The supplied definition states that χ2(d) is tightly concentrated around d.Source: §2 · p. 4
  • The notation records the horizon, dimension, decision sets, actions, rewards, unknown parameter, Gram matrix, regularizer, and perturbation variables.These symbols include H_t for the regularizer and h_t for the perturbation of the action-reward product.Source: §2 · p. 4

3 Linear UCB with Changing Regularizers

The section extends LinUCB to allow round-varying regularizers and perturbations, using confidence sets centered on regularized regression estimates. It states high-probability pseudo-regret guarantees under specified assumptions, including a gap-dependent case.

3 Linear UCB with Changing Regularizers

  • LinUCB forms confidence sets around regularized regression estimates and chooses the action with the highest optimistic reward bound.The confidence ellipsoid contracts along directions informed by many chosen actions, with its scale set by β_t.Source: §3 · p. 4
  • The algorithm permits round-varying PSD regularizers H_t and perturbations h_t in the regression estimate and its confidence-bound analysis.Its assumptions include bounded actions and parameter, conditionally subgaussian reward noise, and PSD regularizers; the stronger action-and-reward bound is used for joint privacy later.Source: §3 · pp. 4–5

3.1 Regret Bounds

  • The analysis adapts the constant-regularizer LinUCB proof of Abbasi-Yadkori et al., with changes that introduce dependence on ρ_max and ρ_min.The authors note that tracing these changes is involved.Source: §3.1 · p. 5
  • Under Assumptions 1–5 and the prescribed confidence bounds, Theorem 5 states a high-probability pseudo-regret bound for Algorithm 1.The supplied theorem passage does not include the bound's expression.Source: §3.1 · p. 5
  • When optimal and suboptimal actions in every decision set have reward gap at least ∆, Theorem 6 states a high-probability gap-dependent pseudo-regret bound.The guarantee is conditional on Assumptions 1–5 and the confidence bounds from Proposition 4.Source: §3.1 · p. 5

4 Linear UCB with Joint Differential Privacy

The section converts Linear UCB into a jointly differentially private learner by privately maintaining its regularizers with a tree-based mechanism, then analyzes Wishart- and Gaussian-noise variants.

4 Linear UCB with Joint Differential Privacy

  • Recording the history through differentially private Gram-matrix and reward-vector estimates makes Linear UCB jointly differentially private by post-processing.The algorithm uses these estimates through its confidence set; its current context still affects the chosen action.Source: §4 · p. 6

4.1 Differential Privacy via Wishart Noise

  • The Wishart variant adds tree-based Wishart noise to the combined matrix estimate and shifts the resulting regularizer by −cI.The matrix combines the Gram matrix and reward vector; the noise is constructed from Gaussian samples and its shift is specified in Eq. (4).Source: §4.1 · p. 6, §4 · p. 6
  • Wishart- and Gaussian-noise tree mechanisms yield pseudo-regret bounds for Algorithm 1, including gap-dependent bounds.The supplied passages state these bounds but do not include their complete expressions.Source: §4.1 · p. 7, §4.2 · p. 8

4.2 Differential Privacy via Additive Gaussian Noise

  • The Gaussian variant symmetrizes noisy matrices and adds 2ΥI to keep the regularizer positive while deriving regret bounds.The passages describe symmetric Gaussian noise and a shift chosen to maintain strictly positive eigenvalues.Source: §4.2 · pp. 7–8

5 Lower Bounds

The section gives lower bounds for contextual bandits under standard differential privacy and for private classic MAB algorithms. It shows linear regret in the former setting and an additional privacy-related regret cost in the latter.

5 Lower Bounds

  • For contextual bandits, any (ε, δ)-differentially private algorithm incurs pseudo-regret Ω(n) when ε < ln(2) and δ < 0.25.The lower bound concerns the standard differential-privacy notion under continual observation.Source: §5 · p. 8
  • Under the stated regret assumption, a private algorithm must pull each suboptimal arm at least log(n)/(100ε∆a) times with probability at least 1/2.Here ∆a is the reward gap between that arm and the leading arm.Source: §5 · p. 8
  • Any ε-differentially private MAB algorithm has expected pseudo-regret at least Ω(k log(n)/ε), in addition to the standard non-private regret bound.The argument assumes an expected-regret upper bound of n^3/4 for the intermediate claim, while the authors note that any n^(1−c) bound for c > 0 suffices.Source: §5 · p. 8

Supplementary Material

The supplementary material reviews the Gaussian mechanism and tree-based continual-sum mechanism, then lists matrix and distribution facts used in the analysis.

A.1 Differential Privacy

  • Differential privacy is defined by bounding output-probability changes on neighboring datasets, with Gaussian noise calibrated to a query’s L2 sensitivity.The supplied text gives the privacy inequality and the sensitivity-based Gaussian variance rule.Source: §A.1 · p. 12, §A.2 · p. 12

A.2 The Tree-Based Mechanism

  • The tree-based mechanism stores subtree sums so any partial sum uses at most m = ⌈log(n) + 1⌉ nodes, each affected at no more than m nodes by a neighboring input change.The text uses composition of node-level privacy guarantees to obtain privacy for the full mechanism.Source: §A.2 · p. 12

A.3 Useful Facts.

  • The appendix collects facts about PSD matrices and concentration bounds for chi-square, Gaussian-matrix, and Wishart distributions used in the proofs.It also states matrix-order relations and eigenvalue or singular-value bounds.Source: §A.3 · p. 12

B Discussion and Proofs from Section 3

This section establishes LinUCB regret guarantees for changing regularizers and explains how their bounds depend on assumptions and reward gaps. It also details how to handle reward bounds larger than one.

B Discussion and Proofs from Section 3

B.1 Regret Bounds Open Problem

The regret bounds match standard MAB bounds in their dependence on n and Δ, but have worse dependence on dimension d. Whether the quadratic gap-dependent dependence on d is necessary remains open.

B.1 Regret Bounds Open Problem

  • The stated n and Δ dependencies are O(√n) in the minimax case and O(log(n)/Δ) in the gap-dependent case.Source: §B.1 · p. 16
  • The bounds match standard MAB dependence on n and Δ, but scale as O(d) for minimax regret and O(d^2) for gap-dependent regret.Source: §B.1 · p. 16
  • Whether O(d^2) dependence is necessary for O(log n) gap-dependent regret remains open because the authors could not prove an Ω(d^2) lower bound.Source: §B.1 · p. 16

C Privacy Proofs

The privacy proofs establish a linear pseudo-regret lower bound for standard differential privacy and give supporting Wishart-noise privacy arguments. The linear lower bound motivates the paper's use of joint differential privacy.

C Privacy Proofs

  • Adding Wishart noise to AᵀA yields (ε, δ)-differential privacy when a single row of A changes, under the theorem's stated conditions.Source: C Privacy Proofs · p. 17
  • For ε < ln(2) and δ < 0.25, every standard differentially private contextual bandit algorithm incurs pseudo-regret Ω(n).Source: C Privacy Proofs · p. 18
  • For a random adversary choosing between two contexts, the proof bounds expected per-round pseudo-regret below by a positive constant.The construction uses two arms whose reward mappings are flipped across the two contexts.Source: C Privacy Proofs · p. 18

D Experiments

The experiments use synthetic contextual decision sets to test LinUCB's dimension dependence on gap instances. The log–log results show a best-fit slope of roughly two for regret against dimension.

D Experiments

  • Each synthetic decision set contains one optimal action and K − 1 suboptimal unit-length actions, with gap Δ = 0.1; a new set is sampled each round.The optimal action has mean reward 0.75, while suboptimal actions have means in [−0.75, 0.65].Source: D Experiments · p. 18
  • The experiments measure expected regret using confidence parameter α = 1/n.Rewards are either −1 or +1 with expectation matching the selected action's linear mean.Source: D Experiments · p. 18

D.1 The Dependency of the Pseudo-Regret on the Dimension for Gap Instances

  • A log–log plot of total accumulated regret against dimension has a best-fit slope of roughly 2, indicating super-linear dependence on d.The authors conjecture that the dependence is quadratic in general.Source: Figure 3 · p. 19, §D.1 · p. 19
  • The dimension experiment evaluates non-private LinUCB for n = 10^5 rounds, with ρ = I and K = d^2, across dimensions 4 to 64.It targets whether gap-dependent regret has Ω(d^2) dependence; the two sub-experiments use Gaussian and ±1 reward noise.Source: §D.1 · p. 19

D.2 Empirical Performance of the Privacy-Preserving Algorithms over Time

The experiment compares privacy-preserving algorithm variants over time with and without a forced sub-optimality gap. Gaussian noise outperforms Wishart noise, while the unshifted Wishart variant’s relative performance depends on the gap.

D.2 Empirical Performance of the Privacy-Preserving Algorithms over Time

  • The experiment compares LinUCB with Gaussian and shifted Wishart variants over n = 5 × 10^7 rounds (d = 5, K = 25), using ε = 1.0 and δ = 0.1 for privacy algorithms, under Δ = 0 and Δ = 0.1.The curves are truncated after 2 × 10^7 rounds because they are essentially flat thereafter.Source: §D.2 · pp. 19–20
  • In the reported setting, Gaussian noise outperforms Wishart noise: their asymptotic performance is fairly close, but Gaussian-version constants are far better.Source: §D.2 · p. 20
  • WishartUnshifted has the worst regret at Δ = 0 but is statistically indistinguishable from shifted Wishart at Δ = 0.1.The authors investigate the relationship between the gap and shifted regularizers in the next experiment.Source: §D.2 · p. 20

D.3 Empirical Performance of Shifted Regularizers for Different Suboptimality Gaps

This experiment varies the shifted regularizer under different sub-optimality gaps, although the bound-optimizing shift does not depend on the gap. Tuning appears to affect regret mainly when gaps are small or zero; large regularizers do not seem to appreciably increase regret in large-gap settings.

D.3 Empirical Performance of Shifted Regularizers for Different Suboptimality Gaps

  • The experiments vary the shift parameter even though the bound-optimizing shift is chosen independently of the sub-optimality gap.The prior experiment found the shifted and unshifted Wishart variants’ relative performance changed with the gap.Source: §D.3 · p. 20
  • The logarithmic x-axis uses ρmin, a proxy for shift; dotted lines mark the algorithms’ Section 4.1 and 4.2 settings, and Gaussian has no unshifted variant.The figure compares Wishart and Gaussian performance across gap settings.Source: §D.3 · pp. 20–21, Figure 5 · p. 21
  • Tuning the shift appears to affect performance significantly only at small or zero gaps; too much regularization does not seem to appreciably increase regret in large-gap settings.The authors conjecture that large regularizers inhibit exploration when exploration is crucial.Source: §D.3 · p. 21, Figure 5 · p. 21
Loading 1810.00068v1…