2
$\begingroup$

is it possible to train a neural network to find the global maximum value of unknown functions like f(x,y)=z with reinforcement learning?

Up until now I had only had experience with simple environments (for example: gym library).

I thought about an agent that is like a hiker who walks on the terrain. I mean two-dimensional functions output different heights (z) which you could see as a terrain.

My thoughts so far for the agent:

The agent always starts at a random location (random x,y values). When the agent reaches the global maximum value the environment (terrain) should reset. This means a new unknown random functions will generate the terrain (z height map).

Actions that the agent can perform:

  • move left (input values: x=x-1 , y=y)
  • move right (input values: x=x+1 , y=y)
  • move up (input values: x=x , y=y+1)
  • move down (input values: x=x , y=y-1)

Rewards for the agent:

  • -1 per step unless other rewards are triggered

  • +10 if the global maximum value was found

I do not really know if this will work because the maximum value could be very far away from the starting point of the agent. Image if the agent starts at something like f(2,5) and the global maximum is located at f(9328193,32929549). Is something like this even possible with reinforcement learning and a neural network? There are litteraly infinite random functions that can generate terrain.

$\endgroup$
0

1 Answer 1

2
$\begingroup$

Is it possible to train a neural network to find the global maximum value of unknown functions like f(x,y)=z with reinforcement learning?

In short, no, and this is technically an impossible task for any known optimisation technique.

The main objection that you already note in the question is true:

I do not really know if this will work because the maximum value could be very far away from the starting point of the agent. Image if the agent starts at something like f(2,5) and the global maximum is located at f(9328193,32929549). Is something like this even possible with reinforcement learning and a neural network? There are litteraly infinite random functions that can generate terrain.

It's also worth noting that many functions don't have global maximums. E.g. $z = x + y$ has no maximum value for $z$. Although very common, we can assume that your search is somehow constrained only to functions that do have finite global maximums, and the problem you raise about difficulty of the search is still an issue.

In addition, your reward scheme pre-supposes that either the agent or the environment can reliably detect that the input parameters represent a global maximimum, in order to terminate the search. This is possible to construct as a toy problem when you design a test or training environment, and already know the maximising input parameters, but there is no corresponding real environment or real way to detect global maximum function points in general for arbitrary functions sampled through experience only (so called "black box" functions).

In practice, there are lots of computing methods to search for maximising input parameters to functions of interest in different problem domains. Which approaches work best depends critically on the nature of the functions. You could start by looking at broad categories of global optimisation approaches.

Completely arbitrary functions are impossible to solve in this way because there could simply be an arbitrary spike at any co-ordinate, and task becomes an infinitely long search. So it is not possible to construct a general purpose solve-all-maximising-problems AI method.

However, most real world problems that you may wish to solve are more tractable. They usually are constrained in some way, e.g. to a finite search space, and/or conforming to model some real system. Such problems tend not to have semi-random spikes that cause global minimums or maximums at unpredictable parameters, and also often have function spaces that can be characterised and allowed for when considering search strategies.

Once the function space is constrained by some kind of model of the problem, there are often one or more techniques that can be applied for effective - or at least efficient - search. Also, often an approximate maximum (or minimum) is acceptable, especially if it can be shown to be within some reasonable bound of a best case global theoretical maximum.

Would a reinforcement learning algorithm as outlined in the question be useful in a more constrained problem space? Perhaps, if anything can be learned by the agent about how to search because there is some common theme for searching for maximums for the kind of problem you are interested in. However, in general, Reinforcement Learning methods are designed for learning through trial and error, and they are not designed to be efficient search methods for solving optimisation problems. So there will often be a better way, depending on the problem space.

$\endgroup$
3
  • $\begingroup$ "In short, no, and this is technically an impossible task for any known optimisation technique."... well technically yes, it can, the actual point is "can it do it in an polynomial amount of time"? There are optimization algorithms that can give you the global max, just think about an extensive grid search... the problem is that they require an exponential amount of time/resources. About the rest, I agree with you $\endgroup$
    – Alberto
    Sep 10, 2023 at 10:43
  • $\begingroup$ @Alberto This is not about polynomial time or search efficiency, just that the general case is immediately infinite, there's no N to consider scaling issues by. If you were talking about a system that was bound in some way, eg a finite grid, then search efficiency does come into play, and the problem tractable in theory. The OP doesn't specify any such bounds, and implies there are none with their example $\endgroup$ Sep 10, 2023 at 12:38
  • $\begingroup$ @NeilSlater Thank you for helping me out! Your answer is very useful. :) $\endgroup$
    – Bubble
    Sep 18, 2023 at 7:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .