# How should an agent learn about a good state?

I am trying to train an agent in an environment (let's say a grid environment) to learn to get to a specific location (let's call it G). The rewards the agent get from this environment is in this way: if the agent gets to G, it receives a reward of 1 and otherwise, it receives the reward of 0.

My problem is that it is very difficult for this agent to get to G by choosing random actions at each location it is in because the probability of getting to G by choosing random actions is almost zero. Due to the reward structure of the environment, if the agent doesn't get to G, it cannot learn anything about the environment.

Now, my question is that is there any solution for this issue?

One idea that comes to mind is to change the reward structure of the environment. That is, instead of just having 0 and 1 as rewards, we assign reward of 0.5 to the neighbors of G, 0.25 to the neighbors of neighbors of G, etc. Is this a valid solution?

The rewards the agent get from this environment is in this way: if the agent gets to G, it receives a reward of 1 and otherwise, it receives the reward of 0.

This is an unusual way to reward an agent for a search, as there is no incentive for it to get to the goal state in any given time. The expected return for random behaviour that gets to the goal after a million moves is 1, the same as the expected return if it gets to the goal in ten moves. All policies that get to the goal state eventually will have a value of 1 for all actions. That in turn means that a random policy is just as optimal as one that heads straight to the goal, so there is nothing useful to be learned.

You need to have either a discount rate, or a cost for taking time. I think the latter will be more effective when combined with TD learning in your case.

Assign a cost, or negative reward for each time step. Say $-1$ per time step. The reward for reaching the goal can be zero in that case. Getting a maximum (but negative) reward is then the same as finding the quickest route from the start to the goal.

the probability of getting to G by choosing random actions is almost zero.

If you use a Temporal Difference algorithm, such as Q learning, and set the initial return estimate for all $Q(s,a)$ to an optimistic value - e.g. $0$ - then the behaviour will not in fact be random. That is because in TD, the agent can learn from rewards it receives mid-episode. The agent will explore "promising" paths that it has not seen before, and be discouraged from states it has been to multiple times without completing the episode. If you visualise the agent on the first episode, you will see it move back and forth over different areas of the map as it exhaustively searches for a better reward than the repeated $-1$.

Depending on the size of the map, it could still take a long time, compared to, say an A* search based on heuristics. Even for simple problems, there is an element of brute-force searching in reinforcement learning. However, that is an unfair comparison, since you have withheld any heuristics from the agent, it has had to learn its own from testing the environment.

If a real-world problem allows you to add prior knowledge about the agent's goal, then the best way to incorporate that is to alter the initial Q estimates - e.g. you could make it similar to the heuristic that you would of fed to A*. You should avoid altering the reward to "help" the agent learn interim steps - instead the reward needs to be designed to formally describe the goal of solving the environment. In toy problems, you are often interested in setting arbitrarily difficult goals in order to see if a particular kind of agent can solve them.

You can improve learning speed further by using more advanced algorithms that combine TD learning with episodic Monte Carlo control. The Q($\lambda$) algorithm allows the agent to assign a portion of sampled reward to the history of previous states and actions, and this can help in environments with sparse reward.

• Thanks for your answer. I already had -0.01 for each unsuccessful step and +1 for reaching the goal. So, I guess the first issue is fine. Regarding the probability issue, I am using neural nets to model to approximate Q functions and the weights of this network is set randomly at the beginning. Can we still have hope that agent find correct paths? Commented Jul 12, 2018 at 19:10
• @user491626: It should work, but there are traps for the unwary, such as Q values diverging unless you do specific things to counter that. This is quite different to the original question here that you posed though. I suggest ask another question with relevant details in it, such as the representation you are using, whether anything on the map changes over time other than the agent location. Also, whether you are using experience replay, or any other stabilising techniques for the NN. Commented Jul 12, 2018 at 19:47
• Thanks for your comment. I asked a new question here: stats.stackexchange.com/questions/355901/… Commented Jul 13, 2018 at 0:53