Year: 2021

Abstract:
In real scenarios, state observations that an agent observes may contain measurement errors or adversarial noises, misleading the agent to take suboptimal actions or even collapse while training. In this paper, we study the training robustness of distributional Reinforcement Learning (RL), a class of state-of-the-art methods that estimate the whole distribution, as opposed to only the expectation, of the total return. Firstly, we propose State-Noisy Markov Decision Process (SNMDP) in the tabular case to incorporate both random and adversarial state observation noises, in which the contraction of both expectation-based and distributional Bellman operators is derived. Beyond SN-MDP with the function approximation, we firstly analyze the vulnerability of least squared loss in expectationbased RL, and by contrast theoretically characterize the bounded gradient norm of histogram-based distributional loss, accounting for the better training robustness of distribution RL. Finally, extensive experiments on the suite of games show that in SN-MDP-like setting both expectation-based and distributional RL can converge albeit corresponding to different levels under various state observation noises. However, distributional RL can enjoys better training robustness in the more complicated noisy state observation settings compared with its expectationbased counterpart.

text: In real scenarios, state observations that an agent observes may contain measurement errors or adversarial noises, misleading the agent to take suboptimal actions or even collapse while training. In this paper, we study the training robustness of distributional Reinforcement Learning (RL), a class of state-of-the-art methods that estimate the whole distribution, as opposed to only the expectation, of the total return. Firstly, we propose State-Noisy Markov Decision Process (SNMDP) in the tabular case to incorporate both random and adversarial state observation noises, in which the contraction of both expectation-based and distributional Bellman operators is derived. Beyond SN-MDP with the function approximation, we firstly analyze the vulnerability of least squared loss in expectationbased RL, and by contrast theoretically characterize the bounded gradient norm of histogram-based distributional loss, accounting for the better training robustness of distribution RL. Finally, extensive experiments on the suite of games show that in SN-MDP-like setting both expectation-based and distributional RL can converge albeit corresponding to different levels under various state observation noises. However, distributional RL can enjoys better training robustness in the more complicated noisy state observation settings compared with its expectationbased counterpart.

heading: 1 INTRODUCTION
text: Learning robust and high-performance policies for continuous state-action reinforcement learning (RL) domains is crucial to enable the successful adoption of deep RL in robotics, autonomy, and control problems. However, recent works have demonstrated that deep RL algorithms are vulnerable either to model uncertainties or external disturbances (Huang et al., 2017; Pattanaik et al., 2017; Ilahi et al., 2020; Chen et al., 2019; Zhang et al., 2020; Shen et al., 2020; Singh et al., 2020; Guan et al., 2020). Particularly, model uncertainties normally occur in a noisy reinforcement learning environment where the agent often encounters systematic or stochastic measurement errors on state observations, such as the inexact locations and velocity obtained from the equipped sensors of a robot. On the other hand, external disturbances are normally adversarial in nature. For instance, the adversary can construct adversarial perturbations on state observations to degrade the performance of deep RL algorithms. These two factors lead to noisy state observations that influence the performance of algorithms, precluding the success of reinforcement learning in real-world applications.
Existing works mainly focus on improving the robustness of algorithms in the test environment with noisy state observations. Smooth Regularized Reinforcement Learning (Shen et al., 2020) introduced a regularization to enforce smoothness in the learned policy, and thus improved its robustness against measurement errors in the test environment. Similarly, the State-Adversarial Markov decision process (SA-MDP) (Zhang et al., 2020) was proposed and the resulting principled policy regularization enhances the adversarial robustness of various kinds of RL algorithms against adversarial noisy state observations. However, both of these works assumed that the agent can access clean state observations during training, which is normally not feasible when the environment is inherently noisy, such as unavoidable measurement errors. Thus, the maintenance and formal analysis of policies robust to noisy state observations during training is a worthwhile area of research.
On the other hand, recent distributional reinforcement learning algorithms, including C51 (Bellemare et al., 2017), Quantile-Regression DQN (QRDQN) (Dabney et al., 2018b), Implicit Quantile Networks (Dabney et al., 2018a) and Moment-Matching DQN (MMD) (Nguyen et al., 2020), constantly set new records in Atari games, gaining huge attention in the research community. However, existing literature mainly focuses on the performance of algorithms, other benefits, including the robustness in the noisy environment, of distributional RL algorithms are less studied. As distributional RL can leverage additional information about distribution that captures the uncertainty of the environment more accurately, it is natural to expect that distributional RL with this better representation capability can be less vulnerable to the noisy environment while training, which motivates our research.
In this paper, we investigate the robustness of distributional RL against various kinds of state observation noises encountered during training. Firstly, we propose a general State-Noisy MDP in the tabular setting, in which we prove the convergence of distributional Bellman operator. We further extend SN-MDP to the function approximation case by considering more complex noisy state observations. Notably, we analyze the vulnerability of classical RL and in contrast characterize the Lipschitz continuity blessing resulting from the Histogram distributional loss in distributional RL, which leads to a bounded gradient norm. This better behaved gradient mitigates the impact of noisy states on the objective function, accounting for the less vulnerability of distributional RL while training. Finally, extensive experiments demonstrate that both expectation-based and distributional RL algorithms can converge in SN-MDP-like settings. More importantly, distributional RL algorithms tend to achieve better robust performance in the presence of more complex state observation noises compared with its expectation-based counterpart that may even diverge in some cases. These empirical results in Section 5 echo our previous theoretical results in both Section 3 and 4. Overall, the training robustness advantage of distributional RL algorithms we revealed facilitates their deployment especially in the noisy environment.

heading: 2 BACKGROUND

heading: 2.1 DISTRIBUTIONAL REINFORCEMENT LEARNING
text: In the tabular setting without noisy states, the agent’s interaction with its environment can be naturally modeled as a standard Markov Decision Process (MDP), a 5-tuple (S,A, R, P, γ). S and A are the state and action spaces, P : S × A × S → [0, 1] is the environment transition dynamics, R : S ×A× S → R is the reward function and γ ∈ (0, 1) is the discount factor.
Value Function vs Value Distribution. Firstly, we denote the return where st = s as Zπ(s) =∑∞ k=0 γ
krt+k+1, representing the cumulative rewards following a policy π, and rt+k+1 is reward scalar obtained in the step t + k + 1. In the algorithm design, traditional expectation-based RL normally focuses on value function V π(s), the expectation of the random variable Zπ(s):
V π(s) := E [Zπ(s)] = E [ ∞∑ k=0 γkrt+k+1 | st = s ] . (1)
In contrast, in the distributional RL setting, we focus on the value distribution, the full distribution of Zπ(s), and the state-action value distribution Zπ(s, a) in the control problem where st = s, at = a. Both of these distributions can better capture the uncertainty of returns in the MDP beyond just its expectation (Dabney et al., 2018a; Mavrin et al., 2019).
Distributional Bellman Operator. In expectation-based RL, we update the value function via the Bellman operator T π , while in distributional RL, the updating is on the value distribution via the distributional Bellman operator Tπ . To derive Tπ , we firstly define the transition operator Pπ : Z → Z:
PπZ(s, a) :D= Z (S′, A′) , S′ ∼ P (·|s, a), A′ ∼ π (·|S′) , (2)
where we use capital letters S′ and A′ to emphasize the random nature of both, and :D= indicates convergence in distribution. For simplicity, we denote Zπ(s, a) by Z(s, a). Thus, the distributional Bellman operator Tπ is defined as:
TπZ(s, a) : D = R(s, a, S′) + γPπZ(s, a). (3)
More importantly, Tπ is still a contraction for policy evaluation under the maximal form of the Wasserstein metric dp over the true and parametric value distributions (Bellemare et al., 2017; Dabney et al., 2018b), where the p-Wasserstein metric dp is defined as
dp = (∫ 1 0 ∣∣F−1Z∗ (ω)− F−1Zθ (ω)∣∣p dω)1/p , (4) which minimizes the distance between the true value distribution Z∗ and the parametric distribution Zθ. F−1 is the inverse cumulative distribution function of a random variable with the cumulative distribution function as F . In the control setting, the distributional analogue of the Bellman optimality operator converges to the set of optimal value distributions, although it is in a weak sense and requires more involved arguments (Dabney et al., 2018b).

