Model-free reinforcement learning attempts to find an optimal control action for an unknown dynamical system by directly searching over the parameter space of controllers. The convergence behavior and statistical properties of these approaches are often poorly understood because of the nonconvex nature of the underlying optimization problems and the lack of exact gradient computation. In this talk, we discuss performance and efficiency of such methods by focusing on the standard infinite-horizon linear quadratic regulator problem for continuous-time systems with unknown state-space parameters. We establish exponential stability for the ordinary differential equation (ODE) that governs the gradient-flow dynamics over the set of stabilizing feedback gains and show that a similar result holds for the gradient descent method that arises from the forward Euler discretization of the corresponding ODE. We also provide theoretical bounds on the convergence rate and sample complexity of the random search method with two-point gradient estimates. We prove that the required simulation time for achieving $\epsilon$-accuracy in the model-free setup and the total number of function evaluations both scale as $\log (1/\epsilon)$.
Most literature on policy evaluation, bandit methods, etc., is focused on settings where actions taken on one unit do not affect other units. Such lack of interference, however, fails to hold in many applications of interest. For example, in a vaccine study, one person getting vaccinated also protects others; in a microcredit study, loans given to one person may stimulate the economy and indirectly benefit others; or, in a jobs-training study, training more people to perform a given task may create over-supply of qualified workers, thus reducing the market value of the training. In this talk, I'll survey various approaches to modeling cross-unit interference, and discuss associated methods for policy evaluation.
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. ℓ_∞ error) for unbounded state space. We need a new notion of performance metric. 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. 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 Monte Carlo Oracle with Lipschitz value. We also design an adaptive version of the algorithm, based on carefully constructed statistical tests, which finds the correct tuning parameter automatically.
This work is joint with Devavrat Shah and Zhi Xu.
