It's hard to know what to recommend, without more context.
One possible approach is to use hill-climbing, simulated annealing, or some other form of local search. A simple form of hill-climbing is to pick a random variable, determine whether increasing/decreasing it will improve your model, and if so, increase/decrease it; then repeat until no further improvement is possible. You can combine with random restarts, or use a more powerful method like simulated annealing.
Alternatively, you could try using something like gradient descent. Suppose you learn not only whether increasing the parameter will improve the model, but how much it improves it. If you have this information, you can estimate the gradient at a point, then move in the direction of the gradient, and repeat. Based on experience with stochastic gradient descent, rather than repeating this many times at a single point and averaging, it's likely to be more effective to do this only once at each point and instead repeat for more iterations of gradient descent (perhaps with a smaller step size). Basically, because your information is noisy, each step is mostly random and is only loosely correlated with the correct direction, so this does a random walk that is slightly more likely to go in a good direction than a bad direction; after sufficiently many iterations, this should converge to a good solution. The analysis of stochastic gradient descent shows that in many settings this performs better than trying to compute many votes at a single point, average them to get a very good estimate of the direction to go, and repeat for many fewer iterations. So, the theory says: take only one vote. There's no theory to tell you how much to change the parameters (the step size). Usual practice in the machine learning literature is to treat this as a hyperparameter, try multiple different values (e.g., 0.0001, 0.001, 0.01, 0.1), and see which works best. Sometimes it may be helpful to start with a large step size and then reduce it after some number of iterations. There are also heuristic optimizers that try to adaptively adjust the step size, such as the Adam optimizer, but it's unclear whether they help or not.
Another approach is to use Bayesian optimization, which uses machine learning to construct a surrogate model that can predicts how well any set of parameters will perform, and then uses optimization methods on the surrogate model. See, e.g., Google Vizier for one representative of this approach.
I can't predict which approach is likely to be most suitable to your setting. That may depend on the number of dimensions (how many parameters you have), the dependence of the metric you care about as a function of the parameters (how nonlinear it is), and what kind of information you receive about any set of parameters.
Related: What solution to apply for finding the optimal parameters?, What is an appropriate global optimization technique for a noisy and expensive function?, Mathematical optimization on a noisy function.
