  Reward shaping (RS) is a powerful method in reinforcement learning (RL) for
overcoming the problem of sparse and uninformative rewards. However, RS relies
on manually engineered shaping-reward functions whose construction is typically
time-consuming and error-prone. It also requires domain knowledge which runs
contrary to the goal of autonomous learning. In this paper, we introduce an
automated RS framework in which the shaping-reward function is constructed in a
novel stochastic game between two agents. One agent learns both which states to
add shaping rewards and their optimal magnitudes and the other agent learns the
optimal policy for the task using the shaped rewards. We prove theoretically
that our framework, which easily adopts existing RL algorithms, learns to
construct a shaping-reward function that is tailored to the task and ensures
convergence to higher performing policies for the given task. We demonstrate
the superior performance of our method against state-of-the-art RS algorithms
in Cartpole and the challenging console games Gravitar, Solaris and Super
Mario.
