Safe Wasserstein Constrained Deep Q-Learning

2020·arXiv

Abstract

1 Introduction

This paper presents an algorithmic framework for improving safety with deep Q-learning. Safe RL is the study of reinforcement learning with safety constraints. The question of safety during online learning and control poses perhaps the greatest open challenge to ongoing RL research. Consider that when starting with no a priori information about the underlying environment, the only ostensible way to learn what behavior is safe and unsafe is by acting in an unsafe manner. Given this challenging fact, ongoing research seeks methods which allow agents to safely learn safe control policies.

Recently, (Garcia and Fernandes [2016]) organize safe RL research into two primary categories. The first category modifies the optimization criterion for the underlying control problem. The second category modifies the fundamental exploration process itself using either, (1) external knowledge, or (2) a risk metric. Take, for example, conventional Q-learning with an - greedy exploration policy. In this case, there is no direct method to ensure constraint satisfaction when taking exploratory actions randomly. This is a problem safe RL research seeks to address when modifying the overall exploration process. A common approach is to use external information to guide the exploration of an RL agent. For instance, Mann et al. avoid random exploration by guiding exploration via transfer learning with an intertask mapping (Mann and Choe [2012]). Other work addresses safe exploration using prior information about the application (e.g. a model) (Maire [2005], Maclin et al. [2005], Moreno et al. [2004]). More recently, (Koppejan and Whiteson [2011]) use predefined safe baseline policies as an initialization for online learning. Incorporating a priori information into the exploration process is frequently coupled with a model-based RL approach (Fisac et al. [2018]).

The exploration process can also be modified using risk criteria obtained during learning. Law et al. presented early work addressing this approach, which defines a flexible risk heuristic that motivates RL agent exploration (Law et al. [2005]). Perkins et al. address this problem by restricting the policy space based on improving identified Lyapunov functions for RL control (Perkins and Barto [2002]). Another risk-criterion based approach can be found in work by Gehring et al. which guides exploration via a controllability metric that represents confidence in the result of taking an action at a given state. In this work, Gehring et al. utilize the TD error given by the objective Q-function for a given state-action pair to quantify confidence in the result from that state-action pair. They show empirically that weighting this TD error in the action selection process can improve safety (Gehring and Precup [2013]). Our proposed safe RL algorithm similarly uses TD errors, as detailed later.

Guiding exploration can also be done based on learning safe regions. For instance, Koller et al. present an approach for learning-based model-predictive control which guarantees the existence of feasible return trajectories to a defined safe region with high-probability (Koller et al. [2018]). Other work by Richards et al. constructs a neural network Lyapunov function in order to learn safe regions for nonlinear dynamic systems (Richards et al. [2018]). Berkenkamp et al. also leverage Lyapunov stability to establish specific metrics of safety for an RL controller (Berkenkamp et al. [2017]).

Recently, ideas from the literature on constrained Markov decision processes (CMDPs) have begun migrating into relevant RL research. Simply put, CMDPs are MDPs where the policy space is limited by constraints imposed on auxiliary cost functions. See work by Altman for more discussion of their specific formulation (Altman [1999]). Q-learning has been applied to solve CMDPs in the past, however existing works re-frame the problem using the assumption of strong duality (Djonin and Krishnamurthy [2007]). In most common use cases, however, Slater’s constraint qualification condition rarely holds, making this approach difficult to effectively implement. The general concept of constraint costs has been applied in recent papers on the subject of safe RL (Chow et al. [2015], Achiam et al. [2017]). Chow et al. present an algorithm reminiscent of past work by (Parr and Russel [1997]) which defines the feasible action space for stationary deterministic MDPs with respect to such constraint cost estimates, improving adherence to constraints. They use resource constraints in the MDP formulation to act in a similar manner as a shield (Alshiekh et al. [2017]). However, the certificates of their algorithm ostensibly depend on an assumption that the convergence of the reward and constraint Q-functions occurs on separate timescales. Their formulation is also sensitive to noisy observations, and has yet to be explored with function approximation.

While these approaches all improve safety during online learning, they still share the exact same shortcoming which remains the strongest motivating force behind this area of literature. Namely, without a priori information about the underlying environment it is impossible to act in a safe manner without violating constraints to some degree. In exploring this open question, this paper takes motivation from literature on robust model-predictive control (MPC), where the concept of “constraint tightening” has become fairly popular over the past decade. In robust MPC, set-membership based methods are frequently applied to guarantee safety with respect to some uncertainty in the control process (Kothare et al. [1996]). Constraint tightening is a general approach in robust MPC where the size of the uncertainty sets varies over time, becoming smaller as our understanding of the dynamics and uncertainty improves (Lorenzen et al. [2017]). The size of the uncertainty set can also be made an additional decision variable to eliminate unnecessary conservatism (Kim et al. [2018]).

