# Efficient Action Robust Reinforcement Learning with Probabilistic Policy
Execution Uncertainty

Guanlin Liu
University of California, Davis
One Shields Avenue, Davis, CA 95616
<EMAIL_ADDRESS>
&Zhihan Zhou
Northwestern University
633 Clark Street, Evanston, IL 60208
<EMAIL_ADDRESS>
&Han Liu
Northwestern University
633 Clark Street, Evanston, IL 60208
<EMAIL_ADDRESS>
&Lifeng Lai
University of California, Davis
One Shields Avenue, Davis, CA 95616
<EMAIL_ADDRESS>

###### Abstract

Robust reinforcement learning (RL) aims to find a policy that optimizes the
worst-case performance in the face of uncertainties. In this paper, we focus
on action robust RL with the probabilistic policy execution uncertainty, in
which, instead of always carrying out the action specified by the policy, the
agent will take the action specified by the policy with probability $1-\rho$
and an alternative adversarial action with probability $\rho$. We establish
the existence of an optimal policy on the action robust MDPs with
probabilistic policy execution uncertainty and provide the action robust
Bellman optimality equation for its solution. Furthermore, we develop Action
Robust Reinforcement Learning with Certificates (ARRLC) algorithm that
achieves minimax optimal regret and sample complexity. Furthermore, we conduct
numerical experiments to validate our approach’s robustness, demonstrating
that ARRLC outperforms non-robust RL algorithms and converges faster than the
robust TD algorithm in the presence of action perturbations.

##  1 Introduction

Reinforcement learning (RL), a framework of control-theoretic problem that
makes decisions over time under an unknown environment, has many applications
in a variety of scenarios such as recommendation systems [1], autonomous
driving [2], finance [3] and business management [4], to name a few. However,
the solutions to standard RL methods are not inherently robust to
uncertainties, perturbations, or structural changes in the environment, which
are frequently observed in real-world settings. A trustworthy reinforcement
learning algorithm should be competent in solving challenging real-world
problems with robustness against perturbations and uncertainties.

Robust RL aims to improve the worst-case performance of algorithms
deterministically or statistically in the face of uncertainties. The
uncertainties could happen in different MDP components, including
observations/states [5, 6], actions [7, 8], transitions [9, 10], and rewards
[11, 12]. Robust RL against action uncertainties focuses on the discrepancy
between the actions generated by the RL agent and the conducted actions [7].
Thus, action uncertainties can be called as policy execution uncertainties.
Taking the robot control as an example, such policy execution uncertainty may
come from the actuator noise, limited power range, or actuator failures in the
real world. Taking the medication advice in healthcare as another example,
such policy execution uncertainty may come from the patient’s personal
behaviors like drug refusal, forgotten medication, or overdose etc.

Adversarial training [13, 14] has been recognized as one of the most effective
approaches in traditional supervised learning tasks in training time defenses.
A lot of robust RL methods adopt the adversarial training framework and thus
assume an adversary conducting adversarial attacks to mimic the naturalistic
uncertainties [15, 7, 8]. Training with an adversary can naturally be
formulated as a zero-sum game between the adversary and the RL agent [7].

[7] proposed probabilistic action robust MDP (PR-MDP) in which, with
probability $\rho$, an alternative adversarial action is taken. [7] introduced
the Probabilistic Robust Policy Iteration (PR-PI) algorithm to train an
adversary along with the agent. PR-PI algorithm converges toward the optimal
value but requires a MDP solver to solve the optimal adversarial policy when
the agent policy is given and the optimal agent policy when the adversarial
policy is given. Thus, it is not suit for unknown reward functions or unknown
transition probabilities. A similar idea as the PR-MDP was presented [8],
which extends temporal difference (TD) learning algorithms by a new robust
operator and shows that the new algorithms converge to the optimal robust
$Q$-function. However, no theoretical guarantee on sample complexity or regret
is given.

In this paper, we aim to fill in the gaps of the existing work on policy
execution uncertainties. In particular, we develop a minimax optimal sample
efficient algorithm for action robust RL with probabilistic policy execution
uncertainty. Our major contributions are summarized as follows:

  * •

We model the episodic RL with probabilistic policy execution uncertain set. We
provide the action robust Bellman equation and the action robust Bellman
optimality equation. We show that there always exists an optimal robust policy
which is deterministic and can be solved via the induction of the action
robust Bellman optimality equation.

  * •

We develop a new algorithm, Action Robust Reinforcement Learning with
Certificates (ARRLC), for episodic action robust MDPs, and show that it
achieves minimax order optimal regret and minimax order optimal sample
complexity.

  * •

We develop a model-free algorithm for episodic action robust MDPs, and analyze
its regret and sample complexity.

  * •

We conduct numerical experiments to validate the robustness of our approach.
In our experiments, our robust algorithm achieves a much higher reward than
the non-robust RL algorithm when being tested with some action perturbations;
and our ARRLC algorithm converges much faster than the robust TD algorithm in
[8].

##  2 Related work

We mostly focus on papers that are related to sample complexity bounds for the
episodic RL and the two-player zero-sum Markov game, and action robust RL,
that are close related to our model. We remark that there are also related
settings, e.g., infinite-horizon discounted MDP [16, 17], robust RL with other
uncertainties [12, 5, 10], robust offline RL [18, 19], adversarial training
with a generative RL model [20, 21], adversarial attacks on RL [22, 23, 24],
etc. These settings are beyond the scope of this paper, though our techniques
may be also related to these settings.

##### Action robust RL

[15] introduce robust adversarial reinforcement learning to address the
generalization issues in reinforcement learning by training with a
destabilizing adversary that applies disturbance forces to the system. [7]
introduce two new criteria of robustness for reinforcement learning in the
face of action uncertainty. One is probabilistic action robust MDP (PR-MDP) in
which, instead of the action specified by the policy, an alternative
adversarial action is taken with probability $\rho$. Another is noisy action
robust MDP (NR-MDP) criterion, in which a perturbation is added to the
continues action vector itself. They generalize their policy iteration
approach to deep reinforcement learning (DRL) and provide extensive
experiments. [8] extends TD learning algorithms by a new robust operator and
shows that the new algorithms converge to the optimal robust $Q$-function.

##### Sample Complexity Bounds for the Episodic RL

There is a rich literature on sample complexity guarantees for episodic
tabular RL, for example [25, 26, 27, 28, 29, 30, 31, 32, 33, 34]. Most
relevant to our paper is the work about policy certificates [31].The algorithm
outputs policy certificates that bound the sub-optimality and return of the
policy in the next episode. They show that computing certificates can even
improve the sample-efficiency of optimism-based exploration.

##### Sample Complexity Bounds for the Two-player Zero-sum Markov Game

Training with an adversary can naturally be formulated as a zero-sum game
between the adversary and the RL agent. Some sample efficient algorithms for
two-player zero-sum Markov game can be used to train the action robust RL
agent. [35] design an algorithm named optimistic Nash value iteration (Nash-
VI) for two-player zero-sum Markov games that is able to output an
$\epsilon$-approximate Nash policy in
$\widetilde{\mathcal{O}}(SABH^{3}/\delta^{2})$ episodes of game playing. [36]
design a new class of fully decentralized algorithms V-learning, which
provably learns $\epsilon$-approximate Nash equilibrium in
$\widetilde{\mathcal{O}}(SAH^{5}/\delta^{2})$ episodes of two-player zero-sum
game playing. The two multi-agent RL algorithms can be used to solve the
action robust optimal policy but are not minimax optimal. They are a factor of
$A$ or $H^{2}$ above the minimax lower bound.

##  3 Problem formulation

##### Tabular MDPs

We consider a tabular episodic MDP
$\mathcal{M}=(\mathcal{S},\mathcal{A},H,P,R)$, where $\mathcal{S}$ is the
state space with $|\mathcal{S}|=S$, $\mathcal{A}$ is the action space with
$|\mathcal{A}|=A$, $H\in\mathbb{Z}^{+}$ is the number of steps in each
episode, $P$ is the transition matrix so that $P_{h}(\cdot|s,a)$ represents
the probability distribution over states if action $a$ is taken for state $s$
at step $h\in[H]$, and $R_{h}:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$
represents the reward function at the step $h$. In this paper, the probability
transition functions and the reward functions can be different at different
steps.

The agent interacts with the MDP in episodes indexed by $k$. Each episode $k$
is a trajectory
$\\{s_{1}^{k},a_{1}^{k},r_{1}^{k},\cdots,s_{H}^{k},a_{H}^{k},r_{H}^{k}\\}$ of
$H$ states $s_{h}^{k}\in\mathcal{S}$, action $a_{h}^{k}\in\mathcal{A}$, and
reward $r_{h}^{k}\in[0,1]$. At each step $h\in[H]$ of episode $k$, the agent
observes the state $s_{h}^{k}$ and chooses an action $a_{h}^{k}$. After
receiving the action, the environment generates a random reward
$r_{h}^{k}\in[0,1]$ derived from a distribution with mean
$R_{h}(s_{h}^{k},a_{h}^{k})$ and next state $s_{h+1}^{k}$ which is drawn from
the distribution $P_{h}(\cdot|s_{h}^{k},a_{h}^{k})$. For notational
simplicity, we assume that the initial states $s_{1}^{k}=s_{1}$ is
deterministic in different episode $k$.

A (stochastic) Markov policy of the agent is a set of $H$ maps
$\pi:=\\{\pi_{h}:\mathcal{S}\rightarrow\Delta_{\mathcal{A}}\\}_{h\in[H]}$,
where $\Delta_{\mathcal{A}}$ denotes the simplex over $\mathcal{A}$. We use
notation $\pi_{h}(a|s)$ to denote the probability of taking action $a$ in
state $s$ under stochastic policy $\pi$ at step $h$. A deterministic policy is
a policy that maps each state to a particular action. Therefore, when it is
clear from the context, we abuse the notation $\pi_{h}(s)$ for a deterministic
policy $\pi$ to denote the action $a$ which satisfies $\pi_{h}(a|s)=1$.

##### Action Robust MDPs

In the action robust case, the policy execution is not accurate and lies in
some uncertainty set centered on the agent’s policy $\pi$. Denote the actual
behavior policy by $\widetilde{\pi}$ where $\widetilde{\pi}\in\Pi(\pi)$ and
$\Pi(\pi)$ is the uncertainty set of the policy execution. Denote the actual
behavior action at episode $k$ and step $h$ by $\widetilde{a}_{h}^{k}$ where
$\widetilde{a}_{h}^{k}\sim\widetilde{\pi}_{h}^{k}$. Define the action robust
value function of a policy $\pi$ as the worst-case expected accumulated reward
over following any policy in the uncertainty set $\Pi(\pi)$ centered on a
fixed policy $\pi$:

$V^{\pi}_{h}(s)=\min_{\widetilde{\pi}\in\Pi(\pi)}\mathbb{E}\left[\sum_{h^{\prime}=h}^{H}R_{h^{\prime}}(s_{h^{\prime}},a_{h^{\prime}})|s_{h}=s,a_{h^{\prime}}\sim\widetilde{\pi}_{h^{\prime}}(\cdot|s_{h^{\prime}}),~{}\forall
h^{\prime}>h\right].$ (1)

$V^{\pi}_{h}$ represents the action robust value function of policy $\pi$ at
step $h$. Similarly, define the action robust $Q$-function of a policy $\pi$:

$Q^{\pi}_{h}(s,a)=\min_{\widetilde{\pi}\in\Pi(\pi)}\mathbb{E}\left[\sum_{h^{\prime}=h}^{H}R_{h^{\prime}}(s_{h^{\prime}},a_{h^{\prime}})|s_{h}=s,a_{h}=a,a_{h^{\prime}}\sim\widetilde{\pi}_{h^{\prime}}(\cdot|s_{h^{\prime}}),~{}\forall
h^{\prime}>h\right].$ (2)

The goal of action robust RL is to find the optimal robust policy $\pi^{*}$
that maximizes the worst-case accumulated reward:
$\pi^{*}=\operatorname*{arg\,max}_{\pi}V^{\pi}_{1}(s),\forall
s\in\mathcal{S}.$ We also denote $V^{\pi^{*}}$ and $Q^{\pi^{*}}$ by $V^{*}$
and $Q^{*}$.

##### Probabilistic Policy Execution Uncertain Set

We follow the setting of the probabilistic action robust MDP (PR-MDP)
introduced in [7] to construct the probabilistic policy execution uncertain
set. For some $0\leq\rho\leq 1$, the policy execution uncertain set is defined
as:

$\Pi^{\rho}(\pi):=\\{\widetilde{\pi}|\forall s,\forall
h,\widetilde{\pi}_{h}(\cdot|s)=(1-\rho)\pi_{h}(\cdot|s)+\rho\pi^{\prime}_{h}(\cdot|s),\pi^{\prime}_{h}(\cdot|s)\in\Delta_{\mathcal{A}}\\}=\otimes_{h,s}\Pi^{\rho}_{h,s}(\pi_{h}(\cdot|s))$
(3)

such that
$\Pi^{\rho}_{h,s}(\pi_{h}(\cdot|s))=\\{\widetilde{\pi}_{h}(\cdot|s)|\widetilde{\pi}_{h}(\cdot|s)=(1-\rho)\pi_{h}(\cdot|s)+\rho\pi^{\prime}_{h}(\cdot|s),\pi^{\prime}_{h}(\cdot|s)\in\Delta_{\mathcal{A}}\\}$.

In this setting, an optimal probabilistic robust policy is optimal w.r.t. a
scenario in which, with probability at most $\rho$, an adversary takes control
and performs the worst possible action. We call $\pi^{\prime}$ as the
adversarial policy. For different agent’s policy $\pi$, the corresponding
adversarial policy $\pi^{\prime}$ that minimizes the cumulative reward may be
different.

The probabilistic uncertain set model is closely related to the uncertainty
set models defined on the total variation distance. The uncertainty set based
on distance is defined as
$\Pi^{D,\rho}(\pi):=\otimes_{h,s}\Pi^{D,\rho}_{h,s}(\pi_{h}(\cdot|s))$ such
that
$\Pi^{D,\rho}_{h,s}(\pi_{h}(\cdot|s))=\\{\widetilde{\pi}_{h}(\cdot|s)\in\Delta_{\mathcal{A}}|D(\pi_{h}(\cdot|s),\widetilde{\pi}_{h}(\cdot|s))\leq\rho\\}$,
where $D$ is some distance metric between two probability measures and $\rho$
is the radius. For any policy
$\widetilde{\pi}_{h}(\cdot|s)\in\Pi^{\rho}_{h,s}(\pi_{h}(\cdot|s))$, the total
variation distance to the center satisfies
$D_{TV}(\pi_{h}(\cdot|s),\widetilde{\pi}_{h}(\cdot|s))=\frac{1}{2}\lVert\pi_{h}(\cdot|s)-\widetilde{\pi}_{h}(\cdot|s)\rVert_{1}\leq\rho$.

##### Additional Notations

We set $\iota=\log(2SAHK/\delta)$ for $\delta>0$. For simplicity of notation,
we treat $P$ as a linear operator such that
$[{P}_{h}V](s,a):=\mathbbm{E}_{s^{\prime}\sim P_{h}(\cdot|s,a)}V(s^{\prime})$,
and we define two additional operators $\mathbbm{D}$ and $\mathbbm{V}$ as
follows:
$[\mathbbm{D}_{\pi_{h}}Q](s):=\mathbbm{E}_{a\sim\pi_{h}(\cdot|s)}Q(s,a)$ and
$\mathbbm{V}_{{P}_{h}}V_{h+1}(s,a):=\sum_{s^{\prime}}{P}_{h}(s^{\prime}|s,a)\left(V_{h+1}(s^{\prime})-[{P}_{h}V_{h+1}](s,a)\right)^{2}=[{P}_{h}(V_{h+1})^{2}](s,a)-([{P}_{h}V_{h+1}](s,a))^{2}$.

##  4 Existence of the optimal robust policy

For the standard tabular MDPs, when the state space, action space, and the
horizon are all finite, there always exists an optimal policy. In addition, if
the reward functions and the transition probabilities are known to the agent,
the optimal policy can be solved by solving the Bellman optimality equation.
In the following theorem, we show that the optimal policy also always exists
in action robust MDPs and can be solved by the action robust Bellman
optimality equation.

###### Theorem 1

If the uncertainty set of the policy execution has the form in (3), the
following perfect duality holds for all $s\in\mathcal{S}$ and all $h\in[H]$:

$\begin{split}&\max_{\pi}\min_{\widetilde{\pi}\in\Pi^{\rho}(\pi)}\mathbb{E}\left[\sum_{h^{\prime}=h}^{H}R_{h^{\prime}}(s_{h^{\prime}},a_{h^{\prime}})|s_{h}=s,a_{h^{\prime}}\sim\widetilde{\pi}_{h^{\prime}}(\cdot|s_{h^{\prime}})\right]\\\
=&\min_{\widetilde{\pi}\in\Pi^{\rho}(\pi)}\max_{\pi}\mathbb{E}\left[\sum_{h^{\prime}=h}^{H}R_{h^{\prime}}(s_{h^{\prime}},a_{h^{\prime}})|s_{h}=s,a_{h^{\prime}}\sim\widetilde{\pi}_{h^{\prime}}(\cdot|s_{h^{\prime}})\right].\end{split}$
(4)

There always exists a deterministic optimal robust policy $\pi^{*}$. The
problem can be solved via the induction of the action robust Bellman
optimality equation on $h=H,\cdots,1$. The action robust Bellman equation and
the action robust Bellman optimality equation are:

