Past Seminars - Spring 2020

Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation

Authors: Yaqi Duan, Mengdi Wang

Abstract: This paper studies the statistical theory of batch data reinforcement learning with function approximation. Consider the off-policy evaluation problem, which is to estimate the cumulative value of a new target policy from logged history generated by unknown behavioral policies. We study a regression-based fitted Q iteration method, and show that it is equivalent to a model-based method that estimates a conditional mean embedding of the transition operator. We prove that this method is information-theoretically optimal and has nearly minimal estimation error. In particular, by leveraging contraction property of Markov processes and martingale concentration, we establish a finite-sample instance-dependent error upper bound and a nearly-matching minimax lower bound. The policy evaluation error depends sharply on a restricted χ²-divergence over the function class between the long-term distribution of the target policy and the distribution of past data. This restricted χ²-divergence is both instance-dependent and function-class-dependent. It characterizes the statistical limit of off-policy evaluation. Further, we provide an easily computable confidence bound for the policy evaluator, which may be useful for optimistic planning and safe policy improvement.

Speaker bio: Mengdi Wang is an associate professor at the Princeton University, and currently a visiting researcher at DeepMind. She received her PhD in Electrical Engineering and Computer Science from Massachusetts Institute of Technology in 2013, advised by Dimitri P. Bertsekas. Mengdi received the Young Researcher Prize in Continuous Optimization of the Mathematical Optimization Society in 2016 (awarded once every three years), the Princeton SEAS Innovation Award in 2016, the NSF Career Award in 2017, the Google Faculty Award in 2017, and the MIT Tech Review 35-Under-35 Innovation Award (China region) in 2018. Her research focuses on data-driven stochastic optimization and applications in machine and reinforcement learning.

Learning Near Optimal Policies with Low Inherent Bellman Error

Authors: Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, Emma Brunskill

Abstract: We study the exploration problem with approximate linear action-value functions in episodic reinforcement learning under the notion of low inherent Bellman error, a condition normally employed to show convergence of approximate value iteration. First we relate this condition to other common frameworks and show that it is strictly more general than the low rank (or linear) MDP assumption of prior work. Second we provide an algorithm with a high probability regret bound $\widetilde O(\sum_{t=1}^H d_t \sqrt{K} + \sum_{t=1}^H \sqrt{d_t} \IBE K)$ where $H$ is the horizon, $K$ is the number of episodes, $\IBE$ is the value if the inherent Bellman error and $d_t$ is the feature dimension at timestep $t$. In addition, we show that the result is unimprovable beyond constants and logs by showing a matching lower bound. This has two important consequences: 1) the algorithm has the optimal statistical rate for this setting which is more general than prior work on low-rank MDPs 2) the lack of closedness (measured by the inherent Bellman error) is only amplified by $\sqrt{d_t}$ despite working in the online setting. Finally, the algorithm reduces to the celebrated LinUCB when $H=1$ but with a different choice of the exploration parameter that allows handling misspecified contextual linear bandits. While computational tractability questions remain open for the MDP setting, this enriches the class of MDPs with a linear representation for the action-value function where statistically efficient reinforcement learning is possible.

Speaker bio: Andrea is a PhD candidate in the Institute for Computational and Mathematical Engineering at Stanford University advised by prof Emma Brunskill and Mykel J. Kochenderfer. He also works closely with Alessandro Lazaric from Facebook Artificial Intelligence Research. His research focuses on provably efficient methods for Reinforcement Learning, in particular, he develop agents capable of autonomous exploration. His research is currently supported by Total.

Improper Learning for Non-Stochastic Control

Authors: Max Simchowitz, Karan Singh, Elad Hazan

Abstract: We consider the problem of controlling a possibly unknown linear dynamical system with adversarial perturbations, adversarially chosen convex loss functions, and partially observed states, known as non-stochastic control. We introduce a controller parametrization based on the denoised observations, and prove that applying online gradient descent to this parametrization yields a new controller which attains sublinear regret vs. a large class of closed-loop policies. In the fully-adversarial setting, our controller attains an optimal regret bound of sqrt(T) when the system is known, and, when combined with an initial stage of least-squares estimation, T^{2/3} when the system is unknown; both yield the first sublinear regret for the partially observed setting. Our bounds are the first in the non-stochastic control setting that compete with all stabilizing linear dynamical controllers, not just state feedback. Moreover, in the presence of semi-adversarial noise containing both stochastic and adversarial components, our controller attains the optimal regret bounds of polylog(T) when the system is known, and sqrt(T) when unknown. To our knowledge, this gives the first end-to-end sqrt(T) regret for online Linear Quadratic Gaussian controller, and applies in a more general setting with adversarial losses and semi-adversarial noise.

Speaker bio: Max Simchowitz is a year PhD student in the EECS department at UC Berkeley, co-adivsed by Ben Recht and Michael Jordan. He is currently supported by an Open Philanthropy fellowship, and in the past has received support from an NSF GRFP grant and a Berkeley Fellowship. His recent work focuses on the theoretical foundations of online linear control and reinforcement learning, with past research ranging broadly across topics in adaptive sampling, multi-arm bandits, complexity of convex and non-convex optimization, and fairness in machine learning.

A Unified Switching System Perspective and O.D.E. Analysis of Q-Learning Algorithms

Authors: Donghwan Lee, Niao He

Abstract: In this paper, we introduce a unified framework for analyzing a large family of Q-learning algorithms, based on switching system perspectives and ODE-based stochastic approximation. We show that the nonlinear ODE models associated with these Q-learning algorithms can be formulated as switched linear systems, and analyze their asymptotic stability by leveraging existing switching system theories. Our approach provides the first O.D.E. analysis of the asymptotic convergence of various Q-learning algorithms, including asynchronous Q-learning and averaging Q-learning. We also extend the approach to analyze Q-learning with linear function approximation and derive a new sufficient condition for its convergence.

