Past Seminars - Autumn 2021

Fast Rates for the Regret of Offline Reinforcement Learning

Authors: Yichun Hu, Nathan Kallus, Masatoshi Uehara

Abstract: We study the regret of reinforcement learning from offline data generated by a fixed behavior policy in an infinite-horizon discounted Markov decision process (MDP). While existing analyses of common approaches, such as fitted Q-iteration (FQI), suggest a O(1/sqrt{n}) convergence for regret, empirical behavior exhibits much faster convergence. In this paper, we present a finer regret analysis that exactly characterizes this phenomenon by providing fast rates for the regret convergence. First, we show that given any estimate for the optimal quality function Q^*, the regret of the policy it defines converges at a rate given by the exponentiation of the Q^*-estimate's pointwise convergence rate, thus speeding it up. The level of exponentiation depends on the level of noise in the decision-making problem, rather than the estimation problem. We establish such noise levels for linear and tabular MDPs as examples. Second, we provide new analyses of FQI and Bellman residual minimization to establish the correct pointwise convergence guarantees. As specific cases, our results imply O(1/n) regret rates in linear cases and exp(-Omega(n)) regret rates in tabular cases.

Speaker Bio: Yichun is a PhD candidate in Operations Research at Cornell University, advised by Professor Nathan Kallus. She is broadly interested in data-driven decision making problems, including but not limited to contextual bandits, reinforcement learning and stochastic optimization.

Optimal policy evaluation using kernel-based temporal difference methods

Authors: Yaqi Duan, Mengdi Wang, Martin J. Wainwright

Abstract: We study methods based on reproducing kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process (MRP). We study a regularized form of the kernel least-squares temporal difference (LSTD) estimate; in the population limit of infinite data, it corresponds to the fixed point of a projected Bellman operator defined by the associated reproducing kernel Hilbert space. The estimator itself is obtained by computing the projected fixed point induced by a regularized version of the empirical operator; due to the underlying kernel structure, this reduces to solving a linear system involving kernel matrices. We analyze the error of this estimate in the L^2(mu)-norm, where denotes the stationary distribution of the underlying Markov chain. Our analysis imposes no assumptions on the transition operator of the Markov chain, but rather only conditions on the reward function and population-level kernel LSTD solutions. We use empirical process theory techniques to derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator, as well as the instance-dependent variance of the Bellman residual error. In addition, we prove minimax lower bounds over sub-classes of MRPs, which shows that our rate is optimal in terms of the sample size and the effective horizon H=(1-gamma)^{-1}. Whereas existing worst-case theory predicts cubic scaling (H^3) in the effective horizon, our theory reveals that there is in fact a much wider range of scalings, depending on the kernel, the stationary distribution, and the variance of the Bellman residual error. Notably, it is only parametric and near-parametric problems that can ever achieve the worst-case cubic scaling.

Speaker Bio: Martin Wainwright joined the faculty at University of California at Berkeley in Fall 2004, and is currently a Chancellor's Professor with a joint appointment between the Department of Statistics and the Department of Electrical Engineering and Computer Sciences. He received his Bachelor's degree in Mathematics from University of Waterloo, Canada, and his Ph.D. degree in Electrical Engineering and Computer Science (EECS) from Massachusetts Institute of Technology (MIT), for which he was awarded the George M. Sprowls Prize from the MIT EECS department in 2002. He is interested in high-dimensional statistics, information theory and statistics, and statistical machine learning. He has received an Alfred P. Sloan Foundation Research Fellowship (2005), IEEE Best Paper Awards from the Signal Processing Society (2008) and Communications Society (2010); the Joint Paper Award from IEEE Information Theory and Communication Societies (2012); a Medallion Lecturer (2013) of the Institute for Mathematical Statistics; a Section Lecturer at the International Congress of Mathematicians (2014); and the COPSS Presidents' Award in Statistics (2014). He is currently serving as an Associate Editor for the Annals of Statistics, Journal of Machine Learning Research, Journal of the American Statistical Association, and Journal of Information and Inference.

Efficient Performance Bounds for Primal-Dual Reinforcement Learning from Demonstrations

Authors: Angeliki Kamoutsi, Goran Banjac, John Lygeros

Abstract: We consider large-scale Markov decision processes with an unknown cost function and address the problem of learning a policy from a finite set of expert demonstrations. We assume that the learner is not allowed to interact with the expert and has no access to reinforcement signal of any kind. Existing inverse reinforcement learning methods come with strong theoretical guarantees, but are computationally expensive, while state-of-the-art policy optimization algorithms achieve significant empirical success, but are hampered by limited theoretical understanding. To bridge the gap between theory and practice, we introduce a novel bilinear saddle-point framework using Lagrangian duality. The proposed primal-dual viewpoint allows us to develop a model-free provably efficient algorithm through the lens of stochastic convex optimization. The method enjoys the advantages of simplicity of implementation, low memory requirements, and computational and sample complexities independent of the number of states. We further present an equivalent no-regret online-learning interpretation.

