<p>The problem you are describing is often answered with <a href="https://www.youtube.com/watch?v=xManAGjbx2k" rel="nofollow noreferrer">Reward Shaping</a>.</p>

<p>Like the frozen lake environment or <a href="https://blog.openai.com/learning-montezumas-revenge-from-a-single-demonstration/" rel="nofollow noreferrer">Montazuma's Revenge</a>, some problems have very sparse rewards. This means that any RL agent must spend a long time to explore the environment to see these rewards. This can be very frustrating for the humans who designed the task for the agent. So, like in the frozen lake environment, people often add extra information like you have suggested. This makes the reward function more dense and (sometimes) allows for faster learning (if the modified reward function actually follows what the human wants the agent to do).</p>

<p>In order for the agent to solve these kinds of problems faster than random search and without human intervention, such as reward shaping or giving the agent a video of expert playing the game, the agent needs some mechanism to explore the space in an intelligent way[<a href="https://xkcd.com/285/" rel="nofollow noreferrer">citation needed</a>].</p>

<p>Some current research areas on this topic are <a href="https://arxiv.org/abs/1703.01732" rel="nofollow noreferrer">Intrinsic Motivation</a>, <a href="https://arxiv.org/pdf/1705.05363.pdf" rel="nofollow noreferrer">Curiosity</a>, and <a href="https://arxiv.org/abs/1609.05140" rel="nofollow noreferrer">Options</a> and <a href="https://arxiv.org/pdf/1703.00956.pdf" rel="nofollow noreferrer">Option discovery</a>.</p>

<p>Although promising, these research areas are still in their infancy and sometimes its just easier to say:</p>

<pre><code>if agent_is_in_a_hole:
  return -10
</code></pre>
How can the FrozenLake OpenAI-Gym environment be solved with no intermediate rewards?
<p>I'm looking at the <a href="https://gym.openai.com/envs/FrozenLake8x8-v0/" rel="nofollow noreferrer">FrozenLake environments</a> in openai-gym. In both of them, there are no rewards, not even negative rewards, until the agent reaches the goal. Even if the agent falls through the ice, there is no negative reward -- although the episode ends.  Without rewards, there is nothing to learn! Each episode starts from scratch with no benefit from previous episodes.</p>

<p>This should be a simple breadth-first search. It doesn't need RL. But assuming you use RL, one approach would be a reward of -1 for a step to a frozen square (that isn't the goal) and a reward of -10 for a step into a hole. The -1 would allow the agent to learn not to repeat squares. The -10 would allow the agent to learn to avoid the holes. So I'm tempted to create my own negative rewards on the agent side. This would make it more like the cliffwalker.</p>

<p>What am I missing? How would RL solve this (except via random search) with no rewards?</p>