Best-of-Both-Worlds Policy Optimization for CMDPs with Bandit Feedback

## Abstract

Abstract We study online learning in constrained Markov decision processes (CMDPs) in which rewards and constraints may be either stochastic or adversarial .
In such settings, Stradi et al. ( 2024a ) proposed the first best-of-both-worlds algorithm able to seamlessly handle stochastic and adversarial constraints, achieving optimal regret and constraint violation bounds in both cases.
This algorithm suffers from two major drawbacks.
First, it only works under full feedback , which severely limits its applicability in practice.
Moreover, it relies on optimizing over the space of occupancy measures, which requires solving convex optimization problems, an highly inefficient task.
In this paper, we provide the first best-of-both-worlds algorithm for CMDPs with bandit feedback .
Specifically, when the constraints are stochastic , the algorithm achieves 𝒪 ~ ⁢ ( T ) ~ 𝒪 𝑇 \widetilde{\mathcal{O}}(\sqrt{T}) over~ start_ARG caligraphic_O end_ARG ( square-root start_ARG italic_T end_ARG ) regret and constraint violation, while, when they are adversarial , it attains 𝒪 ~ ⁢ ( T ) ~ 𝒪 𝑇 \widetilde{\mathcal{O}}(\sqrt{T}) over~ start_ARG caligraphic_O end_ARG ( square-root start_ARG italic_T end_ARG ) constraint violation and a tight fraction of the optimal reward.
Moreover, our algorithm is based on a policy optimization approach, which is much more efficient than occupancy-measure-based methods.

## 1 Introduction

Most of the learning problems arising in real-world scenarios involve an agent sequentially interacting with an unknown environment.
*Markov decision processes* (MDPs) (Puterman, ) have emerged as the most natural models for such interactions, as they allow to capture the fundamental goal of learning an optimal (*i.e.*, reward-maximizing) action-selection policy for the agent.
However, in most of the real-world applications of interest, the learner also has to satisfy some additional requirements.
For instance, in autonomous driving one has to avoid crashing with other cars (Isele et al., ), in ad auctions one must *not* deplete its allocated budget (He et al., ), while in recommendation systems offending items should *not* be presented to the users (Singh et al., ).
In order to capture such requirements, *constrained MDPs* (CMDPs) (Altman, ) have been introduced.
These augment classical MDPs by adding costs that the agent is constrained to keep below some given thresholds.

Over the last years, *online learning* problems in *episodic* CMDPs have received a growing attention (see, *e.g.*, (Efroni et al., ) for a seminal work in the field).
These are problems in which the learner repeatedly interacts with the CMDP environment over multiple episodes.
In such settings, the learner’s goal is to minimize the *regret* of not always selecting a best-in-hindsight policy that satisfies cost constraints, while at the same time ensuring that the cumulative *violation* of cost constraints does *not* grow too fast over the episodes.
Ideally, one would like that both the regret and the constraint violation grow sublinearly in the number of episodes $T$.

In online learning in episodic MDPs, two different assumptions on how rewards and costs are determined at each episode are possible.
They can be selected either *stochastically* according to fixed (unknown) probability distributions or *adversarially*, meaning that no statistical assumption is made.
Very recently, Stradi et al. () proposed the first *best-of-both-worlds* learning algorithm for online learning in episodic CMDPs.
Such an algorithm is able to seamlessly handle stochastic and adversarial constraints, achieving optimal regret and violation bounds in both cases.
However, it suffers from two major drawbacks.
First, it only works under *full feedback*, meaning that the learning agent needs to observe rewards and costs defined over the whole environment after each episode.
This is extremely unreasonable in practice, where only some feedback along the realized trajectory is usually available.
Moreover, the algorithm works by optimizing over the space of occupancy measures, which requires solving a convex problem at every episode, an highly inefficient task.

### 1.1 Original Contributions

We provide the first *best-of-both-worlds* algorithm for online learning in episodic CMDPs with *bandit feedback*.
This means that, after each episode, the algorithm only needs to observe the realized rewards and costs along the trajectory traversed during that episode, as it is the case in most of the real-world applications.
Moreover, our algorithm is based on a primal-dual policy optimization method, and, thus, it is arguably much more efficient than the algorithm by Stradi et al. ().

When the costs are *stochastic*, our algorithm achieves $\widetilde{O}(\sqrt{T})$ regret and constraint violation, while, when the costs are *adversarial*, it attains $\widetilde{O}(\sqrt{T})$ violation and a fraction of the optimal reward.
These results match those of the full-feedback algorithm by Stradi et al. () and are provably tight.

We also analyze the performances of our algorithm with respect to a parameter $\rho$ measuring by “how much” Slater’s condition is satisfied.
Specifically, if $\rho$ is arbitrarily small, our algorithm can still guarantee $\widetilde{\mathcal{O}}(T^{3/4})$ regret and violation in the stochastic setting.
Crucially, similarly to the algorithm by Stradi et al. (), ours *does not require* any knowledge of the Slater’s parameter $\rho$.
In order to attain the aforementioned result, we show that the Lagrangian multipliers are automatically bounded during the learning dynamics, by employing the *no-interval-regret* property of our primal and dual regret minimizers.
Indeed, we develop the first algorithm for unconstrained MDPs with no-interval-regret, under *bandit* feedback. This result may be of independent interest.

Finally, differently from Stradi et al. (), our algorithm can achieve
$\widetilde{\mathcal{O}}(\sqrt{T})$ regret and violation in the adversarial setting, by using a *weaker* baseline that has to satisfy the constraints at every round.

### 1.2 Related Works

In the following, we highlight the works that are mainly related to ours. Due to space constraints, we refer to Appendix A for a complete discussion about related works.

Online learning in MDPs has been widely studied both under stochastic settings (see (Auer et al., )) and adversarial ones (see (Neu et al., )). In adversarial settings, two feedbacks are usually investigated. In the *full-feedback setting*, the reward function (or loss) is entirely revealed at the end of the episode. In this case, Rosenberg and Mansour () show that it is possible to achieve an optimal $\widetilde{\mathcal{O}}(\sqrt{T})$ regret bound. In the more challenging *bandit-feedback setting*, with rewards revealed along the traversed trajectory only, Jin et al. () show that the optimal bound is still attainable.

As concerns MDPs with constraints, online learning has been studied mainly in the stochastic setting (see Efroni et al. () for a seminal work on the topic). As concerns adversarial settings, namely, when the constraints are *not* assumed to be stochastic, there exists an impossibility result from Mannor et al. () that prevents from attaining sublinear regret and violation when the optimal solution is computed with respect to a policy that satisfies the constraints on average. Thus, many works focused on achieving $\widetilde{\mathcal{O}}(\sqrt{T})$ regret and violation for adversarial rewards and stochastic constraints (see (Qiu et al., )) or non-stationary environments with bounded non-stationarity (see (Ding and Lavaei, ; Wei et al., ; Stradi et al., )).

Recently, Stradi et al. () showed the first best-of-both-worlds (with respect to the constraints) algorithm for CMDPs. Precisely, the authors propose a primal-dual algorithm that optimizes over the occupancy measure space, under *full feedback*. When the constraints are stochastic, the algorithm achieves $\widetilde{\mathcal{O}}(\sqrt{T})$ regret and violation, both in the case in which rewards are adversarial and the one where they are stochastic. Contrariwise, in the adversarial setting, the algorithms attains $\widetilde{\mathcal{O}}(\sqrt{T})$ violatios, and the no-$\alpha$-regret property with $\alpha=\nicefrac{{\rho}}{{H+\rho}}$, where $\rho$ is a suitably-defined Slater’s parameter. Notice that this result is in line with the best-of-both-worlds results in the single-state online constrained settings, *e.g.*, (Castiglioni et al., ).

## 2 Problem Setting

In this section, we describe the problem setting and the related notation.

### 2.1 Online Constrained Markov Decision Processes

Figure: Algorithm 1 Learner-Environment Interaction

We study *online episodic constrained* MDPs (Altman, ) (CMDPs), which are defined as tuples $M\coloneqq(X,A,P,\left\{r_{t}\right\}_{t=1}^{T},\left\{G_{t}\right\}_{t=1}^{T})$. Specifically, $T$ is a number of episodes, with $t\in[T]$ denoting a specific episode.
$X,A$ are finite state and action spaces, respectively.
$P:X\times A\to\Delta(X)$ is the transition function. We denote by $P(x^{\prime}|x,a)$ the probability of going from state $x\in X$ to $x^{\prime}\in X$ by taking action $a\in A$. Notice that, w.l.o.g., in this work we consider *loop-free* CMDPs. Formally, this means that $X$ is partitioned into $H$ layers $X_{0},\dots,X_{H}$ such that the first and the last layers are singletons, *i.e.*, $X_{0}=\{x_{0}\}$ and $X_{H}=\{x_{H}\}$, and that $P(x^{\prime}|x,a)>0$ only if $x^{\prime}\in X_{h+1}$ and $x\in X_{h}$ for some $h\in[0\ ..\ H-1]$.
We observe that any episodic CMDP with horizon $H$ that is *not* loop-free can be cast into a loop-free one by suitably duplicating the state space $H$ times, *i.e.*, a state $x$ is mapped to a set of new states $(x,h)$, where $h\in[0\ ..\ H]$.
$\left\{r_{t}\right\}_{t=1}^{T}$ is a sequence of vectors describing the rewards at each episode $t\in[T]$, namely $r_{t}\in[0,1]^{|X\times A|}$. We refer to the reward of a specific state-action pair $x\in X,a\in A$ for an episode $t\in[T]$ as $r_{t}(x,a)$. Rewards may be either stochastic, in that case $r_{t}$ is a random variable distributed according to a distribution $\mathcal{R}$ for every $t\in[T]$, or chosen by an *adversary*.
$\left\{G_{t}\right\}_{t=1}^{T}$ is a sequence of constraint matrices describing the $m$ *constraint* violations at each episode $t\in[T]$, namely $G_{t}\in[-1,1]^{|X\times A|\times m}$, where non-positive violation values stand for satisfaction of the constraints. For $i\in[m]$, we refer to the violation of the $i$-th constraint for a specific state-action pair $x\in X,a\in A$ at episode $t\in[T]$ as $g_{t,i}(x,a)$. Constraint violations may be stochastic, in that case $G_{t}$ is a random variable distributed according to a probability distribution $\mathcal{G}$ for every $t\in[T]$, or chosen by an *adversary*.

In the online setting, the learner chooses a *policy* $\pi:X\to\Delta(A)$ at each episode, defining a probability distribution over actions at each state.
For ease of notation, we denote by $\pi(\cdot|x)$ the probability distribution for a state $x\in X$, with $\pi(a|x)$ denoting the probability of action $a\in A$.
In Algorithm 1 we provide the interaction between the learner and the environment in a CMDP.
Furthermore, we assume that the learner knows $X$ and $A$, but they do *not* know anything about $P$.
Notice that the interaction between the learner and the environment is with *bandit feedback*, namely, the rewards and the constraint violations are revealed for the traversed trajectory only.

##### Occupancy Measures

Given a transition function $P$ and a policy $\pi$, the *occupancy measure* $q^{P,\pi}\in[0,1]^{|X\times A\times X|}$ induced by $P$ and $\pi$ is such that, for all $x\in X_{h}$, $a\in A$, and $x^{\prime}\in X_{h+1}$ with $h\in[0\ ..\ H-1]$, it holds
$q^{P,\pi}(x,a,x^{\prime})=\mathbb{P}\left\{x_{h}=x,a_{h}=a,x_{h+1}=x^{\prime}|
P,\pi\right\}.$
Moreover, we also define
$q^{P,\pi}(x,a)=\sum_{x^{\prime}\in X_{h+1}}q^{P,\pi}(x,a,x^{\prime})$ and
$q^{P,\pi}(x)=\sum_{a\in A}q^{P,\pi}(x,a)$.
Then, following (Rosenberg and Mansour, ), the set of *valid* occupancy measures can be characterized as follows.
Specifically, $q\in[0,1]^{|X\times A\times X|}$ is a valid occupancy measure of an episodic loop-free MDP if and only if the following conditions hold: (i) $\sum_{x\in X_{h}}\sum_{a\in A}\sum_{x^{\prime}\in X_{h+1}}q(x,a,x^{\prime})=1$ for all $h\in[0,\dots,H-1]$; (ii) $\sum_{a\in A}\sum_{x^{\prime}\in X_{h+1}}q(x,a,x^{\prime})=\sum_{x^{\prime}\in
X
_{h-1}}\sum_{a\in A}q(x^{\prime},a,x)$ for all $h\in[1,\dots,H-1]$ and $x\in X_{h}$; and (iii)
$P^{q}=P,$
where $P$ is the transition function of the MDP and $P^{q}$ is the one induced by $q$. Indeed, any valid occupancy measure $q$ induces a transition function $P^{q}$ and a policy $\pi^{q}$, defined as
$P^{q}(x^{\prime}|x,a)\coloneqq\frac{q(x,a,x^{\prime})}{q(x,a)}$ and $\pi^{q}(a|x)\coloneqq\frac{q(x,a)}{q(x)}.$

### 2.2 Offline CMDPs Baseline

In the following, we introduce the *offline* CMDP optimization problem, which is needed to define a proper baseline to evaluate the performances of online learning algorithms.
Specifically, we introduce the following linear program parameterized by a reward vector $r$ and a constraint matrix $G$ as follows:

$$ $\text{OPT}_{r,G}:=\begin{cases}\max_{q\in\Delta(M)}&r^{\top}q\\ \,\,\,\textnormal{s.t.}&G^{\top}q\leq\underline{0},\end{cases}$ (1) $$

where $q\in[0,1]^{|X\times A|}$ is an occupancy measure and $\Delta(M)$ is the set of valid occupancy measures.

Furthermore, we state the following well-known condition on the offline CMDP problem.

###### Condition 1 (Slater’s condition) .

Given a constraint matrix $G$, the Slater’s condition holds when there is a strictly feasible solution $q^{\diamond}$ such that $G^{\top}q^{\diamond}<\underline{0}$.

Notice that, in this work, we do *not* assume that the Slater’s condition holds. Indeed, our algorithm still works when a strictly feasible solution does *not* exists. We refer to Section 2.4 for further details on this.
Finally, we define the Lagrangian function of Problem (1), as follows.

###### Definition 1 (Lagrangian function) .

Given a reward vector $r$ and a constraint matrix $G$, the Lagrangian function $\mathcal{L}_{r,G}:\Delta(M)\times\mathbb{R}^{m}_{\geq 0}\rightarrow\mathbb{R}$ of Problem (1) is defined as:

$$ $\mathcal{L}_{r,G}(q,\lambda):=r^{\top}q-\lambda^{\top}(G^{\top}{q}).$ $$

###### Condition 1 (Slater’s condition) .

###### Definition 1 (Lagrangian function) .

### 2.3 Online Learning Problem

As ti is standard in the online learning literature (Cesa-Bianchi and Lugosi, ), we evaluate the performance of learning algorithms by means of the notion of cumulative regret.

###### Definition 2 .

We define the cumulative regret up to episode $T$ as:

$$ $R_{T}:=T\;\textnormal{OPT}_{\overline{r},\overline{G}}-\sum_{t=1}^{T}r_{t}^{ \top}q^{P,\pi_{t}},$ $$

where $\overline{r}\coloneqq\mathbb{E}_{r\sim\mathcal{R}}[r]$ if rewards are stochastic and $\overline{r}\coloneqq\frac{1}{T}\sum_{t=1}^{T}r_{t}$ if they are adversarial, while $\overline{G}\coloneqq\mathbb{E}_{G\sim\mathcal{G}}[G]$ if the constraints are stochastic and $\overline{G}\coloneqq\frac{1}{T}\sum_{t=1}^{T}G_{t}$ if they are adversarial.

We refer to an optimal occupancy measure, *i.e.*, a feasible one achieving value $\text{OPT}_{\overline{r},\overline{G}}$, as $q^{*}$. Thus, we can rewrite the regret definition as $R_{T}=\sum_{t=1}^{T}\overline{r}^{\top}q^{*}-\sum_{t=1}^{T}r_{t}^{\top}q^{P,
\pi_{t}}.$
Notice that, in the adversarial setting, the regret is computed with respect to an *optimal feasible strategy in hindsight*. Indeed, an optimal solution is *not* required to satisfy the constraints at every episode $t\in[T]$.

Next, we define the performance measure related to constraints: the *cumulative constraint violation*.

###### Definition 3 .

The cumulative constraint violation up to episode $T$ is defined as:

$$ $V_{T}:=\max_{i\in[m]}\sum_{t=1}^{T}\left[G_{t}^{\top}q^{P,\pi_{t}}\right]_{i}.$ $$

Learning algorithms perform properly when they are capable of keeping both the quantities defined above sublinear in $T$, namely, $R_{T}=o(T)$ and $V_{T}=o(T)$.

For the sake of simplicity, in the rest of the paper, we will refer to $q^{P,\pi_{t}}$ as $q_{t}$, omitting the dependence on transition unction $P$ and policy $\pi$.

###### Definition 2 .

###### Definition 3 .

### 2.4 Feasibility

We introduce a problem-specific parameter of Problem (1), called $\rho\in\left[0,H\right]$, which identifies by “how much” Slater’s condition is satisfied. Formally:

- •
when the constraints are selected stochastically, namely, they are chosen from a fixed distribution, the parameter $\rho$ is defined as $\rho:=\max_{q\in\Delta(M)}\min_{i\in[m]}-\left[\overline{G}^{\top}q\right]_{i}.$
- •
when the constraints are chosen adversarially, namely, no statistical assumption is made, the parameter $\rho$ is defined as $\rho:=\max_{q\in\Delta(M)}\min_{t\in[T]}\min_{i\in[m]}-\left[G_{t}^{\top}q
\right]_{i}.$

Furthermore, we denote the occupancy measure $q\in\Delta(M)$ leading to the value of $\rho$ by $q^{\circ}$.
Intuitively, $\rho$ represents the “margin” by which the “most feasible” strictly feasible solution (*i.e.*, $q^{\circ}$) satisfies the constraints.
Finally, we state the following condition on the parameter $\rho$, which will guide the analyses of the performances of our algorithm.

###### Condition 2 .

It holds that
$\rho\geq T^{\frac{1}{8}}H\sqrt{112m}$.

Notice that, it is standard in the literature (see, *e.g*, (Efroni et al., )) to assume that $\rho$ is a constant independent of $T$ and directly include in the regret bound the dependence on $\nicefrac{{1}}{{\rho}}$. Nevertheless, when $\rho$ is too small, this could result in suboptimal regret bounds. In this paper, we take a different approach by providing theoretical guarantees for any value of $\rho$.

###### Condition 2 .

## 3 A Policy Optimization Primal-Dual Approach

In this section, we provide the description of our algorithm. We resort to a primal-dual formulation of the CMDP problem, and we employ different regret minimizers to optimize over the primal space (namely, the policy space) and the dual one (that is, the Lagrangian variables space). Furthermore, our primal algorithm is based on a policy optimization approach. Thus, the learning update is *not* performed over the occupancy measure space, but state-by-state along the MDP structure. This allows us to avoid solving a convex program at each episode (as it is the case in the algorithm by (Stradi et al., )). As concerns the dual, we employ online gradient descent (OGD). We remark that our algorithm does *not* require any knowledge of the Slater’s parameter $\rho$. Indeed, as we further discuss in the rest of this work, we can show that the Lagrangian multipliers are automatically bounded given specific no-regret properties of the primal and dual regret minimizers.

### 3.1 Meta-Algorithm

In Algorithm 2, we provide the pseudocode of *primal-dual bandit policy search* (PDB-PS).

Figure: Algorithm 2 PDB-PS

Algorithm 2 initializes the policy uniformly over the space (see Line 2). Moreover, the Lagrangian variables are initialized as the zero vector, the loss scaling factor to $1$, the loss range to $2$, and, finally, the dual space is instantiated as $\left[0,T^{1/4}\right]^{m}$ (see Line 3). We underline that we force the dual space to be bounded in $\left[0,T^{1/4}\right]^{m}$ only to deal with degenerate cases where Condition 2 does *not* hold. When Condition 2 holds, our algorithm guarantees that the Lagrangian variables are automatically bounded during learning. Furthermore, the algorithm keeps track of the maximum loss range observed by the primal algorithm $\Xi_{t}$, up to episode $t\in[T]$, since the primal regret minimizer needs to dynamically update its belief on the loss range, in order to attain optimal regret bounds. The algorithm plays policy $\pi_{t}$ and observes the *bandit* feedback as depicted in Algorithm 1 (see Line 5). Given the observed feedback, PDB-PS builds a re-scaled Lagrangian loss for each layer $h\in[H]$ as:

$$ $\ell_{t}(x_{h},a_{h}):=\Gamma_{t}+\sum_{i=1}^{m}\lambda_{t,i}g_{t,i}(x_{j},a_{ j})-r_{t}(x_{j},a_{j}).$ (2) $$

Notice that the loss built in Equation (2) can been seen as the Lagrangian suffered by $\pi_{t}$ for state-action pair $(x,a)$, scaled by $\Gamma_{t}$ to guarantee that the losses are always positive (see Line 7). This loss is properly built to feed the primal policy optimization procedure. Moreover, we underline that the feedback given to the primal algorithm encompasses the trajectory and the maximum loss range observed, besides the loss built in Equation (2). Policy $\pi_{t+1}$ is returned by the primal algorithm (Line 8). We refer the reader to the next section for further discussion on the primal optimization algorithm. Algorithm 2 updates the Lagrangian multipliers using an online gradient descent update with loss $-\sum_{h=0}^{H}G_{t}[x_{h},a_{h}]$ in the bounded dual space $[0,T^{\nicefrac{{1}}{{4}}}]^{m}$ as:

$$ $\lambda_{t+1}\leftarrow\Pi_{\mathcal{K}}\left[\lambda_{t}+\eta\sum_{h=0}^{H-1} G_{t}[x_{h},a_{h}]\right],$ $$

where $\Pi_{\mathcal{K}}$ is the euclidean projection over the space $\mathcal{K}$ and $G_{t}[x_{h},a_{h}]$ is the $m$-dimensional vector composed by the violations of any constraint for the state-action pair $(x_{h},a_{h})$ (Line 9).
Thus, the current loss scaling factor is computed as $\Gamma_{t+1}\leftarrow 1+\|\lambda_{t+1}\|_{1}$ (Line 10). Finally, the maximum observed loss range $\Xi_{t+1}$ is updated as
$\Xi_{t+1}\leftarrow\max\left\{\Xi_{t},2\Gamma_{t+1}\right\},$
since the range of losses observed by the primal depends on the Lagrangian multipliers values (Line 11).

### 3.2 Primal Regret Minimizer

In Algorithm 3, we provide the pseudocode of *fixed share policy optimization with dilated bonus* (FS-PODB.UPDATE), namely, the update performed by the primal regret minimizer employed by Algorithm 2. Algorithm 3 builds on top of the state-of-the-art policy optimization algorithm for adversarial MDPs (see (Luo et al., )), equipping it with a fixed share update (Cesa-Bianchi et al., ). This modification allows us to achieve the no-interval regret property, which, to the best of our knowledge, has never been shown for adversarial MDPs with bandit feedback. Thus, we believe that the theoretical guarantees of Algorithm 3 are of independent interest.

Specifically, Algorithm 3 requires in input the trajectory traversed during the learner-environment interaction, the incurred loss functions, and the maximum loss range observed for any $t\in[T]$.(^1^11Notice that, while the input of Algorithm 3 may seem different from the standard bandit feedback received in adversarial MDPs, this is *not* the case. Indeed, it is sufficient to set $\Xi_{t}=1$ for all $t\in[T]$ to achieve the same guarantees attained by Algorithm 3, in the Lagrangian formulation of CMDPs, in standard adversarial MDPs.) During the first episode, the algorithm initializes the estimated transitions space as the set of all possible transition functions (Line 3). Thus, at each episode the algorithm defines a dynamic learning rate $\eta_{t}\propto\frac{1}{\sqrt{T}\Xi_{t}}$ (Line 4), where $\Xi_{t}$ is the upper bound on the range of the loss functions up to $t$. This is done to control the different scales of the loss, due to the Lagrangian multipliers choice of the dual algorithm. Then, Algorithm 3 builds an *optimistic* estimator of the state-action value function as:

