# Towards Optimal Adversarial Robust Q-learning with Bellman Infinity-error

Haoran Li  Zicheng Zhang  Wang Luo  Congying Han  Yudong Hu  Tiande Guo
Shichen Liao

###### Abstract

Establishing robust policies is essential to counter attacks or disturbances
affecting deep reinforcement learning (DRL) agents. Recent studies explore
state-adversarial robustness and suggest the potential lack of an optimal
robust policy (ORP), posing challenges in setting strict robustness
constraints. This work further investigates ORP: At first, we introduce a
consistency assumption of policy (CAP) stating that optimal actions in the
Markov decision process remain consistent with minor perturbations, supported
by empirical and theoretical evidence. Building upon CAP, we crucially prove
the existence of a deterministic and stationary ORP that aligns with the
Bellman optimal policy. Furthermore, we illustrate the necessity of
$L^{\infty}$-norm when minimizing Bellman error to attain ORP. This finding
clarifies the vulnerability of prior DRL algorithms that target the Bellman
optimal policy with $L^{1}$-norm and motivates us to train a Consistent
Adversarial Robust Deep Q-Network (CAR-DQN) by minimizing a surrogate of
Bellman Infinity-error. The top-tier performance of CAR-DQN across various
benchmarks validates its practical effectiveness and reinforces the soundness
of our theoretical analysis.

Machine Learning, ICML

##  1 Introduction

Deep reinforcement learning (DRL) has shown remarkable success in solving
intricate problems (Mnih et al., 2015; Lillicrap et al., 2015; Silver et al.,
2016) and holds promise across diverse practical domains (Ibarz et al., 2021;
Kiran et al., 2021; Yu et al., 2021; Zheng et al., 2018). Nevertheless, subtle
perturbations in state observations can severely degrade well-trained DRL
agents (Huang et al., 2017; Behzadan & Munir, 2017a; Lin et al., 2017; Ilahi
et al., 2021), which limits their trustworthy real-world deployment and
emphasizes the crucial need for developing robust DRL algorithms against
adversarial attacks.

Pioneering work by Zhang et al. (2020) introduced the state-adversarial
paradigm in DRL by formulating a modified Markov decision process (MDP),
termed SA-MDP. Here, the underlying true state remains invariant while the
observed state is subjected to disturbances. They also highlighted the
uncertain existence of an optimal robust policy (ORP) within SA-MDP,
indicating a potential conflict between robustness and optimal policy.
Consequently, existing methods built upon SA-MDP often seek a trade-off
between robust and optimal policies through various regularizations (Oikarinen
et al., 2021; Liang et al., 2022) or adversarial training (Zhang et al., 2021;
Sun et al., 2021). While enhancing robustness, these methods lack theoretical
guarantees and completely neglect the study of ORP.

In this paper, we primarily focus on investigating ORP within SA-MDP. We
suppose that only a few exceptional states lack an ORP, thus it is key for
theoretical clarity to eliminate these states. Therefore, our work starts with
a consistency assumption of policy (CAP), where optimal actions of all states
within the MDP exhibit consistency despite adversarial disturbance. This
implies that, from a decision-making perspective, adversaries cannot alter the
essence of state observations, which we call the intrinsic state. Despite
seeming implausible, we support the rationality of CAP through theoretical
analysis and empirical experiments against strong adversarial attacks like
FGSM (Goodfellow et al., 2014) and PGD (Madry et al., 2017), showcasing that
the state set violating CAP is nearly empty.

Building upon CAP, we demonstrate that there always exists a stationary and
deterministic adversarial ORP coinciding with the Bellman optimal policy,
derived from the Bellman optimality equations. Remarkably, this objective has
been widely employed in previous DRL algorithms (Silver et al., 2014; Schulman
et al., 2015; Wang et al., 2016; Mnih et al., 2016; Schulman et al., 2017) to
maximize the natural returns, lacking robust capabilities. Hence, our findings
incredibly unveil that the Bellman optimal policy doubles as the ORP, and
improving the robustness of DRL agents need not compromise their performance
in natural environments. This insight holds significant value for establishing
DRL agents with Bellman optimality equations in real-world scenarios where
strong adversarial attacks are relatively rare.

In pursuit of ORP, we delve into understanding why conventional DRL
algorithms, which target the Bellman optimal policy, fail to guarantee
adversarial robustness. By analyzing the theoretical properties of
$\|Q_{\theta}-Q^{*}\|_{p}$ and Bellman error
$\|\mathcal{T}_{B}Q_{\theta}-Q_{\theta}\|_{p}$ across diverse Banach spaces,
we identify the substantial impact of the parameter $p$ on adversarial
robustness. Specifically, achieving ORP corresponds to minimizing the Bellman
Infinity-error, i.e., $p=\infty$, whereas conventional algorithms are
typically linked to $p=1$. To address the computational challenges arising
from $L^{\infty}$-norm, we propose the Consistent Adversarial Robust Deep
Q-Network (CAR-DQN), utilizing a surrogate objective of Bellman Infinity-error
for robust policy learning.

To summarize, our paper makes the following contributions:

  * (1).

We propose the rational CAP for SA-MDP, confirm the existence of deterministic
and stationary ORP, and demonstrate its strict alignment with the Bellman
optimal policy, which is a significant advancement over prior research.

  * (2).

We underscore the necessity of employing the $L^{\infty}$-norm to minimize
Bellman error for theoretical ORP attainment. This stands in contrast to
conventional DRL algorithms, which lack robustness due to the use of an
$L^{1}$-norm.

  * (3).

We devise CAR-DQN solely utilizing a surrogate objective based on the
$L^{\infty}$-norm to learn both natural return and robustness. We conduct
comparative evaluations of CAR-DQN against state-of-the-art approaches across
various benchmarks, validating its practical effectiveness and reinforcing our
theoretical soundness.

##  2 Related Work

Adversarial attacks on DRL agents. The seminal work of Huang et al. (2017)
first exposed the vulnerability of DRL agents to FGSM attacks (Goodfellow et
al., 2014) on state observations in Atari games. Subsequently, Lin et al.
(2017); Kos & Song (2017) introduced limited-steps attacks to deceive DRL
policies. Pattanaik et al. (2017) employed a critic action-value function and
gradient descent to degrade DRL performance. Additionally, Behzadan & Munir
(2017a) proposed black-box attacks on DQN and verified the transferability of
adversarial examples, while Inkawhich et al. (2019) showed that even a
constrained adversary with access only to action and reward signals could
launch highly effective and damaging attacks. Kiourti et al. (2020); Wang et
al. (2021); Bharti et al. (2022); Guo et al. (2023) investigated backdoor
attacks in reinforcement learning. Besides, Gleave et al. (2019) have studied
the adversarial policy within multi-agent scenarios, and Zhang et al. (2021);
Sun et al. (2021) developed learned adversaries by training attackers as RL
agents. Lu et al. (2023) suggested an adversarial cheap talk setting and
trained an adversary through meta-learning. Korkmaz (2023) analyzed
adversarial directions in the Arcade Learning Environment, and found that even
state-of-the-art robust agents (Zhang et al., 2020; Oikarinen et al., 2021)
are susceptible to policy-independent sensitivity directions.

Robust discrete action for DRL agents. Earlier works like Kos & Song (2017);
Behzadan & Munir (2017b) incorporated adversarial states into the replay
buffer during training in Atari environments, leading to limited robustness.
Fischer et al. (2019) proposed to separate DQN architecture into a $Q$ network
and a policy network, and robustly trained the policy network with generated
adversarial states and provably robust bounds. Recently, Zhang et al. (2020)
characterized state-adversarial RL as SA-MDP, and revealed the potential non-
existence of ORP. They addressed the challenge by considering a balance
between robustness and natural returns through a KL-based regularization.
Oikarinen et al. (2021) controlled robustness certification bounds to minimize
the overlap between perturbed $Q$ values of the current action and others.
Liang et al. (2022) estimated the worst-case value estimation and combined it
with the classic Temporal Difference (TD)-target, resulting in higher training
efficiency compared to prior methods. The latest work by Nie et al. (2023)
built the DRL architecture upon SortNet (Zhang et al., 2022), enabling global
Lipschitz continuity, thus reducing the need for training extra attackers or
finding adversaries. He et al. (2023) proposed robust multi-agent Q-learning
to solve the robust equilibrium in discrete state and action two-player games.
Bukharin et al. (2023) considered a sub-optimal Lipschitz policy in smooth
environments and extended the robustness regularization (Shen et al., 2020;
Zhang et al., 2020) to multi-agent settings. Prior methods heuristically
constrain local smoothness or invariance to achieve commendable robustness,
while compromising natural performance. In contrast, our approach seeks
optimal robust policies with strict theoretical guarantees, simultaneously
improving natural and robust performance.

##  3 Preliminaries

Markov decision process (MDP) is defined by a tuple
$\left(\mathcal{S},\mathcal{A},r,\mathbb{P},\gamma,\mu_{0}\right)$, where
$\mathcal{S}$ represents the state space, $\mathcal{A}$ denotes the action
space, $r:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ is the reward
function,
$\mathbb{P}:\mathcal{S}\times\mathcal{A}\rightarrow\Delta\left(\mathcal{S}\right)$
stands for the transition dynamics where $\Delta\left(\mathcal{S}\right)$ is
the probability space over $\mathcal{S}$, $\gamma\in[0,1)$ represents the
discount factor, and $\mu_{0}\in\Delta\left(\mathcal{S}\right)$ is the initial
state distribution. In this paper, we consider the setting where the
continuous state space $\mathcal{S}\subset\mathbb{R}^{d}$ is a compact set and
the action space $\mathcal{A}$ is a finite set. Given an MDP, we define the
state value function
$V^{\pi}(s)=\mathbb{E}_{\pi,\mathbb{P}}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})|s_{0}=s\right]$
and the $Q$ (or action-value) function
$Q^{\pi}(s,a)=\mathbb{E}_{\pi,\mathbb{P}}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})|s_{0}=s,a_{0}=a\right]$
for every policy $\pi$. MDPs exhibit a notable property: there exists a
stationary, deterministic policy that maximizes both $V^{\pi}(s)$ and
$Q^{\pi}(s,a)$ for all $s\in\mathcal{S}$ and $a\in\mathcal{A}$. Additionally,
the optimal $Q$ function $Q^{*}(s,a)=\sup_{\pi\in\Pi}Q^{\pi}(s,a)$, satisfies
the Bellman optimality equation

$Q^{*}(s,a)=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot\mid
s,a)}\left[\max_{a^{\prime}\in\mathcal{A}}Q^{*}\left(s^{\prime},a^{\prime}\right)\right].$

State-Adversarial MDP (SA-MDP) allows an adversary $\nu$ to perturb the
observed state $s$ into $s_{\nu}$. Let $\pi\circ\nu$ denote the policy under
perturbations, the adversarial value and $Q$ functions are
$V^{\pi\circ\nu}(s)=\mathbb{E}_{\pi\circ\nu,\mathbb{P}}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})|s_{0}=s\right]$
and
$Q^{\pi\circ\nu}(s,a)=\mathbb{E}_{\pi\circ\nu,\mathbb{P}}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})|s_{0}=s,a_{0}=a\right]$,
respectively. There always exists a strongest adversary
$\nu^{*}(\pi)=\mathop{\arg\min}_{\nu}V^{\pi\circ\nu}$ for any policy $\pi$. An
optimal robust policy (ORP) $\pi^{*}$ should satisfy
$V^{\pi^{*}\circ\nu^{*}(\pi^{*})}(s)=\max_{\pi}V^{\pi\circ\nu^{*}(\pi)}(s)$
for all $s\in\mathcal{S}$.

##  4 Optimal Adversarial Robustness

In this section, we delve into the exploration of ORP within SA-MDP. While
Zhang et al. (2020) noted that ORP does not necessarily exist for a general
adversary, we discover that only a few states lack ORP, and the set of these
abnormal states has a measure close to zero in complicated tasks. For
theoretical clarity, we first propose a consistency assumption of policy (CAP)
to eliminate these states. Then, we devise a novel consistent adversarial
robust operator $\mathcal{T}_{car}$ for computing the adversarial $Q$
function, and under CAP, we identify its fixed point as exactly $Q^{*}$,
thereby proving the existence of a deterministic and stationary ORP.

###  4.1 Consistency Assumption of Policy

Given a general adversary, we observe the true state $s$ and the perturbed
observation $s_{\nu}$ have the same optimal action in practice. Some examples
are shown in Figure 1 and Appendix E. This enlightens Bellman optimal policy
is robust, motivating us to consider how the adversary affects the optimal
action in theory. We first assume that all states have a consistent intrinsic
state neighborhood.

######  Assumption 4.1 (Consistency Assumption of Policy (CAP)).

Given an SA-MDP, the adversary perturbation set is a $\epsilon$-neighbourhood
$B_{\epsilon}(s)=\left\\{\|s^{\prime}-s\|\leq\epsilon\right\\}$. We define the
intrinsic state $\epsilon$-neighbourhood for any state $s$ as

$\displaystyle B^{*}_{\epsilon}(s):=$
$\displaystyle\left\\{s^{\prime}\in\mathcal{S}|\|s^{\prime}-s\|\leq\epsilon,\right.$
$\displaystyle\mathop{\arg\max}_{a}Q^{*}(s^{\prime},a)=\mathop{\arg\max}_{a}Q^{*}(s,a)\\}.$

For all $s\in\mathcal{S}$, its adversary $\epsilon$-perturbation set is the
same as the intrinsic state $\epsilon$-neighbourhood, i.e.,
$B_{\epsilon}(s)=B^{*}_{\epsilon}(s)$.

We provide a theoretical analysis to show CAP is reasonable.

######  Theorem 4.2 (Rationality of CAP).

Given $\epsilon>0$, let
$\mathcal{S}_{nu}=\left\\{s\in\mathcal{S}|\mathop{\arg\max}_{a}Q^{*}(s,a)\text{
is not a singleton}\right\\}$, and
$\mathcal{S}_{nin}=\left\\{s\in\mathcal{S}|B_{\epsilon}(s)\neq
B^{*}_{\epsilon}(s)\right\\}$. If $Q^{*}(\cdot,a)$ is continuous almost
everywhere in $\mathcal{S}$ for all $a\in\mathcal{A}$, we have that
$\mathcal{S}_{nin}\subseteq\mathcal{S}_{nu}\cup\mathcal{S}_{0}+B_{\epsilon}$,
where $\mathcal{S}_{0}$ is a zero measure set.

Actually, $\mathcal{S}_{nu}$ is also close to an empty set in most practical
complex environments, and $\mathcal{S}_{0}$ is a set of special and rare
discontinuous points of $Q^{*}$ (as shown in our proof). Theorem 4.2
essentially shows, for complicated tasks, $\mathcal{S}_{nin}$ is a quite small
set and the magnitude of $\mu(\mathcal{S}_{nin})$ is around $O(\epsilon^{d})$,
where $\mu(A)$ represents the measure of set $A$ and $d$ is the dimension of
state space. The Corollary in Appendix A.1 illustrates better conclusions with
stronger conditions.

Figure 1: An example of state adversary in DQN. While the adversary disrupts
the policy performed by DQN, it does not impact the optimal action dictated by
the Bellman optimal policy. This observation prompts the study of two key
issues: whether the Bellman optimal policy serves as the ORP, and why vanilla
DQN trained with Bellman error fails to ensure robustness.

###  4.2 Consistent Optimal Robust Policy

To establish the relation between the optimal $Q$ function before and after
the perturbation, we propose a consistent adversarial robust (CAR) operator.

######  Definition 4.3 (CAR Operator $\mathcal{T}_{car}$).

Given an SA-MDP, the CAR operator is
$\mathcal{T}_{car}:L^{p}\left(\mathcal{S}\times\mathcal{A}\right)\rightarrow
L^{p}\left(\mathcal{S}\times\mathcal{A}\right)$,

$\displaystyle\left(\mathcal{T}_{car}Q\right)(s,a)=r(s,a)$
$\displaystyle+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[\min_{s^{\prime}_{\nu}\in
B_{\epsilon}(s^{\prime})}Q\left(s^{\prime},\mathop{\arg\max}_{a_{s^{\prime}_{\nu}}}Q\left(s^{\prime}_{\nu},a_{s^{\prime}_{\nu}}\right)\right)\right].$

Although $\mathcal{T}_{car}$ is not contractive (see Appendix A.2.2), Theorem
4.4 shows that under CAP, $\mathcal{T}_{car}$ has a fixed point, which
corresponds to the optimal adversarial $Q$ function.

######  Theorem 4.4 (Relation between $Q^{*}$ and
$Q^{\pi^{*}\circ\nu^{*}(\pi^{*})}$).

  * (1).

If the optimal adversarial $Q$ function $Q^{\pi^{*}\circ\nu^{*}(\pi^{*})}$
exists for all $s\in\mathcal{S}$ and $a\in\mathcal{A}$, then it is the fixed
point of $\mathcal{T}_{car}$.

  * (2).

If the CAP holds, then $Q^{*}$ is the fixed point of $\mathcal{T}_{car}$ and
it is also the optimal adversarial $Q$ function, i.e.,
$Q^{*}(s,a)=Q^{\pi^{*}\circ\nu^{*}(\pi^{*})}(s,a)$, for all $s\in\mathcal{S}$
and $a\in\mathcal{A}$.

We have demonstrated the convergence of $\mathcal{T}_{car}$ in a smooth
environment (see Appendix A.2.3), stating the fixed point iterations of
$\mathcal{T}_{car}$ at least converge to a sub-optimal solution close to
$Q^{*}$. On this basis, it can be derived from Theorem 4.4 that the greedy
policy $\pi^{*}(s):=\mathop{\arg\max}_{a}Q^{*}(s,a)$, for all
$s\in\mathcal{S}$, is exactly the ORP.

######  Corollary 4.5 (Existence of ORP).

If the CAP holds, there exists a deterministic and stationary policy $\pi^{*}$
which satisfies $V^{\pi^{*}\circ\nu^{*}(\pi^{*})}(s)\geq
V^{\pi\circ\nu^{*}(\pi)}(s)$ and $Q^{\pi^{*}\circ\nu^{*}(\pi^{*})}(s,a)\geq
Q^{\pi\circ\nu^{*}(\pi)}(s,a)$, for all $\pi\in\Pi$, $s\in\mathcal{S}$ and
$a\in\mathcal{A}$.

The above theorems indicate that under the CAP, the ORP against the strongest
adversary is actually the Bellman optimal policy derived from the Bellman
optimality equations. This also suggests that the objectives in natural and
adversarial environments are aligned, which is supported by our experiment
results in Sec. 7.2.

##  5 Policy Robustness under Bellman $p$-error

As the Bellman optimal policy is ORP, we further consider the reasons for the
vulnerability of DRL agents: Although former methods, such as Q-learning,
essentially take the Bellman optimal policy as a goal, why do they exhibit
rather poor robustness? We approach this issue by examining the stability of
policy across diverse Banach spaces.

Let $Q_{\theta}$ denote a parameterized $Q$ function. The value-based RL
training theoretically requires minimizing
$\left\|Q_{\theta}-Q^{*}\right\|_{\mathcal{B}}$, where $\mathcal{B}$ is a
Banach space. In practice, it is hard to make the distance between
$Q_{\theta}$ and $Q^{*}$ vanish due to some limitations, such as the
characterization capabilities of neural networks and the convergence of
optimization algorithms. Therefore, we analyze the properties of $Q_{\theta}$
when the $\left\|Q_{\theta}-Q^{*}\right\|_{\mathcal{B}}$ is a small positive
value on different spaces $\mathcal{B}$.

###  5.1 Necessity of $L^{\infty}$-norm for Adversarial Robustness

We study the adversarial robustness of the greedy policy derived from $Q$ when
$0<\left\|Q-Q^{*}\right\|_{p}=\delta\ll 1$ for different $L^{p}$ spaces. Given
a function $Q$ and perturbation budget $\epsilon$, let
$\mathcal{S}^{Q}_{sub}=\\{s|Q^{*}(s,\mathop{\arg\max}_{a}Q(s,a))<\max_{a}Q^{*}(s,a)\\}$
denote the set of states where the greedy policy according to $Q$ is
suboptimal, and $\mathcal{S}^{Q}_{adv}$ denote the set of states in whose
$\epsilon$-neighbourhood there exists the adversarial state, i.e.,

$\displaystyle\mathcal{S}^{Q}_{adv}=$ $\displaystyle\\{s|\exists s_{\nu}\in
B_{\epsilon}(s),$ $\displaystyle\text{s.t.
}Q^{*}(s,\mathop{\arg\max}_{a}Q(s_{\nu},a))<\max_{a}Q^{*}(s,a)\\}.$

######  Theorem 5.1 (Necessity of $L^{\infty}$-norm).

There exists an MDP instance such that the following statements hold.

  * (1).

For any $1\leq p<\infty$ and $\delta>0$, there exists a function $Q\in
L^{p}\left(\mathcal{S}\times\mathcal{A}\right)$ satisfying
$\|Q-Q^{*}\|_{p}\leq\delta$ such that
$\mu\left(\mathcal{S}^{Q}_{sub}\right)=O(\delta)$ yet
$\mu\left(\mathcal{S}^{Q}_{adv}\right)=\mu\left(\mathcal{S}\right)$.

  * (2).

There exists a $\bar{\delta}>0$ such that for any $0<\delta\leq\bar{\delta}$,
and any function $Q\in L^{\infty}\left(\mathcal{S}\times\mathcal{A}\right)$
satisfying $\|Q-Q^{*}\|_{\infty}\leq\delta$, we have that
$\mu\left(\mathcal{S}^{Q}_{sub}\right)=O(\delta)$ and
$\mu\left(\mathcal{S}^{Q}_{adv}\right)=2\epsilon+O\left(\delta\right)$.