heading: 2.2 TWO KINDS OF NOISY STATE OBSERVATIONS
text: We investigate both random and adversarial training robustness, i.e., the performance of RL algorithms under these two types of noisy state observations, between the expectation-based and distributional RL algorithms. We consider continuous state observations with continuous noises. In the random noisy state case, we apply Gaussian noises with mean 0 and different standard deviations to state features to simulate the measurement error stemming from various sources.
In the adversarial state perturbation setting, we construct white-box adversarial perturbations on state observations for the current policy during training, following the strategy proposed in (Huang et al., 2017; Pattanaik et al., 2017) that leveraged the gradient information of an engineered loss function. In particular, we denote atw as the “worst” action, with the lowest probability from the current policy πt(a|s) in the training step t. Thus, the optimal adversarial perturbation ηt, constrained in an -ball, can be derived by minimizing the objective function J :
min η J(st + η, πt) = − n∑ i=1 pti log πt(ai|st + η), s.t.‖η‖ ≤ , (5)
where pti = 1 if i corresponds to the index of the least-chosen action, i.e. the w-th index in the vector a, otherwise pti = 0. In other words, we construct a target one-hot action p
t with 1 assigned to the index of the least-chosen action. Through this minimization in the form of the cross entropy loss, we can construct the state perturbations ηt that can force the policy to choose the least-chosen action atw in each t step.

heading: 3 TABULAR CASE: STATE-NOISY MARKOV DECISION PROCESS
text: In this section, we extend State-Adversarial MDP (Zhang et al., 2020) to a more general StateNoisy Markov Decision Process (SN-MDP), and particularly provide a proof of the convergence and contraction of distributional Bellman operator in this setting.

heading: 3.1 DEFINITIONS
text: As shown in Figure 1, SN-MDP is a 6-tuple (S,A, R, P, γ,N ), where the noise generating mechanism N(·|s) maps the state from s to v(s) using either random or adversarial noise with the Marko-
vian and stationary probability N(v(s)|s). It is worthwhile to note that the explicit definition of the noise mechanism N here is based on discrete state transitions, but the analysis can be naturally extended to the continuous case if we let the state space go to infinity. Moreover, let B(s) be the set that contains the allowed noise space for the noise generating mechanism N , i.e., v(s) ∈ B(s). Following the setting in (Zhang et al., 2020), we only manipulate state observations but do not change the underlying environment transition dynamics based on s or the agent’s actions directly. As such, our SN-MDP is more suitable to model the random measurement error, e.g., sensor errors and equipment inaccuracies, and adversarial state observation perturbations in safety-critical scenarios.

heading: 3.2 ANALYSIS OF SN-MDP FOR EXPECTATION-BASED RL
text: We define the value function Ṽπ◦N given π in SN-MDP. The Bellman Equations are given by: Ṽπ◦N (s) = ∑ a ∑ v(s) N(v(s)|s)π(a|v(s)) ∑ s′ p(s′|s, a) · [ R(s, a, s′) + γṼπ◦N (s ′) ] . (6)
The random noise transits s into v(s) with a certain probability and the adversarial noise is the special case ofN(v(s)|s) whereN(v∗(s)|s) = 1 if v∗(s) is the optimal adversarial noisy state given s, and N(v(s)|s) = 0 otherwise. We denote Bellman operators under random noise mechanism Nr(·|s) and adversarial noise mechanism N∗(·|s) as T πr and T πa , respectively. This implies that T πr Ṽπ◦N = Ṽπ◦Nr and T πa Ṽπ◦N = Ṽπ◦N∗ . We extend Theorem 1 in (Zhang et al., 2020) to both random and adversarial noise scenario, and immediately obtain that both T πr and T πa are contraction operators in SN-MDP. We explain this in Theorem 3 of Appendix A.
The pivotal conclusion from Theorem 3 is T πa Ṽπ◦N = minN Ṽπ◦N . This implies that the adversary attempts to minimize the value function, forcing the agent to select the worse-case action among the allowed transition probability space N(·|s) for each state s. The main proof idea is that Bellman updates in SN-MDP result in the convergence to the value function for another “merged” policy π′ where π′(a|s) = ∑ v(s)N(v(s)|s)π(a|v(s)). The value function for the merged policy might ba far away from that for the original policy π, which tends to worsen the performance of RL algorithms.

heading: 3.3 ANALYSIS OF SN-MDP IN DISTRIBUTIONAL RL
text: In the SN-MDP setting for distributional RL, the new distributional Bellman equations use new transition operators in place of Pπ in Eq. 2. The new transition operators Pπr and Pπa , for the random and adversarial settings, are defined as:
Pπr ZN (s, a) : D = ZNr (S ′, A′), A′ ∼ π(·|V (S′)), and PπaZN (s, a) : D = ZN∗(S ′, A′), A′ ∼ π(·|V ∗(S′)), (7) where V (S′) ∼ Nr(·|S′) is the state random variable after the transition, and V ∗(S′) is attained from N∗(·|S′) under the optimal adversary. Besides, S′ ∼ P (·|s, a). Thus, the corresponding new distributional Bellman operators Tπr and T π a are:
TπrZN (s, a) : D = R(s, a, S′) + γPπr ZN (s, a), and TπaZN (s, a) : D = R(s, a, S′) + γPπaZN (s, a).
(8) In this sense, four sources of randomness define the new compound distribution in the SN-MDP: (1) randomness of reward, (2) randomness in the new environment transition dynamics Pπr or Pπa that additionally includes (3) the stochasticity of the noisy transition N , and (4) the random next-state value distribution Z(S′, A′). Besides, the premise of the robustness of distributional RL against noisy state observations lies in the convergence of the new derived distribution Bellman Operators in SN-MDP setting. We proved this convergence and contraction for policy evaluation in Theorem 1.
Theorem 1. (Convergence and Contraction of Distributional Bellman operators in the SN-MDP) Given a policy π, we define the distributional Bellman operators Tπr and T π a in Eq. 8, and consider the Wasserstein metric dp, the following results hold.
(1) Tπr is a contraction under the maximal form of dp.
(2) Tπa is also a contraction under the maximal form of dp, following the greedy adversarial rule, i.e., N∗(·|s′) = argminN(·|s′) E [Z(s′, a′)] where a′ ∼ π(·|V (s′)) and V (s′) ∼ N(·|s′).
We provide the proof in Appendix B. The convergence of distributional Bellman operators in the SNMDP is one of our main contributions. This result allows us to deploy distributional reinforcement learning algorithms comfortably even in settings with noisy state observations.