This paper presents a novel robust approach to safely solving constrained RL problems. Our work is roughly inspired by the motivating idea of constraint tightening literature, as well as the ideas presented by (Parr and Russel [1997]) regarding hierarchies of machines in RL problems. We use the methodology of Chow et al. [2015] as a simple foundation upon which we build DrQ, a novel framework for safe RL. DrQ is an algorithmic framework for safe deep Q-learning which leverages Wasserstein ambiguity sets to enforce safety constraints. Specifically, we follow (Chow et al. [2015]) by separating consideration of constraints to their own constraint cost functions. These cost functions define the feasible action space within which DrQ operates. Importantly, our DrQ algorithm leverages a novel formulation for pulling the nominal constraint boundary into the safe region, based on worst-case distributions of modeling error. These distributions are characterized by observed TD errors of the underlying constraint cost functions. By presenting a disciplined Wasserstein DRO-based method for recessing the constraint boundary into the safe region, DrQ observes and reacts to unsafe behavior before nominal constraints are violated. Our algorithm yields probabilistic safety guarantees under idealistic circumstances which arise from past theoretical work on Wasserstein ambiguity sets (Esfahani and Kuhn [2018], Gao and Kleywegt [2016], Duan et al. [2018]). As the constraint cost models improve, the constraint offset naturally tightens towards the nominal boundary. Our case studies in safe lithium-ion battery fast charging demonstrates the strong propensity of DrQ to translate these theoretical safety certificates directly to improving safety during exploration and exploitation in more nuanced, real-world RL problems.

2 Mathematical Preliminaries

The principal tools leveraged in DrQ are CMDPs and Wasserstein ambiguity sets. The following subsections detail preliminary information about these concepts.

2.1 Constrained MDPs

Constrained Markov decision processes are identical to MDPs except that additional cumulative costs are used to restrict the space of feasible control policies. We direct the reader to (Altman [1999]) for further reading on the subject. The feasible set of control policies is defined as:

where are cumulative constraint cost functions (henceforth referred to as constraint Q-functions) developed subject to the policy defined by Q:

DrQ is inspired by (Parr and Russel [1997]), which discusses hierarchies of machines in RL problems. More recently, a similar approach for CMDPs was presented by (Chow et al. [2015]), given the title of “Two-Phase” Q-learning. In “Two-Phase” Q-learning, the objective and constraint Q-functions are learned online while limiting the feasible space based on estimates of the constraint cost functions. This approach, however, still requires we experience unsafe states in order to gradually learn safe behavior. Their algorithm is also sensitive to noise, only works for deterministic MDPs, and has yet to be explored with deep function approximation. In the following sections, we will lay groundwork for DrQ, which ameliorates the shortcomings of existing value-based approaches.

2.2 Wasserstein Ambiguity Sets

A chance constrained program contains constraints with random variables R characterized by support . Take the inequality constraint . We assume the random variable R is an additive uncertainty, R is the vector of inequality constraints for the given optimization program. We can reformulate this as a chance constraint:

where is a user-prescribed probability of constraint violation. Often, the random variable is characterized by an empirical distribution of samples drawn from the true distribution

The number of samples comprising the empirical distribution affects the degree to which our approximation matches the true distribution. This can be thought of as a distance within the space of probability distributions. Several statistical tools exist which allow us to quantify this distance. These include the various forms of -divergence, as well as the Wasserstein distance metric, defined as:

Definition 2.1. Given two marginal probability distributions lying within the set of feasible probability distributions , the Wasserstein distance between them is defined by

where is a joint distribution of the random variables denotes any norm in

The Wasserstein metric can be thought of as representing the minimum cost of transporting or redistributing mass from one distribution to another via non-uniform perturbation (Yang [2018]). This inherent minimization is referred to in convention as the Monge-Kantorovich problem.

To guarantee robustness to out-of-sample experience under idealized circumstances, we use Wasserstein distance to optimize over the worst-case realization of the random variable, sourced from a family of distribution functions within a ball centered about our empirical distribution. For instance, let be a ball of probability distributions with radius centered around our empirical CDF

where is the Wasserstein ball radius. Now, the chance constraint in (6) can be reformulated as:

One challenge to the constraint shown in (9), which optimizes over the worst-case realization within the Wasserstein ambiguity set, is that it entails an infinite dimensional nonconvex problem. Ongoing research has pursued tractable equivalent reformulations of this constraint.

Several expressions exist for the Wasserstein ball radius which, for a given confidence level , is probabilistically guaranteed to contain the true distribution. We adopt the following formulation of from (Zhao and Guan [2018]):

where is the diameter of the support of the random variable is the probability that the true distribution lies within distance of our empirical distribution is the number of samples.

The certificates provided by Wasserstein ambiguity sets are out-of-sample guarantees (Esfahani and Kuhn [2018]). This means we can guarantee safety with respect to new experience. For RL problems, this certifying out-of-sample feasibility is critical for ensuring safe control, not just retroactively, but throughout the entire learning process. Leveraging this property for safe RL is our key contribution.

In this paper’s supplementary material, we provide a restatement of the equivalent chance constraint reformulation we adopt from (Duan et al. [2018]) to transform (9) into a tractable inequality constraint. The process of reformulation assumes the constraint function is linear in the random variable R, and entails a scalar convex optimization program that can be solved rapidly in real time with limited additional computation. The end result of this reformulation is a set of constraints:

where the offset variables , of total number m (one for each constraint), enumerate across the vertices of a hypercube whose side length is the decision variable of the additional convex optimization program. Considering the set of constraints as a joint chance constraint would entail the number of function approximators scale with factor . For computational purposes we isolate each constraint as an individual chance constraint with single constant . The offset variables do not vary based on (s, a).