$\begin{split}\left\\{\begin{aligned}
&V^{\pi}_{h}(s)=(1-\rho)[\mathbbm{D}_{\pi_{h}}Q^{\pi}_{h}](s)+\rho\min_{a\in\mathcal{A}}Q^{\pi}_{h}(s,a)~{}\\\
&Q^{\pi}_{h}(s,a)=R_{h}(s,a)+[{P}_{h}V_{h+1}^{\pi}](s,a)\\\
&V^{\pi}_{H+1}(s)=0,~{}\forall s\in\mathcal{S}\end{aligned}\right.\end{split}$
(5) $\begin{split}\left\\{\begin{aligned}
&V^{*}_{h}(s)=(1-\rho)\max_{a\in\mathcal{A}}Q^{*}_{h}(s,a)+\rho\min_{b\in\mathcal{A}}Q^{*}_{h}(s,b)~{}\\\
&Q^{*}_{h}(s,a)=R_{h}(s,a)+[{P}_{h}V_{h+1}^{*}](s,a)\\\
&V^{*}_{H+1}(s)=0,~{}\forall s\in\mathcal{S}\end{aligned}\right..\end{split}$
(6)

Similar result of the perfect duality was show in [7]. They considered a PR-
MDP as a two-player zero-sum Markov game and solving the optimal probabilistic
robust policy can be equivalently viewed as solving the equilibrium value of a
two-player zero-sum Markov game. We define
$C_{h}^{\pi,\pi^{\prime},\rho}(s):=\mathbb{E}\left[\sum_{h^{\prime}=h}^{H}R_{h^{\prime}}(s_{h^{\prime}},a_{h^{\prime}})|s_{h}=s,a_{h^{\prime}}\sim\widetilde{\pi}_{h^{\prime}}(\cdot|s_{h^{\prime}})\right]$.
The perfect duality of the control problems in (4) is equivalent to
$\max_{\pi}\min_{\pi^{\prime}}C_{h}^{\pi,\pi^{\prime},\rho}(s)=\min_{\pi^{\prime}}\max_{\pi}C_{h}^{\pi,\pi^{\prime},\rho}(s)$.
We provide an alternate proof in Appendix A based on the robust Bellman
equation.

##  5 Algorithm and main results

In this section, we introduce the proposed Action Robust Reinforcement
Learning with Certificates (ARRLC) algorithm and provides its theoretical
guarantee. The pseudo code is listed in Algorithm 1. Here, we highlight the
main idea of our algorithm. Algorithm 1 trains the agent in a clean
(simulation) environment and learns a policy that performs well when applied
to a perturbed environment with probabilistic policy execution uncertainty. To
simulate the action perturbation, Algorithm 1 chooses an adversarial action
with probability $\rho$. To learn the agent’s optimal policy and the
corresponding adversarial policy, Algorithm 1 computes an optimistic estimate
$\overline{Q}$ of $Q^{*}$ and a pessimistic estimate $\underline{Q}$ of
$Q^{\overline{\pi}^{k}}$. Algorithm 1 uses the optimistic estimates to explore
the possible optimal policy $\overline{\pi}$ and uses the pessimistic
estimates to explore the possible adversarial policy $\underline{\pi}$. As
shown later in Lemma 2, $\overline{V}\geq V^{*}\geq
V^{\overline{\pi}}\geq\underline{V}$ holds with high probabilities. The
optimistic and pessimistic estimates $\overline{V}$ and $\underline{V}$ can
provide policy certificates, which bounds the cumulative rewards of the return
policy $\overline{\pi}^{k}$ and $\overline{V}-\underline{V}$ bounds the sub-
optimality of the return policy $\overline{\pi}^{k}$ with high probabilities.
The policy certificates can give us some insights about the performance of
$\overline{\pi}^{k}$ in the perturbed environment with probabilistic policy
execution uncertainty.

###  5.1 Algorithm description

We now describe the proposed ARRLC algorithm in more details. In each episode,
the ARRLC algorithm can be decomposed into two parts.

  * •

Line 3-11 (Sample trajectory and update the model estimate): Simulates the
action robust MDP, executes the behavior policy $\widetilde{\pi}$, collects
samples, and updates the estimate of the reward and the transition.

  * •

Line 16-25 (Adversarial planning from the estimated model): Performs value
iteration with bonus to estimate the robust value functions using the
empirical estimate of the transition $\hat{P}$, computes a new policy
$\overline{\pi}$ which is optimal respect to the estimated robust value
functions, and computes a new optimal adversarial policy $\underline{\pi}$
respect to the agent’s policy $\overline{\pi}$.

At a high-level, this two-phase strategy is standard in the majority of model-
based RL algorithms [28, 31]. Algorithm 1 shares similar structure with ORLC
(Optimistic Reinforcement Learning with Certificates) in [31] but has some
significant differences in line 5-6 and line 18-23. The first main difference
is that the ARRLC algorithm simulates the probabilistic policy execution
uncertainty by choosing an adversarial action with probability $\rho$. The
adversarial policy and the adversarial action are computed by the ARRLC
algorithm. The second main difference is that the ARRLC algorithm
simultaneously plans the agent policy $\overline{\pi}$ and the adversarial
policy $\underline{\pi}$ by the action robust Bellman optimality equation.

These two main difference brings two main challenges in the design and
analysis of our algorithm.

(1) The ARRLC algorithm simultaneously plans the agent policy and the
adversarial policy. However the planned adversarial policy $\underline{\pi}$
is not necessarily the true optimal adversary policy towards the agent policy
$\overline{\pi}$ because of the estimation error of the value functions. We
carefully design the bonus items and the update role of the value functions so
that $\overline{V}_{h}(s)\geq V_{h}^{*}(s)\geq
V_{h}^{\overline{\pi}}(s)\geq\underline{V}_{h}(s)$ and
$\overline{Q}_{h}(s,a)\geq Q_{h}^{*}(s,a)\geq
Q_{h}^{\overline{\pi}}(s,a)\geq\underline{Q}_{h}(s,a)$ hold for all $s$ and
$a$.

(2) A crucial step in many UCB-type algorithms based on Bernstein inequality
is bounding the sum of variance of estimated value function across the
planning horizon. The behavior policies in these UCB-type algorithms are
deterministic. However, the behavior policy in our ARRLC algorithm is not
deterministic due to the simulation of the adversary’s behavior. The total
variance is the weighted sum of the sum of variance of estimated value
function across two trajectories. Even if action $\overline{\pi}(s_{h}^{k})$
or $\underline{\pi}(s_{h}^{k})$ is not sampled at state $s_{h}^{k}$, it counts
in the total variance.

1: Initialize $\overline{V}_{h}(s)=H-h+1$, $\overline{Q}_{h}(s,a)=H-h+1$,
$\underline{V}_{h}(s)=0$, $\underline{Q}_{h}(s,a)=0$, $\hat{r}_{h}(s,a)$,
$N_{h}(s,a)=0$ and $N_{h}(s,a,s^{\prime})=0$ for all state $s\in\mathcal{S}$,
all action $a\in\mathcal{A}$ and all step $h\in[H]$.
$\overline{V}_{H+1}(s)=\underline{V}_{H+1}(s)=0$ and
$\overline{Q}_{H+1}(s,a)=\underline{Q}_{H+1}(s,a)=0$ for all $s$ and $a$.
$\Delta=H$.

2: for episode $k=1,2,\dots,K$ do

3: for step $h=1,2,\dots,H$ do

4: Observe $s_{h}^{k}$.

5: Set
$\overline{\pi}_{h}^{k}(s)=\operatorname*{arg\,max}_{a}\overline{Q}_{h}(s,a)$
,
$\underline{\pi}_{h}^{k}(s)=\operatorname*{arg\,min}_{a}\underline{Q}_{h}(s,a)$,
$\widetilde{\pi}_{h}^{k}=(1-\rho)\overline{\pi}_{h}^{k}+\rho\underline{\pi}_{h}^{k}$.

6: Take action $a_{h}^{k}\sim\widetilde{\pi}_{h}^{k}(\cdot|s_{h}^{k})$.

7: Receive reward $r_{h}^{k}$ and observe $s_{h+1}^{k}$.

8: Set $N_{h}(s_{h}^{k},a_{h}^{k})\leftarrow N_{h}(s_{h}^{k},a_{h}^{k})+1$,
$N_{h}(s_{h}^{k},a_{h}^{k},s_{h+1}^{k})\leftarrow
N_{h}(s_{h}^{k},a_{h}^{k},s_{h+1}^{k})+1$.

9: Set
$\hat{r}_{h}^{k}(s_{h}^{k},a_{h}^{k})\leftarrow\hat{r}_{h}^{k}(s_{h}^{k},a_{h}^{k})+(r_{h}^{k}-\hat{r}_{h}^{k}(s_{h}^{k},a_{h}^{k}))/N_{h}(s_{h}^{k},a_{h}^{k})$.

10: Set
$\hat{P}_{h}(\cdot|s_{h}^{k},a_{h}^{k})=N_{h}(s_{h}^{k},a_{h}^{k},\cdot)/N_{h}(s_{h}^{k},a_{h}^{k})$.

11: end for

12: Output policy $\overline{\pi}^{k}$ with certificates
$\mathcal{I}_{k}=[\underline{V}_{1}(s_{1}^{k}),\overline{V}_{1}(s_{1}^{k})]$
and $\epsilon_{k}=|\mathcal{I}_{k}|$ .

13: if $\epsilon_{k}<\Delta$ then

14: $\Delta\leftarrow\epsilon_{k}$ and
$\pi^{out}\leftarrow\overline{\pi}^{k}$.

15: end if

16: for step $h=H,H-1,\dots,1$ do

17: for each $(s,a)\in\mathcal{S}\times\mathcal{A}$ with $N_{h}(s,a)>0$ do

18: Set
$\theta_{h}(s,a)=\sqrt{\frac{2\mathbbm{V}_{\hat{P}_{h}}[(\overline{V}_{h+1}+\underline{V}_{h+1})/2](s,a)\iota}{N_{h}(s,a)}}+\sqrt{\frac{2\hat{r}_{h}(s,a)\iota}{N_{h}(s,a)}}+\frac{\hat{P}_{h}\left(\overline{V}_{h+1}-\underline{V}_{h+1}\right)(s,a)}{H}+\frac{(24H^{2}+7H+7)\iota}{3N_{h}(s,a)}$,

19:
$\overline{Q}_{h}(s,a)\leftarrow\min\\{H-h+1,\hat{r}_{h}(s,a)+\hat{P}_{h}\overline{V}_{h+1}(s,a)+\theta_{h}(s,a)\\}$,

20:
$\underline{Q}_{h}(s,a)\leftarrow\max\\{0,\hat{r}_{h}(s,a)+\hat{P}_{h}\underline{V}_{h+1}(s,a)-\theta_{h}(s,a)\\}$,

21:
$\overline{\pi}_{h}^{k+1}(s)=\operatorname*{arg\,max}_{a}\overline{Q}_{h}(s,a)$
,
$\underline{\pi}_{h}^{k+1}(s)=\operatorname*{arg\,min}_{a}\underline{Q}_{h}(s,a)$,

22:
$\overline{V}_{h}(s)\leftarrow(1-\rho)\overline{Q}_{h}(s,\overline{\pi}_{h}^{k+1}(s))+\rho\overline{Q}_{h}(s,\underline{\pi}_{h}^{k+1}(s))$,

23:
$\underline{V}_{h}(s)\leftarrow(1-\rho)\underline{Q}_{h}(s,\overline{\pi}_{h}^{k+1}(s))+\rho\underline{Q}_{h}(s,\underline{\pi}_{h}^{k+1}(s))$.

24: end for

25: end for

26: end for

27: return $\pi^{out}$

Algorithm 1 ARRLC (Action Robust Reinforcement Learning with Certificates)

###  5.2 Theoretical guarantee

We define the cumulative regret of the output policy $\overline{\pi}^{k}$ at
each episodes $k$ as
$Regret(K):=\sum_{k=1}^{K}(V_{1}^{*}(s_{1}^{k})-{V}_{1}^{\overline{\pi}^{k}}(s_{1}^{k}))$.

###### Theorem 2

For any $\delta\in(0,1]$, letting $\iota=\log(2SAHK/\delta)$, then with
probability at least $1-\delta$, Algorithm 1 achieves:

  * •

$V_{1}^{*}(s_{1})-V_{1}^{\pi^{out}}(s_{1})\leq\epsilon$, if the number of
episodes
$K\geq\Omega(SAH^{3}\iota^{2}/\epsilon^{2}+S^{2}AH^{3}\iota^{2}/\epsilon)$.

  * •

$Regret(K)=\sum_{k=1}^{K}(V_{1}^{*}(s_{1}^{k})-{V}_{1}^{\overline{\pi}^{k}}(s_{1}^{k}))\leq\mathcal{O}(\sqrt{SAH^{3}K}\iota+S^{2}AH^{3}\iota^{2})$.

For small $\epsilon\leq H/S$, the sample complexity scales as
$\mathcal{O}(SAH^{3}\iota^{2}/\epsilon^{2})$. For the case with a large number
of episodes $K\geq S^{3}AH^{3}\iota$, the regret scales as
$\mathcal{O}(\sqrt{SAH^{3}K}\iota)$. For the standard MDPs, the information-
theoretic sample complexity lower bound is $\Omega(SAH^{3}/\epsilon^{2})$
provided in [33] and the regret lower bound is $\Omega(\sqrt{SAH^{3}K})$
provided in [30]. When $\rho=0$, the action robust MDPs is equivalent to the
standard MDPs. Thus, the information-theoretic sample complexity lower bound
and the regret lower bound of the action robust MDPs should have same
dependency on $S$, $A$, $H$, $K$ or $\epsilon$. The lower bounds show the
optimality of our algorithm up to logarithmic factors.

##  6 Proof sketch

In this section, we provide sketch of the proof, which will highlight our the
main ideas of our proof. First, we will show that $\overline{V}_{h}(s)\geq
V_{h}^{*}(s)\geq V_{h}^{\overline{\pi}}(s)\geq\underline{V}_{h}(s)$ hold for
all $s$ and $a$. Then, the regret can be bounded by
$\overline{V}_{1}-\underline{V}_{1}$ and then be divided by four items, each
of which can then be bounded separately. The full proof can be found in the
appendix contained in the supplementary material.

We first introduce a few notations. We use
$\overline{Q}_{h}^{k}$,$\overline{V}_{h}^{k}$,$\underline{Q}_{h}^{k}$,$\underline{V}_{h}^{k}$,
$N_{h}^{k}$, $\hat{P}_{h}^{k}$,$\hat{r}_{h}^{k}$ and $\theta_{h}^{k}$ to
denote the values of
$\overline{Q}_{h}$,$\overline{V}_{h}$,$\underline{Q}_{h}$,$\underline{V}_{h}$,
$\max\\{N_{h},1\\}$, $\hat{P}_{h}$, ${r}_{h}$ and $\theta_{h}$ in the
beginning of the $k$-th episode in Algorithm 1.

###  6.1 Proof of monotonicity

We define $\mathcal{E}^{R}$ to be the event where

$\left|\hat{r}_{h}^{k}(s,a)-R_{h}(s,a)\right|\leq\sqrt{\frac{2\hat{r}_{h}^{k}(s,a)\iota}{N_{h}^{k}(s,a)}}+\frac{7\iota}{3(N_{h}^{k}(s,a))}$
(7)

holds for all $(s,a,h,k)\in S\times A\times[H]\times[K]$. We also define
$\mathcal{E}^{PV}$ to be the event where

$\displaystyle\left|(\hat{P}_{h}^{k}-P_{h})V^{*}_{h+1}(s,a)\right|$
$\displaystyle\leq$
$\displaystyle\sqrt{\frac{2\mathbbm{V}_{\hat{P}_{h}^{k}}V_{h+1}^{*}(s,a)\iota}{N_{h}^{k}(s,a)}}+\frac{7H\iota}{3(N_{h}^{k}(s,a))}$
(8)
$\displaystyle\left|(\hat{P}_{h}^{k}-P_{h})V^{\overline{\pi}^{k}}_{h+1}(s,a)\right|$
$\displaystyle\leq$
$\displaystyle\sqrt{\frac{2\mathbbm{V}_{\hat{P}_{h}^{k}}V_{h+1}^{\overline{\pi}^{k}}(s,a)\iota}{N_{h}^{k}(s,a)}}+\frac{7H\iota}{3N_{h}^{k}(s,a)}$
(9)

holds for all $(s,a,h,k)\in S\times A\times[H]\times[K]$.

Event $\mathcal{E}^{R}$ means that the estimations of all reward functions
stay in certain neighborhood of the true values. Event $\mathcal{E}^{PV}$
represents that the estimation of the value functions at the next step stay in
some intervals. The following lemma shows $\mathcal{E}^{R}$ and
$\mathcal{E}^{PV}$ hold with high probability. The analysis will be done
assuming the successful event $\mathcal{E}^{R}\cap\mathcal{E}^{PV}$ holds in
the rest of this section.

###### Lemma 1

$\mathbbm{P}(\mathcal{E}^{R}\cap\mathcal{E}^{PV})\geq 1-3\delta$.

###### Lemma 2

Conditioned on $\mathcal{E}^{R}\cap\mathcal{E}^{PV}$,
$\overline{V}_{h}^{k}(s)\geq V_{h}^{*}(s)\geq
V_{h}^{\overline{\pi}^{k}}(s)\geq\underline{V}_{h}^{k}(s)$ and
$\overline{Q}_{h}^{k}(s,a)\geq Q_{h}^{*}(s,a)\geq
Q_{h}^{\overline{\pi}^{k}}(s,a)\geq\underline{Q}_{h}^{k}(s,a)$ for all
$(s,a,h,k)\in S\times A\times[H]\times[K]$.

###  6.2 Regret analysis

We decompose the regret and analyze the different terms. Set
$\Theta_{h}^{k}(s,a)=\sqrt{\frac{8\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s,a)\iota}{N_{h}^{k}(s,a)}}+\sqrt{\frac{32}{N_{h}^{k}(s,a)}}+\frac{46\sqrt{SH^{4}\iota}}{N_{h}^{k}(s,a)}$,
where ${\pi}^{k*}$ is the optimal policy towards the adversary policy
$\underline{\pi}^{k}$ with
${\pi}^{k*}_{h}(s)=\operatorname*{arg\,max}_{\pi}{C}^{{\pi},\underline{\pi}^{k},\rho}_{h}(s)$.
We define the cumulative regret of the output policy $\overline{\pi}^{k}$ at
each episodes $k$ as
$Regret(K):=\sum_{k=1}^{K}(V_{1}^{*}(s_{1}^{k})-{V}_{1}^{\overline{\pi}^{k}}(s_{1}^{k}))$.
Let
$M_{1}=\sum_{k=1}^{K}\sum_{h=1}^{H}[\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}\hat{P}_{h}^{k}(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1})(s_{h}^{k})-\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})]$,
$M_{2}=\sum_{k=1}^{K}\sum_{h=1}^{H}\frac{1}{H}[\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}P_{h}(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1})(s_{h}^{k})-{P}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})]$,
$M_{3}=\sum_{k=1}^{K}\sum_{h=1}^{H}({P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})-(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h+1}^{k}))$
and
$M_{4}=\sum_{k=1}^{K}\sum_{h=1}^{H}[\frac{(SH+SH^{2})\iota}{N_{h}^{k}(s_{h}^{k},a_{h}^{k})}+\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}\Theta_{h}^{k}(s_{h}^{k})]$.
Here $M_{1}$ and $M_{2}$ are the cumulative sample error from the random
choices of the adversarial policy or agent’s policy. $M_{3}$ is the cumulative
sample error from the randomness of Monte Carlo sampling of the next state.
$M_{4}$ is the cumulative error from the bonus item $\theta$. Lemma 3 shows
that the regret can be bounded by these four terms.

###### Lemma 3

With probability at least $1-(S+5)\delta$,

$Regret(K)\leq\sum_{k=1}^{K}(\overline{V}_{1}^{k}(s_{1}^{k})-\underline{V}_{1}^{k}(s_{1}^{k}))\leq
21(M_{1}+M_{2}+M_{3}+M_{4}).$ (10)

We now bound each of these four items separately.

###### Lemma 4

With probability at least $1-\delta$, $|M_{1}|\leq H\sqrt{2HK\iota}.$

###### Lemma 5

With probability at least $1-\delta$, $|M_{2}|\leq\sqrt{2HK\iota}$.

###### Lemma 6

With probability at least $1-\delta$, $|M_{3}|\leq H\sqrt{2HK\iota}.$

###### Lemma 7

With probability at least $1-2\delta$, $|M_{4}|\leq
2S^{2}AH^{3}\iota^{2}+8\sqrt{SAH^{2}K\iota}+46S^{\frac{3}{2}}AH^{3}\iota^{2}+\sqrt{24SAH^{3}K}\iota+6\sqrt{SAH^{5}}\iota$.

##### Putting All Together

By Lemmas 3, 4, 5, 6, and 7, we conclude that, with probability
$1-(S+10)\delta$,

$\begin{split}Regret(K)\leq&O(\sqrt{H^{3}K\iota}+\sqrt{SAH^{2}K\iota}+\sqrt{SAH^{3}K}\iota+S^{2}AH^{3}\iota^{2}+\sqrt{SAH^{5}}\iota)\\\
=&O(\sqrt{SAH^{3}K}\iota+S^{2}AH^{3}\iota^{2}).\end{split}$ (11)

