Reinforcement Learning for Non-Deterministic Transition Systems With an Application to Symbolic Control

Reinforcement learning (RL) is a well-established framework for the computation of optimal control policies maximizing the expected reward collected along the evolution of Markov decision processes. In this letter, we extend the RL framework to non-deterministic finite transition systems (FTSs), whose solutions are non-unique but not endowed with a probability measure. We show how to dynamically build RL controllers (possibly learning the FTS model just from experience) maximizing the best-case and worst-case return obtained from a trajectory (run) of the model, assuming full-state information. The framework is successfully applied to the case in which the considered transition system is obtained as a finite approximation of a continuous system, also called a symbolic model. Numerical results on the classical mountain car benchmark highlight the potential of the proposed approach.