betaFeedback

WorksComputer Science

Learning Recommendations under Imperfect Human Compliance with Record-Level Differential Privacy

Abstract

This paper investigates human-in-the-loop recommendation systems, where effectiveness relies on human compliance and privacy concerns restrict the use of historical response data. The pro posed framework models the implemented action as a random response to the recommendation and formulates the recommendation mechanism as a decision-dependent optimisation problem under an unknown compliance distribution. A batched Gaussian process upper confidence bound algorithm is then adapted to learn from locally perturbed historical actions, providing privacy for individual raw records. The analysis establishes record-level differential privacy and derives high-probability simple regret bounds when the compliance distribution is unknown. These bounds characterise how privacy noise, batch size, and behavioural information affect the guaranteed quality of the learned recommendation. In particular, a known upper bound on the non-compliance rate enables the rec ommendation space to be screened before any private data are queried. Simulations of a fixed-state car-following problem with synthetic historical driver responses demonstrate the effectiveness of the proposed algorithm and verify the theoretical findings.

Introduction

Decision-making in cyber–physical–human systems (CPHS) has attracted growing interest in control and optimisation ([2]), spanning applications from assisted driving ([14]) to demand response ([5]). In many human-centric CPHS architectures, a recommendation agent provides operational advice, while humans determine the actions ultimately applied to the physical system. The recommendation may specify a target acceleration in an advanced driver assistance system (ADAS), a thermostat setpoint in residential demand response, or an irrigation volume in agriculture. Since the human does not always follow advice exactly (see Figure 1 for an ADAS car-following example), the effectiveness of the recommendation agent critically depends on the human response it induces.

Illustration of imperfect human compliance in a car-following scenario

Figure 1. Illustration of imperfect human compliance in a car-following scenario.

To capture this dependence, let rr denote the action recommended by the recommendation agent, aa the action implemented by the human, and x∈Rmx \in\mathbb{R}^{m} the context of the physical system. Here, r,a∈Rr, a \in\mathbb{R}, and R⊂Rn\mathcal{R} \subset\mathbb{R}^{n} denotes a finite, discrete space. Imperfect human compliance is modelled by a conditional probability distribution a∼P(⋅∣r,x)a \sim P(\cdot\mid r, x), which describes how the implemented action depends on rr and xx. Given a fixed system context xx and a system cost ℓ(a,x):R→R\ell(a,x):\mathbb{R}\to\mathbb{R}, the recommendation problem can be formulated as

min⁡r∈RJ(r),J(r)=Ea∼P(⋅∣r,x)[ℓ(a,x)].(1)\min_{r\in\mathbb{R}} J(r),\qquad J(r)=\mathbb{E}_{a\sim P(\cdot\mid r,x)}\left[\ell(a,x)\right]. \tag*{(1)}

The recommendation performance is thus influenced by the distribution P(⋅∣r,x)P(\cdot\mid r,x).

However, in practice, the human compliance distribution P(⋅∣r,x)P(\cdot\mid r,x) is generally unknown to the recommendation agent. For a fixed operating context xx, a trusted cloud ChC_h stores historical actions grouped by the recommendations under which they were recorded. The recommendation agent queries these logs sequentially to learn the expected system loss J(r)J(r). To protect individual records, each sampled action is perturbed by the cloud using a differentially private mechanism before transmission (Dwork and Roth [8]). The privatised queries therefore reflect both variability in human responses and randomness introduced by the privacy mechanism.

Under imperfect compliance, the expected loss of a recommendation depends on how often it is followed and which actions are taken when it is ignored. Grand-Clément and Pauphilet [9] describe deviations through a baseline policy, while Bang et al. [4] assume uniform choice among alternative routes. But, when alternative actions incur different losses, their individual probabilities matter. This motivates modelling non-compliance via an unknown compliance distribution, analogous to the treatment response formulation in instrument-armed bandits (Kallus [11]). In CPHS, Dave et al. [7] learn the human response model directly from observed actions. However, access to such actions raises privacy issues. Related work has investigated learning from privatised user feedback in interactive recommendation systems (Zheng et al. [16]), as well as privacy-preserving data aggregation and state inference in human-in-the-loop systems (Cortés et al. [6]). Motivated by these studies, this paper formulates a general recommendation learning problem: how can a recommendation agent learn an optimal recommendation from privacy-protected historical data when the compliance distribution is unknown?

To solve this problem, a batched Gaussian process upper confidence bound (GP-UCB) algorithm (Srinivas et al. [15]) is adapted to learn a recommendation from perturbed historical actions using debiased loss estimates. The main contributions are summarised as follows.

  1. Departing from prior work that treats compliance and privacy in isolation, a human-in-the-loop recommendation framework that jointly accounts for imperfect human compliance and record-level differential privacy (RLDP) is proposed. The dependence of human actions on recommendations is captured by a conditional compliance distribution, leading to a decision-dependent stochastic optimisation problem at the recommendation agent.

  1. The analysis establishes a RLDP guarantee for the full sequence of adaptive queries and derives high-probability simple regret bounds. These results show how human behaviour and privacy noise enter the learning regret. In particular, a known upper bound on the non-compliance rate yields a screening rule that eliminates provably suboptimal recommendations before any private records are queried.

  1. A fixed-state car-following case study evaluates the proposed algorithm using synthetic historical driver responses and a one-step driving loss. Across different compliance distributions, the algorithm achieves low simple regret and outperforms a compliance-unaware recommendation. The simulations also illustrate the effects of privacy noise and compliance on simple regret and optimal-recommendation identification.

Problem Setup and Preliminaries

This section presents the system setup and assumptions for problem (1), followed by preliminaries on Gaussian process regression and the local differential privacy (LDP) mechanism.

System Setup and Assumptions

Following (1), R={α1,…,αK}\mathcal{R}=\{\alpha_1,\ldots,\alpha_K\} denotes a finite action space. The cloud maintains historical datasets D=⋃i=1KDi\mathcal{D}=\bigcup_{i=1}^{K}\mathcal{D}_i, Di={(ai,n,αi,x)}n=1Ni\mathcal{D}_i=\{(a_{i,n},\alpha_i,x)\}_{n=1}^{N_i}, where ai,n∈Ra_{i,n}\in\mathcal{R} is the nn-th recorded action implemented on the physical system in response to αi\alpha_i.

For each query from the recommendation agent, the cloud returns a locally privatised response sampled from D\mathcal{D} to protect any individual raw record within the historical dataset. To help the recommendation agent mitigate the effects of privacy noise, the cloud also provides the noise distribution, including its mean and variance, without revealing individual noise realisations. The recommendation agent knows the loss function ℓ\ell, the space R\mathcal{R}, and the fixed context xx, but not the compliance distributions {P(⋅∣αi,x)}i=1K\{P(\cdot\mid\alpha_i,x)\}_{i=1}^{K}. The following assumption is required.

Assumption 1. The compliance distributions {P(⋅∣αi,x)}i=1K\{P(\cdot\mid\alpha_i,x)\}_{i=1}^{K} remain unchanged throughout the collection of the historical dataset D\mathcal{D}. Each query for recommendation αi\alpha_i is answered by sampling uniformly with replacement from Di\mathcal{D}_i, using fresh sampling randomness at each query.

Under this setup, this work aims to learn an optimal recommendation for (1) from locally privatised query responses and derive regret bounds, while limiting what the recommendation agent or an external adversary can infer about any individual raw record within the historical dataset.

Gaussian Process Regression and Confidence Bounds

Gaussian process regression (GPR) is a nonparametric method for learning an unknown function from noisy observations, providing a posterior mean and associated uncertainty across the domain. GP-UCB then combines these quantities to construct an upper confidence bound that guides the sequential selection of recommendations by balancing exploration and exploitation. The mathematical formulation is as follows.

