# How do I avoid an agent to tend to terminate in a negative state when time needs to be taken into account?

In an unknown environment, how do I avoid an agent to tend to terminate its trajectory in a negative state when time needs to be taken into account?

Suppose the following example to make my question clear:

• A mouse (M) starts in the bottom left of its world
• Its goal is to reach the cheese (C) in the top right (+5 reward) while also avoiding the trap (T) (-5 reward)
• It should do this as quickly as possible, so for every timestep it also receives a penalty (-1 reward)

If the grid world is sufficiently large, it may actually take the mouse many actions to reach the cheese.

Is there a scenario where the mouse may choose to prefer the trap (-1*small + -5 cumulative reward) versus the cheese (-1*large + 5 cumulative reward)? Is this avoidable? How does this translate to an unknown environment where the number of time steps required to reach the positive terminal state is unknown?

This is a common problem in reward shaping. You want a certain behavior from you agent but its challenging to describe it completely in terms of rewards. This situation you are describing is challenging specifically because as the grid world grows, the chance of randomly stumbling onto the goal state becomes less likely AKA the problem of exploration. There are a few techniques that can be used to address this problem though, here are some.

0) This is an emergent property of the environment and gamma (0 based because its more immediate to your problem:p)

If gamma is small, your agent will value rewards that are in its immediate future more highly whereas as gamma approaches 1, the agent values rewards that are further in its future. In your grid world, the the size of the grid affects how this gamma affects your agent. Like in your example, if your grid was 100x100, if the trap was close to the agent, you would have to have a gamma closer to 0 in order for your agent to avoid the trap because its worse than moving to a cell that isn't a trap. This is interesting because the whole purpose of gamma is to increase the weighted value of temporally distant rewards but when you make the trap more favorable than the goal, going to the trap is the optimal strategy. :)

1) Include more observation data to your model

This isn't always a possibility but depending on your application and what you have available, you may be able to give your agent missing information that might be necessary to its ability to solve your task. For instance, in your infinite grid example, you may include the distance between the agent and the goal or the direction of the goal.

2) Include a reward that helps to shape the direction of progress.

One could easily create an infinite grid world where there isn't actually a goal but rather a continuing task where the agent has to cover distance in a desired direction while avoiding obstacles. How would you approach this problem? Perhaps a reward that specifically looks at the number of cells visited by the agent in the desired direction over time aka the discrete analog to velocity. Of course this is still dependent on a know direction but thinking about how to one might handle the "limit" of your environment as it grows (e.g., adding more and more cells to the grid world) helps to give an intuition of what your agent could be missing.

3) Use curiosity based approaches Following from 2), if the direction isn't known, one thing to consider is rather than giving a penalty for each timestep, instead incentivize the agent to be faster, rewarding visiting "infrequently visited" states. As the task requires that the agent performs as quickly as possible, remaining or returning to a previously visited state clearly doesn't benefit the agent. Taking this notion of rewarding "visiting infrequently/unyet visited/ states" further results in the recent research topic of using curiosity to have RL agents that have novel exploration strategies.

Although there are many (often debated) ways to define curiosity, they all share an idea of giving the agent a bonus when it has entered a state that has not been visited before. A paper that gives a good recap of curiosity methods and also introduces a novel approach is Random Network Distillation from OpenAI.