$$ $\widehat{Q}_{t}(x,a)\coloneqq\frac{L_{t,h}}{\overline{q}_{t}(x,a)+\gamma} \mathbb{I}_{t}(x,a),$ $$

where $\mathbb{I}_{t}(x,a)\coloneqq\mathbb{I}\{x_{t,h}=x,a_{t,h}=a\}$ and $L_{t,h}\coloneqq\sum_{j=h}^{H-1}\ell_{t}(x_{j},a_{j})$ is the loss incurred by the algorithm at episode $t$ starting from layer $h$.

Figure: Algorithm 3 FS-PODB.UPDATE

Indeed, since $\overline{q}_{t}(x,a)\coloneqq{\max}_{\widehat{P}\in\mathcal{P}_{t}}q^{
\widehat{P},\pi_{t}}(x,a)$,(^2^22As shown in (Jin et al., ), $\overline{q}_{t}(x,a)$ can be computed efficiently by means of dynamic programming.) and $\gamma$ is a positive quantity, $\widehat{Q}_{t}(x,a)$ results in an optimistic estimator of the state-action value function
(Line 5). The optimistic estimator is employed to control the variance of the loss estimation and, thus, in order to achieve high-probability results. Finally, notice that the state-action value function (as the estimated one) is commonly used in policy optimization as it allows to optimize efficiently state-by-state. In addition to the estimated state-action value function, Algorithm 3 defines a dilated bonus similar to the one introduced by Luo et al. (), which is then incorporated in the final objective of the optimization update. The bonus is defined as:

$$ $B_{t}(x,a)\coloneqq b_{t}(x)+\left(1+\frac{1}{H}\right)\underset{\widehat{P} \in\mathcal{P}_{t}}{\max}\,\,\mathbb{E}_{x^{\prime}\sim\widehat{P}(\cdot|x,a)} \mathbb{E}_{a\sim\pi_{t}(\cdot|x^{\prime})}\left[B_{t}(x^{\prime},a^{\prime}) \right],$ $$

where the term $b_{t}(x)$ depends on the uncertainty on the transitions estimation and the range of the losses, while the term $\left(1+\frac{1}{H}\right)$ attributes more weight to the deeper layers, so as to incentivize exploration (Line 6).
The weights associated to any action are computed employing the so called fixed share update (Cesa-Bianchi et al., ); specifically, the weights are computed as the convex combination between the uniform weight and the solution to optimization step $\propto w_{t}(a|x)e^{-\eta_{t}\left(\widehat{Q}_{t}(x,a)-B_{t}(x,a)\right)}$. The policy is simply computed as a normalization between weights (see Line 7). Notice that the convex combination mentioned above is crucial to bound the regret for each interval (that is, to attain the no-interval regret property). Indeed, it guarantees a lower bound for the value taken by the policy in each available action at each episode, and, thus, for all intervals $[t_{1},t_{2}]\subset[T]$, it allows to find a nice upper bound for the Bregman divergence $D_{\psi}(\pi(\cdot|a);\pi_{t_{1}}(\cdot|a))$, for all policies $\pi$. Finally, the estimation of the transitions is updated given the trajectory traversed in the MDP (Line 8). This estimation is standard in the literature. Thus, we refer to (Rosenberg and Mansour, ) for further discussion on the use of counters and epochs to estimate a superset of the transition space $\mathcal{P}_{t}$.

### 3.3 No-Interval Regret Property

When the Slater’s parameter $\rho$ is known, the only necessary requirement for the primal and the dual regret minimizers is to be no-regret. Thus, it is sufficient to bound the Lagrangian space so that $\|\lambda\|_{1}\leq\mathcal{O}(\nicefrac{{H}}{{\rho}})$ to attain sublinear regret and violation. Nevertheless, knowing $\rho$ is generally *not* possible in real-world scenarios. In order to relax the assumption on the knowledge of $\rho$, we require our primal and dual regret minimizers to have the no-interval regret property.(^3^33What we require is generally known in the literature as the *weak* no-interval regret property. For the sake of simplicity, in our work, we introduce only the *weak* property.).

First, we introduce the interval regret as follows.

###### Definition 4 (Interval regret) .

Given an interval of consecutive episodes $[t_{1},\dots,t_{2}]\subseteq[1,\dots,T]$, the *interval regret* with respect to a general occupancy $q$ (and the associated policy $\pi$) and a sequence of loss functions $\{\ell_{t}\}_{t=1}^{T}$ with $\ell_{t}:X\times A\rightarrow[0,K]$, with $K>0$, is $R_{t_{1},t_{2}}(q):=\sum_{t=t_{1}}^{t_{2}}\ell_{t}^{\top}(q_{t}-q).$

In the following, we omit the dependence on the general occupancy $q$ when it is clear from the context. Thus, given Definition 4, we are able to introduce the no-interval regret property.

###### Definition 5 (No-interval regret property) .

An algorithm attains the no-interval regret property when for any interval of consecutive episodes $[t_{1},\dots,t_{2}]\subseteq[1,\dots,T]$ and with respect to any valid occupancy $q$ (and the associated policy $\pi$), it holds $R_{t_{1},t_{2}}\leq\widetilde{\mathcal{O}}(\sqrt{T})$.

Intuitively, the no-interval regret property guarantees a more stable learning dynamics over the episodes. When *full feedback* is available, as for the dual algorithm, it is sufficient to employ OGD-like updates to attain the desired result. This is *not* the case when the feedback is *bandit*. Nevertheless, given that we use a policy optimization procedure and the fixed share update, we build the first algorithm for adversarial MDPs with no-interval-regret. We state the result in the following theorem.

###### Theorem 3 .

For any $\delta\in(0,1)$, with probability at least $1-8\delta$, Algorithm FS-PODB attains:

$$ $R_{t_{1},t_{2}}\leq\tilde{\mathcal{O}}\left(\Xi_{t_{1},t_{2}}\sqrt{T}+\Xi_{t_{ 1},t_{2}}\frac{t_{2}-t_{1}}{\sqrt{T}}\right),$ $$

where the regret can be computed with respect to any policy function $\pi:X\rightarrow\Delta(A)$.

Notice that, as it is standard for online learning algorithms, $R_{t_{1},t_{2}}$ scales as the loss range, as shown by the dependence on $\Xi_{t_{1},t_{2}}$, that is, the maximum possible range of losses in the interval.

###### Definition 4 (Interval regret) .

###### Definition 5 (No-interval regret property) .

###### Theorem 3 .

### 3.4 Bound on the Lagrangian Multipliers Dynamics

Next, we show that, given the no-interval regret property of the primal and the dual regret minimizers, it is possible to show that the Lagrangian multipliers are automatically bounded during learning. Notice that this bound is necessary since any adversarial regret minimizer needs the loss to be bounded to achieve the no-regret property. Thus, since the rewards $\{r_{t}\}_{t=1}^{T}$ and the constraints $\{G_{t}\}_{t=1}^{T}$ are assumed to be bounded for all episodes, the problem of bounding the loss suffered by the primal algorithm becomes the problem of bounding the Lagrangian multipliers $\{\lambda_{t}\}_{t=1}^{T}$.

###### Theorem 4 .

Under Condition 2, for any $\delta\in(0,1)$, with probability
at least $1-11\delta$, it holds:

$$ $\lVert\lambda_{t}\rVert_{1}\leq\Lambda\quad\forall t\in[T+1],$ $$

where $\Lambda=\frac{112mH^{2}}{\rho^{2}}$.

The general idea behind the proof is to compare, for every interval $[t_{1},t_{2}]\subset[T],$ the upper bound to $-\sum_{t=t_{1}}^{t_{2}}\ell_{t}^{\mathcal{L},\top}q_{t}$ obtained through the regret of the dual algorithm with the lower bound to the same quantity obtained through the primal interval regret, where we define the non-scaled Lagrangian loss $\ell_{t}^{\mathcal{L}}$ as the vector composed by $\ell^{\mathcal{L}}_{t}(x,a)\coloneqq\sum_{i=1}^{m}\lambda_{t,i}g_{t,i}(x,a)-r_
{t}(x,a)$ for all $(x,a)\in X\times A$ and for all $t\in[T]$. The resulting inequality leads, by contradiction, to the desired bound. In this sense, a fundamental requirement for the proof is that the regret guarantees for both the primal and the dual algorithm hold for all subsets of episodes.

###### Theorem 4 .

## 4 Theoretical Analysis

In this section, we prove the best-of-both-world guarantees attained by Algorithm 2.

### 4.1 Stochastic Setting

We first study the performance of Algorithm 2 when the constraints are stochastic.

In such a setting, our algorithm can handle two scenarios. In both of them, employing a primal-dual analysis shows that both the regret and the violations are bounded with order $\widetilde{\mathcal{O}}(\sqrt{T})$ times the maximum value taken over all episodes of the Lagrangian multipliers, *i.e.* $\max_{t\in[T]}\lVert\lambda_{t}\rVert_{1}$. In the first scenario, Condition 2 holds and thus we can apply Theorem 4 to show that the Lagrangian multipliers are bounded. In such a case, $\max_{t\in[T]}\lVert\lambda_{t}\rVert_{1}$ can be easily bounded by $\Lambda$. When Conditions 2 does *not* hold, we need to resort to the bound of Lagrangian multipliers derived by the instantiation of OGD decision space, leading to $\widetilde{\mathcal{O}}(T^{3/4})$ regret and violations bounds.

Specifically, when Condition 2 holds, the Lagrangian multipliers are nicely bounded by $\Lambda$.

###### Theorem 5 .

Suppose that Condition 2 holds and the constraints are generated stochastically. Then, for any $\delta\in(0,1)$, Algorithm 2 attains:

$$ $R_{T}\leq\tilde{\mathcal{O}}\left(\Lambda\sqrt{T}\right),\quad V_{T}\leq\tilde {\mathcal{O}}\left(\Lambda\sqrt{T}\right),$ $$

with probability at least $1-14\delta$ when the rewards are stochastic and at least $1-13\delta$ when the rewards are adversarial.

When Condition 2 does *not* hold, we can still use the bound forced by Algorithm 2 on the dual space. Therefore, the Lagrangian multipliers are bounded by $mT^{\nicefrac{{1}}{{4}}}$, leading to the following result.

###### Theorem 6 .

Suppose that Condition 2 does not hold and the constraints are generated stochastically.
Then, for any $\delta\in(0,1)$, Algorithm 2 attains:

$$ $R_{T}\leq\tilde{\mathcal{O}}\left(T^{\nicefrac{{3}}{{4}}}\right),\quad V_{T} \leq\tilde{\mathcal{O}}\left(T^{\nicefrac{{3}}{{4}}}\right),$ $$

with probability at least $1-11\delta$ when the rewards are stochastic and at least $1-10\delta$ when the rewards are adversarial.

###### Theorem 5 .

###### Theorem 6 .

### 4.2 Adversarial setting

We then study the performance of Algorithm 2 when the constraints are adversarial. Notice that, in such a setting, there exists an impossibility result from (Mannor et al., ) that prevents any algorithm from attaining both sulinear regret and sublinear violations. Thus, best-of-both-worlds algorithms in constrained settings focus on attaining sublinear violations and a fraction of the optimal rewards (see *e.g.*, (Castiglioni et al., ; Stradi et al., )).(^4^44Attaining the no-$\alpha$-regret property, that is, being no-regret w.r.t. a fraction of the optimum, achieving a competitive ratio, and guaranteeing a fraction of the optimal rewards are used as synonyms in the literature, since any of the aforementioned guarantees can be derived by the others.)

In such a setting, we can show the following result.

###### Theorem 7 .

Suppose Condition 2 holds and the constraints are adversarial. Then, for any $\delta\in(0,1)$, Algorithm 2 attains:

$$ $\sum_{t=1}^{T}r_{t}^{\top}q_{t}\geq\Omega\left(\frac{\rho}{\rho+H}\cdot\text{ OPT}_{\overline{r},\overline{G}}\right),\quad V_{T}\leq\tilde{\mathcal{O}} \left(\Lambda\sqrt{T}\right),$ $$

with probability at least $1-14\delta$ when the rewards are stochastic and with probability at least $1-13\delta$ when the rewards are adversarial.

###### Theorem 7 .

#### 4.2.1 A Weaker Baseline

In this section, we show that the impossibility result by Mannor et al. () can be circumvented by adopting a different baseline in the regret definition.
Precisely, we compute the weaker baseline as the solution to the following linear program:

$$ $\text{OPT}^{\mathcal{W}}:=\begin{cases}\max_{q\in\Delta(M)}&\overline{r}^{\top }q\\ \,\,\,\textnormal{s.t.}&G_{t}^{\top}q\leq\underline{0}\quad\forall t\in[T]. \end{cases}$ $$

Notice that, in the previous sections, we allow the optimal policy $q^{*}$ to satisfy the constraints on average, *i.e.*, $\sum_{t=1}^{T}G_{t}^{\top}q^{*}\leq 0$. In such a case, the set of feasible policies is much smaller than the one associated with the weaker baseline, that is, when a feasible policy must satisfy the constraints *at each episode*. Given the new baseline, we can rewrite the regret as $R_{T}\coloneqq T\,\text{OPT}^{\mathcal{W}}-\sum_{t=1}^{T}r_{t}^{\top}q_{t}$.

When the regret is computed w.r.t. the weaker baseline, we can recover the same theoretical results of the stochastic setting. Precisely, when Condition 2 holds we have the following result.

###### Theorem 8 .

Suppose that Condition 2 holds and the constraints are generated adversarially. Then, for any $\delta\in(0,1)$, Algorithm 2 attains:

$$ $R_{T}\leq\tilde{\mathcal{O}}\left(\Lambda\sqrt{T}\right),\quad V_{T}\leq\tilde {\mathcal{O}}\left(\Lambda\sqrt{T}\right),$ $$

with probability at least $1-13\delta$ when the rewards are stochastic and at least $1-12\delta$ when the rewards are adversarial.

We conclude the section by analyzing the scenario in which Condition 2 does *not* hold.

###### Theorem 9 .

Suppose that Condition 2 does not hold and the constraints are generated adversarially.
Then, for any $\delta\in(0,1)$, Algorithm 2 attains:

$$ $R_{T}\leq\tilde{\mathcal{O}}\left(T^{\nicefrac{{3}}{{4}}}\right),\quad V_{T} \leq\tilde{\mathcal{O}}\left(T^{\nicefrac{{3}}{{4}}}\right),$ $$

with probability at least $1-12\delta$ when the rewards are stochastic and at least $1-11\delta$ when the rewards are adversarial.

Intuitively, Theorems 8 and 9 can be proved by the fact that playing the optimal policy guarantees small violations independently on the episode the optimum is chosen. This is *not* the case of the stronger baseline, since playing the optimum in some episodes may lead to arbitrarily large violations.

###### Theorem 8 .

###### Theorem 9 .

## Appendix

The Appendix is structured as follows:

- •
In Section A, we provide additional related works.
- •
In Section B, we provide additional notation employed in the rest of the appendix.
- •
In Section C, we provide the events dictionary.
- •
In Section D we provide the theoretical guarantees attained by Algorithm 3. Precisely, we provide the complete version of the primal algorithm (see Algorithm 4), and analyze the related performances.
- •
In Section E, we provide the theoretical guarantees attained by the dual algorithm.
- •
In Section F, we provide the analysis to bound the Lagrange multipliers during the learning dynamic.
- •
In Section G, we provide the theoretical guarantees attained by Algorithm 2 when the constraints are stochastic.
- •
In Section H, we provide the theoretical guarantees attained by Algorithm 2 when the constraints are adversarial.
- •
In Section I we provide the theoretical guarantees attained by Algorithm 2 when the constraints are adversarial and the baseline is computed w.r.t. the policies that satisfy the constraints at each episode.
- •
In Section J we provide technical lemmas employed in our work.
- •
In Section K, we provide auxiliary lemmas from existing works.

## Appendix A Related Works

In this section we provide further discussions on the works closely related to ours. We first provide some works in the field of unconstrained online MDPs (see (Auer et al., ; Even-Dar et al., ; Neu et al., ; Maran et al., ) for some initial results on the topic). The setting studied in these works generally differentiates the problem based on the nature of the losses (either stochastic or adversarial), the knowledge of the transition probability, and the nature of the feedback. Usually two types of feedback are considered: in the full-information feedback model, the entire loss function is observed after the learner’s choice, while in the bandit feedback model, the learner only observes the loss due to the chosen action.

Azar et al. () study the problem of optimal exploration in episodic MDPs with unknown transitions, stochastic losses and bandit feedback .
The authors improve the previous result by Auer et al. () designing an algorithm whose upper bound on the regret match the lower bound for this class, $\tilde{\mathcal{O}}(\sqrt{T})$.
Rosenberg and Mansour () studies the setting of episodic MDPs with adversarial losses, unknown transitions, and full information feedback. In this case the authors present an online algorithm exploiting entropic regularization and providing a regret upper bound of $\tilde{\mathcal{O}}(\sqrt{T})$.
The same setting is investigated when the feedback is bandit by Rosenberg and Mansour () who attain a regret upper bound of the order of $\tilde{\mathcal{O}}(T^{3/4})$, which is improved by
Jin et al. () by providing an algorithm that achieves in the same setting a regret upper bound of $\tilde{\mathcal{O}}(\sqrt{T})$. Bacchiocchi et al. () study online learning in adversarial MDPs when the feedback received is the one associated to a different agent. Finally, Luo et al. () provide an optimal policy optimization algorithm for adversarial MDPs with bandit feedback.

In case of constrained problem, an fundamental result is presented by Mannor et al. (), who show that it is impossible to attain both sublinear regret and constraints violations when both the losses and constraints are adversarial.
To overcome such an impossibility result, Liakopoulos et al. () study a class of online learning problems with long-term budget constraints that can be chosen by an adversary and they define a new notion of regret.
The new learner’s regret metric introduces the notion of a K-benchmark, *i.e.*, a comparator that meets the problem’s allotted budget over any window of length $K$.
Castiglioni et al. (, ) are the first to provide a best-of-both-worlds algorithm for online learning problems with long-term constraints, being the constraints stochastic or chosen by an adversary.

Constrained problems have been also studied in the context of CMDPs; however almost all previous works focus on the setting where the constraints are chosen stochastically.
Wei et al. () study the case of episodic CMDPs with known transition proabability, full-feedback, adversarial losses and stochastic constraints. The algorithm presented by the authors attains an upper bound both for constraints violation and for the regret of the order of $\tilde{\mathcal{O}}(\sqrt{T})$ .
Zheng and Ratliff () present, in the setting of stochastic losses and constraints, where the transition probabilities are known and the feedback is bandit, an upper bound on the regret of their algorithm of the order of $\tilde{\mathcal{O}}(T^{3/4})$, while the cumulative constraint violations is guaranteed to be below a threshold with a given probability.
Bai et al. () provide the first algorithm to achieve sublinear regret when the transition probabilities are unknown, assuming that the rewards are deterministic and the constraints are stochastic with a particular structure.
Efroni et al. () study the case where transition probabilities, rewards, and constraints are unknown and stochastic, while the feedback is bandit. The authors propose two approaches
to deal with the exploration-exploitation dilemma in episodic CMDPs guaranteeing sublinear regret and constraint violations.
Qiu et al. () provide a primal-dual approach based on optimism in the face of uncertainty. This work shows the effectiveness of such an approach when dealing with episodic CMDPs with adversarial losses and stochastic constraints, achieving both sublinear regret and constraint violation with full-information feedback.
Wei et al. (), Ding and Lavaei () and Stradi et al. () consider the case in which rewards and constraints are non-stationary, assuming that their variation is bounded.
Thus, their results are *not* applicable to general adversarial settings.
Stradi et al. (), in the setting with adversarial losses, stochastic constraints and partial feedback, achieve sublinear regret and sublinear positive constraints violations.
Stradi et al. () propose the first *best-of-both-worlds* algorithm for CMDPs, assuming *full feedback* on the rewards and constraints. Finally, Bacchiocchi et al. () study CMDPs with partial observability on the constraints.

## Appendix B Additional Notation

In the following section, we introduce some useful notation from policy optimization.
First, we define the value function $V^{\pi}(x;f)$, for policy $\pi$, state $x$ and generic function $f$ that assumes values for each state $x\in X$ and for each action $a\in A$. Formally,

$$ $V^{\pi}(x;f):=\mathbb{E}\left[\sum_{j=h(x)+1}^{H}f(x_{j},a_{j})|a_{j}\sim\pi( \cdot|x_{j}),x_{j}\sim P(\cdot|x_{j-1},a_{j-1})\right],$ $$

where $h(x)$ is the layer $h$ such that $x\in X_{h}$.
Notice that the value function can be written using the occupancy measure $q^{\pi,P}$ generated by the policy $\pi$ and the transition probability $P$ as : $V^{\pi}(x_{0};f)=\sum_{x,a}q^{\pi,P}(x,a)f(x,a)$.
We introduce also a ${Q}$-function of a generic function $f$ as:

$$ $\begin{cases}&Q(x,a;f)=f(x,a)+\mathbb{E}_{x^{\prime}\sim P(\cdot|x,a)}\left[V^ {\pi}(x^{\prime};f)\right]\\ &V^{\pi}(x;f)=\mathbb{E}_{a\sim\pi(\cdot|x)}\left[Q^{\pi}(x,a;f)\right]\\ &V^{\pi}(x_{H};f)=0\end{cases}$ $$

In addition we will use the notation $Q_{t}(x,a)$ to indicate the $Q$-function computed with respect to the function $\ell_{t}$, *i.e.* $Q(x,a;\ell_{t})$ .

## Appendix C Dictionary

In the following, we provide the definition of different quantities which will be employed in the rest of the appendix. This is done for the ease of presentation.