Let k:R×R→Rk:\mathcal{R}\times\mathcal{R}\to\mathbb{R} be a positive semidefinite kernel satisfying k(r,r)≤1k(r,r)\le1, ∀r∈R\forall r\in\mathcal{R}, and Hk\mathcal{H}_k denotes its associated reproducing kernel Hilbert space (RKHS). Given a prior mean function μ0:R→R\mu_0:\mathcal{R}\to\mathbb{R}, consider an unknown target function f∈Hkf\in\mathcal{H}_k satisfying ∥f−μ0∥Hk≤B\lVert f-\mu_0\rVert_{\mathcal{H}_k}\le B. At each time iteration tt, a recommendation rt∈Rr_t\in\mathcal{R} is selected based on the prior history Ft−1\mathcal{F}_{t-1}, and an observation yt=f(rt)+wty_t=f(r_t)+w_t is revealed, where the noise wtw_t is conditionally ν\nu-sub-Gaussian, meaning E[eνwt∣Ft−1]≤eν2σ2/2\mathbb{E}[e^{\nu w_t}\mid\mathcal{F}_{t-1}]\le e^{\nu^2\sigma^2/2}, ∀ν∈R\forall\nu\in\mathbb{R}.

Given observations Ot={(ri,yi)}i=1t\mathcal{O}_t=\{(r_i,y_i)\}_{i=1}^{t}, let y1:t=[y1,…,yt]⊤y_{1:t}=[y_1,\ldots,y_t]^\top, μ0,1:t=[μ0(r1),…,μ0(rt)]⊤\mu_{0,1:t}=[\mu_0(r_1),\ldots,\mu_0(r_t)]^\top, kt(r)=[k(r1,r),…,k(rt,r)]⊤k_t(r)=[k(r_1,r),\ldots,k(r_t,r)]^\top, and Kt=[k(ri,rj)]i,j=1tK_t=[k(r_i,r_j)]_{i,j=1}^{t} be the kernel matrix. With a GP prior mean μ0(r)\mu_{0}(r) and unit regularisation, the posterior mean and variance at any r∈Rr \in\mathcal{R} are given by

μt(r)=μ0(r)+kt(r)⊤(Kt+It)−1(y1:t−μ0,1:t),st2(r)=k(r,r)−kt(r)⊤(Kt+It)−1kt(r),(2)\mu_{t}(r)=\mu_{0}(r)+\mathbf{k}_{t}(r)^{\top}(\mathbf{K}_{t}+\mathbf{I}_{t})^{-1}(\mathbf{y}_{1:t}-\mu_{0,1:t}),\qquad s_{t}^{2}(r)=k(r,r)-\mathbf{k}_{t}(r)^{\top}(\mathbf{K}_{t}+\mathbf{I}_{t})^{-1}\mathbf{k}_{t}(r), \tag*{(2)}

with s02(r)=k(r,r)s_{0}^{2}(r)=k(r,r), and It\mathbf{I}_{t} is the identity matrix. Following the GP-UCB framework [15], a high-probability uniform confidence bound is derived from (2) by adapting self-normalised concentration inequalities to the RKHS setting [1]. Specifically, for any δc∈(0,1)\delta_{\mathrm{c}} \in(0,1), with probability at least 1−δc1-\delta_{\mathrm{c}},

∣f(r)−μt−1(r)∣≤btst−1(r),∀r∈R, ∀t≥1,(3)\lvert f(r)-\mu_{t-1}(r)\rvert\le b_{t}s_{t-1}(r),\qquad\forall r\in\mathcal{R},\ \forall t\ge1, \tag*{(3)}

where the confidence multiplier is given by bt=B+ν2(It−1+log⁡1δc)b_{t}=B+\nu\sqrt{2\left(\mathcal{I}_{t-1}+\log\frac{1}{\delta_{\mathrm{c}}}\right)}, and It=12log⁡det⁡(It+Kt)\mathcal{I}_{t}=\frac{1}{2}\log\det(\mathbf{I}_{t}+\mathbf{K}_{t}) denotes the information gain after tt evaluations (I0=0\mathcal{I}_{0}=0).

Local Differential Privacy Mechanism

Let Si,t={(aˉi,t,j,αi,x)}j=1M\mathcal{S}_{i,t}=\{(\bar{a}_{i,t,j},\alpha_{i},x)\}_{j=1}^{M} denote a batch drawn independently and uniformly with replacement from Di\mathcal{D}_{i} at iteration tt. To protect individual records in D\mathcal{D}, each sampled action is locally perturbed before transmission to the recommendation agent for GPR updates and GP-UCB selection.

Definition 1 (Dwork and Roth, [8]) A randomised mechanism M:U→V\mathcal{M}:\mathcal{U}\to\mathcal{V} satisfies (ϵ,δ)(\epsilon,\delta)-DP if, for all u,u′∈Uu,u'\in\mathcal{U} and all measurable subsets S⊆V\mathcal{S}\subseteq\mathcal{V},

