Abstract: In this work, we study the \textit{state-free RL} problem, where the algorithm does not have the states information before interacting with the environment. Specifically, denote the reachable state set by ${\mathcal{S}}^{\mathrm{\Pi }}:=\{s|\underset{\pi \in \mathrm{\Pi }}{max}{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 $\mathcal{S}$ and only depend on ${\mathcal{S}}^{\mathrm{\Pi }}$. We view this as a concrete first step towards \textit{parameter-free RL}, with the goal of designing RL algorithms that require no hyper-parameter tuning.