By rescaling $\delta$, $\log(\frac{2SAHK}{\delta/(S+10)})\leq c\iota$ for some
constant $c$ and we finish the proof of regret. As
$\sum_{k=1}^{K}(\overline{V}_{1}^{k}(s_{1}^{k})-\underline{V}_{1}^{k}(s_{1}^{k}))\leq
O(\sqrt{SAH^{3}K}\iota+S^{2}AH^{3}\iota^{2})$, we have that
$V_{1}^{*}(s_{1})-{V}_{1}^{{\pi}^{out}}(s_{1})\leq\min_{k}\overline{V}_{1}^{k}(s_{1}^{k})-\underline{V}_{1}^{k}(s_{1}^{k})\leq
O(\frac{\sqrt{SAH^{3}}\iota}{K}+\frac{S^{2}AH^{3}\iota^{2}}{K})$ and we finish
the proof of sample complexity.

##  7 Model-free method

In this section, we develop a model-free algorithm and analyze its theoretical
guarantee. We present the proposed Action Robust Q-learning with UCB-Hoeffding
(AR-UCBH) algorithm show in Algorithm 2. Here, we highlight the main idea of
Algorithm 2. Algorithm 2 follows the same idea of Algorithm 1, which trains
the agent in a clean (simulation) environment and learns a policy that
performs well when applied to a perturbed environment with probabilistic
policy execution uncertainty. To simulate the action perturbation, Algorithm 2
chooses an adversarial action with probability $\rho$. To learn the agent’s
optimal policy and the corresponding adversarial policy, Algorithm 2 computes
an optimistic estimate $\overline{Q}$ of $Q^{*}$ and a pessimistic estimate
$\underline{Q}$ of $Q^{\overline{\pi}^{k}}$. Algorithm 2 uses the optimistic
estimates to explore the possible optimal policy $\overline{\pi}$ and uses the
pessimistic estimates to explore the possible adversarial policy
$\underline{\pi}$. The difference is that Algorithm 2 use a model-free method
to update $Q$ and $V$ values.

1: Set $\alpha_{t}=\frac{H+1}{H+t}$. Initialize $\overline{V}_{h}(s)=H-h+1$,
$\overline{Q}_{h}(s,a)=H-h+1$, $\underline{V}_{h}(s)=0$,
$\underline{Q}_{h}(s,a)=0$, $\hat{r}_{h}(s,a)$, $N_{h}(s,a)=0$ for all state
$s\in\mathcal{S}$, all action $a\in\mathcal{A}$ and all step $h\in[H]$.
$\overline{V}_{H+1}(s)=\underline{V}_{H+1}(s)=0$ and
$\overline{Q}_{H+1}(s,a)=\underline{Q}_{H+1}(s,a)=0$ for all $s$ and $a$.
$\Delta=H$. Initial policy $\overline{\pi}_{h}^{1}(a|s)$ and
$\underline{\pi}_{h}^{1}(a|s)=1/A$ for all state $s$, action $a$ and all step
$h\in[H]$.

2: for episode $k=1,2,\dots,K$ do

3: for step $h=1,2,\dots,H$ do

4: Observe $s_{h}^{k}$.

5: Set
$\overline{a}_{h}^{k}=\operatorname*{arg\,max}_{a}\overline{Q}_{h}(s_{h}^{k},a)$
,
$\underline{a}_{h}^{k}=\operatorname*{arg\,min}_{a}\underline{Q}_{h}(s_{h}^{k},a)$,
$\widetilde{\pi}_{h}^{k}(\overline{a}_{h}^{k}|s_{h}^{k})=1-\rho$ and
$\widetilde{\pi}_{h}^{k}(\underline{a}_{h}^{k}|s_{h}^{k})=\rho$.

6: Take action $a_{h}^{k}\sim\widetilde{\pi}_{h}^{k}(\cdot|s_{h}^{k})$.

7: Receive reward $r_{h}^{k}$ and observe $s_{h+1}^{k}$.

8: Set $t=N_{h}(s_{h}^{k},a_{h}^{k})\leftarrow N_{h}(s_{h}^{k},a_{h}^{k})+1$;
$b_{t}=\sqrt{H^{3}\iota/t}$.

9:
$\overline{Q}_{h}(s_{h}^{k},a_{h}^{k})\leftarrow(1-\alpha_{t})\overline{Q}_{h}(s_{h}^{k},a_{h}^{k})+\alpha_{t}(r_{h}^{k}+\overline{V}_{h+1}(s_{h+1}^{k})+b_{t})$,

10:
$\underline{Q}_{h}(s_{h}^{k},a_{h}^{k})\leftarrow(1-\alpha_{t})\underline{Q}_{h}(s_{h}^{k},a_{h}^{k})+\alpha_{t}(r_{h}^{k}+\underline{V}_{h+1}(s_{h+1}^{k})-b_{t})$.

11: Set
$\overline{\pi}_{h}^{k+1}(s_{h}^{k})=\operatorname*{arg\,max}_{a}\overline{Q}_{h}(s_{h}^{k},a)$,
$\underline{\pi}_{h}^{k+1}(s_{h}^{k})=\operatorname*{arg\,min}_{a}\underline{Q}_{h}(s_{h}^{k+1},a)$.

12:
$\overline{V}_{h}(s_{h}^{k})\leftarrow\min\\{\overline{V}_{h}(s_{h}^{k}),(1-\rho)\overline{Q}_{h}(s_{h}^{k},\overline{\pi}_{h}^{k+1}(s_{h}^{k}))+\rho\overline{Q}_{h}(s_{h}^{k},\underline{\pi}_{h}^{k+1}(s_{h}^{k}))\\}$.

13:
$\underline{V}_{h}(s_{h}^{k})\leftarrow\max\\{\underline{V}_{h}(s_{h}^{k}),(1-\rho)\underline{Q}_{h}(s_{h}^{k},\overline{\pi}_{h}^{k+1}(s_{h}^{k}))+\rho\underline{Q}_{h}(s_{h}^{k},\underline{\pi}_{h}^{k+1}(s_{h}^{k}))\\}$.

14: if
$\underline{V}_{h}(s_{h}^{k})>(1-\rho)\underline{Q}_{h}(s_{h}^{k},\overline{\pi}_{h}^{k+1}(s_{h}^{k}))+\rho\underline{Q}_{h}(s_{h}^{k},\underline{\pi}_{h}^{k+1}(s_{h}^{k}))$
then

15: $\overline{\pi}_{h}^{k+1}=\overline{\pi}_{h}^{k}$.

16: end if

17: end for

18: Output policy $\overline{\pi}^{k+1}$ with certificates
$\mathcal{I}_{k+1}=[\underline{V}_{1}(s_{1}^{k}),\overline{V}_{1}(s_{1}^{k})]$
and $\epsilon_{k+1}=|\mathcal{I}_{k+1}|$.

19: end for

20: return $\overline{\pi}^{k+1}$

Algorithm 2 Action Robust Q-learning with UCB-Hoeffding (AR-UCBH)

Here, we highlight the challenges of the model-free planning compared with the
model-based planing. In the model-based planning, we performs value iteration
and the $Q$ values, $V$ values, agent policy $\overline{\pi}$ and adversarial
policy $\underline{\pi}$ are updated on all $(s,a)$. However, in the model-
free method, the $Q$ values, $V$ values are updated only on
$(s_{h}^{k},a_{h}^{k})$ which are the samples on the trajectories. Compared
with the model-based planning, the model-free planning is slower and less
stable. We need to update the output policy carefully. In line 14-16,
Algorithm 2 does not update the output policy when the lower bound on the
value function of the new policy does not improve. By this, the output
policies are stably updated.

We provide the regret and sample complexity bounds of Algorithm 2 in the
following:

###### Theorem 3

For any $\delta\in(0,1]$, letting $\iota=\log(2SABHK/\delta)$, then with
probability at least $1-\delta$, Algorithm 2 achieves:

  * •

$V_{1}^{*}(s_{1})-V_{1}^{\pi^{out}}(s_{1})\leq\epsilon$, if the number of
episodes $K\geq\Omega(SAH^{5}\iota/\epsilon^{2}+SAH^{2}/\epsilon)$.

  * •

$Regret(K)=\sum_{k=1}^{K}(V_{1}^{*}(s_{1}^{k})-{V}_{1}^{\overline{\pi}^{k}}(s_{1}^{k}))\leq\mathcal{O}(\sqrt{SAH^{5}K\iota}+SAH^{2})$.

The detailed proof is provided in Appendix C

##  8 Simulation results

We use OpenAI gym framework [37], and consider two different problems: Cliff
Walking, a toy text environment, and Inverted Pendulum, a control environment
with the MuJoCo [38] physics simulator. We set $H=100$. To demonstrate the
robustness, the policy is learned in a clean environment, and is then tested
on the perturbed environment. Specifically, during the testing, we set a
probability $p$ such that after the agent takes an action, with probability
$p$, the action is uniformly randomly choosen or choosen by a fixed
adversarial policy. A Monte-Carlo method is used to evaluate the accumulated
reward of the learned policy on the perturbed environment. We take the average
over 100 trajectories. Training of ARRLC on CliffWalking-v0 and
InvertedPendulum-v4 respectively cost roughly 5 seconds and 22 seconds per 100
episodes on an i9-9880H CPU core. In Figure 3 and Figure 4, "fix" represents
that the action is perturbed by a fixed adversarial policy during the testing,
"random" represents that the action is randomly perturbed during the testing,
$p$ is the action perturbation probability.

Figure 1: Inverted pendulum environment.

Figure 2: Cliff walking environment.

##### Inverted pendulum

The inverted pendulum experiment as shown in Figure 2 is a classic control
problem in RL. An inverted pendulum is attached by a pivot point to a cart,
which is restricted to linear movement in a plane. The cart can be pushed left
or right, and the goal is to balance the inverted pendulum on the top of the
cart by applying forces on the cart. A reward of $+1$ is awarded for each time
step that the inverted pendulum stand upright within a certain angle limit.
The fixed adversarial policy in the inverted pendulum environment is a force
of $0.5$ N in the left direction.

##### Cliff walking

The cliff walking experiment as shown in Figure 2 is a classic scenario
proposed in [39]. The game starts with the player at location $[3,0]$ of the
$4\times 12$ grid world with the goal located at $[3,11]$. A cliff runs along
$[3,1-10]$. If the player moves to a cliff location, it returns to the start
location and receives a reward of $-100$. For every move which does not lead
into the cliff, the agent receives a reward of $-1$. The player makes moves
until they reach the goal. The fixed adversarial policy in the cliff walking
environment is walking a step to the bottom.

We compare our algorithm with the non-robust RL algorithm, which is ORLC
(Optimistic Reinforcement Learning with Certificates) in [31]. We set
$\rho=0.2$ for our algorithm, which is the uncertain parameter used during the
training. In Figure 3, we plot the accumulated reward of both algorithms under
different $p$ and perturbations. It can be seen that overall our ARRLC
algorithm achieves a much higher reward than the ORLC algorithm. This
demonstrates the robustness of our ARRLC algorithm to policy execution
uncertainty.

(a) p=0.1, fix

(b) p=0.2, fix

(c) p=0.1, random

(d) p=0.2, random

(e) p=0.1, fix

(f) p=0.2, fix

(g) p=0.1, random

(h) p=0.2, random

Figure 3: ARRLC v.s. ORLC.

We compare our algorithm with the robust TD algorithm in [8], which has no
theoretical guarantee on sample complexity or regret. We set $\rho=0.2$. In
Figure 4, we plot the accumulated reward of both algorithms under different
$p$ and perturbations using a base-10 logarithmic scale on the x-axis and a
linear scale on the y-axis. It can be seen that our ARRLC algorithm converges
faster than the robust TD algorithm. This demonstrates the efficiency of our
ARRLC algorithm to learn optimal policy under policy execution uncertainty.

(a) p=0.1, fix

(b) p=0.2, fix

(c) p=0.1, random

(d) p=0.2, random

(e) p=0.1, fix

(f) p=0.2, fix

(g) p=0.1, random

(h) p=0.2, random

Figure 4: ARRLC v.s. Robust TD

##  9 Conclusion

In this paper, we have developed a novel approach for solving action robust RL
problems with probabilistic policy execution uncertainty. We have
theoretically proved the sample complexity bound and the regret bound of the
algorithms. The upper bound of the sample complexity and the regret of
proposed ARRLC algorithm match the lower bound up to logarithmic factors,
which shows the minimax optimality of our algorithm. Moreover, we have carried
out numerical experiments to validate our algorithm’s robustness and
efficiency, revealing that ARRLC surpasses non-robust algorithms and converges
more rapidly than the robust TD algorithm when faced with action
perturbations.

## References

  * [1] Xiangyu Zhao, Long Xia, Liang Zhang, Zhuoye Ding, Dawei Yin, and Jiliang Tang.  Deep reinforcement learning for page-wise recommendations.  In Proceedings of the 12th ACM Conference on Recommender Systems, page 95–103. ACM, 2018.
  * [2] Matthew O’ Kelly, Aman Sinha, Hongseok Namkoong, Russ Tedrake, and John C Duchi.  Scalable end-to-end autonomous vehicle testing via rare-event simulation.  In Advances in Neural Information Processing Systems, volume 31, 2018.
  * [3] Xiao-Yang Liu, Hongyang Yang, Qian Chen, Runjia Zhang, Liuqing Yang, Bowen Xiao, and Christina Dan Wang.  Finrl: A deep reinforcement learning library for automated stock trading in quantitative finance.  Deep RL Workshop, NeurIPS 2020, 2020.
  * [4] MohammadReza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takac.  Reinforcement learning for solving the vehicle routing problem.  In Advances in Neural Information Processing Systems, volume 31, 2018.
  * [5] Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Mingyan Liu, Duane Boning, and Cho-Jui Hsieh.  Robust deep reinforcement learning against adversarial perturbations on state observations.  Advances in Neural Information Processing Systems, 33:21024–21037, 2020.
  * [6] Yanchao Sun, Ruijie Zheng, Yongyuan Liang, and Furong Huang.  Who is the strongest enemy? towards optimal and efficient evasion attacks in deep RL.  In International Conference on Learning Representations, 2022.
  * [7] Chen Tessler, Yonathan Efroni, and Shie Mannor.  Action robust reinforcement learning and applications in continuous control.  In International Conference on Machine Learning, pages 6215–6224. PMLR, 2019.
  * [8] Richard Klima, Daan Bloembergen, Michael Kaisers, and Karl Tuyls.  Robust temporal difference learning for critical domains.  In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’19, page 350–358, 2019.
  * [9] Arnab Nilim and Laurent El Ghaoui.  Robust control of markov decision processes with uncertain transition matrices.  Operations Research, 53(5):780–798, 2005.
  * [10] Yue Wang and Shaofeng Zou.  Online robust reinforcement learning with model uncertainty.  Advances in Neural Information Processing Systems, 34:7193–7206, 2021.
  * [11] Yunhan Huang and Quanyan Zhu.  Deceptive reinforcement learning under adversarial manipulations on cost signals.  In Decision and Game Theory for Security: 10th International Conference, GameSec 2019, Stockholm, Sweden, October 30–November 1, 2019, Proceedings 10, pages 217–237. Springer, 2019.
  * [12] Erwan Lecarpentier and Emmanuel Rachelson.  Non-stationary markov decision processes, a worst-case approach using model-based reinforcement learning.  Advances in neural information processing systems, 32, 2019.
  * [13] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  arXiv preprint arXiv:1412.6572, 2014.
  * [14] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  In International Conference on Learning Representations, 2018.
  * [15] Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta.  Robust adversarial reinforcement learning.  In International Conference on Machine Learning, pages 2817–2826, 2017.
  * [16] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen.  Sample complexity of asynchronous q-learning: Sharper analysis and variance reduction.  Advances in neural information processing systems, 33:7031–7043, 2020.
  * [17] Jiafan He, Dongruo Zhou, and Quanquan Gu.  Nearly minimax optimal reinforcement learning for discounted mdps.  Advances in Neural Information Processing Systems, 34:22288–22300, 2021.
  * [18] Kaiyang Guo, Shao Yunfeng, and Yanhui Geng.  Model-based offline reinforcement learning with pessimism-modulated dynamics belief.  Advances in Neural Information Processing Systems, 35:449–461, 2022\.
  * [19] Laixi Shi and Yuejie Chi.  Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity.  arXiv preprint arXiv:2208.05767, 2022.
  * [20] Zaiyan Xu, Kishan Panaganti, and Dileep Kalathil.  Improved sample complexity bounds for distributionally robust reinforcement learning.  In International Conference on Artificial Intelligence and Statistics, pages 9728–9754. PMLR, 2023.
  * [21] Kishan Panaganti and Dileep Kalathil.  Sample complexity of robust reinforcement learning with a generative model.  In International Conference on Artificial Intelligence and Statistics, pages 9582–9602. PMLR, 2022.
  * [22] Xuezhou Zhang, Yuzhe Ma, Adish Singla, and Xiaojin Zhu.  Adaptive reward-poisoning attacks against reinforcement learning.  In Proceedings of the 37th International Conference on Machine Learning, volume 119, pages 11225–11234, 2020.
  * [23] Guanlin Liu and Lifeng Lai.  Provably efficient black-box action poisoning attacks against reinforcement learning.  Advances in Neural Information Processing Systems, 34, 2021.
  * [24] Yanchao Sun, Da Huo, and Furong Huang.  Vulnerability-aware poisoning mechanism for online rl with unknown dynamics.  In International Conference on Learning Representations, 2021.
  * [25] Michael Kearns and Satinder Singh.  Near-optimal reinforcement learning in polynomial time.  Machine learning, 49:209–232, 2002.
  * [26] Alexander L Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L Littman.  Pac model-free reinforcement learning.  In Proceedings of the 23rd international conference on Machine learning, pages 881–888, 2006.
  * [27] Peter Auer, Thomas Jaksch, and Ronald Ortner.  Near-optimal regret bounds for reinforcement learning.  Advances in neural information processing systems, 21, 2008.
  * [28] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos.  Minimax regret bounds for reinforcement learning.  In International Conference on Machine Learning, pages 263–272, 2017.
  * [29] Christoph Dann, Tor Lattimore, and Emma Brunskill.  Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning.  Advances in Neural Information Processing Systems, 30, 2017.
  * [30] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan.  Is q-learning provably efficient?  Advances in neural information processing systems, 31, 2018.
  * [31] Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill.  Policy certificates: Towards accountable reinforcement learning.  In International Conference on Machine Learning, pages 1507–1516. PMLR, 2019.
  * [32] Max Simchowitz and Kevin G Jamieson.  Non-asymptotic gap-dependent regret bounds for tabular mdps.  Advances in Neural Information Processing Systems, 32, 2019.
  * [33] Zihan Zhang, Yuan Zhou, and Xiangyang Ji.  Almost optimal model-free reinforcement learningvia reference-advantage decomposition.  Advances in Neural Information Processing Systems, 33:15198–15207, 2020.
  * [34] Zihan Zhang, Xiangyang Ji, and Simon Du.  Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon.  In Conference on Learning Theory, pages 4528–4531. PMLR, 2021.
  * [35] Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin.  A sharp analysis of model-based reinforcement learning with self-play.  In International Conference on Machine Learning, pages 7001–7010. PMLR, 2021.
  * [36] Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu.  V-learning–a simple, efficient, decentralized algorithm for multiagent rl.  arXiv preprint arXiv:2110.14555, 2021.
  * [37] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba.  Openai gym.  arXiv preprint arXiv:1606.01540, 2016.
  * [38] Emanuel Todorov, Tom Erez, and Yuval Tassa.  Mujoco: A physics engine for model-based control.  In 2012 IEEE/RSJ international conference on intelligent robots and systems, pages 5026–5033. IEEE, 2012.
  * [39] Richard S Sutton and Andrew G Barto.  Reinforcement learning: An introduction.  MIT press, 2018.
  * [40] Andreas Maurer and Massimiliano Pontil.  Empirical bernstein bounds and sample variance penalization.  arXiv preprint arXiv:0907.3740, 2009.
  * [41] Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger.  Inequalities for the l1 deviation of the empirical distribution.  Hewlett-Packard Labs, Tech. Rep, 2003.

