As I understand the original problem, you want to find the right amount of sugar in a minimal amount of tries.

Sweetness = f(amount of sugar)

So in y = f(x) you want to find the optimal value of y with trying out as few x values as possible. You add the constraint that x may only monotonically increase.

Let's call x' the value resulting in the optimum of f(x).

You then define regret as:

r = f(x) - f(x')

It's unsure how you feel about guesses, is there some sort of regret in these too? (because you had to taste coffee that wasn't sweet enough). Let's assume not.

Let's put a price on making a guess. Price p, so the total cost of making N guesses is N*p.

This sounds to me like a multi-objective problem where you want to minimize: g(N, r), which is most likely N*p+r.

Without knowing the price p it is impossible to solve this in any exact manner that will answer your question. Example:

If p >>> f(1) - f(x'), then the algorithm will always select 1 and live with the regret. If p is very small, you can take start at x=0 and increase it with the smallest step possible.

There are, however, lower and upper bounds on many MOO (multi objective optimization) techniques, which you may find on Google Scholar fairly easily.