Learning When to Trust in Contextual Social Bandits

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 Ω(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_{aud}, is sufficient. We propose \ESA, 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{O}!\big(\sqrt{T,d_{VC}/p_{aud}} + d\sqrt{T} + ε_{tol}T\big), where d_{VC} is the complexity of the adversary's bias strategy. The audit-dependence 1/\sqrt{p_{aud}} matches the information-theoretic necessity of audits. Empirically, \ESA\ recovers the ground truth when 80% of the social layer is adversarial, a regime in which median- and mean-based robust baselines fail.