2
$\begingroup$

I have created a simple OpenAI Gym environment, which consists of:

  • A continuous 2D world with x and y in range [0.0, 1.0]
  • A rabbit which slowly moves randomly in the world with a constant speed
  • A 'wolf' controlled by the agent. The wolf moves at a constant speed
  • The actions are [turn left by a constant angle, turn right by a constant angle, do nothing (continue straight)]
  • The state is [agent_x, agent_y, agent_bearing, rabbit_x, rabbit_y, rabbit_bearning]. Bearings are in radians [0.0, 2*pi]. All values are floating point numbers.
  • The reward is 30 for catching the rabbit (catching means the agent getting sufficiently close to the rabbit). -0.1 for each timestep without catching the rabbit.
  • Maximum timesteps 260

I am having trouble solving this environment. Agents trained in it get scores only slightly better than a random agent even after long training sessions. I have tried Deep Q-learning (with experience replay, target network) REINFORCE (with and without baseline) and PPO.

Conceptually, the problem is quite simple. The agent just needs to learn to turn towards the rabbit. However, it occurs to me that the state representation might make the problem more difficult, since only one of the six variables is directly under the agent's control, and three of them (the rabbit state) are completely random.

Does state representation generally affect how difficult a problem is? Is this a poor state representation? Are there rules of thumb for how to design states? Would it help to reformulating the state, eg. to [distance_from_agent_to_rabbit, angle_between_agent_and_rabbit]?

Environment source code here.

$\endgroup$
  • $\begingroup$ @NeilSlater I have tried the distance-angle state approach without success using REINFORCE. I haven't tried it with other algorithms or with very long training times though. I have added a link to the environment source code. $\endgroup$ – Atuos Oct 2 '18 at 9:18
  • $\begingroup$ Yes, I should have mentioned this. It is intentional. I originally ended the episode if the wolf left the area, but this caused its own set of headaches. $\endgroup$ – Atuos Oct 2 '18 at 9:36
  • $\begingroup$ @NeilSlater good point, I will fix that $\endgroup$ – Atuos Oct 3 '18 at 6:08
  • $\begingroup$ Fantastic. After clipping the bearing I have also been able to solve this with DQN. $\endgroup$ – Atuos Oct 3 '18 at 8:11
1
$\begingroup$

Does state representation generally affect how difficult a problem is?

Yes, due to it being easier or harder for a neural network to learn the relationships between input features and the target policy or value function.

Is this a poor state representation?

No, it should be fine, provided you are interested to see a RL learn to convert from cartesian coordinate space to solving this problem, you should be able to use the state directly as ML features.

It could be made into better features for a NN in two ways:

  • Scaling to fit in ranges with zero mean and limited max absolute values.

  • It could be engineered so that features include domain knowledge of the problem to be solved.

The first part is optional for you, but I think that the bearing values benefit a little from being scaled and centred. In a more general case, even if the state description was complete, you may still want a step that re-scales it.

The second part is tricky - yes you could find better features, but part of the challenge is to create an agent that learns to do this itself. In this case, you may want to gain experience training agents where it is less easy to engineer "golden" features, and focus on RL methods.

Are there rules of thumb for how to design states?

Conceptually, the problem of state representation can break down into three parts:

  • Observations. Raw observations are not always direct candidates for a state representation. In a toy problem, often this is ignored and you feed data from a simulation that looks useful as a state. In the real world you can be limited by what is detectable.

  • State description. Unless you want to explore POMDPs then you usually want the state description to possess the Markov property. This might already mean processing observations into something else - e.g. using history of last 3 observations, keeping running totals or calculating differences.

  • Feature vector. Once you have decided to use function approximation for calculating action values or a policy function, then your inputs need to conform to how the function approximation works. For most function approximators, this means numerical values. For neural networks, it means scaling inputs to fit relatively small ranges. There is also the question of feature engineering using domain knowledge of the problem.

There is some overlap between these design steps, the distinctions are somewhat artificial. When you are designing a test problem like yours, you may find it simple to combine all three steps into a single observation = state = feature. However, in real-world problems, each of the steps may require some consideration.

