Is this variant of PAC learning known?
What you describe is a non-stochastic version of the "functional multi-arm bandit problem": you know you have an unknown function from some class C (does not have to be randomly selected), and you have query access to this function. The goal is to find the element which maximizes the function. As you say, depending on the class C, this may or may not require learning the function.

This paper by Amin, Kearns, and Syed exactly characterizes the query complexity of the problem: http://www.cis.upenn.edu/~mkearns/papers/haystack.pdf