- •
Quantity $\mathcal{E}^{P}_{t_{1},t_{2}}$:
$\mathcal{E}^{P}_{t_{1},t_{2}}=U_{1}\Xi_{t_{1},t_{2}}C\sqrt{T}+U_{2}\Xi_{t_{1},
t_{2}}\frac{(t_{2}-t_{1}+1)}{C\sqrt{T}}+U_{3}\Xi_{t_{1},t_{2}}\frac{1}{C\sqrt{
T}}+U_{4}\Xi_{t_{1},t_{2}}\sqrt{T},$
where:
–
$U_{1}=6H^{2}\ln\left(\frac{H|A|T^{2}}{\delta}\right)$
–
$U_{2}={9H|X||A|}$
–
$U_{3}=\frac{H}{2}\ln\left(\frac{HT^{2}}{\delta}\right)$
–
$U_{4}=30H^{2}|X|^{2}\sqrt{2|A|\ln\left(\frac{T|X|^{2}|A|}{\delta}\right)}$.
With probability at least $1-4\delta$ it holds $R_{t_{1},t_{2}}^{P}\leq\mathcal{E}^{P}_{t_{1},t_{2}},~{}\forall t_{1},t_{2}\in
[T]:1\leq t_{1}\leq t_{2}\leq T$ by Theorem 3.
- •
Quantity $\mathcal{E}^{D}(\underline{0})$:
$\mathcal{E}^{D}(\underline{0})=D_{1}\frac{\lVert\lambda_{t_{1}}\rVert_{2}^{2}}
{\eta}+D_{2}\eta(t_{2}-t_{1}+1),$
where:
–
$D_{1}=\frac{1}{2}$
–
$D_{2}=\frac{mH^{2}}{2}$.
It holds $R_{t_{1},t_{2}}^{D}(\underline{0})\leq\mathcal{E}^{D}(\underline{0}),~{}
\forall t_{1},t_{2}\in[T]:1\leq t_{1}\leq t_{2}\leq T$ by Theorem 11.
- •
Quantity $\mathcal{E}^{G}_{t_{1},t_{2}}$:
$\mathcal{E}_{t_{1},t_{2}}^{G}=B_{1}\sqrt{(t_{2}-t_{1}+1)},$
where:
–
$B_{1}=2H\sqrt{\ln\left(\frac{T^{2}}{\delta}\right)}$.
Given a $q\in\Delta(M)$, with probability at least $1-\delta$ it holds in case of stochastic constraints $\sum_{t=t_{1}}^{t_{2}}(G_{t}^{\top}q-\overline{G}^{\top}q)\leq\mathcal{E}_{t_{
1},t_{2}}^{G}$, by Azuma-Hoeffding inequality.
- •
Quantity $\mathcal{E}_{t_{1},t_{2}}^{\mathbb{I}}$:
$\mathcal{E}_{t_{1},t_{2}}^{\mathbb{I}}=F_{1}\sqrt{(t_{2}-t_{1}+1)},$
where:
–
$F_{1}=H\sqrt{2\ln\left(\frac{T^{2}}{\delta}\right)}$.
With probability at least $1-\delta$ it holds $\sum_{t=t_{1}}^{t_{2}}\sum_{x,a}(\mathbb{I}_{t}(x,a)-q_{t}(x,a))\leq\mathcal{E
}_{t_{1},t_{2}}^{\mathbb{I}}$, and with probability at least $1-\delta$ it holds $\sum_{t=t_{1}}^{t_{2}}\sum_{x,a}(q_{t}(x,a)-\mathbb{I}_{t}(x,a))\leq\mathcal{E
}_{t_{1},t_{2}}^{\mathbb{I}}$, by Azuma-Hoeffding inequality.
- •
Quantity $C$:
$C=252|X||A|H$
- •
Quantity $D$:
$\displaystyle D$
$\displaystyle=84672mH^{2}|X|^{2}|A|$
$\displaystyle=336mH|X|C.$

## Appendix D Omitted Proofs for The Primal Algorithm

In this section we study the guarantees attained by the primal procedure, namely Algorithm 4.

Figure: Algorithm 4 FS-PODB

###### Theorem 10 .

For any $\delta\in(0,1)$, Algorithm 4 attains, with probability at least $1-4\delta$ and for all $[t_{1},\ldots,t_{2}]\subset[T]$:

$$ $\displaystyle\sum_{x}q^{*}(x)$ $\displaystyle\sum_{t=t_{1}}^{t_{2}}\sum_{a}\left(\pi_{t}(a|x)-\pi^{*}(a|x) \right)\left(Q_{t}^{\pi_{t}}(x,a)-B_{t}(x,a)\right)$ $\displaystyle=\Xi_{t_{1},t_{2}}o(T)+\sum_{t=t_{1}}^{t_{2}}V^{\pi^{*}}(x_{0};b_ {t})+\frac{1}{H}\sum_{t=t_{1}}^{t_{2}}\sum_{x,a}q^{*}(x)\pi_{t}(a|x)B_{t}(x,a),$ $$

for all $t_{1},t_{2}\in[T]\text{ s.t. }1\leq t_{1}\leq t_{2}\leq T$ and where $\Xi_{t_{1},t_{2}}\geq\max_{t\in[t_{1},\ldots,t_{2}]}\max_{x,a}\ell_{t}(x,a)$.

###### Proof.

In the rest of the proof, we will refer as $\bar{L}_{t}$ to $\max_{\tau\in[t]}\max_{h\in[H]}L_{\tau,h}$ and $\bar{L}_{t_{1},t_{2}}$ to $\max_{\tau\in[t_{1},\ldots,t_{2}]}\max_{h\in[H]}L_{\tau,h}$; therefore, by definition it holds $\bar{L}_{t}\leq H\Xi_{t}$ for all $t\in[T]$.
As a first step, we decompose $\sum_{x}q^{*}(x)\sum_{t=t_{1}}^{t_{2}}\sum_{a}\left(\pi_{t}(a|x)-\pi^{*}(a|x)
\right)\left(Q_{t}^{\pi_{t}}(x,a)-B_{t}(x,a)\right)$ in three different quantities:

