1
$\begingroup$

For a study, I have a system (black-box) that requires an input in the form of an array with 4 values (input_array) and depending on their values it produces an output (response) signal.

Block diagram

The input_array contains 4 real values (parameters P1-4), with given and separate ranges. The output signal's quality is measured by calculating its signal-to-noise ratio (SNR). Each input_array variant can be applied to the system once every 3 seconds (not faster than 3 s).

I have to find the optimal input_array that produces the greatest SNR (preferably, in the least amount of time). That is, the combination of the 4 real values that maximizes the SNR (an optimal solution is sufficient; an absolute solution is welcomed, but not necessarily required). If helpful in finding a solution, the 4 parameters can be discretized, but their ranges would include hundreds of possible (discrete) values.

The values can be considered independent, no prior knowledge is available for them except their ranges, and their individual influence on the SNR is unknown. The SNR is a real value that is influenced by noise (thus, for the same input_array applied consecutively, it can have different (but close) values).

What solution(s) can be applied to this problem?

  1. The simplest solution that comes to mind is to perform an exhaustive search of the parameters domain, but it is no applicable because the time required will be too long.

  2. Initially, I was considering of applying reinforcement learning algorithms for continuous action spaces, by considering each parameter a separate action and returning a positive/negative reward when the SNR increases/decreases (e.g., +/-1). However, I think they would require too much time; nonetheless, I can stop the learning process at any time I consider that the input_array produces an acceptable SNR.

  3. After further thinking, this problem seemed like a search problem, so I thought that (heuristic) searching algorithms may be appropriate.

Does anybody have an idea what would be the most appropriate solution to this problem?

$\endgroup$
1
$\begingroup$

It appears that you have a function $f:\mathbb{R}^4 \to \mathbb{R}$ and you want to find $x$ that maximizes $f(x)$, but you cannot compute $f$ directly; you can only obtain a noisy estimate of its value.

Many optimization methods can be adapted to this setting. A simple thing you could try would be an iterative method like gradient ascent or Newton's method, but with more iterations to account for the noise; the idea is that the noise will average out given enough iterations.

For instance, gradient ascent requires that you be able to compute the gradient $\nabla f (x)$ for any point of your choosing. In your case, this can be done by estimating

$$\nabla f(x) = ((f(x+e_1)-f(x-e_1))/2, \dots, (f(x+e_4)-f(x-e_4))/2),$$

where $e_1=(1,0,0,0)$, $e_2=(0,1,0,0)$, and so on. Now given the ability to compute $f$ on a point of your choice, by computing $f$ on 8 inputs, you can estimate $\nabla f(x)$ and then take a single step of gradient ascent; and repeat until convergence.

A more sophisticated approach would be to try using Bayesian optimization, such as Google Vizier.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your answer! Please, can you describe what advantages/disadvantages does Google Vizier-Bayesian optimization offer over the simpler methods (gradient ascent, Newton)? Also, I would be grateful to know your opinion if reinforcement learning and heuristic search are/are not suited for this problem. $\endgroup$ – Cristian M May 10 at 9:41
  • $\begingroup$ Are there other algorithms available in Google Vizier that can be applied for this problem? PS I have found an open source implementation of Google Vizier: github.com/tobegit3hub/advisor $\endgroup$ – Cristian M May 10 at 9:52
  • $\begingroup$ @CristianM, I don't know. You might have to try them both. It's possible that Vizier might need fewer queries, but it's hard for me to know. RL might be suitable but I don't know much about it so I'm not in a good position to comment. Heuristic search is a broad area rather than a particular method. $\endgroup$ – D.W. May 10 at 20:52
  • $\begingroup$ Ok, thanks. It would have been good to know how appropriate are reinforcement learning and heuristic search for this problem. I hope someone will see this question and answer. $\endgroup$ – Cristian M May 11 at 9:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.