Provably efficient large-scale reinforcement learning via primal-dual stochastic optimization

Abstract

Real-world sequential decision-making tasks are often characterized by large state spaces and unknown dynamics. In this setting, an efficient method is tasked to learn a near-optimal decision-making policy under a given sample-access model, with time and sample complexity that is independent of the size of the state space. To this end, we study reinforcement learning in large Markov Decision Processes (MDPs), with intractably many states, under a variety of sample-access models. We provide both time- and sample-efficient methods with provable performance guarantees in the contexts of planning with a generative model and offline reinforcement learning with a static dataset. Our approach taken in this thesis is firmly rooted in the classic linear programming formulation of MDPs first introduced in the 1960's. In each context, starting from the approximate linear programs based on linear function approximation, we introduce techniques to further reduce the problem dimension and enable efficient learning. Thereafter, we develop algorithms via (stochastic) primal-dual optimization of the reduced approximate linear programs, and under assumptions on the function approximator and MDP, derive timeand sample-complexity guarantees by studying the corresponding duality gap. Along the way, we contribute to the rich literature on stochastic optimization of convex-concave functions in unconstrained domains.

Las tareas de toma de decisiones secuenciales en el mundo real suelen caracterizarse por grandes espacios de estados y dinámicas desconocidas. En este contexto, la tarea de un método eficiente es aprender una política de toma de decisiones casi óptima bajo un modelo de acceso muestral dado, con una complejidad temporal y muestral independiente del tamaño del espacio de estados. Con este fin, estudiamos el aprendizaje por refuerzo en Procesos de Decisión de Markov (MDP) de gran tamaño, con un número intratable de estados, bajo una variedad de modelos de acceso muestral. Proporcionamos métodos eficientes tanto en tiempo como en muestras con garantías de rendimiento demostrables en los contextos de la planificación con un modelo generativo y el aprendizaje por refuerzo offline con un conjunto de datos estático. El enfoque adoptado en esta tesis está firmemente arraigado en la formulación clásica de programación lineal de los MDP introducida por primera vez en la década de 1960. En cada contexto, partiendo de los programas lineales aproximados basados en la aproximación de funciones lineales, introducimos técnicas para reducir aún más la dimensión del problema y permitir un aprendizaje eficiente. Posteriormente, desarrollamos algoritmos a través de la optimización (estocástica) primal-dual de los programas lineales aproximados reducidos y, bajo supuestos sobre el aproximador de funciones y el MDP, derivamos garantías de complejidad temporal y muestral mediante el estudio de la brecha de dualidad correspondiente. A lo largo del camino, contribuimos a la rica literatura sobre optimización estocástica de funciones convexo-cóncavas en dominios sin restricciones.