  Bayesian optimisation is a powerful tool to solve expensive black-box
problems, but fails when the stationary assumption made on the objective
function is strongly violated, which is the case in particular for
ill-conditioned or discontinuous objectives. We tackle this problem by
proposing a new Bayesian optimisation framework that only considers the
ordering of variables, both in the input and output spaces, to fit a Gaussian
process in a latent space. By doing so, our approach is agnostic to the
original metrics on the original spaces. We propose two algorithms,
respectively based on an optimistic strategy and on Thompson sampling. For the
optimistic strategy we prove an optimal performance under the measure of regret
in the latent space. We illustrate the capability of our framework on several
challenging toy problems.
