Heavy-tailed bandit algorithms attain optimal regret when given a finite moment order and its bound. Without either parameter, optimal adaptation is impossible unless one restricts the reward distributions. What can be achieved under the moment condition alone has remained open. We give a sharp answer in the form of a Pareto frontier. Our algorithm takes only an exploration exponent $\rho\in(0,1)$. It combines deterministic forced exploration with a median-of-means empirical leader and uses neither the moment order, its bound, nor a tail-sign condition. If the unknown rewards have $(1+\epsilon)$th absolute moments bounded by $u$, its worst-case regret is, up to explicit arm factors and an arbitrarily slow factor, $u^{1/(1+\epsilon)} T^{1-\rho\epsilon/(1+\epsilon)},$ while its regret on every fixed instance is $O(T^\rho)$. A matching lower bound shows that improving either polynomial exponent worsens the other. Most notably, every fixed $\rho\leq2/3$ attains this frontier simultaneously for all $\epsilon\in(0,1]$. Thus at any point on this common segment, unknown tail order has no further polynomial price beyond unknown scale. This answers the assumption-free rate question posed at COLT 2025 on the maximal common segment and gives the first matching algorithm for the unknown-scale lower tradeoff.
Keywords: heavy-tailed bandits, adaptation, moment assumptions, regret, median-of-means, multi-armed bandits