{'fraction_non_alphanumeric': 0.0431391404225766, 'fraction_numerical': 0.014157117290381174, 'mean_word_length': 4.443152079092759, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Deep Robust Kalman Filter

A Robust Markov Decision Process (RMDP) is a sequential decision making model that accounts for uncertainty in the parameters of dynamic systems. This uncertainty introduces difficulties in learning an optimal policy, especially for environments with large state spaces. We propose two algorithms, RTD-DQN and Deep-RoK, for solving large-scale RMDPs using nonlinear approximation schemes such as deep neural networks. The RTD-DQN algorithm incorporates the robust Bellman temporal difference error into a robust loss function, yielding robust policies for the agent. The Deep-RoK algorithm is a robust Bayesian method, based on the Extended Kalman Filter (EKF), that accounts for both the uncertainty in the weights of the approximated value function and the uncertainty in the transition probabilities, improving the robustness of the agent. We provide theoretical results for our approach and test the proposed algorithms on a continuous state domain.


Introduction
Sequential decision making in stochastic environments are often modeled as Markov Decision Processes (MDPs) in order to optimize a policy that achieves maximal expected accumulated reward (Puterman, 2014;Bertsekas & Tsitsiklis, 1996). Given the MDP model parameters, namely the transition probabilities and the reward function, the aim of an agent is to find the optimal policy. In many cases the true MDP model is unknown in advance and its parameters are estimated from data. The deviation of the estimated model from the true model may cause a degradation in the performance of the learned policy (Mannor et al., 2007). This undesired behavior leads to the need for model-robust methods that consider a set of possible MDP models and find the optimal policy over this set.
Robustness is effective when environmental safety issues arise (Garcıa & Fernández, 2015;Lipton et al., 2016). For example, in autonomous cars (Figure 1(a)) it is important to account for environmental uncertainties such as weather or road conditions. A robust driving policy should account for all of these uncertainties and must subsequently adjust the agent's driving behavior accordingly. Additional motivation for model-robust methods is when an agent seeks to optimize a coherent risk measure (Artzner et al., 1999) or to follow a risk-sensitive policy (Petrik & Zilberstein, 2011;Chow et al., 2015). For example, investing in stock markets (Figure 1(b)) requires defining a model for the dynamics of the stock prices. This model is based on historical data that may be noisy or insufficient which induces uncertainty in the model. A robust investing policy would account for the uncertain model to avoid dangerous decisions that can cause loss of large amount of money. Control tasks can benefit from robustness as well when state transitions depend on several parameters (Rajeswaran et al., 2016). A robust agent would consider different possible values for these parameters to ensure satisfactory performance in the real world.
The robust-MDP (RMDP) framework (Nilim & El Ghaoui, 2005;Iyengar, 2005) was developed to account for uncer-arXiv:1703.02310v1 [cs.AI] 7 Mar 2017 tainties in the MDP model parameters when looking for an optimal policy. In this framework, each policy is associated with a known uncertainty set of transition probabilities. The optimal policy is the one that maximizes the worst case value function over the associated uncertainty set. When the state space is large, solving robust optimization problems can be a difficult task (Le Tallec, 2007).
We are looking for a method for solving large-scale RMDPs, with on-line nonlinear value function approximation. Existing methods for solving RMDPs (Iyengar, 2005;Nilim & El Ghaoui, 2005;Tamar et al., 2014;Rajeswaran et al., 2016) have several limitations such as linear approximation, off-line estimation and restrictive assumptions on the transition probabilities. We review these methods in Section 2 and compare them to the robust Bayesian approach we propose in this paper.
We distinguish between two types of uncertainty: the MDP model parameters uncertainty refers to all the possible transition probability distributions of stepping from state s to state s when taking an action a. We denote this set by P (·|s,a) , and when it is clear from the context, we omit the subscript and use P. The other type of uncertainty origins from the Bayesian assumption over the weights of the approximated value function. We denote the weight uncertainty set by Θ.
Inspired by the success of Deep Q-Network (DQN) agents (Mnih et al., 2013) in estimating large-scale nonlinear value functions, we propose the Robust Temporal Difference DQN (RTD-DQN) algorithm which replaces the nominal Bellman Temporal Difference (TD) error involved in the optimized objective function with the robust Bellman TD error. We show that this algorithm captures the MDP model uncertainty and improves the robustness of the agent.
The Kalman filter (Kalman et al., 1960) and its variant for nonlinear approximations, the Extended Kalman filter (EKF) (Anderson & Moore, 1979;Gelb, 1974), are used for on-line tracking and for estimating states in dynamic environments through indirect observations. These methods have been successfully applied to numerous control dynamic systems such as navigation and tracking targets. The Kalman filter can be also used for weights estimation of approximation functions, where the weights constitute the states of dynamic systems. We suggest to extend the RTD-DQN algorithm by using a Bayesian approach such as EKF to account for the uncertainty in the weights of the value function approximation, in addition to the uncertainty of the transition probabilities. We present this approach in the Deep Robust Kalman filter (Deep-RoK) algorithm.
This approach may be surprising. How are the weights of the value function related to the MDP model parameters?
To answer this question we refer to the work of Mannor  (2007). When estimating the MDP model parameters, the potential for error in the estimates, i.e., the uncertainty in the MDP model parameters, introduces variance in the estimates of the value function, governed by the value function weights. In Figure 2 we illustrate our robust Bayesian approach. The EKF serves as a Bayesian learning algorithm that receives the new information from the transition probabilities uncertainty set P and propagates it into the weights uncertainty set Θ. This approach provides a robust and efficient estimation as we demonstrate in the experiments.
Our contributions are: (1) A Bayesian approach for online and nonlinear approximation of the value function in RMDPs. We connect the robust Bellman TD error to the EKF updates to achieve robust policies in RMDPs; (2) We propose two algorithms, RTD-DQN and Deep-RoK, to solve large scale RMDPs; (3) We provide theoretical guarantees for our proposed methods; (4) We demonstrate the performance of our two algorithms on a continuous state domain.

Related Work
Our paper is related to several areas of research, namely RMDPs, Deep Q-learning networks, EKF and Bayesian approach for weight uncertainty in Neural Networks (NNs). Our work is the first to solve RMDPs while combining scalability to large state spaces, on-line estimation, nonlinear Q-function approximations, robustness to uncertainty in the transition probabilities and a Bayesian approach (EKF) to account for the uncertainty in the approximation weights. In Table 1 we compare between different approaches and our proposed algorithms, Deep-RoK and RTD-DQN. Tamar et al. (2014) used approximate dynamic programming (ADP) method with linear value function approximation. Their convergence analysis is based on a restrictive assumption over the transitions of the exploration policy and the (uncertain) transitions of the policy under evalua- tion. Our work does not rely on such assumptions which facilitates the convergence analysis of our proposed algorithms.
The use of Kalman filters to solve reinforcement learning (RL) problems was proposed by Geist & Pietquin (2010). Their formulation, called Kalman Temporal Difference (KTD), serves as the base for our formulation for the algorithms we propose. We introduce here several differences between their work and ours: (1) We re-formulate the observation function such that the observation of the agent at time t is the target label, meaning the sum of the immediate reward and the discounted next state optimal Q-function. With this formulation, the observation function is simply the Q-function of the current state and action; (2) They used the nominal Bellman TD error, while we are using the robust version of it; (3) We use the Extended Kalman filter as opposed to their use of the Unscented Kalman filter (UKF) to approximate nonlinear functions (Julier & Uhlmann, 1997;Wan & Van Der Merwe, 2000). In our formulation, the observation function is differential, allowing us to use first order Taylor expansion linearization as used in the EKF and in gradient descent optimization methods. The UKF has shown superior performance in some applications (St-Pierre & Gingras, 2004;Van Der Merwe, 2004), however, its computational cost is much greater than the computational cost of the EKF, due to its requirement of sampling the weights in each training step for number of times equals to the double of the weights dimension. Moreover, it requires to evaluate the observation function at these samples at every training step. Unfortunately, this is not tractable in deep NNs where the weights might be high-dimensional.

Background
In this section we describe formulations from different fields, towards combining them into our formulation for solving large scale RMDPs in Section 4.

Robust Markov Decision Processes (RMDPs)
An RMDP (Iyengar, 2005;Nilim & El Ghaoui, 2005) is a tuple {S, A, P (·|s,a) , R, γ} where S is a finite set of states, A is a finite set of actions, R : S × A → R is a deterministic and bounded reward function, γ is a discount factor and P (·|s,a) is a probability measure over (s, a) which denotes the uncertainty set of the transition probabilities for each state s and action a. At each discrete time step t the system stochastically steps from state s t ∈ S to state s t+1 ∈ S by taking an action a t ∈ A. Each transition (s t , a t , s t+1 ) is associated with an immediate reward r t (s t , a t ). The agent chooses the actions according to a policy π : S → A that maps each state to a probability distribution over the actions set. The transitions in the system are according to the probability distribution P (s t+1 |s t , a t ) which is assumed to lie in a known uncertainty set P ∈ P (·|st,at) .
The Q-function of state-action pair (s, a) under policy π and state transition model P represents the expected sum of discounted returns when starting from (s, a) and executing policy π: Q π,P (s, a) = E π,P ∞ t=0 γ t r t (s t , a t )|s 0 = s, a 0 = a , where E π,P denotes the expectation w.r.t. the state-action distribution induced by the transitions P and the policy π. In RMDPs, we are interested in finding the policy that maximizes the worst case Q-function: Q π (s, a) = inf P ∈P Q π,P (s, a). The optimal robust Qfunction is then the unique solution of the robust Bellman recursion: where s is the successive state when taking an action a in state s. Iyengar (2005) showed that the agent can be restricted to stationary deterministic Markov policies without affecting the achievable robust reward. In this paper we focus on the -greedy exploration strategy, where the agent takes a random action with probability , and follows the optimal policy with probability 1 − .
The solution of the minimization problem in Equation (1) may be computationally demanding. Fortunately, there are some families of sets P for which the solution is tractable. Popular uncertainty sets, presented by Iyengar (2005) and Nilim & El Ghaoui (2005) are constructed from approximations of confidence regions associated with probability density estimation. This choice seems natural when the uncertainty is due to statistical errors when estimating the states transition probabilities using historical data.

Deep Q-learning
Q-learning (Watkins & Dayan, 1992) is a TD method that aims at directly finding the optimal policy by updating the Q-function with the optimal greedy policy a * = arg max a Q * (s, a ) (Sutton, 1988). Therefore, learning the optimal policy can be reduced to learning the optimal Q-function. In many RL problems the state space is large, thus the Q-function is typically approximated by parametric models Q(s, a; θ) where θ denotes the weights of the approximation function.
In Deep Q-learning (Mnih et al., 2013), the agent improves the Q-function (and, in turn, the greedy policy) by minimizing at each time step t the squared nominal Bellman TD error (nBTDe) δ nominal t,θ : where Here, y nominal t,θ is the nominal target label and is defined as: The weight θ is a fixed set of weights, normally called the target network. It is composed of a more stable periodic copy of the trained weights. We denote by p(·) the joint distribution of experiences under the current policy. The observation in each time step o t = (s t , a t , r t , s t+1 ) is typically stored in an experience replay O = o 1 , . . . , o N .
Traditionally, the Q-function is trained by stochastic gradient descent, estimating the loss on each experience as it is encountered, yielding the update: where α is the learning rate.

Deep Q-learning: A Bayesian Perspective
The weights θ can be learned by maximum likelihood estimation (MLE) using stochastic gradient descent methods: θ MLE = arg max θ log p(O|θ). A Bayesian approach uses Bayes rule and suggests adding prior knowledge over the weights p(θ) to calculate the maximum a-posteriori (MAP) estimator: Placing a prior introduces regularization to the network. We will address the advantages of this regularization in Section 4.

Extended Kalman Filter (EKF)
In this section we briefly outline the Extended Kalman filter (Anderson & Moore, 1979;Gelb, 1974). The EKF is a standard technique for estimating the state of a nonlinear dynamic system or for learning the weights of a nonlinear approximation function. In this paper we will focus on its latter role, meaning estimating θ. The EKF considers the following model: where θ t are the weights evaluated at time t, o t is the observation at time t and h(θ t ) is a nonlinear observation function. v t is the evolution noise, n t is the observation noise, both modeled as additive and white noises with covariance P vt and variance P nt respectively. As seen in the model presented in Equation (7) the EKF treats the weights θ t as random variables, similarly to the Bayesian approach. According to this perspective, the weights belong to an uncertainty set Θ governed by the mean and covariance of the weights distribution.
The estimation at time t, denoted asθ t|· is the conditional expectation of the weights with respect to the observed data. The EKF formulation distinguishes between estimates that are based on observations up to time t, θ t|t E[θ t |o 1:t ], and observations up to time t − 1, The conditional error covariances are given by: EKF considers several statistics of interest at each time step: The prediction of the observation function, the observation innovation, the covariance between the weights error and the innovation, the covariance of the innovation and the Kalman gain are defined respectively in Equations The above statistics serve for the update of the weights and the error covariance:

Solving Large-Scale RMDPs
In this section we explain how to combine EKF as a Bayesian method with Deep Q-learning and the robust formulation to solve large scale RMDPs with uncertainty in the transition probabilities.

Robust Temporal Difference Deep Q-Network (RTD-DQN)
Our first step in solving large scale RMDPs with on-line nonlinear approximations is to change the nBTDe presented in Equation (4) with the robust Bellman TD error (rBTDe) δ robust t,θ and minimize the following objective function at each time step: Here, y robust t,θ is the robust target label: Algorithm 1 RTD-DQN Input: P, γ, α; Initialize: O,θ 0|0 , t = 0. 1: for episode = 1 . . . , M do 2: With probability select a random action a i , otherwise select a i = arg max a Q(s i , a ;θ t|t−1 ) 4: Compute ∇ θt Q(s j , a j ;θ t|t−1 ).

7:
Update the weights: end for 10: end for Output:θ t|t The setS is the set of all possible next states from state s t when taking action a t , and it is drawn from the uncertainty set P (·|st,at) . Note that y robust t,θ is a variation of the robust Bellman function for the optimal Q-function presented in Equation (1). It looks for worst case transitions that may reduce the value of the expected Q-function, and sets the robust target label value according to the minimal expectation. In return, the agent that receives these robust target labels, learns how to act optimally over these transitions.
This approach for solving RMDPs is presented in Algorithm 1, RTD-DQN. It is based on the DQN algorithm (Mnih et al., 2013) but incorporates the robust target label instead of the nominal one. RTD-DQN initializes the weightsθ 0|0 with small random values and holds an experience reply O with finite capacity N . The environment is initialized at the beginning of each episode. We denote the estimation process with subscript t, while the observations at each episode are denoted with subscript i. During an episode the agent observes the uncertainty set P (·|si,ai) for the set of next possible statesS (·|si,ai) . For each mini-batch sample o j , the agent computes y robust j,θ (o j ) (14) and updates the weights according to the gradient descent step (5) with y robust j,θ replacing y nominal j,θ . Note that the environment transitions to state s i+1 that is drawn from the true unknown MDP model parameter P . However, actions taken by the agent adhere the robust policy, based on the robust target labels. The output of the RTD-DQN algorithm is the MLE weights estimatorθ M LE t|t . The RTD-DQN algorithm incorporates the robust target label into the weights update, but it does not account for uncertainty in the weights. This uncertainty is important for robustness properties. In the next section we suggest to use EKF for this purpose.

EKF for Deep Q-learning
We propose to improve the performance of RTD-DQN by accounting for uncertainty in the weights in addition to the uncertainty in the transition probabilities. We suggest to use EKF for solving Deep Q-leaning networks. For this purpose, using the formulation for EKF presented in Section 3.4, the observation at time t is simply the nominal target label y nominal t,θ (o t ) (4) and the observation function is the state-action Q-function, h(θ t ) = Q(s t , a t ; θ t ). With this formulation, the EKF model for DQN with Bayesian approach becomes: (15) The EKF uses a first order Taylor series linearization for the observation function (Q-function): whereθ is typically chosen to be the previous estimation of the weights at time t − 1,θ t|t−1 . This linearization helps in computing the statistics of interest (see the supplementary material for more detailed derivations): The Kalman gain then becomes: and the update for the weights of the Q-function and the error covariance are: It is interesting to note that the Kalman gain K t (17) can be interpreted as an adaptive learning rate for each individual weight that implicitly incorporates the uncertainty of each weight. This approach resembles familiar stochastic gradient optimization methods such as Adagrad (Duchi et al., 2011), AdaDelta (Zeiler, 2012), RMSprop (Tieleman & Hinton, 2012) and Adam (Kingma & Ba, 2014), for different choices of P t|t−1 and P nt . We refer the reader to Ruder (2016).
We now revisit the MAP estimator presented in Equation (6). Given the observations gathered up to time t (denoted as o 1:t ) we can write: Here, instead of using the prior of the weights, we present an equivalent derivation for the posterior of the weights conditioned on o 1:t , based on the likelihood of a single observation o t and the posterior conditioned on o 1:t−1 (Van Der Merwe, 2004). When estimating using the EKF, it is common to make the following assumptions regarding the likelihood and the posterior: Assumption 2. The posterior distribution p(θ t |o 1:t−1 ) is assumed to be Gaussian: θ t |o 1:t−1 ∼ N (θ t|t−1 , P t|t−1 ).
We use the notation y t (o t ) for a general target label (for example y nominal t,θ (o t ) or y robust t,θ (o t )) that serves as an observation in the EKF formulation. Based on the Gaussian assumptions, we can derive the following Theorem: Theorem 1. Under Assumptions 1 and 2,θ EKF t|t (18) minimizes at each time step t the following regularized objective function: The proof for Theorem 1 appears in the supplementary material. It is based on solving the maximization problem in Equation (19) using the EKF model (15) and the Gaussian assumptions in Assumptions 1 and 2.
Note that this objective function is a regularized version of the objective function in Equation (2), where the weights are weighted according to the error covariance matrix P t|t−1 . The nBTDe δ nominal t,θ is the same as in Equation (3) and the nominal target label is the same as in Equation (4). The observation noise variance P nt can be interpreted as the regularization coefficient (Rivals & Personnaz, 1998) and we can examine it from two points of view: (1) Looking at P nt as the amount of confidence we have in the observations: if the observations are noisy, we should consider larger values for P nt . (2) Treating P nt as a regularization coefficient: when observations are noisy we would like to put larger impact on the weights prior by increasing P nt .

4:
With probability select a random action a i , otherwise select a i = arg max a Q(s i , a ;θ t|t−1 )

5:
Observe o i = {s i , a i , r i , s i+1 ,S (·|si,ai) } and store it in O.

9:
Update the weights and error covariance: end for 12: end for Output:θ t|t and P t|t

Deep Robust Extended Kalman Filter (Deep-RoK)
We are now ready to combine the EKF as a Bayesian method with the rBTDe δ robust t,θ (13). This approach incorporates uncertainty in the Q-function weights and allows propagation of the uncertainty in the transition probabilities, P, into the uncertainty set of the weights, Θ. This approach can be utilized to solve large scale RMDPs with nonlinear approximation and in an on-line fashion. Practically we change the objective function presented in Equation (2) by both adding regularization according to the EKF formulation and by replacing the nBTDe with the rBTDe δ robust t,θ . This results in the following Theorem: Theorem 2. Under Assumptions 1 and 2,θ robust t|t (50) minimizes at each time step t the following regularized robust objective function: The proof for Theorem 2 follows the same arguments as the proof for Theorem 1, but uses rBTDe δ robust t,θ (13), instead . The proof appears in the supplementary material.
Looking at the weights update in Equation (50) and the definition of the Kalman gain K t in Equation (17), we can see that by combing the rBTDe with the EKF formulation, the Kalman gain propagates the new information from the robust target label (derived from the transition probabilities uncertainty set P), back down into the weight uncertainty set Θ, before combining it with the estimated weight value. This Bayesian approach for solving RMDPs is presented in Algorithm 2, Deep-RoK. Deep-RoK receives as input the initial prior for the error covariance P 0|0 , the evolution noise covariance P vt , the observation noise variance P nt , the uncertainty set P and a discount factor γ. Its observations are similar to the ones described for the RTD-DQN algorithm, but the weights update is different: Deep-RoK uses the EKF updates (50) with the robust target label y robust j,θ which is based on the uncertainty set P.

The output of the Deep-RoK algorithm is the MAP weights estimatorθ MAP
t|t and the error covariance matrix P t|t . Deep-RoK is suitable for any prior P 0|0 , including priors that assume correlations between the weights. Figure 3 presents a block diagram which illustrates the flow of weights updates in the Deep-RoK algorithm.
During the test phase, the output of the Deep-RoK algorithm provides flexibility to the agent. It can choose to use the point estimateθ t|t as a single NN on which it performs tests. Recall thatθ t|t incorporates the information regarding the weights uncertainty set Θ and the transitions uncertainty set P. However, the agent has the ability to take advantage of the additional output P t|t and to test the results over an ensemble of NNs by sampling weights from a distribution with meanθ t|t and covariance P t|t .

Experiments
We demonstrate the performance of the RTD-DQN and Deep-RoK algorithms on the classic RL environment Cart-Pole with nonlinear Q-function approximations. In the Cart-Pole domain the agent's goal is to balance a pole atop a cart while controlling the direction of the force applied on the cart. The action space is discrete and contains two possible actions: applying a constant force to the right or to the left. The state space is continuous, where each state is fourdimensional (x,ẋ, θ,θ) consisting respectively of the cart position, cart velocity, pole angle and the pole's angular velocity. At each time step the agent receives an immediate reward of 1 if the pole has not fallen down and if the cart has not run off the right or the left boundary of the screen. If these cases occur, the agent receives a reward of 0 and the episode is terminated. The transitions follow the dynamic model of the system and are based on the parameters ψ = {cart mass, pole length}. Additional technical details regarding this experiment can be found in the supplementary material.
In order to introduce robustness into the Cart-Pole domain, we assumed that the parameters ψ are not precisely known in advance but rather they lie in a known uncertainty set ψ ∈ Ψ. This in turn introduces uncertainty in the transition probabilities defined by the set P(ψ). We considered the range of 0.2 − 1.4 meters for the pole length and 0.1 − 7 Kg for the cart mass. At each episode we uniformly sampled 5 values from each of the parameters ranges. These samples aided us in building P. We used the implementation CartPole-v0 contained in the OpenAI gym (Brockman et al., 2016) where we added the uncertainty set parameters into the implementation.
We trained the agent with the RTD-DQN and the Deep-RoK algorithms, both using the rBTDe. We compare their performance with a Double-DQN agent (Van Hasselt et al., 2016) that uses the nBTDe. All agents were trained for M = 700 episodes and the results are drawn from testing the trained models over M test = 500 episodes.
In Figure 4(a)-(c) we show the performance of all three agents for different values of pole length. In Figure 4(d)-(f) we show the % of success of all three agents for different values of pole length and cart mass. We can see that the Double-DQN agent performs well (high cumulative reward) on the parameters it was trained on (pole length 0.5 meter and cart mass 1.5 Kg, marked in red in the graphs). However it performs poorly on more extreme values of these parameters. The Double-DQN agent learned a policy which is highly optimized for the specific parameters is was trained on, but is brittle under parameter mismatch. The RTD-DQN agent has high performance also on parameter values which are not the nominal values, but they are taken into account in the uncertainty set P through the rBTDe. The Deep-RoK agent has the most robust results and it keeps high performance for a large range of pole lengths and cart masses. The Bayesian approach in this algorithm provides the agent with more robustness to uncertain parameters.

Discussion
We introduced two algorithms for solving large scale RMDPs using on-line nonlinear estimations. The RTD-DQN algorithm incorporates the robust Bellman temporal difference error into a robust loss function, yielding robust policies for the agent. The Deep-RoK algorithm uses a robust Bayesian approach, based on the Extended Kalman Filter, to account for both the uncertainty in the weights of the value function and the uncertainty in the transition probabilities. We proved that the Deep-RoK algorithm outputs the weights which minimize the robust EKF lost function. We demonstrated the performance of our algorithms on the Cart-Pole domain and showed that our robust approach performs better comparing to a nominal DQN agent. We believe that real-world domains, such as autonomous driving or investment strategies, can benefit from using a robust approach to improve their agents performances by accounting for uncertainties in their models.
Future work should address accounting for changes in the confidence level during the evaluation procedure, directed exploration by using uncertainty estimates and robustness in policy gradient algorithms. Zeiler, Matthew D. Adadelta: an adaptive learning rate method. arXiv preprint arXiv:1212.5701, 2012. .

A. Extended Kalman Filter (EKF)
In this section we briefly outline formulation of the Extended Kalman filter (Anderson & Moore, 1979;Gelb, 1974). The EKF considers the following model: where θ t are the weights evaluated at time t, o t is the observation at time t and h(θ t ) is a nonlinear observation function.
The observation noise n t is white (E[n t ] = 0) with variance P nt E[n 2 t ], E[n t n t ] = 0, ∀t = t . The EKF sets the estimation of the weights θ at time t according to the conditional expectation: where o 1:t are the observations gathered up to time t . The weights errors are defined by: The conditional error covariances are given by: EKF considers several statistics of interest at each time step: The prediction of the observation function:

The observation innovation:
The covariance between the weights error and the innovation: The covariance of the innovation: Põ t E[(õ t|t−1 ) 2 |o 1:t−1 ] + P nt .
The Kalman gain: The above statistics serve for the update of the weights and the error covariance:

B. EKF for Deep Q-learning
When applying the EKF formulation to Deep Q-leaning networks, the observation at time t is simply the nominal target label y nominal t,θ (o t ): where the weight θ is a fixed set of weights. The observation function is the state-action Q-function: We use the notation y t (o t ) for a general target label (for example y nominal t,θ (o t ) or y robust t,θ (o t )) that serves as an observation in the EKF formulation. With this formulation, the EKF model for DQN with Bayesian approach becomes: The EKF uses a first order Taylor series linearization for the observation function (Q-function): whereθ is typically chosen to be the previous estimation of the weights at time t − 1,θ t|t−1 . This linearization helps in computing the statistics of interest. Recall that the expectation here is over the random variable θ t whereθ t|t−1 is fixed. The prediction of the observation function: We conclude that: The observation innovation: The covariance between the weights error and the innovation: Pθ t,ỹ(ot) = P t|t−1 ∇ θt Q(s t , a t ;θ t|t−1 ) The covariance of the innovation: ∇ θt Q(s t , a t ;θ t|t−1 ) P t|t−1 ∇ θt Q(s t , a t ;θ t|t−1 ) + P nt

−1
The update for the weights of the Q-function and the error covariance are: as we prove in Theorem 1.

C. A Bayesian approach: MAP estimator
We adopt the Bayesian approach in which we are interested in finding the optimal set of weights θ t that maximizes the posterior distribution of the weights given the observations we have gathered up to time t, denoted as the o 1:t .
According to Bayes rule, the posterior distribution is defined as: where p(o 1:t |θ) is the likelihood of the observations given the weights θ and p(θ) is the prior distribution over θ.
We will expend the term of the posterior (Van Der Merwe, 2004): The transition in (36) is according to the conditional probability: The transition in (37) is according to the conditional independence: p(o t |o 1:t−1 , θ t ) = p(o t |θ t ), and we multiplied the numerator and the dominator by p(o 1:t−1 ). The transition in (38) is according to Bayes rule: p(θ t |o 1:t−1 ) = p(o1:t−1|θt)p(θt) p(o1:t−1) . The MAP estimator for θ t is the one who maximizes the posterior distribution described in (38).
In (39) We used the derivation in (38) and the fact that the argument which maximizes the posterior is the same as the argument that maximizes the log(·) of the posterior. In addition this argument also minimizes the negative log(·).
We will replace here the current observation o t with the current target label y t (o t ) and receive:

D. Gaussian assumptions
When estimating using the EKF, it is common to make the following assumptions regarding the likelihood and the posterior in Equation (40): Assumption 2. The posterior distribution p(θ t |o 1:t−1 ) is assumed to be Gaussian: θ t |o 1:t−1 ∼ N (θ t|t−1 , P t|t−1 ).
Following are the calculations for the means and covariances in Assumptions 1 and 2. For the likelihood p(y t (o t )|θ t ):

E. Theoretical results
Based on the Gaussian assumptions, we can derive the following Theorem: Theorem 1. Under Assumptions 1 and 2,θ EKF t|t (35) minimizes at each time step t the following regularized objective function: whereθ EKF t|t ∈ arg min θt L EKF t (θ t ).
Proof. We solve the minimization problem in (40) by substituting the Gaussian Assumptions 1 and 2. We show that where |·| denotes the determinant. We receive the following objective function: We replace y t (o t ) with the nominal target label y nominal t,θ (o t ) and define the nominal Bellman TD error δ nominal We receive: which is exactly the objective function (41) in Theorem 1.
To minimize this objective function we take the derivative of L EKF t (θ t ) with respect to θ t : (θt, ot)∇ θ t Q(st, at; θt)] We use the linearization of the Q-function in Equation (29) and the definition of δ nominal t,θ in Equation (42): For simplicity we denote q by q = ∇ θt Q(s t , a t ;θ t|t−1 ).
We now develop the term P −1 t|t−1 + 1 Pn t qq −1 that appears in (43) by using the matrix inversion lemma: (B −1 + CD −1 C ) −1 = B − BC(D + C BC) −1 C B (46) where B is a square symmetric positive-definite (and hence invertible) matrix. For this purpose we assume that the error covariance matrix of θ t , P t|t−1 , is symmetric and positive-definite.
P t|t−1 − P t|t−1 q(Pn t + q P t|t−1 q) −1 q P t|t−1 = (44) We can write the update of the weights error covariance as: We conclude the proof by stating that the optimal weight θ EKF t|t in (35) is the solution to the minimization of the objective function in (41): We are now ready to prove Theorem 2. For this purpose we recall the definition of δ robust t,θ , the robust Bellman TD error and y robust t,θ the robust target label: δ robust t,θ (θ t , o t ) = y robust t,θ (o t ) − Q(s t , a t ; θ t ).
y robust t,θ (ot) = rt + γ min The setS is the set of all possible next states from state s t when taking action a t , and it is drawn from the uncertainty set P (·|st,at) . Theorem 2. Under Assumptions 1 and 2,θ robust t|t (50) minimizes at each time step t the following regularized robust objective function: wherê θ robust t|t =θ t|t−1 +E ot∼p(·) K t y robust t,θ (o t )−Q(s t , a t ;θ t|t−1 ) , (50) andθ robust t|t ∈ arg min θt L robust EKF t (θ t ).
Proof. The proof for Theorem 2 follows the same arguments as the proof for Theorem 1. The difference is in the target label definition. Here we use y robust t,θ instead of y nominal t,θ . Since y robust t,θ does not depend on the random variable θ t , it is fixed when taking the derivative of the objective function with respect to θ t .

