  We consider the problem of reinforcement learning (RL) with unbounded state
space motivated by the classical problem of scheduling in a queueing network.
Traditional policies as well as error metric that are designed for finite,
bounded or compact state space, require infinite samples for providing any
meaningful performance guarantee (e.g. $\ell_\infty$ error) for unbounded state
space. That is, we need a new notion of performance metric. As the main
contribution of this work, inspired by the literature in queuing systems and
control theory, we propose stability as the notion of "goodness": the state
dynamics under the policy should remain in a bounded region with high
probability. As a proof of concept, we propose an RL policy using
Sparse-Sampling-based Monte Carlo Oracle and argue that it satisfies the
stability property as long as the system dynamics under the optimal policy
respects a Lyapunov function. The assumption of existence of a Lyapunov
function is not restrictive as it is equivalent to the positive recurrence or
stability property of any Markov chain, i.e., if there is any policy that can
stabilize the system then it must possess a Lyapunov function. And, our policy
does not utilize the knowledge of the specific Lyapunov function. To make our
method sample efficient, we provide an improved, sample efficient
Sparse-Sampling-based Monte Carlo Oracle with Lipschitz value function that may
be of interest in its own right. Furthermore, we design an adaptive version of
the algorithm, based on carefully constructed statistical tests, which finds
the correct tuning parameter automatically.