You should also consider the likely nature/shape of the function that you will be approximating. Action-value methods like Q learning need to approximate their value functions, whilst policy gradient methods like REINFORCE and PPO need to approximate policies. Sometimes the map between input features and the target function is simple, and if you are lucky some intuition can lead you to figuring that out. This is also a big driver when choosing between DQN or PPO for example - what seems easier to figure out, the correct action, or the value of a state/action pair?

Would it help to reformulating the state, eg. to [distance_from_agent_to_rabbit, angle_between_agent_and_rabbit]?

Maybe. The angle feature that would seem to most help is the difference in angle between the wolf's bearing and the vector between the wolf and rabbit. Then the correct action would map very clearly from that to steer the wolf towards the rabbit - in most cases a negative value means steer right and a positive value means steer left.

However, if you do this, you will in some ways have changed the nature of the problem to be solved. You have to ask, are you interested in applying your domain knowledge of the problem to help the agent, or are you interested to see if the agent can figure out an internal representation that discovers this relationship? For a toy problem, you may want to deliberately make something harder to learn.

I am having trouble solving this environment. Agents trained in it get scores only slightly better than a random agent even after long training sessions. I have tried Deep Q-learning (with experience replay, target network) REINFORCE (with and without baseline) and PPO.

As discussed in comments, the biggest factor towards this actually turned out to be a bug in your environment code, where the agent could end up with a bearing value out of range. The environment still worked, because you are using trig functions to calculate movement, but this causes even larger range of bearing values plus makes states that are identical appear different to the agent making things even harder to learn.

An experiment

I managed to solve this environment using a simple single-step DQN-based agent, and had time to experiment with some different input features to the NN to demonstrate my points above. In each case, I used exactly the same hyperparameters for RL and NN (expect in the last case I had to change the size of the NN's input layer).

I counted the number of training episodes required (including ~80 episodes of purely random behaviour to start experience replay) for 100 completed training runs, and tried some different state feature representations. I counted the environment as "solved" when 100 test runs using the agent acting greedily scored an average return of 20 or more. I did not count the test runs towards the number of training episodes.

I got these results:

  • Unaltered state 629.99 +-23.66 episodes, but failed in 28 out of 100

  • Scaled state 577.78 +-19.41 episodes, no failures

  • Engineered state 153.84 +-3.26 episodes, no failures

There is not quite a significant difference in 100 trials between number of episodes for unscaled and scaled state. However, the high number of failures (gave up after 1500 episodes of training) for unscaled features is a significant difference.

For the scaled state variation, The scaling for the cartesian coordinates was $f_i = 2*(s_i-0.5)$ and the scaling for the bearings was $f_i = 0.5 * (s_i-\pi)$

The engineered state used [distance between wolf and rabbit, angle between vector to rabbit and wolf's bearing, rabbit's bearing] scaled as above, and the performance was radically better.

Another consideration

As an aside, it is worth mentioning episode timeout and "done" flag.

You need to carefully consider what it means for the episode to time out. There is a difference between this being part of the challenge (to succeed within a time limit) and being for training convenience (to avoid wasting time learning from overlong or stuck episodes). Sometimes it is a big difference:

  • For training convenience. The "done" flag is an annoyance here, you want to avoid claiming the episode is really over to the agent, as it will falsely learn that some states, sometimes, end the episode - these states may then even be desirable to the agent as they seem like they stop the flow of negative reward. You don't want to store that white lie in the experience replay table - a simple work-around is to have your agent stop prematurely at least 1 step before the environment times out.

  • Part of the challenge. If the environment can really time out, and not randomly stop at any point, then in order to preserve the Markov property, you must include a representation of the time in the state - it can be time so far or remaining time. Otherwise you have turned the problem into a POMDP, and added complications for calculating value functions.

$\endgroup$
  • $\begingroup$ Beautiful answer, thank you very much. Interesting how much easier the distance, bearing representation was. The done flag discussion was fascinating as well, I wonder why there isn't more awareness of this issue. I don't think I have seen others mention it. $\endgroup$ – Atuos Oct 4 '18 at 12:16
  • $\begingroup$ @Atuos: When environments have 100s of time steps, it generally does not break things to accidentally store and train on convenience timeouts as if they were true episode ends, just adds a small amount of inaccuracy and inefficiency $\endgroup$ – Neil Slater Oct 4 '18 at 12:19

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.