Here is a problem I've never seen, in a model similar to the PAC model. It asks a similar question to PAC learning, but wishes to optimize, rather than learn. I wonder if this problem is known, has any name, or has ever been solved.
Input: A Random Oracle to function $f:[0,1]^n \rightarrow [0,1]$ from a concept class $C$. Additionally, $n$ points $x_1,\ldots,x_n$ in the domain.
Goal: Select an $i$ such that $E[f(x_i)]$ is as large as possible. We assume the function $f$ is randomly distributed amongst all functions in the class $C$ that agree with all the samples we have drawn.
One way to solve this problem is to draw many samples from $f$, create a hypothesis $h$, and choose the $x_i$ whose $h(x_i)$ is largest. There are two problems with this:
- $h$ might not be representative of the set of all $f$'s that agree with the samples we've drawn.
- To solve our problem it is not clearly necessary to learn $f$: for some classes $C$ might be a more efficient way to select a good $i$ without trying to learn $f$.
An example setting is where $C$ is the set of linear classifiers. In that case it should probably be quite easy to solve the problem. But what about other, more complicated classes?
The real version I'm interested in is that of agnostic learning of linear functions? we assume the function $f$ is somewhat correlated with a linear function, and the goal is to choose an i which maximizes $E[f(x_i)]$ to the best of our ability.
