Learning When to Trust in Contextual Social Bandits
March 09, 2026
Abstract
Robust reinforcement learning typically assumes that feedback sources are either globally trustworthy or corrupted within a fixed global budget. We identify a more subtle failure mode that escapes this dichotomy, which we call Contextual Sycophancy. In this failure, evaluators are truthful in benign contexts but systematically biased in critical ones, so that no single evaluator is reliable everywhere and the corrupt evaluators may form a majority in the contexts that matter. Our first result is an information-theoretic lower bound. We exhibit two problem instances that induce identical social-feedback distributions yet have disjoint optimal actions, proving that any algorithm relying on social feedback alone (including any robust aggregator, regardless of breakdown point) incurs \(\Omega(T)\) latent regret. This shows that breaking contextual sycophancy is impossible without having some information. We then show that a sparse stream of ground-truth audits, available with probability \(p_{\mathrm{aud}}\), is sufficient. We propose , which learns a per-evaluator contextual trust boundary from audits and re-weights feedback accordingly, and we prove a high-probability latent-regret bound of \(\tilde{\mathcal{O}}\!\big(\sqrt{T\,d_{VC}/p_{\mathrm{aud}}} + d\sqrt{T} + \epsilon_{\mathrm{tol}}T\big)\), where \(d_{VC}\) is the complexity of the adversary’s bias strategy. The audit-dependence \(1/\sqrt{p_{\mathrm{aud}}}\) matches the information-theoretic necessity of audits. Empirically, recovers the ground truth when \(80\%\) of the social layer is adversarial, a regime in which median- and mean-based robust baselines fail.
1 Introduction↩︎
The alignment of AI systems has largely transitioned from a problem of specification (defining explicit reward functions) to one of adjudication, in which agents learn from aggregated human feedback [1]. This shift was driven by the difficulty of specifying complex goals without inducing reward hacking [2], and Reinforcement Learning from Human Feedback (RLHF) [3], [4] has become the de facto standard for steering large language models [5].
The paradigm though rests on a fragile assumption: that the feedback layer is, on average, reliable. Empirical work challenges this, documenting annotator disagreement, dependence on subjective preference, and inconsistent thresholds for “helpfulness” and “harmfulness” [6]. More pointedly, evaluators exhibit sycophancy, which is a tendency to agree with the user’s stated beliefs rather than report objective truth [7]–[9], which corrupts the feedback distribution in a structured, belief-correlated way. When evaluators are systematically biased, standard aggregation fails to recover the latent ground truth [10]. Robust RL has developed tools for adversarial corruption [11], [12], but these adopt a global corruption model. In this model, evaluators are universally good, universally bad, or corrupt within a fixed global budget (call it \(C\)).
We argue that real-world bias is contextual, and that the global model is therefore the wrong abstraction. An evaluator may answer objective questions (e.g., arithmetic, context A) honestly while strategically agreeing with a user’s prior on contested topics (e.g., politics, context B). We call this the “Jekyll & Hyde”1 problem. Under such contextual corruption, an agent that estimates a single global trust score per source may suffer what we term Contextual Objective Decoupling (COD). In COD, agent’s learned policy decouples from the ground truth precisely in the regions where the adversary dominates, while appearing well-calibrated on average.
A natural hope is that robust aggregation (taking a median or mean across evaluators) rescues the agent. Our first contribution shows this hope is unfounded for fundamental, not merely algorithmic, reasons. When the corrupt evaluators form a contextual majority, the observable feedback distribution is indistinguishable from an instance in which the honest minority and corrupt majority swap roles, yet the two instances disagree on the optimal action. No statistic of the social feedback can separate them. Robustness to corruption below a breakdown point does not help, because the corruption here exceeds any such point in the contexts that matter.
This impossibility result reframes the design question. The agent cannot ask only “who do I trust?”; it must acquire side information about ground truth and learn “when do I trust each source?”. We formalize the side information as sparse verification audits: with small probability \(p_{\mathrm{aud}}\) per round, the agent obtains a ground-truth probe (inspired by the scalable-oversight viewpoint of Constitutional AI [13]). We then propose (Contextual Epistemic Source Alignment–Linear Upper Confidence Bound), which learns a high-dimensional trust boundary per evaluator from these audits and re-weights feedback within a confidence-ellipsoid estimator.
Contributions.
An impossibility result for social feedback (Section 3). We formalize the Contextual Social Bandit and prove the Information-Theoretic Decoupling Theorem (Theorem 1). Two instances with identical social-feedback laws but disjoint optimal actions force \(\Omega(T)\) latent regret on any audit-free algorithm, robust aggregators included. This isolates audits as a necessary resource, not a design convenience.
A semi-supervised algorithm (Section 4). We cast contextual trust as semi-supervised learning: dense social feedback is potentially corrupt, while sparse audits are clean. maintains a per-evaluator contextual trust model updated only on audit rounds, and a trust-weighted ridge estimator updated every round.
Matching upper bound (Section 5). We prove (Theorem 2) a latent-regret bound \(\tilde{\mathcal{O}}(\sqrt{T\,d_{VC}/p_{\mathrm{aud}}} + d\sqrt{T} + \epsilon_{\mathrm{tol}}T)\). The audit term arises from a uniform-convergence argument over the trust hypothesis class and is summed over the online horizon without assuming the trust- and reward-learning phases are independent. The \(1/\sqrt{p_{\mathrm{aud}}}\) dependence is consistent with the audit necessity established by Theorem 1.
Empirical robustness (Section 6). recovers the ground truth when \(80\%\) of evaluators are adversarial (in the presence of audits). We show that median-based robust aggregation is worse than the naive baseline here, empirically confirming Theorem 1.
2 Related Work↩︎
Contextual and linear bandits. Linear bandits established exploration with regret guarantees [14]–[16], with extensions to Thompson Sampling [17], generalized linear models [18], [19], and neural variants [20], [21]. LinUCB [16], [22] uses optimism via a confidence ellipsoid around \(\hat{\theta}_t\) and achieves \(\tilde{O}(d\sqrt T)\) regret. We retain this estimator but drop its implicit assumption that observed rewards are unbiased, embedding learned trust weights inside the ellipsoid.
Robust and adversarial bandits. Learning with corrupted rewards has been studied extensively. [11] and [23] give algorithms robust to a global corruption budget \(C\); in the contextual-linear setting [12] and [24] obtain regret degrading as \(O(C\sqrt T)\), and [25] use uncertainty weighting to down-weight corrupt data. All assume the clean data is, in aggregate, recoverable (typically that clean points are a majority). Our impossibility result (Theorem 1) shows this is exactly what fails under a contextual hostile majority, and it does so information-theoretically: no estimator on the social feedback can succeed, so the gap is not closed by a better aggregator but by audits.
Sycophancy and truth discovery. Sycophancy in LLMs was characterized by [7], [8] and [9], with origins in RLHF dynamics and reward gaming; mitigations via synthetic data [26], [27] generally lack guarantees. Classical truth discovery, e.g.Dawid–Skene [28]–[30], estimates per-annotator confusion matrices but assumes static reliability and cannot represent context-dependent “Jekyll & Hyde” evaluators.
Active learning and label-efficient bandits. Our use of sparse audits connects to active learning, where the generalization error of a classifier scales with the VC dimension and the number of labeled examples [16]. We import this machinery to bound how often an imperfect trust boundary admits adversarial feedback, which is what couples label sparsity to regret.
3 Problem Formulation↩︎
We define the Contextual Social Bandit as a tuple \(\mathcal{B} = \langle \mathcal{X}, \mathcal{A}, \mathcal{E}, R^*, \mathcal{P}_{\mathrm{soc}} \rangle\):
\(\mathcal{X} \subset \mathbb{R}^d\) is the set of observable contexts, assumed bounded in Euclidean norm: there is a constant \(L>0\) such that \(\|x\|_2 \le L\) for all \(x \in \mathcal{X}\).
\(\mathcal{A}\) is the finite set of \(K\) arms (actions).
\(\mathcal{E} = \{e_1, \dots, e_M\}\) is a set of \(M\) evaluators (annotators or AI feedback models).
\(R^*: \mathcal{X} \times \mathcal{A} \to [0,1]\) is the unknown ground-truth reward (the latent objective).
\(\mathcal{P}_{\mathrm{soc}}\) is the social feedback distribution. At time \(t\) the agent receives \(\mathbf{y}_t \in \mathbb{R}^M\) drawn from \(\mathcal{P}_{\mathrm{soc}}(\cdot \mid x_t, a_t)\), where \(y_{t,m}\) is the noisy, possibly biased score of \(e_m\).
The agent seeks a policy \(\pi:\mathcal{X} \to \mathcal{A}\) minimizing latent regret w.r.t.\(R^*\), while observing only samples from \(\mathcal{P}_{\mathrm{soc}}\) plus sparse audits defined below.
Definition 1 (Context-dependent bias). The feedback of evaluator \(m\) is \(y_{t,m} = R^*(x_t, a_t) + \beta_m(x_t, a_t) + \eta_{t,m},\) where \(\eta_{t,m}\) is zero-mean \(\sigma\)-sub-Gaussian noise and \(\beta_m:\mathcal{X}\times\mathcal{A}\to\mathbb{R}\) is a deterministic bias function. Unlike global-corruption models where \(\beta_m \in \{0,\infty\}\), here \(\beta_m\) is continuous and state-dependent, capturing (i) sycophancy, \(\beta_m(x,a)\) correlated with the prevailing consensus rather than \(R^*\), and (ii) contextual incompetence, \(\beta_m(x,a)\) large only where \(e_m\) lacks expertise.
Definition 2 (Trust function and audits). The binary trust function \(\tau^*_m:\mathcal{X}\to\{0,1\}\) marks contexts where \(e_m\) is reliable up to tolerance \(\epsilon_{\mathrm{tol}}\): \(\tau^*_m(x) = \mathbb{I}\!\left( \sup_{a\in\mathcal{A}} |\beta_m(x,a)| \le \epsilon_{\mathrm{tol}} \right).\) This partitions \(\mathcal{X}\) into a trust region \(\mathcal{T}_m=\{x:\tau^*_m(x)=1\}\) and an untrustworthy region \(\mathcal{U}_m\), with the difficulty of learning \(\tau^*_m\) governed by the complexity of the boundary \(\partial\mathcal{T}_m\). An audit at round \(t\) returns a ground-truth probe \(z_t \in \{0,1\}\) indicating whether \(a_t\) is good under \(R^*\); audits occur independently with probability \(p_{\mathrm{aud}}\).
3.1 The Inevitability of Decoupling↩︎
We first show that the social feedback is fundamentally insufficient. The result is information-theoretic: rather than analyzing a specific algorithm, we construct two instances whose observable feedback laws coincide while their optimal actions differ, so that no audit-free algorithm (robust aggregators included) can do better than chance in the disputed region.
Theorem 1 (Information-Theoretic Decoupling). Fix a horizon \(T\), an honest fraction \(\alpha < 1/2\), and a decoupling region \(\mathcal{X}_{\mathrm{dec}}\subset\mathcal{X}\) with \(\mu(\mathcal{X}_{\mathrm{dec}})=\mu_{\mathrm{dec}}>0\) under the i.i.d.context distribution. There exist two Contextual Social Bandit instances \(\mathcal{B}_0,\mathcal{B}_1\), differing only in the ground-truth reward on \(\mathcal{X}_{\mathrm{dec}}\), such that:
For every policy, the law of the social-feedback sequence \(\{\mathbf{y}_t\}_{t\le T}\) is identical under \(\mathcal{B}_0\) and \(\mathcal{B}_1\);
On \(\mathcal{X}_{\mathrm{dec}}\) the optimal actions are disjoint, \(\pi^*_0(x)\neq\pi^*_1(x)\), with suboptimality gap at least \(\Delta_{\min}>0\).
Consequently, any algorithm that does not query audits has worst-case latent regret \(\max_{b\in\{0,1\}} \mathcal{R}^{\mathrm{latent}}_T(\mathfrak{A};\mathcal{B}_b) \;\ge\; \tfrac{1}{4}\,\Delta_{\min}\,\mu_{\mathrm{dec}}\,T.\) Moreover, distinguishing \(\mathcal{B}_0\) from \(\mathcal{B}_1\) to constant confidence requires \(\Omega(1/\mu_{\mathrm{dec}})\) audits inside \(\mathcal{X}_{\mathrm{dec}}\), i.e.\(\Omega(1/(p_{\mathrm{aud}}\mu_{\mathrm{dec}}))\) rounds in expectation.
Proof. We construct two instances \(\mathcal{B}_0,\mathcal{B}_1\) that are observationally identical under social feedback but have disjoint optima on \(\mathcal{X}_{\mathrm{dec}}\), then apply a two-point (Le Cam) argument.
3.1.0.1 Construction.
Outside \(\mathcal{X}_{\mathrm{dec}}\) the instances are identical and irrelevant to the bound. Inside \(\mathcal{X}_{\mathrm{dec}}\), restrict to two actions \(\{a_1,a_2\}\). Let \(b\in\{0,1\}\) index the instance and set the ground truth so that \[R^*_b(x,a_1)=\tfrac12+(-1)^b\tfrac{\Delta_{\min}}{2},\qquad R^*_b(x,a_2)=\tfrac12-(-1)^b\tfrac{\Delta_{\min}}{2},\qquad x\in\mathcal{X}_{\mathrm{dec}},\] so \(\pi^*_0(x)=a_1\) and \(\pi^*_1(x)=a_2\) on \(\mathcal{X}_{\mathrm{dec}}\), with gap \(\Delta_{\min}\) (property (ii)).
Draw a labeling \(\Pi\) uniformly at random that designates an \(\alpha\)-fraction of the \(M\) evaluators as honest (\(H\)) and the remaining \((1-\alpha)\)-fraction as adversarial (\(A\)), with \(\alpha<1/2\). Honest evaluators report \(y_{t,m}=R^*_b(x_t,a_t)+\eta_{t,m}\). Adversarial evaluators report a fixed bias profile that is independent of \(b\): \[y_{t,m}=g(x_t,a_t)+\eta_{t,m},\qquad m\in A,\] where \(g\) is chosen so that, conditioned on \(\Pi\), the full feedback vector has the same law under \(b=0\) and \(b=1\) after marginalizing over \(\Pi\). Concretely, take \(g(x,a_1)=\tfrac12-\tfrac{\Delta_{\min}}{2}\) and \(g(x,a_2)=\tfrac12+\tfrac{\Delta_{\min}}{2}\); then under either instance the multiset of reported means over evaluators is \(\{\)an \(\alpha\)-fraction at \(R^*_b\), a \((1-\alpha)\)-fraction at \(g\}\), and because the honest/adversarial assignment \(\Pi\) is unknown and uniformly random, the marginal law of each coordinate \(y_{t,m}\) is the mixture \(\alpha\,\mathcal{N}(R^*_b,\sigma^2)+(1-\alpha)\,\mathcal{N}(g,\sigma^2)\). Reflecting \(R^*_b\) and \(g\) jointly under \(b\mapsto1-b\) leaves this mixture invariant. Hence the per-coordinate, and therefore the joint, feedback law is identical under \(\mathcal{B}_0\) and \(\mathcal{B}_1\) for every policy (property (i)).
3.1.0.2 Le Cam bound.
Let \(\mathfrak{A}\) be any audit-free algorithm and let \(P_b\) denote the law of its interaction transcript under \(\mathcal{B}_b\). Since the only \(b\)-dependent observations are the social feedbacks, and these have identical law, \(P_0=P_1\) as distributions over transcripts. For any context \(x\in\mathcal{X}_{\mathrm{dec}}\), the event \(\{a_t=a_1\}\) has the same probability under both instances; writing \(q=\Pr_{P}[a_t=a_1\mid x]\), the per-round latent regret is \((1-q)\Delta_{\min}\) on \(\mathcal{B}_0\) and \(q\Delta_{\min}\) on \(\mathcal{B}_1\), so \[\max_b \mathbb{E}[\text{per-round regret}\mid x] \;\ge\; \tfrac12\big[(1-q)+q\big]\Delta_{\min} \;=\; \tfrac12\Delta_{\min} \cdot \tfrac12 \;=\;\tfrac14\Delta_{\min},\] where the second inequality uses \(\max\{u,v\}\ge\tfrac12(u+v)\) and the worst case over \(q\) gives the factor \(\tfrac12\) when balancing the two instances. Summing over the \(\approx\mu_{\mathrm{dec}}T\) rounds with \(x_t\in\mathcal{X}_{\mathrm{dec}}\) (i.i.d.contexts) yields \[\max_b \mathcal{R}^{\mathrm{latent}}_T(\mathfrak{A};\mathcal{B}_b)\;\ge\;\tfrac14\Delta_{\min}\mu_{\mathrm{dec}}T.\]
3.1.0.3 Audit complexity.
Now allow audits. The audit at round \(t\) returns \(z_t=\mathbb{I}(a_t\text{ optimal})\), whose distribution differs across instances: for a fixed action the Bernoulli parameter differs by \(\Delta_{\min}\). By Pinsker’s inequality, distinguishing \(P_0\) from \(P_1\) with the audit channel to constant total-variation distance requires \(\mathrm{KL}(P_0\|P_1)=\Omega(1)\), and each audit inside \(\mathcal{X}_{\mathrm{dec}}\) contributes \(O(\Delta_{\min}^2)\) to the KL. Thus \(\Omega(1/\Delta_{\min}^2)=\Omega(1)\) informative audits are needed; since an audit lands in \(\mathcal{X}_{\mathrm{dec}}\) with probability \(p_{\mathrm{aud}}\mu_{\mathrm{dec}}\), the expected number of rounds is \(\Omega(1/(p_{\mathrm{aud}}\mu_{\mathrm{dec}}))\). ◻
3.1.0.4 Remark.
The construction uses \(\alpha<1/2\) only through the requirement that the adversarial mass dominate the mixture so reflection preserves the law; the bound is therefore tight against any aggregator, recovering Corollary 1 as the special case of consensus-following algorithms.
3.1.0.5 Interpretation.
Theorem 1 is the crux of the paper. It says contextual sycophancy is not an estimation nuisance to be filtered, but an identifiability barrier: the honest minority signal is observationally erased. Robust statistics, which presuppose clean-majority recoverability, cannot help. The only escape is external information, and the audit complexity \(\Omega(1/(p_{\mathrm{aud}}\mu_{\mathrm{dec}}))\) foreshadows the \(1/\sqrt{p_{\mathrm{aud}}}\) factor in our upper bound. We record the algorithm-specific consequence for completeness.
Corollary 1 (Aggregation collapse). Any algorithm that selects actions to be optimal under an aggregate \(\bar y_t=\mathrm{Agg}(\{y_{t,m}\})\), where \(\mathrm{Agg}\) has breakdown point \(\le 1-\alpha\) (e.g.mean, median, trimmed mean), incurs latent regret \(\Omega(\Delta_{\min}\mu_{\mathrm{dec}}T)\) on \(\mathcal{B}_0\) or \(\mathcal{B}_1\).
4 Methodology: ↩︎
Theorem 1 dictates the design: dense social feedback is unreliable but cheap, while sparse audits are reliable but rare. is therefore a semi-supervised procedure. It maintains, for each evaluator \(m\), a contextual trust model \(\tau_m(x)=\sigma(\theta_m^\top x)\) updated only on audit rounds, and a trust-weighted ridge estimator over the reward parameters updated every round.
Epistemic forecasting. At each round the agent predicts trust scores \(\hat{w}_{t,m}=\sigma(\theta_m^\top x_t)\in(0,1)\), the estimated probability that \(e_m\) is reliable in context \(x_t\).
Trust-weighted estimation. The reward parameters minimize the trust-weighted ridge loss over individual evaluator feedbacks, \[\mathcal{L}(\theta_a) = \sum_{\tau=1}^t \sum_{m=1}^M \hat{w}_{\tau,m}\,(y_{\tau,m} - \theta_a^\top x_\tau)^2 + \lambda \|\theta_a\|_2^2,\] so a feedback’s influence is proportional to its predicted trustworthiness, down-weighting adversarial scores before they enter the estimate.
Sparse verification audits. With probability \(p_{\mathrm{aud}}\) the agent obtains \(z_t\) and forms per-evaluator labels \(\ell_{t,m}=\mathbb{I}(y_{t,m}\approx z_t)\), then takes one SGD step on the cross-entropy loss for \(\theta_m\). Audits are the only signal that prevents the trust models from collapsing onto the majority consensus; their analysis requires that the proxy label is informative, which we state as an assumption in Section 5.
5 Theoretical Analysis↩︎
We give a high-probability latent-regret bound for . The two technical obstacles are (i) the trust classifier is trained on sparse labels and updated online, so its error rate is time-varying, and (ii) trust- and reward-learning are coupled. We handle (i) with an anytime uniform-convergence bound summed over the horizon, and (ii) by treating the rounds on which the trust model errs as adversarial corruption to a linear bandit, which removes any need to assume the two phases are independent.
5.1 Assumptions↩︎
Assumption 1 (Realizability and finite complexity). For each \(m\), \(\tau^*_m\) belongs to a hypothesis class \(\mathcal{H}\) of VC dimension \(d_{VC}\), and the trust model is fit within \(\mathcal{H}\) (e.g.linear separators, \(d_{VC}=d+1\)).
Assumption 2 (Audit fidelity). There is a margin \(\gamma_{\mathrm{aud}}>0\) such that, on an audited round, the proxy label is correct in expectation: \(\Pr[\ell_{t,m}=\tau^*_m(x_t)\mid x_t] \ge \tfrac12 + \gamma_{\mathrm{aud}}\). Thus audits identify trust up to a constant-factor inflation of the label budget.
Assumption 3 (Bias span). The expected adversarial bias vector is not orthogonal to the feature span of \(\mathcal{X}\); equivalently, undetected bias projects onto the estimable directions.
Assumption 2 is the formal price of replacing the global-trust assumption. We do not assume any evaluator is reliable everywhere, only that audits are better than random at revealing reliability. Assumption 3 ensures bias that is wrongly trusted actually harms the estimate (otherwise it is harmless and trust is irrelevant).
5.2 Consistency of Trust-Weighted Estimation↩︎
Lemma 1 (The price of distrust). Let \(\hat{\theta}_t\) be the weighted ridge estimator. A Type-I error (False Trust: \(\hat{w}\approx1\), \(\tau^*=0\)) introduces a non-vanishing bias under Assumption 3, rendering \(\hat{\theta}_t\) inconsistent and inducing linear regret. A Type-II error (False Distrust: \(\hat{w}\approx0\), \(\tau^*=1\)) leaves \(\hat{\theta}_t\) asymptotically unbiased but shrinks the effective sample size, inflating the confidence ellipsoid to yield \(\tilde{O}(d\sqrt{T/\rho})\) regret under retention rate \(\rho\).
Proof. Under the linear reward model \(y_{t,m}=x_t^\top\theta^*+\beta_{t,m}+\eta_{t,m}\), the trust-weighted ridge minimizer is \[\hat{\theta} = \Big(\textstyle\sum_t \mathbf{W}_t x_t x_t^\top + \lambda I\Big)^{-1}\sum_t \tilde{y}_t x_t,\qquad \mathbf{W}_t=\textstyle\sum_m \hat{w}_{t,m},\;\;\tilde{y}_t=\textstyle\sum_m \hat{w}_{t,m} y_{t,m}.\] Writing \(\mathbf{X}_w\) for the weight-expanded design matrix and \(\mathbf{b}_w\) for the stacked biases, \[\begin{align} \mathbb{E}[\hat{\theta}] &= (\mathbf{X}_w^\top\mathbf{X}_w+\lambda I)^{-1}\mathbf{X}_w^\top(\mathbf{X}_w\theta^*+\mathbf{b}_w)\\ &= \theta^* -\underbrace{\lambda(\mathbf{X}_w^\top\mathbf{X}_w+\lambda I)^{-1}\theta^*}_{\text{regularization bias}} +\underbrace{(\mathbf{X}_w^\top\mathbf{X}_w+\lambda I)^{-1}\textstyle\sum_{t,m}\hat{w}_{t,m}\beta_{t,m}x_t}_{\text{adversarial bias}}. \end{align}\]
Case 1 (False Trust, Type I). If \(\hat{w}_{t,m}\approx1\) while \(\beta_{t,m}\neq0\), the adversarial-bias term contains \(\sum_{t,m}\beta_{t,m}x_t\), which by Assumption 3 has a non-vanishing projection onto the column space of the design matrix. As \(T\to\infty\) the normalized term converges to a nonzero constant \(\Delta\), so \(\hat{\theta}\to\theta^*+\Delta\). A constant parameter bias produces a constant per-round suboptimality on a positive-measure set of contexts, hence linear regret.
Case 2 (False Distrust, Type II). If \(\hat{w}_{t,m}\approx0\) while \(\beta_{t,m}=0\), the adversarial-bias term vanishes identically, so \(\hat{\theta}\) is asymptotically unbiased as \(\lambda\to0\). The cost is statistical: the Gram matrix \(\mathbf{V}_t=\sum_t\mathbf{W}_t x_t x_t^\top+\lambda I\) grows at rate proportional to the retention rate \(\rho\) (the fraction of mass kept), so \(\mathbf{V}_t^{-1}\succeq \rho^{-1}\mathbf{V}_t^{\mathrm{full},-1}\) and the confidence width inflates by \(\rho^{-1/2}\). Propagating through the LinUCB regret expression yields \(\tilde{O}(d\sqrt{T/\rho})\). ◻
The asymmetry in Lemma 1 motivates a conservative trust threshold. False Trust is unrecoverable (bias), whereas False Distrust costs only variance.
5.3 Regret Bound↩︎
Theorem 2 (Latent-regret upper bound). Under Assumptions 1–3, with probability \(1-\delta\) the cumulative latent regret of satisfies \[\mathcal{R}_T^{\mathrm{latent}} \;\le\; \tilde{O}\!\left( \sqrt{\frac{T\,d_{VC}}{p_{\mathrm{aud}}}} \right) \;+\; \tilde{O}\!\left( d\sqrt{T} \right) \;+\; \epsilon_{\mathrm{tol}}\,T,\] where the \(\tilde{O}\) hides \(\mathrm{polylog}(T,1/\delta)\) and the \(\gamma_{\mathrm{aud}}^{-2}\) factor from Assumption 2.
Proof. Define the leakage indicator \(M_t=\mathbb{I}\{\exists m:\;\hat{w}_{t,m}>\epsilon_{\mathrm{tol}}\;\text{and}\;\tau^*_m(x_t)=0\}\), i.e.rounds on which an untrustworthy evaluator is trusted past tolerance. Let \(L_T=\sum_{t\le T}M_t\). We bound regret on leakage rounds by counting and on clean rounds by a corrupted-bandit analysis. The decomposition is pathwise, so no independence between the trust and bandit processes is assumed.
5.3.0.1 Step 1: Leakage rounds via anytime uniform convergence.
On an audited round the agent observes, for each \(m\), a label \(\ell_{t,m}\) which by Assumption 2 agrees with \(\tau^*_m(x_t)\) with margin \(\gamma_{\mathrm{aud}}\); standard boosting of a weak label costs a factor \(\gamma_{\mathrm{aud}}^{-2}\), which we absorb into \(\tilde{O}\). Audited contexts are i.i.d.from the context distribution (audits are independent Bernoulli(\(p_{\mathrm{aud}}\)) of the context). By round \(t\) the classifier has been trained on \(n_t\) audited samples with \(\mathbb{E}[n_t]=p_{\mathrm{aud}}t\) and, by a Chernoff bound, \(n_t\ge \tfrac12 p_{\mathrm{aud}}t\) with probability \(1-\delta/(2T)\) for \(t\ge \frac{c\log(T/\delta)}{p_{\mathrm{aud}}}\). By the VC uniform-convergence bound (Assumption 1), the trained classifier’s misclassification probability obeys, with probability \(1-\delta/(2T)\), \[\Pr_{x}\big[\hat{\tau}_m(x)\neq\tau^*_m(x)\big]\;\le\; c'\sqrt{\frac{d_{VC}\log(n_t/\delta)}{\gamma_{\mathrm{aud}}^2\,n_t}}\;=\;\tilde{O}\!\left(\sqrt{\frac{d_{VC}}{p_{\mathrm{aud}}\,t}}\right).\] A leakage round occurs only if some trusted evaluator is misclassified, so \(\Pr[M_t=1]\le \tilde{O}(\sqrt{d_{VC}/(p_{\mathrm{aud}}t)})\) (the union over \(M\) evaluators contributes a \(\log M\) absorbed into \(\tilde{O}\)). Summing and using \(\sum_{t\le T}t^{-1/2}\le 2\sqrt T\), \[\mathbb{E}[L_T]\;\le\;\sum_{t=1}^T \tilde{O}\!\left(\sqrt{\frac{d_{VC}}{p_{\mathrm{aud}}\,t}}\right)\;=\;\tilde{O}\!\left(\sqrt{\frac{T\,d_{VC}}{p_{\mathrm{aud}}}}\right),\] and a Freedman/Azuma concentration gives the same bound with high probability. Each leakage round costs at most \(1\) (rewards in \([0,1]\)), so the leakage regret is \(\tilde{O}(\sqrt{T d_{VC}/p_{\mathrm{aud}}})\).
5.3.0.2 Step 2: Clean rounds as a corrupted linear bandit.
On clean rounds (\(M_t=0\)), every trusted evaluator satisfies \(\tau^*_m(x_t)=1\), so its bias obeys \(|\beta_{t,m}|\le\epsilon_{\mathrm{tol}}\) by Definition 2. The trust-weighted target therefore equals the linear signal plus a perturbation of magnitude at most \(\epsilon_{\mathrm{tol}}\). The subsequence of clean rounds is thus an instance of stochastic linear bandits with per-round corruption \(\le\epsilon_{\mathrm{tol}}\) and total corruption \(C\le\epsilon_{\mathrm{tol}}T\). The self-normalized confidence bound of [16] holds for any predictable sequence and gives, with probability \(1-\delta/2\), \[\|\hat{\theta}_t-\theta^*\|_{\mathbf{V}_t}\le \beta_t=\sigma\sqrt{d\log\!\frac{1+TL^2/\lambda}{\delta}}+\lambda^{1/2}\|\theta^*\|.\] Combining with the corruption-robust regret decomposition (e.g.[12]), the clean-round regret is \[\mathcal{R}_{\mathrm{clean}}\le \tilde{O}(d\sqrt T)+\epsilon_{\mathrm{tol}}T.\] Because this bound is stated for an arbitrary adapted subsequence, applying it to the (random) clean set is valid without assuming the clean set is independent of the bandit estimator.
5.3.0.3 Step 3: Combine.
A union bound over Steps 1–2 gives, with probability \(1-\delta\), \[\mathcal{R}_T^{\mathrm{latent}}=\mathcal{R}_{\mathrm{leak}}+\mathcal{R}_{\mathrm{clean}}\le \tilde{O}\!\left(\sqrt{\frac{T d_{VC}}{p_{\mathrm{aud}}}}\right)+\tilde{O}(d\sqrt T)+\epsilon_{\mathrm{tol}}T. \qedhere\] ◻
5.3.0.4 Tightness.
The \(1/\sqrt{p_{\mathrm{aud}}}\) factor matches the audit-complexity lower bound of Theorem 1 up to the dependence on \(d_{VC}\) versus \(1/\mu_{\mathrm{dec}}\), so the rate in \(p_{\mathrm{aud}}\) is not improvable in general.
Proposition 3 (Sycophantic complexity). Let \(\kappa=\inf\{d_{VC}(\mathcal{H}) : \tau^*\in\mathcal{H}\}\) be the complexity of the minimal class representing the adversary’s bias strategy. Then \(\mathcal{R}_T^{\mathrm{latent}}=\tilde{O}(\sqrt{\kappa T/p_{\mathrm{aud}}})\) in the audit-dominated regime.
This substitutes \(d_{VC}=\kappa\) into Theorem 2: more elaborate lies (larger \(\kappa\)) cost more, and the cost is amplified when supervision is sparse. The matching \(1/\sqrt{p_{\mathrm{aud}}}\) rate appears in both the necessity result (Theorem 1) and the upper bound, indicating the audit dependence is not an artifact of the analysis.
6 Experiments↩︎
We evaluate in a high-dimensional Contextual Social Bandit constructed so that social consensus is structurally misaligned with ground truth. We ask: (i) Can the agent recover ground truth when \(80\%\) of evaluators are adversarial? (Robustness) (ii) Does the trust model separate honest sources from sycophants and contextual liars? (Identification) (iii) How does regret scale with dimension \(d\) and audit rate \(p_{\mathrm{aud}}\)? (Scalability and supervision cost)
We additionally position against baselines that, like it, consume the audit signal, so the comparison isolates the contribution of contextual trust modeling rather than the audits alone.
6.1 Setup: the “Hostile Majority”↩︎
We use \(d=20\), \(K=5\), \(M=10\), with an evaluator mix chosen to defeat robust aggregation:
Honest (\(20\%\)): report \(R^*(x,a)\) plus Gaussian noise.
Contextual liars (\(30\%\)): “Jekyll & Hyde” evaluators, truthful in one half-space of \(\mathbb{R}^d\) and reward-inverting in the other.
Sycophants (\(50\%\)): ignore context and report reward \(\approx 1.0\) for every action (“yes-men”).
By construction the mean, median, and majority vote are all adversarial, so any consensus-based method converges to the sycophantic objective (Corollary 1).
6.1.0.1 Baselines.
We compare against (a) Standard LinUCB; (b) Median LinUCB (robust aggregation, breakdown point \(0.5\)); (c) an Audit-Only LinUCB that ignores social feedback and learns from the \(p_{\mathrm{aud}}\) audits alone, isolating how much the dense feedback contributes once trust is modeled; and (d) an Oracle-Weighted estimator with access to \(\tau^*\), an information-theoretic ceiling. The Audit-Only and Oracle baselines are the discriminating comparisons: they share ’s audit budget, so any gap reflects the value of contextual trust modeling rather than supervision.
6.2 Breaking the Consensus Trap↩︎
Figure 3 shows cumulative latent regret. Median LinUCB performs worse than naive LinUCB: with \(50\%\) sycophants and \(30\%\) contextual liars, the median opinion is itself adversarial, and a breakdown point of \(0.5\) is insufficient once corruption is a contextual majority. This is the empirical signature of Theorem 1. (green) instead achieves sublinear regret, plateauing near \(100\), by treating trust as a learned contextual variable and re-weighting updates toward the honest \(20\%\).
6.3 The Geometry of Trust↩︎
Figure 4 visualizes the normalized trust weights. Honest evaluators are quickly identified and carry the dominant mass. Sycophants are suppressed to background level as uncorrelated with audits. Contextual liars, on the other hand, receive an intermediate, dynamically modulated weight that tracks whether the current context lies in their truthful or adversarial half-space, which is a behavior that a static trust score cannot produce.
6.4 Scalability and the Price of Supervision↩︎
Figure 5: Sensitivity analysis. (a) is consistent with the \(\tilde{O}(d\sqrt T)\) term; (b) shows a sharp improvement up to \(p_{\mathrm{aud}}\approx5\%\), consistent with the \(1/\sqrt{p_{\mathrm{aud}}}\) dependence.. a — Scalability: regret scales with dimension., b — Sensitivity: sparse supervision (\(p\approx5\%\)) suffices.
6.4.0.1 Scalability (\(d\) vs.regret).
Varying \(d\in\{10,20,50,100\}\), final regret at \(T=5{,}000\) grows with \(d\) (Figure 5 (a)), consistent with the \(\tilde{O}(d\sqrt T)\) term of Theorem 2.
6.4.0.2 Phase transition in supervision.
Figure 5 (b) shows a sharp transition: below \(p_{\mathrm{aud}}\approx1\%\) the trust boundary fails to converge; performance improves steeply to \(p_{\mathrm{aud}}\approx5\%\) and then plateaus. The location of the knee is consistent with the \(1/\sqrt{p_{\mathrm{aud}}}\) scaling, and indicates that auditing \(\approx1\) in \(20\) interactions suffices (a sharp reduction in oversight relative to fully supervised pipelines [31]).
6.5 Limitations↩︎
Our guarantees assume the trust boundary is realizable in a class of bounded VC dimension (Assumption 1), thus misspecified or non-stationary boundaries would add an approximation term we do not analyze. Assumption 2 requires audits to be informative; adversaries that corrupt the audit channel itself are out of scope. Empirically, our environment is synthetic and adversary mixtures are fixed and transfer to real annotator data and to learned (rather than linear) trust models remains open. Finally, the \(\epsilon_{\mathrm{tol}}T\) term is linear, so the method targets small-tolerance regimes; it does not promise vanishing regret when even “trusted” evaluators carry \(\Omega(1)\) bias.
7 Conclusion↩︎
We challenged the global-trust assumption in robust RL and identified Contextual Objective Decoupling as a structural failure of consensus-based learning under a contextual hostile majority. Our main message is an impossibility result: social feedback alone is information-theoretically insufficient, so robust aggregation cannot rescue the agent, and external audits are necessary. We then showed audits are also sufficient. Our proposed method, learns contextual trust boundaries and attains latent regret \(\tilde{O}(\sqrt{T d_{VC}/p_{\mathrm{aud}}}+d\sqrt T+\epsilon_{\mathrm{tol}}T)\), paying for the complexity of the adversary’s lying strategy rather than the volume of corruption, with audit dependence matching the necessity bound. Empirically, recovers ground truth where mean- and median-based baselines collapse.