heading: 4 FUNCTION APPROXIMATION CASE: NOISY SETTINGS BEYOND SN-MDP
text: In real scenarios, especially safety-critical cases, perturbations on state observations can be more complicated. For instance, the adversary might perform attacks at certain intervals, yielding unbalanced state observation pairs with a perturbed current state and a benign next state and vice versa. This type of unbalanced perturbations is outside the scope of State-Noisy MDP we analyzed in the last section and can have different impacts on the convergence of expectation-based and distributional RL algorithms. In this section, we firstly point out the vulnerability nature of expectation-based RL although we consider the bounded rewards in Section 4.1. Next, we characterize the robustness blessing of distributional RL based on Histogram distributional loss (Imani & White, 2018) with derived bounded gradient norms unlike the unrestricted one in expectationbased RL. Finally, as an extension we analyze the impact of more complex state observations on TD convergence and further conduct a sensitivity analysis by the influence function.
Notation. We derive theoretical results with the linear function approximator. For the expectationbased RL, the value estimate v̂ : S × Rd → R is formed simply as the inner product between state features x(s) and weights w ∈ Rd, given by v̂(s,w) def= w>x(s). At each step, the state feature can be rewritten as xt def = x (St) ∈ Rd. The distributional RL setting is given in Section 4.2.

heading: 4.1 VULNERABILITY FOR EXPECTATION-BASED RL
text: In the classical RL with function approximation, a natural objective function is Mean Squared Value Error (Sutton & Barto, 2018) denoted VE, which is weighted by the state distribution µ:
VE(w) . = ∑ s∈S µ(s) [vπ(s)− v̂(s,w)]2 , (9)
where µ(s) is the fraction of time spent in s. To solve this kind of weighted least squared minimization, we leverage Stochastic Gradient Descent (SGD) and the weight updating rule can be formulated as
wt+1 . = wt + α [vπ (st)− v̂ (st,wt)]∇v̂ (st,wt) . = wt + α ( Ut −w>t xt ) xt
(10)
where α is the step size and the target Ut can be either an unbiased estimate via Monte Carlo method with Ut = ∑∞ k=0 γ
krt+k+1, or a biased estimate via TD learning with Ut = rt+1 + γw>t xt+1. Let gVE be the empirical version of VE(w). To investigate the vulnerability of expectation-based RL over state features, we focus on the gradient norm of gVE regarding x(s) (or xt). For a fair comparison with distributional RL in Section 4.2, we additionally bound the norm of w, i.e., ‖w‖ ≤ l, which can also be easily satisfied by imposing `1 or `2 regularization. Therefore, the upper bound of gradient norm of gVE is
‖ ∂ ∂x(s) gVE‖ = |Ut −w > t xt|‖wt‖ ≤ |Ut −w>t xt|l. (11)
However, this upper bound |Ut − w>t xt|l can be arbitrary large as there is no restriction on |Ut − w>t xt| in either Monte Carlo or TD bootstrap estimate of Ut, which we elaborate as follows. Case 1: Estimate Ut via Monte Carlo. If we consider the bounded rewards, i.e., r ∈ [Rmin, Rmax], we can bound Ut as Ut = ∑∞ k=0 γ krt+k+1 ∈ [Rmin1−γ , Rmax 1−γ ]. However, the bounded rewards can not guarantee the bounded gradient norm of gVE as w > t xt can be sufficiently large.
Case 2: Estimate Ut via bootstrap estimate, e.g., TD (0). Consider TD (0) where Ut = rt+1 + γw>t xt+1. However, we can find that |Ut − w>t xt| = |rt+1 + w>t (γxt+1 − xt)| can still be sufficiently large due to the unrestricted term w>t (γxt+1 − xt). Therefore, we conclude that the unbounded gradient norm of objective function regarding state features for the expectation-based RL results in its vulnerability against state perturbations.

heading: 4.2 ROBUSTNESS BLESSING FOR DISTRIBUTIONAL RL
text: We show that in the function approximation setting, the distributional loss in distributional RL can additionally yield Lipschitz continuity regarding state features, thus leading to more stable gradients relatively to expectation-based RL.
In particular, in distributional RL our goal is to minimize L (Zθ,TZθ), where T is the distributional Bellman operator. Here we leverage histogram to parameterize the distribution Zθ based on KL divergence as L, yielding the histogram distributional loss (Imani & White, 2018). Specifically, we uniformly partition the support of x(s) into k bins, and let function f : X → [0, 1]k provide k-dimensional vector f(x(s)) of the coefficients indicating the probability the target is in that bin given x(s). Next, we use softmax based on the linear approximation x(s)>θi to express f , i.e., fi(x(s)) = exp ( x(s)>θi ) / ∑k j=1 exp ( x(s)>θj ) . Therefore, the histogram distributional loss L(Zθ,TZθ) between Zθ and TZθ can be derived as
Lθ = − k∑ i=1 pi log f θ i (x(s)), (12)
where θ = {θ1, ..., θk} and the target probability pi is the cumulative probability increment of target distribution TZθ within the i-th bin. Detailed derivation of the histogram distributional loss is given in Appendix C.
Based on this histogram distributional loss in distribution RL, we obtain Theorem 2 (proof in Appendix C), revealing that the distribution loss can result in additional Lipschitz continuity property that bounds the norm of gradient over state features x(s): Theorem 2. (Lipschitz Continuity of distributional RL) Consider the histogram distributional loss Lθ = − ∑k i=1 pi log f θ i (x(s)), where fi(x(s)) = exp ( x(s)>θi ) / ∑k j=1 exp ( x(s)>θj ) parameterized by θ = {θ1, ..., θk}. Assume ‖θi‖ ≤ l for ∀i = 1, .., k, then Lθ is kl-Lipschitz continuous w.r.t. x(s), yielding a bounded norm of its gradient, i.e.,∥∥∥∥ ∂∂x(s)Lθ
∥∥∥∥ ≤ kl (13) In conclusion, Theorem 2 shows that distributional loss in distributional RL can additionally enjoy kl-Lipschitz continuity compared with the expectation-based RL where the gradient norm of objective function is unbounded. Thus, the bounded gradient norm regarding state features of distributional RL mitigates the impact of state noises on the objective function while training, therefore yielding better training robustness.
Extension of TD Convergence and Sensitivity Analysis. Beyond the aforementioned robustness analysis on both expectation-based and distributional RL, we also conduct the analysis on the perturbation impacts of different state observations in the TD learning based on expectation-based RL, including the current, next and both state observations. In particular, conditions for TD convergence in these three different noisy state observation settings are derived in Theorem 4 of Appendix D, which are strongly related to the positive definiteness property of relevant matrixs. More importantly, the convergence conditions for current and next noisy state observations are harder than the condition in the noise-free setting and are normally divergent. Nevertheless, which situation is milder heavily depends on the task. Interested readers can refer to Appendix D for more details. In addition, we also conduct a sensitivity analysis by the influence function to characterize the effects that the state noise in particular observation has on an estimator in Theorem 5 of Appendix E. The conclusions we made are similar to the TD convergence analysis part. Note that although the extension analysis is based on the expection-based RL with linear function approximation, our empirical observations demonstrate our analysis results across both expectation-based and distributional RL. We defer detailed empirical verification in the following experimental section.
Remark. In this section, we firstly present the vulnerability of expectation-based RL against noisy state observations in Section 4.1, while we further derived the Lipschitz continuity blessing of distributional RL in Section 4.2, leading to more robustness against noisy state observations than expectation-based RL. In Section 5, we show that our empirical observations coincide with our theoretical results to further demonstrate the robustness advantage of distributional RL.

