learning the relative order of elements I have a list of elements with very little information about them. These elements are ordered and I need to find the correct order. All I can do is to submit a query with a hypothesizes complete order and get a score (between 0 and 1) which represents how far is my ordering from the true ordering, without any information about which part of the ordering is correct/incorrect.
This seems like a standard kind of a problem, but I couldn't find info about that.
Is there a strategy/algorithm that can generate queries based on past answers to minimize learning time and maximize score achieved?
I thought that learning to rank algorithms should help, but their formulation seems far from what I need, although I might have missed something. I am also looking at some reinforcement learning algorithms
However, any references/hints/help  will be appreciated.
For simplicity, let's assume that the score you get for a hypothesized ordering is the percentage of correct pair orderings. however, as this is a statistical learning qustion, you should also consider that there is some noise, and the score you are given is the true score plus some unknown, but typically small random noise.
Thanks.
 A: I think you may be overthinking things. All you need to do is imitate a sorting algorithm. Let's look at a few simple cases.
$n=2$
There are two possible sortings: $(1,2)$ and $(2,1)$. Compare their scores. If $s(1,2)>s(2,1)$, then $(1,2)$ is the correct score, otherwise $(2,1)$. Done.
$n=3$
First compare $s(1,2,3)$ and $s(2,1,3)$ to find out which one of the first two elements has the higher rank. Suppose $s(1,2,3)>s(2,1,3)$ - then we know that the first element is sorted before the second one. We then compare the second and the third element, by looking at $s(1,2,3)$ versus $s(1,3,2)$. If $s(1,2,3)>s(1,3,2)$, then the order is $(1,2,3)$, and we are done. Otherwise, we compare $s(1,3,2)$ and $s(3,1,2)$ and are done after this comparison.

This is nothing else than bubble sort. It generalizes easily to $n>3$. You simply "bubble" each element's rank through the list.

Look at sorting algorithms in general. Each one can be mapped to a solution of your problem. Which one specifically you want will depend on your problem size, on whether you need an easily understood algorithm, or whether you have some specific structure in your data.