Speaker Bio: Angeliki Kamoutsi is a PhD student in the Automatic Control Laboratory at ETH Zürich, under the supervision of Prof. John Lygeros. Her research interests lie in reinforcement learning theory. In particular, the overall goal of her PhD work is to combine modern stochastic optimization and statistical learning theory tools for the design of provably efficient algorithms for inverse reinforcement learning. Previously, Angeliki completed a Master's degree in Mathematics at ETH Zurich and a Diploma degree in Applied Mathematics and Physics at the National Technical University of Athens.

Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes

Authors: Dongruo Zhou, Quanquan Gu, Csaba Szepesvari

Abstract: We study reinforcement learning (RL) with linear function approximation where the underlying transition probability kernel of the Markov decision process (MDP) is a linear mixture model (Jia et al., 2020; Ayoub et al., 2020; Zhou et al., 2020) and the learning agent has access to either an integration or a sampling oracle of the individual basis kernels. We propose a new Bernstein-type concentration inequality for self-normalized martingales for linear bandit problems with bounded noise. Based on the new inequality, we propose a new, computationally efficient algorithm with linear function approximation named UCRL-VTR+ for the aforementioned linear mixture MDPs in the episodic undiscounted setting. We show that UCRL-VTR+ attains an Õ (dH\sqrt{T}) regret where d is the dimension of feature mapping, H is the length of the episode and T is the number of interactions with the MDP. We also prove a matching lower bound Ω(dH\sqrt{T}) for this setting, which shows that UCRL-VTR+ is minimax optimal up to logarithmic factors. In addition, we propose the UCLK+ algorithm for the same family of MDPs under discounting and show that it attains an Õ (d\sqrt{T}/(1−γ)^1.5) regret, where γ∈[0,1) is the discount factor. Our upper bound matches the lower bound Ω(d\sqrt{T}/(1−γ)^1.5) proved by Zhou et al. (2020) up to logarithmic factors, suggesting that UCLK+ is nearly minimax optimal. To the best of our knowledge, these are the first computationally efficient, nearly minimax optimal algorithms for RL with linear function approximation.

Speaker Bio: Dongruo is a third-year PhD student at Department of Computer Science, University of California, Los Angeles, advised by Prof. Quanquan Gu. Previously he obtained my B.Sc from Department of Mathematics Science, Tsinghua University. After that, Dongruo spent one year at Department of System and Information Engineering (Engineering Systems and Environment), University of Virginia. Dongruos research interests are about optimization, reinforcement learning and machine learning. He is interested in designing provable new stochastic algorithms based on classical first-order or high-order deterministic algorithms. He is also interested in understanding basic limitations for different classes of algorithms.

Bilinear Classes: A Structural Framework for Provable Generalization in RL

Authors: Simon S. Du, Sham M. Kakade, Jason D. Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, Ruosong Wang

Abstract: This work introduces Bilinear Classes, a new structural framework, which permit generalization in reinforcement learning in a wide variety of settings through the use of function approximation. The framework incorporates nearly all existing models in which a polynomial sample complexity is achievable, and, notably, also includes new models, such as the Linear Q∗/V∗ model in which both the optimal Q-function and the optimal V-function are linear in some known feature space. Our main result provides an RL algorithm which has polynomial sample complexity for Bilinear Classes; notably, this sample complexity is stated in terms of a reduction to the generalization error of an underlying supervised learning sub-problem. These bounds nearly match the best known sample complexity bounds for existing models. Furthermore, this framework also extends to the infinite dimensional (RKHS) setting: for the the Linear Q∗/V∗ model, linear MDPs, and linear mixture MDPs, we provide sample complexities that have no explicit dependence on the explicit feature dimension (which could be infinite), but instead depends only on information theoretic quantities.

Speaker Bio: Gaurav is a 4th year PhD student in the theory group at UCSD, where he is advised by Sanjoy Dasgupta and Shachar Lovett. Before that, he worked at Microsoft for three years. Gaurav received a BS and MS in Mathematics and Computing from Indian Institute of Technology, Delhi (IITD) advised by Subiman Kundu. In Summer 2021, he was a research intern working with Sham Kakade and Akshay Krishnamurthy at Microsoft Research, New York. Prior to that he has also worked with Jason Lee at Institute for Advanced Study and the Simons Institute. Gaurav is broadly interested in questions related to learning and has recently worked on problems related to reinforcement learning, active learning and unsupervised learning.