heading: 5 EXPERIMENTS
text: We make a comparison between expectation-based and distributional RL algorithms against various noisy state observations. We select DQN (Mnih et al., 2015) as the baseline, and QR-DQN (Dabney et al., 2018b) as its distributional counterpart. The previous analysis is either for policy evaluation or linear function approximation, but there are natural—though in some cases heuristic—extensions to the control setting and to non-linear function approximation.
Experimental Setup. We perform our algorithms on Cart Pole, Mountain Car, Breakout and Qbert games. We followed the procedure in (Ghiassian et al., 2020; Zhang & Yao, 2019). All the experimental settings, including parameters, are identical to the distributional RL baselines implemented by (Zhang, 2018; Dabney et al., 2018b). We perform 200 runs on both Cart Pole and Mountain Car and 3 runs on Breakout and Qbert. Reported Results are averaged with shading indicating the standard error. The learning curve is smoothed over a window of size 10 before averaging across runs. Please refer to Appendix H for more details.
Noisy State Observations. For the random noise, we use Gaussian noise with different standard deviations. In particular, for a better presentation to compare the difference, we select the standard deviations as 0.05, 0.1 in Cart Pole, 0.01, 0.0125 in Mountain Car, 0.01, 0.05 in Breakout and 0.05 in Qbert. For the adversarial noise, we followed (Zhang et al., 2020), where the set of noises B(s) is defined as an `∞ norm ball around s with a radius , given by `∞B(s) := {ŝ : ‖s− ŝ‖∞ ≤ }. We apply Projected Gradient Descent (PGD) version in (Pattanaik et al., 2017), with 3 fixed iterations while adjusting to control the perturbation strength. Concretely, for better presentation we select the perturbation size as 0.05, 0.1 in Cart Pole, 0.01, 0.1 in Mountain Car, 0.005, 0.01 in Breakout, and 0.005 in Qbert.
Experiments Structure. In Section 5.1, we consider the function approximation setting with TD learning where both current and next state observations are perturbed, leading to a SN-MDP-like setting as the vanilla SN-MDP is a tabular case. In this case, we found both DQN and QRDQN converge to different convergence points determined by the noise strength. Next, in Section 5.2 and 5.3, we investigate the robustness advantage of distributional RL, i.e., QRDQN, relative to expectationbased RL, i.e., DQN, under various random and adversarial state observations, respectively.

heading: 5.1 SN-MDP-LIKE SETTING
text: In the classical SN-MDP tabular case, each state will be perturbed via the noise mechanism N . We keep this noise structure and transform it into the function approximation setting with TD learning,
and thus both current and next state observations would be noisy. We further investigate the training robustness of both DQN and QRDQN against either random or adversarial state perturbations across these four games.
We focus on the adversarial setting as suggested in Figure 2. It turns out that all DQN and QRDQN algorithms under various strength of adversarial state noises converge, although they eventually obtained different average returns. This empirical observation is consistent with our theoretical analysis in Section 3 where both classical and distributional Bellman operators are contractive and thus convergent. In addition, Figure 5 also manifests that the final performance that algorithms attained has a decreasing tendency as the perturbation strength, i.e., standard deviation, increases especially for DQN. Remarkably, the final performance of QRDQN is more robust than DQN against different perturbation strength, especially in Breakout and Qbert games, although both DQN and QRDQN are convergent in this SN-MDP-like setting. For the random state observation setting, we provide the similar results in Figure 5 with detailed explanation in Appendix I.

heading: 5.2 SETTING BEYOND SN-MDP WITH RANDOM STATE NOISES
text: Beyond SN-MDP, we further investigate the training robustness of DQN and QRDQN in the more complicated unbalanced state observation setting as mentioned in Section 4, where the agent observe perturbations on current state observations. Similar results in the setting with the perturbed next state observations are given in Appendix J. In this subsection, we firstly focus on the function approximation case with random noises on current state observations, and the learning curves when the agent encounters different strength of random state noises are provided in Figure 3 across four games.
From Figure 3, it illustrates that the final performance of QRDQN (solid lines) is superior to DQN (DQN) in the same color given the same random state perturbations (the same standard deviation) when both DQN and QRDQN achieved similar average returns eventually (red dashed and solid lines). This implies that QRDQN enjoys better training robustness than DQN under the random noisy state observation setting. It is worthy to note that in Mountain Car game although DQN outperforms QRDQN almost across all training process, QRDQN under random state noises (blue and green lines) can surpass DQN with the same noise setting, yielding more training robustness. A more significant result is in Breakout where the training of QRDQN is less vulnerable to various random state perturbations, while the performance of DQN degrades and even diverges as the perturbation strength increases.

heading: 5.3 SETTING BEYOND SN-MDP WITH ADVERSARIAL STATE NOISES
text: Next, we probe the training robust of DQN and QRDQN in the setting where the agent encounters the adversarial state observations in the current state in the function approximation case. Figure 4 presents the learning curves of algorithms over four games against noisy states under different adversarial perturbation sizes .
The results under the adversarial state observations are similar to those in the random noises case. Specifically, both DQN and QRDQN algorithms tend to degrade when getting exposed to adversarial state observations, and even are more likely to diverge. For example, in Cart Pole both DQN (blue and green dotted lines) and QRDQN (blue and green solid lines) degraded to similar poor results when exposing to strong perturbation with = 0.05 and 0.1. However, a key observation is that QRDQN is capable of obtaining desirable performance while DQN even diverges. For instance, in both Breakout and Qbert game, DQN (dotted blue lines) under the adversarial perturbation with = 0.005 led to divergence, QRDQN (solid blue lines) can still attain relatively satisfactory performance eventually on the condition that the performance of both two algorithms are on part with each other without any noisy state observations (red lines).
Sensitivity Analysis of Different Perturbed States. To demonstrate the theoretical results (Theorem 4 and 5) in the Appendix based on TD convergence condition and influence function we ever mentioned in Section 4.2, we provide the consistent results in Appendix D and E. Interested readers can refer to Appendix D and E for a more detailed discussion.

heading: 6 DISCUSSION AND CONCLUSION
text: The Lipschitz continuity blessing is based on the histogram distributional loss, but it is more expected that similar conclusions can be made under Wasserstein or Crammer distance as these distances are more approachable in real distributional RL algorithms. We leave it as future works.
In this paper, we explored the training robustness of distributional RL against noisy state observations. After the convergence analysis of distributional RL in the SN-MDP, we proved the Lipschitz continuity property of distributional RL, accounting for its less vulnerability. We also provided the TD convergence conditions and a sensitivity analysis on more complex noisy settings. Experimental observations coincides with our theoretical results.
Ethics Statement. Our works reveals that distributional RL can enjoy the training robustness against noisy state observations. The advantage is useful to defend against the poisoning attacks, thus contributing to the privacy of algorithms. Based on our experience, there is no other ethic concerns of our work.
Reproducibility Statement. For the theoretical part, we clearly state the related assumption and detailed proof process in the appendix. In terms of the algorithm, our implementation is directly adapted from the public RL algorithms, including DQN and QR-DQN.