F. Cart-Pole experiment
We describe here technical details regarding the Cart-Pole experiment. All algorithms (Double-DQN (Van Hasselt et al., 2016), RTD-DQN and Deep-RoK) used a feed forward fully connected neural network with 2 hidden layers with the tanh activation function. The input dimension is 4 (x,ẋ, θ,θ), the output dimension is 2 (two possible actions) and each hidden layer is composed of 20 neurons. The total number of weights in the network is n = 562. The networks were trained on mini-batches of transitions, 10 samples in each mini-batch. We used a discount factor of γ = 0.9. All algorithms were trained for 700 episodes. Double-DQN and RTD-DQN were trained with the Adam optimizer (Kingma & Ba, 2014) with learning rate α = 0.001. Deep-RoK was trained using the EKF (as described in the main paper) with learning rate α = 1, observation noise P nt = 0.001, evolution noise P vt = 0.01·I and error covariance prior P 0|0 = I (I is the identity matrix). The results presented in the paper are the mean and standard deviation of the cumulative reward, obtained by applying a -greedy policy ( = 0.1) over the learned network for 500 episodes.
The Double-DQN algorithm was trained on the nominal values pole length=0.5m and cart mass=1.5kg. The uncertainty set P(ψ), ψ = {pole length, cart mass} used in RTD-DQN and Deep-RoK algorithms was constructed by sampling uniformly values from the range: pole length ∈ {0.2, 1.4}m; cart mass ∈ {0.1, 7}kg. At the beginning of each episodes, we sampled 5 values from the above ranges and constructed the uncertainty set P for this episode.