Considering the distribution over all of (s, a) when computing q provides a conservative approach. To reduce conservatism, an auxiliary function could be used to fit the distribution of TD errors, creating the following constraint:

In this case, distributional robustness could still be included by further considering the residuals of the function instead of the TD-errors themselves. For now, we relegate investigation of this method to future work.

3 Distributionally Robust Q-Learning

Consider that the primary problem in constrained RL is that we generally cannot plan avoidance of unsafe states without first acquiring some experience of which states are themselves unsafe. For conventional algorithms, this “chicken and egg” problem means the first step to learning safe control is to violate constraints. As a result, conventional algorithms are by nature incompatible with the principal objective of constrained RL. In order to address this challenge, we look to the control theoretic literature for potential solutions. In research on model-predictive control (MPC), the concept of “constraint tightening” is a popular method when implementing adaptive predictive controllers. This field uses heuristics or analytical methods to derive control laws which, if necessary, will safely approach constraint boundaries as model uncertainty decreases. The idea of constraint tightening immediately radiates potential for value-based RL algorithms. By shifting the constraint boundary into the safe region, we can experience artificially unsafe states long before the actual safety of the underlying system comes into question. Motivated by this insight, we present a constraint tightening methodology for Deep Q-Learning which can idealistically provide strong probabilistic guarantees on safety, which in practice we show to generally improve overall constraint satisfaction.

First, we limit our algorithm to solving optimal control problems subject to inequality constraints indexed by . The cost functions associated with these constraints take the form:

This function indicates that the constraint Q-functions represent cumulative constraint violation. Furthermore, it allows us to uncouple the updates between using the following

By updating with its own Bellman equation, we convert the constraint to its best-case counterpart. This means that represents the cumulative constraint cost acquired with the safest possible policy. Since any positive signal in indicates infeasibility, we can make this change. This uncoupling allows us to learn Q and without timescale separation between them. The proof of convergence of the original two-phase Q-learning algorithm in (Chow et al. [2015]) ostensibly depended on this timescale assumption, including for more general problems which do not satisfy (13). We can also apply a tolerance when updating to allow constraint violation to propagate backwards throughout the model. In order for our framework to be consistent with the methodology presented by constraint tightening approaches, we can introduce an offset variable to each constraint cost as follows:

This formulation begs the questions of how we set and update the value of offset variable in real time. For these questions, we consider ways to characterize the modeling error of the constraint Q-functions. Ideally, we want to offset the constraint boundary proportionally to the worst error of our model. For this consideration, we can use TD error distribution for each constraint Q-function. Past work by (Gehring and Precup [2013]) has utilized TD errors in Q-learning as indicators for our confidence in the underlying model. Consider the TD error defined for the ith constraint Q-function (which unlike the objective Q-function is solving a minimization problem):

This TD error is a modeling residual by definition, but it is not perfect. It represents how much our model of the cumulative constraint cost changes after a parameter update. The TD error provides a good indication of modeling error, but since it does not exactly represent that quantity our theoretical guarantees do not exactly translate to real applications. But we show later in this paper that DrQ architecture still manages to dramatically improve safety during online learning. Our best indication of such model error can be obtained by using the distribution of TD errors computed after each update to describe the error inherent to our function approximator for each

Now we can delve into the fundamental basis for our algorithmic architecture. DrQ works by defining the offset variables , one for each inequality constraint, through an equivalent reformulation of the following distributionally robust chance constraint:

where defines the Wasserstein ambiguity set, Rrepresents the realization of the TD error of the ith constraint Q-function, and is our allowed probability of violating the constraint. We can interpret this constraint as follows: we have an empirical distribution of TD errors which we compute after each parameter update of . We want to satisfy the constraint for the worst-case realization of TD error Rsourced from a family of probability distributions centered about our

empirical distribution. This set of distributions is within distance of the empirical distribution, with the expression for given by (10). The reformulation we select for our algorithmic architecture comes from (Duan et al. [2018]), and yields the constant that we augment to our ith constraint cost function. Thus, the greedy action selection process becomes:

where

can be used to limit the feasible action space for exploration and exploitation. In order to evolve the offset as our TD distributions change over time, we store the tuple each time we prepare to update the functions we recompute the unique values of the constraint cost function as per (35) based on our most recent . This formulation mathematically encodes that we seek to satisfy the constraint subject to the addition of the potential worst-case modeling error. As our model improves, we can approach the constraint in a provably safe manner consistent with the theoretical guarantees afforded Wasserstein ambiguity sets.

Algorithm 1 describes the implementation of DrQ. We opt for a fitted Q-iteration method for deep Q-learning. The supplementary appendix includes (i) a full conceptual and graphical demonstration of DrQ, (ii) a full restatement of the process for computing , and (iii) discussion of relevant questions including:

• Can our algorithm accommodate nonstationary MDPs? -No • Can our algorithm accommodate probabilistic MDPs? -Yes • Could stabilize prematurely, removing some safe states from future exploration? - Yes, but only under very specific conditions on the measurement noise or function approximator.

4 Battery Fast Charging Case Study

This paper presents two case studies on battery fast charging to validate the performance and safety of DrQ. For brevity, included in the main draft is a basic but still challenging study on fast charging using an equivalent-circuit battery model. In our supplementary material, we detail a more comprehensive case study using a high-order large scale electrochemical battery model.