heading: A THEOREM 3 WITH PROOF
text: Theorem 3. (Convergence and Contraction of Bellman operators in the SN-MDP) Given a policy π, define the Bellman operator T : R|S| → R|S| under random and adversarial states noises by T πr and T πa , respectively. Denote a “merged” policy π′ where π′(a|s) = ∑ v(s)N(v(s)|s)π(a|v(s)) and S(π) is a policy set given π. Then we have:
(1) T πr is a contraction operator and can converge to Vπ′ , i.e., T πr Ṽπ◦N = Ṽπ◦N = Vπ′ , where multiple policies πr ∈ S(π) might exist with ∑ v(s)N(v(s)|s)πr(a|v(s)) = π ′(a|s).
(2) T πa is a contraction with the convergence satisfying T πa Ṽπ◦N∗ = minN Ṽπ◦N = Vπ◦N∗ , where N∗ is the optimal adversarial noise strategy. If the optimal policy πa exists, it satisfies πa(a|v∗(s)) = π(a|s) for each s and a, where v∗(s) is the adversarial noisy state manipulated by N∗(·|s).
Proof. Our proof is partly based on Theorem 1 and 2 in (Zhang et al., 2020), but adds more analysis on the converged policy especially under the random noisy states setting. The most important insight in the following proof is that the noise transition can be merged into the agent’s policy, resulting in a new “merged” policy π′.
Proof of (1) Firstly, as the Bellman Equation under the random noisy states is right the general form in Eq. 6, it automatically satisfies that T πr Ṽπ◦N = Ṽπ◦N when it converges. As for the proof of contraction, based on our insight about the new “merged” policy π′ where π′(a|s) = ∑ v(s)N(v(s)|s)π(a|v(s)), we can rewrite our Bellman Operator as:
T πr Ṽπ◦N (s) = ∑ a π′(a|s) ∑ s′ p(s′|s, a) [ R(s, a, s′) + γṼπ◦N (s ′) ]
= R(s) + γ ∑ s′ P ′s,s′ Ṽπ◦N (s ′)
(14)
where R(s) = ∑ a π ′(a|s) ∑ s′ p(s ′|s, a)R(s, a, s′), and P ′s,s′ = ∑ a π ′(a|s)p(s′|s, a) determined by the “merged” policy π′. Then for two different value function Ṽ 1π◦N and Ṽ 2 π◦N we have:
‖T πr Ṽ 1π◦N − T πr Ṽ 2π◦N‖∞ = max s |γ ∑ s′ P ′s,s′ Ṽ 1 π◦N (s ′)− γ ∑ s′ P ′s,s′ Ṽ 2 π◦N (s ′)|
≤ γmax s ∑ s′ P ′s,s′ |Ṽ 1π◦N (s′)− Ṽ 2π◦N (s′)|
≤ γmax s ∑ s′ P ′s,s′ max s′ |Ṽ 1π◦N (s′)− Ṽ 2π◦N (s′)|
= γmax s ∑ s′ P ′s,s′‖Ṽ 1π◦N − Ṽ 2π◦N‖∞
= γ‖Ṽ 1π◦N − Ṽ 2π◦N‖∞
(15)
Then according to the Banach fixed-point theorem, since γ ∈ (0, 1), Ṽπ◦N converges to a unique fixed-point Vπ′ . However, even though the obtained policy π′ satisfies that π′(a|s) = ∑ v(s)N(v(s)|s)π(a|v(s)) for each s, a, these equations can not necessarily guarantee a unique π especially when these equations behind this condition are underdetermined. In such scenario, multiple policies πr will exist as long as they satisfy the equations above.
Proof of (2) Firstly, based on Theorem 1 (Zhang et al., 2020) that shows an optimal policy does not always exist, we assume that an optimal policy exists in the adversarial noisy state setting for the convenience of following analysis. Based on this assumption, we need to derive the explicit value function under the adversary. Inspired by (Zhang et al., 2020), the proof insight is that the behavior of optimal adversary can be also viewed as finding another optimal policy, yielding a zero-sum two player game. Specifically, in the SN-MDP setting, the adversary selects an action â ∈ S satisfying â = v(s), attempting to maximize its state-action value function
Q̃πa(s, â). Then the adversary’s value function V̂πa(s) can be formulated as:
V̂πa(s) = max â Q̂πa(s, â)
= max â ∑ s′ p̂(s′|s, â)(R̂(s, â, s′) + γV̂πa(s ′))
= max v(s) ∑ s′ ∑ a π(a|v(s))p(s′|s, a)(−R(s, a, s′) + γV̂πa(s ′))
(16)
where p̂(s′|s, â) is the transition dynamics of the adversary, satisfying p̂(s′|s, â) = ∑ a π(a|v(s))p(s
′|s, a) from the perspective of the agent. R̂(s, â, s′) is the adversary’s reward function while taking action â, which is the opposite number of R(s, a, s′) given the action a. In addition, since both the adversary and agent can serve as a zero-sum two-player game, it indicates that Ṽπa(s) = −V̂πa(s) for the agent’s value function Ṽπa in the adversary setting. Then we rearrange the equation above as follows:
Ṽπa(s) = −V̂πa(s)
= − min N(·|s) ∑ s′ ∑ a π′(a|s)p(s′|s, a)(−R(s, a, s′) − γṼπa(s ′))
= min v(s) ∑ s′ ∑ a π′(a|s)p(s′|s, a)(R(s, a, s′) + γṼπa(s ′))
= min N(·|s) ∑ s′ ∑ a π′(a|s)p(s′|s, a)(rt+1 + γmin N Eπ◦N [ ∞∑ k=0 rt+k+2|st+1 = s′ ] )
= min N Ṽπ◦N (s)
(17)
Note that we optimize over N , which means we consider N(·|s) for each state s. Further, we derive the contraction of the Bellman operator T πa . We rewrite our Bellman Operator T πa as:
T πa Ṽπ◦N (s) = min N Ṽπ◦N (s)
= min N R(s) + γ ∑ s′ P ′s,s′ Ṽπ◦N (s ′)
(18)
We firstly assume T πa Ṽ 1πa(s) ≥ T π a Ṽ 2 πa(s), then we have:
T πa Ṽ 1π◦N (s)− T πa Ṽ 2π◦N (s)
≤ max N(·|s) {γ ∑ s′ P ′s,s′ Ṽ 1 π◦N (s ′)− γ ∑ s′ P ′s,s′ Ṽ 2 π◦N (s ′)}
≤ γ max N(·|s) ∑ s′ P ′s,s′ |Ṽ 1π◦N (s′)− Ṽ 2π◦N (s′)|
≤ γ max N(·|s) ∑ s′ P ′s,s′ max s |Ṽ 1π◦N (s′)− Ṽ 2π◦N (s′)|
= γ max N(·|s) ∑ s′ P ′s,s′‖Ṽ 1π◦N − Ṽ 2π◦N‖∞
≤ γ‖Ṽ 1π◦N − Ṽ 2π◦N‖∞
(19)
where the first inequality holds as minx1 f(x1) − minx2 g(x2) ≤ maxx(f(x) − g(x)) and we extends this inequality into the Wasserstein distance in the proof of convergence of distributional RL setting in Appendix B. The last inequality holds since only P ′s,s′ depends on N(·|s) while the infinity norm is a constant, which is independent with the current N(·|s). Similarly, the other scenario can be still proved. Thus, we have:
‖T πa Ṽ 1π◦N − T πa Ṽ 2π◦N‖∞ ≤ γ‖Ṽ 1π◦N − Ṽ 2π◦N‖∞ (20)
Thus, we proved that T πa is still a contraction and converge to minN Ṽπ◦N . We denote it as Ṽπ◦N∗ In addition, based on the insight of the “merged” policy π′a, we have π′a = ∑ v(s)N
∗(v(s)|s)π(a|v(s)) = π(a|v∗(s)) where the deterministic state v∗(s) is the adversarial noisy state from the state s.

