State-free Reinforcement Learning

In this work, we study the $\mathit{\text{state-free}}\mathit{\text{RL}}$ problem, where the algorithm does not have the states information before interacting with the environment. Specifically, denote the reachable state set by $S^{\mathrm{\Pi }}:=\{s\mathrm{\mid }{\max }_{\pi \in \mathrm{\Pi }}{q}^{P,\pi }(s)>0\}$, we design an algorithm which requires no information on the state space $S$ while having a regret that is completely independent of $S$ and only depend on $S^{\mathrm{\Pi }}$. We view this as a concrete first step towards $\mathit{\text{parameter-free}}\mathit{\text{RL}}$, with the goal of designing RL algorithms that require no hyper-parameter tuning.