##  Appendix A Proof of Theorem 1

The uncertainty set of the policy execution has the form in:

$\Pi^{\rho}(\pi):=\\{\widetilde{\pi}|\forall
s,\widetilde{\pi}_{h}(\cdot|s)=(1-\rho)\pi(\cdot|s)+\rho\pi^{\prime}_{h}(\cdot|s),\pi^{\prime}_{h}(\cdot|s)\in\Delta_{\mathcal{A}}\\}.$
(12)

We define

$\displaystyle C_{h}^{\pi,\pi^{\prime},\rho}(s)$ $\displaystyle:=$
$\displaystyle\mathbb{E}\left[\sum_{h^{\prime}=h}^{H}R_{h^{\prime}}(s_{h^{\prime}},a_{h^{\prime}})|s_{h}=s,a_{h^{\prime}}\sim\widetilde{\pi}_{h^{\prime}}(\cdot|s_{h^{\prime}})\right]$
$\displaystyle D_{h}^{\pi,\pi^{\prime},\rho}(s,a)$ $\displaystyle:=$
$\displaystyle\mathbb{E}\left[\sum_{h^{\prime}=h}^{H}R_{h^{\prime}}(s_{h^{\prime}},a_{h^{\prime}})|s_{h}=s,a_{h}=a,a_{h^{\prime}}\sim\widetilde{\pi}_{h^{\prime}}(\cdot|s_{h^{\prime}})\right].$

##### Robust Bellman Equation

First we prove the action robust Bellman equation holds for all policy $\pi$,
state $s$ action $a$ and step $h$. From the definition of the robust value
function in (1), we have $V^{\pi}_{H+1}(s)=0$, $\forall s\in\mathcal{S}$.

We prove the robust Bellman equation by building a policy ${\pi}^{-}$. Here,
policy $\pi^{-}$ is the optimal adversarial policy towards the policy $\pi$.

At step $H$, we set
${\pi}^{-}_{H}(s)=\operatorname*{arg\,min}_{a\in\mathcal{A}}R_{H}(s,a)$. We
have

$\begin{split}V^{\pi}_{H}(s)&=\min_{\pi^{\prime}}C_{H}^{\pi,\pi^{\prime},\rho}(s)\\\
&=(1-\rho)[\mathbbm{D}_{\pi_{H}}R_{H}](s)+\rho\min_{\pi^{\prime}}[\mathbbm{D}_{\pi^{\prime}_{H}}R_{H}](s)\\\
&=(1-\rho)[\mathbbm{D}_{\pi_{H}}Q^{\pi}_{H}](s)+\rho\min_{a\in\mathcal{A}}Q^{\pi}_{H}(s,a)=C_{H}^{\pi,\pi^{-},\rho}(s),\end{split}$
(13)

as $V_{H+1}=0$.

The robust Bellman equation holds at step $H$ and
$\min_{\pi^{\prime}}\sum_{s}w(s)C_{H}^{\pi,\pi^{\prime},\rho}(s)=\sum_{s}w(s)\min_{\pi^{\prime}}C_{H}^{\pi,\pi^{\prime},\rho}(s)=\sum_{s}w(s)C_{H}^{\pi,\pi^{-},\rho}(s)$
for any state $s$ and any weighted function
$w:\mathcal{S}\rightarrow\Delta_{\mathcal{S}}$.

Suppose the robust Bellman equation holds at step $h+1$ and
$\min_{\pi^{\prime}}\sum_{s}w(s)C_{h+1}^{\pi,\pi^{\prime},\rho}(s)=\sum_{s}w(s)\min_{\pi^{\prime}}C_{h+1}^{\pi,\pi^{\prime},\rho}(s)=\sum_{s}w(s)C_{h+1}^{\pi,\pi^{-},\rho}(s)$
for any state $s$ and any weighted function
$w:\mathcal{S}\rightarrow\Delta_{\mathcal{S}}$.

Now we prove the robust Bellman equation holds at step $h$. From the
definition of the robust $Q$-function in (2) and the form of uncertainty set,
we have

$\begin{split}Q^{\pi}_{h}(s,a)=&\min_{\widetilde{\pi}\in\Pi(\pi)}\mathbb{E}\left[\sum_{h^{\prime}=h}^{H}R_{h^{\prime}}(s_{h^{\prime}},a_{h^{\prime}})|s_{h}=s,a_{h}=a,a_{h^{\prime}}\sim\widetilde{\pi}_{h^{\prime}}(\cdot|s_{h^{\prime}})\right]\\\
=&\min_{\pi^{\prime}}D_{h}^{\pi,\pi^{\prime},\rho}(s,a)\\\
=&R_{h}(s,a)+\min_{\pi^{\prime}}\mathbbm{E}_{s^{\prime}\sim
P_{h}(\cdot|s,a)}C_{h+1}^{\pi,\pi^{\prime},\rho}(s)\\\
=&R_{h}(s,a)+\mathbbm{E}_{s^{\prime}\sim
P_{h}(\cdot|s,a)}\min_{\pi^{\prime}}C_{h+1}^{\pi,\pi^{\prime},\rho}(s)\\\
=&R_{h}(s,a)+[{P}_{h}V_{h+1}^{\pi}](s,a).\end{split}$ (14)

We also have that $Q^{\pi}_{h}(s,a)=D_{h}^{\pi,\pi^{-},\rho}(s,a)$.

Recall that a (stochastic) Markov policy is a set of $H$ maps
$\pi:=\\{\pi_{h}:\mathcal{S}\rightarrow\Delta_{\mathcal{A}}\\}_{h\in[H]}$.
From the definition of the robust value function in (1) and the form of
uncertainty set, we have

$\begin{split}V^{\pi}_{h}(s)=&\min_{\widetilde{\pi}\in\Pi(\pi)}\mathbb{E}\left[\sum_{h^{\prime}=h}^{H}R_{h^{\prime}}(s_{h^{\prime}},a_{h^{\prime}})|s_{h}=s,a_{h^{\prime}}\sim\widetilde{\pi}_{h^{\prime}}(\cdot|s_{h^{\prime}})\right]\\\
=&\min_{\pi^{\prime}}C_{h}^{\pi,\pi^{\prime},\rho}(s)\\\
=&\min_{{\pi^{\prime}}_{h}}\min_{\\{{\pi^{\prime}}_{h^{\prime}}\\}_{h^{\prime}=h+1}^{H}}C_{h}^{\pi,\pi^{\prime},\rho}(s)\\\
\geq&(1-\rho)\min_{\\{{\pi^{\prime}}_{h^{\prime}}\\}_{h^{\prime}=h+1}^{H}}\mathbb{E}_{a\sim\pi_{h}(\cdot|s)}D_{h}^{\pi,\pi^{\prime},\rho}(s,a)+\rho\min_{{\pi^{\prime}}_{h}}\min_{\\{{\pi^{\prime}}_{h^{\prime}}\\}_{h^{\prime}=h+1}^{H}}\mathbb{E}_{a\sim\pi^{\prime}_{h}(\cdot|s)}D_{h}^{\pi,\pi^{\prime},\rho}(s,a)\\\
\geq&(1-\rho)\mathbb{E}_{a\sim\pi_{h}(\cdot|s)}\min_{\\{{\pi^{\prime}}_{h^{\prime}}\\}_{h^{\prime}=h+1}^{H}}D_{h}^{\pi,\pi^{\prime},\rho}(s,a)+\rho\min_{{\pi^{\prime}}_{h}}\mathbb{E}_{a\sim\pi^{\prime}_{h}(\cdot|s)}\min_{\\{{\pi^{\prime}}_{h^{\prime}}\\}_{h^{\prime}=h+1}^{H}}D_{h}^{\pi,\pi^{\prime},\rho}(s,a)\\\
=&(1-\rho)[\mathbbm{D}_{\pi_{h}}Q^{\pi}_{h}](s)+\rho\min_{a\in\mathcal{A}}Q^{\pi}_{h}(s,a).\end{split}$
(15)

We set
${\pi}^{-}_{h}(s)=\operatorname*{arg\,min}_{a\in\mathcal{A}}Q_{h}^{\pi}(s,a)=\operatorname*{arg\,min}_{a\in\mathcal{A}}D_{h}^{\pi,\pi^{-},\rho}(s,a)$.

At step $h$, we have

$\begin{split}V^{\pi}_{h}(s)\leq&C_{h}^{\pi,\pi^{-},\rho}(s)\\\
=&(1-\rho)[\mathbbm{D}_{\pi_{h}}D_{h}^{\pi,\pi^{-},\rho}](s)+\rho\min_{a\in\mathcal{A}}D_{h}^{\pi,\pi^{-},\rho}(s,a)\\\
=&(1-\rho)[\mathbbm{D}_{\pi_{h}}Q^{\pi}_{h}](s)+\rho\min_{a\in\mathcal{A}}Q^{\pi}_{h}(s,a),\end{split}$
(16)

where the last equation comes from the robust Bellman equation at step $h+1$
and

$D_{h}^{\pi,\pi^{-},\rho}(s,a)=R_{h}(s,a)+[{P}_{h}C_{h+1}^{\pi,\pi^{-},\rho}](s,a)=R_{h}(s,a)+[{P}_{h}V_{h+1}^{\pi}](s,a).$

Thus, the robust Bellman equation holds at step $h$.

Then, we prove the commutability of the expectation and the minimization
operations at step $h$. For any weighted function $w$, we have
$\min_{\pi^{\prime}}\sum_{s}w(s)C_{h}^{\pi,\pi^{\prime},\rho}(s)\geq\sum_{s}w(s)\min_{\pi^{\prime}}C_{h}^{\pi,\pi^{\prime},\rho}(s)$.
Then,
$\min_{\pi^{\prime}}\sum_{s}w(s)C_{h}^{\pi,\pi^{\prime},\rho}(s)\leq\sum_{s}w(s)C_{h}^{\pi,\pi^{-},\rho}(s)=\sum_{s}w(s)\min_{\pi^{\prime}}C_{h}^{\pi,\pi^{\prime},\rho}(s)$.

By induction on $h=H,\cdots,1$, we prove the robust Bellman equation.

##### Perfect Duality and Robust Bellman Optimality Equation

We now prove that the perfect duality holds and can be solved by the optimal
robust Bellman equation.

The control problem in the LHS of (4) is equivalent to

$\begin{split}&\max_{\pi}\min_{\widetilde{\pi}\in\Pi^{\rho}(\pi)}\mathbb{E}\left[\sum_{h^{\prime}=h}^{H}R_{h^{\prime}}(s_{h^{\prime}},a_{h^{\prime}})|s_{h}=s,a_{h^{\prime}}\sim\widetilde{\pi}_{h^{\prime}}(\cdot|s_{h^{\prime}})\right]=\max_{\pi}\min_{\pi^{\prime}}C_{h}^{\pi,\pi^{\prime},\rho}(s).\end{split}$
(17)

The control problem in the RHS of (4) is equivalent to

$\begin{split}&\min_{\widetilde{\pi}\in\Pi^{\rho}(\pi)}\max_{\pi}\mathbb{E}\left[\sum_{h^{\prime}=h}^{H}R_{h^{\prime}}(s_{h^{\prime}},a_{h^{\prime}})|s_{h}=s,a_{h^{\prime}}\sim\widetilde{\pi}_{h^{\prime}}(\cdot|s_{h^{\prime}})\right]=\min_{\pi^{\prime}}\max_{\pi}C_{h}^{\pi,\pi^{\prime},\rho}(s).\end{split}$
(18)

For step $H$, we have
$C_{H}^{\pi,\pi^{\prime},\rho}(s)=[\mathbbm{D}_{\left((1-\rho)\pi+\rho\pi^{\prime}\right)_{H}}R_{H}](s)=(1-\rho)[\mathbbm{D}_{\pi_{H}}R_{H}](s)+\rho[\mathbbm{D}_{\pi^{\prime}_{H}}R_{H}](s)$.
Thus, we have

$\begin{split}\max_{\pi}\min_{\pi^{\prime}}C_{H}^{\pi,\pi^{\prime},\rho}(s)=&(1-\rho)\max_{\pi}[\mathbbm{D}_{\pi_{H}}R_{H}](s)+\rho\min_{\pi^{\prime}}[\mathbbm{D}_{\pi^{\prime}_{H}}R_{H}](s)\\\
=&(1-\rho)\max_{a\in\mathcal{A}}R_{H}(s,a)+\rho\min_{b\in\mathcal{A}}R_{H}(s,b),\end{split}$
(19)

and

$\begin{split}\min_{\pi^{\prime}}\max_{\pi}C_{H}^{\pi,\pi^{\prime},\rho}(s)=&(1-\rho)\max_{\pi}[\mathbbm{D}_{\pi_{H}}R_{H}](s)+\rho\min_{\pi^{\prime}}[\mathbbm{D}_{\pi^{\prime}_{H}}R_{H}](s)\\\
=&(1-\rho)\max_{a\in\mathcal{A}}R_{H}(s,a)+\rho\min_{b\in\mathcal{A}}R_{H}(s,b).\end{split}$
(20)

At step $H$, the perfect duality holds for all $s$ and there always exists an
optimal robust policy
$\pi^{*}_{H}(s)=\operatorname*{arg\,max}_{a\in\mathcal{A}}Q_{H}^{*}(s,a)=\operatorname*{arg\,max}_{a\in\mathcal{A}}R_{H}(s,a)$
and its corresponding optimal adversarial policy
$\pi^{-}_{H}(s)=\operatorname*{arg\,min}_{a\in\mathcal{A}}R_{H}(s,a)$ which
are deterministic. The action robust Bellman optimality equation holds at step
$H$ for all state $s$ and action $a$.

In addition,
$\max_{\pi}\min_{\pi^{\prime}}\sum_{s}w(s)C_{H}^{\pi,\pi^{\prime},\rho}(s)=\sum_{s}w(s)\max_{\pi}\min_{\pi^{\prime}}C_{H}^{\pi,\pi^{\prime},\rho}(s)$
for any weighted function $w:\mathcal{S}\rightarrow\Delta_{\mathcal{S}}$. This
can be shown as

$\begin{split}&\max_{\pi}\min_{\pi^{\prime}}\sum_{s\in\mathcal{S}}w(s)C_{H}^{\pi,\pi^{\prime},\rho}(s)\\\
=&(1-\rho)\max_{\pi}\sum_{s\in\mathcal{S}}w(s)[\mathbbm{D}_{\pi_{H}}R_{H}](s)+\rho\min_{\pi^{\prime}}\sum_{s\in\mathcal{S}}w(s)[\mathbbm{D}_{\pi^{\prime}_{H}}R_{H}](s)\\\
=&(1-\rho)\sum_{s\in\mathcal{S}}w(s)\max_{a\in\mathcal{A}}R_{H}(s,a)+\rho\sum_{s\in\mathcal{S}}w(s)\min_{b\in\mathcal{A}}R_{H}(s,b).\end{split}$
(21)

Suppose that at steps from $h+1$ to $H$, the perfect duality holds for all
$s$, the action robust Bellman optimality equation holds for all state $s$ and
action $a$, there always exists an optimal robust policy
$\pi^{*}_{h^{\prime}}=\operatorname*{arg\,max}_{a\in\mathcal{A}}Q_{h^{\prime}}^{*}(s,a)$
and its corresponding optimal adversarial policy
$\pi^{-}_{h^{\prime}}(s)=\operatorname*{arg\,min}_{a\in\mathcal{A}}Q_{h^{\prime}}^{*}(s,a)$,
$\forall h^{\prime}\geq h+1$, which is deterministic , and
$\max_{\pi}\min_{\pi^{\prime}}\sum_{s}w(s)C_{h^{\prime}}^{\pi,\pi^{\prime},\rho}(s)=\sum_{s}w(s)\max_{\pi}\min_{\pi^{\prime}}C_{h^{\prime}}^{\pi,\pi^{\prime},\rho}(s)$
for any state $s$, any weighted function
$w:\mathcal{S}\rightarrow\Delta_{\mathcal{S}}$ and any $h^{\prime}\geq h+1$.
We have
$V_{h^{\prime}}^{*}(s)=V_{h^{\prime}}^{\pi^{*}}(s)=C_{h^{\prime}}^{\pi^{*},\pi^{-},\rho}(s)$
and
$Q_{h^{\prime}}^{*}(s,a)=Q_{h^{\prime}}^{\pi^{*}}(s,a)=D_{h^{\prime}}^{\pi^{*},\pi^{-},\rho}(s,a)$
for any state $s$ and any $h^{\prime}\geq h+1$.

We first prove that the robust Bellman optimality equation holds at step $h$.

We have

$\begin{split}Q_{h}^{*}(s,a)&=\max_{\pi}\min_{\pi^{\prime}}D_{h}^{\pi,\pi^{\prime},\rho}(s,a)\\\
&=\max_{\pi}\min_{\pi^{\prime}}(R_{h}(s,a)+[{P}_{h}C_{h+1}^{\pi,\pi^{\prime},\rho}](s,a))\\\
&=R_{h}(s,a)+[{P}_{h}(\max_{\pi}\min_{\pi^{\prime}}C_{h+1}^{\pi,\pi^{\prime},\rho})](s,a)\\\
&=R_{h}(s,a)+[{P}_{h}V_{h+1}^{*}](s,a).\end{split}$ (22)

and also
$Q_{h}^{*}(s,a)=Q_{h}^{\pi^{*}}(s,a)=D_{h}^{\pi^{*},\pi^{-},\rho}(s,a)$.

From the robust Bellman equation, we have

$\begin{split}\max_{\pi}V^{\pi}_{h}(s)=&\max_{\pi}\left((1-\rho)[\mathbbm{D}_{\pi_{h}}Q^{\pi}_{h}](s)+\rho\min_{a\in\mathcal{A}}Q^{\pi}_{h}(s,a)\right)\\\
\leq&(1-\rho)\max_{{\pi}_{h}}\max_{\\{{\pi}_{h}\\}_{h^{\prime}=h+1}^{H}}[\mathbbm{D}_{\pi_{h}}Q^{\pi}_{h}](s)+\rho\max_{\\{{\pi}_{h}\\}_{h^{\prime}=h+1}^{H}}\min_{a\in\mathcal{A}}Q^{\pi}_{h}(s,a)\\\
\leq&(1-\rho)\max_{{\pi}_{h}}\max_{\\{{\pi}_{h}\\}_{h^{\prime}=h+1}^{H}}[\mathbbm{D}_{\pi_{h}}Q^{\pi}_{h}](s)+\rho\min_{a\in\mathcal{A}}\max_{\\{{\pi}_{h}\\}_{h^{\prime}=h+1}^{H}}Q^{\pi}_{h}(s,a)\\\
\leq&(1-\rho)\max_{{\pi}_{h}}[\mathbbm{D}_{\pi_{h}}Q^{*}_{h}](s)+\rho\min_{a\in\mathcal{A}}Q^{*}_{h}(s,a)\\\
=&(1-\rho)\max_{a\in\mathcal{A}}Q^{*}_{h}(s,a)+\rho\min_{a\in\mathcal{A}}Q^{*}_{h}(s,a).\end{split}$
(23)