heading: B PROOF OF THEOREM 1
text: Proof. Firstly, we will provide the properties of Wassertein distance dp in Lemma 1 that we leverage in our following convergence proof.
Lemma 1. (Properties of Wasserstein Metric) We consider the distribution distance between the random variable U and V . Denote dp as the Wasserstein distance between two distribution defined in Eq. 4. For any scalar a and random variable A independent of U and V , the following relationships hold:
dp(aU, aV ) ≤ |a|dp(U, V ) dp(A+ U,A+ V ) ≤ dp(U, V )
dp(AU,AV ) ≤ ‖A‖pdp(U, V ) (21)
Further, let A1, A2, ... be a set of random variables describing the a partition of ω, when the partition lemma holds:
dp(U, V ) ≤ ∑ i dp(AiU,AiV ). (22)
Then, the following contraction proof is in the maximal form of dp and we denote it as d̄p.
Proof of (1) This contraction proof is similar to the original one (Bellemare et al., 2017) in the distributional RL without state observation noises. The only difference lies in the new transition operator Pπr , but it dose not change the main proof process. For two different random variables Z1N and Z 2 N about returns, we have:
d̄p(T π rZ 1 N ,T π rZ 2 N )
= sup s,a
dp(T π rZ 1 N (s, a),T π rZ 2 N (s, a))
= sup s,a
dp(R(s, a, S ′) + γPπr Z1N (s, a), R(s, a, S′) + γPπr Z2N (s, a))
≤ γ sup s,a dp(Pπr Z1N (s, a),Pπr Z2N (s, a))
≤ γ sup s,a sup s′,a′ dp(Z 1 N (s ′, a′), Z2N (s ′, a′))
= γ sup s′,a′
dp(Z1(s ′, a′), Z2(s ′, a′))
= γ sup s,a
dp(Z 1 N (s, a), Z 2 N (s, a))
= γd̄p(Z 1 N , Z 2 N ).
(23)
Thus, we conclude that Tπr : Z → Z is a γ-contraction in d̄p.
Proof of (2) Firstly, we define the distributional Bellman optimality operator T in MDP as
TZ(s, a) : D = R ( s, a, S′ ) + γZ(S′, πZ(s ′)) (24)
where S′ ∼ P (·|s, a) and πZ(S′) = arg maxa′ E [Z(S′, a′)]. By contrast, in SN-MDP, Our greedy adversarial ruleN∗(·|s′) is based on the greedy policy rule in distributional Bellman optimality operator, which attempts to find adversarial N∗(·|s′) in order to minimize E [ZN (s′, a′)], where a′ ∼ π(·|V (s′)) and V (s′) ∼ N(·|s′). We assume N∗(·|s′) yields a deterministic state s∗, and thus the agent always takes action based on s∗, which we denote as A∗ ∼ π(·|s∗). Therefore, we can obtain the state-action function QπN∗(s, a) under the adversary as
QπN∗(s, a) = min N E [ZπN (s, a)] = E [ Zπ ∗ (s, a) ] (25) where π∗(·|s) = π(·|s∗) for ∀s that follows the adversarial policy A∗.
Next, to derive the contractive property of Tπa , we denote two state-action valued distributions as Z1N (s, a) and Z2N (s, a). Then we have:
d̄p(T π aZ 1 N ,T π aZ 2 N )
= sup s,a
dp(T π aZ 1 N (s, a),T π aZ 2 N (s, a))
= sup s,a
dp(R(s, a, S ′) + γPπaZ1N (s, a), R(s, a, S′) + γPπaZ2N (s, a))
≤ γ sup s,a ∑ s′ P (s′|s, a)dp(Z1N (s′, A∗), Z2N (s′, A∗))
= γ ∑ s′ P (s′|s, a)dp(Z1N (s′, A∗), Z2N (s′, A∗))
≤ γ sup s′ dp(Z 1 N (s ′, A∗), Z2N (s ′, A∗))
= γ sup s′ dp( ∑ a′∗ π(a′∗|s∗)Z1N (s′, a′∗), ∑ a′∗ π(a′∗|s∗)Z2N (s′, a′∗))
≤ γ sup s′ ∑ a′∗ π(a′∗|s∗)dp(Z1N (s′, a′∗), Z2N (s′, a′∗))
≤ γ sup s′,a′∗ dp(Z 1 N (s ′, a′∗), Z 2 N (s ′, a′∗))
= γ sup s,a
dp(Z 1 N (s, a), Z 2 N (s, a))
= d̄p(Z 1 N , Z 2 N )
(26)
Thus, we conclude that Tπa is still a γ-contraction in d̄p.

heading: C PROOF OF THEOREM 2
text: Proof. Firstly, we show the derivation details of the Histogram distribution loss starting from KL divergence between p and qθ . pi is the cumulative probability increment of target distribution TZθ within the i-th bin, and qθ corresponds to a (normalized) histogram, and has density values fθi (x(s))
wi per bin. Thus, we have:
L(Zθ,TZθ) = − ∫ b a p(y) log qθ(y)dy
= − k∑ i=1 ∫ li+wi li p(y) log fθi (x(s)) wi dy = − k∑ i=1 log fθi (x(s)) wi (FTZθ (li + wi)− FTZθ (li))︸ ︷︷ ︸
pi
. = − k∑ i=1 pi log f θ i (x(s))
(27)
where the last equality holds because the width parameter wi can be ignored for this minimization problem.
Next, we compute the gradient of the Histogram distributional loss.
∂
∂x(s) k∑ j=1 pj log f θ j (x(s))
= k∑ j=1 pj 1 fθj (x(s)) ∇fθj (x(s))
= k∑ j=1 pj 1 fθj (x(s)) fθj (x(s)) k∑ i=1 exp(x(s)>θi)∑k p=1 exp(x(s) >θp) (θj − θi)
= k∑ j=1 pj k∑ i=1 fθi (x(s))(θj − θi)
= k∑ j=1 pjθj − k∑ i=1 fθi (x(s))θi = k∑ i=1 (pi − fθi (x(s)))θi
(28)
Then, as we have ‖θi‖ ≤ l for ∀i, we bound the norm of its gradient
‖ ∂ ∂x(s) k∑ j=1 pj log f θ j (x(s))‖
≤ k∑ i=1 ‖(pi − fθi (x(s)))θi‖
= k∑ i=1 |pi − fθi (x(s))|‖θi‖
≤ kl
(29)
The last equality satisfies because |pi − fθi (x(s))| is less than 1 and even smaller. In summary, compared with the least squared loss in expectation-based RL, the histogram distributional loss in distributional RL can additionally enjoy kl-Lipschitz continuity with bounded gradient norm regarding the state features x(s). This upper bound of gradient norm can mitigate the impact of the noises on state observations on the loss function, therefore yielding training robustness for distributional RL.