The first statement indicates that when $\|Q-Q^{*}\|_{p}$ is a small value for
$1\leq p<\infty$, there always exist adversarial examples near almost all
states, resulting in quite poor robustness, while the policy might exhibit
excellent performance in a natural environment without adversarial attacks.
This observation sheds light on the vulnerability of DRL agents, aligning with
findings across various studies (Huang et al., 2017; Ilahi et al., 2021).
Importantly, the second statement points out that through minimizing
$\|Q-Q^{*}\|$ in the $L^{\infty}$-norm space, we can avoid the vulnerability
and attain a policy with both natural and robust capabilities. This inspires
to optimize $\|Q_{\theta}-Q^{*}\|_{\infty}$ in DRL algorithms. Intuitive
examples of Theorem 5.1 are shown in Figure 2.

Figure 2:  Examples of adversarial robustness for $Q$ satisfying
$\|Q-Q^{*}\|_{p}\leq\delta$. Given a perturbation radius $\epsilon$, the red
line represents the set $\mathcal{S}_{adv}^{Q}$, in which states have
adversarial states. The left panel depicts the case of $p=\infty$, where all
$Q$ is distributed in the shadow area with the measure of
$\mathcal{S}_{adv}^{Q}$ being a small value $2\epsilon+O\left(\delta\right)$.
The right panel shows that for $1\leq p<\infty$, there always exists $Q$ such
that $\mathcal{S}_{adv}^{Q}=\mathcal{S}$, indicating poor robustness.

###  5.2 Stability of Bellman Optimality Equations

Unfortunately, it is infeasible to measure $\|Q_{\theta}-Q^{*}\|$ within a
practical DRL procedure due to the unknown nature of $Q^{*}$. Most methods
train $Q_{\theta}$ via optimizing the Bellman error
$\|\mathcal{T}_{B}Q_{\theta}-Q_{\theta}\|_{\mathcal{B}^{\prime}}$, where
$\mathcal{T}_{B}$ is the Bellman optimal operator

$\left(\mathcal{T}_{B}Q\right)(s,a)=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot\mid
s,a)}\left[\max_{a^{\prime}\in\mathcal{A}}Q\left(s^{\prime},a^{\prime}\right)\right].$

Similar to Theorem 5.1, we need to figure out which Banach space
$\mathcal{B}^{\prime}$ is the best to train DRL agents which can keep the
fewest adversarial states. To analyze this issue, we introduce a concept of
functional equations stability drawing on relevant research about physics-
informed neural networks for partial differential equations (Wang et al.,
2022).

######  Definition 5.2 (Stability of Functional Equations).

Given two Banach spaces $\mathcal{B}_{1}$ and $\mathcal{B}_{2}$, if there
exist $\delta>0$ and $C>0$ such that for all
$Q\in\mathcal{B}_{1}\cap\mathcal{B}_{2}$ satisfying
$\|\mathcal{T}Q-Q\|_{\mathcal{B}_{1}}<\delta$, we have that
$\|Q-Q^{*}\|_{\mathcal{B}_{2}}<C\|\mathcal{T}Q-Q\|_{\mathcal{B}_{1}}$, where
$Q^{*}$ is the exact solution of this functional equation, then we say a
nonlinear functional equation $\mathcal{T}Q=Q$ is
$\left(\mathcal{B}_{1},\mathcal{B}_{2}\right)$-stable. For simplicity, we call
that functional $\mathcal{T}$ is
$\left(\mathcal{B}_{1},\mathcal{B}_{2}\right)$-stable.

The above Definition implies that if there exists a space
$\mathcal{B}^{\prime}$ such that $\mathcal{T}_{B}$ is
$\left(\mathcal{B}^{\prime},L^{\infty}\left(\mathcal{S}\times\mathcal{A}\right)\right)$-stable,
then $\left\|Q_{\theta}-Q^{*}\right\|_{\infty}$ will be controlled when
minimizing the Bellman error in $\mathcal{B}^{\prime}$ space, making DRL
agents robust according to Theorem 5.1.(2). The following theorems illustrate
the conditions that affect the stability of $\mathcal{T}_{B}$ and guide for
selecting a suitable $\mathcal{B}^{\prime}$.

######  Theorem 5.3 (Stable Properties of $\mathcal{T}_{B}$ in $L^{p}$
Spaces).

  * (1).

There exists an MDP such that for all $1\leq q<p\leq\infty$, the Bellman
optimality equations $\mathcal{T}_{B}Q=Q$ is not
$\left(L^{q}\left(\mathcal{S}\times\mathcal{A}\right),L^{p}\left(\mathcal{S}\times\mathcal{A}\right)\right)$-stable.

  * (2).

For any MDP, if the following conditions hold:

$\displaystyle C_{\mathbb{P},p}<\frac{1}{\gamma};\quad p\leq q\leq\infty;$
$\displaystyle
p\geq\max\left\\{1,\frac{\log\left(\left|\mathcal{A}\right|\right)+\log\left(\mu\left(\mathcal{S}\right)\right)}{\log\frac{1}{\gamma
C_{\mathbb{P},p}}}\right\\},$

where
$C_{\mathbb{P},p}:=\sup_{(s,a)\in\mathcal{S}\times\mathcal{A}}\left\|\mathbb{P}(\cdot\mid
s,a)\right\|_{L^{\frac{p}{p-1}}\left(\mathcal{S}\right)}$, then we have that
the Bellman optimality equations $\mathcal{T}_{B}Q=Q$ is
$\left(L^{q}\left(\mathcal{S}\times\mathcal{A}\right),L^{p}\left(\mathcal{S}\times\mathcal{A}\right)\right)$-stable.

We note that $\lim_{p\rightarrow\infty}C_{\mathbb{P},p}=1<\frac{1}{\gamma}$
and thus the first condition holds when $p$ is large enough. The second
condition suggests it is available for stability that $q$ is larger than $p$,
and the last condition reveals that $p$ is relevant to the size of the state
and action spaces. Further, we have that $\mathcal{T}_{B}$ is
$\left(L^{\infty}\left(\mathcal{S}\times\mathcal{A}\right),L^{\infty}\left(\mathcal{S}\times\mathcal{A}\right)\right)$-stable
and thus we can optimize DRL agents in space
$\mathcal{B}^{\prime}=L^{\infty}\left(\mathcal{S}\times\mathcal{A}\right)$ for
adversarial robustness. Moreover, $\mathcal{B}^{\prime}$ cannot be
$L^{q}\left(\mathcal{S}\times\mathcal{A}\right)$ for all $1\leq q<\infty$
according to Theorem 5.3.(1).

##  6 Consistent Adversarial Robust DQN

Our theoretical analysis has revealed the feasibility of training a deep
Q-network (DQN) by minimizing the Bellman error in $L^{\infty}$ space to
achieve the ORP. However, the exact computation of the $L^{\infty}$-norm is
intractable because of the unknown environment and continuous state space.
Therefore, we introduce a surrogate objective based on the $L^{\infty}$-norm
and present the Consistent Adversarial Robust deep Q-network (CAR-DQN),
enhancing both the natural and robust performance of agents.

###  6.1 Stability of Deep Q-learning

Define the state-action visitation distribution as

$d_{\mu_{0}}^{\pi}(s,a)=\mathbb{E}_{s_{0}\sim\mu_{0}}(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}\operatorname{Pr}^{\pi}(s_{t}=s,a_{t}=a|s_{0}).$

Deep Q-learning algorithms, e.g., DQN, leverage the following objective due to
interactions with the environment:

$\displaystyle\mathcal{L}(Q_{\theta};\pi_{\theta})=\mathbb{E}_{(s,a)\sim
d_{\mu_{0}}^{\pi_{\theta}}}\left|\mathcal{T}_{B}Q_{\theta}(s,a)-Q_{\theta}(s,a)\right|.$

The former theoretical analysis of functional equations stability can be
extended to $\mathcal{L}(Q_{\theta};\pi_{\theta})$ by integrating sampling
probability into a seminorm.

######  Definition 6.1 ($(p,d_{\mu_{0}}^{\pi})$-seminorm).

Given a policy $\pi$, $f:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$
and $1\leq p\leq\infty$, if $d_{\mu_{0}}^{\pi}$ is a probability density
function, we define the $(p,d_{\mu_{0}}^{\pi})$-seminorm as the following,
which satisfies the absolute homogeneity and triangle inequality:

$\displaystyle\left\|f\right\|_{p,d_{\mu_{0}}^{\pi}}:=(\int_{(s,a)\in\mathcal{S}\times\mathcal{A}}\left|d_{\mu_{0}}^{\pi}(s,a)f(s,a)\right|^{p}d\mu(s,a))^{\frac{1}{p}}.$

We note that $(p,d_{\mu_{0}}^{\pi})$-seminorm will be upgraded to a norm, if
$d_{\mu_{0}}^{\pi}(s,a)>0$ almost everywhere for
$(s,a)\in\mathcal{S}\times\mathcal{A}$. The deep Q-learning objective can be
streamlined as
$\mathcal{L}(Q_{\theta};\pi_{\theta})=\left\|\mathcal{T}_{B}Q_{\theta}-Q_{\theta}\right\|_{1,d_{\mu_{0}}^{\pi_{\theta}}}$
based on the definition. Similar to Theorem 5.3, we prove this objective
cannot ensure robustness, while $(\infty,d_{\mu_{0}}^{\pi})$-norm is necessary
for adversarial robustness (see Appendix C.2).

######  Theorem 6.2.

In the practical DQN procedure, the Bellman optimality equations
$\mathcal{T}_{B}Q=Q$ is
$(L^{\infty,d_{\mu_{0}}^{\pi}}(\mathcal{S}\times\mathcal{A}),L^{p}(\mathcal{S}\times\mathcal{A}))$-stable
for all $1\leq p\leq\infty$, while it is not
$(L^{q,d_{\mu_{0}}^{\pi}}(\mathcal{S}\times\mathcal{A}),L^{p}(\mathcal{S}\times\mathcal{A}))$-stable
for all $1\leq q<p\leq\infty$.

We also investigate the stability when $d_{\mu_{0}}^{\pi}$ is a probability
mass function in Appendix C.1 and C.3.

###  6.2 Consistent Adversarial Robust Objective

Inspired by the theoretical analysis, we propose to train robust DQNs with
$\mathcal{L}_{car}(\theta)=\|\mathcal{T}_{B}Q_{\theta}-Q_{\theta}\|_{\infty,d^{\pi_{\theta}}_{\mu_{0}}}$,
which is equal to (see Appendix D)

$\sup_{(s,a)\in\mathcal{S}\times\mathcal{A}}d_{\mu_{0}}^{\pi_{\theta}}(s,a)\max_{s_{\nu}\in
B_{\epsilon}(s)}\left|\mathcal{T}_{B}Q_{\theta}(s_{\nu},a)-Q_{\theta}(s_{\nu},a)\right|,$

where $\pi_{\theta}$ is a behavior policy related to $Q_{\theta}$ and it is
usually $\epsilon$-greedy policy derived from $Q_{\theta}$. Since interactions
with the environment in an SA-MDP happen based on the true state $s$ rather
than $s_{\nu}$, $\mathcal{T}_{B}Q_{\theta}(s_{\nu},a)$ cannot be directly
estimated. Thus, we exploit $\mathcal{T}_{B}Q_{\theta}(s,a)$ to substituted
it, attaining a surrogate objective $\mathcal{L}_{car}^{train}(\theta)$ which
can bound $\mathcal{L}_{car}$, especially in smooth environments. Denote
$\mathcal{L}_{car}^{diff}(\theta)$ as the following:

$\sup_{(s,a)\in\mathcal{S}\times\mathcal{A}}d_{\mu_{0}}^{\pi_{\theta}}(s,a)\max_{s_{\nu}\in
B_{\epsilon}(s)}\left|\mathcal{T}_{B}Q_{\theta}(s_{\nu},a)-\mathcal{T}_{B}Q_{\theta}(s,a)\right|.$

######  Theorem 6.3 (Bounding $\mathcal{L}_{car}$ with
$\mathcal{L}_{car}^{train}$).

We have that

$\left|\mathcal{L}_{car}^{train}(\theta)-\mathcal{L}_{car}^{diff}(\theta)\right|\leq\mathcal{L}_{car}(\theta)\leq\mathcal{L}_{car}^{train}(\theta)+\mathcal{L}_{car}^{diff}(\theta).$

Further, suppose the environment is $\left(L_{r},L_{\mathbb{P}}\right)$-smooth
and suppose $Q_{\theta}$ and $r$ are uniformly bounded, i.e. $\exists\
M_{Q},M_{r}>0$ such that $\left|Q_{\theta}(s,a)\right|\leq M_{Q},\
\left|r(s,a)\right|\leq M_{r}\ \forall s\in\mathcal{S},a\in\mathcal{A}$. If
$M:=\sup_{\theta,(s,a)\in\mathcal{S}\times\mathcal{A}}d_{\mu_{0}}^{\pi_{\theta}}(s,a)<\infty$,
then we have

$\mathcal{L}_{car}^{diff}(\theta)\leq C_{\mathcal{T}_{B}}\epsilon,$

where $C_{\mathcal{T}_{B}}=L_{\mathcal{T}_{B}}M$,
$L_{\mathcal{T}_{B}}=L_{r}+\gamma C_{Q}L_{\mathbb{P}}$ and
$C_{Q}=\max\left\\{M_{Q},\frac{M_{r}}{1-\gamma}\right\\}$. The definition of
$\left(L_{r},L_{\mathbb{P}}\right)$-smooth environment is shown in Appendix
A.2.3.

Theorem 6.3 suggests that $\mathcal{L}_{car}^{train}(\theta)$ is a proper
surrogate objective from the optimization perspective. It also provides an
insight into potential instability during robust training: If
$\mathcal{L}_{car}^{train}(\theta)$ is minimized to a small value yet less
than $\mathcal{L}_{car}^{diff}(\theta)$, $\mathcal{L}_{car}(\theta)$ may tend
to increase or overfit.

In implementation, to fully utilize each sample in the batch, we derive the
soft version $\mathcal{L}_{car}^{soft}(\theta)$ of the CAR objective
(derivation seen in Appendix D):

$\displaystyle\sum_{i\in\mathcal{\left|B\right|}}\alpha_{i}\max_{s_{\nu}\in
B_{\epsilon}(s_{i})}\left|r_{i}+\gamma\max_{a^{\prime}}Q_{\bar{\theta}}(s_{i}^{\prime},a^{\prime})-Q_{\theta}(s_{\nu},a_{i})\right|,$
$\displaystyle\text{where}\
\alpha_{i}=\frac{e^{\frac{1}{\lambda}\max_{s_{\nu}}\left|r_{i}+\gamma\max_{a^{\prime}}Q_{\bar{\theta}}(s_{i}^{\prime},a^{\prime})-Q_{\theta}(s_{\nu},a_{i})\right|}}{\sum_{i\in\mathcal{\left|B\right|}}e^{\frac{1}{\lambda}\max_{s_{\nu}}\left|r_{i}+\gamma\max_{a^{\prime}}Q_{\bar{\theta}}(s_{i}^{\prime},a^{\prime})-Q_{\theta}(s_{\nu},a_{i})\right|}}.$

$\mathcal{B}$ represents a batch of transition pairs sampled from the replay
buffer. $\bar{\theta}$ is the parameter of target network and $\lambda$ is the
coefficient to control the level of softness.

##  7 Experiments

In this section, we conduct extensive comparison and ablation experiments to
validate the rationality of our theoretical analysis and the effectiveness of
CAR-DQN.

Table 1: Average episode rewards $\pm$ standard error of the mean over 50
episodes on baselines and CAR-DQN. The best results of the algorithm with the
same type of solver are highlighted in bold. CAR-DQN (PGD) outperforms SA-DQN
(PGD) in all metrics and achieves remarkably better robustness ($110\%$ higher
reward) on RoadRunner. CAR-DQN (cov) outperforms baselines in a majority of
cases.

Model | Pong | BankHeist
---|---|---
Natural Reward | PGD | MinBest | ACR |  Natural Reward | PGD | MinBest | ACR
$\epsilon=1/255$ | $\epsilon=1/255$
Standard | DQN | $21.0\pm 0.0$ | $-21.0\pm 0.0$ | $-21.0\pm 0.0$ | $0$ | $1317.2\pm 4.2$ | $22.2\pm 1.9$ | $0.0\pm 0.0$ | $0$
PGD | SA-DQN | $21.0\pm 0.0$ | $21.0\pm 0.0$ | $21.0\pm 0.0$ | $0$ | $1248.8\pm 1.4$ | $965.8\pm 35.9$ | $1118.0\pm 6.3$ | $0$
CAR-DQN (Ours) | $21.0\pm 0.0$ | $21.0\pm 0.0$ | $21.0\pm 0.0$ | $0$ | $\bf 1307.0\pm 6.1$ | $\bf 1243.2\pm 7.4$ | $\bf 1242.6\pm 8.4$ | $0$
Convex Relaxation | SA-DQN | $21.0\pm 0.0$ | $21.0\pm 0.0$ | $21.0\pm 0.0$ | $1.000$ | $1236.0\pm 1.4$ | $1232.2\pm 2.5$ | $1232.2\pm 2.5$ | $0.991$
RADIAL-DQN | $21.0\pm 0.0$ | $21.0\pm 0.0$ | $21.0\pm 0.0$ | $0.898$ | $1341.8\pm 3.8$ | $1341.8\pm 3.8$ | $1341.8\pm 3.8$ | $0.982$
WocaR-DQN | $21.0\pm 0.0$ | $21.0\pm 0.0$ | $21.0\pm 0.0$ | $0.979$ | $1315.0\pm 6.1$ | $1312.0\pm 6.1$ | $1312.0\pm 6.1$ | $0.987$
CAR-DQN (Ours) | $21.0\pm 0.0$ | $21.0\pm 0.0$ | $21.0\pm 0.0$ | $0.986$ | $\bf 1349.6\pm 3.0$ | $\bf 1347.6\pm 3.6$ | $\bf 1347.4\pm 3.6$ | $0.974$
Model | Freeway | RoadRunner
Natural Reward | PGD | MinBest | ACR |  Natural Reward | PGD | MinBest | ACR
$\epsilon=1/255$ | $\epsilon=1/255$
Standard | DQN | $33.9\pm 0.0$ | $0.0\pm 0.0$ | $0.0\pm 0.0$ | $0$ | $41492\pm 903$ | $0\pm 0$ | $0\pm 0$ | $0$
PGD | SA-DQN | $33.6\pm 0.1$ | $23.4\pm 0.2$ | $21.1\pm 0.2$ | $0.250$ | $33380\pm 611$ | $20482\pm 1087$ | $24632\pm 812$ | $0$
CAR-DQN (Ours) | $\bf 34.0\pm 0.0$ | $\bf 33.7\pm 0.1$ | $\bf 33.7\pm 0.1$ | $0$ | $\bf 49700\pm 1015$ | $\bf 43286\pm 801$ | $\bf 48908\pm 1107$ | $0$
Convex Relaxation | SA-DQN | $30.0\pm 0.0$ | $30.0\pm 0.0$ | $30.0\pm 0.0$ | $1.000$ | $46372\pm 882$ | $44960\pm 1152$ | $45226\pm 1102$ | $0.819$
RADIAL-DQN | $33.1\pm 0.1$ | $\bf 33.3\pm 0.1$ | $\bf 33.3\pm 0.1$ | $0.998$ | $46224\pm 1133$ | $45990\pm 1112$ | $46082\pm 1128$ | $0.994$
WocaR-DQN | $30.8\pm 0.1$ | $31.0\pm 0.0$ | $31.0\pm 0.0$ | $0.992$ | $43686\pm 1608$ | $45636\pm 706$ | $45636\pm 706$ | $0.956$
CAR-DQN (Ours) | $\bf 33.2\pm 0.1$ | $33.2\pm 0.1$ | $33.2\pm 0.1$ | $0.981$ | $\bf 49398\pm 1106$ | $\bf 49456\pm 992$ | $\bf 47526\pm 1132$ | $0.760$

###  7.1 Implementation details

Environments. Following recent works (Zhang et al., 2020; Oikarinen et al.,
2021; Liang et al., 2022), we conduct experiments on four Atari video games
(Brockman et al., 2016), including Pong, Freeway, BankHeist, and RoadRunner.
These environments are characterized by high-dimensional pixel inputs and
discrete action spaces. We pre-process the input images into $84\times 84$
grayscale images and normalize the pixel values to the range $[0,1]$. In each
environment, agents execute an action every 4 frames, skipping the other
frames without frame stacking. All rewards are clipped to the range $[-1,1]$.

RoadRunner

BankHeist

Freeway

Pong

Figure 3: Episode rewards of CAR-DQN agents with and without 10-step PGD
attacks on 4 Atari games and 5 random seeds. As evidenced by the overlap of
the two curves, CAR-DQN achieves the consistency between Bellman optimal
policy and ORP.

Baselines. We compare CAR-DQN with several state-of-the-art robust training
methods. SA-DQN (Zhang et al., 2020) incorporates a KL-based regularization
and solves the inner maximization problem using PGD (Madry et al., 2017) and
CROWN-IBP (Zhang et al., 2019), respectively. RADIAL-DQN (Oikarinen et al.,
2021) applies adversarial regularizations based on robustness verification
bounds computed by IBP (Gowal et al., 2018). We utilize the official code of
SA-DQN and RADIAL-DQN and replicate WocaR-DQN, as its official implementation
uses a different environment wrapper compared to SA-DQN and RADIAL.

