Episodic Return Decomposition by Difference of Implicitly Assigned
  Sub-Trajectory Reward
Haoxin Lin Hongqiu Wu Jiaji Zhang Yihao Sun Junyin Ye Yang Yu
Real-world decision-making problems are usually accompanied by delayed
rewards, which affects the sample efficiency of Reinforcement Learning,
especially in the extremely delayed case where the only feedback is the
episodic reward obtained at the end of an episode. Episodic return
decomposition is a promising way to deal with the episodic-reward setting.
Several corresponding algorithms have shown remarkable effectiveness of the
learned step-wise proxy rewards from return decomposition. However, these
existing methods lack either attribution or representation capacity, leading to
inefficient decomposition in the case of long-term episodes. In this paper, we
propose a novel episodic return decomposition method called Diaster (Difference
of implicitly assigned sub-trajectory reward). Diaster decomposes any episodic
reward into credits of two divided sub-trajectories at any cut point, and the
step-wise proxy rewards come from differences in expectation. We theoretically
and empirically verify that the decomposed proxy reward function can guide the
policy to be nearly optimal. Experimental results show that our method
outperforms previous state-of-the-art methods in terms of both sample
efficiency and performance.