Exploration via Cost-Aware Subgoal Design
  The problem of exploration in unknown environments continues to pose a
challenge for reinforcement learning algorithms, as interactions with the
environment are usually expensive or limited. The technique of setting subgoals
with an intrinsic reward allows for the use of supplemental feedback to aid
agent in environment with sparse and delayed rewards. In fact, it can be an
effective tool in directing the exploration behavior of the agent toward useful
parts of the state space. In this paper, we consider problems where an agent
faces an unknown task in the future and is given prior opportunities to
``practice'' on related tasks where the interactions are still expensive. We
propose a one-step Bayes-optimal algorithm for selecting subgoal designs, along
with the number of episodes and the episode length, to efficiently maximize the
expected performance of an agent. We demonstrate its excellent performance on a
variety of tasks and also prove an asymptotic optimality guarantee.
