Direct Contextual UCB under Exact Cauchy Noise

Contextual bandits whose reward noise is so heavy-tailed that the mean does not exist break the usual pseudo-regret benchmark; we study exact symmetric Cauchy noise, targeting latent location regret. We analyze Direct-Cauchy-UCB, a one-pass arm-local projected gradient update driven by the Cauchy likelihood score, with optimism from the current iterate, and $\mathcal{O}(d)$ state per arm. Under bounded parameters, bounded contexts and directional excitation — every direction excited at every step—it attains high-probability location regret $\tilde{\mathcal{O}}(K\log T+\sqrt{KT\log (KT/\delta )})$. Our lower bound of order $\sqrt{KT}$ matches this up to logarithmic factors once the horizon is large enough. The same update keeps that rate under a weaker windowed persistent-excitation assumption, covering deterministic adversarial context designs. Without any excitation assumption, an ellipsoidal variant is sublinear at $\tilde{\mathcal{O}}(\sqrt{dK}{T}^{3/4})$ with $\mathcal{O}(d^2)$ per-arm state. Beyond exact Cauchy noise, a sign (median-score) variant handles symmetric heavy tails at the same rate, with no moment assumption, given a known lower bound on the noise law's slope at its median. Bounded per-arm deviations of size $\rho$ from Cauchy cost the exact-score policy an additive $O(\rho T)$, against a floor $\Omega (\rho T/\sqrt{d})$ proved for that class. On synthetic exact-Cauchy environments our policy attains the lowest location regret among a strengthened suite of robust baselines at low and moderate noise scales.