Evaluations. We evaluate the robustness of agents using three metrics on Atari
games: (1) episode return under a 10-steps untargeted PGD attack (Madry et
al., 2017), (2) episode return under MinBest (Huang et al., 2017), both of
which minimize the probability of selecting the learned best action, and (3)
Action Certification Rate (ACR) (Zhang et al., 2020). ACR uses relaxation
bounds to estimate the percentage of frames where the learned best action is
guaranteed to remain unchanged during rollouts under attacks.

CAR-DQN. We implement CAR-DQN based on Double Dueling DQN (Van Hasselt et al.,
2016; Wang et al., 2016) and train all baselines and CAR-DQN for 4.5 million
steps, based on the same standard model released by Zhang et al. (2020), which
has been trained for 6 million steps. We increase the attack $\epsilon$ from
$0$ to $1/255$ in the first 4 million steps using the same smoothed schedule
as in Zhang et al. (2020); Oikarinen et al. (2021); Liang et al. (2022), and
then continue training with a fixed $\epsilon$ for the remaining 0.5 million
steps. We use Huber loss to replace the absolute value function and separately
apply classic gradient-based methods (PGD) and cheap convex relaxation (IBP)
to resolve the inner optimization in $\mathcal{L}_{car}^{soft}(\theta)$. For
CAR-DQN with PGD solver, hyper-parameters are the same as SA-DQN (Zhang et
al., 2020). For CAR-DQN with IBP solver, we update the target network every
$2000$ steps, and set learning rate as $1.25\times 10^{-4}$, batch size as
$32$, exploration $\epsilon_{exp}$-end as $0.01$, soft coefficient
$\lambda=1.0$ and discount factor as $0.99$. We use a replay buffer with a
capacity of $2\times 10^{5}$ and Adam optimizer (Kingma & Ba, 2014) with
$\beta_{1}=0.9$ and $\beta_{2}=0.999$.

###  7.2 Comparison Results

RoadRunner

BankHeist

Freeway

Pong

Robust

Natural

Figure 4: Episode rewards of baselines and CAR-DQN with and without PGD
attacks on 4 Atari games. Shaded regions are computed over 5 random seeds.
CAR-DQN demonstrates superior natural and robust performance in all
environments.

Evaluation on benchmarks. Table 1 presents the natural and robust performance,
with all agents trained and attacked using a perturbation radius of
$\epsilon=1/255$. More results and discussion are provided in Appendix G.
Notably, CAR-DQN agents exhibit superior performance compared to baselines in
the most challenging RoadRunner environment, achieving significant
improvements in both natural and robust rewards. In the other three games,
CAR-DQN can well match the performance of the baselines. Our proposed loss
function coupled with the PGD solver, achieves a remarkable return of around
45000 on the RoadRunner environment, outperforming the SA-DQN with the PGD
approach. It also attains $60\%$ higher robust rewards under the MinBest
attack on the Freeway game. In these two solvers, we observe that PGD exhibits
relatively weaker robust performance compared to the convex relaxation,
especially failing to ensure the ACR computed with relaxation bounds. This
discrepancy can be attributed to that the PGD solver offers a lower bound
surrogate function of the loss, while the IBP solver gives an upper bound.

Consistency in natural and PGD attack returns. Figure 3 records the natural
and PGD attack returns of CAR-DQN agents during training, showcasing a strong
alignment between natural performance and robustness across all environments.
This alignment validates our theory that the ORP is consistent with the
Bellman optimal policy, and confirms the rationality of the proposed CAP. In
addition, Figure 4 illustrates the natural episode return and robustness
during training for different algorithms. It is worth noting that CAR-DQN
agents can fast and stably converge to peak robustness and natural performance
across all environments, while other algorithms exhibit unstable trends. For
instance, the natural reward curves of SA-DQN and WocaR-DQN on BankHeist and
RADIAL-DQN on RoadRunner distinctly tend to decrease, and the robust curves of
SA-DQN and WocaR-DQN on BankHeist tend to decline. This discrepancy primarily
stems from their robustness objectives, which diverge from the standard
training loss and consequently result in learning sub-optimal actions. In
contrast, the proposed consistent objective ensures that CAR-DQN always learns
optimal actions in both natural and robust directions.

Training efficiency. Training SA-DQN, RADIAL-DQN, WocaR-DQN, and CAR-DQN costs
approximately 27, 12, 20, and 14 hours, respectively. All these models are
trained for 4.5 million frames on identical hardware. Additionally, our
proposed loss does not incur additional memory consumption compared to vanilla
training.

###  7.3 Ablation Studies

Table 2: Performance of DQN with different Bellman $p$-error.

Environment | Norm | Natural | PGD | MinBest | ACR
---|---|---|---|---|---
Pong | $L^{1}$ | $\bf 21.0\pm 0.0$ | $-21.0\pm 0.0$ | $-21.0\pm 0.0$ | $0$
$L^{2}$ | $\bf 21.0\pm 0.0$ | $-21.0\pm 0.0$ | $-20.8\pm 0.1$ | $0$
$L^{\infty}$ | $\bf 21.0\pm 0.0$ | $\bf 21.0\pm 0.0$ | $\bf 21.0\pm 0.0$ | $0.985$
Freeway | $L^{1}$ | $\bf 33.9\pm 0.1$ | $0.0\pm 0.0$ | $0.0\pm 0.0$ | $0$
$L^{2}$ | $21.8\pm 0.3$ | $21.7\pm 0.3$ | $22.1\pm 0.3$ | $0$
$L^{\infty}$ | $33.3\pm 0.1$ | $\bf 33.2\pm 0.1$ | $\bf 33.2\pm 0.1$ | $0.981$
BankHeist | $L^{1}$ | $1325.5\pm 5.7$ | $27.0\pm 2.0$ | $0.0\pm 0.0$ | $0$
$L^{2}$ | $1314.5\pm 4.0$ | $18.5\pm 1.5$ | $22.5\pm 2.6$ | $0$
$L^{\infty}$ | $\bf 1356.0\pm 1.7$ | $\bf 1356.5\pm 1.1$ | $\bf 1356.5\pm 1.1$ | $0.969$
RoadRunner | $L^{1}$ | $43795\pm 1066$ | $0\pm 0$ | $0\pm 0$ | $0$
$L^{2}$ | $30620\pm 990$ | $0\pm 0$ | $0\pm 0$ | $0$
$L^{\infty}$ | $\bf 49500\pm 2106$ | $\bf 48230\pm 1648$ | $\bf 48050\pm 1642$ | $0.947$

Necessity of infinity-norm. To verify the necessity of the
$(\infty,d_{\mu_{0}}^{\pi})$-norm for adversarial robustness, we train DQN
agents using the Bellman error under $(1,d_{\mu_{0}}^{\pi})$-norm and
$(2,d_{\mu_{0}}^{\pi})$-norm, respectively. We then compare their performance
with our CAR-DQN, which approximates the Bellman error under
$(\infty,d_{\mu_{0}}^{\pi})$-norm. As shown in Table 2, all agents perform
well without attacks in the four games. However, the performance of
$(1,d_{\mu_{0}}^{\pi})$-norm and $(2,d_{\mu_{0}}^{\pi})$-norm agents highly
degrades under strong attacks, receiving episode rewards close to the lowest
in each game. These empirical results are highly consistent with Theorem 5.1.

Figure 5: Natural, PGD attack, and MinBest attack rewards of CAR-DQN with
different soft coefficients on RoadRunner game. Table 3: Ablation studies for
soft coefficients on 4 Atari games.

Environment | $\lambda$ | Natural | PGD | MinBest | ACR
---|---|---|---|---|---
Pong | $0$ | $\bf 21.0\pm 0.0$ | $\bf 21.0\pm 0.0$ | $\bf 21.0\pm 0.0$ | $0.972$
$1$ | $\bf 21.0\pm 0.0$ | $\bf 21.0\pm 0.0$ | $\bf 21.0\pm 0.0$ | $0.985$
$\infty$ | $20.6\pm 0.1$ | $20.7\pm 0.1$ | $20.7\pm 0.1$ | $0.980$
Freeway | $0$ | $31.6\pm 0.2$ | $31.5\pm 0.1$ | $31.5\pm 0.1$ | $0.966$
$1$ | $\bf 33.3\pm 0.1$ | $\bf 33.2\pm 0.1$ | $\bf 33.2\pm 0.1$ | $0.981$
$\infty$ | $31.5\pm 0.1$ | $30.9\pm 0.3$ | $31.2\pm 0.2$ | $0.967$
BankHeist | $0$ | $1307.5\pm 11.0$ | $1288.5\pm 14.0$ | $1284.0\pm 13.8$ | $0.980$
$1$ | $\bf 1356.0\pm 1.7$ | $\bf 1356.5\pm 1.1$ | $\bf 1356.5\pm 1.1$ | $0.969$
$\infty$ | $1326.0\pm 4.8$ | $1316.0\pm 6.8$ | $1314.0\pm 6.6$ | $0.979$
RoadRunner | $0$ | $25160\pm 802$ | $24540\pm 760$ | $26785\pm 617$ | $0.007$
$1$ | $\bf 49500\pm 2106$ | $\bf 48230\pm 1648$ | $\bf 48050\pm 1642$ | $0.947$
$\infty$ | $40890\pm 2075$ | $36760\pm 1874$ | $36740\pm 2098$ | $0.940$

Effects of soft coefficient. We validate the effectiveness of the soft CAR-DQN
loss by adjusting the soft coefficient $\lambda$. We train CAR-DQN agents on
the RoadRunner environment with $\lambda$ values ranging from $0$ to $\infty$.
When $\lambda=0$ we utilize the sample with the largest adversarial TD-error
from a batch, while $\lambda=\infty$ corresponds to averaging over all samples
in a batch. It is worth noting that a small $\lambda$ may lead to numerical
instability. As depicted in Figure 5, the agents exhibit similar capabilities
when $0.5\leq\lambda\leq 10$, indicating that the learned policies are not
sensitive to the soft coefficient within this range. Table 3 displays the
performance of CAR-DQN agents with $\lambda=0,1,\infty$ across four Atari
environments. In the RoadRunner, the case $\lambda=0$ yields poor performance,
achieving returns around 25000 due to inadequate utilization of the samples.
Interestingly, utilizing only the sample with the largest adversarial TD error
from a batch achieves good robustness on the other three simpler games. The
case $\lambda=\infty$ results in worse robustness compared to other cases with
differentiated weights. This suggests that each sample in a batch plays a
distinct role in robust training, and we can enhance robust performance by
specifying weightings. These results further validate the efficacy of our CAR-
DQN loss.

##  8 Conclusion

In this paper, we prove the alignment of the optimal robust policy with the
Bellman optimal policy under the consistency assumption of policy. We show
that measuring Bellman error in differed $L^{p}$ spaces yields varied
performance, underscoring the necessity of Bellman infinity-error for
robustness. We validate these findings through experiments with CAR-DQN, which
optimizes a surrogate objective of Bellman infinity-error. We believe this
work contributes significantly to unveiling the nature of robustness in
Q-learning. Since our work focuses on value-based DRL with discrete action
space, we will extend future research into the policy-based DRL and continuous
action space setting.

## Broader Impact

Reinforcing the robustness of Deep Reinforcement Learning agents is crucial
for commercial and industrial applications. Unlike previous approaches that
focus on imposing smoothness or stability on neural networks through
elaborated regularization techniques, this study uncovers the inherent
robustness of the Bellman optimal policy under adversarial attack scenarios.
We believe this discovery can offer fresh insights to the research community,
potentially driving advancements in related applications.

## References

  * Behzadan & Munir (2017a) Behzadan, V. and Munir, A.  Vulnerability of deep reinforcement learning to policy induction attacks.  In _Machine Learning and Data Mining in Pattern Recognition: 13th International Conference, MLDM 2017, New York, NY, USA, July 15-20, 2017, Proceedings 13_ , pp. 262–275. Springer, 2017a.
  * Behzadan & Munir (2017b) Behzadan, V. and Munir, A.  Whatever does not kill deep reinforcement learning, makes it stronger.  _arXiv preprint arXiv:1712.09344_ , 2017b.
  * Bharti et al. (2022) Bharti, S., Zhang, X., Singla, A., and Zhu, J.  Provable defense against backdoor policies in reinforcement learning.  _Advances in Neural Information Processing Systems_ , 35:14704–14714, 2022.
  * Brockman et al. (2016) Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., and Zaremba, W.  Openai gym.  _arXiv preprint arXiv:1606.01540_ , 2016.
  * Bukharin et al. (2023) Bukharin, A., Li, Y., Yu, Y., Zhang, Q., Chen, Z., Zuo, S., Zhang, C., Zhang, S., and Zhao, T.  Robust multi-agent reinforcement learning via adversarial regularization: Theoretical foundation and stable algorithms.  _arXiv preprint arXiv:2310.10810_ , 2023.
  * Fischer et al. (2019) Fischer, M., Mirman, M., Stalder, S., and Vechev, M.  Online robustness training for deep reinforcement learning.  _arXiv preprint arXiv:1911.00887_ , 2019.
  * Gleave et al. (2019) Gleave, A., Dennis, M., Wild, C., Kant, N., Levine, S., and Russell, S.  Adversarial policies: Attacking deep reinforcement learning.  _arXiv preprint arXiv:1905.10615_ , 2019.
  * Goodfellow et al. (2014) Goodfellow, I. J., Shlens, J., and Szegedy, C.  Explaining and harnessing adversarial examples.  _arXiv preprint arXiv:1412.6572_ , 2014.
  * Gowal et al. (2018) Gowal, S., Dvijotham, K., Stanforth, R., Bunel, R., Qin, C., Uesato, J., Arandjelovic, R., Mann, T., and Kohli, P.  On the effectiveness of interval bound propagation for training verifiably robust models.  _arXiv preprint arXiv:1810.12715_ , 2018.
  * Guo et al. (2023) Guo, J., Li, A., Wang, L., and Liu, C.  Policycleanse: Backdoor detection and mitigation for competitive reinforcement learning.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pp. 4699–4708, 2023.
  * He et al. (2023) He, S., Han, S., Su, S., Han, S., Zou, S., and Miao, F.  Robust multi-agent reinforcement learning with state uncertainty.  _arXiv preprint arXiv:2307.16212_ , 2023.
  * Huang et al. (2017) Huang, S., Papernot, N., Goodfellow, I., Duan, Y., and Abbeel, P.  Adversarial attacks on neural network policies.  _arXiv preprint arXiv:1702.02284_ , 2017.
  * Ibarz et al. (2021) Ibarz, J., Tan, J., Finn, C., Kalakrishnan, M., Pastor, P., and Levine, S.  How to train your robot with deep reinforcement learning: lessons we have learned.  _The International Journal of Robotics Research_ , 40(4-5):698–721, 2021.
  * Ilahi et al. (2021) Ilahi, I., Usama, M., Qadir, J., Janjua, M. U., Al-Fuqaha, A., Hoang, D. T., and Niyato, D.  Challenges and countermeasures for adversarial attacks on deep reinforcement learning.  _IEEE Transactions on Artificial Intelligence_ , 3(2):90–109, 2021.
  * Inkawhich et al. (2019) Inkawhich, M., Chen, Y., and Li, H.  Snooping attacks on deep reinforcement learning.  _arXiv preprint arXiv:1905.11832_ , 2019.
  * Kingma & Ba (2014) Kingma, D. P. and Ba, J.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Kiourti et al. (2020) Kiourti, P., Wardega, K., Jha, S., and Li, W.  Trojdrl: evaluation of backdoor attacks on deep reinforcement learning.  In _2020 57th ACM/IEEE Design Automation Conference (DAC)_ , pp. 1–6. IEEE, 2020.
  * Kiran et al. (2021) Kiran, B. R., Sobh, I., Talpaert, V., Mannion, P., Al Sallab, A. A., Yogamani, S., and Pérez, P.  Deep reinforcement learning for autonomous driving: A survey.  _IEEE Transactions on Intelligent Transportation Systems_ , 23(6):4909–4926, 2021.
  * Korkmaz (2023) Korkmaz, E.  Adversarial robust deep reinforcement learning requires redefining robustness.  _arXiv preprint arXiv:2301.07487_ , 2023.
  * Kos & Song (2017) Kos, J. and Song, D.  Delving into adversarial attacks on deep policies.  _arXiv preprint arXiv:1705.06452_ , 2017.
  * Liang et al. (2022) Liang, Y., Sun, Y., Zheng, R., and Huang, F.  Efficient adversarial training without attacking: Worst-case-aware robust reinforcement learning.  _Advances in Neural Information Processing Systems_ , 35:22547–22561, 2022.
  * Lillicrap et al. (2015) Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D.  Continuous control with deep reinforcement learning.  _arXiv preprint arXiv:1509.02971_ , 2015.
  * Lin et al. (2017) Lin, Y.-C., Hong, Z.-W., Liao, Y.-H., Shih, M.-L., Liu, M.-Y., and Sun, M.  Tactics of adversarial attack on deep reinforcement learning agents.  _arXiv preprint arXiv:1703.06748_ , 2017.
  * Lu et al. (2023) Lu, C., Willi, T., Letcher, A., and Foerster, J. N.  Adversarial cheap talk.  In _International Conference on Machine Learning_ , pp. 22917–22941. PMLR, 2023.
  * Madry et al. (2017) Madry, A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A.  Towards deep learning models resistant to adversarial attacks.  _arXiv preprint arXiv:1706.06083_ , 2017.
  * Mnih et al. (2015) Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., et al.  Human-level control through deep reinforcement learning.  _nature_ , 518(7540):529–533, 2015.
  * Mnih et al. (2016) Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap, T., Harley, T., Silver, D., and Kavukcuoglu, K.  Asynchronous methods for deep reinforcement learning.  In _International conference on machine learning_ , pp. 1928–1937. PMLR, 2016.
  * Nie et al. (2023) Nie, B., Ji, J., Fu, Y., and Gao, Y.  Improve robustness of reinforcement learning against observation perturbations via $l\\_\infty$ lipschitz policy networks.  _arXiv preprint arXiv:2312.08751_ , 2023.
  * Oikarinen et al. (2021) Oikarinen, T., Zhang, W., Megretski, A., Daniel, L., and Weng, T.-W.  Robust deep reinforcement learning through adversarial loss.  _Advances in Neural Information Processing Systems_ , 34:26156–26167, 2021.
  * Pattanaik et al. (2017) Pattanaik, A., Tang, Z., Liu, S., Bommannan, G., and Chowdhary, G.  Robust deep reinforcement learning with adversarial attacks.  _arXiv preprint arXiv:1712.03632_ , 2017.
  * Schulman et al. (2015) Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P.  Trust region policy optimization.  In _International conference on machine learning_ , pp. 1889–1897. PMLR, 2015.
  * Schulman et al. (2017) Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_ , 2017.
  * Shen et al. (2020) Shen, Q., Li, Y., Jiang, H., Wang, Z., and Zhao, T.  Deep reinforcement learning with robust and smooth policy.  In _International Conference on Machine Learning_ , pp. 8707–8718. PMLR, 2020.
  * Silver et al. (2014) Silver, D., Lever, G., Heess, N., Degris, T., Wierstra, D., and Riedmiller, M.  Deterministic policy gradient algorithms.  In _International conference on machine learning_ , pp. 387–395. Pmlr, 2014.
  * Silver et al. (2016) Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al.  Mastering the game of go with deep neural networks and tree search.  _nature_ , 529(7587):484–489, 2016.
  * Sun et al. (2021) Sun, Y., Zheng, R., Liang, Y., and Huang, F.  Who is the strongest enemy? towards optimal and efficient evasion attacks in deep rl.  _arXiv preprint arXiv:2106.05087_ , 2021.
  * Van Hasselt et al. (2016) Van Hasselt, H., Guez, A., and Silver, D.  Deep reinforcement learning with double q-learning.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 30, 2016.
  * Wang et al. (2022) Wang, C., Li, S., He, D., and Wang, L.  Is $l^{2}$ physics informed loss always suitable for training physics informed neural network?  _Advances in Neural Information Processing Systems_ , 35:8278–8290, 2022.
  * Wang et al. (2021) Wang, L., Javed, Z., Wu, X., Guo, W., Xing, X., and Song, D.  Backdoorl: Backdoor attack against competitive reinforcement learning.  _arXiv preprint arXiv:2105.00579_ , 2021.
  * Wang et al. (2016) Wang, Z., Schaul, T., Hessel, M., Hasselt, H., Lanctot, M., and Freitas, N.  Dueling network architectures for deep reinforcement learning.  In _International conference on machine learning_ , pp. 1995–2003. PMLR, 2016.
  * Yu et al. (2021) Yu, C., Liu, J., Nemati, S., and Yin, G.  Reinforcement learning in healthcare: A survey.  _ACM Computing Surveys (CSUR)_ , 55(1):1–36, 2021.
  * Zhang et al. (2022) Zhang, B., Jiang, D., He, D., and Wang, L.  Rethinking lipschitz neural networks and certified robustness: A boolean function perspective.  _Advances in Neural Information Processing Systems_ , 35:19398–19413, 2022.
  * Zhang et al. (2019) Zhang, H., Chen, H., Xiao, C., Gowal, S., Stanforth, R., Li, B., Boning, D., and Hsieh, C.-J.  Towards stable and efficient training of verifiably robust neural networks.  _arXiv preprint arXiv:1906.06316_ , 2019.
  * Zhang et al. (2020) Zhang, H., Chen, H., Xiao, C., Li, B., Liu, M., Boning, D., and Hsieh, C.-J.  Robust deep reinforcement learning against adversarial perturbations on state observations.  _Advances in Neural Information Processing Systems_ , 33:21024–21037, 2020.
  * Zhang et al. (2021) Zhang, H., Chen, H., Boning, D., and Hsieh, C.-J.  Robust reinforcement learning on state observations with learned optimal adversary.  _arXiv preprint arXiv:2101.08452_ , 2021.
  * Zheng et al. (2018) Zheng, G., Zhang, F., Zheng, Z., Xiang, Y., Yuan, N. J., Xie, X., and Li, Z.  Drn: A deep reinforcement learning framework for news recommendation.  In _Proceedings of the 2018 world wide web conference_ , pp. 167–176, 2018.