4.1 Equivalent Circuit Model of a Lithium-Ion Battery

This case study utilizes an equivalent circuit model of a lithium-ion battery. The relevant states in this model are the state of charge SOC and capacitor voltage . The relevant constraint is on the terminal voltage V . The state evolution laws are given by the following equations:

where is the current input, and is the nonlinear open-circuit voltage, which is obtained through experiments. Table 1 and Figure 1 in our supplementary material document the relevant parameter values we adopt for this problem, as well as the OCV function profile. We utilize the following formulation of fast charging:

4.2 DrQ Problem Formulation

The objective reward function for this optimal control problem takes the form:

The initial SOC in our case study is 0.2 (20% capacity), and (70% capacity). The constraint penalty takes the form:

where . Our risk metric . For a baseline comparison, we also examine conventional deep Q-learning (DQN) with the following modified performance criterion:

4.3 Results

We generate 10 independent runs of 25 episodes using both DQN and DrQ for this analysis. For DrQ, Q is a single hidden layer neural network with 10 neurons and sigmoid activation and D is a neural network with four hidden layers of size (2, 5, 5, 2). The DQN is a neural network with two hidden layers of size (10, 10). We use sigmoid activation functions for our function approximators. This demonstrates our algorithm is capable of yielding a high performing control policy which safely charges the battery. Comparatively, after 25 episodes the DQN yields a consistently unsafe control policy which overcharges the battery. In fact, analysis of our other runs indicates the DQN frequently fails to converge to any usable result entirely. Figure 1 clearly demonstrates this finding. Overall, DrQ delivers significantly more consistent and near monotonic improvements in performance, whereas the DQN shows no clear pattern of improvement after 25 episodes. DrQ also delivers tighter variance on the overall performance compared to DQN.

Figure 2, which provides our most illustrative results, displays statistics on constraint satisfaction for both DrQ and DQN throughout these 10 runs. After the first episode (where constraint satisfaction is commensurate between DrQ and DQN since we do not enforce DRO), DrQ safely learns to charge the battery by leveraging the idealized probabilistic guarantee of Wasserstein ambiguity sets. In fact, our observations of constraint violation for DrQ are entirely consistent with our chosen chance constraint risk metric (see the figure caption for this analysis). Overall, only 1.25% of episodes and only 0.023% of timesteps violate constraints for DrQ. By observing the magnitude of the y-axis scale between cumulative and maximum constraint violation in Fig. 2, it is clear that DrQ also attenuates the magnitude and frequency of constraint violation in the unlikely event that violations do occur relative to DQN. In comparison, the DQN benchmark consistently violates constraints. The average computation time for each DrQ episode was 5.57 seconds, compared to 3.77 for DQN when run on a PC with a 9th generation intel i5 processor.

DQN is our comparison for several reasons. DrQ, much like DQN, can be augmented with additional and existing safe RL architecture. More importantly, our analysis is intended to quantify real-world adherence to idealized theoretical guarantees we obtain through application of Wasserstein ambiguity sets.

5 Conclusion

This paper presents a novel algorithmic framework for deep Q-learning with probabilistic safety guarantees. Considering CMDPs, we apply a Wasserstein DRO framework to modify the constraint cost functions with offset variables that tighten towards the nominal constraint boundary as our modeling accuracy improves. We characterize the underlying modeling error of our function approximators with the TD errors of the constraint Q-functions, treated as random variables. This scheme allows us to observe constraint cost without violating nominal constraints, which provides strong information we use to define a set of feasible state-action pairs. The probabilistic guarantees of our augmented algorithm allow us to guarantee safety throughout the entire online learning process.

Our algorithm addresses critical challenges of safe RL literature. Specifically, we present a methodology for Q-learning which allows us to provide strong safety certificates during online learning. Our approach is widely applicable to a diverse set of learning-based optimal control problems. Furthermore, our approach facilitates the overall learning process with what we observe to be more consistent and dependable convergence, and more effective intermediate control results.

Appendix

This supplementary material has 5 sections. In Section I, we provide some detailed parameter values for the ECM case study in the main script. In Section II, we detail a graphical example of how DrQ works to demonstrate the varoius moving parts of the algorithm. In Section III, we restate the equivalent chance constraint reformulation we adopt from the literature. Section IV provides additional discussion of DrQ, including addressing several questions raised in the main text. Finally in Section V, we detail a more challenging case study of a learning-based safe optimal charging controller using a higher-order electrochemical battery model.

Figure 1: Greedy policy performance statistics over 10 runs of DrQ and DQN, based on the reward function defined by (66). Performance of -35 indicates no input current is applied, which occurred as the final result of 6 of the DQN runs.

Figure 2: Safety statistics over 10 runs of DrQ and DQN, starting from the second episode. The black “exploration” points correspond to the data obtained from the -greedy policy. The cyan “greedy” points correspond to the greedy policy evaluated at the end of each exploratory episode. The safety observed in both exploration and exploitation with DrQ is consistent with the chance constraint risk metric . Out of 240 exploratory episodes (excluding the first from each run, where we do not enforce DRO), only 3 episodes exhibit constraint violation

Appendix 1: ECM Case Study Details

Table 1: Relevant Parameters

Appendix 2: Conceptual Graphical Example

