I'm curious how one should define the reward for problems where it is not clear whether a target goal can be reached or not but getting as close as possible is desired.

For example in Sutton & Barto - Reinforcement Learning: An Introduction they discuss the example of playing golf (2nd edition, Example 3.6). They state that

To formulate playing a hole of golf as a reinforcement learning task, we count a penalty (negative reward) of 1 for each stroke until we hit the ball into the hole.

In their setup ("environment") they seem to consider an infinite number of steps being allowed and the target (hole) can eventually be reached.

Now consider the variation where the area is covered by some tall obstacles that one has to play around. Furthermore it is not clear whether the target (hole) is actually reachable from the starting position; it might be completely surrounded by obstacles as shown in the following sketch:


In any case the objective is to get as close to the target as possible, whether or not it is reachable. In the above sketch, since the target is not reachable, the optimal position is indicated at one of the obstacles.

I'm interested what are good options for reward shaping in such a scenario. Considering a maximum episode length, similar to OpenAI Gym does for their environments, if I use a reward of -1 per step then there won't be any improvement since it will always hit the time boundary (never reaching the target).

I came up with the following options but I'm not sure if they're appropriate or whether there exist better ones:

  1. Reward -1 per step and stochastic termination of episodes: At each step the episode will terminate with probability $p$ which incorporates the distance of the ball to the target: the closer to the target, the higher the probability to terminate. For example $p = \exp\left(-\sigma\cdot||\vec{x}_{ball} - \vec{x}_{target}||\right)$ with some hyper-parameter $\sigma$. In the long run this should learn that getting closer to the target results in higher rewards since episodes are more likely to terminate. How to formulate $p$ and choose any involved hyper-parameters is however not obvious (and hyper-parameter optimization might take very long).
  2. Reward -1 and gradually relax the target: In a first attempt see whether the environment is solvable for the desired target. In case it is not (i.e. the test runs always hit the time boundary) one would relax the target and consider an episode finished when $||\vec{x}_{ball} - \vec{x}_{target}|| \leq d$ with some hyper-parameter $d$. Then, if it is not solvable either, one would gradually increase $d$ until the algorithm finds a solution. It is however not clear how to choose $d$ and it might take a lot of iterations until the optimal $d$ (and the optimal position) is found.

Does anyone have other ideas on how to tackle this problem or comments on the above suggestions? Any help is greatly appreciated, thanks in advance.


Your Answer

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

Browse other questions tagged or ask your own question.