##  Appendix A Theorems and Proofs of Optimal Adversarial Robustness

###  A.1 Reasonablity of the Consistency Assumption

######  Theorem A.1.

For any MDP $\mathcal{M}$, let $\mathcal{S}_{nu}$ denote the state set where
the optimal action is not unique, i.e.
$\mathcal{S}_{nu}=\left\\{s\in\mathcal{S}|\mathop{\arg\max}_{a}Q^{*}(s,a)\text{
is not a singleton}\right\\}$. If $Q^{*}(\cdot,a)$ is continuous almost
everywhere in $\mathcal{S}$ for all $a\in\mathcal{A}$, we have the following
conclusions:

  * •

For almost everywhere $s\in\mathcal{S}\setminus\mathcal{S}_{nu}$, there exists
$\epsilon>0$ such that $B_{\epsilon}(s)=B^{*}_{\epsilon}(s)$.

  * •

Given $\epsilon>0$, let $\mathcal{S}_{nin}$ denote the set of states where the
intrinsic state $\epsilon$-neighourhood is not the same as the
$\epsilon$-neighourhood, i.e.
$\mathcal{S}_{nin}=\left\\{s\in\mathcal{S}|B_{\epsilon}(s)\neq
B^{*}_{\epsilon}(s)\right\\}$. Then, we have
$\mathcal{S}_{nin}\subseteq\mathcal{S}_{nu}\cup\mathcal{S}_{0}+B_{\epsilon}=\left\\{s_{1}+s_{2}|s_{1}\in\mathcal{S}_{nu}\cup\mathcal{S}_{0},\
\|s_{2}\|\leq\epsilon\right\\}$, where $\mathcal{S}_{0}$ is a zero measure
set.

###### Proof.

(1) Let $\mathcal{S}^{\prime}=\\{s\in\mathcal{S}|\exists
a\in\mathcal{A},\text{s.t. $Q^{*}(s,a)$ is not continuous at }s\\}$. Then
$\mu(\mathcal{S}^{\prime})=0$ because $Q^{*}(\cdot,a)$ is continuous almost
everywhere in $\mathcal{S}$ for all $a\in\mathcal{A}$ and $\mathcal{A}$ is a
finite discrete set. And $Q^{*}(s,a)$ is continuous in
$\left(\mathcal{S}\setminus\mathcal{S}_{nu}\right)\setminus\mathcal{S}^{\prime}$.
Because $\arg\max_{a}Q^{*}(s,a)$ is a singleton for
$s\in\left(\mathcal{S}\setminus\mathcal{S}_{nu}\right)\setminus\mathcal{S}^{\prime}$,
define $\arg\max_{a}Q^{*}(s,a)=\\{a_{s}^{*}\\}$ for any
$s\in\left(\mathcal{S}\setminus\mathcal{S}_{nu}\right)\setminus\mathcal{S}^{\prime}$
. Then $Q^{*}(s,a_{s}^{*})>Q^{*}(s,a)$ for a fixed
$a\in\mathcal{A}\setminus\\{a_{s}^{*}\\}$. According to continuity of
$Q^{*}(\cdot,a)$ for all $a\in\mathcal{A}$, there exists $\epsilon_{a}>0$,
such that $Q^{*}(s^{\prime},a_{s}^{*})>Q^{*}(s^{\prime},a)$ for all
$s^{\prime}\in B_{\epsilon_{a}}(s)$. Because $\mathcal{A}$ is a finite
discrete set, let
$\epsilon=\min_{a\in\mathcal{A}\setminus{a_{s}^{*}}}\\{\epsilon_{a}\\}$, then
$Q^{*}(s^{\prime},a_{s^{\prime}}^{*})>Q^{*}(s^{\prime},a)$ for all
$s^{\prime}\in B_{\epsilon}(s)$ and for all
$a\in\mathcal{A}\setminus\\{a_{s^{\prime}}^{*}\\}$, i.e.
$B_{\epsilon}(s)=B_{\epsilon}^{*}(s)$.

(2)Let $\mathcal{S}_{n}=\\{s\in\mathcal{S}|\forall\epsilon_{1}>0,\exists
s^{\prime}\in B_{\epsilon_{1}}(s),\ \text{s.t.
}\arg\max_{a}Q^{*}(s^{\prime},a)\neq\arg\max_{a}Q^{*}(s,a)\\}$ and
$\mathcal{S}_{0}=\mathcal{S}_{n}\cap\mathcal{S}^{\prime}$. Then $S_{0}$ is the
set of discontinuous points that cause the optimal action to change. And
$\mu(\mathcal{S}_{0})=\mu(\mathcal{S}_{n}\cap\mathcal{S}^{\prime})=0$ because
$\mu(\mathcal{S}^{\prime})=0$.

For any $s\in\mathcal{S}_{nin}=\left\\{s\in\mathcal{S}|B_{\epsilon}(s)\neq
B^{*}_{\epsilon}(s)\right\\}$, we have the following two cases.

Case 1. $\exists s^{\prime}\in B_{\epsilon}(s)$ s.t.
$s^{\prime}\in\mathcal{S}_{nu}$, then $s\in\mathcal{S}_{nu}+B_{\epsilon}$,
i.e.

$s\in\mathcal{S}_{nu}\cup\mathcal{S}_{0}+B_{\epsilon}.$ (1)

Case 2. $\forall s^{\prime}\in
B_{\epsilon}(s),s^{\prime}\notin\mathcal{S}_{nu}$, which means that
$\arg\max_{a}Q^{*}(s^{\prime},a)$ is a singleton for all $s^{\prime}\in
B_{\epsilon}(s)$. Define
$\arg\max_{a}Q^{*}(s^{\prime},a)=\\{a_{s^{\prime}}^{*}\\}$ for any
$s^{\prime}\in B_{\epsilon}(s)$.

Because $s\in\mathcal{S}_{nin}$, there exist a $s^{\prime}\in B_{\epsilon}(s)$
such that $a_{s^{\prime}}^{*}\neq a_{s}^{*}$. Let $s_{1}$ be the point that
closest to $s$ satisfing $a_{s_{1}}^{*}\neq a_{s}^{*}$, then $s_{1}\in
B_{\epsilon}(s)$. We have

$s_{1}\in\mathcal{S}_{n}.$ (2)

Otherwise $s_{1}\notin\mathcal{S}_{n}$ means that
$\exists\epsilon_{1}>0,\forall s^{\prime}\in B_{\epsilon_{1}}(s_{1})$,
$a_{s^{\prime}}^{*}=a_{s_{1}}^{*}$, then $s_{1}$ is not the point that closest
to $s$ satisfing $a_{s_{1}}^{*}\neq a_{s}^{*}$, which is a contradiction. We
also have

$s_{1}\in\mathcal{S}^{\prime}.$ (3)

Otherwise $s_{1}\notin\mathcal{S}^{\prime}$ means that $\forall
a\in\mathcal{A}$, $Q^{*}(\cdot,a)$ is continuous in $s_{1}$. First, we have

$Q^{*}(s_{1},a_{s_{1}}^{*})>Q^{*}(s_{1},a),\forall
a\in\mathcal{A}\setminus\\{a_{s_{1}}^{*}\\}.$ (4)

Then $\exists\epsilon_{2}>0$, $\forall s\in B_{\epsilon_{2}}(s_{1})$, s.t.

$Q^{*}(s,a_{s_{1}}^{*})>Q^{*}(s,a),\forall
a\in\mathcal{A}\setminus\\{a_{s_{1}}^{*}\\}.$ (5)

because of the continuity of point $s_{1}$. This contradicts the definition of
$s_{1}$.

According to (2) and (3), we have
$s_{1}\in\mathcal{S}^{\prime}\cap\mathcal{S}_{n}$ i.e.
$s_{1}\in\mathcal{S}_{0}$. Then $s\in\mathcal{S}_{0}+B_{\epsilon}(s)$, i.e.

$s\in\mathcal{S}_{nu}\cup\mathcal{S}_{0}+B_{\epsilon}.$ (6)

Thus

$\mathcal{S}_{nin}\subseteq\mathcal{S}_{nu}\cup\mathcal{S}_{0}+B_{\epsilon}.$
(7)

∎

######  Remark A.2.

In practical and complex tasks, we can view $\mathcal{S}_{nu}$ as an empty
set.

######  Remark A.3.

Except for the smooth environment, many tasks can be modeled as environments
with sparse rewards. Further, the value function and action-value function in
these environments are almost everywhere continuous.

######  Remark A.4.

According to the construction in the above proof, we know that
$\mathcal{S}_{0}$ is a set of special discontinuous points and its elements
are rare in practical complex environments.

Further, we can get the following corollary in the setting of continuous
functions and there are better conclusions.

######  Corollary A.5.

For any MDP $\mathcal{M}$, let $\mathcal{S}_{nu}$ denote the state set where
the optimal action is not unique, i.e.
$\mathcal{S}_{nu}=\left\\{s\in\mathcal{S}|\mathop{\arg\max}_{a}Q^{*}(s,a)\text{
is not a singleton}\right\\}$. If $Q^{*}(\cdot,a)$ is continuous in
$\mathcal{S}$ for all $a\in\mathcal{A}$, we have the following conclusions:

  * •

For $s\in\mathcal{S}\setminus\mathcal{S}_{nu}$, there exists $\epsilon>0$ such
that $B_{\epsilon}(s)=B^{*}_{\epsilon}(s)$.

  * •

Given $\epsilon>0$, let $\mathcal{S}_{nin}$ denote the set of states where the
intrinsic state $\epsilon$-neighourhood is not the same as the
$\epsilon$-neighourhood, i.e.
$\mathcal{S}_{nin}=\left\\{s\in\mathcal{S}|B_{\epsilon}(s)\neq
B^{*}_{\epsilon}(s)\right\\}$. Then, we have
$\mathcal{S}_{nin}\subseteq\mathcal{S}_{nu}+B_{\epsilon}=\left\\{s_{1}+s_{2}|s_{1}\in\mathcal{S}_{nu},\
\|s_{2}\|\leq\epsilon\right\\}$. Especially, when $\mathcal{S}_{nu}$ is a
finite set, we have
$\mu\left(\mathcal{S}_{nin}\right)\leq\left|\mathcal{S}_{nu}\right|\mu\left(B_{\epsilon}\right)=C_{d}\left|\mathcal{S}_{nu}\right|\epsilon^{d}$,
where $C_{d}$ is a constant with respect to dimension $d$ and norm.

###### Proof.

Corollary A.5 can be derived from Theorem A.1 because we have the following
conclusion in continuous case.

$\mathcal{S}_{0}=\\{s\in\mathcal{S}|\exists a\in\mathcal{A},\text{s.t.
$Q^{*}(s,a)$ is not continuous at }s\\}=\emptyset$ (8)

∎

######  Remark A.6.

Certain natural environments show smooth reward function and transition
dynamics, especially in continuous control tasks where the transition dynamics
come from some physical laws. Further, the value function and action-value
function in these environments is continuous.

###  A.2 ORP and CAR Operator

Define the consistent adversarial robust operator for adversarial action-value
function:

$\left(\mathcal{T}_{car}Q\right)(s,a)=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[\min_{s^{\prime}_{\nu}\in
B_{\epsilon}(s^{\prime})}Q\left(s^{\prime},\mathop{\arg\max}_{a_{s^{\prime}_{\nu}}}Q\left(s^{\prime}_{\nu},a_{s^{\prime}_{\nu}}\right)\right)\right].$
(9)

####  A.2.1 Equivalence with Optimal Adversarial Value Function

######  Lemma A.7 (Bellman equations for fixed $\pi$ and $\nu$ in SA-MDP,
Zhang et al. (2020)).

Given $\pi:\mathcal{S}\rightarrow\Delta(\mathcal{A})$ and
$\nu:\mathcal{S}\rightarrow\mathcal{S}$, we have

$\displaystyle V^{\pi\circ\nu}(s)$
$\displaystyle=\mathbb{E}_{a\sim\pi\left(\cdot|{\nu\left(s\right)}\right)}Q^{\pi\circ\nu}(s,a)$
(10)
$\displaystyle=\mathbb{E}_{a\sim\pi\left(\cdot|{\nu\left(s\right)}\right)}\left[r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}V^{\pi\circ\nu}(s^{\prime})\right],$
(11) $\displaystyle Q^{\pi\circ\nu}(s,a)$
$\displaystyle=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}V^{\pi\circ\nu}(s^{\prime})$
(12)
$\displaystyle=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a),a^{\prime}\sim\pi\left(\cdot|{\nu\left(s^{\prime}\right)}\right)}Q^{\pi\circ\nu}(s^{\prime},a^{\prime}).$
(13)

######  Lemma A.8 (Bellman equation for strongest adversary $\nu^{*}$ in SA-
MDP, Zhang et al. (2020)).

$V^{\pi\circ\nu^{*}(\pi)}(s)=\min_{\nu(s)\in
B_{\epsilon}(s)}\mathbb{E}_{a\sim\pi\left(\cdot|{\nu\left(s\right)}\right)}Q^{\pi\circ\nu^{*}(\pi)}(s,a).$
(14)

######  Definition A.9.

Define the linear functional
$\mathcal{L}^{\pi\circ\nu}:L^{p}\left(\mathcal{S}\times\mathcal{A}\right)\rightarrow
L^{p}\left(\mathcal{S}\times\mathcal{A}\right)$ for fixed $\pi$ and $\nu$:

$\left(\mathcal{L}^{\pi\circ\nu}Q\right)(s,a):=\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a),a^{\prime}\sim\pi\left(\cdot|{\nu\left(s^{\prime}\right)}\right)}Q(s^{\prime},a^{\prime}).$
(15)

Then, by lemma A.7, we have that

$Q^{\pi\circ\nu}=r+\gamma\mathcal{L}^{\pi\circ\nu}Q^{\pi\circ\nu}.$ (16)

######  Lemma A.10.

$\mathcal{T}:\mathcal{X}\rightarrow\mathcal{X}$ is a linear functional where
$\mathcal{X}$ are normed vector space. If there exists $m>0$ such that

$\|\mathcal{T}x\|\geq m\|x\|\quad\forall x\in\mathcal{X},$ (17)

then $\mathcal{T}$ has a bounded inverse operator $\mathcal{T}^{-1}$.

###### Proof.

If $\mathcal{T}x_{1}=\mathcal{T}x_{2}$, then $\mathcal{T}(x_{1}-x_{2})=0$.
While $0=\|\mathcal{T}(x_{1}-x_{2})\|\geq m\|x_{1}-x_{2}\|$, thus
$x_{1}=x_{2}$. Then $\mathcal{T}$ is a bijection and thus the inverse operator
of $\mathcal{T}$ exists.

For any $y\in\mathcal{X}$, $\mathcal{T}^{-1}y\in\mathcal{X}$. We have that

$\displaystyle\|y\|=\|\mathcal{T}\left(\mathcal{T}^{-1}y\right)\|\geq
m\|\mathcal{T}^{-1}y\|.$ (18)

Thus, we attain that

$\|\mathcal{T}^{-1}y\|\leq\frac{1}{m}\|y\|,\quad\forall y\in\mathcal{X},$ (19)

which shows that $\mathcal{T}^{-1}$ is bounded. ∎

######  Lemma A.11.

$I-\gamma\mathcal{L}^{\pi\circ\nu}$ is invertible and thus we have that

$Q^{\pi\circ\nu}=\left(I-\gamma\mathcal{L}^{\pi\circ\nu}\right)^{-1}r.$ (20)

###### Proof.

Firstly, for all $(s,a)\in\mathcal{S}\times\mathcal{A}$, we have

$\displaystyle\left(\mathcal{L}^{\pi\circ\nu}Q\right)(s,a)$
$\displaystyle=\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a),a^{\prime}\sim\pi\left(\cdot|{\nu\left(s^{\prime}\right)}\right)}Q(s^{\prime},a^{\prime})$
(21)
$\displaystyle\leq\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a),a^{\prime}\sim\pi\left(\cdot|{\nu\left(s^{\prime}\right)}\right)}\left\|Q\right\|_{L^{\infty}\left(\mathcal{S}\times\mathcal{A}\right)}$
(22)
$\displaystyle=\left\|Q\right\|_{L^{\infty}\left(\mathcal{S}\times\mathcal{A}\right)}$
(23)

Thus, we have that

$\left\|\mathcal{L}^{\pi\circ\nu}Q\right\|_{L^{\infty}\left(\mathcal{S}\times\mathcal{A}\right)}\leq\left\|Q\right\|_{L^{\infty}\left(\mathcal{S}\times\mathcal{A}\right)}.$
(24)

For any $Q\in L^{p}\left(\mathcal{S}\times\mathcal{A}\right)$, we have

$\displaystyle\left\|\left(I-\gamma\mathcal{L}^{\pi\circ\nu}\right)Q\right\|_{L^{\infty}\left(\mathcal{S}\times\mathcal{A}\right)}$
$\displaystyle=\left\|Q-\gamma\mathcal{L}^{\pi\circ\nu}Q\right\|_{L^{\infty}\left(\mathcal{S}\times\mathcal{A}\right)}$
(25)
$\displaystyle\geq\left\|Q\right\|_{L^{\infty}\left(\mathcal{S}\times\mathcal{A}\right)}-\gamma\left\|\mathcal{L}^{\pi\circ\nu}Q\right\|_{L^{\infty}\left(\mathcal{S}\times\mathcal{A}\right)}$
(26)
$\displaystyle\geq\left\|Q\right\|_{L^{\infty}\left(\mathcal{S}\times\mathcal{A}\right)}-\gamma\left\|Q\right\|_{L^{\infty}\left(\mathcal{S}\times\mathcal{A}\right)}$
(27)
$\displaystyle=\left(1-\gamma\right)\left\|Q\right\|_{L^{\infty}\left(\mathcal{S}\times\mathcal{A}\right)},$
(28)

where the first inequality comes from the triangle inequality and the second
inequality comes from (24). Then, according to lemma A.10, we attain that
$I-\gamma\mathcal{L}^{\pi\circ\nu}$ is invertible. ∎

######  Lemma A.12.

If $Q>0$ for all $(s,a)\in\mathcal{S}\times\mathcal{A}$, then we have that
$\left(I-\gamma\mathcal{L}^{\pi\circ\nu}\right)^{-1}Q>0$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$.

###### Proof.

At first, we have

$\displaystyle\quad\left(I-\gamma\mathcal{L}^{\pi\circ\nu}\right)\left(\sum_{t=0}^{\infty}\gamma^{t}\left(\mathcal{L}^{\pi\circ\nu}\right)^{t}\right)$
(29)
$\displaystyle=\sum_{t=0}^{\infty}\gamma^{t}\left(\mathcal{L}^{\pi\circ\nu}\right)^{t}-\sum_{t=1}^{\infty}\gamma^{t}\left(\mathcal{L}^{\pi\circ\nu}\right)^{t}$
(30) $\displaystyle=I.$ (31)

Thus, we get that

$\left(I-\gamma\mathcal{L}^{\pi\circ\nu}\right)^{-1}=\sum_{t=0}^{\infty}\gamma^{t}\left(\mathcal{L}^{\pi\circ\nu}\right)^{t}.$
(32)

If $Q(s,a)>0$ for all $(s,a)\in\mathcal{S}\times\mathcal{A}$, then for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$, we have

$\left(\mathcal{L}^{\pi\circ\nu}Q\right)(s,a)=\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a),a^{\prime}\sim\pi\left(\cdot|{\nu\left(s^{\prime}\right)}\right)}Q(s^{\prime},a^{\prime})\geq
0.$ (33)

Further, we have that
$\left(\left(\mathcal{L}^{\pi\circ\nu}\right)^{k}Q\right)(s,a)>0$ for all
$k\in\mathbb{N}$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$. Thus, we have

$\displaystyle\quad\left(I-\gamma\mathcal{L}^{\pi\circ\nu}\right)^{-1}Q(s,a)$
(34)
$\displaystyle=\sum_{t=0}^{\infty}\gamma^{t}\left(\left(\mathcal{L}^{\pi\circ\nu}\right)^{t}Q\right)(s,a)$
(35) $\displaystyle>0.$ (36)

∎

######  Theorem A.13.

If the optimal adversarial action-value function under the strongest adversary
$Q_{0}(s,a):=\max_{\pi}\min_{\nu}Q^{\pi\circ\nu}(s,a)$ exists for all
$s\in\mathcal{S}$ and $a\in\mathcal{A}$, then it is the fixed point of CAR
operator.

###### Proof.

Denote $V_{0}(s)=\max_{\pi}\min_{\nu}V^{\pi\circ\nu}(s)$. For all
$s\in\mathcal{S}$ and $a\in\mathcal{A}$, we have

$\displaystyle Q_{0}(s,a)$
$\displaystyle=\max_{\pi}\min_{\nu}Q^{\pi\circ\nu}(s,a)$ (37)
$\displaystyle=r(s,a)+\gamma\max_{\pi}\min_{\nu}\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}V^{\pi\circ\nu}(s^{\prime})$
(38)
$\displaystyle=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}V_{0}(s^{\prime})$
(39)
$\displaystyle=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\min_{\nu(s)\in
B_{\epsilon}(s)}\max_{\pi}\mathbb{E}_{a\sim\pi\left(\cdot|{\nu\left(s\right)}\right)}Q_{0}(s,a)$
(40)
$\displaystyle=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[\min_{s^{\prime}_{\nu}\in
B_{\epsilon}(s^{\prime})}Q_{0}\left(s^{\prime},\mathop{\arg\max}_{a_{s^{\prime}_{\nu}}}Q_{0}\left(s^{\prime}_{\nu},a_{s^{\prime}_{\nu}}\right)\right)\right]$
(41) $\displaystyle=\left(\mathcal{T}_{car}Q\right)(s,a),$ (42)

