Maximize sum of f(x), where f(x) is unknown, but we learn as each x is chosen Let's suppose that I have a function like below, but I don't know what it is. However, as I choose x, I know what corresponding f(x) is. What is the optimal way to choose x such that sum of f(x) is maximized for some finite n tries (let's say 50 tries for the following example)?

My idea so far:
1) Choose some xs at random in grid search type fashion e.g, 0,25,50,75,100.
2) a) Choose xs that correspond to higher f(x) with higher probability.
b) Introduce some kind of noise factor around x, so we are able to search around x. For example if 75 is chosen, in 2.a, in 2.b 78.33 can be chosen. This noise factor should decrease as number of iterations increases.
3) Keep doing step 2 for a number of values of x. 
Is there a better way to do the above? Is there a known algorithm to tackle this problem? 
 A: Your problem is the "Multi-Armed Bandits in Metric Spaces" problem.  Check out the 
Kleinberg,  Slivkinsy, Upfal paper located at 
http://www.cs.cornell.edu/~rdk/papers/bandits-lip.pdf
I suggest you also check out "Direct" optimization.  Here are some slides
http://people.inf.ethz.ch/ybrise/data/talks/msem20080401.pdf
A: Your problem and algorithm reminds me of particle swarm optimization, inspired by the behaviour of flocks of birds and schools of fish.
Outline of the algorithm:


*

*Choose a number of particles.

*Each particle has a current position and velocity and also records its personal best position, where the value of $f(\text{position})$ was highest.

*Initial particle positions and velocities are random.

*Particles cooperate by exchanging information with other particles in their neighbourhood.

*The neighbourhood can be defined geographically, or by particle type, and at its simplest is the whole solution space.

*At each step, each velocity is adjusted by adding in a random mixture of vectors pointing towards personal and global best, where the global best is the position of the particle with the highest value of $f(\text{position})$ in the neighbourhood.

*The positions are then updated using the velocities.
Formally, particles have the following characteristics:


*

*$\mathbf{x}_i$ = current position of particle $i$.

*$\mathbf{v}_i$ = current velocity of particle $i$.

*$\mathbf{p}_i$ = position at which particle $i$ had its personal best result.

*$\mathbf{p}_g$ = position of the particle with the best $f(\text{position})$ in a given particle's neighbourhood (the $_g$ is for "global").
At each time step, positions are updated as follows:
$$\begin{align}
\mathbf{v'}_i &= \mathbf{v'}_i + \psi_{i,1}(\mathbf{p}_i-\mathbf{x}_i) + \psi_{i,2}(\mathbf{p}_g - \mathbf{x}_i) \\
\mathbf{x'}_i &= \mathbf{x}_j + \mathbf{v'}_j
\end{align}$$
where $\psi_{i,j}$ are random parameters, so that the new velocity is calculated by adding to the existing velocity a random mixture of vectors pointing towards personal and global best.
In your case I would vary the neighbourhood depending on how many steps you have left to explore the function $f$. If you have very few steps left, a global neighbourhood would be appropriate: just grab the best you can while you can, even if the best you have is just a local maximum. On the other hand, if you have a lot of steps left, keep your neighbourhood more local, because it's worth spending some time exploring now to try to find a global maximum so that you can settle all your particles on the global maximum for the large number of remaining steps.
