I want to maximize a function like the one in the plot linked below. The challenges are the nature of function itself (it’s constant for most of it’s domain space), the evaluation involves complex computation (around 10 seconds), it’s not described by a mathematical model (no analytic methods or gradient based methods are applicable), and it’s discrete. What are algorithms suitable for this problem?

function plot

I thought about bayesian optimization and it will probably work but performance will be bad because all evaluations in the constant portion of the function won’t lead to any kind of information gain. Other heuristics like simulated annealing will also work, but I’m curious what you would suggest or try on this problem.