In this appendix, we will walk through a complete episodic sequence of DrQ for the following simple optimal control problem:

Figure 3: Experimental Open-Circuit Potential Function

where the unknown state transition function f(s(k), a(k)) can be either deterministic or probabilistic.

Episode 1

The safety guarantees of DrQ become active after our first parameter update of the functions. Therefore, for the first episode of learning, we operate similarly to conventional deep Q-learning while simultaneously recording constraint violation subject to an artificial sunken constraint boundary. For the first episode, the offset can be set as a hyperparameter given any understanding of the scale of the constraint functions and how close they may be to the nominal boundary. Our objective for the first episode is to observe violation of the offset while maintaining safety relative to the actual constraint boundary. A priori knowledge of the constraints can be applied to initialize the constraint offset.

For the first episode, with random initialization of the functions Q and , we essentially act randomly while recording values of r and . Then at the end, when we apply our first parameter update to the function approximators, the constraint costs become:

and we update according to the following targets:

of the feasible set on our update of Q.

Once we have updated the parameters of , we compute the TD errors of our new model as follows:

We use this TD error distribution to recompute the value of for the next episode. Then, for the next episode, we observe constraint violation subject to the modified boundary given by

Episode 2

Once episode 2 begins, the real advantages of DrQ begin to manifest. To demonstrate, lets use a graphical example. Suppose we are at state at the beginning of episode 2. After our parameter updates to , we can plot in 3D the relationship between and the potential actions we can take in for fixed state. Suppose this plot takes the form shown in Figure 4. Here, the action

Figure 4: Plot of for total action space

pairs within the black square correspond to the true (unknown) feasible actions. Since is nonzero, our estimated feasible action space is smaller than the true space, resulting from our offset of the constraint boundary into the safe region. From this plot, we can easily deduce the feasible pairs of and as those with value of equal to zero (dark purple). We can superimpose this set onto our plot of Q to get the graphic in Figure 5. If we are exploring, then we can pick any action within this

Figure 5: Plot of Q with superimposed feasible action space

feasible set. If we are exploiting, we choose the pair which maximizes Q along the restricted domain defined by , which is computed from the data visualized in Figure 4, which in this case turns out to be . This action is safe, but conservative. As the offset progressively tightens, the action DrQ selects will slowly yield improved performance without sacrificing safety.

Now, at the end of episode 2, we can use the new data to further update the parameterizations of the function approximators . With the new TD errors of , we recompute the DRO offset and continue this process until the desired control performance is attained.

Episode k

Suppose arbitrary number of episodes have passed, and we are now at an episode “k.” After these episodes, the TD errors of have reduced in magnitude given the assumption that our model improved. Given no measurement noise, we assume that our TD error distribution is predominantly centered about zero. Now, at the same test state at the beginning of the episode, we evaluate the potential actions to give the following plot of : Here, our estimated safe set is the same as the

Figure 6: Plot of for total action space

true safe set. Since our offset is derived from the TD-error distribution (which is predominantly zero given a converged function approximator), =0 and we have approached the true constraint boundary. Thus, with no modeling errors in this simple conceptual example we eventually act in a truly optimal way relative to the optimal control problem statement. Here, the safe set superimposed on the objective Q-function at episode k takes the form: meaning we pick the truly optimal (and

Figure 7: Plot of Q with superimposed feasible action space

importantly nominally feasible) action . The next section in this appendix details how to compute the DRO offset variable which guides this constraint tightening procedure.

Appendix 3: Chance Constraint Reformulation

Equivalent Chance Constraint Reformulation

In this paper, we adopt an equivalent reformulation of the DRO chance constraint utilized in [Duan et al.(2018)]. This specific reformulation requires that the constraint function is linear in R. An in-depth discussion of this reformulation can be referenced in [Duan et al.(2018)]. Here, we restate a brief overview of their methodology and derivation.

We begin with samples of data corresponding to our random variable This sample comprises our empirical distribution , and the data is drawn from the true underlying distribution . First, we normalize the data samples to form a new random variable as follows:

where is the variance of the data and is the sample mean. This standardization transforms our data samples such that its new mean is 0, and its new variance is . Now, we define the support of this normalized distribution:

Here, defines the support of the normalized random variable and is a column vector of ones. Now, let represent the true and empirical distributions of the normalized data construct the ambiguity set using the relation given by:

allowing us to transform the chance constraint to

where we wish to obtain the least conservative set in order to define the desired Wasserstein uncertainty set

We restrict the overall shape of the set V to be a hypercube, which enables computational tractability:

Now, to compute this ambiguity set without introducing unnecessary conservatism, we need to find the minimum value of the hypercube side length . The following optimization program formalizes this goal:

Here, we estimate using a-priori information about the specific problem context.

The derivation in [Duan et al.(2018)] provides a worst-case probability formulation which allows us to state the following Lemma: Lemma 5.1.

where

