Past Seminars - Spring 2021

Reinforcement Learning, Bit by Bit

Authors: Xiuyuan Lu, Benjamin Van Roy, Vikranth Dwaracherla, Morteza Ibrahimi, Ian Osband, Zheng Wen

Abstract: Reinforcement learning agents have demonstrated remarkable achievements in simulated environments. Data efficiency poses an impediment to carrying this success over to real environments. The design of data-efficient agents calls for a deeper understanding of information acquisition and representation. We develop concepts and establish a regret bound that together offer principled guidance. The bound sheds light on questions of what information to seek, how to seek that information, and it what information to retain. To illustrate concepts, we design simple agents that build on them and present computational results that demonstrate improvements in data efficiency.

Speaker Bio: Xiuyuan Lu is a research scientist at DeepMind. She is interested in developing data-efficient reinforcement learning agents. Before DeepMind, she graduated from Stanford University with a PhD in Operations Research under the supervision of Professor Benjamin Van Roy.

On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function

Authors: Gellért Weisz, Philip Amortila, Barnabás Janzer, Yasin Abbasi-Yadkori, Nan Jiang, Csaba Szepesvári

Abstract: We consider the problem of local planning in fixed-horizon Markov Decision Processes (MDPs) with a generative model under the assumption that the optimal value function lies in the span of a feature map that is accessible through the generative model. As opposed to previous work (e.g. Lattimore et al. (2020)) where linear realizability of all policies was assumed, we consider the significantly relaxed assumption of a single linearly realizable (deterministic) policy. A recent lower bound by Weisz et al. (2020) established that the related problem when the action-value function of the optimal policy is linearly realizable requires an exponential number of queries, either in H (the horizon of the MDP) or d (the dimension of the feature mapping). Their construction crucially relies on having an exponentially large action set. In contrast, in this work, we establish that poly(H, d) learning is possible (with state value function realizability) whenever the action set is small (i.e. O (1)). In particular, we present the TENSORPLAN algorithm which uses poly( (dH/δ)ᴬ) queries to find a δ-optimal policy relative to any deterministic policy for which the value function is linearly realizable with a parameter from a fixed radius ball around zero. This is the first algorithm to give a polynomial query complexity guarantee using only linear-realizability of a single competing value function. Whether the computation cost is similarly bounded remains an interesting open question. The upper bound is complemented by a lower bound which proves that in the infinite-horizon episodic setting, planners that achieve constant suboptimality need exponentially many queries, either in the dimension or the number of actions.

Speaker Bio: Gellért Weisz is a Ph.D. candidate at UCL/DeepMind, under the supervision of Prof. Csaba Szepesvári. He received his master's degree in machine learning from the University of Cambridge. His research interests lie in Reinforcement Learning theory. He is currently focused on the feasibility of efficient RL in the presence of low-dimensional linear structure.

Linear Systems can be Hard to Learn

Authors: Anastasios Tsiamis, George J. Pappas

Abstract: In this paper, we investigate when system identification is statistically easy or hard, in the finite sample regime. Statistically easy to learn linear system classes have sample complexity that is polynomial with the system dimension. Most prior research in the finite sample regime falls in this category, focusing on systems that are directly excited by process noise. Statistically hard to learn linear system classes have worst-case sample complexity that is at least exponential with the system dimension, regardless of the identification algorithm. Using tools from minimax theory, we show that classes of linear systems can be hard to learn. Such classes include, for example, under-actuated or under-excited systems with weak coupling among the states. Having classified some systems as easy or hard to learn, a natural question arises as to what system properties fundamentally affect the hardness of system identifiability. Towards this direction, we characterize how the controllability index of linear systems affects the sample complexity of identification. More specifically, we show that the sample complexity of robustly controllable linear systems is upper bounded by an exponential function of the controllability index. This implies that identification is easy for classes of linear systems with small controllability index and potentially hard if the controllability index is large. Our analysis is based on recent statistical tools for finite sample analysis of system identification as well as a novel lower bound that relates controllability index with the least singular value of the controllability Gramian.

Speaker Bio: Anastasios Tsiamis is a PhD student in the ESE department at the University of Pennsylvania, where he is advised by George Pappas. He received the Diploma degree in Electrical and Computer Engineering from the National Technical University of Athens, Greece. His research interests lie in the intersection of control theory and machine learning. In particular, his recent work focuses on understanding how fundamental control theoretic properties affect the difficulty of learning in system identification, online estimation and control. Previously, he worked on risk-aware control design and control systems security and privacy.

An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap

Authors: Yuanhao Wang, Ruosong Wang, Sham M. Kakade

Abstract: A fundamental question in the theory of reinforcement learning is: suppose the optimal Q-function lies in the linear span of a given d dimensional feature mapping, is sample-efficient reinforcement learning (RL) possible? The recent and remarkable result of Weisz et al. (2020) resolved this question in the negative, providing an exponential (in d) sample size lower bound, which holds even if the agent has access to a generative model of the environment. One may hope that this information theoretic barrier for RL can be circumvented by further supposing an even more favorable assumption: there exists a \emph{constant suboptimality gap} between the optimal Q-value of the best action and that of the second-best action (for all states). The hope is that having a large suboptimality gap would permit easier identification of optimal actions themselves, thus making the problem tractable; indeed, provided the agent has access to a generative model, sample-efficient RL is in fact possible with the addition of this more favorable assumption.

This work focuses on this question in the standard online reinforcement learning setting, where our main result resolves this question in the negative: our hardness result shows that an exponential sample complexity lower bound still holds even if a constant suboptimality gap is assumed in addition to having a linearly realizable optimal Q-function. Perhaps surprisingly, this implies an exponential separation between the online RL setting and the generative model setting. Complementing our negative hardness result, we give two positive results showing that provably sample-efficient RL is possible either under an additional low-variance assumption or under a novel hypercontractivity assumption (both implicitly place stronger conditions on the underlying dynamics model).

Speaker Bio: Yuanhao is a 1st year PhD student at the CS department at Princeton University. Before that, he completed his undergraduate studies at Institute for Interdisciplinary Information Sciences, Tsinghua University (a.k.a. Andrew Yao’s CS pilot class). His research interests include reinforcement learning and minimax optimization.

RL for Latent MDPs: Regret Guarantees and a Lower Bound

Authors: Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, Shie Mannor

Abstract: In this work, we consider the regret minimization problem for reinforcement learning in latent Markov Decision Processes (LMDP). In an LMDP, an MDP is randomly drawn from a set of M possible MDPs at the beginning of the interaction, but the identity of the chosen MDP is not revealed to the agent. We first show that a general instance of LMDPs requires at least \Omega((SA)^M) episodes to even approximate the optimal policy. Then, we consider sufficient assumptions under which learning good policies requires polynomial number of episodes. We show that the key link is a notion of separation between the MDP system dynamics. With sufficient separation, we provide an efficient algorithm with local guarantee, i.e., providing a sublinear regret guarantee when we are given a good initialization. Finally, if we are given standard statistical sufficiency assumptions common in the Predictive State Representation (PSR) literature (e.g., Boots et al.) and a reachability assumption, we show that the need for initialization can be removed.

Speaker Bio: Jeongyeol is a 4th year PhD candidate in the ECE department at The University of Texas at Austin. His research interests focus on robust decision-making in large-scale complex systems, with a focus on theoretical aspects of learning and computation. He has been particularly interested in efficient and practical algorithms for learning mixture and latent variable problems. He has been fascinated by the remarkable EM algorithm, and he have studied various aspects of its performance including its sample and minimax optimality for learning Gaussian mixtures and mixed linear regression. Jeongyeol is currently focusing on developing efficient reinforcement learning algorithms in partially observable domains. Jeongyeol is grateful for support from the Kwanjeong Educational Foundation Scholarship, and from the UT Continuing Graduate Fellowship.

Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature

Authors: Kefan Dong, Jiaqi Yang, Tengyu Ma

Abstract: This paper studies model-based bandit and reinforcement learning (RL) with nonlinear function approximations. We propose to study convergence to approximate local maxima because we show that global convergence is statistically intractable even for one-layer neural net bandit with a deterministic reward. For both nonlinear bandit and RL, the paper presents a model-based algorithm, Virtual Ascent with Online Model Learner (ViOL), which provably converges to a local maximum with sample complexity that only depends on the sequential Rademacher complexity of the model class. Our results imply novel global or local regret bounds on several concrete settings such as linear bandit with finite or sparse model class, and two-layer neural net bandit. A key algorithmic insight is that optimism may lead to over-exploration even for two-layer neural net model class. On the other hand, for convergence to local maxima, it suffices to maximize the virtual return if the model can also reasonably predict the size of the gradient and Hessian of the real return.

Speaker Bio: Kefan Dong is a first-year Ph.D. student at Computer Science Department, Stanford University, advised by Professor Tengyu Ma. Before that, he studied as an undergraduate at Institute for Interdisciplinary Information Sciences, Tsinghua University (a.k.a. Andrew Yao’s CS pilot class). His research interests are reinforcement learning and online learning.

A Primal Approach to Constrained Policy Optimization: Global Optimality and Finite-Time Analysis

Authors: Tengyu Xu, Yingbin Liang, Guanghui Lan

Abstract: Safe reinforcement learning (SRL) problems are typically modeled as constrained Markov Decision Process (CMDP), in which an agent explores the environment to maximize the expected total reward and meanwhile avoids violating certain constraints on a number of expected total costs. In general, such SRL problems have nonconvex objective functions subject to multiple nonconvex constraints, and hence are very challenging to solve, particularly to provide a globally optimal policy. Many popular SRL algorithms adopt a primal-dual structure which utilizes the updating of dual variables for satisfying the constraints. In contrast, we propose a primal approach, called constraint-rectified policy optimization (CRPO), which updates the policy alternatingly between objective improvement and constraint satisfaction. CRPO provides a primal-type algorithmic framework to solve SRL problems, where each policy update can take any variant of policy optimization step. To demonstrate the theoretical performance of CRPO, we adopt natural policy gradient (NPG) for each policy update step and show that CRPO achieves an convergence rate to the global optimal policy in the constrained policy set and an O(1/sqrt(T)) error bound on constraint satisfaction. This is the first finite-time analysis of SRL algorithms with global optimality guarantee. Our empirical results demonstrate that CRPO can outperform the existing primal-dual baseline algorithms significantly.

Speaker bio: Tengyu is a fourth year PhD student at the Department of Electrical and Computer Engineering, Ohio State University, advised by Yingbin Liang. Prior to OSU, he earned his B.Eng. in ME from Xi’an Jiaotong University. His research interests lie in the theoretical foundations of reinforcement learning and large-scale stochastic optimization. His current focus is in developing sample efficient reinforcement learning algorithms in various settings. In addition, he is also interested in the applications of reinforcement learning in autoML and NLP.

Model-free Representation Learning and Exploration in Low-rank MDPs

Authors: Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal

Abstract: The low rank MDP has emerged as an important model for studying representation learning and exploration in reinforcement learning. With a known representation, several model-free exploration strategies exist. In contrast, all algorithms for the unknown representation setting are model-based, thereby requiring the ability to model the full dynamics. In this work, we present the first model-free representation learning algorithms for low rank MDPs. The key algorithmic contribution is a new minimax representation learning objective, for which we provide variants with differing tradeoffs in their statistical and computational properties. We interleave this representation learning step with an exploration strategy to cover the state space in a reward-free manner. The resulting algorithms are provably sample efficient and can accommodate general function approximation to scale to complex environments.

Speaker bio: Aditya is a PhD candidate at the Computer Science and Engineering department in University of Michigan, Ann Arbor, advised by Satinder Singh and Ambuj Tewari. Before coming to Michigan, Aditya completed his undergraduate degree in Computer Science from Indian Institute of Technology, Kanpur in May 2016. His research interests lie in developing methods with provable guarantees for interactive learning and sequential decision making frameworks like reinforcement learning, bandits and (general) online learning. His current focus is on the sample efficiency of reinforcement learning methods under various structural assumptions. Additionally, Aditya has an active interest in real-world applications of reinforcement learning methods.

Adaptive Estimator Selection for Off-Policy Evaluation

Authors: Yi Su, Pavithra Srinath, Akshay Krishnamurthy

Abstract: We develop a generic data-driven method for estimator selection in off-policy policy evaluation settings. We establish a strong performance guarantee for the method, showing that it is competitive with the oracle estimator, up to a constant factor. Via in-depth case studies in contextual bandits and reinforcement learning, we demonstrate the generality and applicability of the method. We also perform comprehensive experiments, demonstrating the empirical efficacy of our approach and comparing with related approaches. In both case studies, our method compares favorably with existing methods.

