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

Reinforcement learning (RL) is a wellestablishedframework for the computation of optimalcontrol policies maximizing the expected reward collectedalong the evolution of Markov decision processes. In thisletter, we extend the RL framework to non-deterministicfinite transition systems (FTSs), whose solutions arenon-unique but not endowed with a probability measure.We show how to dynamically build RL controllers (possiblylearning the FTS model just from experience) maximizingthe 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 whichthe considered transition system is obtained as a finiteapproximation of a continuous system, also called a symbolicmodel. Numerical results on the classical mountaincar benchmark highlight the potential of the proposedapproach.