where the fourth equation comes from lemma (A.8). This completes the proof. ∎

######  Theorem A.14.

If the consistency assumption holds, then $Q^{*}$ is the fixed point of the
CAR operator. Further, $Q^{*}$ is the optimal adversarial action-value
function under the strongest adversary, i.e.
$Q^{*}(s,a)=\max_{\pi}\min_{\nu}Q^{\pi\circ\nu}(s,a)$, for all
$s\in\mathcal{S}$ and $a\in\mathcal{A}$.

###### Proof.

$\displaystyle\left(\mathcal{T}_{car}Q^{*}\right)(s,a)$
$\displaystyle=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[\min_{s^{\prime}_{\nu}\in
B^{*}_{\epsilon}(s^{\prime})}Q^{*}\left(s^{\prime},\mathop{\arg\max}_{a_{s^{\prime}_{\nu}}}Q^{*}\left(s^{\prime}_{\nu},a_{s^{\prime}_{\nu}}\right)\right)\right]$
(43)
$\displaystyle=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[\min_{s^{\prime}_{\nu}\in
B^{*}_{\epsilon}(s^{\prime})}\max_{a^{\prime}}Q^{*}\left(s^{\prime},a^{\prime}\right)\right]$
(44)
$\displaystyle=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[\max_{a^{\prime}}Q^{*}\left(s^{\prime},a^{\prime}\right)\right]$
(45) $\displaystyle=Q^{*}(s,a),$ (46)

where the second equality utilizes the definition of
$B^{*}_{\epsilon}(s^{\prime})$. Thus, $Q^{*}$ is a fixed point of the CAR
operator.

Define $\pi$ and $\nu$ as the following:

$\displaystyle\pi(s)$ $\displaystyle:=\mathop{\arg\max}_{a}Q^{*}(s,a),$ (47)
$\displaystyle\nu(s)$ $\displaystyle:=\mathop{\arg\min}_{s_{\nu}\in
B_{\epsilon}(s)}Q^{*}\left(s,\mathop{\arg\max}_{a_{s_{\nu}}}Q^{*}\left(s_{\nu},a_{s_{\nu}}\right)\right).$
(48)

Then, we have

$\displaystyle\left(\mathcal{T}_{car}Q^{*}\right)(s,a)$
$\displaystyle=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[\min_{s^{\prime}_{\nu}\in
B_{\epsilon}(s^{\prime})}Q^{*}\left(s^{\prime},\mathop{\arg\max}_{a_{s^{\prime}_{\nu}}}Q^{*}\left(s^{\prime}_{\nu},a_{s^{\prime}_{\nu}}\right)\right)\right]$
(49)
$\displaystyle=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[Q^{*}\left(s^{\prime},\mathop{\arg\max}_{a_{\nu(s^{\prime})}}Q^{*}\left(\nu(s^{\prime}),a_{\nu(s^{\prime})}\right)\right)\right]$
(50)
$\displaystyle=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[Q^{*}\left(s^{\prime},\pi\left(\nu(s^{\prime})\right)\right)\right]$
(51)
$\displaystyle=r(s,a)+\gamma\left(\mathcal{L}^{\pi\circ\nu}Q^{*}\right)(s,a).$
(52)

Thus, we have

$Q^{*}=\left(I-\gamma\mathcal{L}^{\pi\circ\nu}\right)^{-1}r=Q^{\pi\circ\nu},$
(53)

where equations comes from lemma A.11. Further, according to the consistency
assumption, we attain $Q^{\pi\circ\nu}(s,a)=Q^{\pi\circ\nu^{*}(\pi)}$. This
shows that $Q^{*}$ is the action-value adversarial function of policy $\pi$
under the strongest adversary $\nu=\nu^{*}(\pi)$.

According to the consistency assumption and the definition of
$B_{\epsilon}^{*}$, we have that

$\pi(\nu(s))=\pi(s),\quad\forall s\in\mathcal{S}.$ (54)

Then, for any stationary policy $\pi^{\prime}$, we have that

$\displaystyle\quad\left[\left(\mathcal{L}^{\pi\circ\nu}-\mathcal{L}^{\pi^{\prime}\circ\nu^{*}(\pi^{\prime})}\right)Q^{\pi\circ\nu}\right](s,a)$
(55)
$\displaystyle=\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[Q^{\pi\circ\nu}\left(s^{\prime},\pi\left(\nu(s^{\prime})\right)\right)-\mathbb{E}_{a^{\prime}\sim\pi^{\prime}\left(\cdot|{\nu^{*}\left(s^{\prime};\pi^{\prime}\right)}\right)}Q^{\pi\circ\nu}(s^{\prime},a^{\prime})\right]$
(56)
$\displaystyle=\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[Q^{\pi\circ\nu}\left(s^{\prime},\pi\left(s^{\prime}\right)\right)-\mathbb{E}_{a^{\prime}\sim\pi^{\prime}\left(\cdot|{\nu^{*}\left(s^{\prime};\pi^{\prime}\right)}\right)}Q^{\pi\circ\nu}(s^{\prime},a^{\prime})\right]$
(57)
$\displaystyle=\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a),a^{\prime}\sim\pi^{\prime}\left(\cdot|{\nu^{*}\left(s^{\prime};\pi^{\prime}\right)}\right)}\left[Q^{\pi\circ\nu}\left(s^{\prime},\pi\left(s^{\prime}\right)\right)-Q^{\pi\circ\nu}(s^{\prime},a^{\prime})\right]$
(58) $\displaystyle\geq 0,$ (59)

where the second equality comes from (54) and the last inequality comes from
(47).

Further, we have that

$\displaystyle Q^{*}-Q^{\pi^{\prime}\circ\nu^{*}(\pi^{\prime})}$
$\displaystyle=Q^{\pi\circ\nu}-Q^{\pi^{\prime}\circ\nu^{*}(\pi^{\prime})}$
(60)
$\displaystyle=Q^{\pi\circ\nu}-\left(I-\gamma\mathcal{L}^{\pi^{\prime}\circ\nu^{*}(\pi^{\prime})}\right)^{-1}r$
(61)
$\displaystyle=Q^{\pi\circ\nu}-\left(I-\gamma\mathcal{L}^{\pi^{\prime}\circ\nu^{*}(\pi^{\prime})}\right)^{-1}\left(I-\gamma\mathcal{L}^{\pi\circ\nu}\right)Q^{\pi\circ\nu}$
(62)
$\displaystyle=\left(I-\gamma\mathcal{L}^{\pi^{\prime}\circ\nu^{*}(\pi^{\prime})}\right)^{-1}\left(\left(I-\gamma\mathcal{L}^{\pi^{\prime}\circ\nu^{*}(\pi^{\prime})}\right)-\left(I-\gamma\mathcal{L}^{\pi\circ\nu}\right)\right)Q^{\pi\circ\nu}$
(63)
$\displaystyle=\gamma\left(I-\gamma\mathcal{L}^{\pi^{\prime}\circ\nu^{*}(\pi^{\prime})}\right)^{-1}\left(\mathcal{L}^{\pi\circ\nu}-\mathcal{L}^{\pi^{\prime}\circ\nu^{*}(\pi^{\prime})}\right)Q^{\pi\circ\nu}$
(64) $\displaystyle\geq 0,$ (65)

where the last inequality comes from (59) and lemma A.12. Thus, we have that
$Q^{\pi\circ\nu}=Q^{*}\geq Q^{\pi^{\prime}\circ\nu^{*}(\pi^{\prime})}$ for all
policy $\pi^{\prime}$ which shows that $\pi$ is the optimal robust policy
under strongest adversary. ∎

######  Corollary A.15.

If the consistency assumption holds, there exists a deterministic and
stationary policy $\pi^{*}$ which satisfies
$V^{\pi^{*}\circ\nu^{*}(\pi^{*})}(s)\geq V^{\pi\circ\nu^{*}(\pi)}(s)$ and
$Q^{\pi^{*}\circ\nu^{*}(\pi^{*})}(s,a)\geq Q^{\pi\circ\nu^{*}(\pi)}(s,a)$ for
all $\pi\in\Pi$, $s\in\mathcal{S}$ and $a\in\mathcal{A}$.

###### Proof.

According to theorem A.14, we have that
$Q^{*}(s,a)=\max_{\pi}\min_{\nu}Q^{\pi\circ\nu}(s,a)$, for all
$s\in\mathcal{S}$ and $a\in\mathcal{A}$. Define $\pi^{*}$ and $\nu^{*}$ as the
following:

$\displaystyle\pi^{*}(s)$ $\displaystyle:=\mathop{\arg\max}_{a}Q^{*}(s,a),$
(66) $\displaystyle\nu^{*}(s)$ $\displaystyle:=\mathop{\arg\min}_{s_{\nu}\in
B_{\epsilon}(s)}Q^{*}\left(s,\mathop{\arg\max}_{a_{s_{\nu}}}Q^{*}\left(s_{\nu},a_{s_{\nu}}\right)\right).$
(67)

Then, we have that

$\displaystyle\left(\mathcal{T}_{car}Q^{*}\right)(s,a)$
$\displaystyle=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[\min_{s^{\prime}_{\nu}\in
B_{\epsilon}(s^{\prime})}Q^{*}\left(s^{\prime},\mathop{\arg\max}_{a_{s^{\prime}_{\nu}}}Q^{*}\left(s^{\prime}_{\nu},a_{s^{\prime}_{\nu}}\right)\right)\right]$
(68)
$\displaystyle=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[Q^{*}\left(s^{\prime},\mathop{\arg\max}_{a_{\nu(s^{\prime})}}Q^{*}\left(\nu^{*}(s^{\prime}),a_{\nu(s^{\prime})}\right)\right)\right]$
(69)
$\displaystyle=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[Q^{*}\left(s^{\prime},\pi^{*}\left(\nu^{*}(s^{\prime})\right)\right)\right]$
(70)
$\displaystyle=r(s,a)+\gamma\left(\mathcal{L}^{\pi^{*}\circ\nu^{*}}Q^{*}\right)(s,a).$
(71)

Thus, we have

$Q^{*}=\left(I-\gamma\mathcal{L}^{\pi\circ\nu}\right)^{-1}r=Q^{\pi^{*}\circ\nu^{*}},$
(72)

where equations comes from lemma A.11. Further, according to the consistency
assumption, we attain
$Q^{\pi^{*}\circ\nu^{*}}(s,a)=Q^{\pi^{*}\circ\nu^{*}(\pi^{*})}$. This shows
that $Q^{*}$ is the action-value adversarial function of policy $\pi^{*}$
under the strongest adversary $\nu*=\nu^{*}(\pi^{*})$. Thus, we have that

$Q^{\pi^{*}\circ\nu^{*}(\pi^{*})}(s,a)\geq
Q^{\pi\circ\nu^{*}(\pi)}(s,a),\quad\forall s\in\mathcal{S},a\in\mathcal{A}.$
(73)

For any policy $\pi$ and $s\in\mathcal{S}$, we have that

$\displaystyle V^{\pi^{*}\circ\nu^{*}(\pi^{*})}(s)$
$\displaystyle=\mathbb{E}_{a\sim\pi^{*}\left(\cdot|{\nu^{*}\left(s;\pi^{*}\right)}\right)}Q^{\pi^{*}\circ\nu^{*}(\pi^{*})}(s,a)$
(74) $\displaystyle=\max_{a}Q^{\pi^{*}\circ\nu^{*}(\pi^{*})}(s,a)$ (75)
$\displaystyle\geq\mathbb{E}_{a\sim\pi\left(\cdot|{\nu^{*}\left(s;\pi\right)}\right)}Q^{\pi^{*}\circ\nu^{*}}(s,a)$
(76)
$\displaystyle\geq\mathbb{E}_{a\sim\pi\left(\cdot|{\nu^{*}\left(s;\pi\right)}\right)}Q^{\pi\circ\nu^{*}(\pi)}(s,a)$
(77) $\displaystyle=V^{\pi\circ\nu^{*}(\pi)}(s),$ (78)

where the first and last equations come from lemma A.7 and the last inequality
comes from (73). ∎

####  A.2.2 Not a Contraction

######  Theorem A.16.

$\mathcal{T}_{car}$ is not a contraction.

###### Proof.

Let $\mathcal{S}=[-1,1]$, $\mathcal{A}=\\{a_{1},a_{2}\\}$, $0<\epsilon\ll 1$
and dynamic transition $\mathbb{P}(\cdot|s,a)$ be a determined function. Let
$n>\max\\{\frac{\delta}{\gamma},2\delta\\}$, $\delta>0$ and

$\displaystyle Q_{1}(s,a_{1})$
$\displaystyle=2n\cdot\mathbbm{1}_{\left\\{s\in\left[-1,0\right)\right\\}}+\left[2n-\frac{2n-2\delta}{\frac{1}{8}\epsilon}s\right]\cdot\mathbbm{1}_{\left\\{s\in\left[0,\frac{1}{8}\epsilon\right)\right\\}}+2\delta\cdot\mathbbm{1}_{\left\\{s\in\left[\frac{1}{8}\epsilon,\frac{3}{8}\epsilon\right)\right\\}}$
(79)
$\displaystyle+\left[2\delta+\frac{n-2\delta}{\frac{1}{8}\epsilon}\left(s-\frac{3\epsilon}{8}\right)\right]\cdot\mathbbm{1}_{\left\\{s\in\left[\frac{3}{8}\epsilon,\frac{1}{2}\epsilon\right)\right\\}}+n\cdot\mathbbm{1}_{\left\\{s\in\left[\frac{1}{2}\epsilon,1\right]\right\\}},$

$\displaystyle Q_{1}(s,a_{2})$
$\displaystyle=n\cdot\mathbbm{1}_{\left\\{s\in\left[-1,0\right)\right\\}}+\left[n-\frac{n-\delta}{\frac{1}{8}\epsilon}s\right]\cdot\mathbbm{1}_{\left\\{s\in\left[0,\frac{1}{8}\epsilon\right)\right\\}}+\delta\cdot\mathbbm{1}_{\left\\{s\in\left[\frac{1}{8}\epsilon,\frac{3}{8}\epsilon\right)\right\\}}$
(80)
$\displaystyle+\left[\delta+\frac{2n-\delta}{\frac{1}{8}\epsilon}\left(s-\frac{3\epsilon}{8}\right)\right]\cdot\mathbbm{1}_{\left\\{s\in\left[\frac{3}{8}\epsilon,\frac{1}{2}\epsilon\right)\right\\}}+2n\cdot\mathbbm{1}_{\left\\{s\in\left[\frac{1}{2}\epsilon,1\right]\right\\}},$

$\displaystyle Q_{2}(s,a_{1})$
$\displaystyle=2n\cdot\mathbbm{1}_{\left\\{s\in\left[-1,0\right)\right\\}}+\left[2n-\frac{2n-\delta}{\frac{1}{8}\epsilon}s\right]\cdot\mathbbm{1}_{\left\\{s\in\left[0,\frac{1}{8}\epsilon\right)\right\\}}+\delta\cdot\mathbbm{1}_{\left\\{s\in\left[\frac{1}{8}\epsilon,\frac{3}{8}\epsilon\right)\right\\}}$
(81)
$\displaystyle+\left[\delta+\frac{n-\delta}{\frac{1}{8}\epsilon}\left(s-\frac{3\epsilon}{8}\right)\right]\cdot\mathbbm{1}_{\left\\{s\in\left[\frac{3}{8}\epsilon,\frac{1}{2}\epsilon\right)\right\\}}+n\cdot\mathbbm{1}_{\left\\{s\in\left[\frac{1}{2}\epsilon,1\right]\right\\}},$

$\displaystyle Q_{2}(s,a_{2})$
$\displaystyle=n\cdot\mathbbm{1}_{\left\\{s\in\left[-1,0\right)\right\\}}+\left[n-\frac{n-2\delta}{\frac{1}{8}\epsilon}s\right]\cdot\mathbbm{1}_{\left\\{s\in\left[0,\frac{1}{8}\epsilon\right)\right\\}}+2\delta\cdot\mathbbm{1}_{\left\\{s\in\left[\frac{1}{8}\epsilon,\frac{3}{8}\epsilon\right)\right\\}}$
(82)
$\displaystyle+\left[2\delta+\frac{2n-2\delta}{\frac{1}{8}\epsilon}\left(s-\frac{3\epsilon}{8}\right)\right]\cdot\mathbbm{1}_{\left\\{s\in\left[\frac{3}{8}\epsilon,\frac{1}{2}\epsilon\right)\right\\}}+2n\cdot\mathbbm{1}_{\left\\{s\in\left[\frac{1}{2}\epsilon,1\right]\right\\}}.$

Then

$\|Q_{1}-Q_{2}\|_{L^{\infty}\left(\mathcal{S}\times\mathcal{A}\right)}=\delta.$
(83)

We have

$\displaystyle\mathcal{T}_{car}Q_{1}(s,a)-\mathcal{T}_{car}Q_{2}(s,a)$
$\displaystyle=\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[\min_{s^{1}_{\nu}\in
B_{\epsilon}(s^{\prime})}Q_{1}\left(s^{\prime},\mathop{\arg\max}_{a_{s^{1}_{\nu}}}Q_{1}\left(s^{1}_{\nu},a_{s^{1}_{\nu}}\right)\right)-\right.$
(84) $\displaystyle\left.\min_{s^{2}_{\nu}\in
B_{\epsilon}(s^{\prime})}Q_{2}\left(s^{\prime},\mathop{\arg\max}_{a_{s^{2}_{\nu}}}Q_{2}\left(s^{2}_{\nu},a_{s^{2}_{\nu}}\right)\right)\right].$

Let $\mathbb{P}(s^{\prime}=-\frac{\epsilon}{2}|s,a)=1$ and
$s^{\prime}=-\frac{\epsilon}{2}$, then

$\displaystyle\min_{s^{1}_{\nu}\in
B_{\epsilon}(s^{\prime})}Q_{1}\left(s^{\prime},\mathop{\arg\max}_{a_{s^{1}_{\nu}}}Q_{1}\left(s^{1}_{\nu},a_{s^{1}_{\nu}}\right)\right)=Q_{1}(s^{\prime},a_{1}),$
(85) $\displaystyle\min_{s^{1}_{\nu}\in
B_{\epsilon}(s^{\prime})}Q_{2}\left(s^{\prime},\mathop{\arg\max}_{a_{s^{2}_{\nu}}}Q_{2}\left(s^{2}_{\nu},a_{s^{2}_{\nu}}\right)\right)=Q_{2}(s^{\prime},a_{2}).$
(86)

Thus

$\displaystyle\mathcal{T}_{car}Q_{1}(s,a)-\mathcal{T}_{car}Q_{2}(s,a)=\gamma\left[Q_{1}(s^{\prime},a_{1})-Q_{2}(s^{\prime},a_{2})\right]=\gamma
n>\delta,$ (87)

which means that

$\displaystyle\|\mathcal{T}_{car}Q_{1}-\mathcal{T}_{car}Q_{2}\|_{L^{\infty}\left(\mathcal{S}\times\mathcal{A}\right)}>\|Q_{1}-Q_{2}\|_{L^{\infty}\left(\mathcal{S}\times\mathcal{A}\right)}.$
(88)

Therefore, $\mathcal{T}_{car}$ is not a contraction. ∎

####  A.2.3 Convergence

In this section, we prove a conclusion for convergence of the fixed point
iterations of the CAR operator under the
$\left(L_{r},L_{\mathbb{P}}\right)$-smooth environment assumption.

######  Definition A.17 (Bukharin et al. (2023)).

Let $\mathcal{S}\subseteq\mathbb{R}^{d}$. We say the environment is
$\left(L_{r},L_{\mathbb{P}}\right)$-smooth, if the reward function
$r:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$, and the transition
dynamics
$\mathbb{P}:\mathcal{S}\times\mathcal{A}\rightarrow\Delta\left(\mathcal{S}\right)$
satisfy

$\left|r(s,a)-r\left(s^{\prime},a\right)\right|\leq
L_{r}\left\|s-s^{\prime}\right\|\text{ and }\left\|\mathbb{P}(\cdot\mid
s,a)-\mathbb{P}\left(\cdot\mid
s^{\prime},a\right)\right\|_{L^{1}\left(\mathcal{S}\right)}\leq
L_{\mathbb{P}}\left\|s-s^{\prime}\right\|,$

for
$\left(s,s^{\prime},a\right)\in\mathcal{S}\times\mathcal{S}\times\mathcal{A}$.
$\|\cdot\|$ denotes a metric on $\mathbb{R}^{d}$.

The definition is motivated by observations that certain natural environments
show smooth reward function and transition dynamics, especially in continuous
control tasks where the transition dynamics come from some physical laws.

The following lemma shows that $\mathcal{T}_{car}^{k}Q$ is uniformly bounded.

######  Lemma A.18.

Suppose $Q$ and $r$ are uniformly bounded, i.e. $\exists\ M_{Q},M_{r}>0$ such
that $\left|Q(s,a)\right|\leq M_{Q},\ \left|r(s,a)\right|\leq M_{r}\ \forall
s\in\mathcal{S},a\in\mathcal{A}$. Then $\mathcal{T}_{car}Q(\cdot,a)$ is
uniformly bounded, i.e.

$\left|\mathcal{T}_{car}Q(s,a)\right|\leq C_{Q},\ \forall
s\in\mathcal{S},a\in\mathcal{A},$ (89)

