Adaptive Discretization-based Non-Episodic Reinforcement Learning in Metric Spaces

We study non-episodic Reinforcement Learning for Lipschitz MDPs in which state-action space is a metric space, and the transition kernel and rewards are Lipschitz functions. We develop computationally efficient UCB-based algorithm, ZoRL-ε that adaptively discretizes the state-action space and show that their regret as compared with ε-optimal policy is bounded as O(ε-(2 dS + d^εz + 1)log(T)), where d^εz is the ε-zooming dimension. In contrast, if one uses the vanilla UCRL-2 on a fixed discretization of the MDP, the regret w.r.t. a ε-optimal policy scales as O(ε-(2 dS + d + 1)log(T)) so that the adaptivity gains are huge when d^εz d. Note that the absolute regret of any 'uniformly good' algorithm for a large family of continuous MDPs asymptotically scales as at least Ω(log(T)). Though adaptive discretization has been shown to yield Õ(H2.5Kᵈz + 1/dz + 2) regret in episodic RL, an attempt to extend this to the non-episodic case by employing constant duration episodes whose duration increases with T, is futile since dz → d as T → ∞. The current work shows how to obtain adaptivity gains for non-episodic RL. The theoretical results are supported by simulations on two systems where the performance of ZoRL-ε is compared with that of 'UCRL-C,' the fixed discretization-based extension of UCRL-2 for systems with continuous state-action spaces.