Prior-Free Adaptation in Improving Bandits: Free without Noise, Costly under Noise

Improving bandits model decision problems in which rewards increase with repeated investment in an arm while exhibiting diminishing returns. Existing guarantees rely on prior knowledge of problem-dependent quantities such as reward scale, a lower-envelope parameter, or the horizon. We ask whether such prior information is fundamentally necessary. Our first result shows that unknown scale is essentially free. We remove the logarithmic overhead in previous scale-oblivious guarantees and obtain the optimal all-horizon competitive ratio $\Theta (\sqrt{k}+k/T)$ without knowing the reward scale. More generally, in the noiseless setting, a single anytime algorithm simultaneously adapts to unknown scale, unknown lower-envelope parameter $\beta$, and unknown horizon, achieving the optimal ratio $\Theta (k^{\beta /(1+\beta )}+k/T)$ for every $\beta \in (0,1]$ whose lower-envelope condition holds for an optimal arm. Thus, the price of prior-free adaptation is constant. We then show that this picture changes under bounded multiplicative noise, with observations fixed by an oblivious adversary. Unknown scale alone remains essentially free, but simultaneously adapting to both scale and $\beta$ incurs a growing cost. For any fixed $\epsilon \in (0,1/2]$, we establish a structural asymptotic lower bound of order ${\Omega }_{\epsilon }(\sqrt{\log k/\log \log k})$ on the uniform price of adaptation, and give a matching algorithm achieving $O_{\epsilon }(\sqrt{\log k/\log \log k})$. The uniform price is the minimax loss relative to $k^{\beta /(1+\beta )}$ over $\beta$, instances, noise tables, and horizons $T\ge 16k$, among algorithms knowing neither scale nor $\beta$. Knowing either the scale or $\beta$ alone restores a constant price. Together, these results reveal a sharp separation between noiseless and noisy improving bandits. Prior-free adaptation is possible at constant cost without noise, while multiplicative noise creates a growing multiscale adaptation cost when scale and envelope information are unknown.