where $C_{Q}=\max\left\\{M_{Q},\frac{M_{r}}{1-\gamma}\right\\}$. Further, for
any $k\in\mathbb{N}$, $\mathcal{T}_{car}^{k}Q(\cdot,a)$ has the same uniform
bound as $\mathcal{T}_{car}Q(\cdot,a)$, i.e.

$\left|\mathcal{T}_{car}^{k}Q(s,a)\right|\leq C_{Q},\ \forall
s\in\mathcal{S},a\in\mathcal{A}.$ (90)

###### Proof.

$\displaystyle\left|\mathcal{T}_{car}Q(s,a)\right|$
$\displaystyle=\left|r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[\min_{s^{\prime}_{\nu}\in
B_{\epsilon}(s^{\prime})}Q\left(s^{\prime},\mathop{\arg\max}_{a_{s^{\prime}_{\nu}}}Q\left(s^{\prime}_{\nu},a_{s^{\prime}_{\nu}}\right)\right)\right]\right|$
(91)
$\displaystyle\leq\left|r(s,a)\right|+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left|\min_{s^{\prime}_{\nu}\in
B_{\epsilon}(s^{\prime})}Q\left(s^{\prime},\mathop{\arg\max}_{a_{s^{\prime}_{\nu}}}Q\left(s^{\prime}_{\nu},a_{s^{\prime}_{\nu}}\right)\right)\right|$
(92) $\displaystyle\leq M_{r}+\gamma M_{Q}$ (93)
$\displaystyle\leq\max\left\\{M_{Q},\frac{M_{r}}{1-\gamma}\right\\},\qquad\forall
s\in\mathcal{S},a\in\mathcal{A}.$ (94)

Let $C_{Q}=\max\left\\{M_{Q},\frac{M_{r}}{1-\gamma}\right\\}$. Suppose the
inequality (90) holds for $k=n$. Then, for $k=n+1$, we have

$\displaystyle\left|\mathcal{T}_{car}^{n+1}Q(s,a)\right|$
$\displaystyle=\left|r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[\min_{s^{\prime}_{\nu}\in
B_{\epsilon}(s^{\prime})}\mathcal{T}_{car}^{n}Q\left(s^{\prime},\mathop{\arg\max}_{a_{s^{\prime}_{\nu}}}\mathcal{T}_{car}^{n}Q\left(s^{\prime}_{\nu},a_{s^{\prime}_{\nu}}\right)\right)\right]\right|$
(95)
$\displaystyle\leq\left|r(s,a)\right|+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left|\min_{s^{\prime}_{\nu}\in
B_{\epsilon}(s^{\prime})}\mathcal{T}_{car}^{n}Q\left(s^{\prime},\mathop{\arg\max}_{a_{s^{\prime}_{\nu}}}\mathcal{T}_{car}^{n}Q\left(s^{\prime}_{\nu},a_{s^{\prime}_{\nu}}\right)\right)\right|$
(96) $\displaystyle\leq M_{r}+\gamma C_{Q}$ (97)
$\displaystyle\leq(1-\gamma)C_{Q}+\gamma C_{Q}$ (98) $\displaystyle=C_{Q}.$
(99)

By induction, we have $\left|\mathcal{T}_{car}^{k}Q(s,a)\right|\leq C_{Q},\
\forall s\in\mathcal{S},a\in\mathcal{A},k\in\mathbb{N}$. ∎

The following lemma shows that $\mathcal{T}_{car}^{k}Q$ is uniformly Lipschitz
continuous in the $\left(L_{r},L_{\mathbb{P}}\right)$-smooth environment.

######  Lemma A.19.

Suppose the environment is $\left(L_{r},L_{\mathbb{P}}\right)$-smooth and
suppose $Q$ and $r$ are uniformly bounded, i.e. $\exists\ M_{Q},M_{r}>0$ such
that $\left|Q(s,a)\right|\leq M_{Q},\ \left|r(s,a)\right|\leq M_{r}\ \forall
s\in\mathcal{S},a\in\mathcal{A}$. Then $\mathcal{T}_{car}Q(\cdot,a)$ is
Lipschitz continuous, i.e.

$\left|\mathcal{T}_{car}Q(s,a)-\mathcal{T}_{car}Q(s^{\prime},a)\right|\leq
L_{\mathcal{T}_{car}}\|s-s^{\prime}\|,$ (100)

where $L_{\mathcal{T}_{car}}=L_{r}+\gamma C_{Q}L_{\mathbb{P}}$ and
$C_{Q}=\max\left\\{M_{Q},\frac{M_{r}}{1-\gamma}\right\\}$. Further, for any
$k\in\mathbb{N}$, $\mathcal{T}_{car}^{k}Q(\cdot,a)$ is Lipschitz continuous
and has the same Lipschitz constant as $\mathcal{T}_{car}Q(\cdot,a)$, i.e.

$\left|\mathcal{T}_{car}^{k}Q(s,a)-\mathcal{T}_{car}^{k}Q(s^{\prime},a)\right|\leq
L_{\mathcal{T}_{car}}\|s-s^{\prime}\|.$ (101)

###### Proof.

For all $s_{1},s_{2}\in\mathcal{S}$, we have

$\displaystyle\quad\mathcal{T}_{car}Q(s_{1},a)-\mathcal{T}_{car}Q(s_{2},a)$
(102)
$\displaystyle=r(s_{1},a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s_{1},a)}\left[\min_{s^{\prime}_{\nu}\in
B_{\epsilon}(s^{\prime})}Q\left(s^{\prime},\mathop{\arg\max}_{a_{s^{\prime}_{\nu}}}Q\left(s^{\prime}_{\nu},a_{s^{\prime}_{\nu}}\right)\right)\right]$
(103)
$\displaystyle\quad-r(s_{2},a)-\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s_{2},a)}\left[\min_{s^{\prime}_{\nu}\in
B_{\epsilon}(s^{\prime})}Q\left(s^{\prime},\mathop{\arg\max}_{a_{s^{\prime}_{\nu}}}Q\left(s^{\prime}_{\nu},a_{s^{\prime}_{\nu}}\right)\right)\right]$
(104) $\displaystyle=\left(r(s_{1},a)-r(s_{2},a)\right)$ (105)
$\displaystyle\quad+\gamma\int_{s^{\prime}}\left(\mathbb{P}(s^{\prime}|s_{1},a)-\mathbb{P}(s^{\prime}|s_{2},a)\right)\min_{s^{\prime}_{\nu}\in
B_{\epsilon}(s^{\prime})}Q\left(s^{\prime},\mathop{\arg\max}_{a_{s^{\prime}_{\nu}}}Q\left(s^{\prime}_{\nu},a_{s^{\prime}_{\nu}}\right)\right)ds^{\prime}.$
(106)

Then, we have

$\displaystyle\quad\left|\mathcal{T}_{car}Q(s_{1},a)-\mathcal{T}_{car}Q(s_{2},a)\right|$
(107) $\displaystyle\leq\left|\left(r(s_{1},a)-r(s_{2},a)\right)\right|$ (108)
$\displaystyle\quad+\left|\gamma\int_{s^{\prime}}\left(\mathbb{P}(s^{\prime}|s_{1},a)-\mathbb{P}(s^{\prime}|s_{2},a)\right)\min_{s^{\prime}_{\nu}\in
B_{\epsilon}(s^{\prime})}Q\left(s^{\prime},\mathop{\arg\max}_{a_{s^{\prime}_{\nu}}}Q\left(s^{\prime}_{\nu},a_{s^{\prime}_{\nu}}\right)\right)ds^{\prime}\right|$
(109) $\displaystyle\leq L_{r}\|s_{1}-s_{2}\|$ (110)
$\displaystyle\quad+\gamma\int_{s^{\prime}}\left|\mathbb{P}(s^{\prime}|s_{1},a)-\mathbb{P}(s^{\prime}|s_{2},a)\right|\left|\min_{s^{\prime}_{\nu}\in
B_{\epsilon}(s^{\prime})}Q\left(s^{\prime},\mathop{\arg\max}_{a_{s^{\prime}_{\nu}}}Q\left(s^{\prime}_{\nu},a_{s^{\prime}_{\nu}}\right)\right)\right|ds^{\prime}$
(111) $\displaystyle\leq L_{r}\|s_{1}-s_{2}\|+\gamma
C_{Q}\int_{s^{\prime}}\left|\mathbb{P}(s^{\prime}|s_{1},a)-\mathbb{P}(s^{\prime}|s_{2},a)\right|ds^{\prime}$
(112) $\displaystyle\leq L_{r}\|s_{1}-s_{2}\|+\gamma
C_{Q}L_{\mathbb{P}}\|s_{1}-s_{2}\|$ (113) $\displaystyle=\left(L_{r}+\gamma
C_{Q}L_{\mathbb{P}}\right)\|s_{1}-s_{2}\|.$ (114)

The second inequality comes from the Lipschitz property of $r$. The third
inequality comes from the uniform boundedness of $Q$ and the last inequality
utilizes the Lipschitz property of $\mathbb{P}$.

Note that $\mathcal{T}_{car}^{k}$ and $\mathcal{T}_{car}$ have the same
uniform boundedness $C_{Q}$. Then, due to lemma A.18, we can extend the above
proof to $\mathcal{T}_{car}^{k}$. ∎

######  Remark A.20.

Note that if replace the operator $\mathcal{T}_{car}$ in the Lemma A.18 and
Lemma A.19 with Bellman optimality operator $\mathcal{T}_{B}$, these lemmas
still hold.

The following lemma shows that the fixed point iteration has a property close
to contraction.

######  Lemma A.21.

Suppose $Q$ and $r$ are uniformly bounded, i.e. $\exists\ M_{Q},M_{r}>0$ such
that $\left|Q(s,a)\right|\leq M_{Q},\ \left|r(s,a)\right|\leq M_{r}\ \forall
s\in\mathcal{S},a\in\mathcal{A}$. Let $Q^{*}$ denote the Bellman optimality
Q-function. If the consistency assumption holds, we have

$\|\mathcal{T}_{car}Q-\mathcal{T}_{car}Q^{*}\|_{\infty}\leq\gamma\left(\|Q-Q^{*}\|_{\infty}+2\max_{s}\max_{s_{\nu}\in
B^{*}_{\epsilon}(s)}\max_{a}\left|Q\left(s,a\right)-Q\left(s_{\nu},a\right)\right|\right).$
(115)

Further, if $Q(\cdot,a)$ is $L$-Lipschitz continuous with respect to
$s\in\mathcal{S}$, i.e

$\left|Q(s,a)-Q(s^{\prime},a)\right|\leq L\|s-s^{\prime}\|,\quad\forall
s,s^{\prime}\in\mathcal{S},\ a\in\mathcal{A},$ (116)

we have

$\|\mathcal{T}_{car}Q-\mathcal{T}_{car}Q^{*}\|_{\infty}\leq\gamma\|Q-Q^{*}\|_{\infty}+2\gamma
L\epsilon.$ (117)

###### Proof.

Denote
$a_{s^{\prime}_{\nu},Q}^{*}=\mathop{\arg\max}_{a}Q\left(s^{\prime}_{\nu},a\right)$
and $s^{\prime,*}_{\nu}=\arg\min_{s^{\prime}_{\nu}\in
B^{*}_{\epsilon}(s^{\prime})}Q\left(s^{\prime},a_{s^{\prime}_{\nu},Q}^{*}\right)$.
If $\mathcal{T}_{car}Q>\mathcal{T}_{car}Q^{*}$, we have

$\displaystyle\quad\left(\mathcal{T}_{car}Q\right)(s,a)-\left(\mathcal{T}_{car}Q^{*}\right)(s,a)$
(118)
$\displaystyle=\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[\min_{s^{\prime}_{\nu}\in
B^{*}_{\epsilon}(s^{\prime})}Q\left(s^{\prime},a_{s^{\prime}_{\nu},Q}^{*}\right)-\min_{s^{\prime}_{\nu}\in
B^{*}_{\epsilon}(s^{\prime})}Q^{*}\left(s^{\prime},a_{s^{\prime}_{\nu},Q^{*}}^{*}\right)\right]$
(119)
$\displaystyle=\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[Q\left(s^{\prime},a_{s^{\prime,*}_{\nu},Q}^{*}\right)-Q^{*}\left(s^{\prime},a_{s^{\prime},Q^{*}}^{*}\right)\right]$
(120)
$\displaystyle=\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[Q\left(s^{\prime},a_{s^{\prime,*}_{\nu},Q}^{*}\right)-Q^{*}\left(s^{\prime},a_{s^{\prime,*}_{\nu},Q}^{*}\right)+Q^{*}\left(s^{\prime},a_{s^{\prime,*}_{\nu},Q}^{*}\right)-Q^{*}\left(s^{\prime},a_{s^{\prime},Q^{*}}^{*}\right)\right]$
(121)
$\displaystyle\leq\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[Q\left(s^{\prime},a_{s^{\prime,*}_{\nu},Q}^{*}\right)-Q^{*}\left(s^{\prime},a_{s^{\prime,*}_{\nu},Q}^{*}\right)\right]$
(122)
$\displaystyle\leq\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[\max_{a^{\prime}}\left(Q\left(s^{\prime},a^{\prime}\right)-Q^{*}\left(s^{\prime},a^{\prime}\right)\right)\right]$
(123) $\displaystyle\leq\gamma\|Q-Q^{*}\|_{\infty},$ (124)

where the second equality utilize the definition of
$B^{*}_{\epsilon}(s^{\prime})$ and the first inequality comes from the
optimality of $a_{s^{\prime},Q^{*}}^{*}$. If
$\mathcal{T}_{car}Q<\mathcal{T}_{car}Q^{*}$, we have

$\displaystyle\quad\left(\mathcal{T}_{car}Q^{*}\right)(s,a)-\left(\mathcal{T}_{car}Q\right)(s,a)$
(125)
$\displaystyle=\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[\min_{s^{\prime}_{\nu}\in
B^{*}_{\epsilon}(s^{\prime})}Q^{*}\left(s^{\prime},a_{s^{\prime}_{\nu},Q^{*}}^{*}\right)-\min_{s^{\prime}_{\nu}\in
B^{*}_{\epsilon}(s^{\prime})}Q\left(s^{\prime},a_{s^{\prime}_{\nu},Q}^{*}\right)\right]$
(126)
$\displaystyle=\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[Q^{*}\left(s^{\prime},a_{s^{\prime},Q^{*}}^{*}\right)-Q\left(s^{\prime},a_{s^{\prime,*}_{\nu},Q}^{*}\right)\right]$
(127)
$\displaystyle=\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[Q^{*}\left(s^{\prime},a_{s^{\prime},Q^{*}}^{*}\right)-Q\left(s^{\prime},a_{s^{\prime},Q^{*}}^{*}\right)\right]$
(128)
$\displaystyle\quad+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[Q\left(s^{\prime},a_{s^{\prime},Q^{*}}^{*}\right)-Q\left(s^{\prime,*}_{\nu},a_{s^{\prime},Q^{*}}^{*}\right)\right]$
(129)
$\displaystyle\quad+\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[Q\left(s^{\prime,*}_{\nu},a_{s^{\prime},Q^{*}}^{*}\right)-Q\left(s^{\prime},a_{s^{\prime,*}_{\nu},Q}^{*}\right)\right].$
(130)

We will separately analyze the items 128, 129 and 130. Firstly, we can bound
the item 128 with $\|Q-Q^{*}\|_{\infty}$.

$\displaystyle\quad\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[Q^{*}\left(s^{\prime},a_{s^{\prime},Q^{*}}^{*}\right)-Q\left(s^{\prime},a_{s^{\prime},Q^{*}}^{*}\right)\right]$
(131)
$\displaystyle\leq\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[\max_{a^{\prime}}\left(Q\left(s^{\prime},a^{\prime}\right)-Q^{*}\left(s^{\prime},a^{\prime}\right)\right)\right]$
(132) $\displaystyle\leq\|Q-Q^{*}\|_{\infty}.$ (133)

For the item 129, we have

$\displaystyle\quad\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[Q\left(s^{\prime},a_{s^{\prime},Q^{*}}^{*}\right)-Q\left(s^{\prime,*}_{\nu},a_{s^{\prime},Q^{*}}^{*}\right)\right]$
(134)
$\displaystyle\leq\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[\max_{a^{\prime}}\left(Q\left(s^{\prime},a^{\prime}\right)-Q\left(s^{\prime,*}_{\nu},a^{\prime}\right)\right)\right]$
(135)
$\displaystyle\leq\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[\max_{s^{\prime}_{\nu}\in
B^{*}_{\epsilon}(s^{\prime})}\max_{a^{\prime}}\left|Q\left(s^{\prime},a^{\prime}\right)-Q\left(s^{\prime}_{\nu},a^{\prime}\right)\right|\right]$
(136) $\displaystyle\leq\max_{s}\max_{s_{\nu}\in
B^{*}_{\epsilon}(s)}\max_{a}\left|Q\left(s,a\right)-Q\left(s_{\nu},a\right)\right|.$
(137)

Due to
$a_{s^{\prime,*}_{\nu},Q}^{*}=\mathop{\arg\max}_{a}Q\left(s^{\prime,*}_{\nu},a\right)$,
we have $Q\left(s^{\prime,*}_{\nu},a\right)\leq
Q\left(s^{\prime,*}_{\nu},a_{s^{\prime,*}_{\nu},Q}^{*}\right),\ \forall a$.
Then, for the item 130, we have

$\displaystyle\quad\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[Q\left(s^{\prime,*}_{\nu},a_{s^{\prime},Q^{*}}^{*}\right)-Q\left(s^{\prime},a_{s^{\prime,*}_{\nu},Q}^{*}\right)\right]$
(138)
$\displaystyle\leq\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[Q\left(s^{\prime,*}_{\nu},a_{s^{\prime,*}_{\nu},Q}^{*}\right)-Q\left(s^{\prime},a_{s^{\prime,*}_{\nu},Q}^{*}\right)\right]$
(139)
$\displaystyle\leq\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[\max_{a^{\prime}}\left|Q\left(s^{\prime},a^{\prime}\right)-Q\left(s^{\prime,*}_{\nu},a^{\prime}\right)\right|\right]$
(140)
$\displaystyle\leq\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot|s,a)}\left[\max_{s^{\prime}_{\nu}\in
B^{*}_{\epsilon}(s^{\prime})}\max_{a^{\prime}}\left|Q\left(s^{\prime},a^{\prime}\right)-Q\left(s^{\prime}_{\nu},a^{\prime}\right)\right|\right]$
(141) $\displaystyle\leq\max_{s}\max_{s_{\nu}\in
B^{*}_{\epsilon}(s)}\max_{a}\left|Q\left(s,a\right)-Q\left(s_{\nu},a\right)\right|.$
(142)

Thus, we have

$\displaystyle\quad\left(\mathcal{T}_{car}Q^{*}\right)(s,a)-\left(\mathcal{T}_{car}Q\right)(s,a)$
(143)
$\displaystyle\leq\gamma\left(\|Q-Q^{*}\|_{\infty}+2\max_{s}\max_{s_{\nu}\in
B^{*}_{\epsilon}(s)}\max_{a}\left|Q\left(s,a\right)-Q\left(s_{\nu},a\right)\right|\right).$
(144)

In a summary, we get

$\|\mathcal{T}_{car}Q-\mathcal{T}_{car}Q^{*}\|_{\infty}\leq\gamma\left(\|Q-Q^{*}\|_{\infty}+2\max_{s}\max_{s_{\nu}\in
B^{*}_{\epsilon}(s)}\max_{a}\left|Q\left(s,a\right)-Q\left(s_{\nu},a\right)\right|\right).$
(145)

Further, when $Q(\cdot,a)$ is $L$-Lipschitz continuous, i.e

$\left|Q(s,a)-Q(s^{\prime},a)\right|\leq L\|s-s^{\prime}\|,\quad\forall
s,s^{\prime}\in\mathcal{S},\ a\in\mathcal{A},$ (146)

we have

$\displaystyle\quad\max_{s}\max_{s_{\nu}\in
B^{*}_{\epsilon}(s)}\max_{a}\left|Q\left(s,a\right)-Q\left(s_{\nu},a\right)\right|$
(147) $\displaystyle\leq\max_{s}\max_{s_{\nu}\in
B^{*}_{\epsilon}(s)}L\|s-s_{\nu}\|$ (148) $\displaystyle\leq L\epsilon.$ (149)

Then, we have

$\|\mathcal{T}_{car}Q-\mathcal{T}_{car}Q^{*}\|_{\infty}\leq\gamma\left(\|Q-Q^{*}\|_{\infty}+2L\epsilon\right).$
(150)

∎

######  Remark A.22.

We can relax the Lipschitz condition to local lipschitz continuous in the
$B^{*}_{\epsilon}(s)$.

We prove that the fixed point iterations of $\mathcal{T}_{car}$ at least
converge to a sub-optimal solution close to $Q^{*}$ in the
$\left(L_{r},L_{\mathbb{P}}\right)$-smooth environment.

######  Theorem A.23.

Suppose the environment is $\left(L_{r},L_{\mathbb{P}}\right)$-smooth and
suppose $Q_{0}$ and $r$ are uniformly bounded, i.e. $\exists\
M_{Q_{0}},M_{r}>0$ such that $\left|Q_{0}(s,a)\right|\leq M_{Q_{0}},\
\left|r(s,a)\right|\leq M_{r}\ \forall s\in\mathcal{S},a\in\mathcal{A}$. Let
$Q^{*}$ denote the Bellman optimality Q-function and
$Q_{k+1}=\mathcal{T}_{car}Q_{k}=\mathcal{T}_{car}^{k+1}Q_{0}$ for all
$k\in\mathbb{N}$. If the consistency assumption holds, we have

$\|Q_{k+1}-Q^{*}\|_{\infty}\leq\gamma^{k+1}\|Q_{0}-Q^{*}\|_{\infty}+\gamma^{k+1}D_{Q_{0}}+\frac{2\gamma\epsilon}{1-\gamma}L_{\mathcal{T}_{car}},$
(151)

