Question regarding the assumptions of the No-Free-Lunch-Theorem for Search I am trying to understand the No-Free-Lunch-Theorem for search (can be found here: http://axon.cs.byu.edu/~martinez/classes/678/Papers/Wolpert_NFLsearch.pdf) and have a question regarding the assumptions that were made by Wolpert et al. with respect to the &quot;general nature&quot; of a search algorithm.
In the paper, the following definitions were made:

$\mathcal{X}$ is the (finite) population of solutions,
$\mathcal{Y}$ is the (finite) evaluation space (e.g. a subset of $\mathbb{R}$),
$f : \mathcal{X} \rightarrow \mathcal{Y}$ is a cost-function,
$d_m = \{ d_m(i) : 1 \leq i \leq m \} = \{ (d_m^x(i), d_m^y(i)) : 1 \leq i \leq m \} \in \mathcal{D_m}$ is the &quot;history&quot;, i.e. the sequence of solution/cost-pairs $(x_1,f(x_1)),\dots,(x_m,f(x_m)) \in \mathcal{X} \times \mathcal{Y}$ that were found until time point $m$,
$a : \cup_{i \geq m} \mathcal{D}_m \rightarrow \mathcal{X}$ is a decision function that yields the next solution dependent on the recent history and
$\vec{c} \in \mathbb{N}^{\mathcal{Y}}$ is the histogram, which is the vector that stores the number of times every score was reached up until time $m$.

The work then shows that the equality $$ \sum_{f} P(\vec{c} \mid f,m,a_1) = \sum_{f} P(\vec{c}\mid f,m,a_2) $$ holds for all $m=1,2,\dots$ where $a_1$ and $a_2$ are arbitrary decision-functions and the sum spans over all possible cost-functions. The proof was done via induction on $m$, in which the equality
$$ P(x \mid d_m, f, m+1, a) = P(x \mid d_m, a) $$
was neccessary for the induction step (page 6). As I understood it, this basically means: the choice of the next solution $x \in \mathcal{X}$ is only dependent on the previous history $d_m$, since $x = a(d_m)$, and therefore independent of the cost-function $f$.
I agree that this holds if based on the above definitions, but I don't really think that this is how most search algorithms work? For example, a simple hill-climbing-algorithm would select a set of neighbours for every solution, compare them, and would then select the best neighbour, dependent on how they score on the cost-function. Therefore, the choice of the successor $x$ would depend on $f$, and one would have something like $x = a(d_m,f)$, i.e. the above part in the induction step wouldn't work.
So, my question basically is: am I missing something or is this work based on a wrong understanding of search algorithms?
I think that I was indeed misunderstanding something. Any search algorithm that wants to evaluate any point $x \in \mathcal{X}$ through $f$ would implicitly add $(x,f(x))$ to the histogram $d$. For example, one could design a hill-climbing algorithm in the following way:

for a solution $x'$, visit all neighbours $x_1,\dots,x_n$
afterwards, $(x',f(x')), (x_1,f(x_1)),\dots,(x_n,f(x_n))$ are all part of the histogram $d$
choose the best neighbour from $x_1,\dots,x_n$ by computing $a(d) = \arg\min_{x=x_1,\dots,x_n} f(x)$, which is independent of $f$ since $f(x_1),\dots,f(x_n)$ are already known
repeat