On the Theory of Reinforcement Learning with Once-per-Episode Feedback

The Reinforcement Learning (RL) paradigm involves a learning agent interacting with an unknown dynamical environment over multiple time steps. The learner receives a reward signal after each step which it uses to improve its performance over time. This formulation of RL has had significant empirical success in the recent past [Mni 15; Lev 16; Sil 17; Sen 20]. While this empirical success is encouraging, as RL starts to tackle a more wide-ranging class of consequential real-world problems, such as self-driving cars, supply chains, and medical care, a new set of challenges arise. Foremost among them is the lack of a well-specified reward signal associated with every state-action pair in many real-world settings. For example, consider a robot manipulation task where the robot must fold a pile of clothes. It is not clear how to design a useful reward signal that aids the robot to learn to complete this task. However, it is fairly easy to check whether the task was successfully completed (that is, whether the clothes were properly folded) and provide feedback at the end of the episode. This is a classical challenge but it is one that is often neglected in theoretical treatments of RL.