$$ $\displaystyle\sum_{x}q^{*}(x)$ $\displaystyle\sum_{t=t_{1}}^{t_{2}}\sum_{a}\left(\pi_{t}(a|x)-\pi^{*}(a|x) \right)\left(Q_{t}^{\pi_{t}}(x,a)-B_{t}(x,a)\right)$ $\displaystyle=\underbrace{\sum_{x}q^{*}(x)\sum_{t=t_{1}}^{t_{2}}\sum_{a}\left( \pi_{t}(a|x)-\pi^{*}(a|x)\right)\left(\widehat{Q}_{t}(x,a)-B_{t}(x,a)\right)}_ {\leavevmode\hbox to8.9pt{\vbox to8.9pt{\pgfpicture\makeatletter\hbox{\hskip 4 .45195pt\lower-4.45195pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } \definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0} \pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ } \pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{4.25195pt}{0.0pt}\pgfsys@curveto{4.25195pt}{2.34831pt}{ 2.34831pt}{4.25195pt}{0.0pt}{4.25195pt}\pgfsys@curveto{-2.34831pt}{4.25195pt}{ -4.25195pt}{2.34831pt}{-4.25195pt}{0.0pt}\pgfsys@curveto{-4.25195pt}{-2.34831 pt}{-2.34831pt}{-4.25195pt}{0.0pt}{-4.25195pt}\pgfsys@curveto{2.34831pt}{-4.25 195pt}{4.25195pt}{-2.34831pt}{4.25195pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}$ $\displaystyle+\underbrace{\sum_{x}q^{*}(x)\sum_{t=t_{1}}^{t_{2}}\sum_{a}\pi_{t }(a|x)\left(Q_{t}^{\pi_{t}}(x,a)-\widehat{Q}_{t}(x,a)\right)}_{\leavevmode \hbox to8.9pt{\vbox to8.9pt{\pgfpicture\makeatletter\hbox{\hskip 4.45195pt \lower-4.45195pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{ pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt} \pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{4.25195pt}{0.0pt}\pgfsys@curveto{4.25195pt}{2.34831pt}{ 2.34831pt}{4.25195pt}{0.0pt}{4.25195pt}\pgfsys@curveto{-2.34831pt}{4.25195pt}{ -4.25195pt}{2.34831pt}{-4.25195pt}{0.0pt}\pgfsys@curveto{-4.25195pt}{-2.34831 pt}{-2.34831pt}{-4.25195pt}{0.0pt}{-4.25195pt}\pgfsys@curveto{2.34831pt}{-4.25 195pt}{4.25195pt}{-2.34831pt}{4.25195pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}$ $\displaystyle+\underbrace{\sum_{x}q^{*}(x)\sum_{t=t_{1}}^{t_{2}}\sum_{a}\pi^{* }(a|x)\left(\widehat{Q}_{t}(x,a)-Q_{t}^{\pi_{t}}(x,a)\right)}_{\leavevmode \hbox to8.9pt{\vbox to8.9pt{\pgfpicture\makeatletter\hbox{\hskip 4.45195pt \lower-4.45195pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{ pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt} \pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{4.25195pt}{0.0pt}\pgfsys@curveto{4.25195pt}{2.34831pt}{ 2.34831pt}{4.25195pt}{0.0pt}{4.25195pt}\pgfsys@curveto{-2.34831pt}{4.25195pt}{ -4.25195pt}{2.34831pt}{-4.25195pt}{0.0pt}\pgfsys@curveto{-4.25195pt}{-2.34831 pt}{-2.34831pt}{-4.25195pt}{0.0pt}{-4.25195pt}\pgfsys@curveto{2.34831pt}{-4.25 195pt}{4.25195pt}{-2.34831pt}{4.25195pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}},$ $$

which we proceed to bound separately.

###### Theorem 10 .

###### Proof.

##### Bound on \protecting 1 .

The quantity of interest can be bounded after noticing that Algorithm 4 employs a slightly modified version of OMD.
In fact, recalling the definition of $\pi_{t}$, we can write:

$$ $\displaystyle\pi_{t+1}(a|x)$ $\displaystyle=\frac{w_{t+1}(a|x)}{\sum_{a^{\prime}}w_{t+1}(a^{\prime}|x)}$ $\displaystyle=\frac{(1-\sigma)w_{t}(a|x)e^{-\eta_{t}\left(\widehat{Q}_{t}(x,a) -B_{t}(x,a)\right)}+\frac{\sigma}{|A|}\sum_{a^{\prime}\in A}w_{t}(a^{\prime}|x )e^{-\eta_{t}\left(\widehat{Q}_{t}(x,a^{\prime})-B_{t}(x,a^{\prime})\right)}}{ \sum_{a^{\prime}\in A}w_{t}(a^{\prime}|x)e^{-\eta_{t}\left(\widehat{Q}_{t}(x,a ^{\prime})-B_{t}(x,a^{\prime})\right)}}$ $\displaystyle=(1-\sigma)\frac{\pi_{t}(a|x)e^{-\eta\left(\widehat{Q}_{t}(x,a)-B _{t}(x,a)\right)}}{\sum_{a^{\prime}}\pi_{t}(a^{\prime}|x)e^{-\eta\left( \widehat{Q}_{t}(x,a^{\prime})-B_{t}(x,a^{\prime})\right)}}+\sigma\frac{1}{|A|}.$ $$

From now on we will refer to $\frac{\pi_{t}(a|x)e^{-\eta\left(\widehat{Q}_{t}(x,a)-B_{t}(x,a)\right)}}{\sum_
{a^{\prime}}\pi_{t}(a^{\prime}|x)e^{-\eta\left(\widehat{Q}_{t}(x,a^{\prime})-B
_{t}(x,a^{\prime})\right)}}$ as $\widetilde{\pi}_{t+1}(x,a)$. Thus,

$$ $\pi_{t+1}(a|x)=(1-\sigma)\widetilde{\pi}_{t+1}(x,a)+\frac{\sigma}{|A|}.$ $$

Calling $\psi(\cdot)$ the negative entropy function defined as $\psi(\pi(\cdot|x))\coloneq\sum_{a}\pi(a|x)\ln\left(\pi(a|x)\right)$, by standard analysis (*e.g.* Orabona ()), it holds:

$$ $\widetilde{\pi}_{t+1}(\cdot|x)=\operatorname*{arg\,min}_{\pi(\cdot|x)\in\Delta (A)}\sum_{a}\left(\widehat{Q}_{t}(x,a)-B_{t}(x,a)\right)\pi(a|x)+\frac{1}{\eta }D_{\psi}(\pi(\cdot|x);\pi_{t}(\cdot|x)),$ $$

where $D_{\psi}$ is Bregman divergence w.r.t. the negative entropy function $\psi(\cdot)$.
Thus, for all $\pi(\cdot|x)$ it holds
$\eta_{t}\sum_{a}\left(\widehat{Q}_{t}(x,a)-B_{t}(x,a)\right)\left(\pi(a|x)-
\widetilde{\pi}_{t+1}(x,a)\right)+\langle\nabla\psi(\widetilde{\pi}_{t+1}(
\cdot|x))-\nabla\psi(\pi_{t}(\cdot|x)),\pi(\cdot|x)-\widetilde{\pi}_{t+1}(
\cdot|x)\rangle\geq 0.$
So, for all $\pi(\cdot|x)$ the following holds:

$$ $\displaystyle\eta_{t}\langle\widehat{Q}_{t}(x,\cdot)-B_{t}(x,\cdot),\pi_{t}( \cdot|x)-\pi(\cdot|x)\rangle$ $\displaystyle=\eta_{t}\langle\widehat{Q}_{t}(x,\cdot)-B_{t}(x,\cdot)+\nabla \psi(\widetilde{\pi}_{t+1}(\cdot|x))-\nabla\psi(\pi_{t}(\cdot|x)),\widetilde{ \pi}_{t+1}(\cdot|x)-\pi(\cdot|x)\rangle$ $\displaystyle\mkern 150.0mu+\eta_{t}\langle\widehat{Q}_{t}(x,\cdot)-B_{t}(x, \cdot),\pi_{t}(\cdot|x)-\widetilde{\pi}_{t+1}(\cdot|x)\rangle$ $\displaystyle\mkern 300.0mu+\langle\nabla\psi(\widetilde{\pi}_{t+1}(\cdot|x))- \nabla\psi(\pi_{t}(\cdot|x)),\pi(\cdot|x)-\widetilde{\pi}_{t+1}(\cdot|x)\rangle$ $\displaystyle\leq\langle\eta_{t}\left(\widehat{Q}_{t}(x,\cdot)-B_{t}(x,\cdot) \right),\pi_{t}(\cdot|x)-\widetilde{\pi}_{t+1}(\cdot|x)\rangle$ $\displaystyle\mkern 200.0mu+\langle\nabla\psi(\widetilde{\pi}_{t+1}(\cdot|x))- \nabla\psi(\pi_{t}(\cdot|x)),\pi(\cdot|x)-\widetilde{\pi}_{t+1}(\cdot|x)\rangle$ $\displaystyle\leq D_{\psi}(\pi(\cdot|x);\pi_{t}(\cdot|x))-D_{\psi}(\pi(\cdot|x );\widetilde{\pi}_{t+1}(\cdot|x))-D_{\psi}(\widetilde{\pi}_{t+1}(\cdot|x);\pi_ {t}(\cdot|x))$ $\displaystyle\mkern 300.0mu+{\eta_{t}}\langle\widehat{Q}_{t}(x,\cdot)-B_{t}(x, \cdot),\pi_{t}(\cdot|x)-\widetilde{\pi}_{t+1}(\cdot|x)\rangle$ (3) $\displaystyle=D_{\psi}(\pi(\cdot|x);\pi_{t}(\cdot|x))-D_{\psi}(\pi(\cdot|x); \widetilde{\pi}_{t+1}(\cdot|x))+\frac{\eta_{t}^{2}}{2}\sum_{a\in A}\left( \widehat{Q}_{t}(x,a)-B_{t}(x,a)\right)^{2}\pi_{t}(a|x),$ (4) $$

where Inequality (3) and Inequality (4) are based on the proofs of Lemma 6.6. and Lemma 6.9. in Orabona ().

Additionally we can show that for all $t\in[T]$: $D_{\psi}(\pi(\cdot|x);\pi_{t}(\cdot|x))-D_{\psi}(\pi(\cdot|x);\widetilde{\pi}_
{t}(\cdot|x))\leq\sigma\ln(|A|)$. Indeed,

$$ $\displaystyle D_{\psi}\left(\pi(\cdot|x);\pi_{t}(\cdot|x)\right)$ $\displaystyle-D_{\psi}\left(\pi(\cdot|x);\widetilde{\pi}_{t}(\cdot|x)\right)$ $\displaystyle=D_{\psi}\left(\pi(\cdot|x);(1-\sigma)\widetilde{\pi}_{t}(\cdot|x )+\sigma\pi^{\frac{1}{|A|}}\right)-D_{\psi}\left(\pi(\cdot|x);\widetilde{\pi}_ {t}(\cdot|x)\right)$ $\displaystyle\leq\sigma D_{\psi}\left(\pi(\cdot|x);\pi^{\frac{1}{|A|}}\right)- \sigma D_{\psi}\left(\pi(\cdot|x);\widetilde{\pi}_{t}(\cdot|x)\right)$ $\displaystyle\leq\sigma\ln(|A|),$ $$

where the last inequality holds since $D_{\psi}(\pi(\cdot|x);\widetilde{\pi}_{t}(\cdot|x))\geq 0$ and

$$ $\displaystyle D_{\psi}(\pi(\cdot|x);\pi^{\frac{1}{|A|}})$ $\displaystyle=\sum_{a\in A}\pi(a|x)\ln\left(\frac{\pi(a|x)}{\pi^{\frac{1}{|A|} }(a|x)}\right)$ $\displaystyle\leq\sum_{a\in A}\pi(a|x)\ln\left(\frac{1}{\pi^{\frac{1}{|A|}}(a| x)}\right)$ $\displaystyle=\sum_{a\in A}\pi(a|x)\ln\left(|A|\right)$ $\displaystyle=\ln(|A|).$ $$

Notice that with we refer as $\pi^{\frac{1}{|A|}}$ to the vector strategy in $[0,1]^{|A|}$ with all elements equal to $\frac{1}{|A|}$.

Moreover we bound $D_{\psi}(\pi(\cdot|x);\pi_{t_{1}}(\cdot|x))$, since $\pi_{t_{1}}(a|x)=(1-\sigma)\widetilde{\pi}_{t_{1}}(a|x)+\sigma(\frac{1}{|A|})
\geq\frac{\sigma}{|A|}$, as follows:

$$ $\displaystyle D_{\psi}(\pi(\cdot|x);\pi_{t_{1}}(\cdot|x))$ $\displaystyle=\sum_{a\in A}\pi(a|x)\ln\left(\frac{\pi(a|x)}{\pi_{t_{1}}(a|x)}\right)$ $\displaystyle\leq\sum_{a\in A}\pi(a|x)\ln\left(\frac{1}{\pi_{t_{1}}(a|x)}\right)$ $\displaystyle\leq\sum_{a\in A}\pi(a|x)\ln\left(\frac{|A|}{\sigma}\right)$ $\displaystyle=\ln\left(\frac{|A|}{\sigma}\right).$ $$

Putting everything together we have that:

$$ 1 $\displaystyle=\sum_{x}q^{*}(x)\sum_{t=t_{1}}^{t_{2}}\sum_{a}\left(\pi_{t}(a|x) -\pi^{*}(a|x)\right)\left(\widehat{Q}_{t}(x,a)-B_{t}(x,a)\right)$ $\displaystyle\leq\sum_{x}q^{*}(x)\left(\frac{D_{\psi}(\pi(\cdot|x);\pi_{t_{1}} (\cdot|x))}{\eta_{t_{1}}}+\sum_{t=t_{1}+1}^{t_{2}}\left(\frac{D_{\psi}(\pi( \cdot|x);\pi_{t}(\cdot|x))}{\eta_{t}}-\frac{D_{\psi}(\pi(\cdot|x);\widetilde{ \pi}_{t}(\cdot|x))}{\eta_{t+1}}\right)\right)$ $\displaystyle\mkern 250.0mu+\sum_{x}q^{*}(x)\sum_{t=t_{1}}^{t_{2}}\frac{\eta_{ t}}{2}\left(\widehat{Q}_{t}(x,a)-B_{t}(x,a)\right)^{2}\pi_{t}(a|x)$ (5a) $\displaystyle\leq\sum_{x}q^{*}(x)\left(\frac{D_{\psi}(\pi(\cdot|x);\pi_{t_{1}} (\cdot|x))}{\eta_{t_{1}}}+\sum_{t=t_{1}+1}^{t_{2}}\left(\frac{D_{\psi}(\pi( \cdot|x);\pi_{t}(\cdot|x))-D_{\psi}(\pi(\cdot|x);\widetilde{\pi}_{t}(\cdot|x)) }{\eta_{t}}\right)\right)$ $\displaystyle\mkern 250.0mu+\sum_{x}q^{*}(x)\sum_{t=t_{1}}^{t_{2}}\frac{\eta_{ t}}{2}\left(\widehat{Q}_{t}(x,a)-B_{t}(x,a)\right)^{2}\pi_{t}(a|x)$ (5b) $\displaystyle\leq\frac{\ln\left(\frac{|A|}{\sigma}\right)}{\eta_{t_{1}}}+ \sigma\sum_{t=t_{1}+1}^{t_{2}}\frac{\ln(|A|)}{\eta_{t_{2}}}+\sum_{x}q^{*}(x) \sum_{t=t_{1}}^{t_{2}}\frac{\eta_{t}}{2}\left(\widehat{Q}_{t}(x,a)-B_{t}(x,a) \right)^{2}\pi_{t}(a|x)$ (5c) $\displaystyle\leq\frac{\ln\left(\frac{|A|}{\sigma}\right)}{\eta_{t_{1}}}+\frac {\sigma T\ln(|A|)}{\eta_{t_{2}}}+\sum_{x}q^{*}(x)\sum_{t=t_{1}}^{t_{2}}\frac{ \eta_{t}}{2}\left(\widehat{Q}_{t}(x,a)-B_{t}(x,a)\right)^{2}\pi_{t}(a|x)$ $\displaystyle=\frac{\ln\left(|A|T\right)}{\eta_{t_{1}}}+\frac{\ln(|A|)}{\eta_{ t_{2}}}+\sum_{x}q^{*}(x)\sum_{t=t_{1}}^{t_{2}}\frac{\eta_{t}}{2}\left(\widehat {Q}_{t}(x,a)-B_{t}(x,a)\right)^{2}\pi_{t}(a|x),$ $$

where $\sigma=\frac{1}{T}$,
Inequality (5a) holds by Inequality (4) , Inequality (5b) holds since $\frac{1}{\eta_{t+1}}\geq\frac{1}{\eta_{t}}$ for all $t\in[T]$, and Inequality (5c) holds since $\eta_{t_{2}}\leq\eta_{t}$ for all $t$ in $[t_{1}+1,\ldots,t_{2}]$.
Focusing now on the last part of the right term, with probability at least $1-2\delta$ the following holds:

$$ $\displaystyle\sum_{x}\sum_{a}q^{*}(x)\sum_{t=t_{1}}^{t_{2}}\frac{\eta_{t}}{2} \left(\widehat{Q}_{t}(x,a)-B_{t}(x,a)\right)^{2}\pi_{t}(a|x)$ $\displaystyle\leq\sum_{t=t_{1}}^{t_{2}}\eta_{t}\sum_{x}\sum_{a}q^{*}(x)\pi_{t} (a|x)\widehat{Q}_{t}(x,a)^{2}+\sum_{t=t_{1}}^{t_{2}}\eta_{t}\sum_{x}\sum_{a}q^ {*}(x)\pi_{t}(a|x)B_{t}(x,a)^{2}$ (6a) $\displaystyle=\sum_{t=t_{1}}^{t_{2}}\eta_{t}\sum_{x}\sum_{a}q^{*}(x)\pi_{t}(a| x)\frac{L_{t,h}^{2}}{(\overline{q}_{t}(x,a)+\gamma)^{2}}\mathbb{I}_{t}(x,a)+ \sum_{t=t_{1}}^{t_{2}}\eta_{t}\sum_{x}\sum_{a}q^{*}(x)\pi_{t}(a|x)B_{t}(x,a)^{2}$ (6b) $\displaystyle\leq\bar{L}_{t_{1},t_{2}}\sum_{t=t_{1}}^{t_{2}}\eta_{t}\bar{L}_{t }\sum_{x}\sum_{a}\frac{q^{*}(x)\pi_{t}(a|x)}{\overline{q}_{t}(x,a)+\gamma} \frac{\mathbb{I}_{t}(x,a)}{\overline{q}_{t}(x,a)+\gamma}+\sum_{t=t_{1}}^{t_{2} }\eta_{t}\sum_{x}\sum_{a}q^{*}(x)\pi_{t}(a|x)B_{t}(x,a)^{2}$ (6c) $\displaystyle\leq\frac{\gamma}{2H}\bar{L}_{t_{1},t_{2}}\sum_{t=t_{1}}^{t_{2}} \sum_{x}\sum_{a}\frac{q^{*}(x)\pi_{t}(a|x)}{\overline{q}_{t}(x,a)+\gamma}\frac {q_{t}(x,a)}{\overline{q}_{t}(x,a)+\gamma}+\frac{\gamma\bar{L}_{t_{1},t_{2}}}{ 2}\ln\left(\frac{HT^{2}}{\delta}\right)$ $\displaystyle\mkern 300.0mu+\sum_{t=t_{1}}^{t_{2}}\eta_{t}\sum_{x}\sum_{a}q^{* }(x)\pi_{t}(a|x)B_{t}(x,a)^{2}$ (6d) $\displaystyle\leq\sum_{t=t_{1}}^{t_{2}}\sum_{x}\sum_{a}q^{*}(x)\pi_{t}(a|x) \frac{\gamma\Xi_{t_{1},t_{2}}}{2(\overline{q}_{t}(x,a)+\gamma)}+\frac{\gamma \bar{L}_{t_{1},t_{2}}}{2}\ln\left(\frac{HT^{2}}{\delta}\right)$ $\displaystyle\mkern 300.0mu+\frac{1}{2H}\sum_{t=t_{1}}^{t_{2}}\sum_{x}\sum_{a} q^{*}(x)\pi_{t}(a|x)B_{t}(x,a)$ (6e) $\displaystyle=\sum_{t=t_{1}}^{t_{2}}\sum_{x}\sum_{a}q^{*}(x)\pi_{t}(a|x)\left( \frac{\gamma\Xi_{t_{1},t_{2}}}{2(\overline{q}_{t}(x,a)+\gamma)}+\frac{B_{t}(x, a)}{2H}\right)+\frac{\gamma\bar{L}_{t_{1},t_{2}}}{2}\ln\left(\frac{HT^{2}}{ \delta}\right),$ $$

where Inequality (6a) holds since $(a-b)^{2}\leq 2a^{2}+2b^{2}$, for all $a,b\in\mathbb{R}$, Equality (6b) holds by definition of $\widehat{Q}(x,a)$, Inequality (6c) is motivated by the fact that $L_{t,h}\leq\bar{L}_{t_{1},t_{2}}$ by its definition, Inequality (6d) holds with probability at least $1-\delta$ by applying Lemma 9 and taking $\alpha_{t}(x,a)=\frac{q^{*}(x)\pi_{t}(a|x)}{\overline{q}_{t}(x,a)+\gamma}$ since $\frac{q^{*}(x)\pi_{t}(a|x)}{\overline{q}_{t}(x,a)+\gamma}\leq\frac{1}{\gamma}$ and considering that by definition $\eta_{t}\Xi_{t}=\frac{\gamma}{2H}$, and finally Inequality (6e) holds since $\overline{q}_{t}(x,a)\geq q_{t}(x,a),~{}\forall(x,a)\in X\times A,\forall t\in
[t_{1}\ldots t_{2}]$ with probability at least $1-\delta$ by Lemma 12 and by Lemma 6.
Setting $\gamma=2\eta_{t}H\Xi_{t}$, we can conclude that, with probability at least $1-2\delta$, 1 is bounded as:

$$ $\frac{4H\Xi_{t_{1},t_{2}}\ln(|A|T)}{\gamma}+\gamma\frac{H\Xi_{t_{1},t_{2}}}{2} \ln\left(\frac{HT^{2}}{\delta}\right)+\sum_{t=t_{1}}^{t_{2}}\sum_{x}\sum_{a}q^ {*}(x)\pi_{t}(a|x)\left(\frac{\gamma\Xi_{t_{1},t_{2}}}{2(\overline{q}_{t}(x,a) +\gamma)}+\frac{B_{t}(x,a)}{2H}\right).$ $$

##### Bound on \protecting 2 .

To bound 2 we employ the same approach as in (Luo et al., ). First we define $Y_{t}$ as $Y_{t}:=\sum_{x}\sum_{a}q^{*}(x)\pi_{t}(a|x)\widehat{Q}_{t}(x,a)$, for all $t\in[T]$. Now since $\sum_{t=t_{1}}^{t_{2}}Y_{t}$ is a martingale sequence , we apply Freedman’s inequality. First notice that under the event $P\in\mathcal{P}_{i}(t)$ for all $t\in[T]$:

$$ $\displaystyle\mathbb{E}[Y_{t}^{2}]$ $\displaystyle\leq\mathbb{E}_{t}\left[\left(\sum_{x}\sum_{a}q^{*}(x)\pi_{t}(a|x )\widehat{Q}_{t}(x,a)\right)^{2}\right]$ $\displaystyle\leq\mathbb{E}_{t}\left[\left(\sum_{x}\sum_{a}q^{*}(x)\pi_{t}(a|x )\right)\left(\sum_{x}\sum_{a}q^{*}(x)\pi_{t}(a|x)\widehat{Q}_{t}(x,a)^{2} \right)\right]$ $\displaystyle=H\mathbb{E}_{t}\left[\sum_{x}\sum_{a}q^{*}(x)\pi_{t}(a|x) \widehat{Q}_{t}(x,a)^{2}\right]$ $\displaystyle=H\sum_{x}\sum_{a}q^{*}(x)\pi_{t}(a|x)\frac{L_{t,h}^{2}}{( \overline{q}_{t}(x,a)+\gamma)^{2}}q_{t}(x,a)$ $\displaystyle\leq\sum_{x}\sum_{a}q^{*}(x)\pi_{t}(a|x)\frac{H\bar{L}_{t}^{2}}{ \overline{q}_{t}(x,a)+\gamma}.$ $$

Thus, thanks to Lemma 8, since $|Y_{t}|\leq H\sup_{x^{\prime},a^{\prime}}\widehat{Q}_{t}(x,a)\leq\frac{H\bar{L
}_{t}}{\gamma}$, with probability at least $1-\delta$ it holds simultaneously for all $t_{1},t_{2}:1\leq t_{1}\leq t_{2}\leq T$:

$$ $\sum_{t=t_{1}}^{t_{2}}\left(\mathbb{E}_{t}[Y_{t}]-Y_{t}\right)\leq\frac{\gamma }{H\bar{L}_{t_{1},t_{2}}}\sum_{t=t_{1}}^{t_{2}}\sum_{x}\sum_{a}q^{*}(x)\pi_{t} (a|x)\frac{H\bar{L}_{t}^{2}}{\overline{q}_{t}(x,a)+\gamma}+\frac{H\bar{L}_{t_{ 1},t_{2}}}{\gamma}\log\left(\frac{T^{2}}{\delta}\right).$ $$

We notice also the following result with probability at least $1-\delta$ for all $t\in[T]$:

$$ $\displaystyle\sum_{x}\sum_{a}$ $\displaystyle q^{*}(x)\pi_{t}(a|x)Q_{t}(x,a)-\mathbb{E}[Y_{t}]$ $\displaystyle=\sum_{x}\sum_{a}q^{*}(x)\pi_{t}(a|x)Q_{t}(x,a)-\mathbb{E}\left[ \sum_{x}\sum_{a}q^{*}(x)\pi_{t}(a|x)\widehat{Q}_{t}(x,a)\right]$ $\displaystyle=\sum_{x}\sum_{a}q^{*}(x)\pi_{t}(a|x)Q_{t}(x,a)\left(1-\frac{q_{t }(x,a)}{\overline{q}_{t}(x,a)+\gamma}\right)$ $\displaystyle\leq\sum_{x}\sum_{a}q^{*}(x)\pi_{t}(a|x)H\Xi_{t}\left(\frac{ \overline{q}_{t}(x,a)-q_{t}(x,a)+\gamma}{\overline{q}_{t}(x,a)+\gamma}\right)$ $\displaystyle\leq\sum_{x}\sum_{a}q^{*}(x)\pi_{t}(a|x)H\Xi_{t}\left(\frac{( \overline{q}_{t}(x,a)-\underline{q}_{t}(x,a))+\gamma}{\overline{q}_{t}(x,a)+ \gamma}\right).$ $$

Finally we can bound 2 with probability at least $1-2\delta$ as follows.

$$ 2 $\displaystyle=\sum_{x}q^{*}(x)\sum_{t=t_{1}}^{t_{2}}\sum_{a}\pi_{t}(a|x)\left( Q_{t}^{\pi_{t}}(x,a)-\widehat{Q}_{t}(x,a)\right)$ $\displaystyle=\sum_{t=t_{1}}^{t_{2}}(\mathbb{E}_{t}[Y_{t}]-Y_{t})+\sum_{t=t_{1 }}^{t_{2}}\left(\sum_{x}\sum_{a}q^{*}(x)\pi_{t}(a|x)Q_{t}(x,a)-\mathbb{E}[Y_{t }]\right)$ $\displaystyle\leq\sum_{t=t_{1}}^{t_{2}}\sum_{x}\sum_{a}q^{*}(x)\pi_{t}(a|x)H \Xi_{t}\left(\frac{(\overline{q}_{t}(x,a)-\underline{q}_{t}(x,a))+2\gamma}{ \overline{q}_{t}(x,a)+\gamma}\right)+\frac{H\bar{L}_{t_{1},t_{2}}}{\gamma}\ln \left(\frac{T^{2}}{\delta}\right).$ $$

##### Bound on \protecting 3 .

With probability at least $1-2\delta$ it holds:

$$ 3 $\displaystyle=\sum_{x}q^{*}(x)\sum_{t=t_{1}}^{t_{2}}\sum_{a}\pi^{*}(a|x)\left( \widehat{Q}_{t}(x,a)-Q_{t}^{\pi_{t}}(x,a)\right)\leq\frac{H^{2}\Xi_{t_{1},t_{2 }}}{2\gamma}\ln\left(\frac{HT^{2}}{\delta}\right),$ $$

by Corollary 1.

##### Conclusion of the proof

Finally we notice that, with probability at least $1-4\delta$, we have the following result.

$$ $\displaystyle\sum_{x}q^{*}(x)$ $\displaystyle\sum_{t=t_{1}}^{t_{2}}\sum_{a}\left(\pi_{t}(a|x)-\pi^{*}(a|x) \right)\left(Q_{t}^{\pi_{t}}(x,a)-B_{t}(x,a)\right)=\leavevmode\hbox to11.37pt {\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657 pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor }{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt} \pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{ 3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{ -5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018 pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48 657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}+\leavevmode\hbox to11.37pt{\vbox to11.37pt{ \pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{ 3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{ -5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018 pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48 657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}+\leavevmode\hbox to11.37pt{\vbox to11.37pt{ \pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{ 3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{ -5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018 pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48 657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}$ $\displaystyle\leq\gamma\frac{H\Xi_{t_{1},t_{2}}}{2}\ln\left(\frac{HT^{2}}{ \delta}\right)+\frac{6H^{2}\Xi_{t_{1},t_{2}}}{\gamma}\ln\left(\frac{H|A|T^{2}} {\delta}\right)$ $\displaystyle\mkern 75.0mu+\sum_{t=t_{1}}^{t_{2}}\sum_{x,a}q^{*}(x)\pi_{t}(a|x )\left(\frac{\Xi_{t}(3\gamma H+H(\overline{q}_{t}(x,a)-\underline{q}_{t}(x,a)) )}{\overline{q}_{t}(x,a)+\gamma}+\frac{B_{t}(x,a)}{H}\right).$ $$

This concludes the proof.
∎

See 3

###### Proof.

By means of Theorem 10 and by Lemma 7 we have that with probability at least $1-4\delta$:

$$ $R_{t_{1},t_{2}}^{P}\leq\gamma\frac{H\Xi_{t_{1},t_{2}}}{2}\ln\left(\frac{HT^{2} }{\delta}\right)+\frac{6H^{2}\Xi_{t_{1},t_{2}}}{\gamma}\ln\left(\frac{H|A|T^{2 }}{\delta}\right)+3\sum_{t=t_{1}}^{t_{2}}\widehat{V}^{\pi_{t}}(x_{0};b_{t}).$ $$

We can bound $\sum_{t=1}^{T}\widehat{V}^{\pi_{t}}(x_{0};b_{t})$, with probability at least $1-4\delta$, as:

$$ $\displaystyle\sum_{t=t_{1}}^{t_{2}}\widehat{V}^{\pi_{t}}(x_{0};b_{t})$ $\displaystyle=\sum_{t=t_{1}}^{t_{2}}\sum_{x,a}q^{\widehat{P}_{t},\pi_{t}}(x,a) \left(\frac{H\Xi_{t}(\overline{q}_{t}(x,a)-\underline{q}_{t}(x,a))+3H\Xi_{t} \gamma}{\overline{q}_{t}(x,a)+\gamma}\right)$ $\displaystyle\leq\sum_{t=t_{1}}^{t_{2}}\sum_{x,a}H\Xi_{t}\left((\overline{q}_{ t}(x,a)-\underline{q}_{t}(x,a))+3\gamma\right)$ $\displaystyle\leq\sum_{t=t_{1}}^{t_{2}}\sum_{x,a}H\Xi_{t}(\overline{q}_{t}(x,a )-\underline{q}_{t}(x,a))+3\Xi_{t_{1},t_{2}}\gamma H(t_{2}-t_{1}+1)|X||A|$ $\displaystyle\leq 4H^{2}\Xi_{t_{1},t_{2}}|X|^{2}\sqrt{2T\ln\left(\frac{H|X|}{ \delta}\right)}+6\Xi_{t_{1},t_{2}}H^{2}|X|^{2}\sqrt{2T|A|\ln\left(\frac{T|X|^{ 2}|A|}{\delta}\right)}$ $\displaystyle\mkern 450.0mu+3\Xi_{t_{1},t_{2}}\gamma H|X||A|(t_{2}-t_{1}+1),$ $$

where the second inequality holds under the event $q^{\widehat{P}_{t},\pi_{t}}(x,a)\leq\bar{q}_{t}(x,a)$ for all $(x,a)\in X\times A$ and for all $t\in[T]$ and the last inequality uses Lemma 10.
Thus, with probability at least $1-8\delta$, it holds:

$$ $\displaystyle R_{t_{1},t_{2}}^{P}$ $\displaystyle\leq\gamma\frac{H\Xi_{t_{1},t_{2}}}{2}\ln\left(\frac{HT^{2}}{ \delta}\right)+\frac{6H^{2}\Xi_{t_{1},t_{2}}}{\gamma}\ln\left(\frac{H|A|T^{2}} {\delta}\right)+30\Xi_{t_{1},t_{2}}H^{2}|X|^{2}\sqrt{2T|A|\ln\left(\frac{T|X|^ {2}|A|}{\delta}\right)}+$ $\displaystyle\mkern 350.0mu+9\Xi_{t_{1},t_{2}}\gamma H|X||A|(t_{2}-t_{1}+1)$ $\displaystyle\leq\frac{H\Xi_{t_{1},t_{2}}}{2C\sqrt{T}}\ln\left(\frac{HT^{2}}{ \delta}\right)+6H^{2}\Xi_{t_{1},t_{2}}C\sqrt{T}\ln\left(\frac{H|A|T^{2}}{ \delta}\right)$ $\displaystyle\mkern 120.0mu+30\Xi_{t_{1},t_{2}}H^{2}|X|^{2}\sqrt{2T|A|\ln\left (\frac{T|X|^{2}|A|}{\delta}\right)}+{9H|X||A|\Xi_{t_{1},t_{2}}}\frac{(t_{2}-t_ {1}+1)}{C\sqrt{T}}$ $\displaystyle=U_{1}\Xi_{t_{1},t_{2}}C\sqrt{T}+U_{2}\Xi_{t_{1},t_{2}}\frac{(t_{ 2}-t_{1}+1)}{C\sqrt{T}}+U_{3}\Xi_{t_{1},t_{2}}\frac{1}{C\sqrt{T}}+U_{4}\Xi_{t_ {1},t_{2}}\sqrt{T}$ $\displaystyle=\mathcal{E}^{P}_{t_{1},t_{2}},$ $$

which concludes the proof.
∎

###### Proof.

## Appendix E Omitted Proofs for the Dual Algorithm

###### Theorem 11 .

When employed by Algorithm 2, online projected gradient descent (OGD) attains:

$$ $R^{D}_{t_{1},t_{2}}(\lambda)=\sum_{t=t_{1}}^{t_{2}}(\lambda-\lambda_{t})^{\top }\sum_{h=0}^{H-1}G_{t}(x_{h},a_{h})\leq\frac{\lVert\lambda_{t_{1}}-\lambda \rVert_{2}^{2}}{2\eta}+\frac{\eta}{2}(t_{2}-t_{1}+1)mH^{2}.$ $$

###### Proof.

We proceed to prove the theorem following (Orabona, ). Indeed, it holds:

$$ $\displaystyle R^{D}_{t_{1},t_{2}}(\lambda)$ $\displaystyle=\sum_{t=t_{1}}^{t_{2}}(\lambda-\lambda_{t})^{\top}\sum_{h=0}^{H- 1}G_{t}(x_{h},a_{h})$ $\displaystyle\leq\frac{\lVert\lambda_{t_{1}}-\lambda\rVert_{2}^{2}}{2\eta}+ \frac{\eta}{2}\sum_{t=t_{1}}^{t_{2}}\lVert\sum_{h=0}^{H-1}G_{t}(x_{h},a_{h}) \rVert_{2}^{2}$ $\displaystyle\leq\frac{\lVert\lambda_{t_{1}}-\lambda\rVert_{2}^{2}}{2\eta}+ \frac{\eta}{2}\sum_{t=t_{1}}^{t_{2}}\sum_{i=1}^{m}\left(\sum_{h=0}^{H-1}G_{t,i }(x_{h},a_{h})\right)^{2}$ $\displaystyle\leq\frac{\lVert\lambda_{t_{1}}-\lambda\rVert_{2}^{2}}{2\eta}+ \frac{\eta}{2}\sum_{t=t_{1}}^{t_{2}}mH^{2}$ $\displaystyle\leq\frac{\lVert\lambda_{t_{1}}-\lambda\rVert_{2}^{2}}{2\eta}+ \frac{\eta}{2}(t_{2}-t_{1}+1)mH^{2}.$ $$

This concludes the proof.
∎

###### Lemma 1 .

When employed by Algorithm 2, online projected gradient descent (OGD) guarantees for all $t\in[T]$:

$$ $\lVert\lambda_{t+1}\rVert_{1}-\lVert\lambda_{t}\rVert_{1}\leq mH\eta.$ $$

###### Proof.

It holds:

$$ $\displaystyle\lambda_{t+1,i}$ $\displaystyle=\min\bigg{\{}\max\bigg{\{}0,\lambda_{t,i}+\eta\sum_{h=0}^{H-1}g_ {t,i}(x_{h},a_{h})\bigg{\}},T^{\frac{1}{4}}\bigg{\}}$ $\displaystyle\leq\max\bigg{\{}0,\lambda_{t,i}+\eta\sum_{h=0}^{H-1}g_{t,i}(x_{h },a_{h})\bigg{\}}$ $\displaystyle\leq\max\bigg{\{}0,\lambda_{t,i}+\eta\sum_{h=0}^{H-1}1\bigg{\}}$ $\displaystyle=\lambda_{t,i}+\eta H,$ $$

which concludes the proof when we take the sum over all $i\in[m]$.
∎

###### Theorem 11 .

###### Proof.

###### Lemma 1 .

###### Proof.

## Appendix F Analysis on Lagrangian multipliers

###### Lemma 2 .

The loss given to the primal algorithm at episode $t\in[T]$, which is defined as $\ell_{t}(x,a)=\Gamma_{t}+\sum_{i\in[m]}\lambda_{t,i}g_{t,i}(x,a)-r_{t}(x,a)$, is such that, considering the Lagrangian loss function $\ell^{\mathcal{L}}_{t}(x,a)=\sum_{i\in[m]}\lambda_{t,i}g_{t,i}(x,a)-r_{t}(x,a)$, it holds:

$$ ${\ell}_{t}^{\top}(q_{t}-q^{*})=\ell_{t}^{\mathcal{L},\top}(q_{t}-q^{*}),$ $$

and additionally, ${\ell}_{t}$ assume values in the bounded interval $\left[0,\Xi_{t}\right]$.

###### Proof.

By simple computation, it holds:

$$ $\displaystyle{\ell}_{t}^{\top}(q_{t}-q^{*})-\ell_{t}^{\mathcal{L},\top}(q_{t}- q^{*})$ $\displaystyle=\Bigg{(}\sum_{x,a}\Gamma_{t}(q_{t}(x,a)-q^{*}(x,a))+\sum_{i\in[m ]}\sum_{x,a}\lambda_{t,i}g_{t,i}(x,a)(q_{t}(x,a)-q^{*}(x,a))$ $\displaystyle\mkern 300.0mu-\sum_{x,a}r_{t}(x,a)(q_{t}(x,a)-q^{*}(x,a))\Bigg{)}$ $\displaystyle\mkern 75.0mu-\left(\sum_{i\in[m]}\sum_{x,a}\lambda_{t,i}g_{t,i}( x,a)(q_{t}(x,a)-q^{*}(x,a))-\sum_{x,a}r_{t}(x,a)(q_{t}(x,a)-q^{*}(x,a))\right)$ $\displaystyle=\sum_{x,a}\Gamma_{t}(q_{t}(x,a)-q^{*}(x,a))$ $\displaystyle=\Gamma_{t}(H-H)$ $\displaystyle=0,$ $$

where the last steps hold since $\Gamma_{t}$ is a constant and by the definition of *valid* occupancy measures.

In addition it holds:

$$ $\displaystyle\ell_{t}(x,a)=\Gamma_{t}+\sum_{i\in[m]}\lambda_{t,i}g_{t,i}(x,a)- r_{t}(x,a)\geq 1+\lVert\lambda_{t}\rVert_{1}-\sum_{i\in[m]}\lambda_{t,i}-1=0,$ $$

and similarly,

$$ $\displaystyle{\ell}_{t}(x,a)=\Gamma_{t}+\sum_{i\in[m]}\lambda_{t,i}g_{t,i}(x,a )-r_{t}(x,a)\leq\Gamma_{t}+\sum_{i\in[m]}\lambda_{t,i}=1+2\lVert\lambda_{t} \rVert\leq\Xi_{t}.$ $$

This concludes the proof.
∎

See 4

###### Proof.

Let $M>1$ be a constant. By absurd suppose $\exists t_{2}\in[T]$ s.t.

$$ $\forall t\leq t_{2}\quad\lVert\lambda_{t}\rVert_{1}\leq\frac{2HM}{\rho^{2}} \quad\land\quad\lVert\lambda_{t_{2}+1}\rVert_{1}>\frac{2HM}{\rho^{2}}$ (7) $$

and let $t_{1}<t_{2}$ s.t.

$$ $\lVert\lambda_{t_{1}-1}\rVert_{1}\leq\frac{2H}{\rho}\quad\land\quad\forall t:t _{1}\leq t\leq t_{2}~{}\lVert\lambda_{t}\rVert_{1}\geq\frac{2H}{\rho}.$ $$

By construction $1<\frac{2H}{\rho}\leq\lVert\lambda_{t}\rVert_{1}\leq\frac{2HM}{\rho^{2}}$ for all $t_{1}\leq t\leq t_{2}$, and it holds if $\eta\leq\frac{1}{mH}$:

$$ $\lVert\lambda_{t_{1}}\rVert_{1}\leq\lVert\lambda_{t_{1}-1}\rVert_{1}+m\eta H \leq\frac{2H}{\rho}+m\eta H\leq\frac{4H}{\rho}.$ (8) $$

Notice also that by construction, calling $\lambda_{t_{1},t_{2}}=\max_{t\in[t_{1},\ldots t_{2}]}\lVert\lambda_{t}\rVert_{1}$, it holds:

$$ $1<\lambda_{t_{1},t_{2}}\leq\frac{2HM}{\rho^{2}}\quad\land\quad 1+\lambda_{t_{1 },t_{2}}<\frac{4HM}{\rho^{2}}.$ (9) $$

In the stochastic setting the following holds by Azuma-Hoeffding inequality with probability at least $1-\delta$:

$$ $\displaystyle\sum_{t=t_{1}}^{t_{2}}-\lambda_{t}^{\top}G_{t}^{\top}q^{\circ}$ $\displaystyle\geq\sum_{t=t_{1}}^{t_{2}}-\lambda_{t}^{\top}\overline{G}^{\top}q ^{\circ}-\lambda_{t_{1},t_{2}}\mathcal{E}_{t_{1},t_{2}}^{G}$ $\displaystyle\geq\lambda_{t_{1},t_{2}}(t_{2}-t_{1}+1)\rho-\lambda_{t_{1},t_{2} }\mathcal{E}_{t_{1},t_{2}}^{G}$ $\displaystyle\geq(t_{2}-t_{1}+1)2H-\lambda_{t_{1},t_{2}}\mathcal{E}_{t_{1},t_{ 2}}^{G},$ $$

where $\mathcal{E}_{t_{1},t_{2}}^{G}=B_{1}\sqrt{(t_{2}-t_{1}+1)}=2H\sqrt{\ln\left(
\nicefrac{{T^{2}}}{{\delta}}\right)}\sqrt{(t_{2}-t_{1}+1)}$.
Instead, in the adversarial setting, it holds:

$$ $\displaystyle\sum_{t=t_{1}}^{t_{2}}-\lambda_{t}^{\top}G_{t}^{\top}q^{\circ}$ $\displaystyle\geq\sum_{t=t_{1}}^{t_{2}}\sum_{i=1}^{m}-\lambda_{t,i}\left[G_{t} ^{\top}q^{\circ}\right]_{i}$ $\displaystyle\geq\rho\sum_{t=t_{1}}^{t_{2}}\sum_{i=1}^{m}\lambda_{t,i}$ $\displaystyle=\rho\sum_{t=t_{1}}^{t_{2}}\lVert\lambda_{t}\rVert_{1}$ $\displaystyle\geq(t_{2}-t_{1}+1)2H.$ $$

Generalizing the result, it holds, both for the stochastic and the adversarial setting, the following inequality with probability equal to 1 in the adversarial case and with probability at least $1-\delta$ in the stochastic case:

$$ $\sum_{t=t_{1}}^{t_{2}}-\lambda_{t}^{\top}G_{t}^{\top}q^{\circ}\geq(t_{2}-t_{1} +1)2H-\lambda_{t_{1},t_{2}}\mathcal{E}_{t_{1},t_{2}}^{G}.$ $$

Thank to this result we can find a lower bound for $-\sum_{t=t_{1}}^{t_{2}}\ell_{t}^{\mathcal{L},\top}q_{t}$ with probability at least $1-9\delta$ in the stochastic setting and with probability at least $1-8\delta$ in the adversarial case, employing Theorem 3 .

$$ $\displaystyle-\sum_{t=t_{1}}^{t_{2}}\ell_{t}^{\mathcal{L},\top}q_{t}$ $\displaystyle=\sum_{t=t_{1}}^{t_{2}}(r_{t}^{\top}q^{\circ}-\lambda^{\top}G_{t} ^{\top}q^{\circ})-\sum_{t=t_{1}}^{t_{2}}\ell_{t}^{\mathcal{L},\top}(q_{t}-q^{ \circ})$ $\displaystyle\geq\sum_{t=t_{1}}^{t_{2}}-\lambda^{\top}G_{t}^{\top}q^{\circ}- \sum_{t=t_{1}}^{t_{2}}\ell_{t}^{\mathcal{L},\top}(q_{t}-q^{\circ})$ (10) $\displaystyle\geq 2H(t_{2}-t_{1}+1)-\lambda_{t_{1},t_{2}}\mathcal{E}^{G}_{t_{1 },t_{2}}-\mathcal{E}^{P}_{t_{1},t_{2}},$ (11) $$

where Inequality (10) holds since $r_{t}^{\top}q^{\circ}\geq 0$, for all $t\in[T]$, and Inequality (11) is derived using the bound on the primal interval regret given by Theorem 3 and defined as $\mathcal{E}_{t_{1},t_{2}}^{P}$ and by Lemma 2.
At the same time, it is possible to define also an upper bound for the same quantity $-\sum_{t=t_{1}}^{t_{2}}\ell_{t}^{\mathcal{L},\top}q_{t}$ with probability at least $1-2\delta$:

$$ $\displaystyle-\sum_{t=t_{1}}^{t_{2}}\ell_{t}^{\mathcal{L},\top}q_{t}$ $\displaystyle=\sum_{t=t_{1}}^{t_{2}}(r_{t}^{\top}q_{t}-\lambda_{t}^{\top}G_{t} ^{\top}q_{t})$ $\displaystyle\leq\sum_{t=t_{1}}^{t_{2}}H-\sum_{t=t_{1}}^{t_{2}}\lambda_{t}^{ \top}(G_{t}^{\top}q_{t}-\sum_{h=0}^{H-1}G_{t}(x_{h},a_{h}))+\sum_{t=t_{1}}^{t_ {2}}(\underline{0}-\lambda_{t})\sum_{h=0}^{H-1}G_{t}(x_{h},a_{h})$ $\displaystyle\leq H(t_{2}-t_{1}+1)+\lambda_{t_{1},t_{2}}\sum_{t=t_{1}}^{t_{2}} \sum_{x,a}G_{t}(x,a)(\mathbb{I}_{t}(x,a)-q_{t}(x,a))+\mathcal{E}_{t_{1},t_{2}} ^{D}(\underline{0})$ $\displaystyle\leq H(t_{2}-t_{1}+1)+\lambda_{t_{1},t_{2}}\mathcal{E}_{t_{1},t_{ 2}}^{\mathbb{I}}+\mathcal{E}_{t_{1},t_{2}}^{D}(\underline{0}),$ $$

where $\mathcal{E}^{\mathbb{I}}=F_{1}\sqrt{(t_{2}-t_{1}+1)}=H\sqrt{2\ln\left(
\nicefrac{{T^{2}}}{{\delta}}\right)}\sqrt{(t_{2}-t_{1}+1)}$ and $\mathcal{E}^{D}(\underline{0})=D_{1}\frac{\lVert\lambda_{t_{1}}\rVert_{2}^{2}}
{\eta}+D_{2}\eta(t_{2}-t_{1}+1)=\frac{1}{2}\frac{\lVert\lambda_{t_{1}}\rVert_{
2}^{2}}{\eta}+\frac{mH^{2}}{2}\eta(t_{2}-t_{1}+1)$.
Thus, combining the two bounds we get with probability at least $1-10\delta$ in the adversarial case and $1-11\delta$ in the stochastic case the following bound,

$$ $2H(t_{2}-t_{1}+1)-\lambda_{t_{1},t_{2}}\mathcal{E}_{t_{1},t_{2}}^{G}-\mathcal{ E}_{t_{1},t_{2}}^{P}\leq H(t_{2}-t_{1}+1)+\lambda_{t_{1},t_{2}}\mathcal{E}_{t_ {1},t_{2}}^{\mathbb{I}}+\mathcal{E}_{t_{1},t_{2}}^{D}(\underline{0}),$ $$

which can be reordered as

$$ $H(t_{2}-t_{1}+1)\leq\lambda_{t_{1},t_{2}}\mathcal{E}_{t_{1},t_{2}}^{G}+\lambda _{t_{1},t_{2}}\mathcal{E}_{t_{1},t_{2}}^{\mathbb{I}}+\mathcal{E}_{t_{1},t_{2}} ^{D}(\underline{0})+\mathcal{E}_{t_{1},t_{2}}^{P}.$ $$

We recall here the definitions of the bounds $\mathcal{E}_{t_{1},t_{2}}^{G},\mathcal{E}_{t_{1},t_{2}}^{\mathbb{I}},\mathcal{
E}_{t_{1},t_{2}}^{D}(\underline{0})$ and $\mathcal{E}_{t_{1},t_{2}}^{P}$.

$$ $\mathcal{E}_{t_{1},t_{2}}^{G}=B_{1}\sqrt{(t_{2}-t_{1}+1)},$ $$

where $B_{1}=2H\sqrt{\ln\left(\frac{T^{2}}{\delta}\right)}$.

$$ $\mathcal{E}_{t_{1},t_{2}}^{\mathbb{I}}=F_{1}\sqrt{(t_{2}-t_{1}+1)},$ $$

where $F_{1}=H\sqrt{2\ln\left(\frac{T^{2}}{\delta}\right)}$.

$$ $\mathcal{E}_{t_{1},t_{2}}^{D}(\underline{0})=D_{1}\frac{\lVert\lambda_{t_{1}} \rVert_{2}^{2}}{\eta}+D_{2}\eta(t_{2}-t_{1}+1),$ $$

where $D_{1}=\frac{1}{2},~{}D_{2}=\frac{mH^{2}}{2}$.

$$ $\mathcal{E}_{t_{1},t_{2}}^{P}=U_{1}\Xi_{t_{1},t_{2}}C\sqrt{T}+U_{2}\Xi_{t_{1}, t_{2}}\frac{(t_{2}-t_{1}+1)}{C\sqrt{T}}+U_{3}\Xi_{t_{1},t_{2}}\frac{1}{C\sqrt{ T}}+U_{4}\Xi_{t_{1},t_{2}}\sqrt{T},$ $$

where $U_{1}=6H^{2}\ln\left(\frac{H|A|T^{2}}{\delta}\right)$, $U_{2}={9H|X||A|}$, $U_{3}=\frac{H}{2}\ln\left(\frac{HT^{2}}{\delta}\right)$ and $U_{4}=30H^{2}|X|^{2}\sqrt{2|A|\ln\left(\frac{T|X|^{2}|A|}{\delta}\right)}$.

Thus, we can write:

$$ $\displaystyle H(t_{2}-t_{1}+1)\leq$ $\displaystyle\underbrace{\lambda_{t_{1},t_{2}}(F_{1}+B_{1})\sqrt{(t_{2}-t_{1}+ 1)}}_{\leavevmode\hbox to8.9pt{\vbox to8.9pt{\pgfpicture\makeatletter\hbox{ \hskip 4.45195pt\lower-4.45195pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke { }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0} \pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ } \pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{4.25195pt}{0.0pt}\pgfsys@curveto{4.25195pt}{2.34831pt}{ 2.34831pt}{4.25195pt}{0.0pt}{4.25195pt}\pgfsys@curveto{-2.34831pt}{4.25195pt}{ -4.25195pt}{2.34831pt}{-4.25195pt}{0.0pt}\pgfsys@curveto{-4.25195pt}{-2.34831 pt}{-2.34831pt}{-4.25195pt}{0.0pt}{-4.25195pt}\pgfsys@curveto{2.34831pt}{-4.25 195pt}{4.25195pt}{-2.34831pt}{4.25195pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}+\underbrace{U_{2}\Xi_{t_{1},t_{2}}\frac{t_{ 2}-t_{1}+1}{C\sqrt{T}}}_{\leavevmode\hbox to8.9pt{\vbox to8.9pt{\pgfpicture \makeatletter\hbox{\hskip 4.45195pt\lower-4.45195pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{4.25195pt}{0.0pt}\pgfsys@curveto{4.25195pt}{2.34831pt}{ 2.34831pt}{4.25195pt}{0.0pt}{4.25195pt}\pgfsys@curveto{-2.34831pt}{4.25195pt}{ -4.25195pt}{2.34831pt}{-4.25195pt}{0.0pt}\pgfsys@curveto{-4.25195pt}{-2.34831 pt}{-2.34831pt}{-4.25195pt}{0.0pt}{-4.25195pt}\pgfsys@curveto{2.34831pt}{-4.25 195pt}{4.25195pt}{-2.34831pt}{4.25195pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}$ $\displaystyle+\underbrace{U_{3}\Xi_{t_{1},t_{2}}\frac{1}{C\sqrt{T}}}_{ \leavevmode\hbox to8.9pt{\vbox to8.9pt{\pgfpicture\makeatletter\hbox{\hskip 4. 45195pt\lower-4.45195pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } \definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0} \pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ } \pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{4.25195pt}{0.0pt}\pgfsys@curveto{4.25195pt}{2.34831pt}{ 2.34831pt}{4.25195pt}{0.0pt}{4.25195pt}\pgfsys@curveto{-2.34831pt}{4.25195pt}{ -4.25195pt}{2.34831pt}{-4.25195pt}{0.0pt}\pgfsys@curveto{-4.25195pt}{-2.34831 pt}{-2.34831pt}{-4.25195pt}{0.0pt}{-4.25195pt}\pgfsys@curveto{2.34831pt}{-4.25 195pt}{4.25195pt}{-2.34831pt}{4.25195pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}+\underbrace{U_{1}\Xi_{t_{1},t_{2}}C\sqrt{T} }_{\leavevmode\hbox to8.9pt{\vbox to8.9pt{\pgfpicture\makeatletter\hbox{\hskip 4 .45195pt\lower-4.45195pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } \definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0} \pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ } \pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{4.25195pt}{0.0pt}\pgfsys@curveto{4.25195pt}{2.34831pt}{ 2.34831pt}{4.25195pt}{0.0pt}{4.25195pt}\pgfsys@curveto{-2.34831pt}{4.25195pt}{ -4.25195pt}{2.34831pt}{-4.25195pt}{0.0pt}\pgfsys@curveto{-4.25195pt}{-2.34831 pt}{-2.34831pt}{-4.25195pt}{0.0pt}{-4.25195pt}\pgfsys@curveto{2.34831pt}{-4.25 195pt}{4.25195pt}{-2.34831pt}{4.25195pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{4}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}+\underbrace{D_{2}\eta(t_{2}-t_{1}+1)}_{ \leavevmode\hbox to8.9pt{\vbox to8.9pt{\pgfpicture\makeatletter\hbox{\hskip 4. 45195pt\lower-4.45195pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } \definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0} \pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ } \pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{4.25195pt}{0.0pt}\pgfsys@curveto{4.25195pt}{2.34831pt}{ 2.34831pt}{4.25195pt}{0.0pt}{4.25195pt}\pgfsys@curveto{-2.34831pt}{4.25195pt}{ -4.25195pt}{2.34831pt}{-4.25195pt}{0.0pt}\pgfsys@curveto{-4.25195pt}{-2.34831 pt}{-2.34831pt}{-4.25195pt}{0.0pt}{-4.25195pt}\pgfsys@curveto{2.34831pt}{-4.25 195pt}{4.25195pt}{-2.34831pt}{4.25195pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{5}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}$ $\displaystyle+\underbrace{D_{1}\frac{\lVert\lambda_{t_{1}}\rVert_{2}^{2}}{\eta }}_{\leavevmode\hbox to8.9pt{\vbox to8.9pt{\pgfpicture\makeatletter\hbox{ \hskip 4.45195pt\lower-4.45195pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke { }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0} \pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ } \pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{4.25195pt}{0.0pt}\pgfsys@curveto{4.25195pt}{2.34831pt}{ 2.34831pt}{4.25195pt}{0.0pt}{4.25195pt}\pgfsys@curveto{-2.34831pt}{4.25195pt}{ -4.25195pt}{2.34831pt}{-4.25195pt}{0.0pt}\pgfsys@curveto{-4.25195pt}{-2.34831 pt}{-2.34831pt}{-4.25195pt}{0.0pt}{-4.25195pt}\pgfsys@curveto{2.34831pt}{-4.25 195pt}{4.25195pt}{-2.34831pt}{4.25195pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{6}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}+\underbrace{U_{4}\Xi_{t_{1},t_{2}}\sqrt{T}} _{\leavevmode\hbox to8.9pt{\vbox to8.9pt{\pgfpicture\makeatletter\hbox{\hskip 4 .45195pt\lower-4.45195pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } \definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0} \pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ } \pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{4.25195pt}{0.0pt}\pgfsys@curveto{4.25195pt}{2.34831pt}{ 2.34831pt}{4.25195pt}{0.0pt}{4.25195pt}\pgfsys@curveto{-2.34831pt}{4.25195pt}{ -4.25195pt}{2.34831pt}{-4.25195pt}{0.0pt}\pgfsys@curveto{-4.25195pt}{-2.34831 pt}{-2.34831pt}{-4.25195pt}{0.0pt}{-4.25195pt}\pgfsys@curveto{2.34831pt}{-4.25 195pt}{4.25195pt}{-2.34831pt}{4.25195pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{7}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}.$ $$

To conclude the proof by absurd it is sufficient to prove that all $\leavevmode\hbox to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{
\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke
{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}
\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{
3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{
-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018
pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48
657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}},\leavevmode\hbox to11.37pt{\vbox to11.37pt{
\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{
3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{
-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018
pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48
657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}},\leavevmode\hbox to11.37pt{\vbox to11.37pt{
\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{
3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{
-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018
pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48
657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}},\leavevmode\hbox to11.37pt{\vbox to11.37pt{
\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{
3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{
-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018
pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48
657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{4}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}},\leavevmode\hbox to11.37pt{\vbox to11.37pt{
\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{
3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{
-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018
pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48
657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{5}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}},\leavevmode\hbox to11.37pt{\vbox to11.37pt{
\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{
3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{
-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018
pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48
657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{6}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}},\leavevmode\hbox to11.37pt{\vbox to11.37pt{
\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{
3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{
-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018
pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48
657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{7}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}$ are smaller or equal to $\frac{H(t_{2}-t_{1}+1)}{7}$, with at least one being strictly smaller.

Prove $\protecting{\leavevmode\hbox to11.37pt{\vbox to11.37pt{\pgfpicture
\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{
3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{
-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018
pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48
657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}}<\frac{H(t_{2}-t_{1}+1)}{7}$
If $\eta\leq\frac{1}{14m(F_{1}+B_{1})\sqrt{T}}$, then $\protecting{\leavevmode\hbox to11.37pt{\vbox to11.37pt{\pgfpicture
\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{
3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{
-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018
pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48
657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}}<\frac{H(t_{2}-t_{1}+1)}{7}$ holds. Indeed:

$$ $\displaystyle\frac{H(t_{2}-t_{1}+1)}{7}$ $\displaystyle>\frac{HM}{7\rho^{2}m\eta}$ (12a) $\displaystyle\geq\frac{2HM}{\rho^{2}}(F_{1}+B_{1})\sqrt{T}$ (12b) $\displaystyle\geq\lambda_{t_{1},t_{2}}(F_{1}+B_{1})\sqrt{T}$ (12c) $\displaystyle\geq\lambda_{t_{1},t_{2}}(F_{1}+B_{1})\sqrt{t_{2}-t_{1}+1},$ $$

where Inequality (12a) holds by Lemma 11, Inequality (12b) is equivalent to condition $\eta\leq\frac{1}{14m(F_{1}+B_{1})\sqrt{T}}$ and Inequality (12c) is true by Assumption (7).

Prove $\protecting{\leavevmode\hbox to11.37pt{\vbox to11.37pt{\pgfpicture
\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{
3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{
-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018
pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48
657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}}<\frac{H(t_{2}-t_{1}+1)}{7}$
If $C\geq 56\frac{MU_{2}}{\rho^{2}\sqrt{T}}$ holds, then $\leavevmode\hbox to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{
\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke
{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}
\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{
3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{
-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018
pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48
657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}<\frac{H(t_{2}-t_{1}+1)}{7}$ also holds. Indeed:

$$ $\displaystyle\frac{H(t_{2}-t_{1}+1)}{7}$ $\displaystyle\geq 2U_{2}\left(\frac{4HM}{\rho^{2}}\right)\frac{t_{2}-t_{1}+1}{ C\sqrt{T}}$ (13a) $\displaystyle>U_{2}2(1+\lambda_{t_{1},t_{2}})\frac{t_{2}-t_{1}+1}{C\sqrt{T}}$ (13b) $\displaystyle\geq U_{2}\Xi_{t_{1},t_{2}}\frac{t_{2}-t_{1}+1}{C\sqrt{T}},$ (13c) $$

where Inequality (13a) is equivalent to the condition $C\geq 56\frac{MU_{2}}{\rho^{2}\sqrt{T}}$, Inequality (13b) holds by Inequality (9) and Inequality (13c) is true since $\Xi_{t_{1},t_{2}}\leq 2(1+\lambda_{t_{1},t_{2}})$.

Prove $\protecting{\leavevmode\hbox to11.37pt{\vbox to11.37pt{\pgfpicture
\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{
3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{
-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018
pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48
657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}}<\frac{H(t_{2}-t_{1}+1)}{7}$ If $\eta\leq\frac{C\sqrt{T}}{56mU_{3}}$ holds then also $\leavevmode\hbox to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{
\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke
{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}
\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{
3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{
-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018
pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48
657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}<\frac{H(t_{2}-t_{1}+1)}{7}$ holds. Indeed:

$$ $\displaystyle\frac{H(t_{2}-t_{1}+1)}{7}$ $\displaystyle>\frac{HM}{7\rho^{2}m\eta}$ (14a) $\displaystyle\geq U_{3}2\frac{4HM}{\rho^{2}}\frac{1}{C\sqrt{T}}$ (14b) $\displaystyle\geq U_{3}2(1+\lambda_{t_{1},t_{2}})\frac{1}{C\sqrt{T}}$ (14c) $\displaystyle\geq U_{3}\Xi_{t_{1},t_{2}}\frac{1}{C\sqrt{T}},$ (14d) $$

where Inequality (14a) hold by Lemma 11, Inequality (14b) holds if condition $\eta\leq\frac{C\sqrt{T}}{56mU_{3}}$ holds, and Inequality (14c) and Inequality (14d) follow the same reasoning as Inequality (13b) and Inequality (13c).

Prove $\protecting{\leavevmode\hbox to11.37pt{\vbox to11.37pt{\pgfpicture
\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{
3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{
-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018
pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48
657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{4}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}}<\frac{H(t_{2}-t_{1}+1)}{7}$
If $\eta\leq\frac{1}{56mU_{1}C\sqrt{T}}$ holds then also $\leavevmode\hbox to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{
\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke
{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}
\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{
3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{
-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018
pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48
657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{4}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}<\frac{H(t_{2}-t_{1}+1)}{7}$ holds. Indeed:

$$ $\displaystyle\frac{H(t_{2}-t_{1}+1)}{7}$ $\displaystyle>\frac{HM}{7\rho^{2}m\eta}$ $\displaystyle\geq U_{1}2\frac{4HM}{\rho^{2}}{C\sqrt{T}}$ (15) $\displaystyle\geq U_{1}2(1+\lambda_{t_{1},t_{2}}){C\sqrt{T}}$ $\displaystyle\geq U_{1}\Xi_{t_{1},t_{2}}{C\sqrt{T}},$ $$

where Inequality (15) holds when condition $\eta\leq\frac{1}{56mU_{1}C\sqrt{T}}$ also holds, and the rest of the inequalities follow a similar reasoning to the one used to bound 3.

Prove $\protecting{\leavevmode\hbox to11.37pt{\vbox to11.37pt{\pgfpicture
\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{
3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{
-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018
pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48
657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{5}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}}\leq\frac{H(t_{2}-t_{1}+1)}{7}$ It is immediate to see that if $\eta\leq\frac{H}{7D_{2}}$ holds, then it holds also that:

$$ $\protecting{\leavevmode\hbox to11.37pt{\vbox to11.37pt{\pgfpicture \makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{ 3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{ -5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018 pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48 657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{5}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}=D_{2}\eta(t_{2}-t_{1}+1)\leq\frac{H(t_{2}-t _{1}+1)}{7}.$ $$

Prove $\protecting{\leavevmode\hbox to11.37pt{\vbox to11.37pt{\pgfpicture
\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{
3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{
-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018
pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48
657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{6}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}}<\frac{H(t_{2}-t_{1}+1)}{7}$

If the condition $M\geq 112D_{1}Hm$ is satisfied than the inequality $\protecting{\leavevmode\hbox to11.37pt{\vbox to11.37pt{\pgfpicture
\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{
3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{
-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018
pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48
657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{6}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}}<\frac{H(t_{2}-t_{1}+1)}{7}$ holds too. Indeed:

$$ $\displaystyle\frac{H(t_{2}-t_{1}+1)}{7}$ $\displaystyle>\frac{HM}{7\rho^{2}m\eta}$ (16a) $\displaystyle\geq D_{1}\frac{16H^{2}}{\rho^{2}}\frac{1}{\eta}$ (16b) $\displaystyle\geq D_{1}\frac{\lVert\lambda_{t_{1}}\rVert_{1}^{2}}{\eta}$ (16c) $\displaystyle\geq D_{1}\frac{\lVert\lambda_{t_{1}}\rVert_{2}^{2}}{\eta},$ $$

where Inequality 16a holds by Lemma 11, Inequality (16b) holds when the condition $M\geq 112D_{1}Hm$ is satisfied and Inequality (16c) holds by Inequality (8).

Prove $\protecting{\leavevmode\hbox to11.37pt{\vbox to11.37pt{\pgfpicture
\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{
3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{
-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018
pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48
657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{7}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}}<\frac{H(t_{2}-t_{1}+1)}{7}$
If the condition $\eta\leq\frac{1}{56mU_{4}\sqrt{T}}$ is satisfied then $\protecting{\leavevmode\hbox to11.37pt{\vbox to11.37pt{\pgfpicture
\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{
3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{
-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018
pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48
657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{7}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}}<\frac{H(t_{2}-t_{1}+1)}{7}$ also holds. In fact

$$ $\displaystyle\frac{H(t_{2}-t_{1}+1)}{7}$ $\displaystyle>\frac{HM}{7\rho^{2}m\eta}$ (17a) $\displaystyle\geq U_{4}2\frac{4HM}{\rho^{2}}\sqrt{T}$ (17b) $\displaystyle\geq U_{4}2(1+\lambda_{t_{1},t_{2}})\sqrt{T}$ $\displaystyle\geq U_{4}\Xi_{t_{1},t_{2}}\sqrt{T}.$ $$

where Inequality (17a) holds by Lemma11 and inequality (17b) holds if condition $\eta\leq\frac{1}{56mU_{4}\sqrt{T}}$ also holds.

###### Lemma 2 .

###### Proof.

###### Proof.

##### Conclusion of the proof

Thus, we have the following 3 conditions:

- •
First condition:
$\displaystyle M$
$\displaystyle\geq 112D_{1}Hm$
$\displaystyle=112\frac{1}{2}Hm$
$\displaystyle=56Hm.$
- •
Second condition:
$\displaystyle C$
$\displaystyle\geq 56\frac{MU_{2}}{\rho^{2}\sqrt{T}}$
$\displaystyle=56\frac{M9H|X||A|}{\rho^{2}\sqrt{T}}.$
- •
Third condition:
$\eta\leq\min\bigg{\{}\frac{1}{14m(F_{1}+B_{1})\sqrt{T}},\frac{C\sqrt{T}}{56mU_
{3}},\frac{1}{56mU_{1}C\sqrt{T}},\frac{H}{7D_{2}},\frac{1}{56mU_{4}\sqrt{T}}
\bigg{\}}.$

Thus, we set $M$ as $M=56Hm$, and consequently, under Condition 2 we set $C=252|X||A|H$ since

$$ $\displaystyle C$ $\displaystyle=252|X||A|H$ $\displaystyle\geq 252|X||A|$ $\displaystyle\geq 252|X||A|\frac{112mH^{2}}{\rho^{2}}\frac{1}{\sqrt{T}}$ $\displaystyle=56\frac{(56Hm)9H|X||A|}{\rho^{2}\sqrt{T}}$ $\displaystyle=56\frac{9MH|X||A|}{\rho^{2}\sqrt{T}}.$ $$

Notice that the inequality is deduced directly by Condition 2. In fact if $\rho\geq T^{\frac{1}{8}}H\sqrt{112m}$ then it is also true that

$$ $\frac{112mH^{2}}{\rho^{2}}\leq T^{\frac{1}{4}}\leq\sqrt{T}.$ $$

As a final remark, we choose $252|X||A|H$ as value of $C$ instead of the smaller value $252|X||A|$, which is useful for Lemma 6.
Finally we study the condition on $\eta$.

$$ $\displaystyle\min\bigg{\{}$ $\displaystyle\frac{1}{14m(F_{1}+B_{1})\sqrt{T}},\frac{C\sqrt{T}}{56mU_{3}}, \frac{1}{56mU_{1}C\sqrt{T}},\frac{H}{7D_{2}},\frac{1}{56mU_{4}\sqrt{T}}\bigg{\}}$ $\displaystyle\geq\min\Bigg{\{}\frac{1}{14m\left(4H\sqrt{\ln\left(\frac{T^{2}}{ \delta}\right)}\right)\sqrt{T}},\frac{252|X||A|H\sqrt{T}}{56m\left(\frac{H}{2} \ln\left(\frac{HT^{2}}{\delta}\right)\right)},$ $\displaystyle\quad\frac{1}{56m\left(6H^{2}\ln\left(\frac{H|A|T^{2}}{\delta} \right)\right)\left(252|X||A|H\right)\sqrt{T}},\frac{H}{7\left(\frac{mH^{2}}{2 }\right)},$ $\displaystyle\quad\frac{1}{56m\left(30H^{2}|X|^{2}\sqrt{2|A|\ln\left(\frac{T|X |^{2}|A|}{\delta}\right)}\right)\sqrt{T}}\Bigg{\}}$ $\displaystyle\geq\frac{1}{84672mH^{2}|X|^{2}|A|\ln\left(\frac{|A||X|^{2}T^{2}} {\delta}\right)\sqrt{T}}.$ $$

Thus, the proof is concluded taking $\eta=\frac{1}{84672mH^{2}|X|^{2}|A|\ln\left(\frac{|A||X|^{2}T^{2}}{\delta}
\right)\sqrt{T}}$.
∎

###### Lemma 3 .

If Condition 2 holds, for all $t\in[T]$ and for each constraints $i\in[m]$, it holds:

$$ $\lambda_{t,i}\geq\eta\widehat{V}_{t-1,i},$ $$

where $\widehat{V}_{t,i}:=\sum_{\tau=1}^{t}\sum_{x,a}g_{\tau,i}(x,a)\mathbb{I}_{\tau}
(x,a)$.

###### Proof.

First observe that with $t=1$ we have that $\widehat{V}_{t-1,i}$ is the sum of zero elements and as such, it is equal to zero.
This means that for $t=1$ the inequality $\lambda_{t,i}\geq\eta\widehat{V}_{t-1,i}$ is equivalent to

$$ $\lambda_{t,i}\geq 0,$ $$

which is true by construction.
We finish the proof by induction. Suppose $\lambda_{t,i}\geq\eta\widehat{V}_{t-1,i}$ is true for a $t\in[T]$, we show that it also holds for $t+1$, indeed:

$$ $\displaystyle\lambda_{t+1,i}$ $\displaystyle=\max\bigg{\{}\lambda_{t,i}+\eta\sum_{h=0}^{H-1}g_{t,i}(x_{h},a_{ h}),0\bigg{\}}$ $\displaystyle=\max\bigg{\{}\lambda_{t,i}+\eta\sum_{x,a}g_{t,i}(x,a)\mathbb{I}_ {t}(x,a),0\bigg{\}}$ $\displaystyle\geq\lambda_{t,i}+\eta\sum_{x,a}g_{t,i}(x,a)\mathbb{I}_{t}(x,a)$ $\displaystyle\geq\eta\widehat{V}_{t-1,i}+\eta\sum_{x,a}g_{t,i}(x,a)\mathbb{I}_ {t}(x,a)$ $\displaystyle=\eta\left(\sum_{\tau=1}^{t-1}g_{\tau,i}(x,a)\mathbb{I}_{\tau}(x, a)+g_{t,i}(x,a)\mathbb{I}_{t}(x,a)\right)$ $\displaystyle=\eta\sum_{\tau=1}^{t}g_{\tau,i}(x,a)\mathbb{I}_{t}(x,a)$ $\displaystyle=\eta\widehat{V}_{t,i}.$ $$

This concludes the proof.
∎

###### Lemma 4 .

If Condition 2 holds, referring as $i^{*}$ to the element in $[m]$ such that $i^{*}=\operatorname*{arg\,max}_{i\in[m]}\sum_{t=1}^{T}\left[G_{t}^{\top}q^{P,
\pi_{t}}\right]_{i}$ , then with probability at least $1-\delta$, it holds:

$$ $V_{T}\leq\widehat{V}_{T,i^{*}}+\mathcal{E}^{\mathbb{I}}.$ $$

###### Proof.

We observe with probability at least $1-\delta$:

$$ $\displaystyle V_{T}$ $\displaystyle=\sum_{t=1}^{T}\left[G_{t}^{\top}q^{P,\pi_{t}}\right]_{i^{*}}$ $\displaystyle=\sum_{t=1}^{T}\sum_{x,a}g_{t,i^{*}}(x,a)\left(q_{t}(x,a)-\mathbb {I}_{t}(x,a)\right)+\sum_{t=1}^{T}\sum_{x,a}g_{t,i^{*}}(x,a)\mathbb{I}_{t}(x,a)$ $\displaystyle\leq\sum_{t=1}^{T}\sum_{x,a}g_{t,i^{*}}(x,a)\left(q_{t}(x,a)- \mathbb{I}_{t}(x,a)\right)+\widehat{V}_{T,i^{*}}$ $\displaystyle\leq\mathcal{E}^{\mathbb{I}}+V_{T,i^{*}}.$ $$

This concludes the proof.
∎

###### Lemma 5 .

When Condition 2 does not hold, with probability at least $1-10\delta$ in case of stochastic costs and $1-9\delta$ in case of adversarial costs it holds for all $i\in[m]$:

$$ $\widehat{V}_{T,i}\leq\frac{4T^{\frac{1}{4}}}{\eta}.$ $$

###### Proof.

Recall the definition of $\widehat{V}_{t,i}$ as $\widehat{V}_{t,i}=\sum_{\tau=1}^{t}\sum_{x,a}g_{t,i}(x,a)\mathbb{I}_{t}(x,a)$.
We first focus on the stochastic setting. Thus, with probability at least $1-\delta$, it holds:

$$ $\displaystyle\sum_{t=1}^{T}r_{t}^{\top}q_{t}-\sum_{t=1}^{T}\lambda_{t}^{\top}G _{t}^{\top}q_{t}$ $\displaystyle=\sum_{t=1}^{T}r_{t}^{\top}q^{\circ}-\sum_{t=1}^{T}\lambda_{t}^{ \top}G_{t}^{\top}q^{\circ}+\sum_{t=1}^{T}\ell_{t}^{\mathcal{L},\top}(q^{\circ} -q_{t})$ $\displaystyle\geq-\sum_{t=1}^{T}\lambda_{t}^{\top}\overline{G}^{\top}q^{\circ} -\lambda_{1,T}\mathcal{E}^{G}_{T}+\sum_{t=1}^{T}\ell_{t}^{\mathcal{L},\top}(q^ {\circ}-q_{t})$ $\displaystyle\geq-mT^{\frac{1}{4}}\mathcal{E}^{G}_{T}+\sum_{t=1}^{T}\ell_{t}^{ \mathcal{L},\top}(q^{\circ}-q_{t}).$ $$

On the other hand, in case of adversarial constraints, it holds:

$$ $\displaystyle\sum_{t=1}^{T}r_{t}^{\top}q_{t}-\sum_{t=1}^{T}\lambda_{t}^{\top}G _{t}^{\top}q_{t}$ $\displaystyle=\sum_{t=1}^{T}r_{t}^{\top}q^{\circ}-\sum_{t=1}^{T}\lambda_{t}^{ \top}G_{t}^{\top}q^{\circ}+\sum_{t=1}^{T}\ell_{t}^{\mathcal{L}}{}^{\top}(q^{ \circ}-q_{t})$ $\displaystyle\geq\sum_{t=1}^{T}\ell_{t}^{\mathcal{L},\top}(q^{\circ}-q_{t}).$ $$

Define a vector $\widetilde{\lambda}\in[0,T^{\frac{1}{4}}]^{m}$ as $\widetilde{\lambda}_{j}=0$ if $j\neq i$ and $\widetilde{\lambda}_{j}=T^{\frac{1}{4}}$ if $j=i$. Simultaneously with probability at least $1-\delta$ it holds:

$$ $\displaystyle\sum_{t=1}^{T}$ $\displaystyle r_{t}^{\top}q_{t}-\sum_{t=1}^{T}\lambda_{t}^{\top}G_{t}^{\top}q_ {t}$ $\displaystyle\leq\sum_{t=1}^{T}r_{t}^{\top}q_{t}-\sum_{t=1}^{T}\widetilde{ \lambda}^{\top}\sum_{x,a}G_{t}(x,a)\mathbb{I}_{t}(x,a)+\sum_{t=1}^{T}( \widetilde{\lambda}-\lambda_{t})^{\top}\sum_{x,a}G_{t}(x,a)\mathbb{I}_{t}(x,a) +\lambda_{1,T}\mathcal{E}^{\mathbb{I}}$ $\displaystyle\leq\sum_{t=1}^{T}r_{t}^{\top}q_{t}-\sum_{t=1}^{T}\widetilde{ \lambda}^{\top}\sum_{x,a}G_{t}(x,a)\mathbb{I}_{t}(x,a)+\mathcal{E}^{D}_{T}( \widetilde{\lambda})+mT^{\frac{1}{4}}\mathcal{E}^{\mathbb{I}}$ $\displaystyle\leq HT-T^{\frac{1}{4}}\widehat{V}_{T,i}+\mathcal{E}^{D}_{T}( \widetilde{\lambda})+mT^{\frac{1}{4}}\mathcal{E}^{\mathbb{I}},$ $$

where in the first equality we used the definition of $\mathcal{E}_{T}^{\mathbb{I}}$, in the first inequality we used the definition of the dual space $[0,T^{\frac{1}{4}}]^{m}$ to bound $\lambda_{1,T}$ as $mT^{\frac{1}{4}}$, and in the last inequality we used the definition of $\widetilde{\lambda}$.
We can then compare the lower and the upper bound for $\sum_{t=1}^{T}r_{t}^{\top}q_{t}-\sum_{t=1}^{T}\lambda_{t}^{\top}G_{t}^{\top}q_
{t}$ obtaining the following inequality, which holds with probability at least $1-\delta$ with adversarial constraints and with probability at least $1-2\delta$ with stochastic constraints:

$$ $-mT^{\frac{1}{4}}\mathcal{E}^{G}_{T}+\sum_{t=1}^{T}\ell_{t}^{\mathcal{L},\top} (q^{\circ}-q_{t})\leq HT-T^{\frac{1}{4}}\widehat{V}_{T,i}+\mathcal{E}^{D}_{T}( \widetilde{\lambda})+mT^{\frac{1}{4}}\mathcal{E}^{\mathbb{I}},$ $$

from which we can write the following inequality that holds with probability at least $1-9\delta$ with adversarial constraints and $1-10\delta$ with stochastic constraints:

$$ $T^{\frac{1}{4}}\widehat{V}_{T,i}\leq mT^{\frac{1}{4}}(\mathcal{E}_{T}^{G}+ \mathcal{E}_{T}^{\mathbb{I}})+\mathcal{E}_{T}^{P}+\mathcal{E}_{T}^{D}( \widetilde{\lambda})+HT.$ (18) $$

We proceed now to bound each element of the right side of the inequality.
To bound $\mathcal{E}^{P}$ we use the fact that $\Xi_{1,T}\leq(1+\lambda_{1,T})\leq(1+mT^{\frac{1}{4}})$ and the definition of $\eta$ as following:

$$ $\displaystyle\mathcal{E}^{P}_{T}$ $\displaystyle=\Xi_{1,T}\left(U_{1}C\sqrt{T}+U_{2}\frac{\sqrt{T}}{C}+U_{3}\frac {1}{C\sqrt{T}}\right)+U_{4}\sqrt{T}$ $\displaystyle\leq 2(1+mT^{\frac{1}{4}})\sqrt{T}\left(1512H^{3}|X||A|\ln\left( \frac{H|A|T^{2}}{\delta}\right)+\frac{9H|X||A|}{252H|X||A|}+\frac{\frac{H}{2} \ln\left(\frac{HT^{2}}{\delta}\right)}{252H|X||A|}\right)$ $\displaystyle\quad+\sqrt{T}30H^{2}|X|^{2}\sqrt{2|A|\ln\left(\frac{T|X|^{2}|A|} {\delta}\right)}$ $\displaystyle\leq T^{\frac{1}{4}}\sqrt{T}6056H^{3}m|X||A|\ln\left(\frac{H|A|T^ {2}}{\delta}\right)+\sqrt{T}30H^{2}|X|^{2}\sqrt{2|A|\ln\left(\frac{T|X|^{2}|A| }{\delta}\right)}$ $\displaystyle\leq T^{\frac{1}{4}}\sqrt{T}6116H^{2}m|X|^{2}|A|\ln\left(\frac{|X |^{2}|A|T^{2}}{\delta}\right)$ $\displaystyle\leq\frac{T^{\frac{1}{4}}}{\eta}$ $$

To bound $\mathcal{E}_{T}^{D}(\widetilde{\lambda})$ we use Theorem 11, the fact that by its definition $\lVert\widetilde{\lambda}\rVert_{2}^{2}=\left(T^{\frac{1}{4}}\right)^{2}=\sqrt
{T}$, the initialization of the dual $\lambda_{1}=\underline{0}$ and the definition of $\eta$ in the following way:

$$ $\displaystyle\mathcal{E}_{T}^{D}(\widetilde{\lambda})$ $\displaystyle\leq\frac{\lVert\lambda_{1}-\widetilde{\lambda}\rVert_{2}^{2}}{2 \eta}+\frac{\eta}{2}TmH^{2}$ $\displaystyle=\frac{\lVert\widetilde{\lambda}\rVert_{2}^{2}}{2\eta}+\frac{\eta }{2}TmH^{2}$ $\displaystyle=\frac{\sqrt{T}}{2\eta}+\frac{\eta}{2}TmH^{2}$ $\displaystyle\leq\frac{\sqrt{T}}{2\eta}+\frac{mH^{2}T}{2}\frac{1}{84672mH^{2}| X|^{2}|A|\ln\left(\frac{|A||X|^{2}T^{2}}{\delta}\right)\sqrt{T}}$ $\displaystyle\leq\frac{\sqrt{T}}{2\eta}+\frac{\sqrt{T}}{2\eta}=\frac{\sqrt{T}} {\eta}$ $$

We proceed to simply bound also $mT^{\frac{1}{4}}\left(\mathcal{E}_{T}^{G}+\mathcal{E}_{T}^{\mathbb{I}}\right)$ through their definition:

$$ $\displaystyle mT^{\frac{1}{4}}\left(\mathcal{E}_{T}^{G}+\mathcal{E}_{T}^{ \mathbb{I}}\right)$ $\displaystyle=mT^{\frac{1}{4}}\sqrt{T}\left(2H\sqrt{\ln\left(\frac{T^{2}}{ \delta}\right)}+H\sqrt{2\ln\left(\frac{T^{2}}{\delta}\right)}\right)$ $\displaystyle\leq\frac{T^{\frac{1}{4}}}{\eta}$ $$

Finally we bound $HT$ as $HT\leq\frac{\sqrt{T}}{\eta}$.

Thus, Inequality (18) becomes

$$ $\widehat{V}_{T,i}\leq\frac{1}{T^{\frac{1}{4}}}\left(mT^{\frac{1}{4}}(\mathcal{ E}_{T}^{G}+\mathcal{E}_{T}^{\mathbb{I}})+\mathcal{E}_{T}^{P}+\mathcal{E}_{T}^{ D}(\widetilde{\lambda})+HT\right)\leq\frac{4\sqrt{T}}{T^{\frac{1}{4}}\eta}= \frac{4T^{\frac{1}{4}}}{\eta},$ $$

which concludes the proof.
∎

###### Lemma 3 .

###### Proof.

###### Lemma 4 .

###### Proof.

###### Lemma 5 .

###### Proof.

## Appendix G Analysis with Stochastic Constraints

See 5

###### Proof.

With probability at least $1-12\delta$ it holds:

$$ $\displaystyle V_{T}$ $\displaystyle\leq\widehat{V}_{T,i^{*}}+\mathcal{E}^{\mathbb{I}}$ (19a) $\displaystyle\leq\frac{1}{\eta}\lambda_{T+1,i^{*}}+\mathcal{E}^{\mathbb{I}}$ (19b) $\displaystyle\leq\frac{1}{\eta}\Lambda+\mathcal{E}^{\mathbb{I}},$ (19c) $$

where Inequality (19a) holds by Lemma 4, Inequality (19b) holds by Lemma 3 and Inequality (19c) holds by Theorem 4.
Then, with probability at least $1-12\delta$ we observe that:

$$ $\displaystyle\sum_{t=1}^{T}r_{t}^{\top}q^{*}-\sum_{t=1}^{T}r_{t}^{\top}q^{P, \pi_{t}}$ $\displaystyle\leq\sum_{t=1}^{T}\left(r_{t}^{\top}q^{*}-\lambda_{t}^{\top}G_{t} ^{\top}q^{*}\right)-\sum_{t=1}^{T}\left(r_{t}^{\top}q_{t}-\lambda_{t}^{\top}G_ {t}^{\top}q_{t}\right)+\sum_{t=1}^{T}\lambda_{t}^{\top}G_{t}^{\top}(q^{*}-q_{t})$ $\displaystyle\leq\mathcal{E}^{P}+\mathcal{E}^{D}(\underline{0})+\lambda_{1,T} \mathcal{E}^{\mathbb{I}}+\sum_{t=1}^{T}\lambda_{t}^{\top}G_{t}^{\top}q^{*}$ (20a) $\displaystyle=\mathcal{E}^{P}+\mathcal{E}^{D}(\underline{0})+\lambda_{1,T} \mathcal{E}^{\mathbb{I}}+\sum_{t=1}^{T}\lambda_{t}^{\top}(G_{t}-\overline{G})^ {\top}q^{*}+\sum_{t=1}^{T}\lambda_{t}^{\top}\overline{G}^{\top}q^{*}$ $\displaystyle\leq\mathcal{E}^{P}+\mathcal{E}^{D}(\underline{0})+\lambda_{1,T} \mathcal{E}^{\mathbb{I}}+\lambda_{1,T}\mathcal{E}^{G}$ (20b) $\displaystyle\leq\mathcal{E}^{P}+\mathcal{E}^{D}(\underline{0})+\Lambda \mathcal{E}^{\mathbb{I}}+\Lambda\mathcal{E}^{G},$ (20c) $$

where Inequality (G) holds by Theorem 3 and by Theorem 11, Inequality (20b) holds since in the stochastic constraint case $\sum_{t=1}^{T}(G_{t}-\overline{G})^{\top}q^{*}\leq\mathcal{E}^{G}$ with probability at least $1-\delta$ by definition of $\mathcal{E}^{G}$, and finally Inequality (20c) holds by Theorem 4.
Finally we observe that in the stochastic case
with probability at least $1-\delta$:

$$ $\left(T\cdot\text{OPT}_{\overline{r},\overline{G}}-\sum_{t=1}^{T}r_{t}^{\top}q _{t}\right)-\sum_{t=1}^{T}r_{t}^{\top}(q^{*}-q_{t})\leq\mathcal{E}^{r}.$ $$

Thus, if the rewards are stochastic with probability at least $1-14\delta$ it holds:

$$ $R_{T}\leq\mathcal{E}^{P}+\mathcal{E}^{D}(\underline{0})+\Lambda\mathcal{E}^{ \mathbb{I}}+\Lambda\mathcal{E}^{G}+\mathcal{E}^{r},\quad V_{T}\leq\frac{1}{ \eta}\Lambda+\mathcal{E}^{\mathbb{I}}$ $$

and if the rewards are adversarial with probability at least $1-13\delta$ it holds:

$$ $R_{T}\leq\mathcal{E}^{P}+\mathcal{E}^{D}(\underline{0})+\Lambda\mathcal{E}^{ \mathbb{I}}+\Lambda\mathcal{E}^{G},\quad V_{T}\leq\frac{1}{\eta}\Lambda+ \mathcal{E}^{\mathbb{I}}$ $$

which concludes the proof.
∎

See 6

###### Proof.

Similar to the proof of Lemma 5 it holds with probability at least $1-10\delta$:

$$ $\displaystyle\sum_{t=1}^{T}r_{t}^{\top}q^{*}-\sum_{t=1}^{T}r_{t}^{\top}q^{P, \pi_{t}}$ $\displaystyle\leq\sum_{t=1}^{T}\left(r_{t}^{\top}q^{*}-\lambda_{t}^{\top}G_{t} ^{\top}q^{*}\right)-\sum_{t=1}^{T}\left(r_{t}^{\top}q_{t}-\lambda_{t}^{\top}G_ {t}^{\top}q_{t}\right)+\sum_{t=1}^{T}\lambda_{t}^{\top}G_{t}^{\top}(q^{*}-q_{t})$ $\displaystyle\leq\mathcal{E}^{P}+\mathcal{E}^{D}(\underline{0})+\lambda_{1,T} \mathcal{E}^{\mathbb{I}}+\sum_{t=1}^{T}\lambda_{t}^{\top}G_{t}^{\top}q^{*}$ $\displaystyle=\mathcal{E}^{P}+\mathcal{E}^{D}(\underline{0})+\lambda_{1,T} \mathcal{E}^{\mathbb{I}}+\sum_{t=1}^{T}\lambda_{t}^{\top}(G_{t}-\overline{G})^ {\top}q^{*}+\sum_{t=1}^{T}\lambda_{t}^{\top}\overline{G}^{\top}q^{*}$ $\displaystyle\leq\mathcal{E}^{P}+\mathcal{E}^{D}(\underline{0})+\lambda_{1,T} \mathcal{E}^{\mathbb{I}}+\lambda_{1,T}\mathcal{E}^{G},$ $$

therefore with probability at least $1-10\delta$ following the reasoning of Lemma 5 it holds with adversarial rewards:

$$ $\sum_{t=1}^{T}r_{t}^{\top}q_{t}\geq T\cdot\text{OPT}_{\overline{r},\overline{G }}-mT^{\nicefrac{{1}}{{4}}}\mathcal{E}^{G}+mT^{\nicefrac{{1}}{{4}}}\mathcal{E} ^{\mathbb{I}}-\mathcal{E}^{D}(\underline{0})-\mathcal{E}^{P},$ $$

and with stochastic rewards with probability ta least $1-11\delta$:

$$ $\sum_{t=1}^{T}r_{t}^{\top}q_{t}\geq T\cdot\text{OPT}_{\overline{r},\overline{G }}-mT^{\nicefrac{{1}}{{4}}}\mathcal{E}^{G}+mT^{\nicefrac{{1}}{{4}}}\mathcal{E} ^{\mathbb{I}}-\mathcal{E}^{D}(\underline{0})-\mathcal{E}^{P}-\mathcal{E}^{r}.$ $$

Applying Lemma 5 to bound the constraints violation concludes the proof.
∎

###### Proof.

###### Proof.

## Appendix H Analysis with Adversarial Constraints

See 7

###### Proof.

Thanks to Theorem 3 , Theorem 11 and Theorem 4 with probability at least $1-11\delta$ it holds for all $q\in\Delta(P)$:

$$ $\displaystyle\sum_{t=1}^{T}r_{t}^{\top}q-\sum_{t=1}^{T}r_{t}^{\top}q_{t}$ $\displaystyle\leq-\sum_{t=1}^{T}\ell_{t}^{\mathcal{L},\top}q+\sum_{t=1}^{T} \ell_{t}^{\mathcal{L},\top}q_{t}+\sum_{t=1}^{T}\lambda_{t}^{\top}G_{t}^{\top}q -\sum_{t=1}^{T}\lambda_{t}^{\top}G_{t}^{\top}q_{t}$ $\displaystyle\leq\mathcal{E}^{P}_{T}+\sum_{t=1}^{T}\lambda_{t}^{\top}G_{t}^{ \top}q+\sum_{t=1}^{T}(\underline{0}-\lambda_{t})^{\top}\sum_{h=0}^{H-1}G_{t}(x _{h},a_{h})+\sum_{t=1}^{T}\lambda_{t}^{\top}\left(\sum_{h=0}^{H-1}G_{t}(x_{h}, a_{h})-G_{t}^{\top}q_{t}\right)$ $\displaystyle\leq\mathcal{E}^{P}_{T}+\mathcal{E}^{D}_{T}(\underline{0})+ \lambda_{1,T}\mathcal{E}^{\mathbb{I}}+\sum_{t=1}^{T}\sum_{i=1}^{m}\lambda_{t,i }g_{t,i}^{\top}q$ $\displaystyle\leq\mathcal{E}^{P}_{T}+\mathcal{E}^{D}_{T}(\underline{0})+ \lambda_{1,T}\mathcal{E}^{\mathbb{I}}+\sum_{t=1}^{T}\sum_{i=1}^{m}\lambda_{t,i }g_{t,i}^{\top}q$ $\displaystyle\leq\mathcal{E}^{P}_{T}+\mathcal{E}^{D}_{T}(\underline{0})+ \Lambda\mathcal{E}^{\mathbb{I}}+\sum_{t=1}^{T}\sum_{i=1}^{m}\lambda_{t,i}g_{t, i}^{\top}q.$ $$

Consider now the occupancy measure $\widetilde{q}=\frac{\rho}{H+\rho}q^{*}+\frac{H}{H+\rho}q^{\circ}$. For all $i\in[m]$ and for all $t\in[T]$:

$$ $\displaystyle g_{t,i}^{\top}\widetilde{q}$ $\displaystyle\leq\left(\frac{\rho}{H+\rho}g_{t,i}^{\top}q^{*}+\frac{H}{H+\rho} g_{t,i}^{\top}q^{\circ}\right)$ $\displaystyle\leq\left(\frac{H\rho}{H+\rho}-\frac{H\rho}{H+\rho}\right)$ $\displaystyle=0,$ $$

given that $g_{t,i}^{\top}q^{*}\leq\lVert q^{*}\rVert_{1}\leq H$, and $g_{t,i}^{\top}q^{\circ}\leq-\rho$ by definition of $q^{\circ}$ and by definition of $\rho$.

$$ $\displaystyle\sum_{t=1}^{T}r_{t}^{\top}\widetilde{q}$ $\displaystyle=\sum_{t=1}^{T}\left(\frac{\rho}{H+\rho}r_{t}^{\top}q^{*}+\frac{H }{H+\rho}r_{t}^{\top}q^{\circ}\right)$ $\displaystyle\geq\frac{\rho}{H+\rho}\sum_{t=1}^{T}r_{t}^{\top}q^{*},$ $$

since $r_{t}^{\top}q^{\circ}\geq 0$. Notice also that with adversarial rewards $\sum_{t=1}^{T}r_{t}^{\top}q^{*}=T\cdot\text{OPT}_{\overline{r},\overline{G}}$, while with stochastic rewards with probability at least $1-\delta$ it holds $\sum_{t=1}^{T}r_{t}^{\top}q^{*}\geq T\cdot\text{OPT}_{\overline{r},\overline{G
}}-\mathcal{E}^{r}$, by definition of $\mathcal{E}^{r}$ and $\text{OPT}_{\overline{r},\overline{G}}$ for stochastic rewards.
By reordering the terms we get that with probability at least $1-11\delta$

$$ $\sum_{t=1}^{T}r_{t}^{\top}q_{t}\geq\frac{\rho}{H+\rho}\sum_{t=1}^{T}r_{t}^{ \top}q^{*}-\mathcal{E}^{P}_{T}-\mathcal{E}^{D}_{T}(\underline{0})-\Lambda \mathcal{E}^{\mathbb{I}},$ $$

we can proceed to bound the regret in both cases: adversarial rewards and stochastic rewards.

With probability at least $1-11\delta$ with adversarial rewards it holds:

$$ $\displaystyle R_{T}$ $\displaystyle=\sum_{t=1}^{T}r_{t}^{\top}q^{*}-\sum_{t=1}^{T}r_{t}^{\top}q_{t}$ $\displaystyle\leq\sum_{t=1}^{T}r_{t}^{\top}q^{*}-\left(\frac{\rho}{H+\rho}\sum _{t=1}^{T}r_{t}^{\top}q^{*}-\mathcal{E}^{P}_{T}-\mathcal{E}^{D}_{T}(\underline {0})-\Lambda\mathcal{E}^{\mathbb{I}}\right)$ $\displaystyle\leq\frac{H}{H+\rho}\sum_{t=1}^{T}r_{t}^{\top}q^{*}+\mathcal{E}^{ P}_{T}+\mathcal{E}^{D}_{T}(\underline{0})+\Lambda\mathcal{E}^{\mathbb{I}}$ $\displaystyle\leq\frac{H}{H+\rho}T\cdot\text{OPT}_{\overline{r},\overline{G}}+ \mathcal{E}^{P}_{T}+\mathcal{E}^{D}_{T}(\underline{0})+\Lambda\mathcal{E}^{ \mathbb{I}}.$ $$

With stochastic rewards it holds with probability at least $1-11\delta$:

$$ $\sum_{t=1}^{T}r_{t}^{\top}q_{t}\geq\frac{\rho}{H+\rho}\sum_{t=1}^{T}r_{t}^{ \top}q^{*}-\mathcal{E}^{P}_{T}-\mathcal{E}^{D}_{T}(\underline{0})-\Lambda \mathcal{E}^{\mathbb{I}},$ $$

and with probability at least $1-12\delta$:

$$ $\sum_{t=1}^{T}r_{t}^{\top}q_{t}\geq\frac{\rho}{H+\rho}T\cdot\text{OPT}_{ \overline{r},\overline{G}}-\mathcal{E}^{P}_{T}-\mathcal{E}^{D}_{T}(\underline{ 0})-\Lambda\mathcal{E}^{\mathbb{I}}-\mathcal{E}^{r}.$ $$

To conclude the proof we observe that following the analogous reasoning to Theorem 5 in case of adversarial constraints it also holds with probability at least $1-12\delta$:

$$ $V_{T}\leq\frac{1}{\eta}\Lambda+\mathcal{E}^{\mathbb{I}}.$ $$

∎

###### Proof.

## Appendix I Analysis with respect to The Weaker Baseline

In this section we will study the guarantees of Algorithm 2 when the regret is computed with respect to a policy $q^{*}$ that respect the constraints at each episode, *i.e.* $g_{t}^{\top}q^{*}\leq 0$ for all $i\in[m]$, for all $t\in[T]$.

See 8

###### Proof.

The violation can be bounded as in Theorem 5.
Also similarly to Theorem 5 it holds with probability $1-12\delta$

$$ $\displaystyle\sum_{t=1}^{T}r_{t}^{\top}q^{*}-\sum_{t=1}^{T}r_{t}^{\top}q_{t}$ $\displaystyle\leq-\sum_{t=1}^{T}\ell_{t}^{\mathcal{L},\top}q^{*}+\sum_{t=1}^{T }\ell_{t}^{\mathcal{L},\top}q_{t}+\sum_{t=1}^{T}\lambda_{t}^{\top}G_{t}^{\top} q^{*}-\sum_{t=1}^{T}\lambda_{t}^{\top}G_{t}^{\top}q_{t}$ $\displaystyle\leq\mathcal{E}^{P}_{T}+\sum_{t=1}^{T}(\underline{0}-\lambda_{t}) ^{\top}\sum_{h=0}^{H-1}G_{t}(x_{h},a_{h})+\sum_{t=1}^{T}\lambda_{t}^{\top} \left(\sum_{h=0}^{H-1}G_{t}(x_{h},a_{h})-G_{t}^{\top}q_{t}\right)$ $\displaystyle\leq\mathcal{E}^{P}_{T}+\mathcal{E}^{D}_{T}(\underline{0})+ \lambda_{1,T}\mathcal{E}^{\mathbb{I}}$ $\displaystyle\leq\mathcal{E}^{P}_{T}+\mathcal{E}^{D}_{T}(\underline{0})+ \Lambda\mathcal{E}^{\mathbb{I}}.$ $$

Finally with stochastic rewards with probability at least $1-\delta$:

$$ $T\cdot\text{OPT}_{\overline{r},\overline{G}}-\sum_{t=1}^{T}r_{t}^{\top}q^{*} \leq\mathcal{E}^{r}.$ $$

Therefore, with adversarial rewards it holds with probability at least $1-12\delta$:

$$ $R_{T}\leq\mathcal{E}^{P}+\mathcal{E}^{D}(\underline{0})+\Lambda\mathcal{E}^{ \mathbb{I}},\quad V_{T}\leq\frac{1}{\eta}\Lambda+\mathcal{E}^{\mathbb{I}},$ $$

and with stochastic rewards it holds with probability at least $1-13\delta$:

$$ $R_{T}\leq\mathcal{E}^{P}+\mathcal{E}^{D}(\underline{0})+\Lambda\mathcal{E}^{ \mathbb{I}}+\mathcal{E}^{r},\quad V_{T}\leq\frac{1}{\eta}\Lambda+\mathcal{E}^{ \mathbb{I}},$ $$

which concludes the proof.
∎

See 9

###### Proof.

The violation can be bounded thanks to Lemma 3, as in Theorem 6.
To bound the regret, notice that it holds with probability $1-9\delta$:

$$ $\displaystyle\sum_{t=1}^{T}r_{t}^{\top}q^{*}-\sum_{t=1}^{T}r_{t}^{\top}q_{t}$ $\displaystyle\leq-\sum_{t=1}^{T}\ell_{t}^{\mathcal{L},\top}q^{*}+\sum_{t=1}^{T }\ell_{t}^{\mathcal{L},\top}q_{t}+\sum_{t=1}^{T}\lambda_{t}^{\top}G_{t}^{\top} q^{*}-\sum_{t=1}^{T}\lambda_{t}^{\top}G_{t}^{\top}q_{t}$ $\displaystyle\leq\mathcal{E}^{P}_{T}+\sum_{t=1}^{T}(\underline{0}-\lambda_{t}) ^{\top}\sum_{h=0}^{H-1}G_{t}(x_{h},a_{h})+\sum_{t=1}^{T}\lambda_{t}^{\top} \left(\sum_{h=0}^{H-1}G_{t}(x_{h},a_{h})-G_{t}^{\top}q_{t}\right)$ $\displaystyle\leq\mathcal{E}^{P}_{T}+\mathcal{E}^{D}_{T}(\underline{0})+ \lambda_{1,T}\mathcal{E}^{\mathbb{I}}$ $\displaystyle\leq\mathcal{E}^{P}_{T}+\mathcal{E}^{D}_{T}(\underline{0})+mT^{ \nicefrac{{1}}{{4}}}\mathcal{E}^{\mathbb{I}}.$ $$

Finally with stochastic rewards with probability at least $1-\delta$:

$$ $T\cdot\text{OPT}_{\overline{r},\overline{G}}-\sum_{t=1}^{T}r_{t}^{\top}q^{*} \leq\mathcal{E}^{r}.$ $$

Therefore, with adversarial rewards it holds with probability at least $1-11\delta$:

$$ $R_{T}\leq\mathcal{E}^{P}+\mathcal{E}^{D}(\underline{0})+mT^{\nicefrac{{1}}{{4} }}\mathcal{E}^{\mathbb{I}},\quad V_{T}\leq\frac{4T^{\nicefrac{{1}}{{4}}}}{\eta},$ $$

and with stochastic rewards it holds with probability at least $1-12\delta$:

$$ $R_{T}\leq\mathcal{E}^{P}+\mathcal{E}^{D}(\underline{0})+mT^{\nicefrac{{1}}{{4} }}\mathcal{E}^{\mathbb{I}}+\mathcal{E}^{r},\quad V_{T}\leq\frac{4T^{\nicefrac{ {1}}{{4}}}}{\eta},$ $$

which concludes the proof.
∎

###### Proof.

###### Proof.

## Appendix J Auxiliary Lemmas

###### Lemma 6 (Adapted from (Luo et al., 2021 ) Lemma C.4) .

$$ $\eta_{t}\widehat{Q}_{t}(x,a)\leq\frac{1}{2}\quad\land\quad\eta_{t}B_{t}(x,a) \leq\frac{1}{2H}.$ $$

###### Proof.

Recall $\gamma=2\eta_{t}H\Xi_{t}$. Thus, it holds:

$$ $\eta_{t}\widehat{Q}_{t}(x,a)\leq\frac{\eta_{t}H\Xi_{t}}{\gamma}=\frac{\eta_{t} H\Xi_{t}}{2\eta_{t}H\Xi_{t}}=\frac{1}{2}$ $$

and

$$ $\eta_{t}b_{t}(x,a)=\frac{3\eta_{t}H\Xi_{t}\gamma+\eta_{t}\Xi_{t}H(\overline{q} _{t}(x,a)-\underline{q}_{t}(x,a))}{\overline{q}_{t}(x,a)+\gamma}\leq 3\eta_{t} \Xi_{t}H+\eta_{t}H\Xi_{t}=2\gamma.$ $$

Finally,

$$ $\displaystyle\eta_{t}B_{t}(x,a)$ $\displaystyle\leq H\left(1+\frac{1}{H}\right)^{H}\eta_{t}\sup_{x^{\prime},a^{ \prime}}b_{t}(x^{\prime},a^{\prime})$ $\displaystyle\leq 3H2\gamma$ $\displaystyle=6H\gamma$ $\displaystyle=\frac{6H}{C\sqrt{T}}$ $\displaystyle=\frac{6H}{252|X||A|H\sqrt{T}}$ $\displaystyle\leq\frac{1}{42H}$ $\displaystyle\leq\frac{1}{2H}.$ $$

This concludes the poof.
∎

###### Lemma 7 (Adapted from (Luo et al., 2021 ) , Lemma B.1) .

If the following inequality holds:

$$ $\displaystyle\sum_{x}q^{*}(x)$ $\displaystyle\sum_{t=t_{1}}^{t_{2}}\sum_{a}\left(\pi_{t}(a|x)-\pi^{*}(a|x) \right)\left(Q_{t}^{\pi_{t}}(x,a)-B_{t}(x,a)\right)$ $\displaystyle\leq o(T)+\sum_{t=t_{1}}^{t_{2}}V^{\pi^{*}}(x_{0};b_{t})+\frac{1} {H}\sum_{t=t_{1}}^{t_{2}}\sum_{x,a}q^{*}(x)\pi_{t}(a|x)B_{t}(x,a),$ (21) $$

with $B_{t}$ defined as

$$ $B_{t}(x,a)=b_{t}(x,a)+\left(1+\frac{1}{H}\right)\mathbb{E}_{x^{\prime}\sim P( \cdot|x,a)}\mathbb{E}_{a^{\prime}\sim\pi_{t}(\cdot|x^{\prime})}\left[B_{t}(x^{ \prime},a^{\prime})\right]\quad\forall t\in[T],\forall x\in X,\forall a\in A,$ (22) $$

then it holds that:

$$ $R_{t_{1},t_{2}}\leq o(T)+3\sum_{t=t_{1}}^{t_{2}}\widehat{V}^{\pi_{t}}(x_{0};b_ {t}).$ $$

###### Proof.

The proof is analogous to the one proposed by (Luo et al., ), Lemma B.1, since the proof is episode based and then the sum over $t$ is taken.
∎

###### Lemma 8 (Adapted from (Luo et al., 2021 ) , Lemma A.1) .

Let $\mathcal{F}_{0},\ldots,\mathcal{F}_{T}$ be a filtration and $X_{1},\ldots,X_{T}$ be real random variables such that $X_{t}$ is $\mathcal{F}_{t}$-measurable, $\mathbb{E}[X_{t}|\mathcal{F}_{t}]=0$, $|X_{t}|\leq b$ for all $t\in[T]$ and $\sum_{t=t_{1}}^{t_{2}}\mathbb{E}[X_{t}^{2}|\mathcal{F}_{t}]\leq V_{t_{1},t_{2}}$ for some fixed $V_{t_{1},t_{2}}>0$ and $b>0$ for every $t_{1},t_{2}\in[T]$ such that $1\leq t_{1}\leq t_{2}\leq T$. Then with probability at least $1-\delta$ it holds simultaneously for all $[t_{1},\ldots,t_{2}]\subset[T]$:

$$ $\sum_{t=t_{1}}^{t_{2}}X_{t}\leq\frac{V_{t_{1},t_{2}}}{b}+b\log\left(\frac{T^{2 }}{\delta}\right).$ $$

###### Proof.

For all $\delta^{\prime}\in(0,1)$ by Lemma A.1 (Luo et al., ) it holds:

$$ $\mathbb{P}\left(\sum_{t=t_{1}}^{t_{2}}X_{t}\geq\frac{V_{t_{1},t_{2}}}{b}+b\log \left(\frac{1}{\delta^{\prime}}\right)\right)\leq\delta^{\prime}.$ $$

It is sufficient to consider the intersection of all events for all possible intervals $[t_{1},\ldots,t_{2}]$, that are less than $T^{2}$.

$$ $\mathbb{P}\left(\bigcap_{t_{1},t_{2}}\bigg{\{}\sum_{t=t_{1}}^{t_{2}}X_{t}\geq \frac{V_{t_{1},t_{2}}}{b}+b\log\left(\frac{1}{\delta^{\prime}}\right)\bigg{\}} \right)\leq T^{2}\delta^{\prime}.$ $$

To conclude the proof we take $\delta$ as $T^{2}\delta^{\prime}$.
∎

Consider a loss function $f_{t}(x,a)\in[0,Z]$, for all $t\in[T],(x,a)\in X\times A$, with $Z>0$. Define another function $\widetilde{f}_{t}\in[0,Z]^{|X\times A|}$. If we define the estimator $\widehat{f}_{t}(x,a)=\frac{\widetilde{f}_{t}(x,a)\mathbb{I}_{t}(x,a)}{
\overline{q}_{t}(x,a)+\gamma}$ where $\mathbb{E}[\widetilde{f}_{t}(x,a)]=f_{t}(x,a)$, we can state the following result.

###### Lemma 9 (Adapted from (Jin et al., 2020 ) ) .

For every sequence of functions $\alpha_{1},\ldots\alpha_{T}$ such that $\alpha_{t}\in[0,\frac{2\gamma}{Z}]^{|X\times A|}$ is $\mathcal{F}_{t}$ measurable for all $t\in[T]$, we have with probability at least $1-\delta$ that simultaneously for all $t_{1},t_{2}\in[T]$ such that $1\leq t_{1}\leq t_{2}\leq T$ it holds:

$$ $\sum_{t=t_{1}}^{t_{2}}\sum_{x,a}\alpha_{t}(x,a)\left(\widehat{f}_{t}(x,a)- \frac{q_{t}(x,a)}{\overline{q}_{t}(x,a)}f_{t}(x,a)\right)\leq H\ln\left(\frac{ HT^{2}}{\delta}\right).$ $$

###### Proof.

$$ $\displaystyle\widehat{\ell}_{t}(x,a)$ $\displaystyle=\frac{\widetilde{f}_{t}(x,a)\mathbb{I}_{t}(x,a)}{\overline{q}_{t }(x,a)+\gamma}$ $\displaystyle\leq\frac{\widetilde{f}_{t}(x,a)\mathbb{I}_{t}(x,a)}{\overline{q} _{t}(x,a)+\frac{\widetilde{f}_{t}(x,a)}{Z}\gamma}$ $\displaystyle=\frac{\mathbb{I}_{t}(x,a)Z}{2\gamma}\frac{2\gamma\frac{ \widetilde{f}_{t}(x,a)}{Z}}{\overline{q}_{t}(x,a)+\gamma\frac{\widetilde{f}_{t }(x,a)}{Z}}$ $\displaystyle=\frac{\mathbb{I}_{t}(x,a)Z}{2\gamma}\frac{2\gamma\frac{ \widetilde{f}_{t}(x,a)}{Z\overline{q}_{t}(x,a)}}{1+\gamma\frac{\widetilde{f}_{ t}(x,a)}{Z\overline{q}_{t}(x,a)}}$ $\displaystyle\leq\frac{Z}{2\gamma}\ln\left(1+2\gamma\frac{\mathbb{I}_{t}(x,a) \widetilde{f}_{t}(x,a)}{Z\overline{q}_{t}(x,a)}\right).$ $$

For each layer $h\in[H]$ we define $\widehat{S}_{t,h}:=\sum_{x\in X_{h},a\in A}\alpha_{t}(x,a)\widehat{f}_{t}(x,a)$ and $S_{t,h}:=\sum_{x\in X_{h},a\in A}\alpha_{t}(x,a)\frac{q_{t}(x,a)}{\overline{q}
_{t}(x,a)}f_{t}(x,a)$.

$$ $\displaystyle\mathbb{E}_{t}[\exp(\widehat{S}_{t,h})]$ $\displaystyle=\mathbb{E}\left[\exp\left(\sum_{x\in X_{h},a\in A}\alpha_{t}(x,a )\widehat{f}_{t}(x,a)\right)\right]$ $\displaystyle\leq\mathbb{E}\left[\exp\left(\sum_{x\in X_{h},a\in A}\alpha_{t}( x,a)\frac{Z}{2\gamma}\ln\left(1+2\gamma\frac{\mathbb{I}_{t}(x,a)\widetilde{f}_ {t}(x,a)}{Z\overline{q}_{t}(x,a)}\right)\right)\right]$ $\displaystyle\leq\mathbb{E}\left[\prod_{x\in X_{h},a\in A}\left(1+\alpha_{t}(x ,a)\frac{\mathbb{I}_{t}(x,a)\widetilde{f}_{t}(x,a)}{\overline{q}_{t}(x,a)} \right)\right]$ $\displaystyle\leq 1+\sum_{x\in X_{h},a\in A}\alpha_{t}(x,a)\frac{q_{t}(x,a)f_{ t}(x,a)}{\overline{q}_{t}(x,a)}=1+S_{t,h}$ $\displaystyle\leq\exp(S_{t,h})$ $$

For each interval $[t_{1},\ldots,t_{2}]\subset[T]$ it holds:

$$ $\mathbb{P}\left[\sum_{t=t_{1}}^{t_{2}}(\widehat{S}_{t,h}-S_{t,h})\geq\ln\left( \frac{H}{\delta^{\prime}}\right)\right]\leq\frac{\delta^{\prime}}{H}.$ $$

Taking the intersection event for all intervals $[t_{1},\ldots,t_{2}]\subset[T]$:

$$ $\mathbb{P}\left[\bigcap_{t_{1},t_{2}}\bigg{\{}\sum_{t=t_{1}}^{t_{2}}(\widehat{ S}_{t,h}-S_{t,h})\geq\ln\left(\frac{H}{\delta^{\prime}}\right)\bigg{\}}\right] \leq T^{2}\frac{\delta^{\prime}}{H}.$ $$

$$ $\delta=T^{2}\delta^{\prime},$ $$

and

$$ $\mathbb{P}\left[\bigcap_{t_{1},t_{2}}\bigg{\{}\sum_{t=t_{1}}^{t_{2}}(\widehat{ S}_{t,h}-S_{t,h})\geq\ln\left(\frac{HT^{2}}{\delta}\right)\bigg{\}}\right]\leq \frac{\delta}{H}.$ $$

Finally we take the sum over $h\in[H]$:

$$ $\mathbb{P}\left[\sum_{t=t_{1}}^{t_{2}}\sum_{x,a}\alpha_{t}(x,a)\left(\widehat{ f}_{t}(x,a)-\frac{q_{t}(x,a)}{u_{t}(x,a)}f_{t}(x,a)\right)\leq H\ln\left(\frac {HT^{2}}{\delta}\right)\right]\leq\delta.$ $$

This concludes the proof.
∎

###### Corollary 1 .

Given $\delta\in(0,1)$, it holds with probability at least $1-2\delta$ simultaneously for all $t_{1},t_{2}\in[T]$ such that $1\leq t_{1}\leq t_{2}\leq T$:

$$ $\sum_{t=t_{1}}^{t_{2}}\sum_{x,a}\left(\widehat{f}_{t}(x,a)-f_{t}(x,a)\right) \leq\frac{ZH}{2\gamma}\ln\left(\frac{HT^{2}}{\delta}\right).$ $$

###### Lemma 10 .

Let $\{\pi_{t}\}_{t=1}^{T}$ policies, then for any collection of transition $P_{t}^{x}\in\mathcal{P}_{i(t)}$ with probability at least $1-2\delta$,

$$ $\sum_{t=1}^{T}\lVert q^{P,\pi_{t}}-q^{P_{t}^{x},\pi_{t}}\rVert_{1}\leq 2H|X|^{ 2}\sqrt{2T\ln\left(\frac{H|X|}{\delta}\right)}+3H|X|^{2}\sqrt{2T|A|\ln\left( \frac{T|X|^{2}|A|}{\delta}\right)}.$ $$

###### Proof.

It holds:

$$ $\displaystyle\sum_{t=1}^{T}\lVert q^{P,\pi_{t}}-q^{P_{t}^{x},\pi_{t}}\rVert_{1}$ $\displaystyle=\sum_{t=1}^{T}\sum_{x,a}\lvert q^{P,\pi_{t}}(x,a)-q^{P_{t}^{x}, \pi_{t}}(x,a)\rvert$ $\displaystyle\leq\sum_{t=1}^{T}\sum_{x,a}\sum_{x^{\prime}}\lvert q^{P,\pi_{t}} (x^{\prime},a)-q^{P_{t}^{x},\pi_{t}}(x^{\prime},a)\rvert$ $\displaystyle=\sum_{x}\sum_{t=1}^{T}\sum_{x^{\prime},a}\lvert q^{P,\pi_{t}}(x^ {\prime},a)-q^{P_{t}^{x},\pi_{t}}(x^{\prime},a)\rvert$ $\displaystyle\leq\sum_{x}\left(2H|X|\sqrt{2T\ln\left(\frac{H|X|}{\delta}\right )}+3H|X|\sqrt{2T|A|\ln\left(\frac{T|X|^{2}|A|}{\delta}\right)}\right)$ $\displaystyle\leq|X|\left(2H|X|\sqrt{2T\ln\left(\frac{|X|H}{\delta}\right)}+3H |X|\sqrt{2T|A|\ln\left(\frac{T|X|^{2}|A|}{\delta}\right)}\right),$ $$

by Lemma 13, taking the union bound over $X$ $\left(\delta^{\prime}=\frac{\delta}{|X|}\right)$. This concludes the proof.
∎

###### Lemma 6 (Adapted from (Luo et al., 2021 ) Lemma C.4) .

###### Proof.

###### Lemma 7 (Adapted from (Luo et al., 2021 ) , Lemma B.1) .

###### Proof.

###### Lemma 8 (Adapted from (Luo et al., 2021 ) , Lemma A.1) .

###### Proof.

###### Lemma 9 (Adapted from (Jin et al., 2020 ) ) .

###### Proof.

###### Corollary 1 .

###### Lemma 10 .

###### Proof.

## Appendix K Auxiliary Lemmas From Existing Works

###### Lemma 11 ( Stradi et al. ( 2024a ) lemma D.2) .

For $\eta\leq\frac{1}{mH}$ and $\frac{M}{\rho}>4$, if $\lVert\lambda_{t_{2}+1}\rVert_{1}>\frac{2HM}{\rho^{2}}$ and $\lVert\lambda_{t_{1}}\rVert_{1}\leq\frac{4H}{\rho}$ it holds:

$$ $(t_{2}-t_{1}+1)>\frac{M}{\rho^{2}m\eta}$ $$

###### Lemma 12 ( Rosenberg and Mansour ( 2019a ) ) .

For any $\delta\in(0,1)$

$$ $\lVert P(\cdot|x,a)-\overline{P}_{i}(\cdot|x,a)\rVert_{1}\leq\sqrt{\frac{2|X_{ h(x)+1}|\ln\left(\frac{T|X||A|}{\delta}\right)}{\max\{1,N_{i}(x,a)\}}},$ $$

simultaneously for all $(x,a)\in X\times A$ and for all epochs with probability at least $1-\delta$.

###### Lemma 13 ( Rosenberg and Mansour ( 2019a ) ) .

Let $\{\pi_{t}\}_{t=1}^{T}$ policies and let $\{P_{t}\}_{t=1}^{T}$ transition functions such that $q^{P_{t},\pi_{t}}\in\Delta(\mathcal{P}_{i(t)})$ for every $t\in[T]$. Then with probability at least $1-2\delta$,

$$ $\sum_{t=1}^{T}\lVert q^{P,\pi_{t}}-q^{P_{t},\pi_{t}}\rVert_{1}\leq 2H|X|\sqrt{ 2T\ln\left(\frac{H}{\delta}\right)}+3H|X|\sqrt{2T|A|\ln\left(\frac{T|X||A|}{ \delta}\right)}.$ $$

###### Lemma 11 ( Stradi et al. ( 2024a ) lemma D.2) .

###### Lemma 12 ( Rosenberg and Mansour ( 2019a ) ) .

###### Lemma 13 ( Rosenberg and Mansour ( 2019a ) ) .

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: 1. (Line 144): It seems like the occupancy measure, $q^{P, \pi}$ should be a function of $h$. However, it certainly is not. Am I missing something? Should there be an averaging over $h$ instead?

2. I see that the regret is computed using the optimal policy in hindsight. However, I believe a more sensible approach should have been to compute the optimal policy for each episode separately and then use that to compute regret. In summary, instead of using $T\mathrm{Opt}\_{\bar{r}, \bar{G}}$ as the baseline in regret computation, the term $\sum_{t} \mathrm{Opt}\_{r_t, G_t}$ should have been used. Any comment on why the second approach is not used?

3. Theorem 7: Can the roles of regret and constraint violation be reversed? In other words, is it possible to derive a $\mathcal{O}(\sqrt{T})$ regret bound while the constraints are satisfied up to some fractions?

4. Section 4.2.1: Shouldn't $\mathrm{Opt}^{\mathcal{W}}$ be a function of $t$ (since $G_t$ is used in the optimization instead of its time averaged value)?
soundness: 3
strengths: 1. Clarity on presentation.
2. Sound analysis.
summary: The authors present an algorithm for adversarial CMDP. They showed that it achieves $\mathcal{O}(T^{3/4})$ regret and constraint violation both in the stochastic and adversarial setting with modified baselines.
weaknesses: **Minor Comments**

1. I think the definition of the occupancy measure is wrong. See the questions below for more details.

2. The bonus update seems ambiguous (lines 312, 313). In this update, both LHS and RHS have the term $B_t(x, a)$, and the only initial condition given is $B_t(x_H, a)=0$, $\forall a$ (this is mentioned in the algorithm, not in the main text). I guess the layered structure of the state space is essential to fill up all entries of $B_t(\cdot, \cdot)$ using the stated update. This should be emphasized in the main text for the reader's benefit. 

**Major Comments**

3. Theorem 3: In the worst case, the loss range upper bound can be an increasing function of $T$. Hence, in general, the regret upper bound may no longer be $\mathcal{O}(\sqrt{T})$, and thus the algorithm FS-PODB cannot be claimed to be no-regret.

4.  Condition 2 holds for small $T$. Therefore, Theorem 5, 7 and 8 also hold for small $T$. I think the authors are misusing the $\mathcal{O}(\cdot)$ notations in these theorems. Note that a $\mathcal{O}(\sqrt{T})$ regret should mean that the algorithm incurs at most $k\sqrt{T}$ regret for all $T\geq T_0$ where $k, T_0$ are some constants. This is clearly not true for Theorem 5, 7 and 8. 

5. In the stochastic setting, the regret obtained by the authors for large $T$ is $\mathcal{O}(T^{3/4})$ (Theorem 6). This should be the only result reported by the authors in the stochastic setting, and Theorem 5 should be discarded. The introduction and abstract should be changed accordingly. Surely, $\mathcal{O}(\sqrt{T})$ should not be highlighted as the primary result since it might mislead the readers. In the above light, the result of the authors seems weaker than Stradi et. al. (2024b). The claims accordingly have to be weakened in the introduction.

6. Similarly, Theorem 7, 8 should be discarded and only Theorem 9 should be kept in the adversarial setting with modified baseline. Since Theorem 7 was one of the main contributions of this paper, I am not sure what contribution of the paper remains.

7. The authors did not discuss the computational complexity of their algorithm in each iteration, although it was once of the main motivation mentioned in the introduction. In order to compute this complexity, the authors should take $S^H$ as the size of the state space since a general state space may not have a layered structure. The authors should compare their computational complexity with that of the earlier papers which they claimed to have more difficult problems to solve in each iteration.

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 4
questions: - Besides allowing the algorithm to be more efficient by, is there any theoretical benefit of conducting the analysis via an policy optimization approach. For example, could the analysis have been done using an occupancy-measure-based methods like in prior work?
- Spelling: 176 "ti" -> "it"
soundness: 3
strengths: - The proposed method extends prior work to a more practical setting while retaining similar guarantees
- The authors do a good job in presenting the problem setting and algorithm
summary: The authors introduce an algorithm for online learning in CMDP with either stochastic and adversarial constraints while only requiring bandit feedback unlike in prior work. The resulting regret and constraint violation bounds matches prior work with full-feedback and retain the property of not requiring the knowledge of the Slater's parameter. Additionally, the authors show that using a weaker-baseline that only requires a policy to satisfy a constraint at each episode, the propose algorithm achieve sub-linear regret and constraint violations.
weaknesses: - It's unclear why is the useful to consider a weaker baseline since it is unclear what is the befit (from a practical standpoint) of only considering the optimal policy that  respect the constraints at each episode
- Having simple numerical experiments would help showcase the benefit of updating the primal based on a policy optimization approach vs the occupancy measure space.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: If Condition 2 holds, then the regret and violation are $\Lambda \sqrt{T}$. According to Theorem 4, $\Lambda \leq \frac{c}{\rho^2} \leq \frac{c}{T^4}$. Does this mean that the regret and violation can achieve an order of $T^{1/4}$? How can this be true, as it would even better than the lower bound?
soundness: 2
strengths: The paper considers the CMDP setting with bandit feedback in both stochastic and adversarial settings, which is more practical. The authors provide theoretical guarantees on regret and constraint violation, with a specific analysis of the dependency on Slater’s condition. By focusing on policy space optimization rather than occupancy measures, the paper presents a more computationally efficient alternative for real-world applications where solving convex programs per episode is infeasible.
summary: This paper proposes an algorithm for online CMDPs with bandit feedback under both stochastic and adversarial constraints settings. Applying an existing policy optimization algorithm to a primal-dual approach to policy optimization, the algorithm achieves $\sqrt{T}$ regret and constraint violation bounds for stochastic constraints under certain conditions, and a $\sqrt{T}$ condition violation under adversarial constraints.
weaknesses: - The paper’s theoretical results rely heavily on Condition 2. As discussed in Section 2.4, $\rho \in [0, H]$; however, it is unclear how this condition could hold even when $T = 1$. Even setting aside this issue, if Condition 2 does hold, it implies that $\rho$ must be a relatively large value as $T$ increases, which is likely to be the case in online settings. According to Theorem 4, the Lagrangian multiplier is bounded by $c/\rho^2$, resulting in a very small constant close to zero. In such cases, the reward function becomes the dominant term, yielding a regret rate of $\sqrt{T}$.

- The theoretical analysis heavily relies on prior work by Stradi et al. (2024b) and Luo et al. (2021). 
- No simulations are included to support the efficiency claims made by the authors.

A lot of relevant papers on online CMDPs are missing:

[1] Arnob Ghosh, Xingyu Zhou, and Ness Shroff. Provably efficient model-free constrained rl with linear function approximation. Advances in Neural Information Processing Systems, 35:13303–13315, 2022

[2] Tao Liu, Ruida Zhou, Dileep Kalathil, Panganamala Kumar, and Chao Tian. Learning policies with zero or bounded constraint violation for constrained mdps. Advances in Neural Information Processing Systems, 34:17183–17193, 2021.

[3] Adrian Müller, Pragnya Alatur, Giorgia Ramponi, and Niao He. Cancellation-free regret bounds for lagrangian approaches in constrained markov decision processes. arXiv preprint arXiv:2306.07001, 2023.

[4] Adrian Müller, Pragnya Alatur, Volkan Cevher, Giorgia Ramponi, and Niao He. Truly no-regret learning in constrained mdps. arXiv preprint arXiv:2402.15776, 2024.

[5] Honghao Wei, Xin Liu, and Lei Ying. Triple-q: A model-free algorithm for constrained reinforcement learning with sublinear regret and zero constraint violation. In International Conference on Artificial Intelligence and Statistics, pages 3274–3307. PMLR, 2022.

[6] Qinbo Bai, Amrit Singh Bedi, Mridul Agarwal, Alec Koppel, and Vaneet Aggarwal. Achieving zero constraint violation for constrained reinforcement learning via primal-dual approach. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 3682–3689, 2022.

[7] Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo Jovanovic. Provably efficient safe exploration via primal-dual policy optimization. In International conference on artificial intelligence and statistics, pages 3304–3312. PMLR, 2021.

[8] Dongsheng Ding, Chen-Yu Wei, Kaiqing Zhang, and Alejandro Ribeiro. Last-iterate convergent policy gradient primal-dual methods for constrained mdps. Advances in Neural Information Processing Systems, 36, 2024.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: I do not understand why the authors design  the algorithm based on policy optimization. It seems there is no substantial difficulty in applying the occupancy-based algorithm (Stradi et. al., 2024) with the same reward\&constraint estimators. Although the policy optimization algorithm seems more practical, it might leads to worse dependence on other parameters. Is there any potential advantages by applying policy optimization to solve CMDP?

Typo: it should be $\rho\geq T^{-1/8}H\sqrt{112m}$ in Condition 2?
soundness: 3
strengths: 1. This paper considers the bandit feedback setting of learning a CMDP, which is the case of many practical problems..

2. The proposed regret\& violation bounds match the best previous result under full-information feedback.
summary: This paper studies the problem of learning a constrained MDP under bandit feedback. The authors propose a policy-based algorithm to reach $\tilde{O}(T^{3/4})$ regret and violations. By assuming that the Lagrangian multiplier  is bounded by $\Lambda$, the regret and violation bounded could be improved to $\tilde{O}(\Lambda\sqrt{T})$.  In the meantime, the proposed algorithm could also achieve similar regret and violation bounds under the adversarial setting, which is referred as "best-of-both-worlds" property.
weaknesses: 1. The technical novelty is limited given the previous work (Stradi et. al., 2024). (Stradi et. all 2024) worked on the same problem with full-information feedback. As far as I can see, there is no substantial difficulty to combine their algorithm with classical estimators for online learning with bandit-feedback.

2. The key problem in (Stradi et. al., 2024) is not resolved (whether it is possible to remove the slater condition number in the violation and regret bound. In other words, whether a $\tilde{O}(\sqrt{T})$ regret & violation bound is achievable without further assumptions for the best-of-both-worlds setting). It is known (Jin et. al., 2020) that for reward-adv MDP without constraints, it is possible to reach an $\tilde(O)(\sqrt{T})$ regret, while for stochastic reward and constraints, there exists algorithm (Agrawal et. al., 2022) to reach $\tilde{O}(\sqrt{T})$ regret\& violation bound. So the question is that: is it possible to get an $\tilde{O}(\sqrt{T})$ regret (violation) bound for CMDP with adv reward (constraints)?

3. As claimed by the authors, one possible benefit by policy optimization is to avoid solving some convex optimization problem. But there is empirical results to demonstrate that the policy-based algorithm is more efficient than the occupancy-based algorithm.

References:

[Jin et. al., 2020] Learning Adversarial MDPs with Bandit Feedback and Unknown Transition

[Agrawal et. al., 2022] Regret Guarantees for Model-Based Reinforcement Learning with Long-Term Average Constraints

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: Please see the weakness.
soundness: 2
strengths: The proposed algorithm achieves some interesting results, such as sublinear regret and constraint violation for stochastic settings and a constant competitive ratio for adversarial settings.
summary: This paper studied the constrained Markov decision process (CMDP) problem where the transition kernel is stochastic unknown, and the reward and costs could be adversarial and stochastic settings. The paper leverages the techniques from the existing literature to address the trade-off between rewards and constraint violations. The theoretical analysis is provided to justify the proposed algorithm.
weaknesses: 1. The paper studied the Constrained Markov Decision Process (CMDP) problem in both stochastic and adversarial settings. However, it heavily relies on the framework established by previous works (e.g., policy optimization in Luo et al., 2021; primal-dual design and analysis in Castiglioni et al., 2022b; Stradi et al., 2024b). This combination seems not interesting and the technical contribution of this paper is somewhat limited for a theory paper, especially considering the extensive literature on CMDPs, both in theory and algorithmic sides.

2. The metric of cumulative constraint violation is problematic in safety-critical applications in the paper because it may have limitations since it allows for compensation among different rounds. 

3. The proposed method adopts a model-based approach and is limited to tabular settings. It might not be scalable to the setting with a large state and action space. 

4. The paper primarily focuses on theoretical aspects; however, it would be beneficial to include numerical experiments to validate the proposed algorithm. By comparing it with representative studies in the extensive literature, such as the LP-based method discussed in Efroni et al. (2020) and Stradi et al. (2024b), as well as a model-based RL method in reference [1] and a model-free RL method in reference [2], the practical performance of the algorithm can be more clearly demonstrated. BTW, [1] and [2] are very related work and not mentioned in the paper. 

[1] Tao Liu, Ruida Zhou, Dileep Kalathil, PR Kumar, and Chao Tian. Learning policies with zero or bounded constraint violation for constrained MDPs. NeurIPS 2021.

[2] Arnob Ghosh, Xingyu Zhou, and Ness Shroff. Provably efficient model-free constrained rl with linear function approximation. NeurIPS 2022.

Meta-review: This paper considers the online constrained Markov decision problem (CMDP) with bandit feedback under both stochastic and adversarial constraints. The CMDP considered is under the finite horizon episodic setting. The authors propose a best-of-both-worlds algorithm that can handle the considered problem setting with both stochastic and adversarial constraints. Based on the value of a constant $\rho$ that captures the "degree" that Slater's condition is satisfied, $O(T^{1/2})$ or $O(T^{3/4})$ regret/violation can be achieved.

After the author-reviewer discussion, there are still several issue that has yet been cleared. 

First, even as a theoretical paper, this work lacks basic numerical evaluation of the result. Second, and most importantly, even after correcting the typo in Cond. 2, it still remains not well-justified. According to the defination, $\rho$ is in fact not a constant. In stochastic setting it relies on $\bar{G}:=(G_1+\cdots+G_T)/T$. In adversarial setting it relies on all $G_t, t\leq T$ and involves a minimum over $t$. That is $\rho$ should in fact be $\rho_T$ and is changing in each step. The current Cond. 2 is misleading in that $\rho$ looks like a constant and Cond.2 "seems to hold when T is large enough". However, as $\rho_T$ is changing in each step (even monotonically decreasing for adversarial setting), there lacks justification on why Cond. 2 should eventually hold.  

Overall, the AC would give a rejection to the paper.

Decision: Reject