where $D_{Q_{0}}=2\max_{s}\max_{s_{\nu}\in
B^{*}_{\epsilon}(s)}\max_{a}\left|Q_{0}\left(s,a\right)-Q_{0}\left(s_{\nu},a\right)\right|$,
$L_{\mathcal{T}_{car}}=L_{r}+\gamma C_{Q_{0}}L_{\mathbb{P}}$ and
$C_{Q_{0}}=\max\left\\{M_{Q_{0}},\frac{M_{r}}{1-\gamma}\right\\}$.

###### Proof.

For any $k\in\mathbb{N}$, we have

$\displaystyle\quad\|Q_{k+1}-Q^{*}\|_{\infty}$ (152)
$\displaystyle=\|\mathcal{T}_{car}^{k+1}Q_{0}-\mathcal{T}_{car}^{k+1}Q^{*}\|_{\infty}$
(153)
$\displaystyle\leq\gamma\|\mathcal{T}_{car}^{k}Q_{0}-\mathcal{T}_{car}^{k}Q^{*}\|_{\infty}+2\gamma
L_{\mathcal{T}_{car}}\epsilon$ (154)
$\displaystyle\leq\gamma\left(\gamma\|\mathcal{T}_{car}^{k-1}Q_{0}-\mathcal{T}_{car}^{k-1}Q^{*}\|_{\infty}+2\gamma
L_{\mathcal{T}_{car}}\epsilon\right)+2\gamma L_{\mathcal{T}_{car}}\epsilon$
(155)
$\displaystyle=\gamma^{2}\|\mathcal{T}_{car}^{k-1}Q_{0}-\mathcal{T}_{car}^{k-1}Q^{*}\|_{\infty}+2\epsilon
L_{\mathcal{T}_{car}}\sum_{l=1}^{2}\gamma^{l}$ (156) $\displaystyle\leq\cdots$
(157)
$\displaystyle\leq\gamma^{k}\|\mathcal{T}_{car}Q_{0}-\mathcal{T}_{car}Q^{*}\|_{\infty}+2\epsilon
L_{\mathcal{T}_{car}}\sum_{l=1}^{k}\gamma^{l}$ (158)
$\displaystyle\leq\gamma^{k+1}\|Q_{0}-Q^{*}\|_{\infty}+2\gamma^{k+1}\max_{s}\max_{s_{\nu}\in
B^{*}_{\epsilon}(s)}\max_{a}\left|Q_{0}\left(s,a\right)-Q_{0}\left(s_{\nu},a\right)\right|+2\epsilon
L_{\mathcal{T}_{car}}\sum_{l=1}^{k}\gamma^{l}$ (159)
$\displaystyle\leq\gamma^{k+1}\|Q_{0}-Q^{*}\|_{\infty}+2\gamma^{k+1}\max_{s}\max_{s_{\nu}\in
B^{*}_{\epsilon}(s)}\max_{a}\left|Q_{0}\left(s,a\right)-Q_{0}\left(s_{\nu},a\right)\right|+\frac{2\gamma\epsilon}{1-\gamma}L_{\mathcal{T}_{car}}.$
(160)

The first and second inequalities come from Lemma A.19 and Lemma A.21. The
penultimate inequality comes from Lemma A.21. ∎

##  Appendix B Theorems and Proofs of Policy Robustness under Bellman p-error

Banach Space is a complete normed space $\left(X,\|\cdot\|\right)$, consisting
of a vector space $X$ together with a norm
$\|\cdot\|:X\rightarrow\mathbb{R}^{+}$. In this paper, we consider the setting
where the continuous state space $\mathcal{S}\subset\mathbb{R}^{d}$ is a
compact set and the action space $\mathcal{A}$ is a finite set. We discuss in
the Banach space
$\left(L^{p}\left(\mathcal{S}\times\mathcal{A}\right),\|\cdot\|_{p}\right),\
1\leq p\leq\infty$. Define
$L^{p}\left(\mathcal{S}\times\mathcal{A}\right)=\left\\{f|\|f\|_{p}<\infty\right\\}$,
where
$\|f\|_{p}=\left(\int_{\mathcal{S}}\sum_{a\in\mathcal{A}}\left|f(s,a)\right|^{p}d\mu(s)\right)^{\frac{1}{p}}$
for $\ 1\leq p<\infty$, $\mu$ is the measure over $\mathcal{S}$ and
$\|f\|_{\infty}=\inf\left\\{M\in\mathbb{R}_{\geq 0}|\left|f(s,a)\right|\leq
M\text{ for almost every }(s,a)\right\\}$. For simplicity, we refer to this
Banach space as $L^{p}\left(\mathcal{S}\times\mathcal{A}\right)$.

###  B.1 $L^{\infty}$ is Necessary for Adversarial Robustness

######  Theorem B.1.

There exists an MDP instance $\mathcal{M}$ such that the following statements
hold. Given a function $Q$ and adversary perturbation size $\epsilon$, let
$\mathcal{S}^{Q}_{sub}$ denote the set of states where the greedy policy
according to $Q$ is suboptimal, i.e.
$\mathcal{S}^{Q}_{sub}=\left\\{s|Q^{*}(s,\mathop{\arg\max}_{a}Q(s,a))<\max_{a}Q^{*}(s,a)\right\\}$
and let $\mathcal{S}^{Q}_{adv}$ denote the set of states in whose
$\epsilon$-neighbourhood there exists the adversarial state, i.e.
$\mathcal{S}^{Q}_{adv}=\left\\{s|\exists s_{\nu}\in B_{\epsilon}(s),\
\text{s.t.
}Q^{*}(s,\mathop{\arg\max}_{a}Q(s_{\nu},a))<\max_{a}Q^{*}(s,a)\right\\}$,
where $Q^{*}$ is the Bellman optimal $Q$-function.

  * •

For any $1\leq p<\infty$ and $\delta>0$, there exists a function $Q\in
L^{p}\left(\mathcal{S}\times\mathcal{A}\right)$ satisfying
$\|Q-Q^{*}\|_{L^{p}\left(\mathcal{S}\times\mathcal{A}\right)}\leq\delta$ such
that $\mu\left(\mathcal{S}^{Q}_{sub}\right)=O(\delta)$ yet
$\mu\left(\mathcal{S}^{Q}_{adv}\right)=\mu\left(\mathcal{S}\right)$.

  * •

There exists a $\bar{\delta}>0$ such that for any $0<\delta\leq\bar{\delta}$,
for any function $Q\in L^{\infty}\left(\mathcal{S}\times\mathcal{A}\right)$
satisfying
$\|Q-Q^{*}\|_{L^{\infty}\left(\mathcal{S}\times\mathcal{A}\right)}\leq\delta$,
we have that $\mu\left(\mathcal{S}^{Q}_{sub}\right)=O(\delta)$ and
$\mu\left(\mathcal{S}^{Q}_{adv}\right)=2\epsilon+O\left(\delta\right)$.

###### Proof.

Given a MDP instance $\mathcal{M}$ such that $\mathcal{S}=[-1,1]$,
$\mathcal{A}=\\{a_{1},a_{2}\\}$ and

$\mathbb{P}(s^{\prime}|s,a_{1})=\left\\{\begin{aligned}
\mathbbm{1}_{\left\\{s^{\prime}=s-\epsilon_{1}\right\\}},&\quad
s\in[-1+\epsilon_{1},1]\\\ \mathbbm{1}_{\left\\{s^{\prime}=-1\right\\}},&\quad
s\in[-1,-1+\epsilon_{1})\end{aligned}\right.$ (161)
$\mathbb{P}(s^{\prime}|s,a_{2})=\left\\{\begin{aligned}
\mathbbm{1}_{\left\\{s^{\prime}=s+\epsilon_{1}\right\\}},&\quad
s\in[-1,1-\epsilon_{1}]\\\ \mathbbm{1}_{\left\\{s^{\prime}=1\right\\}},&\quad
s\in(1-\epsilon_{1},1]\end{aligned}\right.$ (162) $\displaystyle r(s,a_{1})$
$\displaystyle=-ks,$ (163) $\displaystyle r(s,a_{2})$ $\displaystyle=ks.$

where $\mathbb{P}$ is the transition dynamic, $r$ is the reward function,
$k>0$, $0<\epsilon_{1}\ll 1$ and $\mathbbm{1}_{\left\\{\cdot\right\\}}$ is the
indicator function. Let $\gamma$ be the discount factor.

First, we prove that equation (164) is the optimal policy.

$\pi^{*}(s)=\arg\max_{a}Q^{*}(s,a)=\left\\{\begin{aligned} \\{a_{2}\\},s>0\\\
\\{a_{1}\\},s<0\\\ \\{a_{1},a_{2}\\},s=0\end{aligned}\right.$ (164)

Define $s_{t}^{\pi}$ is state rollouted by policy $\pi$ in time step $t$.

Let $s_{0}>0$, then

  * •

If $s_{t}^{\pi^{*}}=1$ , while $s_{t}^{\pi}\in[-1,1]$, then
$s_{t}^{\pi^{*}}\geq|s_{t}^{\pi}|$ hold for any policy $\pi$.

  * •

If $s_{t}^{\pi^{*}}<1$ . First we have

$0<s_{t}^{\pi^{*}}=s_{0}+t\epsilon_{1}<1,$ (165) $-1<s_{0}-t\epsilon_{1}.$
(166)

Then for any policy $\pi$, we have the following equation by definition of
transition,

$s_{t}^{\pi}=s_{0}+\sum_{i=1}^{t}x_{i}\epsilon_{1},$ (167)

where $x_{i}\in\\{-1,1\\},i=1,...,t$. Then

$s_{t}^{\pi^{*}}\geq|s_{t}^{\pi}|$ (168)

Then for any policy $\pi$ ,$s_{0}>0$ and $t\geq 0$, we have

$s_{t}^{\pi^{*}}\geq|s_{t}^{\pi}|$ (169)

and

$\displaystyle\quad\pi(a_{2}|s_{t}^{\pi})r(s_{t}^{\pi},a_{2})+\pi(a_{1}|s_{t}^{\pi})r(s_{t}^{\pi},a_{1})$
(170)
$\displaystyle\leq\max\\{\pi(a_{2}|s_{t}^{\pi})(ks_{t}^{\pi})+\pi(a_{1}|s_{t}^{\pi})(-ks_{t}^{\pi}),\pi(a_{2}|s_{t}^{\pi})(-ks_{t}^{\pi})+\pi(a_{1}|s_{t}^{\pi})(ks_{t}^{\pi})\\}$
$\displaystyle=\left|ks_{t}^{\pi}\left(\pi(a_{2}|s_{t}^{\pi})-\pi(a_{1}|s_{t}^{\pi})\right)\right|$
$\displaystyle\leq\left|ks_{t}^{\pi}\right|$ $\displaystyle\leq
ks_{t}^{\pi^{*}}$ $\displaystyle=r(s_{t}^{\pi^{*}},a_{2})$

Let $s_{0}$ be the initial state, $\tau=(s_{0},...)$ be the trajectory of
policy $\pi$. Define
$J(\pi,s_{0})=\mathbb{E}_{\tau}\sum_{t}\gamma^{t}r(s_{t},a_{t})$ is expected
reward in initial state $s_{0}$ about policy $\pi$. Then

$\displaystyle J(\pi^{*},s_{0})-J(\pi,s_{0})$
$\displaystyle=\mathbb{E}_{s_{t}^{\pi^{*}},a_{t}\sim\pi^{*}(\cdot|s_{t}^{\pi^{*}})}\sum_{t}\gamma^{t}r(s_{t}^{\pi^{*}},a_{t})-\mathbb{E}_{s_{t}^{\pi},a_{t}\sim\pi(\cdot|s_{t}^{\pi})}\sum_{t}\gamma^{t}r(s_{t}^{\pi},a_{t})$
(171)
$\displaystyle=\sum_{t}\gamma^{t}r(s_{t}^{\pi^{*}},a_{2})-\sum_{t}\gamma^{t}\mathbb{E}_{s_{t}^{\pi},a_{t}\sim\pi(\cdot|s_{t}^{\pi})}r(s_{t}^{\pi},a_{t})$
(172)
$\displaystyle=\sum_{t}\gamma^{t}r(s_{t}^{\pi^{*}},a_{2})-\sum_{t}\gamma^{t}\mathbb{E}_{s_{t}^{\pi}}\left[\pi(a_{2}|s_{t}^{\pi})r(s_{t}^{\pi},a_{2})+\pi(a_{1}|s_{t}^{\pi})r(s_{t}^{\pi},a_{1})\right]$
(173)
$\displaystyle=\sum_{t}\gamma^{t}\mathbb{E}_{s_{t}^{\pi}}\left[r(s_{t}^{\pi^{*}},a_{2})-\left[\pi(a_{2}|s_{t}^{\pi})r(s_{t}^{\pi},a_{2})+\pi(a_{1}|s_{t}^{\pi})r(s_{t}^{\pi},a_{1})\right]\right]$
(174) $\displaystyle\geq 0.$ (175)

For (172), the policy $\pi^{*}$ and dynamic transition $\mathbb{P}$ are
deterministic. For (175), We use property (170).

Then for $s>0$, we get that the optimal policy is $\pi(\cdot|s)=a_{2}$. By
symmetry, we can also get that the optimal policy is $\pi(\cdot|s)=a_{1}$ for
$s<0$ and $a_{1}$,$a_{2}$ are also optimal action for $s=0$. Thus we have
proved equation (164) is the optimal policy.

First,we have the following equation according to (164)

$\displaystyle Q^{*}(0,a_{2})=Q^{*}(0,a_{1}).$ (176)

For $s>0$, we have

$\displaystyle Q^{*}(s,a_{2})$ $\displaystyle=ks+\gamma
k(s+\epsilon_{1})+\gamma^{2}k(s+2\epsilon_{1})+...+\gamma^{t_{s}}k(s+t_{s}\epsilon_{1})+\sum_{n=1}^{\infty}\gamma^{t_{s}+n}k\times
1$ (177)
$\displaystyle=ks+k\left[\sum_{t=1}^{t_{s}}\gamma^{t}\left(s+t\epsilon_{1}\right)+\sum_{t=t_{s}+1}^{\infty}\gamma^{t}\right].$

where $s+t_{s}\epsilon_{1}\in(1-\epsilon_{1},1]$, i.e.
$t_{s}=\lfloor\frac{1-s}{\epsilon_{1}}\rfloor$.

For $s\geq\epsilon_{1}$, we have

$\displaystyle Q^{*}(s,a_{1})$ $\displaystyle=-ks+\gamma
k(s-\epsilon_{1})+\gamma^{2}ks+\dots+\gamma^{t_{s}+2}k(s+t_{s}\epsilon_{1})+\sum_{n=1}^{\infty}\gamma^{t_{s}+2+n}k\times
1$ (178)
$\displaystyle=-ks+k\left[\sum_{t=1}^{t_{s}+2}\gamma^{t}\left(s+(t-2)\epsilon_{1}\right)+\sum_{t=t_{s}+3}^{\infty}\gamma^{t}\right].$

For $0<s<\epsilon_{1}$, we have

$\displaystyle Q^{*}(s,a_{1})$
$\displaystyle=-ks+\gamma(-k)(s-\epsilon_{1})+\gamma^{2}(-k)(s-2\epsilon_{1})+\dots+\gamma^{q_{s}}(-k)(s-q_{s}\epsilon_{1})+\sum_{n=1}^{\infty}\gamma^{q_{s}+n}(-k)(-1)$
(179)
$\displaystyle=-ks+k\left[\sum_{t=1}^{q_{s}}\gamma^{t}\left(t\epsilon_{1}-s\right)+\sum_{t=q_{s}+1}^{\infty}\gamma^{t}\right].$

where $s-q_{s}\epsilon_{1}\in[-1,-1+\epsilon_{1})$ ,i.e.
$q_{s}=\lfloor\frac{1+s}{\epsilon_{1}}\rfloor>t_{s}$.

According to (177), (178), (179) and $q_{s}>t_{s}$, we have

$Q^{*}(s,a_{2})-Q^{*}(s,a_{1})>2ks,s>0$ (180)

By symmetry, we can also get

$Q^{*}(s,a_{1})-Q^{*}(s,a_{2})>-2ks,s<0$ (181)

(1)First, we have

$0<Q^{*}(s,a)<\sum_{t=0}^{\infty}\gamma^{t}=\frac{1}{1-\gamma}$ (182)

For any $1\leq p<\infty$ , let
$n>\max\left\\{\frac{1}{\epsilon},\left(\frac{1}{1-\gamma}\right)^{p},\delta^{p},\delta^{p-1}\right\\}$
, $n\in\mathbb{N}$ and

$\displaystyle Q(s,a_{2})$
$\displaystyle=\left\\{\begin{array}[]{l}Q^{*}(s,a_{2})-n^{\frac{1}{p}},s\in[\frac{k}{n},\frac{k}{n}+\frac{\delta^{p}}{n^{2}}],k=0,1,\dots,n-1\\\
Q^{*}(s,a_{2}),others\\\ \end{array}\right.$ (185) $\displaystyle Q(s,a_{1})$
$\displaystyle=\left\\{\begin{array}[]{l}Q^{*}(s,a_{1})-n^{\frac{1}{p}},s\in[-\frac{k+1}{n},-\frac{k+1}{n}+\frac{\delta^{p}}{n^{2}}],k=0,1,\dots,n-1\\\
Q^{*}(s,a_{1}),others\\\ \end{array}\right.$ (188)

Then

$\displaystyle\|Q(s,a_{1})-Q^{*}(s,a_{1})\|_{L^{p}\left(\mathcal{S}\right)}=\|Q(s,a_{2})-Q^{*}(s,a_{2})\|_{L^{p}\left(\mathcal{S}\right)}=\left[n*\frac{\delta^{p}}{n^{2}}*\left(n^{\frac{1}{p}}\right)^{p}\right]^{\frac{1}{p}}\leq\delta.$
(189)

And

$\displaystyle\|Q(s,a)\|_{L^{p}\left(\mathcal{S}\right)}$
$\displaystyle=\|Q(s,a)-Q^{*}(s,a)+Q^{*}(s,a)\|_{L^{p}\left(\mathcal{S}\right)}$
(190)
$\displaystyle\leq\|Q(s,a)-Q^{*}(s,a)\|_{L^{p}\left(\mathcal{S}\right)}+\|Q^{*}(s,a)\|_{L^{p}\left(\mathcal{S}\right)}$
(191) $\displaystyle<\infty.$ (192)

which means $Q\in L^{p}\left(\mathcal{S}\times\mathcal{A}\right)$.

We have the following two inequalities because
$n>\left(\frac{1}{1-\gamma}\right)^{p}$ and (182),

$Q^{*}(s,a_{2})-n^{\frac{1}{p}}<Q^{*}(s,a_{1}),$ (193)
$Q^{*}(s,a_{1})-n^{\frac{1}{p}}<Q^{*}(s,a_{2}).$ (194)

Then

$\mathcal{S}^{Q}_{sub}=\bigcup_{k=-n}^{n-1}\left[\frac{k}{n},\frac{k}{n}+\frac{\delta^{p}}{n^{2}}\right]$
(195)

and

$\displaystyle\mu\left(\mathcal{S}^{Q}_{sub}\right)=2n*\frac{\delta^{p}}{n^{2}}<2\delta=O\left(\delta\right)$
(196)

because $n>\delta^{p-1}$.

According to (195), the distance between any two adjacent intervals of
$\mathcal{S}^{Q}_{sub}$ is less than $\epsilon$. For any $s\in\mathcal{S}$,
$\exists k\in\\{-n,-n+1,...,n-1\\}$ s.t. $s\in[\frac{k}{n},\frac{k+1}{n}]$.
Because $n>\frac{1}{\epsilon}$ (i.e. $\frac{1}{n}<\epsilon$), then
$d(s,\frac{k}{n})<\epsilon$ i.e. $d(s,\mathcal{S}^{Q}_{sub})<\epsilon$, where
$d(\cdot,\cdot)$ is Euclid distance. According to the definition of
$\mathcal{S}^{Q}_{adv}$, we have $\mathcal{S}^{Q}_{adv}=\mathcal{S}$ and

$\mu\left(\mathcal{S}^{Q}_{adv}\right)=\mu\left(\mathcal{S}\right).$ (197)

(2)Let $\bar{\delta}\in(0,k]$, for any $0<\delta\leq\bar{\delta}$, for any
state-action value function $Q\in
L^{\infty}\left(\mathcal{S}\times\mathcal{A}\right)$ satisfying
$\|Q-Q^{*}\|_{L^{\infty}\left(\mathcal{S}\times\mathcal{A}\right)}\leq\delta$,
we can get the following two inequalities by (180) and (181).

$Q(s,a_{2})\geq Q^{*}(s,a_{2})-\delta>Q^{*}(s,a_{1})+\delta\geq
Q(s,a_{1}),s\in(\frac{\delta}{k},1],$ (198) $Q(s,a_{1})\geq
Q^{*}(s,a_{1})-\delta>Q^{*}(s,a_{2})+\delta\geq
Q(s,a_{2}),s\in[-1,-\frac{\delta}{k}).$ (199)

Then

$\mu\left(\mathcal{S}^{Q}_{sub}\right)\leq\frac{2\delta}{k}=O\left(\delta\right),$
(200)
$\mu\left(\mathcal{S}^{Q}_{adv}\right)\leq\frac{2\delta}{k}+2\epsilon=2\epsilon+O\left(\delta\right).$
(201)

∎

###  B.2 Stability of Bellman Optimality Equations

We propose the following concept of stability drawing on relevant research in
the field of partial differential equations (Wang et al., 2022).

######  Definition B.2.

Given two Banach spaces $\mathcal{B}_{1}$ and $\mathcal{B}_{2}$, if there
exist $\delta>0$ and $C>0$ such that for all
$Q\in\mathcal{B}_{1}\cap\mathcal{B}_{2}$ satisfying
$\|\mathcal{T}Q-Q\|_{\mathcal{B}_{1}}<\delta$, we have that
$\|Q-Q^{*}\|_{\mathcal{B}_{2}}<C\|\mathcal{T}Q-Q\|_{\mathcal{B}_{1}}$, where
$Q^{*}$ is the exact solution of this functional equation. Then, we say that a
nonlinear functional equation $\mathcal{T}Q=Q$ is
$\left(\mathcal{B}_{1},\mathcal{B}_{2}\right)$-stable.

######  Remark B.3.

This definition indicates that if $\mathcal{T}Q=Q$ is
$\left(\mathcal{B}_{1},\mathcal{B}_{2}\right)$-stable, then
$\|Q-Q^{*}\|_{\mathcal{B}_{2}}=O\left(\|\mathcal{T}Q-Q\|_{\mathcal{B}_{1}}\right)$,
as $\|\mathcal{T}Q-Q\|_{\mathcal{B}_{1}}\longrightarrow 0$, $\forall
Q\in\mathcal{B}_{1}\cap\mathcal{B}_{2}$.

######  Lemma B.4.

For any functions $f,g:\mathcal{X}\rightarrow\mathbb{R}$, we have

$\max_{x\in\mathcal{X}}f(x)-\max_{x\in\mathcal{X}}g(x)\leq\max_{x\in\mathcal{X}}\left(f(x)-g(x)\right).$
(202)

###### Proof.

$\max_{x\in\mathcal{X}}f(x)-\max_{x\in\mathcal{X}}g(x)=f(x_{f}^{*})-\max_{x\in\mathcal{X}}g(x)\leq
f(x_{f}^{*})-g(x_{f}^{*})\leq\max_{x\in\mathcal{X}}\left(f(x)-g(x)\right),$
(203)

where $x_{f}^{*}$ is the maximizer of function $f$, i.e.
$x_{f}^{*}=\arg\max_{x\in\mathcal{X}}f(x)$. ∎

######  Lemma B.5.

For any functions $f,g:\mathcal{X}\rightarrow\mathbb{R}$, we have

$\left|\max_{x\in\mathcal{X}}\left(f+g\right)(x)-\max_{x\in\mathcal{X}}f(x)\right|\leq\max_{x\in\mathcal{X}}\left|g(x)\right|.$
(204)

###### Proof.

If $\max_{x\in\mathcal{X}}\left(f+g\right)(x)\geq\max_{x\in\mathcal{X}}f(x)$,
we have

$\displaystyle\quad\max_{x\in\mathcal{X}}\left(f+g\right)(x)-\max_{x\in\mathcal{X}}f(x)$
(205)
$\displaystyle\leq\max_{x\in\mathcal{X}}f(x)+\max_{x\in\mathcal{X}}g(x)-\max_{x\in\mathcal{X}}f(x)$
(206) $\displaystyle=\max_{x\in\mathcal{X}}g(x)$ (207)
$\displaystyle\leq\max_{x\in\mathcal{X}}\left|g(x)\right|.$ (208)

If $\max_{x\in\mathcal{X}}\left(f+g\right)(x)<\max_{x\in\mathcal{X}}f(x)$, we
have

$\max_{x\in\mathcal{X}}f(x)-\max_{x\in\mathcal{X}}\left(f+g\right)(x)\leq\max_{x\in\mathcal{X}}\left(-g(x)\right)\leq\max_{x\in\mathcal{X}}\left|g(x)\right|,$
(209)

where the first inequality comes from Lemma B.4. ∎

######  Theorem B.6.

For any MDP $\mathcal{M}$, let
$C_{\mathbb{P},p}:=\sup_{(s,a)\in\mathcal{S}\times\mathcal{A}}\left\|\mathbb{P}(\cdot\mid
s,a)\right\|_{L^{\frac{p}{p-1}}\left(\mathcal{S}\right)}$. Assume $p$ and $q$
satisfy the following conditions:

$C_{\mathbb{P},p}<\frac{1}{\gamma};\quad
p\geq\max\left\\{1,\frac{\log\left(\left|\mathcal{A}\right|\right)+\log\left(\mu\left(\mathcal{S}\right)\right)}{\log\frac{1}{\gamma
C_{\mathbb{P},p}}}\right\\};\quad p\leq q\leq\infty.$ (210)

Then, Bellman optimality equation $\mathcal{T}_{B}Q=Q$ is
$\left(L^{q}\left(\mathcal{S}\times\mathcal{A}\right),L^{p}\left(\mathcal{S}\times\mathcal{A}\right)\right)$-stable.

###### Proof.

For any $1\leq p\leq q\leq\infty$ and $Q\in
L^{p}\left(\mathcal{S}\times\mathcal{A}\right)\cap
L^{q}\left(\mathcal{S}\times\mathcal{A}\right)$, denote that

$\displaystyle\mathcal{L}_{0}Q(s,a)$
$\displaystyle:=\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot\mid
s,a)}\left[\max_{a^{\prime}\in\mathcal{A}}Q\left(s^{\prime},a^{\prime}\right)\right],$
(211) $\displaystyle\mathcal{L}Q$
$\displaystyle:=\mathcal{T}_{B}Q-Q=r+\mathcal{L}_{0}Q-Q.$ (212)

Let $Q^{*}$ denote the Bellman optimality Q-function. Note that
$\mathcal{T}_{B}Q^{*}=Q^{*}$ and $\mathcal{L}Q^{*}=0$. Define

$\displaystyle w$ $\displaystyle=w_{Q}:=Q-Q^{*},$ (213) $\displaystyle f$
$\displaystyle=f_{Q}:=\mathcal{L}Q=\mathcal{L}Q-\mathcal{L}Q^{*}.$ (214)

Based on the above notations, we have

$\displaystyle f$ $\displaystyle=\mathcal{L}Q-\mathcal{L}Q^{*}$ (215)
$\displaystyle=\mathcal{L}_{0}Q-Q-\mathcal{L}_{0}Q^{*}+Q^{*}$ (216)
$\displaystyle=\left(\mathcal{L}_{0}Q-\mathcal{L}_{0}Q^{*}\right)-\left(Q-Q^{*}\right)$
(217)
$\displaystyle=-w+\mathcal{L}_{0}\left(Q^{*}+w\right)-\mathcal{L}_{0}Q^{*}.$
(218)

Then, we have

$\displaystyle\left|w(s,a)\right|$
$\displaystyle=\left|-f+\mathcal{L}_{0}\left(Q^{*}+w\right)-\mathcal{L}_{0}Q^{*}\right|\bigg{|}_{(s,a)}$
(219)
$\displaystyle\leq\left|f\right|+\left|\mathcal{L}_{0}\left(Q^{*}+w\right)-\mathcal{L}_{0}Q^{*}\right|\bigg{|}_{(s,a)}.$
(220)

Thus, we obtain

$\displaystyle\left\|w\right\|_{L^{p}\left(\mathcal{S}\times\mathcal{A}\right)}$
$\displaystyle\leq\left\|\left|f\right|+\left|\mathcal{L}_{0}\left(Q^{*}+w\right)-\mathcal{L}_{0}Q^{*}\right|\right\|_{L^{p}\left(\mathcal{S}\times\mathcal{A}\right)}$
(221)
$\displaystyle\leq\left\|f\right\|_{L^{p}\left(\mathcal{S}\times\mathcal{A}\right)}+\left\|\mathcal{L}_{0}\left(Q^{*}+w\right)-\mathcal{L}_{0}Q^{*}\right\|_{L^{p}\left(\mathcal{S}\times\mathcal{A}\right)},$
(222)

where the last inequality comes from the Minkowski’s inequality. In the
following, we analyze the relation between
$\left\|\mathcal{L}_{0}\left(Q^{*}+w\right)-\mathcal{L}_{0}Q^{*}\right\|_{L^{p}\left(\mathcal{S}\times\mathcal{A}\right)}$
and $\left\|w\right\|_{L^{p}\left(\mathcal{S}\times\mathcal{A}\right)}$.

$\displaystyle\quad\left|\mathcal{L}_{0}\left(Q^{*}+w\right)-\mathcal{L}_{0}Q^{*}\right|\bigg{|}_{(s,a)}$
(223)
$\displaystyle=\left|\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot\mid
s,a)}\left[\max_{a^{\prime}\in\mathcal{A}}\left(Q^{*}\left(s^{\prime},a^{\prime}\right)+w\left(s^{\prime},a^{\prime}\right)\right)-\max_{a^{\prime}\in\mathcal{A}}Q^{*}\left(s^{\prime},a^{\prime}\right)\right]\right|$
(224) $\displaystyle\leq\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot\mid
s,a)}\left|\max_{a^{\prime}\in\mathcal{A}}\left(Q^{*}\left(s^{\prime},a^{\prime}\right)+w\left(s^{\prime},a^{\prime}\right)\right)-\max_{a^{\prime}\in\mathcal{A}}Q^{*}\left(s^{\prime},a^{\prime}\right)\right|$
(225) $\displaystyle\leq\gamma\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot\mid
s,a)}\left[\max_{a^{\prime}\in\mathcal{A}}\left|w\left(s^{\prime},a^{\prime}\right)\right|\right]$
(226)
$\displaystyle=\gamma\int_{s^{\prime}}\max_{a^{\prime}\in\mathcal{A}}\left|w\left(s^{\prime},a^{\prime}\right)\right|\mathbb{P}(s^{\prime}\mid
s,a)ds^{\prime}$ (227)
$\displaystyle\leq\gamma\left\|\max_{a\in\mathcal{A}}\left|w\left(s,a\right)\right|\right\|_{L^{p}\left(\mathcal{S}\right)}\left(\int_{s^{\prime}}\left(\mathbb{P}(s^{\prime}\mid
s,a)\right)^{\frac{p}{p-1}}ds^{\prime}\right)^{1-\frac{1}{p}}$ (228)
$\displaystyle=\gamma\left\|\mathbb{P}(\cdot\mid
s,a)\right\|_{L^{\frac{p}{p-1}}\left(\mathcal{S}\right)}\left\|\max_{a\in\mathcal{A}}\left|w\left(s,a\right)\right|\right\|_{L^{p}\left(\mathcal{S}\right)}.$
(229)