We set $\pi^{*}_{h}(s)=\max_{a\in\mathcal{A}}Q^{*}_{h}(s,a)$. According to the
robust bellman equation, we have

$\begin{split}\max_{\pi}V^{\pi}_{h}(s)\geq
V^{\pi^{*}}_{h}(s)&=(1-\rho)[\mathbbm{D}_{\pi^{*}_{h}}Q^{\pi^{*}}_{h}](s)+\rho\min_{a\in\mathcal{A}}Q^{\pi^{*}}_{h}(s,a)\\\
&=(1-\rho)\max_{a\in\mathcal{A}}Q^{\pi^{*}}_{h}(s,a)+\rho\min_{a\in\mathcal{A}}Q^{\pi^{*}}_{h}(s,a)\\\
&=(1-\rho)\max_{a\in\mathcal{A}}Q^{*}_{h}(s,a)+\rho\min_{a\in\mathcal{A}}Q^{*}_{h}(s,a).\end{split}$
(24)

Thus, the robust Bellman optimality equation holds at step $h$. There always
exists an optimal robust policy
$\pi^{*}_{h}=\operatorname*{arg\,max}_{a\in\mathcal{A}}Q_{h}^{*}(s,a)$ and its
corresponding optimal adversarial policy
$\pi^{-}_{h}(s)=\operatorname*{arg\,min}_{a\in\mathcal{A}}Q_{h}^{*}(s,a)$
which is deterministic so that $C_{h}^{\pi^{*},\pi^{-},\rho}(s)=V_{h}^{*}(s)$.

Then, we prove the commutability of the expectation, the minimization and the
maximization operations at step $h$.

In the proof of robust Bellman equation, we have shown that

$\min_{\pi^{\prime}}\sum_{s}w(s)C_{h}^{\pi,\pi^{\prime},\rho}(s)=\sum_{s}w(s)\min_{\pi^{\prime}}C_{h}^{\pi,\pi^{\prime},\rho}(s)$

for any policy $\pi$ and any weighted function $w$. Hence

$\max_{\pi}\min_{\pi^{\prime}}\sum_{s}w(s)C_{h}^{\pi,\pi^{\prime},\rho}(s)\sum_{s}=\max_{\pi}\sum_{s}w(s)\min_{\pi^{\prime}}C_{h}^{\pi,\pi^{\prime},\rho}(s).$

First, we have

$\max_{\pi}\sum_{s}w(s)\min_{\pi^{\prime}}C_{h}^{\pi,\pi^{\prime},\rho}(s)\leq\sum_{s}w(s)\max_{\pi}\min_{\pi^{\prime}}C_{h}^{\pi,\pi^{\prime},\rho}(s).$

Then, we can show

$\displaystyle\max_{\pi}\sum_{s}w(s)\min_{\pi^{\prime}}C_{h}^{\pi,\pi^{\prime},\rho}(s)$
$\displaystyle\geq$
$\displaystyle\sum_{s}w(s)\min_{\pi^{\prime}}C_{h}^{\pi^{*},\pi^{\prime},\rho}(s)$
(25) $\displaystyle=$
$\displaystyle\sum_{s}w(s)C_{h}^{\pi^{*},\pi^{-},\rho}(s)$ $\displaystyle=$
$\displaystyle\sum_{s}w(s)\max_{\pi}\min_{\pi^{\prime}}C_{h}^{\pi,\pi^{\prime},\rho}(s).$

In summary,

$\max_{\pi}\min_{\pi^{\prime}}\sum_{s}w(s)C_{h}^{\pi,\pi^{\prime},\rho}(s)\sum_{s}=w(s)\max_{\pi}\min_{\pi^{\prime}}C_{h}^{\pi,\pi^{\prime},\rho}(s).$

We can show the perfect duality at step $h$ by

$\begin{split}\max_{\pi}\min_{\pi^{\prime}}C_{h}^{\pi,\pi^{\prime},\rho}(s)=C_{h}^{\pi^{*},\pi^{-},\rho}(s)=\max_{\pi}C_{h}^{\pi,\pi^{-},\rho}(s)\geq\min_{\pi^{\prime}}\max_{\pi}C_{h}^{\pi,\pi^{\prime},\rho}(s).\end{split}$
(26)

By induction on $h=H,\cdots,1$, we prove Theorem 1.

##  Appendix B Proof for Action Robust Reinforcement Learning with
Certificates

In this section, we prove Theorem 2. Recall that we use
$\overline{Q}_{h}^{k}$,$\overline{V}_{h}^{k}$,$\underline{Q}_{h}^{k}$,$\underline{V}_{h}^{k}$,
$N_{h}^{k}$, $\hat{P}_{h}^{k}$,$\hat{r}_{h}^{k}$ and $\theta_{h}^{k}$ to
denote the values of
$\overline{Q}_{h}$,$\overline{V}_{h}$,$\underline{Q}_{h}$,$\underline{V}_{h}$,
$\max\\{N_{h},1\\}$, $\hat{P}_{h}$, ${r}_{h}$ and $\theta_{h}$ at the
beginning of the $k$-th episode in Algorithm 1.

###  B.1 Proof of monotonicity

####  B.1.1 Proof of Lemma 1

When $N^{k}_{h}(s,a)\leq 1$, (8), (9) and (7) hold trivially by the bound of
the rewards and value functions.

For every $h\in[H]$ the empiric Bernstein inequality combined with a union
bound argument, to take into account that $N^{k}_{h}(s,a)>1$ is a random
number, leads to the following inequality w.p. $1-SAH\delta$ (see Theorem 4 in
[40])

$\begin{split}\left|(\hat{P}_{h}^{k}-P_{h})V^{*}_{h+1}(s,a)\right|\leq\sqrt{\frac{2\mathbbm{V}_{\hat{P}_{h}^{k}}V_{h+1}^{*}(s,a)\iota}{N_{h}^{k}(s,a)}}+\frac{7H\iota}{3(N_{h}^{k}(s,a))},\end{split}$
(27)

and

$\begin{split}\left|(\hat{P}_{h}^{k}-P_{h})V^{\overline{\pi}^{k}}_{h+1}(s,a)\right|\leq\sqrt{\frac{2\mathbbm{V}_{\hat{P}_{h}^{k}}V_{h+1}^{\overline{\pi}^{k}}(s,a)\iota}{N_{h}^{k}(s,a)}}+\frac{7H\iota}{3(N_{h}^{k}(s,a))}.\end{split}$
(28)

Similarly, with Azuma’s inequality, w.p. $1-SAH\delta$

$\left|\hat{r}_{h}^{k}(s,a)-R_{h}(s,a)\right|\leq\sqrt{\frac{2Var(r_{h}^{k}(s,a))\iota}{N_{h}^{k}(s,a)}}+\frac{7\iota}{3(N_{h}^{k}(s,a))}\leq\sqrt{\frac{2\hat{r}_{h}^{k}(s,a)\iota}{N_{h}^{k}(s,a)}}+\frac{7\iota}{3(N_{h}^{k}(s,a))},$
(29)

where $Var(r_{h}^{k}(s,a))$ is the empirical variance of $R_{h}(s,a)$ computed
by the $N_{h}^{k}(s,a)$ samples and
$Var(r_{h}^{k}(s,a))\leq\hat{r}_{h}^{k}(s,a)$ .

####  B.1.2 Proof of Lemma 2

We first prove that $\overline{Q}_{h}^{k}(s,a)\geq Q_{h}^{*}(s,a)$ for all
$(s,a,h,k)\in S\times A\times[H]\times[K]$, by backward induction conditioned
on the event $\mathcal{E}^{R}\cap\mathcal{E}^{PV}$. Firstly, the conclusion
holds for $h=H+1$ because $\overline{V}_{H+1}(s)=\underline{V}_{H+1}(s)=0$ and
$\overline{Q}_{H+1}(s,a)=\underline{Q}_{H+1}(s,a)=0$ for all $s$ and $a$. For
$h\in[H]$, assuming the conclusion holds for $h+1$, by Algorithm 1, we have

$\begin{split}&\hat{r}_{h}^{k}(s,a)+\hat{P}_{h}^{k}\overline{V}_{h+1}(s,a)+\theta_{h}^{k}(s,a)-Q_{h}^{*}(s,a)\\\
=&\hat{r}_{h}^{k}(s,a)+\hat{P}_{h}^{k}\overline{V}_{h+1}(s,a)+\theta_{h}^{k}(s,a)-R_{h}(s,a)-P_{h}V_{h+1}^{*}(s,a)\\\
=&\hat{r}_{h}^{k}(s,a)-R_{h}(s,a)+\hat{P}_{h}^{k}\left(\overline{V}_{h+1}-V_{h+1}^{*}\right)(s,a)+(\hat{P}_{h}^{k}-P_{h})V_{h+1}^{*}(s,a)+\theta_{h}^{k}(s,a)\\\
\geq&(\hat{P}_{h}^{k}-P_{h})V_{h+1}^{*}(s,a)+\sqrt{\frac{2\mathbbm{V}_{\hat{P}_{h}^{k}}[(\overline{V}^{k}_{h+1}+\underline{V}^{k}_{h+1})/2](s,a)\iota}{N_{h}^{k}(s,a)}}+\frac{\hat{P}_{h}^{k}\left(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1}\right)(s,a)}{H}+\frac{8H^{2}\iota}{N_{h}^{k}(s,a)}\\\
\geq&\sqrt{\frac{2\mathbbm{V}_{\hat{P}_{h}^{k}}[(\overline{V}^{k}_{h+1}+\underline{V}^{k}_{h+1})/2](s,a)\iota}{N_{h}^{k}(s,a)}}+\frac{\hat{P}_{h}^{k}\left(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1}\right)(s,a)}{H}+\frac{8H^{2}\iota}{N_{h}^{k}(s,a)}-\sqrt{\frac{2\mathbbm{V}_{\hat{P}_{h}^{k}}V_{h+1}^{*}(s,a)\iota}{N_{h}^{k}(s,a)}},\end{split}$
(30)

where the first inequality comes from event $\mathcal{E}^{R}$,
$\overline{V}_{h+1}(s)\geq V_{h+1}^{*}(s)$ and the definition of
$\theta_{h}^{k}(s,a)$ and the last inequality from event $\mathcal{E}^{PV}$.
By the relation of $V$-values in the step $(h+1)$,

$\begin{split}&\left|\mathbbm{V}_{\hat{P}_{h}^{k}}\left(\frac{\overline{V}^{k}_{h+1}+\underline{V}^{k}_{h+1}}{2}\right)(s,a)-\mathbbm{V}_{\hat{P}_{h}^{k}}V_{h+1}^{*}(s,a)\right|\\\
\leq&\left|[\hat{P}_{h}^{k}(\overline{V}^{k}_{h+1}+\underline{V}^{k}_{h+1})/2]^{2}-(\hat{P}_{h}^{k}V_{h+1}^{*})^{2}\right|(s,a)+\left|\hat{P}_{h}^{k}[(\overline{V}^{k}_{h+1}+\underline{V}^{k}_{h+1})/2]^{2}-\hat{P}_{h}^{k}(V_{h+1}^{*})^{2}\right|(s,a)\\\
\leq&4H\hat{P}_{h}^{k}\left|(\overline{V}^{k}_{h+1}+\underline{V}^{k}_{h+1})/2-V_{h+1}^{*}\right|(s,a)\\\
\leq&2H\hat{P}_{h}^{k}\left(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1}\right)(s,a)\end{split}$
(31)

and

$\begin{split}&\sqrt{\frac{2\mathbbm{V}_{\hat{P}_{h}^{k}}V_{h+1}^{*}(s,a)\iota}{N_{h}^{k}(s,a)}}\\\
\leq&\sqrt{\frac{2\mathbbm{V}_{\hat{P}_{h}^{k}}[(\overline{V}^{k}_{h+1}+\underline{V}^{k}_{h+1})/2](s,a)\iota+4H\hat{P}_{h}^{k}\left(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1}\right)(s,a)\iota}{N_{h}^{k}(s,a)}}\\\
\leq&\sqrt{\frac{2\mathbbm{V}_{\hat{P}_{h}^{k}}[(\overline{V}^{k}_{h+1}+\underline{V}^{k}_{h+1})/2](s,a)\iota}{N_{h}^{k}(s,a)}}+\sqrt{\frac{4H\hat{P}_{h}^{k}\left(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1}\right)(s,a)\iota}{N_{h}^{k}(s,a)}}\\\
\leq&\sqrt{\frac{2\mathbbm{V}_{\hat{P}_{h}^{k}}[(\overline{V}^{k}_{h+1}+\underline{V}^{k}_{h+1})/2](s,a)\iota}{N_{h}^{k}(s,a)}}+\frac{\hat{P}_{h}^{k}\left(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1}\right)(s,a)}{H}+\frac{8H^{2}\iota}{N_{h}^{k}(s,a)}.\end{split}$
(32)

Plugging (32) back into (30), we have
$\hat{r}_{h}^{k}(s,a)+\hat{P}_{h}^{k}\overline{V}_{h+1}(s,a)+\theta_{h}^{k}(s,a)\geq
Q_{h}^{*}(s,a)$. Thus,
$\overline{Q}_{h}^{k}(s,a)=\min\\{H-h+1,\hat{r}_{h}^{k}(s,a)+\hat{P}_{h}^{k}\overline{V}_{h+1}^{k}(s,a)+\theta_{h}^{k}(s,a)\\}\geq
Q_{h}^{*}(s,a)$.

From the definition of $\overline{V}_{h}^{k}(s)$ and $\overline{\pi}_{h}^{k}$,
we have

$\begin{split}\overline{V}_{h}^{k}(s)=&(1-\rho)\overline{Q}_{h}^{k}(s,\overline{\pi}_{h}^{k}(s))+\rho\overline{Q}_{h}^{k}(s,\underline{\pi}_{h}^{k}(s))\\\
\geq&(1-\rho)\overline{Q}_{h}^{k}(s,{\pi}_{h}^{*}(s))+\rho{Q}_{h}^{*}(s,\underline{\pi}_{h}^{k}(s))\\\
\geq&(1-\rho){Q}_{h}^{*}(s,{\pi}_{h}^{*}(s))+\rho\min_{a\in\mathcal{A}}{Q}_{h}^{*}(s,a)={V}_{h}^{*}(s).\end{split}$
(33)

Similarly, we can prove that $\underline{Q}_{h}^{k}(s,a)\leq
Q_{h}^{\overline{\pi}^{k}}(s,a)$ and $\underline{V}_{h}^{k}(s)\leq
V_{h}^{\overline{\pi}^{k}}(s)$.

$\begin{split}&\hat{r}_{h}^{k}(s,a)+\hat{P}_{h}^{k}\underline{V}_{h+1}(s,a)-\theta_{h}^{k}(s,a)-Q_{h}^{\overline{\pi}^{k}}(s,a)\\\
=&\hat{r}_{h}^{k}(s,a)+\hat{P}_{h}^{k}\underline{V}_{h+1}(s,a)-\theta_{h}^{k}(s,a)-R_{h}(s,a)-P_{h}V_{h+1}^{\overline{\pi}^{k}}(s,a)\\\
=&\hat{r}_{h}^{k}(s,a)-R_{h}(s,a)+\hat{P}_{h}^{k}\left(\underline{V}_{h+1}-V_{h+1}^{\overline{\pi}^{k}}\right)(s,a)+(\hat{P}_{h}^{k}-P_{h})V_{h+1}^{\overline{\pi}^{k}}(s,a)-\theta_{h}^{k}(s,a)\\\
\leq&(\hat{P}_{h}^{k}-P_{h})V_{h+1}^{\overline{\pi}^{k}}(s,a)-\sqrt{\frac{2\mathbbm{V}_{\hat{P}_{h}^{k}}[(\overline{V}^{k}_{h+1}+\underline{V}^{k}_{h+1})/2](s,a)\iota}{N_{h}^{k}(s,a)}}\\\
&-\frac{\hat{P}_{h}^{k}\left(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1}\right)(s,a)}{H}-\frac{8H^{2}\iota}{N_{h}^{k}(s,a)}\\\
\leq&\sqrt{\frac{2\mathbbm{V}_{\hat{P}_{h}^{k}}V_{h+1}^{\overline{\pi}^{k}}(s,a)\iota}{N_{h}^{k}(s,a)}}-\sqrt{\frac{2\mathbbm{V}_{\hat{P}_{h}^{k}}[(\overline{V}^{k}_{h+1}+\underline{V}^{k}_{h+1})/2](s,a)\iota}{N_{h}^{k}(s,a)}}\\\
&-\frac{\hat{P}_{h}^{k}\left(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1}\right)(s,a)}{H}-\frac{8H^{2}\iota}{N_{h}^{k}(s,a)}\leq
0,\end{split}$ (34)

and

$\begin{split}\underline{V}_{h}^{k}(s)=&(1-\rho)\underline{Q}_{h}^{k}(s,\overline{\pi}_{h}^{k}(s))+\rho\underline{Q}_{h}^{k}(s,\underline{\pi}_{h}^{k}(s))\\\
\leq&(1-\rho){Q}_{h}^{\overline{\pi}^{k}}(s,\overline{\pi}_{h}^{k}(s))+\rho\min_{a\in\mathcal{A}}\underline{Q}_{h}^{k}(s,a)\\\
\leq&(1-\rho){Q}_{h}^{\overline{\pi}^{k}}(s,\overline{\pi}_{h}^{k}(s))+\rho\underline{Q}_{h}^{k}(s,\operatorname*{arg\,min}_{a\in\mathcal{A}}{Q}_{h}^{\overline{\pi}^{k}}(s,a))\\\
\leq&(1-\rho){Q}_{h}^{\overline{\pi}^{k}}(s,\overline{\pi}_{h}^{k}(s))+\rho\min_{a\in\mathcal{A}}{Q}_{h}^{\overline{\pi}^{k}}(s,a)={V}_{h}^{\overline{\pi}^{k}}(s).\end{split}$
(35)

###  B.2 Regret Analysis

####  B.2.1 Proof of Lemma 3

We consider the event $\mathcal{E}^{R}\cap\mathcal{E}^{PV}$. The following
analysis will be done assuming the successful event
$\mathcal{E}^{R}\cap\mathcal{E}^{PV}$ holds. By Lemma 2, the regret can be
bounded by
$Regret(K):=\sum_{k=1}^{K}(V_{1}^{*}(s_{1}^{k})-{V}_{1}^{\overline{\pi}^{k}}(s_{1}^{k}))\leq\sum_{k=1}^{K}(\overline{V}_{1}^{k}(s_{1}^{k})-\underline{V}_{1}^{k}(s_{1}^{k}))$.

By the update steps in Algorithm 1, we have