heading: D TD CONVERGENCE UNDER NOISY STATE OBSERVATIONS
text: Let µ(s) be the stationary distribution under the policy π and p(s′|s) be the transition probability from s to s′ satisfying p(s′|s) = ∑ a π(a|s)p(s
′|s, a). We analyze conditions of TD convergence when exposing state observation noises. Firstly, we recall the classical TD update at step t:
wt+1 ← wt + αt(Rt+1 + γw>t xt+1 −w>t xt)xt (30) where αt is the step size at time t. Once the system has reached the steady state for any wt, then the expected next weight vector can be written as E[wt+1|wt] = wt + αt(b − Awt), where b = E(Rt+1xt) ∈ Rd and A .= E [ xtd > t ] ∈ Rd×d. The TD fixed point wTD to the system satisfies AwTD = b. From (Sutton & Barto, 2018), we know that the matrix A determines the convergence in the linear TD setting. In particular, wt converges with probability one to the TD fixed point if A is positive definite. However, if we add state noises η on either xt or xt+1 in Eq. 30, the convergence condition will be different. Theorem 4 (proof in Appendix F) provides conditions for TD convergence in three different noisy state observation settings. Theorem 4. (Conditions for TD Convergence under Noisy State Observations) Define P as the |S| × |S| matrix forming from p(s′|s), D as the |S| × |S| diagonal matrix with µ(s) on its diagonal, and X as the |S| × d matrix with x(s) as its rows, and E is the |S| × d perturbation matrix with each perturbation vector e(s) as its rows. The stepsizes αt ∈ (0, 1] satisfy ∑∞ t=0 αt = ∞ and ∑∞ t=0 α 2 t = 0. For noisy states, we consider the following three cases: (i) e(s) on current state features, i.e., xt ← xt +et, (ii) e(s′) on next state features, i.e., xt+1 ← xt+1 + et+1, (iii) the same e on both state features. We can attain that wt converges to TD fixed point if the following conditions are satisfied, respectively.
Case (i): both A and (X + E)>DPE are positive definite. Case (ii): both A and −X>DPE are positive definite. Case (iii): A is positive definite.
From the convergence conditions for the three cases in Theorem 4, it is clear that (iii) is the mildest. This is the same condition as that in the normal TD learning without noisy state observations. Note that the case (iii) can be viewed as the SN-MDP setting, whose convergence has been already rigorously analyzed in Section 3. In Section 5, our experiments demonstrate that both expectation-based and distribution RL are more likely to converge in case (iii) compared with case (i) and (ii).
In cases (i) and (ii), the positive definiteness of X>DPE+E>DPE and−X>DPE is crucial. We partition (X + E)>DPE into X>DPE + E>DPE, where the first term has the opposite positive definiteness to −X>DPE, and the second term is positive definite (Sutton & Barto, 2018). Based on these observations, we discuss the subtle convergence relationship in cases (i) and (ii):
(1) If −X>DPE is positive definite, which indicates that TD is convergent in case (ii), TD can still converge in case (i) unless the positive definiteness of E>DPE dominates in X>DPE + E>DPE.
(2) If−X>DPE is negative definite, TD is likely to diverge in case (ii). By contrast, TD will converge in case (i).
In summary, there exists a subtle trade-off of TD convergence in case (i) and (ii) if we approximately ignore the term E>DPE in case (i). The key of it lies in the positive definiteness of the matrix X>DPE, which heavily depends on the task. In Section 5, we empirically verify that the convergence situations for current and next state observations are normally different. Which situation is superior is heavily dependent on the task.

heading: E SENSITIVITY ANALYSIS BY INFLUENCE FUNCTION
text: Next, we conduct an outlier analysis by the influence function, a key facet in the robust statistics (Huber, 2004). The influence function characterizes the effect that the noise in particular observation has on an estimator, and can be utilized to investigate the impact of one particular state observation noise on the training of reinforcement learning algorithms. Specifically, suppose that F is the contaminated distribution function that combines the clear data distribution F and an outlier x. The distribution F can be defined as
F = (1− )F + δx, (31)
where δx is a probability measure assigning probability 1 to x. Let θ̂ be a regression estimator. The influence function of θ at F , ψ : X → Γ is defined as
ψθ̂,F (x) = lim →0
θ̂ (F (x))− θ̂(F )
. (32)
Mathematically, the influence function is the Gateaux derivative of θ at F in the direction δx. Owing to the fact that traditional value-based RL algorithms, e.g., DQN (Mnih et al., 2015), can be viewed as a regression problem (Fan et al., 2020), the linear TD approximator also has a strong connection with regression problems. Based on this correlation, in the following Theorem 5, we quantitatively evaluate the influence function of TD learning in the case of linear function approximation. Theorem 5. (Influence Function Analysis in TD Learning with linear function approximation) Denote dt = xt−γxt+1 ∈ Rd, and A . = E [ xtd > t ] ∈ Rd×d. Let Fπ be the data distribution generated from the environment dynamics given a policy π. Consider an outlier pair (xt,xt+1) with the reward Rt+1, the influence function ψ of this pair on the estimator w is derived as
ψw,Fπ (xt,xt+1) = E(A >A)−1dtx > t xt(Rt+1 − d>t w). (33)
Please refer to Appendix G for the proof. Theorem 5 shows the quantitative impact of an outlier pair (xt,xt+1) on the learned parameter w. Moreover, a corollary can be immediately obtained to make a precise comparison of the impacts of perturbations on current and next state features. Corollary 1. Given the same perturbation η on either current or next state features, i.e., xt, and xt+1, at the step t, if we approximate ηη>xt and ηη>w as 0 as η is small enough, the following relationship between the resulting variations of influence function, ∆xtψ and ∆xt+1ψ, holds:
γ∆xtψ + ∆xt+1ψ = 2γdtηx > t (Rt+1 − d>t w). (34)
We provide the proof of Corollary 1 in Appendix G. Under this equation, the sensitivity of noises on xt and xt+1, measured by ∆xtψ and ∆xt+1ψ, present a trade-off relationship as their weighted sum is definite. However, there is not an ordered relationship between ∆xtψ and ∆xt+1ψ. In summary, we conclude that the sensitivity of current and next state features against perturbations is normally divergent, and the degree of sensitivity is heavily determined by the task. These conclusions are similar to those we derived in the TD convergence part.