The result of this optimization program is the value of the scalar variable , which is used to reformulate the chance constraints via convex approximation. The convex optimization required to compute is a simple and fast scalar optimization program suitable for a real-time control application. For a convex approximation of the constraint function, the hypercube becomes the convex hull of its vertices. For example, in the case where m = 1 (i.e. the random variable is 1-dimensional, then . This means that the ambiguity set U becomes where . This can be leveraged to complete the convex approximation as a set of constraints of the form

Appendix 4: Extended Discussion of DrQ

This appendix provides further discussion on the following questions raised in the main text:

• Can our algorithm accommodate nonstationary MDPs? -No

• Can our algorithm accommodate probabilistic MDPs? -Yes

• Could stabilize prematurely, removing some safe states from future exploration? - Yes, but only under very specific conditions on the measurement noise or function approximator

Nonstationary MDPs

Our algorithm in its current state cannot effectively accommodate nonstationary MDPs. Consider that if the underlying dynamics change, the historical data mapping will no longer represent the actual constraint dynamics. This would cause the DRO offset to grow given growing model residuals from inconsistent historical data. Perhaps with a disciplined forgetting scheme this phenomenon could be avoided, however as of now we relegate this issue to future work.

Probabilistic MDPs

Our algorithm can accommodate probabilistic MDPs. Past work by (Chow et al. [2015]) and (Paruchuri et al. [2004]) indicates similar algorithms cannot accommodate probabilistic MDPs without miscoordination occurring. These studies explore frameworks for multi-agent systems. When applied to single-agent systems, our algorithm avoids this shortcoming.

For the case where state transition dynamics are probabilistic, consider the definition of the functions Q and . Both consider cumulative costs, which given probabilistic dynamics simply become cumulative expected costs. For , any nonzero signal indicates constraint violation (subject to the offset ), so any state-action pair with a non-zero probabilitiy of violating constraints will eventually be pruned.

Stability of

Two cases exist where the value of stabilizes prematurely, removing some safe state-action pairs from future consideration. The first has to do with measurement noise. Assuming the function approximator converges, if our measurements of are subject to a measurement noise process, then the eventual TD error distribution of will represent the underlying measurement noise process. This distribution of residuals could create a permanently nonzero

The second has to do with the properties of the function approximator. If the function approximator fails to converge, then the value of may not stabilize and could oscillate or diverge. Our numerical experiments have yet to show a case where this occurs, but it is a possibility for nearly any deep Q-learning algorithm. Some specific cases where this occur can be found in (Lu et al. [2018]).

Appendix 5: SPMeT Case Study

In this section we detail our comprehensive case study on safety-aware learning-based fast charging control, with a large scale electrochemical battery model.

Single Particle Model with Electrolyte & Thermal Dynamics

The single particle model with electrolyte and thermal dynamics (henceforth denoted as SPMeT) is a reduced-order electrochemical lithium-ion battery model derived from the Doyle-Fuller-Newman (DFN) electrochemical battery model Moura et al. [2017]. The DFN model employs a continuum of particles throughout the anode and cathode of the battery cell. Diffusion within this continuum is represented with partial differential equations (PDEs) and differential-algebraic equations (DAEs). The SPMeT uses a simplified representation of solid phase diffusion based on a single spherical particle in each electrode of the battery cell. Compared to the ECM model used in the main text (which is isothermal), the SPMeT incorporates thermal dynamics. Furthermore, the state variables of the SPMeT model provide direct physical intuition on the conditions occurring within the battery cell. The SPMeT model also provides much more accurate prediction at higher input current rates.

The main advantage of designing fast charging controllers with the SPMeT is that we can leverage the granular electrochemical information encoded in the dynamical state to replace the phenomenological equivalent circuit model used in the main text. Specifically, by constraining electrochemical state variables instead of terminal output voltage, we can safely expand the safe operating envelope in order to improve charging times significantly. Coincidentally, constraining electrochemical states gives us greater agency in avoiding rapid cell aging sourced from myopic charging protocols.

The governing equations for SPMeT include linear and quasiliniar PDEs and a nonlinear voltage output equation, given by:

where t represents time. The superscript j denotes anode, seperator and cathode, , each forming essential components of the lithium ion battery cell. The terminal voltage output is governed by a combination of electric overpotential, electrode thermodyanmics, and Butler-Volmer kinetics, yielding:

where is the solid phase surface concentration, namely is the open-circuit potential, and is the maximum possible concentration in the solid phase. The exchange current density and solid-electrolyte surface concentration are given by:

Note the electrolyte diffusion PDE (52) is quasilinear because the diffusion coefficient depends on lithium concentration,

The nonlinear temperature dynamics are modeled with a single lumped thermal mass subjected to heat generation from the input current:

where is the ambient temperature, m is the mass of the cell, is the thermal specific heat capacity of the cell, is the thermal resistance of the cell, and is the heat added from the charging, which is governed by

Here, I(t) is the input current (the control input), and V (t) is the voltage determined by (53). Both nonlinear open circuit potential functions in (57) are functions of the bulk state of charge (SOC) in the anode and cathode, respectively. For more details on the SPMeT equations and notation, we direct the reader to (Moura et al. [2017]).

Optimal Control Problem Statement

The optimal control problem statement for fast charging with SPMeT is given by:

where is the normalized bulk concentration in the anode, is the control action, and is the state vector. We define the overall cell SOC as:

To solve this problem using reinforcemnet learning, we spatially discretize the system of PDEs to formulate a discrete-time and space model of the form . The reward function for DrQ takes the form:

We also compare DrQ to a conventional DQN, whose reward function takes the form:

where we apply a constant step penalty for any constraint violation.

For each relevant constraint, we define a feed forward neural network to approximate with 2 hidden layers each with 10 neurons and sigmoid activation function. We approximate the objective Q-function using a network of similar architecture. Table 2 includes the hyperparameters for the overall problem. The SPMeT model we use as a simulator is parameterized for a prismatic lithium nickel manganese cobalt oxide cell, different from the lithium iron phosphate cell used in our ECM case study. The episode simulation horizon is 1400 seconds. For an optimal baseline, we use methods outlined in (Perez et al. [2015]). Figure 8 shows the baseline control result. Several meaningful insights can be taken from these baseline results. First, the anode electrolyte constraint has the potential to be violated at almost every timestep. Violation of this constraint can cause rapid aging or catastophic failure. Second, the multitude of constraints provides a stronger challenge to our algorithm.

Figure 8: Baseline optimal control result.

Table 2: Relevant Parameters

DrQ Results

We simulate 10 independent runs of both DrQ and DQN, each with 25 episodes. Figure 9 shows a comparison of the performance between DrQ and DQN, averaged across the runs. We evaluate the greedy policy performance at episodes 2, 5, 10, 15, 20, and 25 for computational purposes, given the SPMeT model is numerically expensive to simulate. Relative to DrQ, the variance in the DQN performance is greater. Furthermore, the performance of DrQ is on average 31% greater compared to DQN. One important note is that, to get the DQN baseline properly running, we had to add a fail-safe which set the input current to zero if the anode electrolyte concentration became too low. DQN tended to max out the input current in the first several episodes of each run, which would rapidly deplete the electrolyte. With a real battery cell, this would cause unsafe charging conditions and potential for catastrophic failure. In simulation, however, this would simply terminate the code with numerical errors.

The safety advantages of DrQ can be seen in plots of constraint satisfaction. Figures 10 and 11 show these results for the two active constraints, namely and T. Figure 10 is particularly informative, since the electrolyte constraint is most often the dominant constraint. Here, DrQ strongly attenuates the magnitude and frequency of constraint violation. The temperature constraint is violated less for several reasons. First, the temperature constraint only becomes active after a history of high input current. DrQ shows faster convergence to an optimal policy, which aggressively charges the battery. Therefore, this constraint is violated more compared to DQN, which yields lower performing policies on average. Nevertheless, the risk metric of the DrQ algorithm () is validated within these experiments for all of the constraints, given that over all of the episodes and runs only 4.82% of timesteps exhibited any constraint violation.

Based on our data, the average DrQ episode took 361.58 seconds while the average DQN episode took 90.12 seconds. Both simulate faster than real-time, which suggests that DrQ (and DQN) could run within on-board microcontrollers, even for complex dynamical systems.

References

Javier Garcia and Fernando Fernandes. A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16:1437–1480, 2016.

Timothy A. Mann and Yoonsuck Choe. A comprehensive survey on safe reinforcement learning. In JMLR: Workshop and Conference Proceedings 24:59–75, 2012 10th European Workshop on Reinforcement Learning, pages 1437–1480, Edinburgh, Scotland, 2012. JMLR W|&C Proceedings.

Frederic Maire. Apprenticeship learning for initial value functions in reinforcement learning. In V. Bulitko and S. Koenig, editors, Proceedings of the IJCAI’05 Workshop on Planning and Learning in A Priori Unknown or Dynamic Domains, pages 23–28, Edinburgh, United Kingdom, 2005. International Joint Conferences on Artificial Intelligence.

Richard Maclin, Jude Shavlik, Trevor Walker, and Lisa Torrey. Knowledge-based support vector regression for reinforcement learning. In Proceedings of the IJCAI’05 Workshop on Reasoning, Representation, and Learning in Computer Games, pages 61–66, Edinburgh, Scotland, 2005. International Joint Conferences on Artificial Intelligence.

David L. Moreno, Carlos V. Regueiro, Roberto Iglesias, and Senen Barro. Using prior knowledge to improve reinforcement learning in mobile robotics. In Proceedings of the Conference Towards Autonomous Robotics Systems, Bath, England, 2004. Springer.

Rogier Koppejan and Shimon Whiteson. Neuroevolutionary reinforcement learning for generalized control of simulated helicopters. Evolutionary Intelligence, 4(4):219–241, 2011.

Jaime F. Fisac, Anayo Akametalu, Melanie Nicole Zeilinger, Shahab Kaynama, Jeremy H. Gillula, and Claire J. Tomlin. A general safety framework for learning-based control in uncertain robotic systems. IEEE Transactions on Automatic Control, pages 1–1, 2018.

Edith L.M. Law, Melanie Coggan, Doina Precup, and Bohdana Ratitch. Risk-directed exploration in reinforcement learning. In V. Bulitko and S. Koenig, editors, Proceedings of the IJCAI’05 Workshop on Planning and Learning in A Priori Unknown or Dynamic Domains, pages 97–102, Edinburgh, United Kingdom, 2005. International Joint Conferences on Artificial Intelligence.

Figure 9: Greedy policy performance statistics over 10 runs of DrQ and DQN, based on the reward function defined by (66).

Figure 10: Safety statistics for the active constraint over 10 runs of DrQ and DQN, starting from the second episode. The black “exploration” points correspond to the data obtained from the policy. The cyan “greedy” points correspond to the greedy policy evaluated incrementally across each run.

T. J. Perkins and A. G. Barto. Lyapunov design for safe reinforcement learning. Journal of Machine Learning Research, 3:803—-832, 2002.

Clement Gehring and Doina Precup. Smart exploration in reinforcement learning using absolute temporal difference errors. In Takayuki Ito, Catholijn Jonker, Maria Gini, and Onn Shehory, editors, Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems, pages 1037–1043, Saint Paul, Minnesota, USA, 2013. International Foundation for Autonomous Agents and Multiagent Systems.

Torsten Koller, Felix Berkenkamp, Matteo Turchetta, and Andreas Krause. Learning-based model predictive control for safe exploration and reinforcement learning. arXiv, pages 1–8, 2018.

Spencer Richards, Felix Berkenkamp, and Andreas Krause. The lyapunov neural network: Adaptive stability certification for safe learning of dynamic systems. arXiv, pages 1–11, 2018.

Felix Berkenkamp, Matteo Turchetta, Angela P. Schoellig, and Andreas Krause. Safe model-based reinforcement learning withstability guarantees. In Proceedings of the 31st Conference on Neural Information Processing Systems (NIPS 2017), Long Beach, CA, 2017. Neural Information Processing Systems Foundation, Inc.

Eitan Altman. Constrained markov decision processes. 1999.

Dejan V. Djonin and Vikram Krishnamurthy. Q-learning algorithms for constrained markov decision processes with randomized monotone policies: Application to mimo transmission control. IEEE Transactions on Signal Processing, 55(5):2170–2181, 2007.

Yinlam Chow, Jia Yuan Yu, and Marco Pavone. Two phase q-learning for bidding-based vehicle sharing. arXiv, pages 1–11, 2015.

Figure 11: Safety statistics for the active T constraint over 10 runs of DrQ and DQN, starting from the second episode.

Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In Proceedings of the 2017 International Conference on Machine Learning (ICML), Sydney, Australia, 2017. PMLR.

Ronald Parr and Stuart Russel. Reinforcement learning with hierarchies of machines. In Proceedings of the 10th Conference on Neural Information Processing Systems (NIPS 1997), Denver, CO, 1997. Neural Information Processing Systems Foundation, Inc.

Mohammed Alshiekh, Roderick Bloem, Rudinger Ehlers, Bettina Konighofer, Scott Niekum, and Ufuk Top. Safe reinforcement learning via shielding. arXiv, pages 1–23, 2017.

Mayuresh V. Kothare, Venkataramanan Balakrishnan, and Manfred Morari. Robust constrained model predictive control using linear matrix inequalities. Automatica, 32(10):1361–1379, 1996.

Matthias Lorenzen, Fabrizio Dabbene, Roberto Tempo, and Frank Allgower. Constraint-tightening and stability in stochastic model predictive control. IEEE Transactions on Automatic Control, 62 (7):3165–3177, 2017.

Yeojun Kim, Xiaojing Zhang, Jacopo Guanetti, and Francesco Borrelli. Robust model predictive control with adjustable uncertainty sets. In 2018 IEEE Conference on Decision and Control, Miami, FL, 2018. IEEE.

Payman Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization using the wasser- stein metric: Performance guarantees and tractable reformulations. Mathematical Programming, 171(1–2):115–166, 2018.

Rui Gao and Anton J. Kleywegt. Distributionally robust stochastic optimization with wasserstein distance. arXiv, 2016.

Chao Duan, Wanliang Fang, Lin Jiang, Li Yao, and Jun Liu. Distributionally robust chanceconstrained approximate ac-opf with wasserstein metric. IEEE Transactions on Power Systems, 33 (5):4924–4936, 2018.

Insoon Yang. Wasserstein distributionally robust stochastic control: A data-driven approach. arXiv, 2018.

Chaoyue Zhao and Yongpei Guan. Data-driven risk-averse stochastic optimization with wasserstein metric. Operations Research Letters, 46(2):262–267, 2018.

Praveen Paruchuri, Milind Tambe, Fernando Ordonez, and Sarit Kraus. Towards a formalization of teamwork with resource constraints. In Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, 2004. AAMAS 2004., New York, NY USA, 2004. IEEE.

Tyler Lu, Dale Schuurmans, and Craig Boutilier. Non-delusional q-learning and value-iteration. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 9949–9959. Curran Associates, Inc., 2018.

Scott J. Moura, Federico Bribiesca Argomedo, Reinhardt Klein, Anahita Mirtabatabaei, and Miroslav Krstic. Battery State Estimation for a Single Particle Model with Electrolyte Dynamics. IEEE Transactions on Control Systems Technology, 25(2):453–468, mar 2017. doi: 10.1109/TCST.2016. 2571663. URL http://ieeexplore.ieee.org/document/7489035/.

Hector Perez, Niloofar Shahmohammadhamedani, and Scott Moura. Enhanced Performance of Li-Ion Batteries via Modified Reference Governors and Electrochemical Models. IEEE/ASME Transactions on Mechatronics, 20(4):1511–1520, August 2015. doi: https://doi.org/10.1109/ TMECH.2014.2379695. URL https://ieeexplore.ieee.org/document/7004876.

Designed for Accessibility and to further Open Science