where the second inequality comes from Lemma B.5 and the last inequality comes
from the Holder’s inequality. Let
$C_{\mathbb{P},p}:=\sup_{(s,a)\in\mathcal{S}\times\mathcal{A}}\left\|\mathbb{P}(\cdot\mid
s,a)\right\|_{L^{\frac{p}{p-1}}\left(\mathcal{S}\right)}$. Then, we have

$\displaystyle\quad\left\|\mathcal{L}_{0}\left(Q^{*}+w\right)-\mathcal{L}_{0}Q^{*}\right\|_{L^{p}\left(\mathcal{S}\times\mathcal{A}\right)}$
(230)
$\displaystyle\leq\left(\int_{\mathcal{S}\times\mathcal{A}}\left(\gamma\left\|\mathbb{P}(\cdot\mid
s,a)\right\|_{L^{\frac{p}{p-1}}\left(\mathcal{S}\right)}\left\|\max_{a\in\mathcal{A}}\left|w\left(s,a\right)\right|\right\|_{L^{p}\left(\mathcal{S}\right)}\right)^{p}d\mu(s,a)\right)^{\frac{1}{p}}$
(231)
$\displaystyle\leq\left(\int_{\mathcal{S}\times\mathcal{A}}1d\mu(s,a)\right)^{\frac{1}{p}}\gamma
C_{\mathbb{P},p}\left\|\max_{a\in\mathcal{A}}\left|w\left(s,a\right)\right|\right\|_{L^{p}\left(\mathcal{S}\right)}$
(232)
$\displaystyle=\left(\mu\left(\mathcal{S}\times\mathcal{A}\right)\right)^{\frac{1}{p}}\gamma
C_{\mathbb{P},p}\left\|\max_{a\in\mathcal{A}}\left|w\left(s,a\right)\right|\right\|_{L^{p}\left(\mathcal{S}\right)}$
(233) $\displaystyle=\gamma
C_{\mathbb{P},p}\left(\left|\mathcal{A}\right|\mu\left(\mathcal{S}\right)\right)^{\frac{1}{p}}\left\|\max_{a\in\mathcal{A}}\left|w\left(s,a\right)\right|\right\|_{L^{p}\left(\mathcal{S}\right)}$
(234) $\displaystyle\leq\gamma
C_{\mathbb{P},p}\left(\left|\mathcal{A}\right|\mu\left(\mathcal{S}\right)\right)^{\frac{1}{p}}\left\|w\right\|_{L^{p}\left(\mathcal{S}\times\mathcal{A}\right)},$
(235)

where the last inequality comes from
$\left\|w\right\|_{l^{\infty}\left(\mathcal{A}\right)}\leq\left\|w\right\|_{l^{p}\left(\mathcal{A}\right)}$.
Thus, when $C_{\mathbb{P},p}<\frac{1}{\gamma}$ and
$p\geq\frac{\log\left(\left|\mathcal{A}\right|\right)+\log\left(\mu\left(\mathcal{S}\right)\right)}{\log\frac{1}{\gamma
C_{\mathbb{P},p}}}$ and $q\geq p$, we have

$\left\|w\right\|_{L^{p}\left(\mathcal{S}\times\mathcal{A}\right)}\leq\frac{1}{1-\gamma
C_{\mathbb{P},p}\left(\left|\mathcal{A}\right|\mu\left(\mathcal{S}\right)\right)^{\frac{1}{p}}}\left\|f\right\|_{L^{p}\left(\mathcal{S}\times\mathcal{A}\right)}\leq\frac{\left(\left|\mathcal{A}\right|\mu\left(\mathcal{S}\right)\right)^{\frac{1}{p}-\frac{1}{q}}}{1-\gamma
C_{\mathbb{P},p}\left(\left|\mathcal{A}\right|\mu\left(\mathcal{S}\right)\right)^{\frac{1}{p}}}\left\|f\right\|_{L^{q}\left(\mathcal{S}\times\mathcal{A}\right)},$
(236)

where the last inequality comes from
$\left\|f\right\|_{L^{p}\left(\mathcal{S}\times\mathcal{A}\right)}\leq\mu\left(\mathcal{S}\times\mathcal{A}\right)^{\frac{1}{p}-\frac{1}{q}}\left\|f\right\|_{L^{q}\left(\mathcal{S}\times\mathcal{A}\right)}$.
∎

######  Remark B.7.

Note that we have proved a stronger conclusion than stability because the
equation (236) holds for all $Q$ rather than for $Q$ satisfying
$\|\mathcal{T}Q-Q\|_{\mathcal{B}_{1}}\longrightarrow 0$.

######  Remark B.8.

When $\mathbb{P}(\cdot\mid s,a)$ is a probability mass function, then we have
that $C_{\mathbb{P},p}\leq 1<\frac{1}{\gamma}$ holds for all $1<p\leq\infty$.
Generally, note that $\lim_{p\rightarrow\infty}C_{\mathbb{P},p}=1$ and as a
consequence, when $p$ is large enough, $C_{\mathbb{P},p}<\frac{1}{\gamma}$
holds.

###  B.3 Instability of Bellman Optimality Equations

######  Theorem B.9.

There exists a MDP $\mathcal{M}$ such that Bellman optimality equation
$\mathcal{T}_{B}Q=Q$ is not
$\left(L^{p}\left(\mathcal{S}\times\mathcal{A}\right),L^{\infty}\left(\mathcal{S}\times\mathcal{A}\right)\right)$-stable,
for $1\leq p<\infty$.

Generally, we have the following theorem.

######  Theorem B.10.

There exists an MDP $\mathcal{M}$ such that Bellman optimality equation
$\mathcal{T}_{B}Q=Q$ is not
$\left(L^{q}\left(\mathcal{S}\times\mathcal{A}\right),L^{p}\left(\mathcal{S}\times\mathcal{A}\right)\right)$-stable,
for all $1\leq q<p\leq\infty$.

###### Proof.

In order to show a Bellman optimality equation $\mathcal{T}_{B}Q=Q$ is not
$\left(L^{q}\left(\mathcal{S}\times\mathcal{A}\right),L^{p}\left(\mathcal{S}\times\mathcal{A}\right)\right)$-stable,
it is sufficient and necessary to prove $\forall
n\in\mathbb{N},\forall\delta>0,\exists Q(s,a),\text{ such that
}\|\mathcal{T}_{B}Q-Q\|_{L^{q}\left(\mathcal{S}\times\mathcal{A}\right)}<\delta,\text{
but }\|Q-Q^{*}\|_{L^{p}\left(\mathcal{S}\times\mathcal{A}\right)}\geq
n{\|\mathcal{T}_{B}Q-Q\|_{L^{q}\left(\mathcal{S}\times\mathcal{A}\right)}}.$

Define an MDP $\mathcal{M}$ where
$\mathcal{S}=[-1,1],\mathcal{A}=\\{a_{1},a_{2}\\},$

$\mathbb{P}(s^{\prime}|s,a_{1})=\left\\{\begin{aligned}
&\mathbbm{1}_{\left\\{s^{\prime}=s-0.1\right\\}},\quad&&s\in[-0.9,1]\\\
&\mathbbm{1}_{\left\\{s^{\prime}=s\right\\}},&&else\end{aligned}\right.,\quad\mathbb{P}(s^{\prime}|s,a_{2})=\left\\{\begin{aligned}
&\mathbbm{1}_{\left\\{s^{\prime}=s+0.1\right\\}},\quad&&s\in[-1,0.9]\\\
&\mathbbm{1}_{\left\\{s^{\prime}=s\right\\}},&&else\end{aligned}\right.,$

$r(s,a_{i})=k_{i}s,\ k_{2}\geq k_{1}>0$. The transition function is
essentially a deterministic transition dynamic and for convenience, we denote
that

$p(s,a_{1})=\left\\{\begin{aligned} &s-0.1,\quad&&s\in[-0.9,1]\\\
&s,&&else\end{aligned}\right.,\quad p(s,a_{2})=\left\\{\begin{aligned}
&s+0.1,\quad&&s\in[-1,0.9]\\\ &s,&&else\end{aligned}\right..$

Let $Q^{*}(s,a)=Q^{\pi^{*}}(s,a)$ be the optimal Q-function, where $\pi^{*}$
is the optimal policy.

We have $Q^{*}(s,a_{2})\geq Q^{*}(s,a_{1}),\ \forall s\geq 0$. To prove this,
we define $\bar{\pi}(s)\equiv a_{2},\forall s\geq 0$, and thus

$Q^{\bar{\pi}}(s,a_{2})=\sum_{i=0}^{\infty}\gamma^{i}r(s_{i},a_{2}),$ (237)

where $s_{0}=s\geq 0,\ s_{i}=p(s_{i-1},a_{2})\geq 0,\,i\geq 1.$ Consider
Q-function of any policy $\pi$

$Q^{\pi}(s,\alpha_{0})=\sum_{i=0}^{\infty}\gamma^{i}r(\tilde{s}_{i},\pi(\tilde{s}_{i})),$
(238)

where $\pi(\tilde{s}_{0})=\alpha_{0}\in\mathcal{A},\ \tilde{s}_{0}=s\geq 0,\
\tilde{s}_{i+1}=p(\tilde{s}_{i},\pi(\tilde{s}_{i}))$ and
$r(\tilde{s}_{i},\pi(\tilde{s}_{i}))=\pi(a_{1}|\tilde{s}_{i})r(\tilde{s}_{i},a_{1})+\pi(a_{2}|\tilde{s}_{i})r(\tilde{s}_{i},a_{2})$.

We first notice that all $s_{i}$ and $\tilde{s}_{i}$ lie on the grid points
$\mathcal{S}\cap\\{s+0.1z:\,z\in\mathbb{Z}\\}$, actually,
$-\lfloor\frac{1+s}{0.1}\rfloor\leq z\leq\lfloor\frac{1-s}{0.1}\rfloor$. In
the following, we prove $s_{i}\geq\tilde{s}_{i},\ \forall i$. We consider the
recursion method and suppose $s_{i}\geq\tilde{s}_{i}.$ Then, we have the
following two cases. If $s_{i}\leq 0.9$, we obtain

$s_{i+1}=s_{i}+0.1\geq\tilde{s}_{i}+0.1\geq\tilde{s}_{i+1}.$

If $s_{i}>0.9$, it follows from $z\leq\lfloor\frac{1-s}{0.1}\rfloor$ that

$s_{i+1}=s_{i}=s+0.1\lfloor\frac{1-s}{0.1}\rfloor\geq\tilde{s}_{i+1}.$

Thus, we have $s_{i+1}\geq\tilde{s}_{i+1},\ \forall i$. Note that
$s_{0}=\tilde{s}_{0}=s$, and by recursion, it can be obtained that
$s_{i}\geq\tilde{s}_{i}$ holds for all $i$.

Noticing that the reward $r(s,a)$ is an increasing function in terms of $s$
and satisfies $r(s,a_{2})\geq r(s,a_{1}),\forall s\geq 0,$ we have

$r(s_{i},a_{2})\geq r(s_{i},\alpha_{i})\geq
r(\tilde{s}_{i},\alpha_{i}),\quad\forall\alpha_{i}\in\mathcal{A},i=0,1,2,\dots,$

where the second inequality is due to $s_{i}\geq\tilde{s}_{i}$. As a
consequence,

$r(s_{i},a_{2})\geq r(\tilde{s}_{i},\pi(\tilde{s}_{i})),\quad\forall
i=0,1,2,\dots.$ (239)