heading: F PROOF OF THEOREM 4
text: Proof. To prove the convergence of TD under the noisy states, we use the results from (Borkar & Meyn, 2000) that require the condition about stepsizes αt holds: ∑∞ t=0 αt = ∞ and ∑∞ t=0 α 2 t = 0. Based on (Sutton & Barto, 2018), the positive definiteness of A will determine the TD convergence. For linear TD(0), in the continuing case with γ < 1, A can be re-written as:
A = ∑ s µ(s) ∑ a π(a|s) ∑ r,s′ p(r, s′|s, a)xt (xt − γxt+1)>
= ∑ s µ(s) ∑ s′ p(s′|s)xt (xt − γxt+1)>
= ∑ s µ(s)xt(xt − γ ∑ s′ p(s′|s)xt+1)> = X>DX−X>DγPX
= X>D(I− γP)X
(35)
Then we use At to present the convergence matrix in the case (i) where the perturbation vector et is added onto the current state features, i.e., xt ← xt + et, while we use At+1 and At,t+1to present the counterparts in the case (ii) and (iii), respectively. Based on Eq. 35, in the case (iii), we have:
At,t+1 = (X + E) >D(X + E)− (X + E)>DγP(X + E)
= (X + E)>D(I− γP)(X + E) (36)
From (Sutton & Barto, 2018), we know that the inner matrix D(I − γP) is the key to determine the positive definiteness of A. If we assume that A is positive definite, which also indicates that D(I − γP) is positive definite equivalently. As such, At,t+1 is positive definite automatically, and thus the liner TD would converge to the TD fixed point. Next, in the case (i) we have:
At = (X + E) >D(X + E)− (X + E)>DγPX
= A + X>DE + E>DX + E>DE−E>DγPX
= (X + E)>D(I− γP)(X + E) + (X + E)>DγPE
= At,t+1 + γ(X + E) >DPE
= At,t+1 + γ(X >DγPE + E>DγPE)
(37)
Similarly, in the case (ii), we can also attain:
At+1 = X >DX−X>DγP(X + E)
= A− γX>DPE (38)
We know that the positive definiteness of A and At,t+1 is only determined by the positive definiteness of the inner matrix D(I − γP). If we assume the positive definiteness of A, i.e., the positive definiteness of At,t+1 and D(I−γP), as γ > 0, what we only need to focus on are the positive definiteness of X>DPE+E>DPE and −X>DPE. If they are positive definite, TD learning will converge under their cases, respectively.

heading: G PROOF OF THEOREM 5 AND COROLLARY 1
text: Proof. We combine the proof of Theorem 5 and Corollary 1 together. The TD fixed point wTD to the system satisfies AwTD = b. Thus, the TD convergence point, i.e., TD fixed point, can be attained by solving the following regression problem:
min w ‖b−Aw‖2 (39)
To derive the influence function, consider the contaminated distribution which puts a little more weight on the outlier pair (xt,xt+1):
ŵ = arg min w
(1− )E[(b−Aw)>(b−Aw)]+
(yb − x>Aw)>(yb − x>Aw), (40)
where yb = Rt+1xt and xb = dtx>t . We take the first condition:
(1− )E(2A>Aw − 2A>b)− 2 xA(yb − x>Aw) = 0. (41)
Then we arrange this equality and obtain:
(1− )E(A>A + xAx>A)w = (1− )E(A>b) + xAyb. (42)
Then we take the gradient on and let = 0, then we have:
(−E(A>A) + xAx>A)w + E(A>A)ψw,Fπ = −E(A >b)
+xAyb. (43)
We know that under the least square estimation, the closed-form solution of w is E(A>A)−1E(A>b). Thus, after the simplicity, we finally attain:
ψw,Fπ (xt,xt+1) = E(A >A)−1xA(yb − x>Aw)
= E(A>A)−1dtx>t xt(Rt+1 − d>t w). (44)
Next, we prove the Corollary. We only need to focus on the item dtx>t xt(Rt+1 − d>t w), which we denote as ψ0. Then we use ∆xtψ and ∆xt+1ψ to represent the change of ψ after adding perturbations η on xt and xt+1, respectively. In particular, since we approximate ηη>xt and ηη>w as 0, then we have that the change of influence function for the perturbation η on the current state feature xt:
∆xtψ ≈ (dt + η)(x > t xt + 2η >xt)(Rt+1 − d>t w − η>w)− ψ0 ≈ −dtx>t xtη>w + 2dtη>xt(Rt+1 − d>t w) + η · x>t xt(Rt+1 − d>t w)
= 2dtη >xt(Rt+1 − d>t w)−
1 γ (γdtx > t xtη
>w − γηx>t xt(Rt+1 − d>t w)). (45)
Then the influence function for the perturbation η on the next state feature xt+1 is:
∆xt+1ψ = (dt − γη)x > t xt(Rt+1 − d>t w + γη>w)− ψ0
≈ γdtx>t xtη>w − γηx>t xt(Rt+1 − d>t w). (46)
Finally, it is easy to observe that the following relationship holds:
γ∆xtψ = 2γdtηx > t (Rt+1 − d>t w)−∆xt+1ψ. (47)

heading: H EXPERIMENTAL SETUP
text: After a linear search, in the QR-DQN, We set κ = 1 for the Huber quantile loss across all tasks due to its smoothness.
Cart Pole After a linear search, in the QR-DQN, we set the number of quantiles N to be 20, and evaluate both DQN and QR-DQN on 200,000 training iterations.
Mountain Car After a linear search, in the QR-DQN, we set the number of quantiles N to be 2, and evaluate both DQN and QR-DQN on 100,000 training iterations.
Breakout and Qbert After a linear search, in the QR-DQN, we set the number of quantiles N to be 200, and evaluate both DQN and QR-DQN on 12,000,000 training iterations.

heading: I SN-MDP SETTING WITH RANDOM NOISES
text: From Figure 5, we can easily observe that all DQN and QRDQN algorithms under various strength of random state noises converge, although they eventually obtained different average returns. This empirical observation is consistent with our theoretical analysis in Section 3 where both classical and distributional Bellman operators are contractive and thus convergent. In addition, Figure 5 also manifests that the eventual performance that algorithms attained has a decreasing tendency as the perturbation strength, i.e., standard deviation, increases especially for DQN. Remarkably, the final performance of QRDQN is more robust than DQN against different perturbation strength, especially in Mount Car and Breakout games, although both DQN and QRDQN are convergent in this SN-MDP-like setting.

heading: J EXTENSION ANALYSIS OF PERTURBATIONS ON CURRENT, NEXT AND BOTH STATE OBSERVATION
text: We provide the results of robust performance with different perturbation states in Breakout under random and adversarial noisy state observations in Figure 6 and 7, respectively.
In the random state observation setting as shown in Figure 6, it turns out that perturbations on current state observations is more robust than next state by comparing the first and second subfigures given the same perturbation strength. This empirical finding demonstrates the conclusion in Appendix D and E that the sensitivity of current and next states are normally divergent. The result where noises are added on both states seems to be most robust, consistent with the mildest TD convergence condition as shown in Theorem 4.
In the adversarial state observation setting as shown in Figure 7, it also turns out that perturbations on current state observations is more robust than next state by comparing the first and second subfigures given the same perturbation strength, and algorithms converge easiest. These empirical results also demonstrates the conclusion we made in Appendix D and E.

Review summaries:
This work presented State-Noisy Markov Decision Process (SN-MDP), where there is a noise generating mechanism (either from the environment noise or from the adversary), and the theoretical properties (such as convergence and contraction) for corresponding (expected) Bellman operator and distributional Bellman operator were proved. The theoretical analysis was done for both tabular and linear funcion approximation settings. Especially in function approximation setting, authors characterized the robustness blessing of distributional RL based on histogram distributional loss and analyzed how the noise factor affects TD learning by using influence function that utilizes the perburbation method. Empirical analysis was done for DQN and QRDQN by varying noise standard deviations and the position of noise (state/successor state or both), which aims to support the authors' intuition coming from their theorems. 

This paper studies the robustness of distributional reinforcement learning, in particular the robustness on state observations, which have been demonstrated in a few papers on adversarial attacks to deep reinforcement learning. Compared to existing works on robust reinforcement learning on state observations, the main difference in this work is that it considers the distributional RL setting and also considers noise during training time. Theoretically, the authors find that distributional RL can be more robust under this setting, via the lens of Lipschitz continuity of the loss function and the influence function. The findings are also verified empirically on 4 benchmarks.