Summary: The aim of this chapter is to draw links between (1) No Free Lunch (NFL) theorems which, interpreted inversely, lay the foundation of how to design search heuristics that exploit prior knowledge about the function, (2) partially observable Markov decision processes (POMDP) and their approach to the problem of sequentially and optimally choosing search points, and (3) the use of Gaussian processes as a representation of belief, i.e., knowledge about the problem. On the one hand, this joint discussion of NFL, POMDPs and Gaussian processes will give a broader view on the problem of search heuristics. On the other hand this will naturally introduce us to efficient global optimization algorithms that are well known in operations research and geology [H. M. Gutmann, J. Glob. Optim. 19, No. 3, 201–227 (2001; Zbl 0972.90055); D. R. Jones et al., J. Glob. Optim. 13, No. 4, 455–492 (1998; Zbl 0917.90270); D. R. Jones, J. Glob. Optim. 21, No. 4, 345–383 (2001; Zbl 1172.90492)] and which, in our view, naturally arise from a discussion of NFL and POMDPs.
For the entire collection see [Zbl 1304.68009].