Locally Minimax Pseudo-Variance Adaptive Contextual Bandits for Heavy-Tailed Pareto Payoffs

Contextual bandits with heavy-tailed payoffs typically rely on estimators designed to be robust to outliers. However, for certain polynomial-tailed distributions, including the Pareto distribution, outliers cannot simply be discarded, as they carry essential information about the reward distribution. We instead retain every observation, mapping rewards into a score space and developing a likelihood-based online Newton estimator and a converted estimator that has a self-normalized confidence ellipsoid. Building on this estimator, we propose a computationally efficient method that performs boundary-safe optimism directly in score space, with an exact Pareto identity inversely mapping the estimated score back into the mean reward for regret computation. This construction yields a pseudo-variance-adaptive regret bound that remains finite even in the infinite-variance regime, with a leading-order scale matching that of an explicit local minimax lower bound up to logarithmic factors. Numerical experiments validate that the proposed algorithm attains the lowest pseudo-regret in all controlled settings and remains competitive on Pareto distributed data.