3
$\begingroup$

Assume we want to train an agent where the agent should select a vector of K actions (the action size for this agent is K). More specifically, assume a grid environment where we have K robots where each robots can move up, down, left, right. There are K specific goal locations where the robots should go there. In each episode, if each robot occupy one goal (so that all goal locations are occupied), we get the reward of 1 and this episode ends; otherwise, for each time passed we get -0.01 (a punishment so our agent learns to do this task faster). Each episode have T time steps and the agent receives the sum of rewards obtained at each time step. I want to use a DQN to train this agent.

What we are usually do when using a DQN is that we fill the replay memory of size M with random actions (without updating the network). When the memory is full, we start taking batch from memory and update our network while following an epsilon greedy algorithm (decreasing epsilon from 1 to 0.05 in L time steps).

The issue here is that the probability of observing the positive reward for our agent is almost zero. So, it is quite possible that when we fill the memory, all experiences have the episode reward of -0.01*T. Even it is quite possible that all L exploration steps end and the agent does not observe the reward of 1.

Is there any way to remedy this issue? This issue become more severe as we increase K.

Is any of following ways is going to help?

  • Increase T to a very large number so that we make sure that the experience regarding positive reward happens.
  • Increase L to increase the chance of experiencing positive reward happens. In this case, we need to increase M proportionally.

Obviously, if we give partial positive rewards to the agent, it can learn it easier (and faster).

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

In general, solving reinforcement learning tasks with sparse rewards is still an open problem.

Some popular classes of solutions are

  1. Shaped dense rewards, which you mentioned in your question.

  2. Learning from demonstrations from an expert who can solve the problem, whether that expert is a human player or an expensive solver which can do the task with enough computation. See this survey paper.

  3. Curriculum learning, where you start with an easier set of tasks which can be easily learned, and then ramp up the difficulty gradually. See 1 and 2.

  4. Hindsight experience replay, where if the agent does X instead of Y, you add on to the memory a fabricated episode of gameplay in which you pretend you intended to do X and got a reward.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks for your answer. Can you be more specific about point 4? $\endgroup$
    – user491626
    Jul 16, 2018 at 4:27
  • 1
    $\begingroup$ The original paper is here. It applies mainly to multigoal environments, where the DQN learns $Q([s,g],a)$: the expected cumulative future reward at state $s$ performing action $a$ for goal $g$. So if your goal was $X$ but you reached $Y$, then you simultaneously learn $Q([s,X],a)$ is low, but $Q([s,Y],a)$ is high. Hence, you manage to get some useful signal even when you fail! $\endgroup$
    – shimao
    Jul 16, 2018 at 4:33
  • $\begingroup$ Are there any papers for the points 2 and 3? $\endgroup$
    – user491626
    Jul 16, 2018 at 21:04
  • 1
    $\begingroup$ @user491626 I added some references for learning from demonstrations and curriculum learning. If you have a specific query about hindsight experience replay please feel free to ask in a separate question $\endgroup$
    – shimao
    Jul 17, 2018 at 2:52
  • 1
    $\begingroup$ I asked a new question here: stats.stackexchange.com/questions/357508/… $\endgroup$
    – user491626
    Jul 17, 2018 at 4:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.