Pr⁡(M(u)∈S)≤eϵPr⁡(M(u′)∈S)+δ,\Pr(\mathcal{M}(u)\in\mathcal{S})\le e^{\epsilon}\Pr(\mathcal{M}(u')\in\mathcal{S})+\delta,

where ϵ>0\epsilon>0 and δ∈[0,1)\delta\in[0,1) denote the privacy parameters. When δ=0\delta=0, M\mathcal{M} satisfies pure ϵ\epsilon-DP.

Lemma 1 (Le Ny and Pappas, [12]) Let ϵ>0\epsilon>0, δ∈(0,12)\delta\in(0,\frac{1}{2}) and Q(x)=12π∫x∞e−u22 duQ(x)=\frac{1}{\sqrt{2\pi}}\int_{x}^{\infty}e^{-\frac{u^{2}}{2}}\,\mathrm{d}u. Consider a function q:U→Rnq:\mathcal{U}\to\mathbb{R}^{n} with ℓ2\ell_{2}-sensitivity Δ2(q)=sup⁡u,u′∈U∥q(u)−q(u′)∥2\Delta_{2}(q)=\sup_{u,u'\in\mathcal{U}}\lVert q(u)-q(u')\rVert_{2}. The mechanism M(u)=q(u)+η\mathcal{M}(u)=q(u)+\eta, η∼N(0,σ2)\eta\sim\mathcal{N}(0,\sigma^{2}), satisfies (ϵ,δ)(\epsilon,\delta)-DP, where

σ≥Δ2(q)Q−2(δ)+2ϵ−Q−1(δ).\sigma\ge\frac{\Delta_{2}(q)}{\sqrt{Q^{-2}(\delta)+2\epsilon}-Q^{-1}(\delta)}.

Compliance-Aware Recommendation Algorithm with Privacy Preservation

This section presents the proposed algorithm, summarised in Algorithm 1. Under Assumption 1, it applies batched GP-UCB to solve (1) via privatised queries, using a privacy channel to debias loss estimates and updating a GP model for recommendation selection. The main steps follow.

Local Sampling and Private Queries. At iteration tt, let rt=αir_{t}=\alpha_{i} (i∈{1,…,K}i\in\{1,\ldots,K\}) be the recommendation selected by the recommendation agent. The cloud draws a batch Si,t\mathcal{S}_{i,t} from Di\mathcal{D}_{i} and transmits the perturbed batch S~i,t={(a~i,t,j,αi,x)}j=1M\widetilde{\mathcal{S}}_{i,t}=\{(\widetilde{a}_{i,t,j},\alpha_{i},x)\}_{j=1}^{M} to the recommendation agent, where

a~i,t,j=ai,t,j+ηi,t,j,ηi,t,j∼i.i.d.N(0,σ2In),j=1,…,M,(4)\widetilde{a}_{i,t,j}=a_{i,t,j}+\eta_{i,t,j},\qquad\eta_{i,t,j}\overset{\mathrm{i.i.d.}}{\sim}\mathcal{N}(0,\sigma^{2}\mathbf{I}_{n}),\qquad j=1,\ldots,M, \tag*{(4)}

with noise samples independent of the sampled actions. Upon receiving S~i,t\widetilde{\mathcal{S}}_{i,t}, the recommendation agent projects each perturbed action onto R\mathcal{R} via the nearest-neighbour operator:

zt,j=ΠR(a~i,t,j)≜αk∗(a~i,t,j),k∗(u)≜min⁡{arg min⁡k∈{1,…,K} ∥u−αk∥2}.(5)z_{t,j}=\Pi_{\mathcal{R}}(\widetilde{a}_{i,t,j})\triangleq\alpha_{k^{*}(\widetilde{a}_{i,t,j})},\qquad k^{*}(u)\triangleq\min\left\{\underset{k\in\{1,\ldots,K\}}{\operatorname{arg\,min}}\ \lVert u-\alpha_{k}\rVert_{2}\right\}. \tag*{(5)}

Privacy Channel and Loss Debiasing

The perturbation in (4) and projection in (5) induce a recommendation-independent privacy channel with column-stochastic transition matrix Wσ∈RK×KW_{\sigma} \in\mathbb{R}^{K \times K} (1K⊤Wσ=1K⊤\mathbf{1}_{K}^{\top}W_{\sigma}=\mathbf{1}_{K}^{\top}), whose entries are

[Wσ]kl=Pr⁡(ΠR(αl+η)=αk)=∫Vk1(2πσ2)n/2e−∥u−αl∥22σ2 du,η∼N(0,σ2In),(6)[W_{\sigma}]_{kl}=\Pr(\Pi_{\mathcal{R}}(\alpha_l+\eta)=\alpha_k)=\int_{\mathcal{V}_k}\frac{1}{(2\pi\sigma^2)^{n/2}}e^{-\frac{\lVert u-\alpha_l\rVert^2}{2\sigma^2}}\,du,\qquad\eta\sim\mathcal{N}(0,\sigma^2 I_n), \tag*{(6)}

where Vk={u∈Rn:ΠR(u)=αk}\mathcal{V}_k=\{u\in\mathbb{R}^n:\Pi_{\mathcal{R}}(u)=\alpha_k\} denotes the Voronoi projection region associated with αk\alpha_k. Let ℓ=[ℓ(α1,x),…,ℓ(αK,x)]⊤\boldsymbol{\ell}=[\ell(\alpha_1,x),\ldots,\ell(\alpha_K,x)]^{\top}. Assuming WσW_{\sigma} is invertible, the recommendation agent precomputes the debiased loss vector ℓ~σ=[ℓ~σ,1,…,ℓ~σ,K]⊤\widetilde{\boldsymbol{\ell}}_{\sigma}=[\widetilde{\ell}_{\sigma,1},\ldots,\widetilde{\ell}_{\sigma,K}]^{\top} prior to the online iterations by solving

Wσ⊤ℓ~σ=ℓ.(7)W_{\sigma}^{\top}\widetilde{\boldsymbol{\ell}}_{\sigma}=\boldsymbol{\ell}. \tag*{(7)}

By mapping each projected sample zt,j=αkz_{t,j}=\alpha_k to ℓ~σ(zt,j,x)=[ℓ~σ]k\widetilde{\ell}_{\sigma}(z_{t,j},x)=[\widetilde{\boldsymbol{\ell}}_{\sigma}]_k, the debiased batch loss at iteration tt is computed as

J^tdeb=1M∑j=1Mℓ~σ(zt,j,x).(8)\widehat{J}^{\mathrm{deb}}_t=\frac{1}{M}\sum_{j=1}^{M}\widetilde{\ell}_{\sigma}(z_{t,j},x). \tag*{(8)}

Algorithm 1: Batched GP-UCB with debiased private feedback

Input: Action set R\mathcal{R}, context xx, losses {ℓ(αi,x)}i=1K\{\ell(\alpha_i,x)\}_{i=1}^{K}, noise level σ\sigma, batch size MM, horizon TT, kernel parameters h,ρh,\rho, confidence parameter δc\delta_c, prior pair (μ0,B)(\mu_0,B)

Output: Recommendation r^T\widehat{r}_T

  1. Compute Lmin⁡L_{\min}, Lmax⁡L_{\max}, DD, and cc;

  2. Construct WσW_{\sigma} by (6) and solve (7);

  3. Compute D~σ\widetilde{D}_{\sigma} and νσ\nu_{\sigma} by (10);

  4. Set s0(r)=1s_0(r)=1 for all r∈Rr\in\mathcal{R}, and set I0=0\mathcal{I}_0=0 (default prior: μ0(r)=0\mu_0(r)=0, B=K2ρB=\frac{\sqrt{K}}{2\sqrt{\rho}});

  5. for t=1,…,Tt=1,\ldots,T do

    1. Compute btb_t and select rtr_t by (12);

    2. Record qt=μt−1(rt)−btst−1(rt)q_t=\mu_{t-1}(r_t)-b_ts_{t-1}(r_t);

    3. For rt=αir_t=\alpha_i, the cloud samples MM actions independently with replacement from Di\mathcal{D}_i and transmits their perturbed values by (4);

    4. Project the received values by (5) and calculate yty_t by (8) and (9);

    5. Add (rt,yt)(r_t,y_t) to the GP data and update μt\mu_t, sts_t, and It\mathcal{I}_t;

    6. Set τ∈arg⁡max⁡1≤t≤Tqt\tau\in\arg\max_{1\leq t\leq T}q_t and r^T=rτ\widehat{r}_T=r_{\tau};

    7. return r^T\widehat{r}_T;

GP-Based Recommendation Selection and Update

Define Lmin⁡≜min⁡iℓ(αi,x)L_{\min}\triangleq\min_i\ell(\alpha_i,x), Lmax⁡≜max⁡iℓ(αi,x)L_{\max}\triangleq\max_i\ell(\alpha_i,x), D≜Lmax⁡−Lmin⁡D\triangleq L_{\max}-L_{\min}, and c≜(Lmin⁡+Lmax⁡)/2c\triangleq(L_{\min}+L_{\max})/2. If D=0D=0, every recommendation is optimal, so this case is omitted here. For the non-trivial case D>0D>0, minimising J(r)J(r) is equivalent to maximising the normalised objective f(r)f(r), with the corresponding GP observation yty_t given by

f(r)=c−J(r)D,yt=c−J^tdebD.(9)f(r)=\frac{c-J(r)}{D},\qquad y_t=\frac{c-\widehat{J}^{\mathrm{deb}}_t}{D}. \tag*{(9)}

To calibrate the GP confidence bound under debiased batch observations, set the span of the debiased loss vector and the effective noise scale (corresponding to ν\nu in § 2.2) as

D~σ=max⁡k[ℓ~σ]k−min⁡k[ℓ~σ]k,νσ=D~σ2DM.(10)\widetilde{D}_{\sigma}=\max_k[\widetilde{\boldsymbol{\ell}}_{\sigma}]_k-\min_k[\widetilde{\boldsymbol{\ell}}_{\sigma}]_k,\qquad\nu_{\sigma}=\frac{\widetilde{D}_{\sigma}}{2D\sqrt{M}}. \tag*{(10)}

Adopt the regularised Gaussian kernel

k(r,r′)=(1−ρ)e−∥r−r′∥222h2+ρ1{r=r′},h>0, 0<ρ≤1.(11)k(r,r') = (1-\rho)e^{-\frac{\lVert r-r'\rVert_2^2}{2h^2}}+\rho\mathbf{1}_{\{r=r'\}},\qquad h>0,\ 0<\rho\leq1. \tag*{(11)}

The GP is initialised with s0(r)=1s_0(r)=1 for all r∈Rr\in\mathcal{R} and a prior pair (μ0,B)(\mu_0,B) satisfying ∥f−μ0∥Hk≤B\lVert f-\mu_0\rVert_{\mathcal{H}_k}\leq B. Without prior compliance information, set μ0(r)=0\mu_0(r)=0 and B=K2ρB=\frac{\sqrt{K}}{2\sqrt{\rho}}.

At each iteration tt, using the confidence multiplier btb_t from § 2.2 (with ν=νσ\nu=\nu_\sigma and confidence parameter δc∈(0,1)\delta_c\in(0,1)), the algorithm selects the recommendation rtr_t and records its pessimistic score qtq_t:

rt∈arg max⁡r∈R[μt−1(r)+btst−1(r)],qt=μt−1(rt)−btst−1(rt).(12)r_t\in\underset{r\in\mathcal{R}}{\operatorname{arg\,max}}\left[\mu_{t-1}(r)+b_ts_{t-1}(r)\right],\qquad q_t=\mu_{t-1}(r_t)-b_ts_{t-1}(r_t). \tag*{(12)}

After updating the posterior mean μt(r)\mu_t(r) and standard deviation st(r)s_t(r) with yty_t via (2), the algorithm returns r^T=rτ\hat{r}_T=r_\tau after TT iterations, where τ∈arg max⁡1≤t≤Tqt\tau\in\operatorname{arg\,max}_{1\leq t\leq T}q_t.

Privacy and Regret Analysis

This section establishes privacy and regret guarantees for Algorithm 1. The GP confidence bound (3) requires a bounded RKHS norm and conditionally sub-Gaussian observation noise. These conditions are first examined for the empirical objective induced by the dataset D\mathcal{D}.

Let p(αi)=[P(α1∣αi,x),…,P(αK∣αi,x)]⊤p(\alpha_i)=[P(\alpha_1\mid\alpha_i,x),\ldots,P(\alpha_K\mid\alpha_i,x)]^\top denote the compliance distribution under αi\alpha_i, and let P=[p(α1),…,p(αK)]P=[p(\alpha_1),\ldots,p(\alpha_K)] be the compliance transition matrix. For the fixed dataset D\mathcal{D}, let p^i\hat{p}_i be the empirical action distribution in Di\mathcal{D}_i and define JD(αi)=ℓ⊤p^iJ_{\mathcal{D}}(\alpha_i)=\ell^\top\hat{p}_i. For rt=αir_t=\alpha_i, Assumption 1 implies that {zt,j}j=1M\{z_{t,j}\}_{j=1}^{M} are conditionally i.i.d. given Ft−1\mathcal{F}_{t-1}, with distribution Wσp^iW_\sigma\hat{p}_i. By (7),

E[ℓ~σ(zt,j,x)∣Ft−1]=ℓ~σ⊤Wσp^i=ℓ⊤p^i=JD(rt).\mathbb{E}[\tilde{\ell}_\sigma(z_{t,j},x)\mid\mathcal{F}_{t-1}]=\tilde{\ell}_\sigma^\top W_\sigma\hat{p}_i=\ell^\top\hat{p}_i=J_{\mathcal{D}}(r_t).

Thus, J^tdeb\hat{J}^{\mathrm{deb}}_t is conditionally unbiased for JD(rt)J_{\mathcal{D}}(r_t). For D>0D>0, define fD(r)=(c−JD(r))/Df_{\mathcal{D}}(r)=(c-J_{\mathcal{D}}(r))/D. By (9), E[yt−fD(rt)]=0\mathbb{E}[y_t-f_{\mathcal{D}}(r_t)]=0. Since the debiased losses are conditionally independent and each lies in an interval of length D~σ\widetilde{D}_\sigma, Hoeffding's Lemma (Hoeffding, [10]) gives the conditional sub-Gaussian parameter νσ=D~σ/(2DM)\nu_\sigma=\widetilde{D}_\sigma/(2D\sqrt{M}) in (10). If p^i=p(αi)\hat{p}_i=p(\alpha_i) for every ii, then JD=JJ_{\mathcal{D}}=J and fD=ff_{\mathcal{D}}=f.

For the default prior μ0=0\mu_0=0, let KRK_{\mathcal{R}} be the kernel matrix evaluated on R\mathcal{R} and let fD=[fD(α1),…,fD(αK)]⊤\mathbf{f}_{\mathcal{D}}=[f_{\mathcal{D}}(\alpha_1),\ldots,f_{\mathcal{D}}(\alpha_K)]^\top. The diagonal regulariser in (11) gives λmin⁡(KR)≥ρ\lambda_{\min}(K_{\mathcal{R}})\geq\rho. Since ∣fD(r)∣≤1/2|f_{\mathcal{D}}(r)|\leq1/2 for all r∈Rr\in\mathcal{R},

∥fD−μ0∥Hk=fD⊤KR−1fD≤K2ρ=B.\lVert f_{\mathcal{D}}-\mu_0\rVert_{\mathcal{H}_k}=\sqrt{\mathbf{f}_{\mathcal{D}}^\top K_{\mathcal{R}}^{-1}\mathbf{f}_{\mathcal{D}}}\leq\frac{\sqrt{K}}{2\sqrt{\rho}}=B.

Consequently, the confidence bound (3) holds uniformly throughout Algorithm 1 with probability at least 1−δc1-\delta_c. The privacy and regret guarantees are established in the following subsections.

Record-Level Privacy Guarantee of Algorithm 1

Let ΔR≜max⁡a,a′∈R∥a−a′∥2\Delta_{\mathcal{R}}\triangleq\max_{a,a'\in\mathcal{R}}\lVert a-a'\rVert_2 denote the diameter of the action space. The RLDP guarantee is established as follows.

Theorem 2 Under Assumption 1, select δ0∈(0,12)\delta_0\in(0,\frac{1}{2}) and σ>0\sigma>0 in (4) such that ϵ0≜ΔR22σ2+ΔRσQ−1(δ0)\epsilon_0\triangleq\frac{\Delta_{\mathcal{R}}^2}{2\sigma^2}+\frac{\Delta_{\mathcal{R}}}{\sigma}\mathcal{Q}^{-1}(\delta_0). For each i∈{1,…,K}i\in\{1,\ldots,K\}, every raw action record ai,na_{i,n} in the historical dataset Di={(ai,n,αi,x)}n=1Ni\mathcal{D}_i=\{(a_{i,n},\alpha_i,x)\}_{n=1}^{N_i} satisfies at least (ϵi,T,δi,T)(\epsilon_{i,T},\delta_{i,T})-RLDP over TT iterations of Algorithm 1, where

ϵi,T=MTlog⁡(1+eϵ0−1Ni),δi,T=MTδ0Ni.(13)\epsilon_{i,T}=MT\log\left(1+\frac{e^{\epsilon_0}-1}{N_i}\right),\qquad\delta_{i,T}=\frac{MT\delta_0}{N_i}. \tag*{(13)}

Proof. Consider a single sample draw at iteration t≤Tt \le T when rt=αir_t = \alpha_i. Define the perturbation mechanism in (4) as M(a)≜a+η\mathcal{M}(a) \triangleq a + \eta for any a∈Ra \in\mathcal{R}. Since the ℓ2\ell_2-sensitivity of releasing an action in R\mathcal{R} is ΔR\Delta_{\mathcal{R}}, Lemma 1 ensures that M\mathcal{M} satisfies (ϵ0,δ0)(\epsilon_0,\delta_0)-DP with respect to each sampled action aˉi,t,j\bar{a}_{i,t,j}.

Next, analyse the privacy guarantee for any specific raw record ai,n∈Dia_{i,n} \in\mathcal{D}_i under a single uniform draw with replacement. Define the subsampled mechanism Ms(Di)≜M(aˉi,t,j)\mathcal{M}_s(\mathcal{D}_i) \triangleq\mathcal{M}(\bar{a}_{i,t,j}), which draws an action aˉi,t,j\bar{a}_{i,t,j} uniformly at random from Di\mathcal{D}_i and then applies the base mechanism M\mathcal{M}. Let Di\mathcal{D}_i and Di′\mathcal{D}'_i be two neighbouring datasets of size NiN_i differing only in the nn-th record (ai,na_{i,n} versus ai,n′a'_{i,n}). By Assumption 1, a single draw selects the nn-th record with probability 1Ni\frac{1}{N_i}, and selects from the remaining Ni−1N_i-1 identical records with probability 1−1Ni1-\frac{1}{N_i} (inducing a common output distribution QQ under both Di\mathcal{D}_i and Di′\mathcal{D}'_i). Thus, for any measurable set SS, the output of Ms\mathcal{M}_s satisfies

Pr⁡(Ms(Di)∈S)=Ni−1NiQ(S)+1NiPr⁡(M(ai,n)∈S)≤Ni−1NiQ(S)+1Ni(eϵ0Pr⁡(M(ai,n′)∈S)+δ0)\Pr(\mathcal{M}_s(\mathcal{D}_i) \in S)=\frac{N_i-1}{N_i}Q(S)+\frac{1}{N_i}\Pr(\mathcal{M}(a_{i,n})\in S)\le\frac{N_i-1}{N_i}Q(S)+\frac{1}{N_i}\left(e^{\epsilon_0}\Pr(\mathcal{M}(a'_{i,n})\in S)+\delta_0\right)

where the inequality follows from the (ϵ0,δ0)(\epsilon_0,\delta_0)-DP property of M\mathcal{M}. Applying the standard privacy amplification bound by subsampling (Balle et al., [3]) yields Pr⁡(Ms(Di)∈S)≤eϵiPr⁡(Ms(Di′)∈S)+δi\Pr(\mathcal{M}_s(\mathcal{D}_i) \in S) \le e^{\epsilon_i}\Pr(\mathcal{M}_s(\mathcal{D}'_i) \in S)+\delta_i, confirming that Ms\mathcal{M}_s satisfies (ϵi,δi)(\epsilon_i,\delta_i)-RLDP with ϵi=log⁡(1+eϵ0−1Ni)\epsilon_i=\log(1+\frac{e^{\epsilon_0}-1}{N_i}) and δi=δ0Ni\delta_i=\frac{\delta_0}{N_i}.

Finally, since each query to Di\mathcal{D}_i invokes Ms\mathcal{M}_s independently MM times and Di\mathcal{D}_i is queried at most TT times, Ms\mathcal{M}_s is executed no more than MTMT times on Di\mathcal{D}_i. By the sequential composition theorem (Dwork and Roth, [8]) and the post-processing immunity of the projection operator (5), the overall privacy loss over TT iterations is bounded by (ϵi,T,δi,T)(\epsilon_{i,T},\delta_{i,T}) in (13).

While the bound in (13) depends on TT, it serves as an a priori worst-case guarantee by assuming Di\mathcal{D}_i is queried in every iteration. In practice, because query decisions are adaptive, the actual number of queries made to Di\mathcal{D}_i by termination is a trajectory-dependent quantity that may be strictly smaller, yielding a tighter ex-post realised privacy loss (ϵi,T′,δi,T′)(\epsilon'_{i,T},\delta'_{i,T}).

Regret Bounds and Behavioural Insights for Algorithm 1

Let r⋆∈arg⁡min⁡r∈RJ(r)r^\star\in\arg\min_{r\in\mathcal{R}} J(r). The simple regret of Algorithm 1 after TT iterations is defined as ST≜J(r^T)−J(r⋆)S_T \triangleq J(\hat{r}_T)-J(r^\star). Moreover, let γT≜max⁡r1:T∈RTIT\gamma_T \triangleq\max_{r_{1:T}\in\mathcal{R}^T} I_T denote the maximum information gain over all TT-step recommendation sequences, and κ(r)≜Pr⁡(a≠r∣r,x)\kappa(r) \triangleq\Pr(a \ne r \mid r,x) the non-compliance rate.

Lemma 3 (Srinivas et al., [15]; Abbasi-Yadkori et al. [1]). For any sequence {r1,…,rT}∈RT\{r_1,\ldots,r_T\}\in\mathcal{R}^T and horizon T≥1T\ge1 under k(r,r)≤1k(r,r)\le1 and ∣R∣=K|\mathcal{R}|=K, the cumulative posterior variance and maximum information gain satisfy ∑t=1Tst−12(rt)≤2TγTlog⁡2≤2γTlog⁡2\sum_{t=1}^{T}s^2_{t-1}(r_t)\le\frac{2T\gamma_T}{\log2}\le\frac{2\gamma_T}{\log2}, and γT≤K2log⁡(1+TK)\gamma_T\le\frac{K}{2}\log(1+\frac{T}{K}).

Theorem 4 Suppose p^i=p(αi),∀i∈R\hat{p}_i=p(\alpha_i),\forall i\in\mathcal{R} and Assumption 1 hold, D>0D>0, and WσW_\sigma in (6) is invertible. Run Algorithm 1 with the GP prior mean μ0\mu_0 and parameter BB specified by one of the following settings:

  1. Unknown compliance distribution. Set default prior: μ0(r)=0\mu_0(r)=0, B=K2ρB=\frac{\sqrt{K}}{2\sqrt{\rho}}.

  1. Known non-compliance bound. Suppose κ(r)≤κˉ,∀r∈R\kappa(r)\le\bar{\kappa},\forall r\in\mathcal{R}, where κˉ∈[0,1]\bar{\kappa}\in[0,1] is known. Set

g(r)=c−ℓ(r,x)D,μ0(r)=(1−κˉ)g(r),B=κˉK2ρ,g(r)=\frac{c-\ell(r,x)}{D},\qquad\mu_0(r)=(1-\bar{\kappa})g(r),\qquad B=\frac{\bar{\kappa}\sqrt{K}}{2\sqrt{\rho}},

For either setting and any δc∈(0,1)\delta_c \in(0,1), the simple regret of Algorithm 1 satisfies the following bound simultaneously for all T≥1T \ge1, with probability at least 1−δc1-\delta_c:

J(r^T)−J(r∗)≤2DbT2γTTlog⁡2,(14)J(\hat{r}_T)-J(r^*) \le2D b_T \sqrt{\frac{2\gamma_T}{T\log2}}, \tag*{(14)}

where bT=B+D~σ2DM2(IT−1+log⁡1δc)b_T = B + \frac{\widetilde{D}_\sigma}{2D\sqrt{M}}\sqrt{2\left(\mathcal{I}_{T-1}+\log\frac{1}{\delta_c}\right)}, IT−1≤γT≤K2log⁡(1+TK)\mathcal{I}_{T-1} \le\gamma_T \le\frac{K}{2}\log\left(1+\frac{T}{K}\right).

Proof. For the first setting, the preceding analysis establishes ∥f−μ0∥Hk=∥f∥Hk≤K2ρ\|f-\mu_0\|_{\mathcal{H}_k}=\|f\|_{\mathcal{H}_k}\le\frac{\sqrt{K}}{2\sqrt{\rho}} with p^i=p(αi)\hat{p}_i=p(\alpha_i). For the second, expanding f(r)=∑a∈RP(a∣r,x)g(a)f(r)=\sum_{a\in\mathcal{R}}P(a\mid r,x)g(a) yields f(r)−μ0(r)=(κˉ−κ(r))g(r)+∑a≠rP(a∣r,x)g(a)f(r)-\mu_0(r)=(\bar{\kappa}-\kappa(r))g(r)+\sum_{a\ne r}P(a\mid r,x)g(a). Since the coefficients are non-negative and sum to κˉ\bar{\kappa}, and ∣g(a)∣≤1/2|g(a)|\le1/2, ∀a∈R\forall a\in\mathcal{R}, it follows that ∣f(r)−μ0(r)∣≤κˉ/2|f(r)-\mu_0(r)|\le\bar{\kappa}/2. Combined with KR⪰ρIKK_{\mathcal{R}}\succeq\rho I_K implies ∥f−μ0∥Hk≤κˉK/(2ρ)\|f-\mu_0\|_{\mathcal{H}_k}\le\bar{\kappa}\sqrt{K}/(2\sqrt{\rho}). Hence, ∥f−μ0∥Hk≤B\|f-\mu_0\|_{\mathcal{H}_k}\le B holds for either setting with its BB.

With p^i=p(αi)\hat{p}_i=p(\alpha_i), the preceding analysis shows that yt−f(rt)y_t-f(r_t) is conditionally νσ\nu_\sigma-sub-Gaussian. Applying the confidence bound (3) to f−μ0f-\mu_0 ensures that, with probability at least 1−δc1-\delta_c, ∣f(r)−μt−1(r)∣≤btst−1(r)|f(r)-\mu_{t-1}(r)|\le b_t s_{t-1}(r) for all r∈Rr\in\mathcal{R} and t≥1t\ge1. Conditioned on this event, the selection rule (12) implies f(r∗)≤μt−1(rt)+btst−1(rt)=qt+2btst−1(rt)f(r^*)\le\mu_{t-1}(r_t)+b_t s_{t-1}(r_t)=q_t+2b_t s_{t-1}(r_t) and qt≤f(rt)q_t\le f(r_t). Since r^T=rτ\hat{r}_T=r_\tau with τ∈arg⁡max⁡1≤t≤Tqt\tau\in\arg\max_{1\le t\le T}q_t and bt≤bTb_t\le b_T, applying the Cauchy–Schwarz inequality and Lemma 3 gives f(r∗)−f(r^T)≤min⁡1≤t≤T(f(r∗)−qt)≤2bTT∑t=1Tst−1(rt)≤2bT2γT/(Tlog⁡2)f(r^*)-f(\hat{r}_T)\le\min_{1\le t\le T}(f(r^*)-q_t)\le\frac{2b_T}{T}\sum_{t=1}^{T}s_{t-1}(r_t)\le2b_T\sqrt{2\gamma_T/(T\log2)}. Multiplying both sides by DD establishes (14).

Combining Theorem 2 and Theorem 4 yields some key insights into the interplay between privacy protection, human compliance, and learning performance:

  1. Privacy–Suboptimality Trade-off under Imperfect Compliance. Although exact loss debiasing yields unbiased batch estimates, their concentration depends on the debiased loss span D~σ\widetilde{D}_\sigma, which enters the regret bounds in (14). For an invertible WσW_\sigma, this span satisfies max⁡i≠j∣ℓi−ℓj∣2Φ(∥αi−αj∥2/(2σ))−1≤D~σ≤2∥ℓ−c1∥2smin⁡(Wσ)\max_{i\ne j}\frac{|\ell_i-\ell_j|}{2\Phi(\|\alpha_i-\alpha_j\|_2/(2\sigma))-1}\le\widetilde{D}_\sigma\le\frac{\sqrt{2}\|\ell-c\mathbf{1}\|_2}{s_{\min}(W_\sigma)}, where smin⁡(Wσ)s_{\min}(W_\sigma) is the smallest singular value of WσW_\sigma. The lower bound is at least 2πσmax⁡i≠j∣ℓi−ℓj∣∥αi−αj∥2\sqrt{2\pi}\sigma\max_{i\ne j}\frac{|\ell_i-\ell_j|}{\|\alpha_i-\alpha_j\|_2}. Thus, the lower bound on D~σ\widetilde{D}_\sigma grows at least linearly with σ\sigma. The upper bound depends on the conditioning of the privacy channel and may be large when WσW_\sigma is ill-conditioned. These bounds characterise the dependence of the stated regret guarantees on privacy noise. The effect of σ\sigma on the regret bound also depends on the information gain It\mathcal{I}_t of the adaptively selected recommendations, which can vary with the human compliance distribution.

  1. Guidelines for Batch Size Selection: Increasing the batch size MM shrinks STS_T at rate M−1/2M^{-1/2}. However, since ϵi,T\epsilon_{i,T} scales linearly with MM (modulated by the dataset size NiN_i), a larger MM accelerates RLDP budget consumption. Let MreqM_{\mathrm{req}} denote the minimum batch size required to guarantee ST≤τS_T\le\tau (Theorem 4), and let MprivM_{\mathrm{priv}} denote the maximum batch size permitted under the TT-round RLDP budget (ϵˉ,δˉ)(\bar{\epsilon},\bar{\delta}) and dataset size NiN_i (Theorem 2). Then the condition Mreq≤MprivM_{\mathrm{req}}\le M_{\mathrm{priv}} certifies that target accuracy and privacy are jointly attainable. Furthermore, under a fixed total sample budget MTMT, a dominant structural complexity BB favours more rounds with smaller batches to prioritise exploration, whereas a large debiased span D~σ\widetilde{D}_\sigma favours fewer rounds with larger batches to suppress per-step estimation variance.

  1. Recommendation space screening via κˉ\bar{\kappa}: Suppose κˉ\bar{\kappa} is known a priori to the recommendation agent. For r0∈arg⁡min⁡r∈Rℓ(r,x)r_0 \in\arg\min_{r\in\mathcal{R}} \ell(r,x) and Δ(r)=ℓ(r,x)−ℓ(r0,x)\Delta(r)=\ell(r,x)-\ell(r_0,x), the bound

J(r)−J(r0)≥(1−κˉ)Δ(r)−κˉDˉJ(r)-J(r_0)\geq(1-\bar{\kappa})\Delta(r)-\bar{\kappa}\bar{D}

ensures that every minimiser of JJ resides in the screened set A={r∈R:(1−κˉ)Δ(r)≤κˉDˉ}\mathcal{A}=\{r\in\mathcal{R}:(1-\bar{\kappa})\Delta(r)\leq\bar{\kappa}\bar{D}\}, computable offline from ℓ\ell and κˉ\bar{\kappa}. In particular, if (1−κˉ)min⁡r≠r0Δ(r)>κˉDˉ(1-\bar{\kappa})\min_{r\neq r_0}\Delta(r)>\bar{\kappa}\bar{D}, then A={r0}\mathcal{A}=\{r_0\}, allowing r0r_0 to be returned directly without querying any logs. Otherwise, restricting Algorithm 1 to A\mathcal{A} tightens the RKHS norm bound to BA=κˉ∣A∣/(2ρ)B_{\mathcal{A}}=\bar{\kappa}\sqrt{|\mathcal{A}|}/(2\sqrt{\rho}) and the maximum information gain to γT(A)≤12∣A∣log⁡(1+T/∣A∣)\gamma_T(\mathcal{A})\leq\frac{1}{2}|\mathcal{A}|\log(1+T/|\mathcal{A}|).

Remark 5 Exact loss debiasing in Theorem 4 requires ℓ∈Range⁡(WσT)\ell\in\operatorname{Range}(W_{\sigma}^{\mathsf{T}}), which holds automatically when WσW_{\sigma} is invertible. Under this condition, even if WσW_{\sigma} is rank-deficient, a valid debiased loss vector is ℓ~σ=(WσT)†ℓ\tilde{\ell}_{\sigma}=(W_{\sigma}^{\mathsf{T}})^{\dagger}\ell (the Moore–Penrose pseudoinverse). Since WσTℓ~σ=ℓW_{\sigma}^{\mathsf{T}}\tilde{\ell}_{\sigma}=\ell, the resulting loss estimates remain exactly unbiased. The conclusion of Theorem 4 and the regret bounds retain their stated form, with the debiased loss span and the corresponding noise parameter computed from ℓ~σ=(WσT)†ℓ\tilde{\ell}_{\sigma}=(W_{\sigma}^{\mathsf{T}})^{\dagger}\ell.

A Case Study in Advanced Driver Assistance Systems

This section applies the proposed framework to longitudinal driving advisory, with the ADAS as the recommendation agent, and examines the effects of privacy noise and driver compliance.

Mathematical Modelling

Consider a highway car-following scenario (see Figure 1) in which an ADAS seeks an optimal steady-state acceleration recommendation for a representative, discretised traffic regime (e.g. a clustered cruising band of speeds and inter-vehicle spacings). The context for this regime is fixed as x=(ve,vl,s,θd)x=(v_e,v_l,s,\theta_d), where vev_e, vlv_l, and ss denote the ego speed, leading vehicle speed, and net spacing, respectively. The parameter vector θd=(vd,s0,th,apref,bpref,δdrv)\theta_d=(v_d,s_0,t_h,a_{\mathrm{pref}},b_{\mathrm{pref}},\delta_{\mathrm{drv}}) specifies the reference speed, standstill spacing, time headway, acceleration and braking magnitudes, and model exponent. Both recommended and executed accelerations belong to the finite set R={α1,…,αK}⊂R\mathcal{R}=\{\alpha_1,\ldots,\alpha_K\}\subset\mathbb{R}, where α1<⋯<αK\alpha_1<\cdots<\alpha_K.

Under the proposed framework, imperfect driver compliance is modelled by the unknown compliance transition matrix PP, and historical responses are collected as described in § 2.1.

Following the cost structure in Lot et al. [13], the driving loss is evaluated at the predicted one-step state:

ℓ(a,x)=δdrv2(vavd−1)2+([a]+apref)2+([−a]+bpref)2+γ(va)(sa/sd,a−1)2(sa/sd,a)2+1,(15)\ell(a,x)=\delta_{\mathrm{drv}}^{2}\left(\frac{v_a}{v_d}-1\right)^2+\left(\frac{[a]_+}{a_{\mathrm{pref}}}\right)^2+\left(\frac{[-a]_+}{b_{\mathrm{pref}}}\right)^2+\gamma(v_a)\frac{(s_a/s_{d,a}-1)^2}{(s_a/s_{d,a})^2+1}, \tag*{(15)}

where [z]+=max⁡{z,0}[z]_+=\max\{z,0\}, sd,a=s0+thvas_{d,a}=s_0+t_hv_a, and γ(v)=8[(v/vd)δdrv−1]2\gamma(v)=8[(v/v_d)^{\delta_{\mathrm{drv}}}-1]^2. Assuming constant leading vehicle speed and ego acceleration over Δt\Delta t, the predicted speed and spacing are va=ve+aΔtv_a=v_e+a\Delta t and sa=s+Δt(vl−ve)−12a(Δt)2s_a=s+\Delta t(v_l-v_e)-\frac{1}{2}a(\Delta t)^2. Further modelling details are given in Lot et al. [13]. The recommendation objective is the expected loss J(r)=∑k=1Kℓ(αk,x)P(αk∣r,x)J(r)=\sum_{k=1}^{K}\ell(\alpha_k,x)P(\alpha_k\mid r,x) as in (1). The optimal recommendation therefore depends on the driver’s response.

For the scalar action set, the privacy channel in (6) can be computed using the standard normal cumulative distribution function Φ\Phi. Let di=(αi+αi+1)/2d_i=(\alpha_i+\alpha_{i+1})/2 for i=1,…,K−1i=1,\ldots,K-1, with d0=−∞d_0=-\infty and dK=+∞d_K=+\infty. For σ>0\sigma>0, the channel entries are computed as

[Wσ]kl=Φ(dk−αlσ)−Φ(dk−1−αlσ),k,l=1,…,K.(16)[W_{\sigma}]_{kl}=\Phi\left(\frac{d_k-\alpha_l}{\sigma}\right)-\Phi\left(\frac{d_{k-1}-\alpha_l}{\sigma}\right),\qquad k,l=1,\ldots,K. \tag*{(16)}

The ADAS evaluates the loss vector ℓ=[ℓ(α1,x),…,ℓ(αK,x)]⊤\ell= [\ell(\alpha_1, x), \ldots, \ell(\alpha_K, x)]^{\top} and obtains the debiased loss vector by solving Wσ⊤ℓ~σ=ℓW_\sigma^{\top}\tilde{\ell}_\sigma= \ell. Algorithm 1 then learns a recommendation using perturbed actions sampled from the historical dataset, without knowledge of PP.

Simulation Setup and Results

The simulations consider the fixed traffic regime ve=vl=23v_e = v_l = 23 m/s, s=35s = 35 m, with vd=30v_d = 30 m/s, s0=2s_0 = 2 m, th=1.3t_h = 1.3 s, apref=2a_{\mathrm{pref}} = 2 m/s2^2, bpref=3b_{\mathrm{pref}} = 3 m/s2^2, δdrv=4\delta_{\mathrm{drv}} = 4, and Δt=1\Delta t = 1 s. The candidate acceleration set is R={−1,−0.5,0,0.5,1}\mathcal{R} = \{-1, -0.5, 0, 0.5, 1\} m/s2^2. Then equation (15) gives the corresponding loss vector ℓ=[1.2931,1.0547,0.8858,0.8203,0.8921]⊤\ell= [1.2931, 1.0547, 0.8858, 0.8203, 0.8921]^{\top}.

To examine the effect of compliance, the following transition matrices are considered:

Pbase=(0.4500.3850.0550.3850.3850.0550.4500.0550.0550.0550.0550.0550.4500.0550.0550.0550.0550.0550.4500.0550.3850.0550.3850.0550.450),P(ψ)=ψI+1−ψ0.55(Pbase−0.45I),P_{\mathrm{base}} = \begin{pmatrix} 0.450 & 0.385 & 0.055 & 0.385 & 0.385 \\ 0.055 & 0.450 & 0.055 & 0.055 & 0.055 \\ 0.055 & 0.055 & 0.450 & 0.055 & 0.055 \\ 0.055 & 0.055 & 0.055 & 0.450 & 0.055 \\ 0.385 & 0.055 & 0.385 & 0.055 & 0.450 \end{pmatrix}, \qquad P(\psi) = \psi I + \frac{1-\psi}{0.55}(P_{\mathrm{base}} - 0.45I),

where ψ∈Ψ={0.45,0.65,0.80,0.90}\psi\in\Psi= \{0.45, 0.65, 0.80, 0.90\} is the compliance probability and P(0.45)=PbaseP(0.45) = P_{\mathrm{base}}. For each ψ\psi and αi\alpha_i, a synthetic historical dataset DiD_i of Ni=3,200,000N_i = 3{,}200{,}000 records is constructed with action frequencies matching the ii-th column of the associated matrix P(ψ)P(\psi). Algorithm 1 is evaluated with T=100T = 100, M=60M = 60, h=0.55h = 0.55, ρ=0.25\rho= 0.25, δc=0.05\delta_c = 0.05, and candidate Gaussian noise standard deviations σ∈Σ={0.60,0.65,0.70,0.75,0.80}\sigma\in\Sigma= \{0.60, 0.65, 0.70, 0.75, 0.80\}. Taking δ0=0.1\delta_0 = 0.1, (13) yields max⁡iδi,T′≤1.875×10−4\max_i \delta'_{i,T} \le1.875 \times10^{-4}. Each simulation configuration is averaged over 100 independent Monte Carlo runs. Figure 2, Figure 3 summarise the numerical results.

Effectiveness of Algorithm 1 under imperfect human compliance and privacy noise

Figure 2. (a) Compliance-aware vs. unaware (b) Effect of privacy noise

Figure 2: Effectiveness of Algorithm 1 under imperfect human compliance and privacy noise.

Joint effects of compliance-privacy interplay and prior action-space screening

Figure 3. (a) Interplay between compliance sharpness and privacy noise (b) Known vs. unknown κˉ\bar{\kappa}

Figure 3: Joint effects of compliance-privacy interplay and prior action-space screening.

Figure 2(a) compares the mean terminal regret of Algorithm 1 at σ=0.60\sigma= 0.60 with the compliance-unaware baseline r0=arg min⁡r∈Rℓ(r,x)=0.5r_0 = \operatorname*{arg\,min}_{r \in\mathcal{R}} \ell(r, x) = 0.5 m/s2^2 across all ψ∈Ψ\psi\in\Psi. Since r0r_0 is computed directly from ℓ(r,x)\ell(r, x) without accessing historical logs, it is unaffected by noise. For Algorithm 1, the corresponding realised privacy losses max⁡iεi,T′\max_i \varepsilon'_{i,T} are 15.5926, 14.2066, 13.1671, and 14.5531, respectively. These confirm the effectiveness of Algorithm 1 under RLDP requirements. Figure 2(b) illustrates the impact of the privacy noise σ\sigma on recommendation performance and privacy protection under ψ=0.45\psi= 0.45. Shaded bands represent the pointwise 95% confidence intervals across 100 Monte Carlo runs. Across Σ\Sigma, the corresponding realised privacy losses max⁡iεi,T′\max_i \varepsilon'_{i,T} are 15.5926, 4.8344, 1.8576, 0.8396, and 0.4511, respectively. Notably, increasing σ\sigma beyond 0.70 yields diminishing marginal reductions in max⁡iεi,T′\max_i \varepsilon'_{i,T} at the expense of a sharp rise in STS_T. This reflects the worsening conditioning of WσW_\sigma at high noise levels, which inflates the debiased loss span D~σ\widetilde{D}_\sigma and suggests the existence of a σ\sigma for balancing privacy protection and learning performance.

Figure 3(a) shows terminal regret and optimal recommendation identification rates across ψ∈Ψ\psi\in\Psi and σ∈Σ\sigma\in\Sigma, with 95% Student-tt and Wilson intervals, respectively. Under moderate noise, Algorithm 1 achieves effective privacy protection alongside high identification accuracy and low STS_T. Interestingly, a higher compliance rate ψ\psi may make the optimal recommendation harder to identify, yet simultaneously reduce the cost of misidentification. This occurs because certain compliance distributions flatten J(r)J(r) near the optimum. For instance, at ψ=0.80\psi= 0.80, J(r)J(r) evaluates to 1.215, 1.077, 0.897, 0.894, and 0.950 for r∈{−1,−0.5,0,0.5,1}r \in\{-1, -0.5, 0, 0.5, 1\}, respectively, yielding a marginal optimality gap between J(0)J(0) and J(0.5)J(0.5). This narrow gap makes exact best-recommendation identification difficult from finite privatised samples, thereby reducing identification accuracy. Figure 3(b) compares the simple regret StS_t at σ=0.80\sigma= 0.80 with and without a known non-compliance bound κˉ\bar{\kappa}. Without prior knowledge of κˉ\bar{\kappa}, Algorithm 1 searches the full action set R\mathcal{R}. Given κˉ=1−ψ\bar{\kappa} = 1-\psi, the screening rule in § 4.2 reduces the candidate set to A={0.5}\mathcal{A} = \{0.5\}, {0,0.5,1}\{0, 0.5, 1\}, and {−0.5,0,0.5,1} m/s2\{-0.5, 0, 0.5, 1\}\ \mathrm{m/s^2} for ψ=0.90\psi= 0.90, 0.800.80, and 0.650.65, respectively (For ψ=0.45\psi= 0.45, A=R\mathcal{A} = \mathbb{R}). Restricting Algorithm 1 to the screened set A\mathcal{A} eliminates redundant exploration and consequently improves learning efficiency.

Conclusion

This paper developed a human-in-the-loop recommendation learning framework under imperfect human compliance. The analysis established privacy and simple regret guarantees and showed how prior compliance information can support screening before private data access. In a car-following simulation, the algorithm achieved low regret across the tested compliance distributions. The framework provides a starting point for studying more general recommendation frameworks with complex human behaviour, evolving physical dynamics and safety constraints.

Acknowledgments

This work was supported by Engineering and Physical Sciences Research Council (EPSRC) of UK Research and Innovation (UKRI) under Grant EP/W524335/1.

References

  1. [1]Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
  2. [2]Anuradha M. Annaswamy, Pramod P. Khargonekar, Sarah K. Spurgeon, et al. Cyber-physical-human systems: fundamentals and applications. John Wiley & Sons, 2023.
  3. [3]Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. Advances in neural information processing systems, 31, 2018.arxiv.org/abs/1807.01647
  4. [4]Heeseung Bang, Jung-Hoon Cho, Cathy Wu, and Andreas A Mal ikopoulos. Route recommendations for traffic management under learned partial driver compliance. In 2026 American Control Conference (ACC), pages 4138–4143. IEEE, 2026.arxiv.org/abs/2504.02993
  5. [5]Guido Cavraro, Andrey Bernstein, and Emiliano Dall’Anese. Demand response under stochastic, price-dependent user behavior. IEEE Control Systems Letters, 2026.
  6. [6]Jorge Cortés, Geir E Dullerud, Shuo Han, Jerome Le Ny, Sayan Mitra, and George J Pappas. Differential privacy in control and network systems. In 2016 IEEE 55th Conference on Decision and Control (CDC), pages 4252–4272. IEEE, 2016.DOI
  7. [7]Aditya Dave, Heeseung Bang, and Andreas A Malikopoulos. A framework for effective ai recommendations in cyber-physical-human systems. IEEE control systems letters, 8: 1379–1384, 2024.DOI
  8. [8]Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3–4):211–407, 2014.
  9. [9]Julien Grand-Clément and Jean Pauphilet. The best decisions are not the best advice: Making adherence-aware recommendations. Management Science, 72(1):667–692, 2024.
  10. [10]Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American statistical association, 58(301):13–30, 1963.
  11. [11]Nathan Kallus. Instrument-armed bandits. In Proceedings of the 29th International Conference on Algorithmic Learning Theory (ALT), pages 529–546. PMLR, 2018.arxiv.org/abs/1705.07377
  12. [12]Jerome Le Ny and George J Pappas. Differentially private filtering. IEEE Transactions on Automatic Control, 59(2):341–354, 2013.
  13. [13]Roberto Lot, James Fleming, Boli Chen, and Simos Evangelou. Eco-driving optimal control for electric vehicles with driver preferences. Transportation Engineering, 19:100302, 2025.DOI
  14. [14]Chouki Sentouh, Anh-Tu Nguyen, Mohamed Amir Benlou cif, and Jean-Christophe P opieul. Driver-automation cooperation oriented approach for shared control of lane keeping assist systems. IEEE Transactions on Control Systems Technology, 27(5):1962–1978, 2018.DOI
  15. [15]Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: no regret and experimental design. In Proceedings of the 27th International Conference on International Conference on Machine Learning, page 1015–1022, 2010.DOI
  16. [16]Kai Zheng, Tianle Cai, Weiran Huang, Zhenguo Li, and Liwei Wang. Locally differentially private (contextual) bandits learning. Advances in Neural Information Processing Systems, 33:12300–12310, 2020.arxiv.org/abs/2006.00701

Paper details

vlnc:W_q2zhc5vb
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents