Reinforcement Learning Theory
Jun 11, 2019
Speakers
Adrien Ali Taiga
Speaker · 0 followers
Ahmed Touati
Speaker · 0 followers
Andrea Zanette
Speaker · 0 followers
Anna Harutyunyan
Speaker · 0 followers
Ben London
Speaker · 0 followers
Bruno Scherrer
Speaker · 0 followers
Chen Tessler
Speaker · 0 followers
Christoph Dann
Speaker · 0 followers
Dale Schuurmans
Speaker · 2 followers
David Abel
Speaker · 1 follower
Doina Precup
Speaker · 17 followers
Emma Brunskill
Speaker · 13 followers
George Konidaris
Speaker · 1 follower
Georgios Theocharous
Speaker · 0 followers
James Kostas
Speaker · 0 followers
Jee Won Park
Speaker · 0 followers
Joelle Pineau
Speaker · 5 followers
Joshua Romoff
Speaker · 0 followers
Marc Bellemare
Speaker · 3 followers
Matthieu Geist
Speaker · 0 followers
Nicolas Le Roux
Speaker · 0 followers
Olivier Pietquin
Speaker · 0 followers
Peter Henderson
Speaker · 0 followers
Peter Vrancx
Speaker · 0 followers
Philip S. Thomas
Speaker · 1 follower
Philippe Hamel
Speaker · 0 followers
Robert Dadashi
Speaker · 0 followers
Scott M. Jordan
Speaker · 0 followers
Shie Mannor
Speaker · 1 follower
Ted Sandler
Speaker · 0 followers
Yann Ollivier
Speaker · 0 followers
Yash Chandak
Speaker · 0 followers
Yonathan Efroni
Speaker · 0 followers
Yuu Jinnai
Speaker · 0 followers
About
Separable value functions across time-scales In many finite horizon episodic reinforcement learning (RL) settings, it is desirable to optimize for the undiscounted return - in settings like Atari, for instance, the goal is to collect the most points while staying alive in the long run. Yet, it may be difficult (or even intractable) mathematically to learn with this target. As such, temporal discounting is often applied to optimize over a shorter effective planning horizon. This comes at the cost of potentially biasing the optimization target away from the undiscounted goal. In settings where this bias is unacceptable - where the system must optimize for longer horizons at higher discounts - the target of the value function approximator may increase in variance leading to difficulties in learning. We present an extension of temporal difference (TD) learning, which we call TD( Δ), that breaks down a value function into a series of components based on the differences between value functions with smaller discount factors. The separation of a longer horizon value function into these components has useful properties in scalability and performance. We discuss these properties and show theoretic and empirical improvements over standard TD learning in certain settings. Learning Action Representations for Reinforcement Learning Most model-free reinforcement learning methods leverage state representations (embeddings) for generalization, but either ignore structure in the space of actions or assume the structure is provided a priori. We show how a policy can be decomposed into a component that acts in a low-dimensional space of action representations and a component that transforms these representations into actual actions. These representations improve generalization over large, finite action sets by allowing the agent to infer the outcomes of actions similar to actions already taken. We provide an algorithm to both learn and use action representations and provide conditions for its convergence. The efficacy of the proposed method is demonstrated on large-scale real-world problems. Bayesian Counterfactual Risk Minimization We present a Bayesian view of counterfactual risk minimization (CRM), also known as offline policy optimization from logged bandit feedback. Using PAC-Bayesian analysis, we derive a new generalization bound for the truncated IPS estimator. We apply the bound to a class of Bayesian policies, which motivates a novel, potentially data-dependent, regularization technique for CRM. Experimental results indicate that this technique outperforms standard L2 regularization, and that it is competitive with variance regularization while being both simpler to implement and more computationally efficient. Per-Decision Option Discounting In order to solve complex problems, an agent must be able to reason over a sufficiently long horizon. Temporal abstraction, commonly modeled through options, offers the ability to reason at many time scales, but the horizon length is still determined by the single discount factor of the underlying Markov Decision Process. We propose a modification to the options framework that allows the agent’s horizon to grow naturally as its actions become more complex and extended in time. We show that the proposed option-step discount controls a bias-variance trade-off, with larger discounts (counter-intuitively) leading to less estimation variance. Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds Strong worst-case performance bounds for episodic reinforcement learning exist but fortunately in practice RL algorithms perform much better than such bounds would predict. Algorithms and theory that provide strong problem-dependent bounds could help illuminate the key features of what makes a RL problem hard and reduce the barrier to using RL algorithms in practice. As a step towards this we derive an algorithm and analysis for finite horizon discrete MDPs with state-of-the-art worst-case regret bounds and substantially tighter bounds if the RL environment has special features but without apriori knowledge of the environment from the algorithm. As a result of our analysis, we also help address an open learning theory question~\cite{jiang2018open} about episodic MDPs with a constant upper-bound on the sum of rewards, providing a regret bound function of the number of episodes with no dependence on the horizon. A Theory of Regularized Markov Decision Processes Many recent successful (deep) reinforcement learning algorithms make use of regularization, generally based on entropy or on Kullback-Leibler divergence. We propose a general theory of regularized Markov Decision Processes that generalizes these approaches in two directions: we consider a larger class of regularizers, and we consider the general modified policy iteration approach, encompassing both policy iteration and value iteration. The core building blocks of this theory are a notion of regularized Bellman operator and the Legendre-Fenchel transform, a classical tool of convex optimizatoin. This approach allows for error propagation analyses of general algorithmic schemes of which (possibly variants of) classical algorithms such as Trust Region Policy Optimization, Soft Q-learning, Stochastic Actor Critic or Dynamic Policy Programming are special cases. This also draws connections to proximal convex optimization, especially to Mirror Descent. Discovering Options for Exploration by Minimizing Cover Time One of the main challenges in reinforcement learning is on solving tasks with sparse reward. We first show that the difficulty of discovering the rewarding state is bounded by the expected cover time of the underlying random walk induced by a policy. We propose a method to discover options automatically which reduce the cover time so as to speed up the exploration in sparse reward domains. We show empirically that the proposed algorithm successfully reduces the cover time, and improves the performance of the reinforcement learning agents. Policy Certificates: Towards Accountable Reinforcement Learning The performance of a reinforcement learning algorithm can vary drastically during learning because of exploration. Existing algorithms provide little information about the quality of their current policy before executing it, and thus have limited use in high-stakes applications, such as healthcare. We address this lack of accountability by proposing that algorithms output policy certificates. These certificates bound the sub-optimality and return of the policy in the next episode, allowing humans to intervene when the certified quality is not satisfactory. We further introduce two new algorithms with certificates and present a new framework for theoretical analysis that guarantees the quality of their policies and certificates. For tabular MDPs, we show that computing certificates can even improve the sample-efficiency of optimism-based exploration. As a result, one of our algorithms achieves regret and PAC bounds that are tighter than state of the art and minimax up to lower-order terms. Action Robust Reinforcement Learning and Applications in Continuous Control A policy is said to be robust if it maximizes the reward while considering a bad, or even adversarial, model. In this work we formalize two new criteria of robustness to action uncertainty. Specifically, we consider two scenarios in which the agent attempts to perform an action \action, and (i) with probability α, an alternative adversarial action ¯\action is taken, or (ii) an adversary adds a perturbation to the selected action in the case of continuous action space. We show that our criteria are related to common forms of uncertainty in robotics domains, such as the occurrence of abrupt forces, and suggest algorithms in the tabular case. Building on the suggested algorithms, we generalize our approach to deep reinforcement learning (DRL) and provide extensive experiments in the various MuJoCo domains. Our experiments show that not only does our approach produce robust policies, but it also improves the performance in the absence of perturbations. This generalization indicates that action-robustness can be thought of as implicit regularization in RL problems. The Value Function Polytope in Reinforcement Learning We establish geometric and topological properties of the space of value functions in finite state-action Markov decision processes. Our main contribution is the characterization of the nature of its shape: a general polytope \cite{aigner2010proofs}. To demonstrate this result, we exhibit several properties of the structural relationship between policies and value functions including the line theorem, which shows that the value functions of policies constrained on all but one state describe a line segment. Finally, we use this novel perspective and introduce visualizations to enhance the understanding of the dynamics of reinforcement learning algorithms.Separable value functions across time-scales In many finite horizon episodic reinforcement learning (RL) settings, it is desirable to optimize for the undiscounted return - in settings like Atari, for instance, the goal is to collect the most points while staying alive in the long run. Yet, it may be difficult (or even intractable) mathematically to learn with this target. As such, temporal discounting is often applied to optimize over a shorter effective planning horizon. This comes at the cost…
Categories
AI & Data Science
Category · 10.8k presentations
Mathematics
Category · 2.4k presentations
About ICML 2019
The International Conference on Machine Learning (ICML) is the premier gathering of professionals dedicated to the advancement of the branch of artificial intelligence known as machine learning. ICML is globally renowned for presenting and publishing cutting-edge research on all aspects of machine learning used in closely related areas like artificial intelligence, statistics and data science, as well as important application areas such as machine vision, computational biology, speech recognition, and robotics. ICML is one of the fastest growing artificial intelligence conferences in the world. Participants at ICML span a wide range of backgrounds, from academic and industrial researchers, to entrepreneurs and engineers, to graduate students and postdocs.
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Real-World Sequential Decision Making - Panel Discussion
Watch later
Dawn Woodard, …
Fairness
Watch later
Aaron Roth, …
AI Commons
Watch later
Limits of Deepfake Detection: A Robust Estimation Viewpoint
Watch later
Toward Robust AI Systems for Understanding and Reasoning Over Multimodal Data
Watch later