$\begin{split}&\overline{V}_{h}^{k}(s_{h}^{k})-\underline{V}_{h}^{k}(s_{h}^{k})\\\
=&(1-\rho)\overline{Q}_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))+\rho\overline{Q}_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))-(1-\rho)\underline{Q}_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))-\rho\underline{Q}_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))\\\
\leq&[\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})](s_{h}^{k})+2\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}\theta_{h}(s_{h}^{k})\\\
=&[\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})](s_{h}^{k})-[\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})](s_{h}^{k},a_{h}^{k})+2\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}\theta_{h}(s_{h}^{k})\\\
&+[\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})](s_{h}^{k},a_{h}^{k})\\\
=&[\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})](s_{h}^{k})-[\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})](s_{h}^{k},a_{h}^{k})+2\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}\theta_{h}(s_{h}^{k})\\\
&+[\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})](s_{h}^{k},a_{h}^{k})-c_{1}{P}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})\\\
&+c_{1}{P}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})-c_{2}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h+1}^{k})+c_{2}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h+1}^{k})\\\
=&[\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})](s_{h}^{k})-[\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})](s_{h}^{k},a_{h}^{k})\\\
&+[\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})](s_{h}^{k},a_{h}^{k})-c_{1}{P}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})\\\
&+c_{1}{P}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})-c_{2}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h+1}^{k})+c_{2}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h+1}^{k})\\\
&+2(1-\rho)\sqrt{\frac{2\mathbbm{V}_{\hat{P}_{h}^{k}}[(\overline{V}^{k}_{h+1}+\underline{V}^{k}_{h+1})/2](s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}}+2(1-\rho)\sqrt{\frac{2\hat{r}_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}}\\\
&+(1-\rho)\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))/H+\frac{2(1-\rho)(24H^{2}+7H+7)\iota}{3N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k})))}\\\
&+2\rho\sqrt{\frac{2\mathbbm{V}_{\hat{P}_{h}^{k}}[(\overline{V}^{k}_{h+1}+\underline{V}^{k}_{h+1})/2](s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}}+2\rho\sqrt{\frac{2\hat{r}_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}}\\\
&+\rho\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))/H+\frac{2\rho(24H^{2}+7H+7)\iota}{3N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k})))}\\\
=&(1+1/H)[\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})](s_{h}^{k})-(1+1/H)[\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})](s_{h}^{k},a_{h}^{k})\\\
&+\underbrace{(1+1/H)[\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})](s_{h}^{k},a_{h}^{k})-c_{1}{P}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})}_{(a)}\\\
&+c_{1}{P}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})-c_{2}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h+1}^{k})+c_{2}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h+1}^{k})\\\
&+2(1-\rho)\underbrace{\sqrt{\frac{2\mathbbm{V}_{\hat{P}_{h}^{k}}[(\overline{V}^{k}_{h+1}+\underline{V}^{k}_{h+1})/2](s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}}}_{(b1)}+2(1-\rho)\sqrt{\frac{2\hat{r}_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}}\\\
&+\frac{2(1-\rho)(24H^{2}+7H+7)\iota}{3N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k})))}+2\rho\underbrace{\sqrt{\frac{2\mathbbm{V}_{\hat{P}_{h}^{k}}[(\overline{V}^{k}_{h+1}+\underline{V}^{k}_{h+1})/2](s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}}}_{(b2)}\\\
&+2\rho\sqrt{\frac{2\hat{r}_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}}+\frac{2\rho(24H^{2}+7H+7)\iota}{3N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k})))}.\end{split}$
(36)

##### Bound of the error of the empirical probability estimator (a)

By Bennett’s inequality, we have that w.p. $1-S\delta$

$|\hat{P}_{h}^{k}(s^{\prime}|s,a)-P_{h}(s^{\prime}|s,a)|\leq\sqrt{\frac{2P_{h}(s^{\prime}|s,a)\iota}{N_{h}^{k}(s,a)}}+\frac{\iota}{3N_{h}^{k}(s,a)}$
(37)

holds for all $s,a,h,k,s^{\prime}$.

Thus, we have that

$\begin{split}&(\hat{P}_{h}^{k}-P_{h})(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s,a)\\\
=&\sum_{s^{\prime}}(\hat{P}_{h}^{k}(s^{\prime}|s,a)-P_{h}(s^{\prime}|s,a))(\overline{V}_{h+1}^{k}(s^{\prime})-\underline{V}_{h+1}^{k}(s^{\prime}))\\\
\leq&\sum_{s^{\prime}}\sqrt{\frac{2P_{h}(s^{\prime}|s,a)\iota}{N_{h}^{k}(s,a)}}(\overline{V}_{h+1}^{k}(s^{\prime})-\underline{V}_{h+1}^{k}(s^{\prime}))+\frac{SH\iota}{3N_{h}^{k}(s,a)}\\\
\leq&\sum_{s^{\prime}}\left(\frac{P_{h}(s^{\prime}|s,a)\iota}{H}+\frac{H}{2N_{h}^{k}(s,a)}\right)\left(\overline{V}_{h+1}^{k}(s^{\prime})-\underline{V}_{h+1}^{k}(s^{\prime})\right)+\frac{SH\iota}{3N_{h}^{k}(s,a)}\\\
\leq&P_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s,a)/H+\frac{SH^{2}}{2N_{h}^{k}(s,a)}+\frac{SH\iota}{3N_{h}^{k}(s,a)}\\\
\leq&P_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s,a)/H+\frac{SH^{2}\iota}{N_{h}^{k}(s,a)},\end{split}$
(38)

where the second inequality is due to AM-GM inequality.

##### Bound of the error of the empirical variance estimator (b1) & (b2)

Here, we bound
$\mathbbm{V}_{\hat{P}_{h}^{k}}[(\overline{V}^{k}_{h+1}+\underline{V}^{k}_{h+1})/2](s_{h}^{k},a_{h}^{k})$.

Recall that
$C_{h}^{\pi,\pi^{\prime},\rho}(s)=\mathbb{E}\left[\sum_{h^{\prime}=h}^{H}R_{h^{\prime}}(s_{h^{\prime}},a_{h^{\prime}})|s_{h}=s,a_{h^{\prime}}\sim\widetilde{\pi}_{h^{\prime}}(\cdot|s_{h^{\prime}})\right]$
in Appendix A. Set ${\pi}^{k*}$ here is the optimal policy towards the
adversary policy $\underline{\pi}^{k}$ with
${\pi}^{k*}_{h}(s)=\operatorname*{arg\,max}_{\pi}{C}^{{\pi},\underline{\pi}^{k},\rho}_{h}(s)$.
Similar to the proof in Appendix B.1.2, we can show that
$\overline{V}_{h}^{k}(s)\geq{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h}(s)$.
We also have that
${C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h}(s)=\max_{\pi}{C}^{{\pi},\underline{\pi}^{k},\rho}_{h}(s)\geq{C}^{\overline{\pi}^{k},\underline{\pi}^{k},\rho}_{h}(s)\geq
V_{h}^{\overline{\pi}^{k}}(s)\geq\underline{V}_{h}^{k}(s)$ . For any
$(s,a,h,k)\in\mathcal{S}\times\mathcal{A}\times[H]\times[K]$, under event
$\mathcal{E}^{R}\cap\mathcal{E}^{PV}$,

$\begin{split}&\mathbbm{V}_{\hat{P}_{h}^{k}}[(\overline{V}^{k}_{h+1}+\underline{V}^{k}_{h+1})/2](s,a)-\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s,a)\\\
=&\hat{P}_{h}^{k}[(\overline{V}^{k}_{h+1}+\underline{V}^{k}_{h+1})/2]^{2}(s,a)-[\hat{P}_{h}^{k}(\overline{V}^{k}_{h+1}+\underline{V}^{k}_{h+1})/2]^{2}(s,a)\\\
&-{P}_{h}({C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1})^{2}(s,a)+({P}_{h}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1})^{2}(s,a)\\\
\leq&[\hat{P}_{h}^{k}(\overline{V}^{k}_{h+1})^{2}-(\hat{P}_{h}^{k}\underline{V}^{k}_{h+1})^{2}-P_{h}(\underline{V}^{k}_{h+1})^{2}+(P_{h}\overline{V}^{k}_{h+1})^{2}](s,a)\\\
\leq&|(\hat{P}_{h}^{k}-P_{h})(\overline{V}^{k}_{h+1})^{2}|(s,a)+|(P_{h}\underline{V}^{k}_{h+1})^{2}-(\hat{P}_{h}^{k}\underline{V}^{k}_{h+1})^{2}|(s,a)\\\
&+P_{h}|(\overline{V}^{k}_{h+1})^{2}-(\underline{V}^{k}_{h+1})^{2}|(s,a)+|(P_{h}\overline{V}^{k}_{h+1})^{2}-(P_{h}\underline{V}^{k}_{h+1})^{2}|(s,a),\end{split}$
(39)

where the first inequality is due
$\overline{V}_{h}^{k}(s)\geq{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h}(s)\geq\underline{V}_{h}^{k}(s)$.
The result of [41] combined with a union bound on $N^{k}_{h}(s,a)\in[K]$
implies w.p $1-\delta$

$\lVert\hat{P}_{h}^{k}(\cdot|s,a)-P_{h}(\cdot|s,a)\rVert_{1}\leq\sqrt{\frac{2S\iota}{N_{h}^{k}(s,a)}}$
(40)

holds for all $s,a,h,k$.

These terms can be bounded separately by

$\begin{split}&|(\hat{P}_{h}^{k}-P_{h})(\overline{V}^{k}_{h+1})^{2}|(s,a)\leq
H^{2}\sqrt{\frac{2S\iota}{N_{h}^{k}(s,a)}},\\\
&|(P_{h}\underline{V}^{k}_{h+1})^{2}-(\hat{P}_{h}^{k}\underline{V}^{k}_{h+1})^{2}|(s,a)\leq
2H|(P_{h}-\hat{P}_{h}^{k})\underline{V}^{k}_{h+1}|\leq
2H^{2}\sqrt{\frac{2S\iota}{N_{h}^{k}(s,a)}},\\\
&P_{h}|(\overline{V}^{k}_{h+1})^{2}-(\underline{V}^{k}_{h+1})^{2}|(s,a)\leq
2HP_{h}(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1})(s,a),\\\
&|(P_{h}\overline{V}^{k}_{h+1})^{2}-(P_{h}\underline{V}^{k}_{h+1})^{2}|(s,a)\leq
2HP_{h}(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1})(s,a),\end{split}$ (41)

where the first two inequality is due to (40). In addition,
$3H^{2}\sqrt{\frac{2S\iota}{N_{h}^{k}(s,a)}}\leq
1+\frac{9SH^{4}\iota}{2N_{h}^{k}(s,a)}$. Thus, we have

$\begin{split}&(1-\rho)\sqrt{\frac{\mathbbm{V}_{\hat{P}_{h}^{k}}[(\overline{V}^{k}_{h+1}+\underline{V}^{k}_{h+1})/2](s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}}+\rho\sqrt{\frac{\mathbbm{V}_{\hat{P}_{h}^{k}}[(\overline{V}^{k}_{h+1}+\underline{V}^{k}_{h+1})/2](s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}}\\\
\leq&(1-\rho)\sqrt{\frac{\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}}+\rho\sqrt{\frac{\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}}\\\
&+(1-\rho)\sqrt{\frac{4HP_{h}(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1})(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}}+\rho\sqrt{\frac{4HP_{h}(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1})(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}}\\\
&+(1-\rho)\sqrt{\frac{1}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}}+\rho\sqrt{\frac{1}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}}+\frac{(1-\rho)\sqrt{9SH^{4}\iota/2}}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}+\frac{\rho\sqrt{9SH^{4}\iota/2}}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}\\\
\leq&(1-\rho)\sqrt{\frac{\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}}+\rho\sqrt{\frac{\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}}\\\
&+(1-\rho)\left(\frac{P_{h}(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1})(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}{2\sqrt{2}H}+\frac{2\sqrt{2}H^{2}\iota}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}\right)\\\
&+\rho\left(\frac{P_{h}(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1})(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}{2\sqrt{2}H}+\frac{2\sqrt{2}H^{2}\iota}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}\right)\\\
&+(1-\rho)\sqrt{\frac{1}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}}+\rho\sqrt{\frac{1}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}}\\\
&+\frac{(1-\rho)\sqrt{9SH^{4}\iota/2}}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}+\frac{\rho\sqrt{9SH^{4}\iota/2}}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}\\\
=&(1-\rho)\sqrt{\frac{\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}}+\rho\sqrt{\frac{\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}}\\\
&+\frac{\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}P_{h}(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1})(s_{h}^{k})}{2\sqrt{2}H}+\frac{2\sqrt{2}(1-\rho)H^{2}\iota}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}+\frac{2\sqrt{2}\rho
H^{2}\iota}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}\\\
&+(1-\rho)\sqrt{\frac{1}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}}+\rho\sqrt{\frac{1}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}}\\\
&+\frac{(1-\rho)\sqrt{9SH^{4}\iota/2}}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}+\frac{\rho\sqrt{9SH^{4}\iota/2}}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))},\end{split}$
(42)

where the second inequality is due to AM-GM inequality.

##### Recursing on $h$

Plugging (38) and (42) into (36)and setting $c_{1}=1+1/H$ and
$c_{2}=(1+1/H)^{3}$ , we have

$\begin{split}&\overline{V}_{h}^{k}(s_{h}^{k})-\underline{V}_{h}^{k}(s_{h}^{k})\\\
\leq&(1+1/H)[\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})](s_{h}^{k})-(1+1/H)[\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})](s_{h}^{k},a_{h}^{k})\\\
\
&+(1/H+1/H^{2}){P}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})+\frac{(SH+SH^{2})\iota}{N_{h}^{k}(s_{h}^{k},a_{h}^{k})}\\\
&+c_{1}{P}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})-c_{2}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h+1}^{k})+c_{2}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h+1}^{k})\\\
&+2(1-\rho)\sqrt{\frac{2\hat{r}_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}}+\frac{2(1-\rho)(24H^{2}+7H+7)\iota}{3N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k})))}\\\
&+2\rho\sqrt{\frac{2\hat{r}_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}}+\frac{2\rho(24H^{2}+7H+7)\iota}{3N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k})))}\\\
&+(1-\rho)\sqrt{\frac{8\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}}+\rho\sqrt{\frac{8\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}}\\\
&+\frac{\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}P_{h}(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1})(s_{h}^{k})}{H}+\frac{8(1-\rho)H^{2}\iota}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}+\frac{8\rho
H^{2}\iota}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}\\\
&+(1-\rho)\sqrt{\frac{8}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}}+\rho\sqrt{\frac{8}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}}+\frac{6(1-\rho)\sqrt{SH^{4}\iota}}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}+\frac{6\rho\sqrt{SH^{4}\iota}}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}.\end{split}$
(43)

We set
$\Theta_{h}^{k}(s,a)=\sqrt{\frac{8\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s,a)\iota}{N_{h}^{k}(s,a)}}+\sqrt{\frac{32}{N_{h}^{k}(s,a)}}+\frac{46\sqrt{SH^{4}\iota}}{N_{h}^{k}(s,a)}$.
Since $r_{h}^{k}(s,a)\leq 1$, by organizing the items, we have that

$\begin{split}&\overline{V}_{h}^{k}(s_{h}^{k})-\underline{V}_{h}^{k}(s_{h}^{k})\\\
\leq&(1+1/H)[\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})](s_{h}^{k})-(1+1/H)[\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})](s_{h}^{k},a_{h}^{k})\\\
&+(1/H+1/H^{2}){P}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})+\frac{(SH+SH^{2})\iota}{N_{h}^{k}(s_{h}^{k},a_{h}^{k})}\\\
&+c_{1}{P}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})-c_{2}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h+1}^{k})+c_{2}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h+1}^{k})\\\
&+\frac{\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}P_{h}(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1})(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}{H}+\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}\Theta_{h}^{k}(s_{h}^{k})\\\
\leq&(1+1/H)[\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})](s_{h}^{k})-(1+1/H)[\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})](s_{h}^{k},a_{h}^{k})\\\
&+\frac{1}{H}[\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}P_{h}(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1})(s_{h}^{k})-{P}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})]\\\
&+(1+3/H+1/H^{2}){P}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})-c_{2}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h+1}^{k})\\\
&+c_{2}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h+1}^{k})+\frac{(SH+SH^{2})\iota}{N_{h}^{k}(s_{h}^{k},a_{h}^{k})}+\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}\Theta_{h}^{k}(s_{h}^{k})\\\
\leq&(1+1/H)[\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})](s_{h}^{k})-(1+1/H)[\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})](s_{h}^{k},a_{h}^{k})\\\
&+\frac{1}{H}[\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}P_{h}(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1})(s_{h}^{k})-{P}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})]\\\
&+c_{2}{P}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})-c_{2}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h+1}^{k})\\\
&+c_{2}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h+1}^{k})+\frac{(SH+SH^{2})\iota}{N_{h}^{k}(s_{h}^{k},a_{h}^{k})}+\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}\Theta_{h}^{k}(s_{h}^{k}).\end{split}$
(44)

By induction of (36) on $h=1,\cdots,H$ and
$\overline{V}_{h+1}^{k}=\underline{V}_{h+1}^{k}=0$, we have that

$\begin{split}Regret(K)\leq
21\sum_{k=1}^{K}\sum_{h=1}^{H}(&\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}\hat{P}_{h}^{k}(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1})(s_{h}^{k})-\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})\\\
&+\frac{1}{H}[\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}P_{h}(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1})(s_{h}^{k})-{P}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})]\\\
&+{P}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})-(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h+1}^{k})\\\
&+\frac{(SH+SH^{2})\iota}{N_{h}^{k}(s_{h}^{k},a_{h}^{k})}+\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}\Theta_{h}^{k}(s_{h}^{k})).\end{split}$
(45)

Here we use $(1+1/H)^{3}H<21$.

####  B.2.2 Proof of Lemma 4

Recall that
$M_{1}=\sum_{k=1}^{K}\sum_{h=1}^{H}[\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}\hat{P}_{h}^{k}(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1})(s_{h}^{k})-\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})]$.

Since
$\mathbbm{E}_{a_{h}^{k}\sim\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}}[\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})]=\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}\hat{P}_{h}^{k}(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1})(s_{h}^{k})$,
we have that
$\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}\hat{P}_{h}^{k}(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1})(s_{h}^{k})-\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})$
is a martingale difference sequence. By the Azuma-Hoeffding inequality, with
probability $1-\delta$, we have

$\left|\sum_{k=1}^{K}\sum_{h=1}^{H}[\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}\hat{P}_{h}^{k}(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1})(s_{h}^{k})-\hat{P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})]\right|\leq
H\sqrt{2HK\iota}.$ (46)

####  B.2.3 Proof of Lemma 5

Recall that
$M_{2}=\sum_{k=1}^{K}\sum_{h=1}^{H}\frac{1}{H}[\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}P_{h}(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1})(s_{h}^{k})-{P}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})]$.

Since
$\mathbbm{E}_{a_{h}^{k}\sim\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}}[{P}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})]=\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}P_{h}(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1})(s_{h}^{k})$,
we have that
$\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}P_{h}(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1})(s_{h}^{k})-{P}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})$
is a martingale difference sequence. By the Azuma-Hoeffding inequality, with
probability $1-\delta$, we have

$\left|\sum_{k=1}^{K}\sum_{h=1}^{H}[\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}P_{h}(\overline{V}^{k}_{h+1}-\underline{V}^{k}_{h+1})(s_{h}^{k})-{P}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})]\right|\leq
H\sqrt{2HK\iota}.$ (47)

####  B.2.4 Proof of Lemma 6

Recall that
$M_{3}=\sum_{k=1}^{K}\sum_{h=1}^{H}({P}_{h}^{k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})-(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h+1}^{k}))$.