Speaker bio: Niao He is currently an Assistant Professor in the Department of Industrial and Enterprise Systems Engineering (ISE) at the University of Illinois at Urbana-Champaign (UIUC). She is also affiliated with the Department of Electrical & Computer Engineering and Coordinated Science Laboratory (CSL). She received a Ph.D. in Operations Research under the supervision of Arkadi Nemirovski at Georgia Institute of Technology in 2015 and B.S. in Mathematics at the University of Science and Technology of China in 2010. Niao's research interest lie in the interface of optimization and machine learning, with a primary focus on developing fast algorithms and theoretical analyses for large-scale optimization problems that stem from big data applications in machine learning, signal processing, statistical inference, reinforcement learning, healthcare analytics, financial engineering, and etc.

Q-Learning with Uniformly Bounded Variance: Large Discounting Is Not a Barrier to Fast Learning

Authors: Adithya M. Devraj, Sean P. Meyn

Abstract: Sample complexity bounds are a common performance metric in the Reinforcement Learning literature. In the discounted cost, infinite horizon setting, all of the known bounds have a factor that is a polynomial in 1/(1 − β), where β < 1 is the discount factor. For a large discount factor, these bounds seem to imply that a very large number of samples is required to achieve an ε-optimal policy. The objective of the present work is to introduce a new class of algorithms that have sample complexity uniformly bounded for all β < 1. One may argue that this is impossible, due to a recent min-max lower bound. The explanation is that this previous lower bound is for a specific problem, which we modify, without compromising the ultimate objective of obtaining an ε-optimal policy. Specifically, we show that the asymptotic variance of the Q-learning algorithm with an optimized step-size sequence is a quadratic function of 1/(1 − β); an expected, and essentially known result. The new relative Q-learning algorithm proposed here is shown to have asymptotic variance that is a quadratic in 1/(1 − ρ∗β), where 1 − ρ∗ > 0 is an upper bound on the spectral gap of an optimal transition matrix.

Speaker bio: Adithya is a postdoc at Stanford University, where he is working with Prof. Benjamin Van Roy. Before arriving at Stanford, he obtained his PhD in December 2019 from University of Florida, Gainesville, where he worked with Prof. Sean Meyn. His dissertation was on designing Reinforcement Learning algorithms with optimal variance.

On the Sample Complexity of the Linear Quadratic Regulator

Authors: Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, Stephen Tu

Abstract: This paper addresses the optimal control problem known as the Linear Quadratic Regulator in the case when the dynamics are unknown. We propose a multi-stage procedure, called Coarse-ID control, that estimates a model from a few experimental trials, estimates the error in that model with respect to the truth, and then designs a controller using both the model and uncertainty estimate. Our technique uses contemporary tools from random matrix theory to bound the error in the estimation procedure. We also employ a recently developed approach to control synthesis called System Level Synthesis that enables robust control design by solving a convex optimization problem. We provide end-to-end bounds on the relative error in control cost that are nearly optimal in the number of parameters and that highlight salient properties of the system to be controlled such as closed-loop sensitivity and optimal control magnitude. We show experimentally that the Coarse-ID approach enables efficient computation of a stabilizing controller in regimes where simple control schemes that do not take the model uncertainty into account fail to stabilize the true system.

Speaker bio: Sarah Dean is a PhD candidate in the Department of Electrical Engineering and Computer Science at UC Berkeley, where she is advised by Ben Recht. She received her BSE in electrical engineering and mathematics from the University of Pennsylvania in 2016. Sarah is broadly interested in designing methods for and understanding the implications of data-driven optimization. She has worked specifically on topics in optimal control, machine learning, and computational imaging, with motivating applications in robotics and recommender systems.

Provably Efficient Reinforcement Learning with Linear Function Approximation

Authors: Chi Jin, Zhuoran Yang, Zhaoran Wang, Michael I. Jordan

Abstract: Modern Reinforcement Learning (RL) is commonly applied to practical problems with an enormous number of states, where function approximation must be deployed to approximate either the value function or the policy. The introduction of function approximation raises a fundamental set of challenges involving computational and statistical efficiency, especially given the need to manage the exploration/exploitation tradeoff. As a result, a core RL question remains open: how can we design provably efficient RL algorithms that incorporate function approximation? This question persists even in a basic setting with linear dynamics and linear rewards, for which only linear function approximation is needed.

This paper presents the first provable RL algorithm with both polynomial runtime and polynomial sample complexity in this linear setting, without requiring a "simulator" or additional assumptions. Concretely, we prove that an optimistic modification of Least-Squares Value Iteration (LSVI)---a classical algorithm frequently studied in the linear setting---achieves $\tilde O( \sqrt{d^3 H^3 T)$ regret, where d is the ambient dimension of feature space, H is the length of each episode, and T is the total number of steps. Importantly, such regret is independent of the number of states and actions.

Speaker Bio: Chi Jin is assistant professor of Electrical Engineering at Princeton University. He obtained his Ph.D. in Computer Science at UC Berkeley, advised by Michael I. Jordan. He received his B.S. in Physics from Peking University. His research interest lies in theoretical machine learning, with special emphases on nonconvex optimization and reinforcement learning. His representative work includes proving noisy gradient descent / accelerated gradient descent escape saddle points efficiently, proving sample complexity bounds for Q-learning / LSVI with UCB, and designing near-optimal algorithms for minimax optimization. He is the recipient of the best paper award in the ICML 2018 workshop on "Exploration in Reinforcement Learning".