The Cost of Parameter-Free Adaptation in Lexicographic Bandits

This investigates the fundamental statistical cost of parameter-free adaptation in lexicographic multi-objective bandits, where objectives are prioritised strictly and the learner is not given the actual trade-off parameter or any upper bound on it. The paper establishes a sharp characterisation of attainable regret exponents for two-objective Lipschitz bandits on a cube of known dimension, under the original trade-off normalisation. The resulting Pareto frontier is achieved by a two-resolution policy that preserves primary-screened cells before refining secondary optimisation, with matching lower bounds against adaptive randomised policies. Further contributions establish fractional sensitivity–time laws for two-arm bandits with an arbitrary fixed number of objectives and for finite-arm bandits with two objectives. Matching Gaussian information-theoretic converses identify the optimal polynomial dependence on the time horizon and, in the stated finite-arm regime, the number of actions. The analysis distinguishes adaptation under the original evaluation criterion from improvements obtained by changing the trade-off weights. It also identifies attainable square-root sensitivity profiles, clarifies the scope of existing results and delineates remaining open cases. Deposited materials Main research manuscript (34 pages), including mathematical proofs and technical appendices. Online Appendix 1 (v014), containing supplementary code, computational checks, numerical results, figure-generation material and reproducibility instructions. Author: Shardul Mishra, School of Computer Science and Engineering (SCOPE), Vellore Institute of Technology, India. Copyright: © 2026 Shardul Mishra. All rights reserved.