Let the one-hot vector $\hat{\mathbbm{1}}^{k}_{h}(\cdot|s_{h}^{k},a_{h}^{k})$
to satisfy that $\hat{\mathbbm{1}}^{k}_{h}(s_{h+1}^{k}|s_{h}^{k},a_{h}^{k})=1$
and $\hat{\mathbbm{1}}^{k}_{h}(s|s_{h}^{k},a_{h}^{k})=0$ for $s\neq
s_{h+1}^{k}$. Thus,
$[({P}_{h}^{k}-\hat{\mathbbm{1}}^{k}_{h})(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})](s_{h}^{k},a_{h}^{k})$
is a martingale difference sequence. By the Azuma-Hoeffding inequality, with
probability $1-\delta$, we have

$\left|\sum_{k=1}^{K}\sum_{h=1}^{H}[({P}_{h}^{k}-\hat{\mathbbm{1}}^{k}_{h})(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})](s_{h}^{k},a_{h}^{k})\right|\leq
H\sqrt{2HK\iota}.$ (48)

####  B.2.5 Proof of Lemma 7

We bounded
$M_{4}=\sum_{k=1}^{K}\sum_{h=1}^{H}[\frac{(SH+SH^{2})\iota}{N_{h}^{k}(s_{h}^{k},a_{h}^{k})}+\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}\Theta_{h}^{k}(s_{h}^{k})]$
by separately bounding the four items.

##### Bound
$\sum_{k=1}^{K}\sum_{h=1}^{H}\frac{(SH+SH^{2})\iota}{N_{h}^{k}(s_{h}^{k},a_{h}^{k})}$

We regroup the summands in a different way.

$\begin{split}\sum_{k=1}^{K}\sum_{h=1}^{H}\frac{(SH+SH^{2})\iota}{N_{h}^{k}(s_{h}^{k},a_{h}^{k})}=(SH+SH^{2})\iota\sum_{h=1}^{H}\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}\sum_{n=1}^{N_{h}^{K}(s,a)}\frac{1}{n}\leq(SH+SH^{2})SAH\iota^{2}.\end{split}$
(49)

Recall that
$\Theta_{h}^{k}(s,a)=\sqrt{\frac{8\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s,a)\iota}{N_{h}^{k}(s,a)}}+\sqrt{\frac{32}{N_{h}^{k}(s,a)}}+\frac{46\sqrt{SH^{4}\iota}}{N_{h}^{k}(s,a)}$.

##### Bound
$\sum_{k=1}^{K}\sum_{h=1}^{H}[(1-\rho)\sqrt{\frac{32\iota}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}}+\rho\sqrt{\frac{32\iota}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}}]$

We regroup the summands in a different way. For any policy $\pi$, we have

$\begin{split}\sum_{k=1}^{K}\sum_{h=1}^{H}\sqrt{\frac{32\iota}{N_{h}^{k}(s_{h}^{k},\pi(s_{h}^{k}))}}=\sum_{h=1}^{H}\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}\sum_{n=1}^{N_{h}^{K}(s,a)}\sqrt{\frac{32\iota}{n}}\leq
8H\sqrt{SAK\iota}.\end{split}$ (50)

##### Bound
$\sum_{k=1}^{K}\sum_{h=1}^{H}[(1-\rho)\frac{46SH^{2}\iota}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}+\rho\frac{46SH^{2}\iota}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}]$

We regroup the summands in a different way. For any policy $\pi$, we have

$\begin{split}\sum_{k=1}^{K}\sum_{h=1}^{H}\frac{46\sqrt{SH^{4}\iota}}{N_{h}^{k}(s_{h}^{k},\pi(s_{h}^{k}))}=46\sqrt{SH^{4}\iota}\sum_{h=1}^{H}\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}\sum_{n=1}^{N_{h}^{K}(s,a)}\frac{1}{n}\leq
46S^{\frac{3}{2}}AH^{3}\iota^{2}.\end{split}$ (51)

##### Bound
$\sum_{k=1}^{K}\sum_{h=1}^{H}\left[(1-\rho)\sqrt{\frac{8\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}}+\rho\sqrt{\frac{8\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}}\right]$

By Cauchy-Schwarz inequality,

$\begin{split}&\sum_{k=1}^{K}\sum_{h=1}^{H}\sqrt{\frac{\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}}\\\
\leq&\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))\cdot\sum_{k=1}^{K}\sum_{h=1}^{H}\frac{\iota}{N_{h}^{k}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}}\\\
\leq&\sqrt{SAH\iota^{2}\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}.\end{split}$
(52)

Similarly,

$\begin{split}&\sum_{k=1}^{K}\sum_{h=1}^{H}\sqrt{\frac{\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))\iota}{N_{h}^{k}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}}\\\
\leq&\sqrt{SAH\iota^{2}\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}.\end{split}$
(53)

By $(1-\rho)a^{2}+\rho b^{2}\geq((1-\rho)a+\rho b)^{2}$,

$\begin{split}&(1-\rho)\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))}+\rho\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))}\\\
\leq&\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}[(1-\rho)\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))+\rho\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))]}.\end{split}$
(54)

Now we bound the total variance. Let
$\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}P_{h}(s^{\prime}|s)=(1-\rho)P_{h}(s^{\prime}|s,\overline{\pi}_{h}^{k}(s)+\rho
P_{h}(s^{\prime}|s,\underline{\pi}_{h}^{k}(s))$,

$\begin{split}[\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}P_{h}V_{h+1}](s)=&\sum_{s^{\prime}}[(1-\rho)P_{h}(s^{\prime}|s,\overline{\pi}_{h}^{k}(s))+\rho
P_{h}(s^{\prime}|s,\underline{\pi}_{h}^{k}(s))]V_{h+1}(s^{\prime}),\end{split}$
(55)

and

$\begin{split}\mathbbm{V}_{[\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}P_{h}]}V_{h+1}(s)=&\sum_{s^{\prime}}[(1-\rho)P_{h}(s^{\prime}|s,\overline{\pi}_{h}^{k}(s))+\rho
P_{h}(s^{\prime}|s,\underline{\pi}_{h}^{k}(s))][V_{h+1}(s^{\prime})]^{2}\\\
&-[\sum_{s^{\prime}}\left((1-\rho)P_{h}(s^{\prime}|s,\overline{\pi}_{h}^{k}(s))+\rho
P_{h}(s^{\prime}|s,\underline{\pi}_{h}^{k}(s))\right)V_{h+1}(s^{\prime})]^{2}.\end{split}$
(56)

We have that

$\begin{split}&\mathbbm{V}_{[\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}P_{h}]}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k})\\\
=&\sum_{s^{\prime}}[(1-\rho)P_{h}(s^{\prime}|s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))+\rho
P_{h}(s^{\prime}|s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))][{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s^{\prime})]^{2}\\\
&-[\sum_{s^{\prime}}\left((1-\rho)P_{h}(s^{\prime}|s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))+\rho
P_{h}(s^{\prime}|s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))\right){C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s^{\prime})]^{2}\\\
\geq&(1-\rho)\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))+\rho\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))\\\
&+(1-\rho)[P_{h}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))]^{2}+\rho
P_{h}[{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k}))]^{2}\\\
&-[\sum_{s^{\prime}}(1-\rho)P_{h}(s^{\prime}|s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k})){C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s^{\prime})+\rho
P_{h}(s^{\prime}|s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k})){C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s^{\prime})]^{2}\\\
\geq&(1-\rho)\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},\overline{\pi}_{h}^{k}(s_{h}^{k}))+\rho\mathbbm{V}_{{P}_{h}}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},\underline{\pi}_{h}^{k}(s_{h}^{k})),\end{split}$
(57)

where the last inequality is due to $(1-\rho)a^{2}+\rho
b^{2}\geq((1-\rho)a+\rho b)^{2}$.

With probability $1-2\delta$, we also have that

$\begin{split}&\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbbm{V}_{[\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}P_{h}]}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k})\\\
=&\sum_{k=1}^{K}\sum_{h=1}^{H}\left([\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}P_{h}({C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1})^{2}](s_{h}^{k})-\left([\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}P_{h}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}](s_{h}^{k})\right)^{2}\right)\\\
=&\sum_{k=1}^{K}\sum_{h=1}^{H}\left([\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}P_{h}({C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1})^{2}](s_{h}^{k})-\left({C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h+1}^{k})\right)^{2}\right)\\\
&+\sum_{k=1}^{K}\sum_{h=1}^{H}\left(\left({C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h+1}^{k})\right)^{2}-\left([\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}P_{h}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}](s_{h}^{k})\right)^{2}\right)\\\
\leq&H^{2}\sqrt{2HK\iota}+\sum_{k=1}^{K}\sum_{h=1}^{H}\left(({C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h}(s_{h}^{k}))^{2}-\left([\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}P_{h}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}](s_{h}^{k})\right)^{2}\right)-\sum_{k=1}^{K}({C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{1}(s_{1}^{k}))^{2}\\\
\leq&H^{2}\sqrt{2HK\iota}+2H\sum_{k=1}^{K}\sum_{h=1}^{H}|{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h}(s_{h}^{k})-\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}{P}_{h}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k})|\\\
\leq&H^{2}\sqrt{2HK\iota}+2H\sum_{k=1}^{K}\left({C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{1}(s_{1}^{k})+\sum_{h=1}^{H}\left({C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h+1}^{k})-\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}{P}_{h}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k},a_{h}^{k})\right)\right)\\\
\leq&H^{2}\sqrt{2HK\iota}+2H^{2}K+2H^{2}\sqrt{2HK\iota}\\\
\leq&3H^{2}K+9H^{3}\iota/2,\\\ \end{split}$ (58)

where the first inequality holds with probability $1-\delta$ by Azuma-
Hoeffding inequality, the second inequality is due to the bound of V-values,
the third inequality is due to Lemma 2 so that
${C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h}(s_{h}^{k})\geq\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}D_{h}^{{\pi}^{k*},\underline{\pi}^{k},\rho}(s_{h}^{k})\geq\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}{P}_{h}{C}^{{\pi}^{k*},\underline{\pi}^{k},\rho}_{h+1}(s_{h}^{k})$,
the fourth inequality holds with probability $1-\delta$ by Azuma-Hoeffding
inequality, and the last inequality holds with $2ab\leq a^{2}+b^{2}$.

In summary, with probability at least $1-\delta$, we have
$\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbbm{V}_{{P}_{h}}{V}^{\overline{\pi}^{k}}_{h+1}(s_{h}^{k},a_{h}^{k})\leq(H^{2}K+H^{3}\iota)$.

In summary,
$\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}\Theta_{h}^{k}(s_{h}^{k})\leq
8\sqrt{SAH^{2}K\iota}+46S^{\frac{3}{2}}AH^{3}\iota^{2}+\sqrt{24SAH^{3}K\iota^{2}+36SAH^{5}\iota^{2}}\leq
8\sqrt{SAH^{2}K\iota}+46S^{\frac{3}{2}}AH^{3}\iota^{2}+\sqrt{24SAH^{3}K}\iota+6\sqrt{SAH^{5}}\iota$.

##  Appendix C Proof for model-free algorithm

In this section, we prove Theorem 3. Recall that we use
$\overline{Q}_{h}^{k}$,$\overline{V}_{h}^{k}$,$\underline{Q}_{h}^{k}$,$\underline{V}_{h}^{k}$
and $N_{h}^{k}$ to denote the values of
$\overline{Q}_{h}$,$\overline{V}_{h}$,$\underline{Q}_{h}$,$\underline{V}_{h}$
and $\max\\{N_{h},1\\}$ at the beginning of the $k$-th episode.

##### Property of learning rate $\alpha_{t}$

We refer the readers to the setting of the learning rate
$\alpha_{t}:=\frac{H+1}{H+t}$ and the Lemma 4.1 in [30]. For notational
convenience, define $\alpha_{t}^{0}:=\prod_{j=1}^{t}(1-\alpha_{t})$ and
$\alpha_{t}^{i}:=\alpha_{i}\prod_{j=i+1}^{t}(1-\alpha_{t})$. Here, we
introduce some useful properties of $\alpha_{t}^{i}$ which were proved in
[30]:
(1) $\sum_{i=1}^{t}\alpha_{t}^{i}=1$ and $\alpha_{t}^{0}=0$ for $t\geq 1$;
(2) $\sum_{i=1}^{t}\alpha_{t}^{i}=0$ and $\alpha_{t}^{0}=1$ for $t=0$;
(3)
$\frac{1}{\sqrt{t}}\leq\sum_{i=1}^{t}\frac{\alpha_{t}^{i}}{\sqrt{t}}\leq\frac{2}{\sqrt{t}}$
for every $t\geq 1$;
(4) $\sum_{i=1}^{t}(\alpha_{t}^{i})^{2}\leq\frac{2H}{t}$ for every $t\geq 1$;
(5) $\sum_{t=i}^{\infty}\alpha_{t}^{i}\leq(1+\frac{1}{H})$ for every $i\geq
1$.

##### Recursion on $Q$

As shown in [30], at any
$(s,a,h,k)\in\mathcal{S}\times\mathcal{A}\times[H]\times[K]$, let
$t={N}_{h}^{k}(s,a)$ and suppose $(s,a)$ was previously taken by the agent at
step $h$ of episodes $k_{1},k_{2},\dots,k_{t}<k$. By the update equations in
Algorithm 2 and the definition of $\alpha_{t}^{i}$, we have

$\begin{split}&\overline{Q}_{h}^{k}(s,a)=\alpha_{t}^{0}(H-h+1)+\sum_{i=1}^{t}\alpha_{t}^{i}\left(r_{h}^{k_{i}}+\overline{V}_{h+1}^{k_{i}}(s_{h+1}^{k_{i}})+b_{i}\right);\\\
&\underline{Q}_{h}^{k}(s,a)=\sum_{i=1}^{t}\alpha_{t}^{i}\left(r_{h}^{k_{i}}+\underline{V}_{h+1}^{k_{i}}(s_{h+1}^{k_{i}})-b_{i}\right).\end{split}$
(59)

Thus,

$\begin{split}(\overline{Q}_{h}^{k}-Q^{*}_{h})(s,a)=&\alpha_{t}^{0}(H-h+1)+\sum_{i=1}^{t}\alpha_{t}^{i}\left(r_{h}^{k_{i}}+\overline{V}_{h+1}^{k_{i}}(s_{h+1}^{k_{i}})+b_{i}\right)\\\
&-\left(\alpha_{t}^{0}Q^{*}_{h}(s,a)+\sum_{i=1}^{t}\alpha_{t}^{i}\left(R_{h}(s,a)+P_{h}{V}_{h+1}^{*}(s,a)\right)\right)\\\
=&\alpha_{t}^{0}(H-h+1-Q^{*}_{h}(s,a))+\sum_{i=1}^{t}\alpha_{t}^{i}\left((\overline{V}_{h+1}^{k_{i}}-{V}_{h+1}^{*})(s_{h+1}^{k_{i}})\right)\\\
&+\sum_{i=1}^{t}\alpha_{t}^{i}\left((r_{h}^{k_{i}}-R_{h}(s,a))+{V}_{h+1}^{*}(s_{h+1}^{k_{i}})-P_{h}{V}_{h+1}^{*}(s,a)+b_{i}\right),\end{split}$
(60)

and similarly

$\begin{split}(\underline{Q}_{h}^{k}-Q^{\overline{\pi}^{k}}_{h})(s,a)=&\sum_{i=1}^{t}\alpha_{t}^{i}\left(r_{h}^{k_{i}}+\underline{V}_{h+1}^{k_{i}}(s_{h+1}^{k_{i}})-b_{i}\right)\\\
&-\left(\alpha_{t}^{0}Q^{\overline{\pi}^{k}}_{h}(s,a)+\sum_{i=1}^{t}\alpha_{t}^{i}\left(R_{h}(s,a)+P_{h}{V}_{h+1}^{\overline{\pi}^{k}}(s,a)\right)\right)\\\
=&-\alpha_{t}^{0}Q^{\overline{\pi}^{k}}_{h}(s,a)+\sum_{i=1}^{t}\alpha_{t}^{i}\left([P_{h}(\underline{V}_{h+1}^{k_{i}}-{V}_{h+1}^{\overline{\pi}^{k}})](s,a)\right)\\\
&+\sum_{i=1}^{t}\alpha_{t}^{i}\left((r_{h}^{k_{i}}-R_{h}(s,a))+\underline{V}_{h+1}^{k_{i}}(s_{h+1}^{k_{i}})-P_{h}\underline{V}_{h+1}^{k_{i}}(s,a)-b_{i}\right).\end{split}$
(61)

In addition, for any $k^{\prime}\leq k$, let
$t^{\prime}={N}_{h}^{k^{\prime}}(s,a)$. Thus, $(s,a)$ was previously taken by
the agent at step $h$ of episodes
$k_{1},k_{2},\dots,k_{t^{\prime}}<k^{\prime}$. We have

$\begin{split}(\underline{Q}_{h}^{k^{\prime}}-Q^{\overline{\pi}^{k}}_{h})(s,a)=&-\alpha_{t}^{0}Q^{\overline{\pi}^{k}}_{h}(s,a)+\sum_{i=1}^{t^{\prime}}\alpha_{t^{\prime}}^{i}\left([P_{h}(\underline{V}_{h+1}^{k_{i}}-{V}_{h+1}^{\overline{\pi}^{k}})](s,a)\right)\\\
&+\sum_{i=1}^{t^{\prime}}\alpha_{t^{\prime}}^{i}\left((r_{h}^{k_{i}}-R_{h}(s,a))+\underline{V}_{h+1}^{k_{i}}(s_{h+1}^{k_{i}})-P_{h}\underline{V}_{h+1}^{k_{i}}(s,a)-b_{i}\right).\end{split}$
(62)

##### Confidence bounds

By the Azuma-Hoeffding inequality, with probability $1-\delta$, we have that
for all $s$, $a$, $h$ and $t\leq K$,

$\left|\sum_{i=1}^{t}\alpha_{t}^{i}\left((r_{h}^{k_{i}}-R_{h}(s,a))+\underline{V}_{h+1}^{k_{i}}(s_{h+1}^{k_{i}})-P_{h}\underline{V}_{h+1}^{k_{i}}(s,a)\right)\right|\leq
H\sqrt{\sum_{i=1}^{t}(\alpha_{t}^{i})^{2}\iota/2}\leq\sqrt{H^{3}\iota/t}.$
(63)

At the same time, with probability $1-\delta$, we have that for all $s$, $a$,
$h$ and $t\leq K$,

$\left|\sum_{i=1}^{t}\alpha_{t}^{i}\left((r_{h}^{k_{i}}-R_{h}(s,a))+{V}_{h+1}^{*}(s_{h+1}^{k_{i}})-P_{h}{V}_{h+1}^{*}(s,a)\right)\right|\leq\sqrt{H^{3}\iota/t}.$
(64)

In addition, we have
$\sqrt{H^{3}\iota/t}\leq\sum_{i=1}^{t}\alpha_{t}^{i}b_{i}\leq
2\sqrt{H^{3}\iota/t}$.

##### Monotonicity

Now we prove that $\overline{V}_{h}^{k}(s)\geq V_{h}^{*}(s)\geq
V_{h}^{\overline{\pi}^{k}}(s)\geq\underline{V}_{h}^{k}(s)$ and
$\overline{Q}_{h}^{k}(s,a)\geq Q_{h}^{*}(s,a)\geq
Q_{h}^{\overline{\pi}^{k}}(s,a)\geq\underline{Q}_{h}^{k}(s,a)$ for all
$(s,a,h,k)\in S\times A\times[H]\times[K]$.