Speaker bio: Yi is a PhD student in the Department of Statistics and Data Science at Cornell University, advised by Professor Thorsten Joachims and supported by a Bloomberg Data Science Ph.D. Fellowship. Previously, Yi received their BSc (Honors) in Mathematics from Nanyang Technological University in Singapore. During her undergraduate years, Yi spent a summer at University of California, Berkeley and a year at the Department of Statistics and Applied Probability, National University of Singapore. In Spring 2019, Yi worked as a Research Intern at the Machine Learning Group at Microsoft Research NYC, advised by Miro Dudik and Akshay Krishnamurthy. In Summer 2020, Yi worked as a Research Intern at Bloomberg AI. Yi is interested in machine learning methods, algorithms, and systems. Specifically she is interested in learning from user behavioral data and implicit feedback in search engines, recommender systems and market platforms. Yi's current interest lies in off-policy evaluation and learning in contextual bandits and reinforcement learning.

Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition

Authors: Liyu Chen, Haipeng Luo, Chen-Yu Wei

Abstract: We study the stochastic shortest path problem with adversarial costs and known transition, and show that the minimax regret is O˜(\sqrt{DT^⋆K}) and O˜(\sqrt{DT^⋆SAK}) for the full-information setting and the bandit feedback setting respectively, where D is the diameter, T^⋆ is the expected hitting time of the optimal policy, S is the number of states, A is the number of actions, and K is the number of episodes. Our results significantly improve upon the existing work of (Rosenberg and Mansour, 2020) which only considers the full-information setting and achieves suboptimal regret. Our work is also the first to consider bandit feedback with adversarial costs.

Our algorithms are built on top of the Online Mirror Descent framework with a variety of new techniques that might be of independent interest, including an improved multi-scale expert algorithm, a reduction from general stochastic shortest path to a special loop-free case, a skewed occupancy measure space, %the usage of log-barrier with an increasing learning rate schedule, and a novel correction term added to the cost estimators. Interestingly, the last two elements reduce the variance of the learner via positive bias and the variance of the optimal policy via negative bias respectively, and having them simultaneously is critical for obtaining the optimal high-probability bound in the bandit feedback setting.

Speaker bio: Liyu is a fourth year PhD student at University of Southern California. He is advised by Prof. Haipeng Luo. Liyu's research interests are in online learning and theory of reinforcement learning. Previously he did his bachelors at the Hong Kong Universiy of Science and Technology and did his final year thesis with Prof. Dit-Yan Yeung.

Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL

Authors: Andrea Zanette

Abstract: Several practical applications of reinforcement learning involve an agent learning from past data without the possibility of further exploration. Often these applications require us to 1) identify a near optimal policy or to 2) estimate the value of a target policy. For both tasks we derive \emph{exponential} information-theoretic lower bounds in discounted infinite horizon MDPs with a linear function representation for the action value function even if 1) \emph{realizability} holds, 2) the batch algorithm observes the exact reward and transition \emph{functions}, and 3) the batch algorithm is given the \emph{best} a priori data distribution for the problem class. Furthermore, if the dataset does not come from policy rollouts then the lower bounds hold even if the action-value function of \emph{every} policy admits a linear representation.

If the objective is to find a near-optimal policy, we discover that these hard instances are easily solved by an \emph{online} algorithm, showing that there exist RL problems where \emph{batch RL is exponentially harder than online RL} even under the most favorable batch data distribution. In other words, online exploration is critical to enable sample efficient RL with function approximation. A second corollary is the exponential separation between finite and infinite horizon batch problems under our assumptions. On a technical level, this work helps formalize the issue known as \emph{deadly triad} and explains that the \emph{bootstrapping} problem \citep{sutton2018reinforcement} is potentially more severe than the \emph{extrapolation} issue for RL because unlike the latter, bootstrapping cannot be mitigated by adding more samples.

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. Andreas research focuses on provably efficient methods for Reinforcement Learning, in particular, he develops agents capable of autonomous exploration. His research has been partially supported by Total. Before starting his PhD, Andrea was a master’s student in the same department, and his bachelors is in Mechanical Engineering from the University of Padova.