The SP problem and its special cases SSP and SLP are episodic reinforcement learning settings. When the horizon, the length of each episode is fixed and known, these problems have been extensively studied [1]}, [2]}, [3]}, [4]}, [5]}, [6]}. Among these work on finite-horizon tabular RL, the recent line of work on horizon-free algorithms [7]}, [6]}, [9]} is of particular interest. These works assume that rewards are non-negative and their cumulative sum are bounded by 1 and aim for regret that only incurs a logarithmic dependency on the horizon. Although many techniques developed there are useful for our setting as well, the SLP and general SP problem is more difficult since the reward sum is not bounded by 1, and there are potentially negative rewards.
