We review foundational aspects of planning in Markov decision processes (MDPs). The goal is to build up the necessary knowledge to get to the point that we can discuss planning with generative models in large-scale MDPs. For this, we will focus on finite (but perhaps large-scale) MDPs, and leave extensions that go beyond finite MDPs to discussions. We start with basic definitions (what is an MDP, various criteria of optimality) and review fundamentals of dynamic programming (value functions, optimal value functions, Bellman’s equations). After reviewing basic properties of the three fundamental approaches of finding an optimal policy (value-, policy-iteration, linear programming, policy gradient), we wrap up exact planning with discussing known computational complexity and query complexity results. We next consider approximate planning with generative models and how one can save computation and improve generalization by moving away from exact global planning. We discuss differences between local and global planning in MDPs, and finish with a discussion of what is known about using (mainly linear) function approximation in approximate planning.

In the second part, we will study the "multi-armed bandit" problem where only the reward of the chosen action is revealed to the algorithm, and show that we may formalize this problem as either a modified full-information game or as a MDP with a trivial state space. When the target is to minimize regret, we may apply full-information algorithms by constructing estimates of the full loss (as is done by the EXP3 algorithm) or apply the "optimism in the face of uncertainty" (OFU) principle to choose the action with the highest plausible reward (as is done by the UCB algorithm). We will then discuss the "pure exploration" problem (a.k.a. the best-arm-identification problem), where we wish to maximize our chances of finding a (nearly) optimal arm, and introduce "action elimination" algorithms that do well in this setting. Finally, we discuss the setting where the learner also receives some contextual information before having to select an action: the contextual bandit problem requires the learner to compete with a class of mappings from contexts to actions. Throughout, we will highlight important lower bounds on regret which, when combined with the upper bounds for specific algorithms, often fully characterize the difficulty of these settings.

This tutorial will cover the basics of regret analysis in (tabular) Markov Decision Processes (MDPs). The first part will focus on learning in an unknown but fixed MDP. Two families of algorithms will be covered: those based on optimism in the face of uncertainty (OFU) and those based on posterior (or Thompson) sampling. The second part will focus on learning in a harder setting where the MDP transition function and/or the reward function can change adversarially at each time step. Techniques from online learning such as exponential weights, online mirror descent (OMD), and follow the regularized leader (FTRL) will be used to study this challenging problem. Algorithms and their regret analyses establish upper bounds on the minimax regret in various settings. To complement these upper bounds, we will also include a discussion of hardness results especially in the form of regret lower bounds.

This tutorial will cover the basics of performing offline / batch reinforcement learning. There is a significant potential to better leverage existing datasets about decisions made and their outcomes in many applications including commerce and healthcare. The basic problems may be described as batch policy evaluation-- how to estimate the performance of a policy given old data -- and batch policy optimization-- how to find the best policy to deploy in the future. I will discuss common assumptions underlying estimators and optimizers, recent progress in this area, and ideas for relaxing some of the common assumptions, such as that the data collection policy sufficiently covers the space of states and actions, and lack of confounding variables that might have influenced prior data. These topics are also of significant interest in epidemiology, statistics and economics: here I will focus particularly on the sequential decision process (such as Markov decision process) setting with more than 2 actions, which is of particular interest in RL and has been much less well studied than the binary action, single time step setting.

Many estimands of interest in sequential decision problems are non-smooth functionals of the data-generating distribution. Examples include the marginal mean outcome under an optimal policy and coefficients indexing regression models in approximate dynamic programming.  We review how this non-regularity induces instability which in turn can cause standard inference procedures based on asymptotic approximations to perform poorly.  We derive inference procedures based on bounding a non-regular functional between two smooth functionals and show that the resulting inference is valid under fixed and moving parameter asymptotic frameworks. We also show that in some cases, the resulting procedures are universal (i.e., provide consistent coverage uniformly over a large class of distributions) and also provide conditional coverage. Having derived confidence intervals and tests for the estimands of interest, we then consider power and sample size calculations based on these estimands.

In the second half of this tutorial, we introduce a number of open problems in statistical reinforcement learning. These include testing a parsimonious model against a nonparametric alternative; spatio-temporal decision problems; and doubly-robust methods for combining model-based and model-free methods. We introduce each problem and, in most cases, present partial solutions while identifying remaining technical and conceptual challenges.

This tutorial is designed to present RL theory and design techniques with emphasis on control  foundations, and without any probability prerequisites.  Motivation comes in part from deep-rooted control philosophy (e.g., do you think we modeled the probability of hitting a seagull when we designed a control system to go to the moon?) The models used in traditional control design are often absurdly simple, but good enough to get insight on how to control a rocket or a pancreas. Beyond this, once you understand RL techniques in this simplified framework, it does not take much work to extend the ideas to more complex probabilistic settings. The tutorial is organized as follows:  

1.   Control crash course: control objectives, state space philosophy and modeling, and the dynamic programming equations

2.   Convex formulations of Q-learning and their relationship to deep Q-learning.  

3.   Extremum seeking control and gradient free approaches to RL

4.   Applications to power systems.  In particular, online optimization with measurement feedback (both gradient-based and gradient-free) and application to optimal power flow  (presented by Andrey Berstein@NREL: former student of Nahum Shimkin, Technion)

Resources: Extensive lecture notes will be provided prior to the bootcamp (link below).  In addition, students are strongly encouraged to view Prof. Richard Murray's tutorial on control fundamentals:  https://simons.berkeley.edu/talks/murray-control-1

This tutorial is designed to present RL theory and design techniques with emphasis on control  foundations, and without any probability prerequisites.  Motivation comes in part from deep-rooted control philosophy (e.g., do you think we modeled the probability of hitting a seagull when we designed a control system to go to the moon?) The models used in traditional control design are often absurdly simple, but good enough to get insight on how to control a rocket or a pancreas. Beyond this, once you understand RL techniques in this simplified framework, it does not take much work to extend the ideas to more complex probabilistic settings. The tutorial is organized as follows:  

1.   Control crash course: control objectives, state space philosophy and modeling, and the dynamic programming equations

2.   Convex formulations of Q-learning and their relationship to deep Q-learning.  

3.   Extremum seeking control and gradient free approaches to RL

4.   Applications to power systems.  In particular, online optimization with measurement feedback (both gradient-based and gradient-free) and application to optimal power flow  (presented by Andrey Berstein@NREL: former student of Nahum Shimkin, Technion)

Resources: Extensive lecture notes will be provided prior to the bootcamp (link below).  In addition, students are strongly encouraged to view Prof. Richard Murray's tutorial on control fundamentals:  https://simons.berkeley.edu/talks/murray-control-1

In the first part of the tutorial we discuss theoretical and modeling issues involved in making "optimal" decisions under  conditions of uncertainty. The traditional approach is to model the underlying data process as random (stochastic) and to optimize a specified objective function on average. This raises the questions of controlling the risk,  and the uncertainty with respect to the considered probability   distributions themselves.  In the second part of the tutorial we discuss numerical methods for solving stochastic programming problems. I will try to emphasize difficulties and limitations of different approaches and suggest important, from my point of view, open questions.

In this tutorial, we will discuss the basics of simulation. We will start with a quick review of what makes sampling-based methods attractive in many computational settings, and then talk about simulation output analysis. Output analysis is concerned with questions of determining how long a simulation must be run to obtain a solution of prescribed accuracy. In the second half of the tutorial, we will discuss several variance reduction methods that have broad applicability, including control variates and importance sampling. We will conclude with a discussion of gradient estimation.