At step $H+1$, we have
$\overline{V}_{H+1}^{k}(s)=V_{H+1}^{*}(s)=V_{H+1}^{\overline{\pi}^{k}}(s)=\underline{V}_{H+1}^{k}(s)=0$
and
$\overline{Q}_{H+1}^{k}(s,a)=Q_{H+1}^{*}(s,a)=Q_{H+1}^{\overline{\pi}^{k}}(s,a)=\underline{Q}_{H+1}^{k}(s,a)=0$
for all $(s,a,k)\in S\times A\times[K]$.

Consider any step $h\in[H]$ in any episode $k\in[K]$, and suppose that the
monotonicity is satisfied for all previous episodes as well as all steps
$h^{\prime}\geq h+1$ in the current episode, which is

$\begin{split}&\overline{V}_{h^{\prime}}^{k^{\prime}}(s)\geq
V_{h^{\prime}}^{*}(s)\geq
V_{h^{\prime}}^{\overline{\pi}^{k^{\prime}}}(s)\geq\underline{V}_{h^{\prime}}^{k^{\prime}}(s)~{}\forall(k^{\prime},h^{\prime},s)\in[k-1]\times[H+1]\times\mathcal{S},\\\
&\overline{Q}_{h^{\prime}}^{k^{\prime}}(s,a)\geq Q_{h^{\prime}}^{*}(s,a)\geq
Q_{h^{\prime}}^{\overline{\pi}^{k^{\prime}}}(s,a)\geq\underline{Q}_{h^{\prime}}^{k^{\prime}}(s,a)~{}\forall(k^{\prime},h^{\prime},s,a)\in[k-1]\times[H+1]\times\mathcal{S}\times\mathcal{A},\\\
&\overline{V}_{h^{\prime}}^{k}(s)\geq V_{h^{\prime}}^{*}(s)\geq
V_{h^{\prime}}^{\overline{\pi}^{k}}(s)\geq\underline{V}_{h^{\prime}}^{k}(s)~{}\forall
h^{\prime}\geq h+1~{}\text{and}~{}s\in\mathcal{S},\\\
&\overline{Q}_{h^{\prime}}^{k}(s,a)\geq Q_{h^{\prime}}^{*}(s,a)\geq
Q_{h^{\prime}}^{\overline{\pi}^{k}}(s,a)\geq\underline{Q}_{h^{\prime}}^{k}(s,a)~{}\forall
h^{\prime}\geq
h+1~{}\text{and}~{}(s,a)\in\mathcal{S}\times\mathcal{A}.\end{split}$ (65)

We first show the monotonicity of $Q$ values. We have

$\begin{split}(\overline{Q}_{h}^{k}-Q^{*}_{h})(s,a)\geq\alpha_{t}^{0}(H-h+1-Q^{*}_{h}(s,a))+\sum_{i=1}^{t}\alpha_{t}^{i}\left((\overline{V}_{h+1}^{k_{i}}-{V}_{h+1}^{*})(s_{h+1}^{k_{i}})\right)\geq
0,\end{split}$ (66)

and, by to the update rule of $\underline{V}$ values (line 13) in Algorithm 2,

$\begin{split}(\underline{Q}_{h}^{k}-Q^{\overline{\pi}^{k}}_{h})(s,a)\leq&-\alpha_{t}^{0}Q^{\overline{\pi}^{k}}_{h}(s,a)+\sum_{i=1}^{t}\alpha_{t}^{i}\left([P_{h}(\underline{V}_{h+1}^{k_{i}}-{V}_{h+1}^{\overline{\pi}^{k}})](s,a)\right)\\\
\leq&-\alpha_{t}^{0}Q^{\overline{\pi}^{k}}_{h}(s,a)+\sum_{i=1}^{t}\alpha_{t}^{i}\left([P_{h}(\underline{V}_{h+1}^{k}-{V}_{h+1}^{\overline{\pi}^{k}})](s,a)\right)\leq
0.\end{split}$ (67)

In addition, for any $k^{\prime}\leq k$,

$\begin{split}(\underline{Q}_{h}^{k^{\prime}}-Q^{\overline{\pi}^{k}}_{h})(s,a)\leq&-\alpha_{t}^{0}Q^{\overline{\pi}^{k}}_{h}(s,a)+\sum_{i=1}^{t^{\prime}}\alpha_{t^{\prime}}^{i}\left([P_{h}(\underline{V}_{h+1}^{k_{i}}-{V}_{h+1}^{\overline{\pi}^{k}})](s,a)\right)\\\
\leq&-\alpha_{t}^{0}Q^{\overline{\pi}^{k}}_{h}(s,a)+\sum_{i=1}^{t^{\prime}}\alpha_{t^{\prime}}^{i}\left([P_{h}(\underline{V}_{h+1}^{k}-{V}_{h+1}^{\overline{\pi}^{k}})](s,a)\right)\leq
0.\end{split}$ (68)

Then, we show the monotonicity of $V$ values. We have that

$\begin{split}&(1-\rho)\max_{a}\overline{Q}_{h}^{k}(s,a)+\rho\overline{Q}_{h}^{k}(s,\operatorname*{arg\,min}_{a}\underline{Q}_{h}^{k}(s,a))\\\
\geq&(1-\rho)\max_{a}\overline{Q}_{h}^{k}(s,a)+\rho{Q}_{h}^{*}(s,\operatorname*{arg\,min}_{a}\underline{Q}_{h}^{k}(s,a))\\\
\geq&(1-\rho)\overline{Q}_{h}^{k}(s,{\pi}_{h}^{*}(s))+\rho\min_{a\in\mathcal{A}}{Q}_{h}^{*}(s,a)\\\
\geq&(1-\rho){Q}_{h}^{*}(s,{\pi}_{h}^{*}(s))+\rho\min_{a\in\mathcal{A}}{Q}_{h}^{*}(s,a)={V}_{h}^{*}(s).\end{split}$
(69)

By the update rule of $\overline{V}$ values (line 12) in Algorithm 2,

$\overline{V}_{h}^{k}(s)=\min\\{\overline{V}_{h}^{k-1}(s),(1-\rho)\max_{a}\overline{Q}_{h}^{k}(s,a)+\rho\overline{Q}_{h}^{k}(s,\operatorname*{arg\,min}_{a}\underline{Q}_{h}^{k}(s,a))\\}\geq{V}_{h}^{*}(s).$
(70)

Here, we need use the update rule of policy $\underline{\pi}$ (line 11-16) in
Algorithm 2. Define
${\tau}(k,h,s):=\max\\{k^{\prime}:k^{\prime}<k~{}\text{and}~{}\underline{V}_{h}^{k^{\prime}+1}(s)=(1-\rho)\underline{Q}_{h}^{k^{\prime}+1}(s,\operatorname*{arg\,max}_{a}\overline{Q}_{h}^{k^{\prime}+1}(s,a))+\rho\min_{a}\underline{Q}_{h}^{k^{\prime}+1}(s,a)\\}$,
which denotes the last episode (before the beginning of the episode $k$), in
which the $\overline{\pi}$ and $\underline{V}$ was updated at $(h,s)$. For
notational simplicity, we use $\tau$ to denote ${\tau}(k,h,s)$ here. After the
end of episode $\tau$ and before the beginning of the episode $k$, the agent
policy $\overline{\pi}$ was not updated and $\underline{V}$ was not updated at
$(h,s)$, i.e.
$\underline{V}_{h}^{k}(s)=\underline{V}_{h}^{\tau+1}(s)=(1-\rho)\underline{Q}_{h}^{\tau+1}(s,\overline{\pi}_{h}^{\tau+1}(s))+\rho\min_{a}\underline{Q}_{h}^{\tau+1}(s,a)$
and
$\overline{\pi}_{h}^{k}(s)=\overline{\pi}_{h}^{\tau+1}(s)=\operatorname*{arg\,max}_{a}\overline{Q}_{h}^{\tau+1}(s,a))$.
Thus,

$\begin{split}\underline{V}_{h}^{k}(s)=&(1-\rho)\underline{Q}_{h}^{\tau+1}(s,\overline{\pi}_{h}^{\tau+1}(s))+\rho\min_{a}\underline{Q}_{h}^{\tau+1}(s,a)\\\
\leq&(1-\rho){Q}_{h}^{\overline{\pi}^{k}}(s,\overline{\pi}_{h}^{\tau+1}(s))+\rho\min_{a}\underline{Q}_{h}^{\tau+1}(s,a)\\\
\leq&(1-\rho){Q}_{h}^{\overline{\pi}^{k}}(s,\overline{\pi}_{h}^{k}(s))+\rho\underline{Q}_{h}^{\tau+1}(s,\operatorname*{arg\,min}_{a\in\mathcal{A}}{Q}_{h}^{\overline{\pi}^{k}}(s,a))\\\
\leq&(1-\rho){Q}_{h}^{\overline{\pi}^{k}}(s,\overline{\pi}_{h}^{k}(s))+\rho\min_{a\in\mathcal{A}}{Q}_{h}^{\overline{\pi}^{k}}(s,a)={V}_{h}^{\overline{\pi}^{k}}(s).\end{split}$
(71)

By induction from $h=H+1$ to $1$ and $k=1$ to $K$, we can conclude that
$\overline{V}_{h}^{k}(s)\geq V_{h}^{*}(s)\geq
V_{h}^{\overline{\pi}^{k}}(s)\geq\underline{V}_{h}^{k}(s)$ and
$\overline{Q}_{h}^{k}(s,a)\geq Q_{h}^{*}(s,a)\geq
Q_{h}^{\overline{\pi}^{k}}(s,a)\geq\underline{Q}_{h}^{k}(s,a)$ for all
$(s,a,h,k)\in S\times A\times[H]\times[K]$.

##### Regret analysis

According to the monotonicity, the regret can be bounded by

$\begin{split}Regret(K):=&\sum_{k=1}^{K}(V_{1}^{*}(s_{1}^{k})-{V}_{1}^{\overline{\pi}^{k}}(s_{1}^{k}))\leq\sum_{k=1}^{K}(\overline{V}_{1}^{k}(s_{1}^{k})-\underline{V}_{1}^{k}(s_{1}^{k})).\end{split}$
(72)

By the update rules in Algorithm 2, we have

$\begin{split}&\overline{V}_{h}^{k}(s_{h}^{k})-\underline{V}_{h}^{k}(s_{h}^{k})\\\
\leq&(1-\rho)\overline{Q}_{h}^{k}(s_{h}^{k},\operatorname*{arg\,max}_{a}\overline{Q}_{h}^{k}(s_{h}^{k},a))+\rho\overline{Q}_{h}^{k}(s_{h}^{k},\operatorname*{arg\,min}_{a}\underline{Q}_{h}^{k}(s_{h}^{k},a))\\\
&-(1-\rho)\underline{Q}_{h}^{k}(s_{h}^{k},\operatorname*{arg\,max}_{a}\overline{Q}_{h}^{k}(s_{h}^{k},a))+\rho\underline{Q}_{h}^{k}(s_{h}^{k},\operatorname*{arg\,min}_{a}\underline{Q}_{h}^{k}(s_{h}^{k},a))\\\
=&(1-\rho)[\overline{Q}_{h}^{k}-\underline{Q}_{h}^{k}](s_{h}^{k},\overline{a}_{h}^{k})+\rho[\overline{Q}_{h}^{k}-\underline{Q}_{h}^{k}](s_{h}^{k},\underline{a}_{h}^{k})\\\
=&[\overline{Q}_{h}^{k}-\underline{Q}_{h}^{k}](s_{h}^{k},{a}_{h}^{k})+[\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}(\overline{Q}_{h}^{k}-\underline{Q}_{h}^{k})](s_{h}^{k})-[\overline{Q}_{h}^{k}-\underline{Q}_{h}^{k}](s_{h}^{k},{a}_{h}^{k}).\end{split}$
(73)

Set $n_{h}^{k}=N_{h}^{k}(s_{h}^{k},a_{h}^{k})$ and where
$k_{i}(s_{h}^{k},a_{h}^{k})$ is the episode in which $(s_{h}^{k},a_{h}^{k})$
was taken at step $h$ for the $i$-th time. For notational simplicity, we set
$\phi_{h}^{k}=\overline{V}_{h}^{k}(s_{h}^{k})-\underline{V}_{h}^{k}(s_{h}^{k})$
and
$\xi_{h}^{k}=[\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}(\overline{Q}_{h}^{k}-\underline{Q}_{h}^{k})](s_{h}^{k})-[\overline{Q}_{h}^{k}-\underline{Q}_{h}^{k}](s_{h}^{k},{a}_{h}^{k})$.
According to the update rules,

$\begin{split}\phi_{h}^{k}=&\overline{V}_{h}^{k}(s_{h}^{k})-\underline{V}_{h}^{k}(s_{h}^{k})\\\
\leq&\alpha_{n_{h}^{k}}^{0}(H-h+1)+\sum_{i=1}^{n_{h}^{k}}\alpha_{n_{h}^{k}}^{i}\left(\overline{V}_{h+1}^{k_{i}(s_{h}^{k},a_{h}^{k})}(s_{h+1}^{k_{i}(s_{h}^{k},a_{h}^{k})})-\underline{V}_{h+1}^{k_{i}(s_{h}^{k},a_{h}^{k})}(s_{h+1}^{k_{i}(s_{h}^{k},a_{h}^{k})})+2b_{i}\right)\\\
&+[\mathbbm{D}_{\widetilde{\pi}_{h}^{k}}(\overline{Q}_{h}^{k}-\underline{Q}_{h}^{k})](s_{h}^{k})-[\overline{Q}_{h}^{k}-\underline{Q}_{h}^{k}](s_{h}^{k},{a}_{h}^{k})\\\
=&\alpha_{n_{h}^{k}}^{0}(H-h+1)+\sum_{i=1}^{n_{h}^{k}}\alpha_{n_{h}^{k}}^{i}(\phi_{h+1}^{k_{i}(s_{h}^{k},a_{h}^{k})}+2b_{i})+\xi_{h}^{k}\\\
\leq&\alpha_{n_{h}^{k}}^{0}(H-h+1)+\sum_{i=1}^{n_{h}^{k}}\alpha_{n_{h}^{k}}^{i}\phi_{h+1}^{k_{i}(s_{h}^{k},a_{h}^{k})}+\xi_{h}^{k}+4\sqrt{H^{3}\iota/n_{h}^{k}}.\end{split}$
(74)

We add $\overline{V}_{h}^{k}(s_{h}^{k})-\underline{V}_{h}^{k}(s_{h}^{k})$ over
$k$ and regroup the summands in a different way. Note that for any episode
$k$, the term
$\sum_{i=1}^{n_{h}^{k}}\alpha_{n_{h}^{k}}^{i}\phi_{h+1}^{k_{i}(s_{h}^{k},a_{h}^{k})}$
takes all the prior episodes $k_{i}<k$ where $(s_{h}^{k},a_{h}^{k})$ was taken
into account. In other words, for any episode $k^{\prime}$, the term
$\phi_{h+1}^{k^{\prime}}$ appears in the summands at all posterior episodes
$k>k^{\prime}$ where $(s_{h}^{k^{\prime}},a_{h}^{k^{\prime}})$ was taken. The
first time it appears we have ${n}_{h}^{k}=n_{h}^{k^{\prime}}+1$, and the
second time it appears we have ${n}_{h}^{k}=n_{h}^{k^{\prime}}+2$, and so on.
Thus, we have

$\begin{split}&\sum_{k=1}^{K}(\overline{V}_{h}^{k}(s_{h}^{k})-\underline{V}_{h}^{k}(s_{h}^{k}))\\\
\leq&\sum_{k=1}^{K}\alpha_{n_{h}^{k}}^{0}(H-h+1)+\sum_{k=1}^{K}\sum_{i=1}^{n_{h}^{k}}\alpha_{n_{h}^{k}}^{i}\phi_{h+1}^{k_{i}(s_{h}^{k},a_{h}^{k})}+\sum_{k=1}^{K}\xi_{h}^{k}+\sum_{k=1}^{K}4\sqrt{H^{3}\iota/n_{h}^{k}}\\\
=&\sum_{k=1}^{K}\alpha_{n_{h}^{k}}^{0}(H-h+1)+\sum_{k^{\prime}=1}^{K}\phi_{h+1}^{k^{\prime}}\sum_{t=n_{h}^{k^{\prime}}+1}^{n_{h}^{K}}\alpha_{t}^{n_{h}^{k^{\prime}}}+\sum_{k=1}^{K}\xi_{h}^{k}+\sum_{k=1}^{K}4\sqrt{H^{3}\iota/n_{h}^{k}}\\\
\leq&\sum_{k=1}^{K}\alpha_{n_{h}^{k}}^{0}(H-h+1)+(1+1/H)\sum_{k=1}^{K}\phi_{h+1}^{k}+\sum_{k=1}^{K}\xi_{h}^{k}+\sum_{k=1}^{K}4\sqrt{H^{3}\iota/n_{h}^{k}}\end{split}$
(75)

where the final inequality uses the property
$\sum_{t=i}^{\infty}\alpha_{t}^{i}\leq(1+\frac{1}{H})$ for every $i\geq 1$.

Taking the induction from $h=1$ to $H$, we have

$\begin{split}&\sum_{k=1}^{K}(\overline{V}_{1}^{k}(s_{1}^{k})-\underline{V}_{1}^{k}(s_{1}^{k}))\\\
\leq&3\sum_{h=1}^{H}\sum_{k=1}^{K}\alpha_{n_{h}^{k}}^{0}(H-h+1)+3\sum_{h=1}^{H}\sum_{k=1}^{K}\xi_{h}^{k}+\sum_{h=1}^{H}\sum_{k=1}^{K}12\sqrt{H^{3}\iota/n_{h}^{k}}\end{split}$
(76)

where we use the fact that $(1+1/H)^{H}<3$ and $\phi_{H+1}^{k}=0$ for all $k$.

We bound the three items separately.

(1) We have
$\sum_{h=1}^{H}\sum_{k=1}^{K}\alpha_{n_{h}^{k}}^{0}(H-h+1)=\sum_{h=1}^{H}\sum_{k=1}^{K}\mathbbm{1}[n_{h}^{k}=0](H-h+1)\leq
SAH^{2}$.

(2) Similar to Lemma 4, by the Azuma-Hoeffding inequality, with probability
$1-\delta$, we have $\sum_{h=1}^{H}\sum_{k=1}^{K}\xi_{h}^{k}\leq
H\sqrt{2HK\iota}$.

(3) We have
$\sum_{h=1}^{H}\sum_{k=1}^{K}12\sqrt{H^{3}\iota/n_{h}^{k}}=\sum_{h=1}^{H}\sum_{(s,a)}\sum_{n=1}^{N_{h}^{K}(s,a)}\sqrt{H^{3}\iota/n}\leq
H\sqrt{2H^{3}SAK\iota}$.

In summary,

$Regret(K)=\sum_{k=1}^{K}(V_{1}^{*}(s_{1}^{k})-{V}_{1}^{\overline{\pi}^{k}}(s_{1}^{k}))\leq\mathcal{O}(\sqrt{SAH^{5}K\iota}+SAH^{2})$

and

$\begin{split}V_{1}^{*}(s_{1})-{V}_{1}^{{\pi}^{out}}(s_{1})\leq&\overline{V}_{1}^{K+1}(s_{1})-\underline{V}_{1}^{K+1}(s_{1})\\\
=&\min_{k\in[K+1]}(\overline{V}_{1}^{k}(s_{1}^{k})-\underline{V}_{1}^{k}(s_{1}^{k}))\\\
\leq&O\left(\frac{\sqrt{SAH^{5}\iota}}{K}+\frac{SAH^{2}}{K}\right).\end{split}$
(77)