Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraints

## Abstract

Abstract In constrained Markov decision processes (CMDPs) with adversarial rewards and constraints, a well-known impossibility result prevents any algorithm from attaining both sublinear regret and sublinear constraint violation, when competing against a best-in-hindsight policy that satisfies constraints on average.
In this paper, we show that this negative result can be eased in CMDPs with non-stationary rewards and constraints, by providing algorithms whose performances smoothly degrade as non-stationarity increases.
Specifically, we propose algorithms attaining 𝒪 ~ ⁢ ( T + C ) ~ 𝒪 𝑇 𝐶 \tilde{\mathcal{O}}(\sqrt{T}+C) over~ start_ARG caligraphic_O end_ARG ( square-root start_ARG italic_T end_ARG + italic_C ) regret and positive constraint violation under bandit feedback, where C 𝐶 C italic_C is a corruption value measuring the environment non-stationarity.
This can be Θ ⁢ ( T ) Θ 𝑇 \Theta(T) roman_Θ ( italic_T ) in the worst case, coherently with the impossibility result for adversarial CMDPs.
First, we design an algorithm with the desired guarantees when C 𝐶 C italic_C is known.
Then, in the case C 𝐶 C italic_C is unknown , we show how to obtain the same results by embedding such an algorithm in a general meta-procedure .
This is of independent interest, as it can be applied to any non-stationary constrained online learning setting.

## 1 Introduction

Reinforcement learning (Sutton and Barto, ) is concerned with settings where a learner sequentially interacts with an environment modeled as a *Markov decision process* (MDP) (Puterman, ).
Most of the works in the field focus on learning policies that maximize learner’s rewards.
However, in most of the real-world applications of interest, the learner also has to meet some additional requirements.
For instance, autonomous vehicles must avoid crashing (Isele et al., ; Wen et al., ), bidding agents in ad auctions must *not* deplete their budget (Wu et al., ; He et al., ), and users of recommender systems must *not* be exposed to offending content (Singh et al., ).
These requirements can be captured by *constrained* MDPs (CMDPs) (Altman, ), which generalize MDPs by specifying constraints that the learner has to satisfy while maximizing their rewards.

We study *online learning* in *episodic* CMDPs (see, *e.g.*, (Efroni et al., )), where the goal of the learner is twofold.
On the one hand, the learner wants to minimize their *regret*, which measures how much reward they lost over the episodes compared to what they would have obtained by always using a best-in-hindsight constraint-satisfying policy.
On the other hand, the learner wants to ensure that the *(cumulative) constraint violation* is minimized during the learning process.
Ideally, one seeks for algorithms with both regret and constraint violation growing sublinearly in the number of episodes $T$.

A crucial feature distinguishing online learning problems in CMDPs is whether rewards and constraints are selected *stochastically* or *adversarially*.
Most of the works focus on the case in which constraints are stochastic (see, *e.g.*, (Wei et al., ; Zheng and Ratliff, ; Efroni et al., ; Qiu et al., ; Liu et al., ; Bai et al., )), with only one exception addressing settings with adversarial constraints (Germano et al., ).
This is primarily motivated by a well-known impossibility result by Mannor et al. (), which prevents any learning algorithm from attaining both sublinear regret and sublinear constraint violation, when competing against a best-in-hindsight policy that satisfies the constraints *on average*.
However, dealing with adversarially-selected constraints is of paramount importance to cope with real-world environments, which are typically non-stationary.

### 1.1 Original contributions

The main contribution of this paper is to show how to ease the negative result of (Mannor et al., ), by considering CMDPs with *non-stationary rewards and constraints*.
Specifically, we address CMDPs where rewards and constraints are selected from probability distributions that are allowed to change *adversarially* from episode to episode.
One may think of our setting as bridging the gap between fully-stochastic and fully-adversarial ones.
We design algorithms whose performances—in terms of regret and constraint violation—smoothly degrade as a suitable measure of non-stationarity increases.
This is called *(adversarial) corruption*, as it intuitively quantifies how much the distributions of rewards and constraints vary over the episodes with respect to some “fictitious” non-corrupted counterparts.

We propose algorithms that attain $\tilde{\mathcal{O}}(\sqrt{T}+C)$ regret and constraint violation, where $C$ denotes the corruption of the setting.
We remark that $C$ can be $\Theta(T)$ in the worst case, and, thus, our bounds are coherent with the impossibility result by Mannor et al. ().
Notably, our algorithms work under *bandit* feedback, namely, by only observing rewards and constraint costs of the state-action pairs visiting during episodes.
Moreover, they are able to manage *positive* constraint violation.
This means that they do *not* allow for a negative violation (*i.e.*, a constraint satisfaction) to cancel out a positive one across different episodes.
This is a crucial requirement for most of the practical applications.
For instance, in autonomous driving, avoiding a collision does *not* “repair” a previously-occurred crash.

In the first part of the paper, we design an algorithm, called NS-SOPS, which works assuming that the value of the corruption $C$ is known.
This algorithm achieves $\tilde{\mathcal{O}}(\sqrt{T}+C)$ regret and positive constraint violation by employing a *policy search* method that is *optimistic* in both reward maximization and constraint satisfaction.
Specifically, the algorithm incorporates $C$ in the confidence bounds of rewards and constraint costs, so as to “boost” its optimism and achieve the desired guarantees.

In the second part of the paper, we show how to embed the NS-SOPS algorithm in a *meta-procedure* that allows to achieve $\tilde{\mathcal{O}}(\sqrt{T}+C)$ regret and positive constraint violation when $C$ is *unknown*.
The meta-procedure works by instantiating multiple instances of an algorithm for the case in which $C$ is known, each one taking care of a different “guess” on the value of $C$.
Specifically, the meta-procedure acts as a *master* by choosing which instance to follow in order to select a policy at each episode.
To do so, it employs an adversarial online learning algorithm, which is fed with losses constructed starting from the Lagrangian of the CMDP problem, suitably modified to account for *positive* constraint violation.
Our meta-procedure is of independent interest, as it can be applied in *any* non-stationary constrained online learning setting, so as to relax the knowledge of $C$.

### 1.2 Related works

Within the literature on CMDPs, settings with *stochastic* rewards and constraints have been widely investigated.
However, their *non-stationary* counterparts, including *adversarial* ones in the worst case, are still largely unexplored.
In the following, we discuss the works that are most related to ours, while we refer the reader to Appendix A for a comprehensive survey of related works.

Qiu et al. () provide the first primal-dual approach to deal with episodic CMDPs with adversarial losses and stochastic constraints, achieving, under full feedback, both sublinear regret and sublinear (non-positive) constraint violation (*i.e.*, allowing for cancellations).
Stradi et al. () are the first to tackle CMDPs with adversarial losses and stochastic constraints under bandit feedback, by proposing an algorithm that achieves sublinear regret and sublinear positive constraint violation.
These works do *not* consider settings where constraints are non-stationary, *i.e.*, they may change over the episodes.

Ding and Lavaei () and Wei et al. () consider the case in which rewards and constraints are non-stationary, assuming that their variation is bounded.
Our work differs from theirs in multiple aspects.
First, we consider *positive* constraint violation, while they allow for cancellations.
As concerns the definition of regret, ours and that used by Ding and Lavaei () and Wei et al. () are *not* comparable.
Indeed, they employ a dynamic regret baseline, which, in general, is harder than the static regret employed in our work.
However, they compare learner’s performances against a dynamic policy that satisfies the constraints at every round.
Instead, we consider a policy that satisfies the constraints *on average*, which can perform arbitrarily better than a policy satisfying the constraints at every round.
Furthermore, the dependence on $T$ in their regret bound is much worse than ours, even when the non-stationarity is small, namely, when it is a constant independent of $T$ (and, thus, dynamic regret collapses to static regret).
Finally, we do *not* make any assumption on $T$, while both regret and constraint violation bounds in (Wei et al., ) only hold for large $T$.

Finally, Germano et al. () are the first to study CMDPs with adversarial constraints.
Given the impossibility result by Mannor et al. (), they propose an algorithm that, under full feedback, attains sublinear (non-positive) constraint violation (*i.e.*, with cancellations allowed) and a fraction of the optimal reward, thus resulting in a regret growing linearly in $T$.
We show that sublinear regret and sublinear constraint violation can indeed be attained simultaneously if one takes into account the corruption $C$, which can be seen as a measure of how much adversarial the environment is.
Moreover, let us remark that our algorithms deal with *positive* constraint violation under *bandit* feedback, and, thus, they are much more general than those in (Germano et al., ).

## 2 Preliminaries

### 2.1 Constrained Markov decision processes

We study *episodic constrained* MDPs (Altman, ) (CMDPs), in which a learner interacts with an unknown environment over $T$ episodes, with the goal of maximizing long-term rewards subject to some constraints.
$X$ is a finite set of states of the environment, $A$ is a finite set of actions available to the learner in each state, while the environment dynamics is governed by a transition function $P:X\times A\times X\to[0,1]$, with $P(x^{\prime}|x,a)$ denoting the probability of going from state $x\in X$ to $x^{\prime}\in X$ by taking action $a\in A$.(^1^11In this paper, we consider w.l.o.g. *loop-free* CMDPs. This means that $X$ is partitioned into $L$ layers $X_{0},\dots,X_{L}$ such that the first and the last layers are singletons, *i.e.*, $X_{0}=\{x_{0}\}$ and $X_{L}=\{x_{L}\}$. Moreover, the loop-free property implies that $P(x^{\prime}|x,a)>0$ only if $x^{\prime}\in X_{k+1}$ and $x\in X_{k}$ for some $k\in[0\ldots L-1]$. Notice that any episodic CMDP with horizon $L$ that is *not* loop-free can be cast into a loop-free one by suitably duplicating the state space $L$ times, *i.e.*, a state $x$ is mapped to a set of new states $(x,k)$, where $k\in[0\ldots L]$.)At each episode $t\in[T]$,(^2^22In this paper, we denote by $[a\ldots b]$ the set of all the natural numbers from $a\in\mathbb{N}$ to $b\in\mathbb{N}$ (both included), while $[b]\coloneqq[1\ldots b]$ is the set of the first $b\in\mathbb{N}$ natural numbers.) a reward vector $r_{t}\in[0,1]^{|X\times A|}$ is sampled according to a probability distribution $\mathcal{R}_{t}$, with $r_{t}(x,a)$ being the reward of taking action $a\in A$ in state $x\in X$ at episode $t$.
Moreover, a constraint cost matrix $G_{t}\in[0,1]^{|X\times A|\times m}$ is sampled according to a probability distribution $\mathcal{G}_{t}$, with $g_{t,i}(x,a)$ being the cost of constraint $i\in[m]$ when taking action $a\in A$ in state $x\in X$ at episode $t$.
We also denote by $g_{t,i}\in[0,1]^{|X\times A|}$ the vector of all the costs $g_{t,i}(x,a)$ associated with constraint $i$ at episode $t$.
Each constraint requires that its corresponding expected cost is kept below a given threshold.
The thresholds of all the $m$ constraints are encoded in a vector $\alpha\in[0,L]^{m}$, with $\alpha_{i}$ denoting the threshold of the $i$-th constraint.

We consider a setting in which the sequences of probability distributions $\{\mathcal{R}_{t}\}_{t=1}^{T}$ and $\{\mathcal{G}_{t}\}_{t=1}^{T}$ are selected *adversarially*.
Thus, reward vectors $r_{t}$ and constraint cost matrices $G_{t}$ are random variables whose distributions are allowed to change arbitrarily from episode to episode.
To measure how much such probability distributions change over the episodes, we introduce the notion of *(adversarial) corruption*.
In particular, we define the adversarial corruption $C_{r}$ for the rewards as follows:

$$ $C_{r}\coloneqq\min_{r\in[0,1]^{|X\times A|}}\sum_{t\in[T]}\left\lVert\mathbb{E }[r_{t}]-r\right\rVert_{1}.$ (1) $$

Intuitively, the corruption $C_{r}$ encodes the sum over all episodes of the distances between the means $\mathbb{E}[r_{t}]$ of the adversarial distributions $\mathcal{R}_{t}$ and a “fictitious” non-corrupted reward vector $r$.
Notice that a similar notion of corruption has been employed in unconstrained MDPs to measure the non-stationarity of transition probabilities; see (Jin et al., ).
In the following, we let $r^{\circ}\in[0,1]^{|X\times A|}$ be a reward vector that attains the minimum in the definition of $C_{r}$.
Similarly, we introduce the adversarial corruption $C_{G}$ for constraint costs, which is defined as follows:

$$ $C_{G}\coloneqq{\min_{G\in[0,1]^{|X\times A|\times m}}}\underset{t\in[T]}{\sum} \underset{i\in[m]}{\max}\lVert\mathbb{E}[g_{t,i}]-g_{i}\rVert_{1},$ (2) $$

where $g_{i}$ is the $i$-th component of $G$. We let $G^{\circ}\in[0,1]^{|X\times A|\times m}$ be the constraint cost matrix that attains the minimum in the definition of $C_{G}$.
Finally, we introduce the total adversarial corruption $C$, which is defined as $C\coloneqq\max\{C_{G},C_{r}\}$.

Figure: Algorithm 1 Learner-Environment Interaction

Algorithm 1 summarizes how the learner interacts with the environment at episode $t\in[T]$.
In particular, the learner chooses a *policy* $\pi:X\times A\to[0,1]$ at each episode, defining a probability distribution over actions to be employed in 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)$ being the probability of selecting action $a\in A$.
Let us remark that we assume that the learner knows $X$ and $A$, but they do *not* know anything about $P$.
Moreover, the *feedback* received by the learner after each episode is *bandit*, as they observe the realizations of rewards and constraint costs only for the state-action pairs $(x_{k},a_{k})$ actually visited during that episode.

### 2.2 Occupancy measures

Next, we introduce *occupancy measures*, following the notation by (Rosenberg and Mansour, ).
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 every $x\in X_{k}$, $a\in A$, and $x^{\prime}\in X_{k+1}$ with $k\in[0\ldots L-1]$:

$$ $q^{P,\pi}(x,a,x^{\prime})\coloneqq\mathbb{P}[x_{k}=x,a_{k}=a,x_{k+1}=x^{\prime }|P,\pi],$ (3) $$

which represents the probability that, under $P$ and $\pi$, the learner reaches state $x$, plays action $a$, and gets to the next state $x^{\prime}$.
Moreover, we also define the following quantities:

$$ $\displaystyle q^{P,\pi}(x,a)\coloneqq\sum_{x^{\prime}\in X_{k+1}}q^{P,\pi}(x,a ,x^{\prime})\quad\text{and}\quad q^{P,\pi}(x)\coloneqq\sum_{a\in A}q^{P,\pi}(x ,a).$ (4) $$

The following lemma characterizes when a vector $q\in[0,1]^{|X\times A\times X|}$ is a *valid* occupancy measure.

###### Lemma 1 ( Rosenberg and Mansour ( 2019b ) ) .

A vector $q\in[0,1]^{|X\times A\times X|}$ is a valid occupancy measure of an episodic loop-free CMDP if and only if it satisfies the following conditions:

$$ $\begin{cases}\displaystyle\sum_{x\in X_{k}}\sum_{a\in A}\sum_{x^{\prime}\in X_ {k+1}}q(x,a,x^{\prime})=1&\forall k\in[0\dots L-1]\\ \displaystyle\sum_{a\in A}\sum\limits_{x^{\prime}\in X_{k+1}}q(x,a,x^{\prime}) =\sum_{x^{\prime}\in X_{k-1}}\sum_{a\in A}q(x^{\prime},a,x)&\forall k\in[1 \dots L-1],\forall x\in X_{k}\\ P^{q}=P,\end{cases}$ $$

where $P$ is the transition function of the CMDP and $P^{q}$ is the one induced by $q$ (see Equation (5)).

Notice that any valid occupancy measure $q$ induces a transition function $P^{q}$ and a policy $\pi^{q}$ as:

$$ $P^{q}(x^{\prime}|x,a)=\frac{q(x,a,x^{\prime})}{q(x,a)}\quad\text{and}\quad\pi^ {q}(a|x)=\frac{q(x,a)}{q(x)}.$ (5) $$

###### Lemma 1 ( Rosenberg and Mansour ( 2019b ) ) .

### 2.3 Performance metrics to evaluate learning algorithms

In order to define the performance metrics used to evaluate our *online* learning algorithms, we need to introduce an *offline* optimization problem.
Given a CMDP with transition function $P$, we define the following parametric *linear program* (Program (6)), which is parametrized by a reward vector $r\in[0,1]^{|X\times A|}$, a constraint cost matrix $G\in[0,1]^{|X\times A|\times m}$ and a threshold vector ${\alpha}\in[0,L]^{m}$.

$$ $\text{OPT}_{r,G,{\alpha}}\coloneqq\begin{cases}\max_{q\in\Delta(P)}&r^{\top}q \quad\text{s.t.}\\ &G^{\top}q\leq{\alpha},\end{cases}$ (6) $$

where $q\in[0,1]^{|X\times A|}$ is a vector encoding an occupancy measure, whose values are defined for state-action pairs according to Equation (4), and $\Delta(P)$ is the set of all valid occupancy measures given the transition function $P$ (this set can be encoded by linear constraints thanks to Lemma 1).

We say that an instance of Program (6) satisfies *Slater’s condition* if the following holds.

###### Condition 1 (Slater) .

There exists an occupancy measure $q^{\circ}\in\Delta(P)$ such that $G^{\top}q^{\circ}<\alpha$.

Moreover, we also introduce a problem-specific *feasibility parameter* related to Program (6). This is denoted by $\rho\in[0,L]$ and formally defined as
$\rho\coloneqq\sup_{q\in\Delta(P)}\min_{i\in[m]}\left[\alpha-G^{\top}q\right]_{i}$.(^3^33In this paper, given a vector $y$, we denote by $[y]_{i}$ its $i$-th component.)
Intuitively, $\rho$ represents by how much feasible solutions to Program (6) strictly satisfy the constraints.
Notice that Condition 1 is equivalent to say that $\rho>0$, while, whenever $\rho=0$, there is no occupancy measure that allows to strictly satisfy the constraints $G^{\top}q\leq\alpha$ in Program (6).

We are now ready to introduce the notion of *(cumulative) regret* and *positive (cumulative) constraint violation*, which are the performance metrics that we use to evaluate our learning algorithm.
In particular, we define the cumulative regret over $T$ episodes as follows:

$$ $R_{T}\coloneqq T\cdot\text{OPT}_{\overline{r},\overline{G},\alpha}-\sum_{t\in[ T]}\mathbb{E}[r_{t}]^{\top}q^{P,\pi_{t}},$ $$

where $\overline{r}\coloneqq\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}[r_{t}]$ and $\overline{G}\coloneqq\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}[G_{t}]$.
In the following, we denote by $q^{*}$ an occupancy measure solving Program (6) instantiated with $\overline{r}$, $\overline{G}$, and $\alpha$, while its corresponding policy (computed by Equation (5)) is $\pi^{*}$.
Thus, $\text{OPT}_{\overline{r},\overline{G},\alpha}=\overline{r}^{\top}q^{*}$ and the regret is $R_{T}\coloneqq\sum_{t=1}^{T}\mathbb{E}[r_{t}]^{\top}(q^{*}-q^{P,\pi_{t}})$.
Furthermore, we define the positive cumulative constraint violation over $T$ episodes as:

$$ $V_{T}:=\max_{i\in[m]}\sum_{t\in[T]}\left[\mathbb{E}[G_{t}]^{\top}q^{P,\pi_{t}} -{\alpha}\right]^{+}_{i},$ $$

where we let $[\cdot]^{+}:=\max\{0,\cdot\}$.
In the following, for ease of notation, we compactly refer to $q^{P,\pi_{t}}$ as $q_{t}$, thus omitting the dependency on $P$ and $\pi$.

###### Remark 1 (Relation with adversarial/stochastic CMDPs) .

Our setting is more akin to CMDPs with adversarial rewards and constraints, rather than stochastic ones.
This is because our notion of regret is computed with respect to an optimal constraint-satisfying policy in hindsight that takes into account the average over episodes of the mean values $\mathbb{E}[r_{t}]$ and $\mathbb{E}[G_{t}]$ of the adversarially-selected probability distributions $\mathcal{R}_{t}$ and $\mathcal{G}_{t}$.
This makes our setting much harder than one with stochastic rewards and constraints.
Indeed, in the special case in which the supports of $\mathcal{R}_{t}$ and $\mathcal{G}_{t}$ are singletons (and, thus, mean values are fully revealed after each episode), our setting reduces to a CMDP with adversarial rewards and constraints, given that such supports are selected adversarially.

###### Remark 2 (Impossibility results carrying over from adversarial CMDPs) .

Mannor et al. () show that, in online learning problems with constraints selected adversarially, it is impossible to achieve both regret and constraint violation growing sublinearly in $T$.
This result holds for a regret definition that corresponds to ours. Thus, it carries over to our setting.
This is why we look for algorithms whose regret and positive constraint violation scale as $\tilde{\mathcal{O}}(\sqrt{T}+C)$, with a linear dependency on the adversarial corruption $C$.
Notice that the impossibility result by Mannor et al. () does not rule out the possibility of achieving such a guarantee, since regret and positive constraint violation are not sublinear when $C$ grows linearly in $T$, as it could be the case in a classical adversarial setting.

###### Condition 1 (Slater) .

###### Remark 1 (Relation with adversarial/stochastic CMDPs) .

###### Remark 2 (Impossibility results carrying over from adversarial CMDPs) .

## 3 Learning when C 𝐶 C italic_C is known: More optimism is all you need

We start studying the case in which the learner *knows* the adversarial corruption $C$.
We propose an algorithm (called NS-SOPS, see also Algorithm 2), which adopts a suitably-designed UCB-like approach encompassing the adversarial corruption $C$ in the confidence bounds of rewards and constraint costs.
This effectively results in “boosting” the *optimism* of the algorithm, and it allows to achieve regret and positive constraint violation of the order of $\tilde{\mathcal{O}}(\sqrt{T}+C)$.
The NS-SOPS algorithm is also a crucial building block in the design of our algorithm for the case in which the adversarial corruption $C$ is *not* known, as we show in the following section.

### 3.1 NS-SOPS : non-stationary safe optimistic policy search

Algorithm 2 provides the pseudocode of the *non-stationary safe optimistic policy search* (NS-SOPS for short) algorithm.
The algorithm keeps track of suitably-defined confidence bounds for transition probabilities, rewards, and constraint costs.
At each episode $t\in[T]$, the algorithm builds a confidence set $\mathcal{P}_{t}$ for the transition function $P$ by following the same approach as Jin et al. () (see Appendix G for its definition).
Instead, for rewards and constraint costs, the algorithm adopts novel *enlarged* confidence bounds, which are suitably designed to tackle non-stationarity.
Given $\delta\in(0,1)$, by letting $N_{t}(x,a)$ be the total number of visits to the state-action pair $(x,a)\in X\times A$ up to episode $t$ (excluded), the confidence bound for the reward $r_{t}(x,a)$ is:

$$ $\phi_{t}(x,a)\coloneqq\min\left\{1,\sqrt{\frac{\ln\left(\nicefrac{{2T|X||A|}}{ {\delta}}\right)}{2\max\{N_{t}(x,a),1\}}}+\frac{C}{\max\{N_{t}(x,a),1\}}+\frac {C}{T}\right\},$ $$

while the confidence bound for the constraint costs $g_{t,i}(x,a)$ is defined as:

$$ $\xi_{t}(x,a)\coloneqq\min\left\{1,\sqrt{\frac{\ln\left(\nicefrac{{2mT|X||A|}}{ {\delta}}\right)}{2\max\{N_{t}(x,a),1\}}}+\frac{{C}}{\max\{N_{t}(x,a),1\}}+ \frac{{C}}{T}\right\}.$ $$

Intuitively, the first term in the expressions above is derived from Azuma-Hoeffding inequality, the second term allows to deal with the non-stationarity of rewards and constraint costs, while the third term is needed to bound how much the average reward vector $\overline{r}$ and the average constraint costs $[\overline{G}]_{i}$ differ from their “fictitious” non-corrupted counterparts $r^{\circ}$ and $[G^{\circ}]_{i}$, respectively.

Algorithm 2 also computes empirical rewards and constraint costs.
At each episode $t\in[T]$, for any state-action pair $(x,a)\in X\times A$ and constraint $i\in[m]$, these are defined as follows:

$$ $\widehat{r}_{t}(x,a)\coloneqq\frac{\sum_{\tau\in[t]}\mathbb{I}_{\tau}(x,a)r_{ \tau}(x,a)}{\max\{N_{t}(x,a),1\}}\quad\text{and}\quad\widehat{g}_{t,i}(x,a) \coloneqq\frac{\sum_{\tau\in[t]}\mathbb{I}_{\tau}(x,a)g_{\tau,i}(x,a)}{\max\{N _{t}(x,a),1\}},$ $$

where $\mathbb{I}_{\tau}(x,a)=1$ if and only if $(x,a)$ is visited during episode $\tau$, while $\mathbb{I}_{\tau}(x,a)=0$ otherwise.
For ease of notation, we let $\widehat{G}_{t}\in[0,1]^{|X\times A|\times m}$ be the matrix with components $\widehat{g}_{t,i}(x,a)$.
We refer the reader to Appendix C for all the technical results related to confidence bounds.

Figure: Algorithm 2 NS-SOPS

Algorithm 2 selects policies with an UCB-like approach encompassing *optimism* in both rewards and constraints satisfaction, following an approach similar to that employed by Efroni et al. ().
Specifically, at each episode $t\in[T]$ and for any state-action pair $(x,a)\in X\times A$, the algorithm employs an *upper* confidence bound for the reward $r_{t}(x,a)$, defined as $\overline{r}_{t}(x,a)\coloneqq\widehat{r}_{t}(x,a)+\phi_{t}(x,a)$, while it uses *lower* confidence bounds for the constraint costs $g_{t,i}(x,a)$, defined as $\underline{g}_{t,i}(x,a)\coloneqq\widehat{g}_{t,i}(x,a)-\xi_{t}(x,a)$ for every constraint $i\in[m]$.
Then, by letting $\overline{r}_{t}\in[0,1]^{|X\times A|}$ be the vector with components $\overline{r}_{t}(x,a)$ and $\underline{G}_{t}$ be the matrix with entries $\underline{g}_{t,i}(x,a)$, Algorithm 2 chooses the policy to be employed in the next episode $t+1$ by solving the following linear program:

$$ $\text{{OPT-CB}}_{\Delta(\mathcal{P}_{t}),\overline{r}_{t},\underline{G}_{t}, \alpha}\coloneqq\begin{cases}\operatorname*{arg\,max}_{q\in\Delta(\mathcal{P}_ {t})}&\overline{r}_{t}^{\top}q\quad\text{s.t.}\\ &\underline{G}_{t}^{\top}q\leq{\alpha},\end{cases}$ (7) $$

where $\Delta(\mathcal{P}_{t})$ is the set of all the possible valid occupancy measures given the confidence set $\mathcal{P}_{t}$ (see Appendix G).
If $\texttt{OPT-CB}_{\Delta(\mathcal{P}_{t}),\overline{r}_{t},\underline{G}_{t},\alpha}$ is feasible, its solution is used to compute a policy to be employed in the next episode, otherwise the algorithm uses any occupancy measure in the set $\Delta(\mathcal{P}_{t})$.

### 3.2 Theoretical guarantees of NS-SOPS

Next, we prove the theoretical guarantees attained by Algorithm 2 (see Appendix D for complete proofs of the theorems and associated lemmas).
First, we analyze the positive cumulative violation incurred by the algorithm.
Formally, we can state the following result.

###### Theorem 2 .

Given any $\delta\in(0,1)$, with probability at least $1-8\delta$, Algorithm 2 attains:

$$ $V_{T}=\mathcal{O}\left(L|X|\sqrt{|A|T\ln\left(\nicefrac{{mT|X||A|}}{{\delta}} \right)}+\ln(T)|X||A|C\right).$ $$

Intuitively, Theorem 2 is proved by showing that every constraint-satisfying occupancy measure is also feasible for Program (7) with high probability.
This holds since Program (7) employs lower confidence bounds for constraint costs.
Thus, in order to bound $V_{T}$, it is sufficient to analyze at which rate the feasible region of Program (7) concentrates to the *true* one (*i.e.*, the one defined by $\overline{G}$ in Program (6)).
Since by definition of $\xi_{t}(x,a)$ the feasibility region of Program (7) concentrates as $1/\sqrt{t}+C/t$, the resulting bound for the positive constraint violation $V_{T}$ is of the order of $\tilde{\mathcal{O}}(\sqrt{T}+C)$.

The regret guaranteed by Algorithm 2 is formalized by the following theorem.

###### Theorem 3 .

Given any $\delta\in(0,1)$, with probability at least $1-9\delta$, Algorithm 2 attains:

$$ $R_{T}=\mathcal{O}\left(L|X|\sqrt{|A|T\ln\left(\nicefrac{{T|X||A|}}{{\delta}} \right)}+\ln(T)|X||A|C\right).$ $$

Theorem 3 is proved similarly to Theorem 2.
Indeed, since every constraint-satisfying occupancy measure is feasible for Program (7) with high probability, this also holds for $q^{*}$, as it satisfies constraints by definition.
Thus, since by definition of $\phi_{t}(x,a)$ the upper confidence bound for the rewards maximized by Program (7) concentrates as $1/\sqrt{t}+C/t$, the regret bound follows.

###### Remark 3 (What if some under/overestimate of $C$ is available) .

We also study what happens if the learner runs Algorithm 2 with an under/overestimate on the adversarial corruption as input.
We defer to Appendix E all the technical results related to this analysis.
In particular, it is possible to show that any underestimate on $C$ does not detriment the bound on $V_{T}$, which remains the one in Theorem 2.
On the other hand, an overestimate on $C$, say $\widehat{C}>C$, results in a bound on $V_{T}$ of the order of $\mathcal{O}(\sqrt{T}+\widehat{C})$, which is worse than the one in Theorem 2.
Intuitively, this is because using an overestimate makes Algorithm 2 too conservative.
As a result, one could be tempted to conclude that running Algorithm 2 with an underestimate of $C$ as input is satisfactory when the true value of $C$ is unknown.
However, this would lead to a regret $R_{T}$ growing linearly in $T$, since, intuitively, a regret-minimizing policy could be cut off from the algorithm decision space.
This motivates the introduction of additional tools to deal with the case in which $C$ is unknown, as we do in Section 4.

###### Theorem 2 .

###### Theorem 3 .

###### Remark 3 (What if some under/overestimate of C 𝐶 C italic_C is available) .

## 4 Learning when C 𝐶 C italic_C is not known: A Lagrangified meta-procedure

In this section, we go beyond Section 3 by studying the more relevant case in which the learner does *not* know the value of the adversarial corruption $C$.
In order to tackle this challenging scenario, we develop a *meta-procedure* (called Lag-FTRL, see Algorithm 3) that instantiates multiple instances of an algorithm working for the case in which $C$ is known, with each instance taking care of a different “guess” on the value of $C$.
The Lag-FTRL algorithm is inspired by the work of Agarwal et al. () in the context of classical (unconstrained) multi-armed bandit problems.
Let us remark that Lag-FTRL is a general algorithm that is *not* specifically tailored for our non-stationary CMDP setting.
Indeed, it could be applied to any non-stationary online learning problem with constraints when the adversarial corruption $C$ is unknown, provided that an algorithm working for known $C$ is available.
In this section, to deal with our non-stationary CMDP setting, we let Lag-FTRL instantiate multiple instances of the NS-SOPS algorithm developed in Section 3.

### 4.1 Lag-FTRL : Lagrangified FTRL

At a high level, the *Lagrangified follow-the-regularized-leader* (Lag-FTRL for short) algorithm works by instantiating several different instances of Algorithm 2, suitably stabilized (see section H), with each instance $\texttt{Alg}^{j}$ being run for a different “guess” of the (unknown) adversarial corruption value $C$.
The algorithm plays the role of a *master* by choosing which instance $\texttt{Alg}^{j}$ to use at each episode.
The selection is done by employing an FTRL approach with a suitable log-barrier regularization.
In particular, at each episode $t\in[T]$, by letting $\texttt{Alg}^{j_{t}}$ be the selected instance, the Lag-FTRL algorithm employs the policy $\pi_{t}^{j_{i}}$ prescribed by $\texttt{Alg}^{j_{t}}$ and provides the observed feedback to instance $\texttt{Alg}^{j_{t}}$ only.

The Lag-FTRL algorithm faces two main challenges.
First, the feedback available to the FTRL procedure implemented at the master level is *partial*.
This is because, at each episode $t\in[T]$, the algorithm only observes the result of using the policy $\pi_{t}^{j_{i}}$ prescribed by the chosen instance $\texttt{Alg}^{j_{t}}$, and *not* those of the policies suggested by other instances.
The algorithm tackles this challenge by employing *optimistic loss estimators* in the FTRL selection procedure, following an approach originally introduced by Neu ().
The second challenge originates from the fact that the goal of the algorithm is to keep under control both the regret and the positive constraint violation.
This is accomplished by feeding the FTRL procedure with losses constructed starting from the Lagrangian of the offline optimization problem in Program (6), and suitably modified to manage *positive* violations.

Figure: Algorithm 3 Lag-FTRL

The pseudocode of the Lag-FTRL algorithm is provided in Algorithm 3.
At Line 5, it instantiates $M\coloneqq\lceil\log_{2}T\rceil$ instances of Algorithm 2, with each instance $\texttt{Alg}^{j}$, for $j\in[M]$, receiving as input a “guess” on the adversarial corruption $C=2^{j}$. Notice that, to every instance of Algorithm 2, a standard doubling trick and a stabilization procedure is applied (see Algorithm 4 for additional details). This modification to Algorithm 2 is necessary to guarantee that each instance $j$ attains a regret and positive cumulative constraints violation which smoothly degrade with $\nu_{T,j}=\nicefrac{{1}}{{\min_{t\in[T]}w_{t,j}}}$ and linearly in $C$, when employed by the master algorithm. The algorithm assigns weights defining a probability distribution to instances $\texttt{Alg}^{j}$, with $w_{t,j}\in[0,1]$ denoting the weight of instance $\texttt{Alg}^{j}$ at episode $t\in[T]$.
We denote by $w_{t}\in\Delta_{M}$ the weight vector at episode $t$, with $\Delta_{M}$ being the $M$-dimensional simplex.
At the first episode, all the weights $w_{1,j}$ are initialized to the value $\nicefrac{{1}}{{M}}$ (Line 6).
Then, at each episode $t\in[T]$, the algorithm samples an instance index $j_{t}\in[M]$ according to the probability distribution defined by the weight vector $w_{t}$ (Line 8), and it employs the policy $\pi_{t}^{j_{t}}$ prescribed by $\texttt{Alg}^{j_{t}}$ (Line 9).
The algorithm observes the feedback from the interaction described in Algorithm 1 and it sends such a feedback to instance $\texttt{Alg}^{j_{t}}$ (Line 11).
Then, at Line 13, the algorithm builds an *optimistic* loss estimator to be fed into each instance $\texttt{Alg}^{j}$.
In particular, at episode $t\in[T]$ and for every $j\in[M]$, the optimistic loss estimator is defined as:

$$ $\ell_{t,j}\coloneqq\frac{\mathbb{I}(j_{t}=j)}{w_{t,j}+\gamma}\Bigg{(}L-\sum_{k \in[0\ldots L-1]}r_{t}(x_{k}^{t},a_{k}^{t})+\Lambda\sum_{i\in[m]}\left[\Big{(} \widehat{G}_{t}^{j}\Big{)}^{\top}\,\widehat{q}_{t}^{j}-\alpha\right]_{i}^{+} \Bigg{)},$ (8) $$

where $\gamma$ is a suitably-defined implicit exploration factor, $(x_{k}^{t},a_{k}^{t})$ is the state-action pair visited at layer $k$ during episode $t$, $\Lambda$ is a suitably-defined upper bound on the optimal values of Lagrangian multipliers,(^4^44Notice that, in the definition of $\Lambda$, $\rho$ is the feasibility parameter of Program (6) for the reward vector $\overline{r}$, the constraint cost matrix $\overline{G}$, and the threshold vector $\alpha$. In order to compute $\Lambda$, Algorithm 3 needs knowledge of $\rho$. Nevertheless, our results continue to hold even if Algorithm 3 is only given access to a lower bound on $\rho$.) $\widehat{G}_{t}^{j}$ is the matrix of empirical constraint costs built by the instance $\texttt{Alg}^{j}$ of Algorithm 2 at episode $t$, while $\widehat{q}_{t}^{j}$ is the occupancy measure computed by instance $\texttt{Alg}^{j}$ of Algorithm 2 at $t$.
Finally, the algorithm updates the weight vector according to an FTRL update on a cut decision space with a suitable log-barrier regularization and a bonus term $b_{t}$ defined as:

$$ $b_{t,j}\coloneq\left(\left(m\Lambda\beta_{5}+\beta_{2}\right)+\left(\sqrt{ \beta_{1}}+m\Lambda\sqrt{\beta_{4}}\right)\sqrt{T}\right)(\nu_{t,j}-\nu_{t-1,j }),,$ (9) $$

where $\nu_{t,j}=\max_{\tau\leq t}\frac{1}{w_{\tau,j}}$ and the parameters $\beta$ are linked to the performance of Algorithm 2 (see Line 14 and Section F.2.1 for additional details).
See Line 15 for the complete definition of the update. The bonus term purpose is to balance out the term related to the difference between the performance of Algorithm 2 updated at each episode and the performance of its stabilized version, which works under the condition imposed by the master algorithm.

### 4.2 Theoretical guarantees of Lag-FTRL

Next, we prove the theoretical guarantees attained by Algorithm 3 (see Appendix F for complete proofs of the theorems and associated lemmas).
As a first preliminary step, we extend the well-known strong duality result for CMDPs (Altman, ) to the case of bounded Lagrangian multipliers.

###### Lemma 2 .

Given a CMDP with a transition function $P$, for every reward vector $r\in[0,1]^{|X\times A|}$, constraint cost matrix $G\in[0,1]^{|X\times A|\times m}$, and threshold vector $\alpha\in[0,L]^{m}$, if Program (6) satisfies Slater’s condition (Condition 1), then the following holds:

$$ $\displaystyle\min_{\lVert\lambda\rVert_{1}\in[0,\nicefrac{{L}}{{\rho}}]}\max_{ q\in\Delta(P)}r^{\top}q-\sum_{i\in[m]}\lambda_{i}\left[{G}^{\top}q-\alpha \right]_{i}$ $\displaystyle=\max_{q\in\Delta(P)}\min_{\lVert\lambda\rVert_{1}\in[0,\nicefrac {{L}}{{\rho}}]}r^{\top}q-\sum_{i\in[m]}\lambda_{i}\left[{G}^{\top}q-\alpha \right]_{i}$ $\displaystyle=\textnormal{OPT}_{r,G,\alpha},$ $$

where $\lambda\in\mathbb{R}^{m}_{\geq 0}$ is a vector of Lagrangian multipliers and $\rho$ is the feasibility parameter of Program (6).

Intuitively, Lemma 2 states that, under Slater’s condition, strong duality continues to hold even when restricting the set of Lagrangian multipliers to the $\lambda\in\mathbb{R}^{m}_{\geq 0}$ having $\lVert\lambda\rVert_{1}$ bounded by $\nicefrac{{L}}{{\rho}}$.
Furthermore, we extend the result in Lemma 2 to the case of a Lagrangian function suitably-modified to encompass *positive* violations.
We call it *positive Lagrangian* of Program (6), defined as follows.

###### Definition 1 (Positive Lagrangian) .

Given a CMDP with a transition function $P$, for every reward vector $r\in[0,1]^{|X\times A|}$, constraint cost matrix $G\in[0,1]^{|X\times A|\times m}$, and threshold vector $\alpha\in[0,L]^{m}$, the *positive Lagrangian* of Program (6) is defined as a function $\mathcal{L}:\mathbb{R}_{+}\times\Delta(P)\to\mathbb{R}$ such that it holds $\mathcal{L}\left(\beta,q\right)\coloneqq r^{\top}q-\beta\sum_{i\in[m]}\left[{G
}^{\top}q-\alpha\right]_{i}^{+}$ for every $\beta\geq 0$ and $q\in\Delta(P).$

The positive Lagrangian is related to the Lagrangian of a variation of Program (6) in which the $[\cdot]^{+}$ operator is applied to the constraints.
Notice that such a problem does *not* admit Slater’s condition, since, by definition of $[\cdot]^{+}$, it does *not* exist an occupancy measure $q^{\circ}$ such that $\left[{G}^{\top}q^{\circ}-\alpha\right]_{i}^{+}<0$ for every $i\in[m]$.
Nevertheless, we show that a kind of strong duality result still holds for $\mathcal{L}(\nicefrac{{L}}{{\rho}},q)$, when Slater’s condition is met by Program (6). This is done in the following result.

###### Theorem 4 .

Given a CMDP with a transition function $P$, for every reward vector $r\in[0,1]^{|X\times A|}$, constraint cost matrix $G\in[0,1]^{|X\times A|\times m}$, and threshold vector $\alpha\in[0,L]^{m}$, if Program (6) satisfies Slater’s condition (Condition 1), then the following holds:

$$ $\displaystyle\max_{q\in\Delta(P)}\mathcal{L}(\nicefrac{{L}}{{\rho}},q)=\max_{q \in\Delta(P)}r^{\top}q-\frac{L}{\rho}\sum_{i\in[m]}\left[{G}^{\top}q-\alpha \right]_{i}^{+}=\textnormal{OPT}_{r,G,\alpha},$ $$

where $\rho$ is the feasibility parameter of Program (6).

Theorem 4 intuitively shows that a $L/\rho$ multiplicative factor on the positive constraint violation is enough to compensate the large rewards that non-feasible policies would attain when employed by the learner.
This result is crucial since, without properly defining the Lagrangian function optimized by Algorithm 3, the FTRL optimization procedure would choose instances with both large rewards and large constraint violation, thus preventing the violation bound from being sublinear.

By means of Theorem 4, it is possible to provide the following result.

###### Theorem 5 .

If Program (6) instantiated with $\overline{r}$, $\overline{G}$ and $\alpha$ satisfies Slater’s condition (Condition 1), then, given any $\delta\in(0,1)$, Algorithm 3 attains the following bound with probability at least $1-34\delta$:

$$ $\displaystyle V_{T}=\mathcal{O}\bigg{(}m^{2}L^{2}|X|$ $\displaystyle\sqrt{|A|T\log\left(\nicefrac{{mT|X||A|}}{{\delta}}\right)}\log(T )^{2}$ $\displaystyle+m^{2}L|X|^{2}|A|^{2}\log(T)^{3}\log\left(\nicefrac{{\log(T)}}{{ \delta}}\right)+m^{2}L\log(T)^{2}|X||A|C\bigg{)}.$ $$

Intuitively, to prove Theorem 5, it is necessary to bound the negative regret attained by the algorithm, *i.e.*, how better Algorithm 3 can perform in terms of rewards with respect to an optimal occupancy in hindsight $q^{*}$. Notice that this is equivalent to showing that the FTRL procedure cannot gain more than $\textnormal{OPT}_{\overline{r},\overline{G},\alpha}$ by playing policies that are *not* feasible, or, equivalently, by choosing instances $\texttt{Alg}^{j}$ with a large corruption guess, which, by definition of the confidence sets employed by Algorithm 2, may play non-feasible policies attaining large rewards.
This is done by employing Theorem 4, which shows that the positive Lagrangian does *not* allow the algorithm to achieve too large rewards with respect to $q^{*}$.
Thus, the violations are still upper bounded by $\tilde{\mathcal{O}}(\sqrt{T}+C)$.

Finally, we prove the regret bound attained by Algorithm 3.

###### Theorem 6 .

If Program (6) instantiated with $\overline{r}$, $\overline{G}$ and $\alpha$ satisfies Slater’s condition (Condition 1), then, given any $\delta\in(0,1)$, Algorithm 3 attains the following bound with probability at least $1-30\delta$:

$$ $\displaystyle R_{T}=\mathcal{O}\bigg{(}m^{2}L^{2}|X|$ $\displaystyle\sqrt{|A|T\log\left(\nicefrac{{mT|X||A|}}{{\delta}}\right)}\log(T )^{2}$ $\displaystyle+m^{2}L|X|^{2}|A|^{2}\log(T)^{3}\log\left(\nicefrac{{\log(T)}}{{ \delta}}\right)+m^{2}L\log(T)^{2}|X||A|C\bigg{)}.$ $$

Bounding the regret attained by Algorithm 3 requires different techniques with respect to bounding constraint violation. Indeed, strong duality is *not* needed, since, even if $\Lambda$ is set to a too small value and thus the algorithm plays non-feasible policies, then the regret would still be sublinear.
The regret bound is strongly related to the optimal value of the problem associated with the positive Lagrangian, which, by definition of $[\cdot]^{+}$ cannot perform worse than the optimum of Program (6), in terms of rewards gained.
Thus, by letting $j^{*}$ be the index of the instance associated with true corruption value $C$, proving Theorem 6 reduces to bounding the regret and the constraint violation of instance $\texttt{Alg}^{j^{*}}$, with the additional challenge of bounding the estimation error of the optimistic loss estimator. Finally, by means of the results for the *known* $C$ case derived in Section 3, we are able to show that the regret is at most $\tilde{\mathcal{O}}(\sqrt{T}+C)$, which is the desired bound.

###### Lemma 2 .

###### Definition 1 (Positive Lagrangian) .

###### Theorem 4 .

###### Theorem 5 .

###### Theorem 6 .

## Appendix

The appendix is structured as follows:

- •
In Appendix A we provide the complete related works.
- •
In Appendix B we provide the events dictionary.
- •
In Appendix C we provide the preliminary results on the confidence sets employed to estimate the unknown parameters of the environment.
- •
In Appendix D we provide the omitted proofs related to the theoretical guarantees when the corruption value is known by the learner, namely, the results attained by Algorithm 2.
- •
In Appendix E we provide the omitted proofs of the theoretical guarantees attained by Algorithm 2, when a guess on the corruption is given as input to the algorithm.
- •
In Appendix F we provide the omitted proofs related to the theoretical guarantees when the corruption value is *not* known by the learner, namely, the results attained by Algorithm 3.
- •
In Appendix G we restate useful results from existing works.
- •
In Appendix H we provide the results related to stability a corruption-robustness.

## Appendix A Related works

In the following, we discuss some works that are tightly related to ours.
In particular, we first describe works dealing with the online learning problem in MDPs, and, then, we discuss some works studying the constrained version of the classical online learning problem.

##### Online learning in MDPs

The literature on online learning problems (Cesa-Bianchi and Lugosi, ) in MDPs is wide (see (Auer et al., ; Even-Dar et al., ; Neu et al., ) for some initial results on the topic).
In such settings, two types of feedback are usually studied: 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 and stochastic losses when the feedback is bandit.
The authors present an algorithm whose regret upper bound is $\tilde{\mathcal{O}}(\sqrt{T})$,
thus matching the lower bound for this class of MDPs and improving the previous result by Auer et al. ().

##### Online learning in non-stationary MDPs

The literature on non-stationary MDPs encompasses both works on non-stationary rewards and non-stationary transitions. As concerns the first research line,
Rosenberg and Mansour () study the online learning problem in episodic MDPs with adversarial losses and unknown transitions when the feedback is full information. 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 by Rosenberg and Mansour () when the feedback is bandit. In such a case, the authors provide 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})$. Related to the non-stationarity of the transitions , Wei et al. () study MDPs with adversarial corruption on transition functions and rewards, reaching a regret upper bound of order $\widetilde{\mathcal{O}}(\sqrt{T}+C)$ (where $C$ is the amount of adversarial corruption) with respect to the optimal policy of the non-corrupted MDP .
Finally, Jin et al. () is the first to study completely adversarial MDPs with changing transition functions, providing a $\tilde{\mathcal{O}}(\sqrt{T}+C)$ regret bounds, where $C$ is a corruption measure of the adversarially changing transition functions.

##### Online learning with constraints

A central result is provided by Mannor et al. (), who show that it is impossible to suffer from sublinear regret and sublinear constraint violation when an adversary chooses losses and constraints.
Liakopoulos et al. () try to overcome such an impossibility result by defining a new notion of regret. They study a class of online learning problems with long-term budget constraints that can be chosen by an adversary.
The learner’s regret metric is modified by introducing 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. (, ) deal with the problem of online learning with stochastic and adversarial losses, providing the first best-of-both-worlds algorithm for online learning problems with long-term constraints.

##### Online learning in CMDPs

Online Learning In MDPs with constraints is generally studied when the constraints are selected stochastically. Precisely, Zheng and Ratliff () deal with episodic CMDPs with stochastic losses and constraints, where the transition probabilities are known and the feedback is bandit. The regret upper bound of their algorithm is of the order of $\tilde{\mathcal{O}}(T^{3/4})$, while the cumulative constraint violation is guaranteed to be below a threshold with a given probability.
Wei et al. () deal with adversarial losses and stochastic constraints, assuming the transition probabilities are known and the feedback is full information. The authors present an algorithm that guarantees an upper bound of the order of $\tilde{\mathcal{O}}(\sqrt{T})$ on
both regret and constraint violation.
Bai et al. () provide the first algorithm that achieves 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. () propose two approaches
to deal with the exploration-exploitation dilemma in episodic CMDPs. These approaches guarantee sublinear regret and constraint violation when transition probabilities, rewards, and constraints are unknown and stochastic, while the feedback is bandit.
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.
Stradi et al. () is the first work to tackle CMDPs with adversarial losses and bandit feedback. They propose an algorithm which achieves sublinear regret and sublinear positive constraints violations, assuming that the constraints are stochastic.
Germano et al. () are the first to study CMDPs with adversarial constraints. Given the well-known impossibility result to learn with adversarial constraints, they propose an algorithm that attains sublinear violation (with cancellations allowed) and a fraction of the optimal reward when the feedback is full.
Finally, Ding and Lavaei () and Wei et al. () consider the case in which rewards and constraints are non-stationary, assuming that their variation is bounded, as in our work. Nevertheless, our settings differ in multiple aspects. First of all, we consider positive constraints violations, while the aforementioned works allow the cancellations in their definition.
We consider a static regret adversarial baseline, while Ding and Lavaei () and Wei et al. () consider the stronger baseline of dynamic regret. Nevertheless, our bounds are not comparable, since we achieve linear regret and violations only in the worst case scenario in which $C=T$, while a sublinear corruption would lead to linear dynamic regret in their work. Finally, we do not make any assumption on the number of episodes, while both the regret and violations bounds presented in Wei et al. () hold only for large $T$.

## Appendix B Events dictionary

In the following, we introduce the main events which are related to estimation of the unknown stochastic parameters of the environment.

- •
Event $\mathcal{E}_{P}$:
for all $t\in[T],P\in\mathcal{P}_{t}$.
$\mathcal{E}_{P}$ holds with probability at least $1-4\delta$ by Lemma 19. The event is related to the estimation of the unknown transition function.
- •
Event $\mathcal{E}_{G}$: for all $t\in[T],i\in[m],(x,a)\in X\times A$:
$\bigg{\lvert}\widehat{g}_{t,i}(x,a)-\frac{1}{T}\underset{\tau\in[T]}{\sum}
\mathbb{E}[g_{\tau,i}(x,a)]\bigg{\rvert}\leq\xi_{t}(x,a).$
Similarly,
$\bigg{\lvert}\widehat{g}_{t,i}(x,a)-g_{i}^{\circ}(x,a)\bigg{\rvert}\leq\xi_{t}
(x,a),$
where $g_{i}^{\circ}\in[0,1]^{|X\times A|}\coloneq[G^{\circ}]_{i}$.
$\mathcal{E}_{G}$ holds with probability at least $1-\delta$
by Corollary 2. The event is related to the estimation of the unknown constraint functions.
- •
Event $\mathcal{E}_{r}$: for all $t\in[T],(x,a)\in X\times A$:
$\bigg{\lvert}\widehat{r}_{t}(x,a)-\frac{1}{T}\underset{\tau\in[T]}{\sum}
\mathbb{E}[r_{\tau}(x,a)]\bigg{\rvert}\leq\phi_{t}(x,a).$
Similarly,
$\bigg{\lvert}\widehat{r}_{t}(x,a)-r^{\circ}(x,a)\bigg{\rvert}\leq\phi_{t}(x,a).$
$\mathcal{E}_{r}$ holds with probability at least $1-\delta$
by Corollary 4. The event is related to the estimation of the unknown reward function.
- •
Event $\mathcal{E}_{\widehat{q}\ }$: for any $P_{t}^{x}\in\mathcal{P}_{t}$:
$\sum_{t\in[T]}\sum_{x\in X,a\in A}\left|q^{P_{t}^{x},\pi_{t}}(x,a)-q_{t}(x,a)
\right|\leq\mathcal{O}\left(L|X|\sqrt{|A|T\ln\left(\frac{T|X||A|}{\delta}
\right)}\right).$
$\mathcal{E}_{\widehat{q}\ }$ holds with probability at least $1-6\delta$
by Lemma 20. The event is related to the convergence to the true unknown occupancy measure. Notice that $\mathbb{P}\left[\mathcal{E}_{\widehat{q}\ }\cap\mathcal{E}_{P}\right]\geq 1-6\delta$ by construction.

## Appendix C Confidence intervals

In this section we will provide the preliminary results related to the high probability confidence sets for the estimation of the cost constraints matrices and the reward vectors.

We start bounding the distance between the *non-corrupted* costs and rewards with respect to the mean of the adversarial distributions.

###### Lemma 3 .

For all $i\in[m]$, fixing $(x,a)\in X\times A$, it holds:

$$ $\bigg{\lvert}{g}_{i}^{\circ}(x,a)-\frac{1}{T}\underset{t\in[T]}{\sum}\mathbb{E }[g_{t,i}(x,a)]\bigg{\rvert}\leq\frac{C_{G}}{T}.$ $$

Similarly, fixing $(x,a)\in X\times A$, it holds:

$$ $\bigg{\lvert}{r}^{\circ}(x,a)-\frac{1}{T}\underset{t\in[T]}{\sum}\mathbb{E}[r_ {t}(x,a)]\bigg{\rvert}\leq\frac{C_{r}}{T},$ $$

###### Proof.

By triangle inequality and from the definition of $C_{G}$, it holds:

$$ $\displaystyle\bigg{|}g^{\circ}_{i}(x,a)-\frac{1}{T}\underset{t\in[T]}{\sum} \mathbb{E}[g_{t,i}(x,a)]\bigg{|}$ $\displaystyle=\bigg{|}\frac{1}{T}\underset{t\in[T]}{\sum}(g^{\circ}_{i}(x,a)- \mathbb{E}[g_{t,i}(x,a)])\bigg{|}$ $\displaystyle\leq\frac{1}{T}\underset{t\in[T]}{\sum}\bigg{|}g^{\circ}_{i}(x,a) -\mathbb{E}[g_{t,i}(x,a)]\bigg{|}$ $\displaystyle\leq\frac{C_{G}}{T}.$ $$

Notice that the proof holds for all $i\in[m]$ since $C_{G}$ is defined employing the maximum over $i\in[m]$.
Following the same steps, it holds:

$$ $\displaystyle\left|r^{\circ}(x,a)-\frac{1}{T}\underset{t\in[T]}{\sum}\mathbb{E }[r_{t}(x,a)]\right|$ $\displaystyle=\left|\frac{1}{T}\underset{t\in[T]}{\sum}(r^{\circ}(x,a)-\mathbb {E}[r_{t}(x,a)])\right|$ $\displaystyle\leq\frac{1}{T}\underset{t\in[T]}{\sum}\bigg{|}r^{\circ}(x,a)- \mathbb{E}[r_{t}(x,a)]\bigg{|}$ $\displaystyle\leq\frac{C_{r}}{T},$ $$

which concludes the proof.
∎

In the following lemma, we bound the distance between the empirical mean of the constraints function and the true *non-corrupted* value.

###### Lemma 4 .

Fixing $i\in[m]$, $(x,a)\in X\times A$ , $t\in[T]$, for any $\delta\in(0,1)$, it holds with probability at least $1-\delta$:

$$ $\bigg{\lvert}\widehat{g}_{t,i}(x,a)-g^{\circ}_{i}(x,a)\bigg{\rvert}\leq\sqrt{ \frac{1}{2\max\{N_{t}(x,a),1\}}\ln\left(\frac{2}{\delta}\right)}+\frac{C_{G}}{ \max\{N_{t}(x,a),1\}}.$ $$

###### Proof.

We start bounding the quantity of interest as follows:

$$ $\displaystyle\bigg{|}\widehat{g}_{t,i}(x,a)-g^{\circ}_{i}(x,a)\bigg{|}$ $\displaystyle=\left|\left(\frac{\sum_{\tau\in[t]}\mathbb{I}_{\tau}(x,a)g_{\tau ,i}(x,a)}{\max\{N_{t}(x,a),1\}}\right)-g^{\circ}_{i}(x,a)\right|$ $\displaystyle\leq\left|\frac{1}{\max\{N_{t}(x,a),1\}}\underset{\tau\in[t]}{ \sum}\mathbb{I}_{\tau}(x,a)\left(g_{\tau,i}(x,a)-\mathbb{E}[g_{\tau,i}(x,a)] \right)\right|$ $\displaystyle\ \ +\left|\frac{1}{\max\{N_{t}(x,a),1\}}\underset{\tau\in[t]}{ \sum}\mathbb{I}_{\tau}(x,a)[\mathbb{E}[g_{\tau,i}(x,a)]-g^{\circ}_{i}(x,a)] \right|,$ (10) $$

where we employed the triangle inequality and the definition of $\widehat{g}_{t,i}(x,a)$.

We bound the two terms in Equation (10) separately.
For the first term, by Hoeffding’s inequality and noticing that constraints values are bounded in $[0,1]$, it holds that:

$$ $\mathbb{P}\left[\mathcal{A}\geq\frac{c}{\max\{N_{t}(x,a),1\}}\right]\leq 2\exp \Bigg{(}-\frac{2c^{2}}{\max\{N_{t}(x,a),1\}}\Bigg{)},$ $$

where,

$$ $\mathcal{A}=\left|\left(\frac{\sum_{\tau\in[t]}\mathbb{I}_{\tau}(x,a)g_{\tau,i }(x,a)}{\max\{N_{t}(x,a),1\}}\right)-\left(\frac{\sum_{\tau\in[t]}\mathbb{I}_{ \tau}(x,a)\mathbb{E}[g_{\tau,i}(x,a)]}{\max\{N_{t}(x,a),1\}}\right)\right|,$ $$

Setting $\delta=2\exp\left(-\frac{2c^{2}}{\max\{N_{t}(x,a),1\}}\right)$ and solving to find a proper value of $c$ we get that with probability at least $1-\delta$:

$$ $\left|\frac{1}{\max\{N_{t}(x,a),1\}}\underset{\tau\in[t]}{\sum}\mathbb{I}_{ \tau}(x,a)\left(g_{\tau,i}(x,a)-\mathbb{E}[g_{\tau,i}(x,a)]\right)\right|\leq \sqrt{\frac{1}{2\max\{N_{t}(x,a),1\}}\ln\left(\frac{2}{\delta}\right)}.$ $$

Finally, we focus on the second term. Thus, employing the triangle inequality and the definition of $C_{G}$, it holds:

$$ $\displaystyle\Bigg{|}\frac{1}{\max\{N_{t}(x,a),1\}}\underset{\tau\in[t]}{\sum} \mathbb{I}_{\tau}(x,a)$ $\displaystyle\left[\mathbb{E}[g_{\tau,i}(x,a)]-g^{\circ}_{i}(x,a)\right]\Bigg{|}$ $\displaystyle\leq\frac{1}{\max\{N_{t}(x,a),1\}}\underset{\tau\in[t]}{\sum} \mathbb{I}_{\tau}(x,a)\bigg{|}\mathbb{E}[g_{\tau,i}(x,a)]-g^{\circ}_{i}(x,a) \bigg{|}$ $\displaystyle\leq\frac{1}{\max\{N_{t}(x,a),1\}}\underset{\tau\in[T]}{\sum} \bigg{|}\mathbb{E}[g_{\tau,i}(x,a)]-g^{\circ}_{i}(x,a)\bigg{|}$ $\displaystyle\leq\frac{C_{G}}{\max\{N_{t}(x,a),1\}},$ $$

which concludes the proof.
∎

We now prove a similar result for the rewards function.

###### Lemma 5 .

Fixing $(x,a)\in X\times A$ , $t\in[T]$, for any $\delta\in(0,1)$, it holds with probability at least $1-\delta$:

$$ $\bigg{\lvert}\widehat{r}_{t}(x,a)-r^{\circ}(x,a)\bigg{\rvert}\leq\sqrt{\frac{1 }{2\max\{N_{t}(x,a),1\}}\ln\left(\frac{2}{\delta}\right)}+\frac{C_{r}}{\max\{N _{t}(x,a),1\}}.$ $$

###### Proof.

The proof is analogous to the one of Lemma 4.
∎

We now generalize the previous results as follows.

###### Lemma 6 .

Given any $\delta\in(0,1)$, for any $(x,a)\in X\times A,t\in[T],$ and $i\in[m]$, it holds with probability at least $1-\delta$:

$$ $\bigg{\lvert}\widehat{g}_{t,i}(x,a)-g^{\circ}_{i}(x,a)\bigg{\rvert}\leq\sqrt{ \frac{1}{2\max\{N_{t}(x,a),1\}}\ln\left(\frac{2mT|X||A|}{\delta}\right)}+\frac {C_{G}}{\max\{N_{t}(x,a),1\}}.$ $$

###### Proof.

First let’s define $\zeta_{t}(x,a)$ as:

$$ $\zeta_{t}(x,a):=\sqrt{\frac{1}{2\max\{N_{t}(x,a),1\}}\ln\left(\frac{2}{\delta} \right)}+\frac{C_{G}}{\max\{N_{t}(x,a),1\}}.$ $$

From Lemma 4, given $\delta^{\prime}\in(0,1)$, we have, fixed any $i\in[m]$, $t\in[T]$ and $(x,a)\in X\times A$:

$$ $\mathbb{P}\Bigg{[}\bigg{\lvert}\widehat{g}_{t,i}(x,a)-g^{\circ}_{i}(x,a)\bigg{ \rvert}\leq\zeta_{t}(x,a)\Bigg{]}\geq 1-\delta^{\prime}.$ $$

Now, we are interested in the intersection of all the events, namely,

$$ $\mathbb{P}\Bigg{[}\bigcap_{x,a,i,t}\Big{\{}\Big{|}\widehat{g}_{t,i}(x,a)-g^{ \circ}_{i}(x,a)\Big{|}\leq\zeta_{t}(x,a)\Big{\}}\Bigg{]}.$ $$

Thus, we have:

$$ $\displaystyle\mathbb{P}\Bigg{[}\bigcap_{x,a,i,t}\Big{\{}\Big{|}\widehat{g}_{t, i}(x,a)-g^{\circ}_{i}(x,a)$ $\displaystyle\Big{|}\leq\zeta_{t}(x,a)\Big{\}}\Bigg{]}$ $\displaystyle=1-\mathbb{P}\Bigg{[}\bigcup_{x,a,i,t}\Big{\{}\Big{|}\widehat{g}_ {t,i}(x,a)-g^{\circ}_{i}(x,a)\Big{|}\leq\zeta_{t}(x,a)\Big{\}}^{c}\Bigg{]}$ $\displaystyle\geq 1-\sum_{x,a,i,t}\mathbb{P}\Bigg{[}\Big{\{}\Big{|}\widehat{g} _{t,i}(x,a)-g^{\circ}_{i}(x,a)\Big{|}\leq\zeta_{t}(x,a)\Big{\}}^{c}\Bigg{]}$ (11) $\displaystyle\geq 1-|X||A|mT\delta^{\prime},$ $$

where Inequality (11) holds by Union Bound. Noticing that $g_{t,i}(x,a)\leq 1$, substituting $\delta^{\prime}$ with $\delta:=\delta^{\prime}/|X||A|mT$ in $\zeta_{t}(x,a)$ with an additional Union Bound over the possible values of $N_{t}(x,a)$, we have, with probability at least $1-\delta$:

$$ $\bigg{\lvert}\widehat{g}_{t,i}(x,a)-g^{\circ}_{i}(x,a)\bigg{\rvert}\leq\sqrt{ \frac{1}{2\max\{N_{t}(x,a),1\}}\ln\left(\frac{2mT|X||A|}{\delta}\right)}+\frac {C_{G}}{\max\{N_{t}(x,a),1\}},$ $$

which concludes the proof.
∎

We provide a similar result for the rewards function.

###### Lemma 7 .

Given any $\delta\in(0,1)$, for any $(x,a)\in X\times A,t\in[T],$ it holds with probability at least $1-\delta$:

$$ $\bigg{\lvert}\widehat{r}_{t}(x,a)-r^{\circ}(x,a)\bigg{\rvert}\leq\sqrt{\frac{1 }{2\max\{N_{t}(x,a),1\}}\ln\left(\frac{2T|X||A|}{\delta}\right)}+\frac{C_{r}}{ \max\{N_{t}(x,a),1\}}.$ $$

###### Proof.

First let’s define $\psi_{t}(x,a)$ as:

$$ $\psi_{t}(x,a):=\sqrt{\frac{1}{2\max\{N_{t}(x,a),1\}}\ln\left(\frac{2}{\delta} \right)}+\frac{C_{r}}{\max\{N_{t}(x,a),1\}}.$ $$

From Lemma 5, given $\delta^{\prime}\in(0,1)$, we have fixed any $t\in[T]$ and $(x,a)\in X\times A$:

$$ $\mathbb{P}\Bigg{[}\bigg{\lvert}\widehat{r}_{t}(x,a)-r^{\circ}(x,a)\bigg{\rvert }\leq\psi_{t}(x,a)\Bigg{]}\geq 1-\delta^{\prime}.$ $$

Now, we are interested in the intersection of all the events, namely,

$$ $\mathbb{P}\Bigg{[}\bigcap_{x,a,t}\Big{\{}\Big{|}\widehat{r}_{t}(x,a)-r^{\circ} (x,a)\Big{|}\leq\psi_{t}(x,a)\Big{\}}\Bigg{]}.$ $$

Thus, we have:

$$ $\displaystyle\mathbb{P}\Bigg{[}\bigcap_{x,a,t}\Big{\{}\Big{|}\widehat{r}_{t}(x ,a)-r^{\circ}(x,a)$ $\displaystyle\Big{|}\leq\psi_{t}(x,a)\Big{\}}\Bigg{]}$ $\displaystyle=1-\mathbb{P}\Bigg{[}\bigcup_{x,a,t}\Big{\{}\Big{|}\widehat{r}_{t }(x,a)-r^{\circ}(x,a)\Big{|}\leq\psi_{t}(x,a)\Big{\}}^{c}\Bigg{]}$ $\displaystyle\geq 1-\sum_{x,a,t}\mathbb{P}\Bigg{[}\Big{\{}\Big{|}\widehat{r}_{ t}(x,a)-r^{\circ}(x,a)\Big{|}\leq\psi_{t}(x,a)\Big{\}}^{c}\Bigg{]}$ (12) $\displaystyle\geq 1-|X||A|T\delta^{\prime},$ $$

where Inequality (12) holds by Union Bound. Noticing that $r_{t}(x,a)\leq 1$, substituting $\delta^{\prime}$ with $\delta:=\delta^{\prime}/|X||A|T$ in $\psi_{t}(x,a)$ with an additional Union Bound over the possible values of $N_{t}(x,a)$, we have, with probability at least $1-\delta$:

$$ $\bigg{\lvert}\widehat{r}_{t}(x,a)-r^{\circ}(x,a)\bigg{\rvert}\leq\sqrt{\frac{1 }{2\max\{N_{t}(x,a),1\}}\ln\left(\frac{2T|X||A|}{\delta}\right)}+\frac{C_{r}}{ \max\{N_{t}(x,a),1\}},$ $$

which concludes the proof.
∎

In the following, we bound the distance between the empirical estimation of the constraints and the empirical mean of the mean values of the constraints distribution during the learning dynamic.

###### Lemma 8 .

Given $\delta\in(0,1)$, for all episodes $t\in[T]$, state-action pairs $(x,a)\in X\times A$ and constraint $i\in[m]$,it holds, with probability at least $1-\delta$:

$$ $\bigg{\lvert}\widehat{g}_{t,i}(x,a)-\frac{1}{T}\underset{\tau\in[T]}{\sum} \mathbb{E}[g_{\tau,i}(x,a)]\bigg{\rvert}\leq\xi_{t}(x,a),$ $$

where,

$$ $\xi_{t}(x,a):=\min\left\{1,\sqrt{\frac{1}{2\max\{N_{t}(x,a),1\}}\ln\left(\frac {2mT|X||A|}{\delta}\right)}+\frac{C_{G}}{\max\{N_{t}(x,a),1\}}+\frac{C_{G}}{T} \right\}.$ $$

###### Proof.

We first notice that if $\xi_{t}(x,a)=1$, the results is derived trivially by definition on the cost function.
We prove now the non trivial case $\sqrt{\frac{1}{2\max\{N_{t}(x,a),1\}}\ln\left(\frac{2mT|X||A|}{\delta}\right)}
+\frac{C_{G}}{\max\{N_{t}(x,a),1\}}+\frac{C_{G}}{T}\leq 1$.
Employing Lemma 3 and Lemma 6, with probability $1-\delta$ for all $(x,a)\in X\times A$, for all $t\in[T]$ and for all $i\in[m]$, it holds that:

$$ $\displaystyle\Bigg{|}\widehat{g}_{t,i}(x,a)-\frac{1}{T}$ $\displaystyle\underset{\tau\in[T]}{\sum}\mathbb{E}[g_{\tau,i}(x,a)]\Bigg{|}$ $\displaystyle\leq\Bigg{\lvert}\widehat{g}_{t,i}(x,a)-g^{\circ}_{i}(x,a)\Bigg{ \rvert}+\Bigg{\lvert}{g}^{\circ}_{i}(x,a)-\frac{1}{T}\underset{t\in[T]}{\sum} \mathbb{E}[g_{t,i}(x,a)]\Bigg{\rvert}$ $\displaystyle\leq\sqrt{\frac{1}{2\max\{N_{t}(x,a),1\}}\ln\left(\frac{2mT|X||A| }{\delta}\right)}+\frac{C_{G}}{\max\{N_{t}(x,a),1\}}+\frac{C_{G}}{T},$ $$

where the first inequality follows from the triangle inequality. This concludes the proof.
∎

For the sake of simplicity, we analyze our algorithm with respect to the total corruption of the environment, defined as the maximum between the reward and the constraints corruption. In the following, we show that this choice does not prevent the confidence set events from holding.

###### Corollary 1 .

Given a corruption guess $\widehat{C}\geq C_{G}$ and $\delta\in(0,1)$, for all episodes $t\in[T]$, state-action pairs $(x,a)\in X\times A$ and constraint $i\in[m]$, with probability at least $1-\delta$, it holds:

$$ $\bigg{\lvert}\widehat{g}_{t,i}(x,a)-\frac{1}{T}\underset{\tau\in[T]}{\sum} \mathbb{E}[g_{\tau,i}(x,a)]\bigg{\rvert}\leq\xi_{t}(x,a),$ $$

where,

$$ $\xi_{t}(x,a)=\min\left\{1,\sqrt{\frac{1}{2\max\{N_{t}(x,a),1\}}\ln\left(\frac{ 2mT|X||A|}{\delta}\right)}+\frac{\widehat{C}}{\max\{N_{t}(x,a),1\}}+\frac{ \widehat{C}}{T}\right\}.$ $$

###### Proof.

Following the same analysis of Lemma 8 for $\widehat{C}\geq C_{G}$, it holds

$$ $\displaystyle\bigg{\lvert}\widehat{g}_{t,i}(x,a)-$ $\displaystyle\frac{1}{T}\underset{\tau\in[T]}{\sum}\mathbb{E}[g_{\tau,i}(x,a)] \bigg{\rvert}$ $\displaystyle\leq\sqrt{\frac{1}{2\max\{N_{t}(x,a),1\}}\ln\left(\frac{2mT|X||A| }{\delta}\right)}+\frac{C_{G}}{\max\{N_{t}(x,a),1\}}+\frac{C_{G}}{T}$ $\displaystyle\leq\sqrt{\frac{1}{2\max\{N_{t}(x,a),1\}}\ln\left(\frac{2mT|X||A| }{\delta}\right)}+\frac{\widehat{C}}{\max\{N_{t}(x,a),1\}}+\frac{\widehat{C}}{ T},$ $$

which concludes the proof.
∎

###### Corollary 2 .

Taking the definition of $\xi_{t}$ employed in Lemma 8
and defining $\mathcal{E}_{G}$ as the intersection event:

$$ $\displaystyle\mathcal{E}_{G}:=\bigg{\{}$ $\displaystyle\big{\lvert}\widehat{g}_{t,i}(x,a)-g^{\circ}_{i}(x,a)\big{\rvert} \leq\xi_{t}(x,a),~{}\forall(x,a)\in X\times A,\forall t\in[T],\forall i\in[m] \bigg{\}}\quad\bigcap$ $\displaystyle\left\{\bigg{|}\widehat{g}_{t,i}(x,a)-\frac{1}{T}\underset{\tau \in[T]}{\sum}\mathbb{E}[g_{\tau,i}(x,a)]\bigg{|}\leq\xi_{t}(x,a),~{}\forall(x, a)\in X\times A,\forall t\in[T],\forall i\in[m]\right\},$ $$

it holds that $\mathbb{P}[\mathcal{E}_{G}]\geq 1-\delta.$

Notice that by Corollary 1, $\mathcal{E}_{G}$ includes all the analogous events where $\xi_{t}$ is built employing an arbitrary adversarial corruption $\widehat{C}$ such that $\widehat{C}\geq C_{G}$.

In the following, we provide similar results for the reward function.

###### Lemma 9 .

Given $\delta\in(0,1)$, for all episodes $t\in[T]$ and for all state-action pairs $(x,a)\in X\times A$, with probability at least $1-\delta$, it holds:

$$ $\left\lvert\widehat{r}_{t}(x,a)-\frac{1}{T}\underset{\tau\in[T]}{\sum}\mathbb{ E}[r_{\tau}(x,a)]\right\rvert\leq\phi_{t}(x,a),$ $$

where,

$$ $\phi_{t}(x,a):=\min\left\{1,\sqrt{\frac{1}{2\max\{N_{t}(x,a),1\}}\ln\left( \frac{2T|X||A|}{\delta}\right)}+\frac{C_{r}}{\max\{N_{t}(x,a),1\}}+\frac{C_{r} }{T}\right\}.$ $$

###### Proof.

Employing Lemma 3 and Lemma 7, with probability at least $1-\delta$, for all $(x,a)\in X\times A$ and for all $t\in[T]$, it holds:

$$ $\displaystyle\bigg{|}\widehat{r}_{t}(x,a)-\frac{1}{T}\underset{\tau\in[T]}{ \sum}\mathbb{E}$ $\displaystyle[r_{\tau}(x,a)]\bigg{|}$ $\displaystyle\leq\bigg{\lvert}\widehat{r}_{t}(x,a)-r^{\circ}(x,a)\bigg{\rvert} +\bigg{\lvert}{r}^{\circ}(x,a)-\frac{1}{T}\underset{t\in[T]}{\sum}\mathbb{E}[r _{t}(x,a)]\bigg{\rvert}$ $\displaystyle\leq\sqrt{\frac{1}{2\max\{N_{t}(x,a),1\}}\ln\left(\frac{2T|X||A|} {\delta}\right)}+\frac{C_{r}}{\max\{N_{t}(x,a),1\}}+\frac{C_{r}}{T},$ $$

where the first inequality follows from the triangle inequality. Noticing that, by construction,

$$ $\bigg{|}\widehat{r}_{t}(x,a)-\frac{1}{T}\underset{\tau\in[T]}{\sum}\mathbb{E}[ r_{\tau}(x,a)]\bigg{|}\leq 1,$ $$

for all episodes $t\in[T]$ and $(x,a)\in X\times A$ concludes the proof.
∎

We conclude the section, showing the overestimating the reward corruption does not invalidate the confidence set estimation.

###### Corollary 3 .

Given a corruption guess $\widehat{C}\geq C_{r}$ and $\delta\in(0,1)$, for all episodes $t\in[T]$ and for all state-action pairs $(x,a)\in X\times A$, with probability at least $1-\delta$, it holds:

$$ $\bigg{\lvert}\widehat{r}_{t}(x,a)-\frac{1}{T}\underset{\tau\in[T]}{\sum} \mathbb{E}[r_{\tau}(x,a)]\bigg{\rvert}\leq\phi_{t}(x,a),$ $$

where,

$$ $\phi_{t}(x,a):=\min\left\{1,\sqrt{\frac{1}{2\max\{N_{t}(x,a),1\}}\ln\left( \frac{2T|X||A|}{\delta}\right)}+\frac{\widehat{C}}{\max\{N_{t}(x,a),1\}}+\frac {\widehat{C}}{T}\right\}.$ $$

###### Proof.

The proof is analogous to the one of Corollary 1.
∎

###### Corollary 4 .

Taking the definition of $\phi_{t}$ employed in Lemma 9
and defining $\mathcal{E}_{r}$ as the intersection event:

$$ $\displaystyle\mathcal{E}_{r}:=\bigg{\{}\big{\lvert}\widehat{r}_{t}(x,a)-$ $\displaystyle r^{\circ}(x,a)\big{\rvert}\leq\phi_{t}(x,a),~{}\forall(x,a)\in X \times A,\forall t\in[T]\bigg{\}}\quad\bigcap$ $\displaystyle\left\{\bigg{|}\widehat{r}_{t}(x,a)-\frac{1}{T}\underset{\tau\in[ T]}{\sum}\mathbb{E}[r_{\tau}(x,a)]\bigg{|}\leq\phi_{t}(x,a),~{}\forall(x,a)\in X \times A,\forall t\in[T]\right\},$ $$

it holds that $\mathbb{P}[\mathcal{E}_{r}]\geq 1-\delta.$

Notice that by Corollary 3, $\mathcal{E}_{r}$ includes all the analogous events where $\phi_{t}$ is built employing an arbitrary adversarial corruption $\widehat{C}$ such that $\widehat{C}\geq C_{r}$.

###### Lemma 3 .

###### Proof.

###### Lemma 4 .

###### Proof.

###### Lemma 5 .

###### Proof.

###### Lemma 6 .

###### Proof.

###### Lemma 7 .

###### Proof.

###### Lemma 8 .

###### Proof.

###### Corollary 1 .

###### Proof.

###### Corollary 2 .

###### Lemma 9 .

###### Proof.

###### Corollary 3 .

###### Proof.

###### Corollary 4 .

## Appendix D Omitted proofs when the corruption is known

In the following, we provide the main results attained by Algorithm 2 in term of regret and constraints violations. The following results hold when the corruption of the environment is known to the learner.

We start providing a preliminary result, which shows that the linear program solved by Algorithm 2 at each $t\in[T]$ admits a feasible solution, with high probability.

###### Lemma 10 .

For any $\delta\in(0,1)$, for all episodes $t\in[T]$, with probability at least $1-5\delta$, the space defined by linear constraints $\left\{q\in\Delta(\mathcal{P}_{t}):\underline{G}_{t}^{\top}q\leq\alpha\right\}$ admits a feasible solution and it holds:

$$ $\left\{q\in\Delta(P):\overline{G}^{\top}q\leq\alpha\right\}\subseteq\left\{q \in\Delta(\mathcal{P}_{t}):\underline{G}_{t}^{\top}q\leq\alpha\right\}.$ $$

###### Proof.

Under the event $\mathcal{E}_{P}$, we have that $\Delta(P)\subseteq\Delta(\mathcal{P}_{t})$, for all episodes $t\in[T]$. Similarly, under the event $\mathcal{E}_{G}$, it holds that $\left\{q:\frac{1}{T}\underset{t\in[T]}{\sum}\mathbb{E}[G_{t}]^{\top}q\leq
\alpha\right\}\subseteq\left\{q:\underline{G}_{t}^{\top}q\leq\alpha\right\}$. This implies that any feasible solution of the offline problem, is included in the optimistic safe set $\left\{q\in\Delta(\mathcal{P}_{t}):\underline{G}_{t}^{\top}q\leq\alpha\right\}$.
Taking the intersection event $\mathcal{E}_{P}\cap\mathcal{E}_{G}$ concludes the proof.
∎

We are now ready to provide the violation bound attained by Algorithm 2.
See 2

###### Proof.

In the following, we will refer as $\mathcal{E}_{\widehat{q}\ }$ to the event described in Lemma 20, which holds with probability at least $1-6\delta$ .
Thus, under $\mathcal{E}_{G}\cap\mathcal{E}_{\widehat{q}\ }$, the linear program solved by Algorithm 2 has a feasible solution (see Lemma 10) and it holds:

$$ $\displaystyle V_{T}$ $\displaystyle=\underset{i\in[m]}{\max}\underset{t\in[T]}{\sum}\left[\mathbb{E} [G_{t}]^{\top}q_{t}-\alpha\right]_{i}^{+}$ $\displaystyle=\underset{i\in[m]}{\max}\underset{t\in[T]}{\sum}\left[\left( \mathbb{E}[g_{t,i}]-g^{\circ}_{i}\right)^{\top}q_{t}+g^{\circ}_{i}{}^{\top}q_{ t}-\alpha_{i}\right]^{+}$ $\displaystyle\leq\underset{i\in[m]}{\max}\underset{t\in[T]}{\sum}\left[\left( \mathbb{E}[g_{t,i}]-g^{\circ}_{i}\right)^{\top}q_{t}+\left(\underline{g}_{t-1, i}+2\xi_{t-1}\right)^{\top}q_{t}-\alpha_{i}\right]^{+}$ (13a) $\displaystyle=\underset{i\in[m]}{\max}\underset{t\in[T]}{\sum}\left[\left( \mathbb{E}[g_{t,i}]-g^{\circ}_{i}\right)^{\top}q_{t}+\underline{g}_{t-1,i}^{ \top}\left(q_{t}-\widehat{q}_{t}\right)+\underline{g}_{t-1,i}^{\top}\widehat{q }_{t}+2\xi_{t-1}^{\top}q_{t}-\alpha_{i}\right]^{+}$ $\displaystyle\leq\underset{i\in[m]}{\max}\underset{t\in[T]}{\sum}\left[\left( \mathbb{E}[g_{t,i}]-g^{\circ}_{i}\right)^{\top}q_{t}+\underline{g}_{t-1,i}^{ \top}\left(q_{t}-\widehat{q}_{t}\right)+2\xi_{t-1}^{\top}q_{t}\right]^{+}$ (13b) $\displaystyle\leq\underset{i\in[m]}{\max}\underset{t\in[T]}{\sum}\left|\left( \mathbb{E}[g_{t,i}]-g^{\circ}_{i}\right)^{\top}q_{t}\right|+2\underset{i\in[m] }{\max}\underset{t\in[T]}{\sum}\left|\xi_{t-1}^{\top}q_{t}\right|+\underset{i \in[m]}{\max}\underset{t\in[T]}{\sum}\left|\underline{g}_{t-1,i}^{\top}\left(q _{t}-\widehat{q}_{t}\right)\right|$ (13c) $\displaystyle\leq\underset{i\in[m]}{\max}\underset{t\in[T]}{\sum}\left\lVert \mathbb{E}[g_{t,i}]-g^{\circ}_{i}\right\rVert_{1}+2\underset{i\in[m]}{\max} \underset{t\in[T]}{\sum}\xi_{t-1}^{\top}q_{t}+\underset{i\in[m]}{\max} \underset{t\in[T]}{\sum}\left\lVert q_{t}-\widehat{q}_{t}\right\rVert_{1}$ (13d) $\displaystyle\leq C_{G}+2\underset{i\in[m]}{\max}\underset{t\in[T]}{\sum}\xi_{ t-1}^{\top}q_{t}+\underset{t\in[T]}{\sum}\lVert q_{t}-\widehat{q}_{t}\rVert_{1},$ (13e) $$

where Inequality (13a) follows from Corollary 2, Inequality (13b) holds since Algorithm 2 ensures, for all $t\in[T]$ and for all $i\in[m]$, that $\underline{g}_{t,i}^{\top}\widehat{q}_{t}\leq\alpha_{i}$, Inequality (13c) holds since $[a+b]^{+}\leq|a|+|b|$, for all $a,b\in\mathbb{R}$, Inequality (13d) follows from Hölder inequality since $||\underline{g}_{t,i}(x,a)||_{\infty}\leq 1$ and $||q_{t}(x,a)||_{\infty}\leq 1$, and finally Equation (13e) holds for the definition of $C_{G}$.

To bound the last term of Equation (13e), we notice that, under $\mathcal{E}_{\widehat{q}}$, by Lemma 20, it holds:

$$ $\underset{t\in[T]}{\sum}\lVert q_{t}-\widehat{q}_{t}\rVert_{1}=\mathcal{O} \left(L|X|\sqrt{|A|T\ln\left(\frac{T|X||A|}{\delta}\right)}\right).$ $$

To bound the second term of Equation (13e) we proceed as follows. Under $\mathcal{E}_{\widehat{q}}$ ,with probability at least $1-\delta$, it holds:

$$ $\displaystyle\sum_{t\in[T]}\xi_{t-1}^{\top}q_{t}\leq\sum_{t\in[T]}\sum_{x,a} \xi_{t-1}(x,a)\mathbb{I}_{t}(x,a)+L\sqrt{2T\ln\frac{1}{\delta}}$ (14a) $\displaystyle\leq\underset{x,a}{\sum}\underset{t\in[T]}{\sum}\mathbb{I}_{t}(x, a)\Bigg{(}\sqrt{\frac{1}{2\max\{N_{t-1}(x,a),1\}}\ln\left(\frac{2mT|X||A|}{ \delta}\right)}+$ $\displaystyle\mkern 180.0mu+\frac{C_{G}}{\max\{N_{t-1}(x,a),1\}}+\frac{C_{G}}{ T}\Bigg{)}+L\sqrt{2T\ln\frac{1}{\delta}}$ (14b) $\displaystyle\leq\sqrt{\frac{1}{2}\ln\left(\frac{2mT|X||A|}{\delta}\right)} \underset{x,a}{\sum}\underset{t\in[T]}{\sum}\mathbb{I}_{t}(x,a)\sqrt{\frac{1}{ \max\{N_{t-1}(x,a),1\}}}+$ $\displaystyle\mkern 180.0mu+C_{G}\underset{x,a}{\sum}{\sum_{t\in[T]}}\left( \frac{\mathbb{I}_{t}(x,a)}{\max\{N_{t-1}(x,a),1\}}+\frac{1}{T}\right)+L\sqrt{2 T\ln\frac{1}{\delta}}$ $\displaystyle\leq 3\sqrt{\frac{1}{2}|X||A|LT\ln\left(\frac{2mT|X||A|}{\delta} \right)}+|X||A|(2+\ln(T))C_{G}+|X||A|C_{G}+L\sqrt{2T\ln\frac{1}{\delta}}$ (14c) $\displaystyle\leq 3\sqrt{\frac{1}{2}|X||A|LT\ln\left(\frac{2mT|X||A|}{\delta} \right)}+(3+\ln(T))|X||A|C_{G}+L\sqrt{2T\ln\frac{1}{\delta}}$ $\displaystyle=\mathcal{O}\left(\sqrt{|X||A|LT\ln\left(\frac{mT|X||A|}{\delta} \right)}+\ln(T)|X||A|C_{G}\right),$ $$

where Inequality (14a) follows from the Azuma-Hoeffding inequality and noticing that $\sum_{x,a}\xi_{t-1}(x,a)q_{t}(x,a)\leq L$, Equality (14b) follows from the definition of $\xi_{t}$ and finally,
Inequality (14c) holds since $1+\sum_{t=1}^{N_{T}(x,a)}\sqrt{\frac{1}{t}}\leq 1+2\sqrt{N_{T}(x,a)}\leq 3
\sqrt{N_{T}(x,a)}$ , since $1+\sum_{t=1}^{N_{T}(x,a)}\frac{1}{t}\leq 2+\ln(T)$ and by Cauchy-Schwarz inequality.
Finally, we notice that the intersection event $\mathcal{E}_{G}\cap\mathcal{E}_{\widehat{q}\ }\cap\mathcal{E}_{\text{Azuma}}$ holds with the following probability,

$$ $\displaystyle\mathbb{P}\left[\mathcal{E}_{G}\cap\mathcal{E}_{\widehat{q}\ } \cap\mathcal{E}_{\text{Azuma}}\right]$ $\displaystyle=1-\mathbb{P}\left[\mathcal{E}_{G}^{C}\cup\mathcal{E}_{\widehat{q }\ }^{C}\cup\mathcal{E}_{\text{Azuma}}^{C}\right]$ $\displaystyle\geq 1-\left(\mathbb{P}\left[\mathcal{E}_{G}^{C}\right]+\mathbb{P }\left[\mathcal{E}_{\widehat{q}\ }^{C}\right]+\mathbb{P}\left[\mathcal{E}_{ \text{Azuma}}^{C}\right]\right)$ $\displaystyle\geq 1-8\delta.$ $$

Noticing that, by Corollary 1, what holds for a $\xi_{t}$ built with corruption value $C_{G}$, still holds for a higher corruption (by definition, $C\geq C_{G}$) concludes the proof.
∎

We conclude the section providing the regret bound attained by Algorithm 2.
See 3

###### Proof.

First, we notice that under the event $\mathcal{E}_{r}$ it holds that, for all $(x,a)\in X\times A$ and for all $t\in[T]$:

$$ $\overline{r}_{t}(x,a)-2\phi_{t}(x,a)\leq\frac{1}{T}\sum_{t\in[T]}\mathbb{E}[r_ {t}(x,a)].$ $$

Let’s observe that, by Lemma 10, under the event $\mathcal{E}_{G}\cap\mathcal{E}_{P}$, $\widehat{q}_{t}$ is optimal solution for $\overline{r}_{t-1}$ in $\left\{q\in\Delta(\mathcal{P}_{t}):\underline{G}_{t}^{\top}q\leq\alpha\right\}$. Thus, under $\mathcal{E}_{G}\cap\mathcal{E}_{P}$ the optimal feasible solution $q^{*}$ is such that:

$$ $\overline{r}_{t-1}^{\top}\widehat{q}_{t}\geq\overline{r}_{t-1}^{\top}q^{*}.$ $$

Thus under the event $\mathcal{E}_{r}$, it holds:

$$ $\displaystyle\frac{1}{T}\sum_{t\in[T]}\mathbb{E}[r_{t}]^{\top}q^{*}$ $\displaystyle\leq\overline{r}_{t-1}^{\top}q^{*}$ $\displaystyle\leq\overline{r}_{t-1}^{\top}\widehat{q}_{t}$ $\displaystyle\leq\left(\frac{1}{T}\sum_{t\in[T]}\mathbb{E}[r_{t}]+2\phi_{t-1} \right)^{\top}\widehat{q}_{t}.$ $$

Thus, we can rewrite the regret (under the event $\mathcal{E}_{G}\cap\mathcal{E}_{r}\cap\mathcal{E}_{P}$) as,

$$ $\displaystyle R_{T}$ $\displaystyle=\sum_{t\in[T]}\mathbb{E}[r_{t}]^{\top}(q^{*}-q_{t})$ $\displaystyle=\sum_{t\in[T]}\frac{1}{T}\sum_{\tau\in[T]}\mathbb{E}[r_{\tau}]^{ \top}(q^{*}-q_{t})+\sum_{t\in[T]}\left(\mathbb{E}[r_{t}]-\overline{r}\right)^{ \top}(q^{*}-q_{t})$ $\displaystyle=\sum_{t\in[T]}\frac{1}{T}\sum_{\tau\in[T]}\mathbb{E}[r_{\tau}]^{ \top}(q^{*}-\widehat{q}_{t}+\widehat{q}_{t}-q_{t})+\sum_{t\in[T]}\left(\mathbb {E}[r_{t}]-r^{\circ}+r^{\circ}-\overline{r}\right)^{\top}(q^{*}-q_{t})$ $\displaystyle\leq\sum_{t\in[T]}\left[\frac{1}{T}\sum_{\tau\in[T]}\mathbb{E} \left[r_{\tau}\right]^{\top}(q^{*}-\widehat{q}_{t})\right]+\sum_{t\in[T]} \lVert\widehat{q}_{t}-q_{t}\rVert_{1}+\sum_{t\in[T]}\lVert\mathbb{E}[r_{t}]-r^ {\circ}\rVert_{1}+\sum_{t\in[T]}\lVert r^{\circ}-\overline{r}\rVert_{1}$ $\displaystyle\leq\sum_{t\in[T]}2\phi_{t-1}^{\top}q_{t}+\sum_{t\in[T]}\lVert \widehat{q}_{t}-q_{t}\rVert_{1}+2C_{r}.$ $$

By Lemma 19 with probability at least $1-6\delta$ under event $\mathcal{E}_{\widehat{q}}$ we can bound $\sum_{t\in[T]}\lVert\widehat{q}_{t}-q_{t}\rVert_{1}$ as:

$$ $\sum_{t\in[T]}\lVert\widehat{q}_{t}-q_{t}\rVert_{1}=\mathcal{O}\left(L|X|\sqrt {|A|T\ln\left(\frac{T|X||A|}{\delta}\right)}\right).$ $$

Finally with probability at least $1-\delta$ it holds:

$$ $\displaystyle\sum_{t\in[T]}\phi_{t-1}^{\top}q_{t}\leq\sum_{t\in[T]}\sum_{x,a} \phi_{t-1}(x,a)\mathbb{I}_{t}(x,a)+L\sqrt{2T\ln\frac{1}{\delta}}$ (15a) $\displaystyle\leq\underset{x,a}{\sum}\underset{t\in[T]}{\sum}\mathbb{I}_{t}(x, a)\Bigg{(}\sqrt{\frac{1}{2\max\{N_{t-1}(x,a),1\}}\ln\left(\frac{2T|X||A|}{ \delta}\right)}+$ $\displaystyle\mkern 170.0mu+\frac{C_{r}}{\max\{N_{t-1}(x,a),1\}}+\frac{C_{r}}{ T}\Bigg{)}+L\sqrt{2T\ln\frac{1}{\delta}}$ (15b) $\displaystyle\leq\sqrt{\frac{1}{2}\ln\left(\frac{2T|X||A|}{\delta}\right)} \underset{x,a}{\sum}\underset{t\in[T]}{\sum}\mathbb{I}_{t}(x,a)\sqrt{\frac{1}{ \max\{N_{t-1}(x,a),1\}}}+$ $\displaystyle\mkern 170.0mu+C_{r}\underset{x,a}{\sum}\underset{t\in[T]}{{\sum} }\left(\frac{\mathbb{I}_{t}(x,a)}{\max\{N_{t-1}(x,a),1\}}+\frac{1}{T}\right)+L \sqrt{2T\ln\frac{1}{\delta}}$ $\displaystyle\leq 3\sqrt{\frac{1}{2}|X||A|LT\ln\left(\frac{2T|X||A|}{\delta} \right)}+|X||A|(2+\ln(T))C_{r}+|X||A|C_{r}+L\sqrt{2T\ln\frac{1}{\delta}}$ (15c) $\displaystyle\leq 3\sqrt{\frac{1}{2}|X||A|LT\ln\left(\frac{2T|X||A|}{\delta} \right)}+(3+\ln(T))|X||A|C_{r}+L\sqrt{2T\ln\frac{1}{\delta}}$ $\displaystyle=\mathcal{O}\left(\sqrt{|X||A|LT\ln\left(\frac{T|X||A|}{\delta} \right)}+\ln(T)|X||A|C_{r}\right),$ $$

where Inequality (15a) follows from Azuma-Hoeffding inequality, Equality (15b) holds for the definition of $\phi_{t}$, and Inequality (15c) holds since $1+\sum_{t=1}^{N_{T}(x,a)}\sqrt{\frac{1}{t}}\leq 1+2\sqrt{N_{T}(x,a)}\leq 3
\sqrt{N_{T}(x,a)}$, $1+\sum_{t=1}^{N_{T}(x,a)}\frac{1}{t}\leq 2+\ln(T)$ and by Cauchy-Schwarz inequality.
Thus, we observe that with probability at least $1-9\delta$ it holds:

$$ $R_{T}=\mathcal{O}\left(L|X|\sqrt{|A|T\ln\left(\frac{T|X||A|}{\delta}\right)}+ \ln(T)|X||A|C_{r}\right).$ $$

Employing Corollary 3 and the definition of $C$, which is at least equal to $C_{r}$, concludes the proof.
∎

###### Lemma 10 .

###### Proof.

###### Proof.

###### Proof.

## Appendix E Omitted proofs when the knowledge of C 𝐶 C italic_C is not precise

In this section, we focus on the performances of Algorithm 2 when a guess on the corruption value is given as input. These preliminary results are "the first step" to relax the assumption on the knowledge about the corruption.

First, we present some preliminary results on the confidence set.

###### Lemma 11 .

Given the corruption guess $\widehat{C}_{G}$, where $C_{G}=\widehat{C}_{G}+\epsilon,$ with $\epsilon>0$, and confidence $\xi_{t}$ as defined in Algorithm 2 using $\widehat{C}_{G}$ as corruption value, for any $\delta\in(0,1)$, with probability at least $1-\delta$, for all episodes $t\in[T]$, state-action pair $(x,a)\in X\times A$ and constraint $i\in[m]$, the following result holds:

$$ $g^{\circ}_{i}(x,a)\leq\widehat{g}_{t,i}(x,a)+\xi_{t}(x,a)+\left(\frac{\epsilon }{\max\{N_{t}(x,a),1\}}+\frac{\epsilon}{T}\right).$ $$

Similarly, recalling the definition of $\underline{G}_{t}$, for all episodes $t\in[T]$, state-action pairs $(x,a)\in X\times A$ and constraints $i\in[m]$, it holds:

$$ $g^{\circ}_{i}(x,a)\leq\underline{g}_{t,i}(x,a)+2\xi_{t}(x,a)+\left(\frac{ \epsilon}{\max\{N_{t}(x,a),1\}}+\frac{\epsilon}{T}\right).$ $$

###### Proof.

To prove the result, we recall that, by Corollary 2, with probability at least $1-\delta$, the following holds, for all episodes $t\in[T]$, state-action pairs $(x,a)\in X\times A$ and constraints $i\in[m]$:

$$ $\displaystyle\bigg{\lvert}\widehat{g}_{t,i}(x,a)-$ $\displaystyle g^{\circ}_{i}(x,a)]\bigg{\rvert}\leq$ $\displaystyle\sqrt{\frac{1}{2\max\{N_{t}(x,a),1\}}\ln\left(\frac{2mT|X||A|}{ \delta}\right)}+\frac{C_{G}}{\max\{N_{t}(x,a),1\}}+\frac{C_{G}}{T},$ $$

which can be rewritten as:

$$ $\bigg{\lvert}\widehat{g}_{t,i}(x,a)-g^{\circ}_{i}(x,a)]\bigg{\rvert}\leq\xi_{t }(x,a)+\frac{\epsilon}{\max\{N_{t}(x,a),1\}}+\frac{\epsilon}{T},$ $$

where,

$$ $\xi_{t}(x,a):=\min\left\{1,\sqrt{\frac{1}{2\max\{N_{t}(x,a),1\}}\ln\left(\frac {2mT|X||A|}{\delta}\right)}+\frac{\widehat{C}_{G}}{\max\{N_{t}(x,a),1\}}+\frac {\widehat{C}_{G}}{T}\right\},$ $$

and $C_{G}=\widehat{C}_{G}+\epsilon$, which concludes the proof.
∎

We are now ready study the regret bound attained by the algorithm when the guess on the corruption is an overestimate.

###### Theorem 7 .

For any $\delta\in(0,1)$, Algorithm 2, when instantiated with corruption value $\widehat{C}$ which is an overestimate of the true value of $C$, i.e. $\widehat{C}>C_{G}$ and $\widehat{C}>C_{r}$, attains with probability at least $1-8\delta$:

$$ $R_{T}=\mathcal{O}\left(L|X|\sqrt{|A|T\ln\left(\frac{T|X||A|}{\delta}\right)}+ \ln(T)|X||A|\widehat{C}\right).$ $$

###### Proof.

By Corollary 1, it holds that the decision space of the linear program performed by Algorithm 2 contains with high probability the optimal solution that respects to the constraints. Furthermore, employing Corollary 3 and following the proof of Theorem 3 concludes the proof.
∎

We proceed bounding the violation attained by our algorithm when an underestimate of the corruption is given as input.

###### Theorem 8 .

For any $\delta\in(0,1)$, Algorithm 2, when instantiated with corruption value $\widehat{C}$ which is an underestimate of the true value of $C_{G}$, i.e. $\widehat{C}<C_{G}$, attains with probability at least $1-9\delta$:

$$ $V_{T}=\mathcal{O}\left(L|X|\sqrt{|A|T\ln\left(\frac{mT|X||A|}{\delta}\right)}+ \ln(T)|X||A|C_{G}\right).$ $$

###### Proof.

First, let’s define $\epsilon\in\mathbb{R}^{+}$ such that $\epsilon:=C_{G}-\widehat{C}$. Then, with probability at least $1-\delta$:

$$ $\displaystyle V_{T}$ $\displaystyle=\underset{i\in[m]}{\max}\underset{t\in[T]}{\sum}\left[\mathbb{E} [G_{t}]^{\top}q_{t}-\alpha\right]_{i}^{+}$ (16a) $\displaystyle=\underset{i\in[m]}{\max}\underset{t\in[T]}{\sum}\left[\left( \mathbb{E}[g_{t,i}]-g^{\circ}_{i}\right)^{\top}q_{t}+g^{\circ}_{i}{}^{\top}q_{ t}-\alpha_{i}\right]^{+}$ $\displaystyle\leq\underset{i\in[m]}{\max}\underset{t\in[T]}{\sum}\Bigg{[}( \mathbb{E}[g_{t,i}]-g^{\circ}_{i})^{\top}q_{t}+\underline{g}_{t-1,i}^{\top}(q_ {t}-\widehat{q}_{t})+\underline{g}_{t-1,i}^{\top}\widehat{q}_{t}+2\xi_{t-1}^{ \top}q_{t}+$ $\displaystyle\mkern 200.0mu+\sum_{x,a}\left(\frac{\epsilon}{\max\{N_{t-1}(x,a) ,1\}}+\frac{\epsilon}{T}\right)q_{t}(x,a)-\alpha_{i}\Bigg{]}^{+}$ (16b) $\displaystyle\leq C_{G}+2\underset{i\in[m]}{\max}\underset{t\in[T]}{\sum}\xi_{ t-1}^{\top}q_{t}+\underset{t\in[T]}{\sum}\lVert q_{t}-\widehat{q}_{t}\rVert_{1}+$ $\displaystyle\mkern 200.0mu+\underset{t\in[T]}{\sum}\sum_{x,a}\frac{\epsilon}{ \max\{N_{t-1}(x,a),1\}}q_{t}(x,a)+\epsilon L,$ (16c) $$

where Inequality (16b) follows from Lemma 11 and Inequality (16c) is derived as in the proof of Theorem 2, and considering that $\lVert q_{t}\rVert_{1}=L,\ \forall t\in[T]$.
Now, employing the Azuma-Hoeffding inequality, we can bound, with probability at least $1-\delta$ the term $\sum_{t=1}^{T}\sum_{x,a}\frac{\epsilon}{\max\{N_{t-1}(x,a),1\}}q_{t}(x,a)$ as follows:

$$ $\displaystyle\underset{t\in[T]}{\sum}\sum_{x,a}\frac{\epsilon}{\max\{N_{t-1}(x ,a),1\}}q_{t}(x,a)$ $\displaystyle\leq L\sqrt{2T\ln\frac{1}{\delta}}+\underset{t\in[T]}{\sum}\sum_{ x,a}\frac{\epsilon}{\max\{N_{t-1}(x,a),1\}}\mathbb{I}_{t}(x,a)$ $\displaystyle\leq L\sqrt{2T\ln\frac{1}{\delta}}+\epsilon|X||A|(1+\ln(T)),$ $$

where we applied Azume Hoeffding inequality and the fact that $\sum_{t\in[N_{T}(x,a)]}\frac{1}{t}\leq 1+\ln(T)$.
Finally, following the steps of the proof of Theorem 2 to bound the first 3 elements of Inequality (16c) under $\mathcal{E}_{\widehat{q}}$ with probability at least $1-\delta$, and considering that $\epsilon\leq C_{G}$ and $\widehat{C}\leq C_{G}$, it holds, with probability at least $1-9\delta$,

$$ $V_{T}=\mathcal{O}\left(L|X|\sqrt{|A|T\ln\left(\frac{T|X||A|}{\delta}\right)}+ \ln(T)|X||A|C_{G}\right),$ $$

which concludes the proof.
∎

Finally, we provide the violation bound attained by Algorithm 2 when an overestimate of the corruption value is given as input.

###### Theorem 9 .

For any $\delta\in(0,1)$, Algorithm 2, when instantiated with corruption value $\widehat{C}$ which is an overestimate of the true value of $C_{G}$, i.e. $\widehat{C}>C_{G}$, attains with probability at least $1-8\delta$:

$$ $V_{T}=\mathcal{O}\left(L|X|\sqrt{|A|T\ln\left(\frac{T|X||A|}{\delta}\right)}+ \ln(T)|X||A|\widehat{C}\right).$ $$

###### Proof.

The proof follows by employing Corollary 1 to the proof of Theorem 2.
∎

###### Lemma 11 .

###### Proof.

###### Theorem 7 .

###### Proof.

###### Theorem 8 .

###### Proof.

###### Theorem 9 .

###### Proof.

## Appendix F Omitted proofs when the corruption is not known

In the following section we provide the omitted proofs of the theoretical guarantees attained by Algorithm 3. The algorithm is designed to work when the corruption value is *not* known.

### F.1 Lagrangian formulation of the constrained optimization problem

Since Algorithm 3 is based on a Lagrangian formulation of the constrained problem, it is necessary to show that this approach is well characterized. Precisely, we show that a *strong duality-like* result holds even when the Lagrangian function is defined taking the positive violations.

First, we show that strong duality holds with respect to the standard Lagrangian function, even considering a subset of the Lagrangian multiplier space.

See 2

###### Proof.

The proof follows the one of Theorem 3.3 in (Castiglioni et al., ).
First we prove that, given the Lagrangian function $\mathcal{Q}(\lambda,q):=r^{\top}q-\sum_{i\in[m]}\lambda_{i}\left({G}_{i}^{\top
}q-\alpha_{i}\right)$, it holds:

$$ $\min_{\lVert\lambda\rVert_{1}\in[0,L/\rho]}\max_{q\in\Delta(P)}\mathcal{Q}( \lambda,q)=\min_{\lambda\in\mathbb{R}^{m}_{\geq 0}}\max_{q\in\Delta(P)} \mathcal{Q}(\lambda,q),$ $$

with $\lambda\in\mathbb{R}^{m}_{\geq 0}$.
In fact notice that for all $\lambda\in\mathbb{R}^{m}_{\geq 0}$ such that $\lVert\lambda\rVert_{1}>L/\rho$ :

$$ $\max_{q\in\Delta(P)}\mathcal{Q}(\lambda,q)\geq\mathcal{Q}(\lambda,{q}^{\circ}) \geq-\sum_{i\in[m]}\lambda_{i}\left({G}_{i}^{\top}q^{\circ}-\alpha_{i}\right) \geq\lVert\lambda\rVert_{1}\rho>L,$ $$

where $q^{\circ}$ is defined as $q^{\circ}:=\operatorname*{arg\,max}_{q\in\Delta(P)}\min_{i\in[m]}\left[\alpha_
{i}-G_{i}^{\top}q\right]$.
Moreover since

$$ $\min_{\lVert\lambda\rVert_{1}\in[0,L/\rho]}\max_{q\in\Delta(P)}\mathcal{Q}( \lambda,q)\leq\max_{q\in\Delta(P)}\mathcal{Q}(\underline{0},q)=\max_{q\in \Delta(P)}r^{\top}q\leq L,$ $$

it holds:

$$ $\displaystyle\min_{\lambda\in\mathbb{R}^{m}_{\geq 0}}\max_{q\in\Delta(P)} \mathcal{Q}(\lambda,q)$ $\displaystyle=\min\left\{\min_{\lVert\lambda\rVert_{1}\in[0,L/\rho]}\max_{q\in \Delta(P)}\mathcal{Q}(\lambda,q),\min_{\lVert\lambda\rVert_{1}\geq L/\rho}\max _{q\in\Delta(P)}\mathcal{Q}(\lambda,q)\right\}$ $\displaystyle=\min_{\lVert\lambda\rVert_{1}\in[0,L/\rho]}\max_{q\in\Delta(P)} \mathcal{Q}(\lambda,q).$ $$

Thus,

$$ $\displaystyle\text{OPT}_{r,G,\alpha}$ $\displaystyle=\max_{q\in\Delta(P)}\min_{\lambda\in\mathbb{R}^{m}_{\geq 0}} \mathcal{Q}(\lambda,q)$ $\displaystyle\leq\max_{q\in\Delta(P)}\min_{\lVert\lambda\rVert_{1}\geq L/\rho} \mathcal{Q}(\lambda,q)$ $\displaystyle\leq\min_{\lVert\lambda\rVert_{1}\geq L/\rho}\max_{q\in\Delta(P)} \mathcal{Q}(\lambda,q)$ $\displaystyle=\min_{\lambda\in\mathbb{R}_{\geq 0}^{m}}\max_{q\in\Delta(P)} \mathcal{Q}(\lambda,q)$ $\displaystyle=\text{OPT}_{r,G,\alpha},$ $$

where the second inequality holds by the *max-min* inequality and the last step holds by the well-known strong duality result in CMDPs (Altman, ). This concludes the proof.
∎

In the following, we extend the previous result for the Lagrangian function which encompasses the positive violations.
See 4

###### Proof.

Following the definition of Lagrangian function, we have:

$$ $\displaystyle\max_{q\in\Delta(P)}\mathcal{L}(L/\rho,q)$ $\displaystyle=\max_{q\in\Delta(P)}r^{\top}q-\frac{L}{\rho}\sum_{i\in[m]}\left[ {G}_{i}^{\top}q-\alpha_{i}\right]^{+}$ $\displaystyle\leq\max_{q\in\Delta(P)}\min_{\lVert\lambda\rVert_{1}\in[0,L/\rho ]}r^{\top}q-\sum_{i\in[m]}\lambda_{i}[{G}_{i}^{\top}q-\alpha_{i}]^{+}$ $\displaystyle\leq\min_{\lVert\lambda\rVert_{1}\in[0,L/\rho]}\max_{q\in\Delta(P )}r^{\top}q-\sum_{i\in[m]}\lambda_{i}[{G}_{i}^{\top}q-\alpha_{i}]^{+}$ $\displaystyle\leq\min_{\lVert\lambda\rVert_{1}\in[0,L/\rho]}\max_{q\in\Delta(P )}r^{\top}q-\sum_{i\in[m]}\lambda_{i}\left({G}_{i}^{\top}q-\alpha_{i}\right)$ $\displaystyle=\text{OPT}_{r,G,\alpha}$ $$

where $\lambda\in\mathbb{R}^{m}_{\geq 0}$ is the Lagrangian vector, the second inequality holds by the *max-min inequality* and the last step follows from Lemma 2.
Noticing that for all $q$ belonging to $\left\{q\in\Delta(P):G^{\top}q\leq\alpha\right\}$, we have $\mathcal{L}(1/\rho,q)=r^{\top}q$, which implies that $\max_{q\in\Delta(P)}\mathcal{L}(1/\rho,q)\geq\text{OPT}_{r,G,\alpha}$, concludes the proof.
∎

###### Proof.

###### Proof.

### F.2 Preliminary results

In the following sections we will refer as:

$$ $\widehat{V}_{T}:=\sum_{t\in[T]}\sum_{j\in[M]}\frac{w_{t,j}\mathbb{I}(j_{t}=j)} {w_{t,j}+\gamma}\sum_{i\in[m]}\left[\widehat{g}_{t,i}^{\ j\top}\widehat{q}_{t} ^{\ j}-\alpha_{i}\right]^{+},$ (17) $$

to the estimated violation attained by the instances of Algorithm 3. Furthermore, we will refer as:

$$ $\widehat{V}_{T,j^{*}}:=\sum_{t\in[T]}\frac{\mathbb{I}(j_{t}=j^{*})}{w_{t,j^{*} }+\gamma}\sum_{i\in[m]}\left[\widehat{g}_{t,i}^{\ j^{*}\top}\widehat{q}_{t}^{ \ j^{*}}-\alpha_{i}\right]^{+},$ (18) $$

to the estimated violation attained by the optimal instance $j^{*}$, namely, the integer in $[M]$ such that the true corruption $C\in[2^{j^{*}-1},2^{j^{*}}]$.

Furthermore, we will refer as $q_{t}^{j}$ to the occupancy measure induced by the policy proposed by $\texttt{Alg}^{j}$ at episode $t$, with $j\in[M],t\in[T]$, and we will refer as:

$$ $\widehat{g}_{t,i}^{j}(x,a):=\frac{\sum_{\tau\in[t]}\mathbb{I}_{\tau}(x,a) \mathbb{I}(j_{\tau}=j)g_{\tau,i}(x,a)}{\max\{N_{t}^{j}(x,a),1\}},$ $$

to the estimate of the cost computed for $j$-th algorithm, where $N_{t}^{j}(x,a)$ is a counter initialize to 0 0 in $t=0$, and which increases by one from episode $t$ to episode $t+1$ whenever $\mathbb{I}_{t}(x,a)\mathbb{I}(j_{t}=j)=1$.

#### F.2.1 Stability parameters

In the following sections, we will employ the stability parameters $\beta$ defined as follows:

- •
$\beta_{1}=\mathcal{O}\left(L^{2}|X|^{2}|A|\ln\left(\frac{T|X||A|}{\delta}
\right)\right)$
- •
$\beta_{2}=\mathcal{O}\left(|X|^{2}|A|^{2}\log(T)\log\left(\nicefrac{{\log(T)}}
{{\delta}}\right)\right)$
- •
$\beta_{3}=\mathcal{O}\left(\ln(T)^{2}|X||A|\right)$
- •
$\beta_{4}=\mathcal{O}\left(L^{2}|X|^{2}|A|\ln\left(\frac{mT|X||A|}{\delta}
\right)\right)$
- •
$\beta_{5}=\mathcal{O}\left(|X|^{2}|A|^{2}\log(T)\log\left(\nicefrac{{\log(T)}}
{{\delta}}\right)\right)$
- •
$\beta_{6}=\mathcal{O}\left(\ln(T)^{2}|X||A|\right)$

#### F.2.2 Omitted proofs and lemmas

We start providing some preliminary results on the optimistic estimator employed by Algorithm 3.

###### Lemma 12 .

For any $\delta\in(0,1)$, given $\gamma\in\mathbb{R}_{\geq 0}$, with probability at least $1-\delta$, it holds:

$$ $\widehat{R}_{T}\leq\mathcal{O}\left(\gamma TLM+L\sqrt{2T\ln\left(\frac{1}{ \delta}\right)}\right),$ $$

where $\widehat{R}_{T}=\sum_{t\in[T]}\sum_{j\in[M]}\left(w_{t,j}\left(L-\mathbb{E}[r_
{t}]^{\top}q_{t}^{j}\right)-\frac{w_{t,j}\mathbb{I}(j_{t}=j)}{w_{t,j}+\gamma}
\sum_{(x_{k}^{t},a_{k}^{t})}\left(1-r_{t}\left(x_{k}^{t},a_{k}^{t}\right)
\right)\right)$.

###### Proof.

We first observe that by construction:

$$ $\mathbb{E}\left[\sum_{t\in[T]}\sum_{j\in[M]}\frac{w_{t,j}\mathbb{I}(j_{t}=j)}{ w_{t,j}+\gamma}\sum_{(x_{k}^{t},a_{k}^{t})}\left(1-r_{t}\left(x_{k}^{t},a_{k}^ {t}\right)\right)\right]=\sum_{t\in[T]}\sum_{j\in[M]}\frac{w_{t,j}^{2}}{w_{t,j }+\gamma}\left(L-\mathbb{E}[r_{t}]^{\top}q_{t}^{j}\right).$ $$

Moreover, still by construction, for all episodes $t\in[T]$, it holds:

$$ $\sum_{j\in[M]}\frac{w_{t,j}\mathbb{I}(j_{t}=j)}{w_{t,j}+\gamma}\sum_{(x_{k}^{t },a_{k}^{t})}\left(1-r_{t}\left(x_{k}^{t},a_{k}^{t}\right)\right)\leq\sum_{j \in[M]}\mathbb{I}(j_{t}=j)\sum_{(x_{k}^{t},a_{k}^{t})}\left(1-r_{t}\left(x_{k} ^{t},a_{k}^{t}\right)\right)\leq L.$ $$

Thus, employing Azuma-Hoeffding inequality, with probability at least $1-\delta$, it holds:

$$ $\displaystyle\sum_{t\in[T]}\sum_{j\in[M]}\left(\frac{w_{t,j}^{2}}{w_{t,j}+ \gamma}(L-\mathbb{E}[r_{t}]^{\top}q_{t}^{j})-\frac{w_{t,j}\mathbb{I}(j_{t}=j)} {w_{t,j}+\gamma}\sum_{(x_{k}^{t},a_{k}^{t})}(1-r_{t}(x_{k}^{t},a_{k}^{t})) \right)\leq L\sqrt{2T\ln\left(\frac{1}{\delta}\right)}.$ $$

Finally we notice that:

$$ $\displaystyle\sum_{t\in[T]}\sum_{j\in[M]}w_{t,j}$ $\displaystyle\left(L-\mathbb{E}[r_{t}]^{\top}q_{t}^{j}\right)-\sum_{t\in[T]} \sum_{j\in[M]}\frac{w_{t,j}^{2}}{w_{t,j}+\gamma}\left(L-\mathbb{E}[r_{t}]^{ \top}q_{t}^{j}\right)$ $\displaystyle=\sum_{t\in[T]}\sum_{j\in[M]}\left(\frac{w_{t,j}}{w_{t,j}+\gamma} \right)\gamma\left(L-\mathbb{E}[r_{t}]^{\top}q_{t}^{j}\right)$ $\displaystyle\leq\gamma TLM.$ $$

Adding and subtracting $\mathbb{E}\left[\sum_{t\in[T]}\sum_{j\in[M]}\frac{w_{t,j}\mathbb{I}(j_{t}=j)}{
w_{t,j}+\gamma}\sum_{(x_{k}^{t},a_{k}^{t})}\left(1-r_{t}\left(x_{k}^{t},a_{k}^
{t}\right)\right)\right]$ to the quantity of interest and employing the previous bound concludes the proof.
∎

We provide an additional result on the optimistic estimator employed by Algorithm 3.

###### Lemma 13 .

For any $\delta\in(0,1)$, given $\gamma\in\mathbb{R}_{\geq 0}$, with probability at least $1-\delta$, it holds:

$$ $\sum_{t\in[T]}\frac{\mathbb{I}(j_{t}=j^{*})}{w_{t,j^{*}}+\gamma}\sum_{(x_{k}^{ t},a_{k}^{t})}\left(1-r_{t}\left(x_{k}^{t},a_{k}^{t}\right)\right)-\sum_{t\in[ T]}\left(L-\mathbb{E}[r_{t}]^{\top}q_{t}^{j^{*}}\right)=\mathcal{O}\left(\frac {L}{\gamma}\ln\left(\frac{1}{\delta}\right)\right)$ $$

###### Proof.

The proof closely follows the idea of Corollary 5.
We define the loss $\bar{\ell}_{t}=\sum_{(x_{k}^{t},a_{k}^{t})}(1-r_{t}(x_{k}^{t},a_{k}^{t}))$, the optimistic loss estimator $\widehat{\ell}_{t}:=\frac{\mathbb{I}(j_{t}=j^{*})}{w_{t,j^{*}}+\gamma}\sum_{(x
_{k}^{t},a_{k}^{t})}(1-r_{t}(x_{k}^{t},a_{k}^{t}))$ and the unbiased estimator $\widetilde{\ell}_{t}:=\frac{\mathbb{I}(j_{t}=j^{*})}{w_{t,j^{*}}}\sum_{(x_{k}^
{t},a_{k}^{t})}(1-r_{t}(x_{k}^{t},a_{k}^{t}))$.

Employing the same argument as Neu () it holds:

$$ $\widehat{\ell}_{t}=\frac{\mathbb{I}(j_{t}=j^{*})}{w_{t,j^{*}}+\gamma}\bar{\ell }_{t}\leq\frac{\mathbb{I}(j_{t}=j^{*})}{w_{t,j^{*}}+\gamma\bar{\ell}_{t}/L} \bar{\ell}_{t}\leq\frac{L}{2\gamma}\frac{2\gamma\bar{\ell}_{t}/w_{t,j^{*}}L}{1 +\gamma\bar{\ell}_{t}/w_{t,j^{*}}L}\mathbb{I}(j_{t}=j^{*})\leq\frac{L}{2\gamma }\ln\left(1+\frac{2\gamma}{L}\widetilde{\ell}_{t}\right),$ $$

since $\frac{z}{1+z/2}\leq\ln(1+z),z\in\mathbb{R}^{+}$. Employing the previous inequality, it holds:

$$ $\displaystyle\mathbb{E}\left[\exp\left(\frac{2\gamma}{L}\widehat{\ell}_{t} \right)\Bigg{|}\mathcal{F}_{t-1}\right]$ $\displaystyle\leq\mathbb{E}\left[\exp\left(\frac{2\gamma}{L}\frac{L}{2\gamma} \ln\left(1+\frac{2\gamma}{L}\widetilde{\ell}_{t}\right)\right)\Bigg{|}\mathcal {F}_{t-1}\right]$ $\displaystyle=\mathbb{E}\left[1+\frac{2\gamma}{L}\widetilde{\ell}_{t}\Bigg{|} \mathcal{F}_{t-1}\right]$ $\displaystyle=1+\frac{2\gamma}{L}\mathbb{E}\left[\frac{\mathbb{I}(j_{t}=j^{*}) }{w_{t,j^{*}}}\sum_{(x_{k}^{t},a_{k}^{t})}(1-r_{t}(x_{k}^{t},a_{k}^{t}))\Bigg{ |}\mathcal{F}_{t-1}\right]$ $\displaystyle\leq 1+\frac{2\gamma}{L}\left(L-\mathbb{E}[r_{t}]^{\top}q_{t}^{j^ {*}}\right)$ $\displaystyle\leq\exp\left(\frac{2\gamma}{L}\left(L-\mathbb{E}[r_{t}]^{\top}q_ {t}^{j^{*}}\right)\right),$ $$

where $\mathcal{F}_{t-1}$ is the filtration up to episode $t$.
We conclude the proof employing the Markov inequality as follows:

$$ $\displaystyle\mathbb{P}\Bigg{(}\sum_{t\in[T]}\frac{2\gamma}{L}$ $\displaystyle\left(\widehat{\ell}_{t}-\left(L-\mathbb{E}[r_{t}]^{\top}q_{t}^{j ^{*}}\right)\right)\geq\epsilon\Bigg{)}$ $\displaystyle\leq\mathbb{E}\left[\exp\left(\sum_{t\in[T]}\frac{2\gamma}{L} \left(\widehat{\ell}_{t}-\left(L-\mathbb{E}[r_{t}]^{\top}q_{t}^{j^{*}}\right) \right)\right)\right]\exp(-\epsilon)$ $\displaystyle\leq\exp(-\epsilon).$ $$

Solving $\delta=\exp(-\epsilon)$ for $\epsilon$ we obtain:

$$ $\mathbb{P}\left(\sum_{t\in[T]}\left(\widehat{\ell}_{t}-\left(L-\mathbb{E}[r_{t }]^{\top}q_{t}^{j^{*}}\right)\right)\geq\frac{L}{2\gamma}\ln\left(\frac{1}{ \delta}\right)\right)\leq\delta.$ $$

This concludes the proof.
∎

We are now ready to prove the regret bound attained by FTRL with respect to the Lagrangian underlying problem.

###### Lemma 14 .

For any $\delta\in(0,1)$ and properly setting the learning rate $\eta$ such that $\eta\leq\frac{1}{2\Lambda m\left(\sqrt{\beta_{1}T}+\beta_{2}+\beta_{5}+\sqrt{
\beta_{4}T}\right)}$, Algorithm 3 attains, with probability at least $1-2\delta$:

$$ $\displaystyle\sum_{t\in[T]}\mathbb{E}[r_{t}]^{\top}q_{t}^{j^{*}}-\sum_{t\in[T] }\sum_{j\in[M]}w_{t,j}\mathbb{E}[r_{t}]^{\top}q_{t}^{j}+\frac{Lm+1}{\rho} \widehat{V}_{T}-\frac{Lm+1}{\rho}\widehat{V}_{T,j^{*}}$ $\displaystyle\hskip 28.45274pt+\left(\frac{m(mL+1)}{\rho}\beta_{5}+\beta_{2} \right)\nu_{T,j^{*}}+\left(\sqrt{\beta_{1}}+\left(\frac{m(Lm+1)}{\rho}\right) \sqrt{\beta_{4}}\right)\sqrt{T}\nu_{T,j*}$ $\displaystyle\leq\mathcal{O}\bigg{(}\frac{M\ln T}{\eta}+\eta~{}{m^{4}L^{4}TM}+ \eta~{}M\ln(T)m^{4}L^{2}\beta_{5}^{2}+\eta~{}M\ln(T)\beta_{2}^{2}$ $\displaystyle\mkern 100.0mu+\eta T(\beta_{1}+L^{2}m^{4}\beta_{4})M\log(T)+ \gamma TLM+L\sqrt{T\ln\left(\nicefrac{{1}}{{\delta}}\right)}+\frac{L}{\gamma} \ln\left(\nicefrac{{1}}{{\delta}}\right)\bigg{)}.$ $$

###### Proof.

First, we define $\ell_{t,j}$, for all $t\in[T]$, for all $j\in[M]$ as:

$$ $\ell_{t,j}:=\frac{\mathbb{I}(j_{t}=j)}{w_{t,j}+\gamma}\left(\sum_{(x_{k}^{t},a _{k}^{t})}(1-r_{t}(x_{k}^{t},a_{k}^{t}))+\frac{Lm+1}{\rho}\sum_{i\in[m]}\left[ \widehat{g}_{t,i}^{\ j\top}\widehat{q}_{t}^{\ j}-\alpha_{i}\right]^{+}\right),$ $$

and $b_{t,j}$ for all $t\in[T]$, for all $j\in[M]$ as:

$$ $b_{t,j}:=\left(\left(\frac{m(mL+1)}{\rho}\beta_{5}+\beta_{2}\right)+\left( \sqrt{\beta_{1}}+\frac{m(Lm+1)}{\rho}\sqrt{\beta_{4}}\right)\sqrt{T}\right)( \nu_{t,j}-\nu_{t-1,j}),$ $$

with $\nu_{t,j}=\max_{\tau\in[t]}\frac{1}{w_{\tau,j}}$.
First we prove that $\eta w_{t,j}|\ell_{t,j}-b_{t,j}|\leq\nicefrac{{1}}{{2}}$ for all $t\in[T],j\in[M]$, to apply Lemma 17. It holds that $\eta w_{t,j}\lvert\ell_{t,j}\rvert\leq\frac{\eta(L\rho+L^{2}m^{2}+Lm)}{\rho}
\leq\frac{1}{2}$ for all $j\in[M]$, for all $t\in[T]$ as long as $\eta\leq\frac{\rho}{2(L\rho+L^{2}m^{2}+Lm)}\leq\frac{\rho}{2(L^{2}m^{2}+Lm)}$, which is true if $\eta\leq\frac{\rho}{2Lm(Lm+1)}$. It also holds that

$$ $\displaystyle\eta w_{t,j}|b_{t,j}|$ $\displaystyle=\eta w_{t,j}\left(\left(\frac{m(Lm+1)}{\rho}\beta_{5}+\beta_{2} \right)+\left(\frac{m(Lm+1)}{\rho}\sqrt{\beta_{4}}+\sqrt{\beta_{1}}\right) \sqrt{T}\right)(\nu_{t,j}-\nu_{t-1,j})$ $\displaystyle\leq\eta\left(\left(\frac{m(Lm+1)}{\rho}\beta_{5}+\beta_{2}\right )+\left(\frac{m(Lm+1)}{\rho}\sqrt{\beta_{4}}+\sqrt{\beta_{1}}\right)\sqrt{T} \right)\left(1-\frac{\nu_{t-1,j}}{\nu_{t,j}}\right)$ $\displaystyle\leq\eta\left(\left(\frac{m(Lm+1)}{\rho}\beta_{5}+\beta_{2}\right )+\left(\frac{m(Lm+1)}{\rho}\sqrt{\beta_{4}}+\sqrt{\beta_{1}}\right)\sqrt{T}\right)$ $\displaystyle\leq\frac{1}{2},$ $$

if $\eta\leq\frac{1}{2\Lambda m\left(\sqrt{\beta_{1}T}+\beta_{2}+\beta_{5}+\sqrt{
\beta_{4}T}\right)}$, where we used the fact that $\nu_{t,j}\neq\nu_{t-1,j}\iff\nicefrac{{1}}{{w_{t,j}}}=\nu_{t,j}$.
Thus, if the previous conditions on $\eta$ hold, and notice that the second condition implies the first, Algorithm 3 attains, by Lemma 17 :

$$ $\displaystyle\sum_{t\in[T]}\Bigg{[}\sum_{j\in[M]}\frac{w_{t,j}\mathbb{I}(j_{t} =j)}{w_{t,j}+\gamma}\sum_{(x_{k}^{t},a_{k}^{t})}(1-r_{t}(x_{k}^{t},a_{k}^{t})) -\frac{\mathbb{I}(j_{t}=j^{*})}{w_{t,j^{*}}+\gamma}\sum_{(x_{k}^{t},a_{k}^{t}) }(1-r_{t}(x_{k}^{t},a_{k}^{t}))\Bigg{]}+\frac{Lm+1}{\rho}\widehat{V}_{T}$ $\displaystyle\leq\frac{M\ln T}{\eta}+2\eta\frac{TM(L\rho+L^{2}m^{2}+Lm)^{2}}{ \rho^{2}}$ $\displaystyle\ \ \ \ +2\eta\left(2\left(\frac{m(mL+1)}{\rho}\beta_{5}+\beta_{2 }\right)^{2}M\ln\left(T\right)+2T\left(\sqrt{\beta_{1}}+\left(\frac{m(Lm+1)}{ \rho}\right)\sqrt{\beta_{4}}\right)^{2}M\ln(T)\right)$ $\displaystyle\mkern 250.0mu+\frac{Lm+1}{\rho}\widehat{V}_{T,j^{*}}+\sum_{t\in[ T]}\sum_{j\in[M]}w_{t,j}b_{t,j}-\sum_{t\in[T]}b_{t,j^{*}},$ (19) $$

where we used the following inequalities:

- •
First inequality:
$\sum_{t\in[T]}\sum_{j\in[M]}w_{t,j}^{2}(\ell_{t,j}-b_{t,j})^{2}\leq 2\sum_{t
\in[T]}\sum_{j\in[M]}w_{t,j}^{2}\ell_{t,j}^{2}+2\sum_{t\in[T]}\sum_{j\in[M]}w_
{t,j}^{2}b_{t,j}^{2},$
- •
Second inequality:
$\left(\sum_{(x_{k}^{t},a_{k}^{t})}(1-r_{t}(x_{k}^{t},a_{k}^{t}))+\frac{Lm+1}{
\rho}\sum_{i\in[m]}\left[\widehat{g}_{t,i}^{\ j\top}\widehat{q}_{t}^{\ j}-
\alpha_{i}\right]^{+}\right)\leq\frac{(L\rho+L^{2}m^{2}+Lm)}{\rho},$
- •
Third inequality:
$\sum_{t\in[T]}\sum_{j\in[M]}w_{t,j}^{2}\ell_{t,j}^{2}\leq\frac{TM(L\rho+L^{2}m
^{2}+Lm)^{2}}{\rho^{2}},$

and that, it holds:

$$ $\displaystyle\sum_{t\in[T]}\sum_{j\in[M]}w_{t,j}^{2}b_{t,j}^{2}$ $\displaystyle=\sum_{t\in[T]}\sum_{j\in[M]}(w_{t,j}b_{t,j})^{2}$ $\displaystyle\leq\left(\left(\frac{m(Lm+1)}{\rho}\beta_{5}+\beta_{2}\right)+ \left(\frac{m(Lm+1)}{\rho}\sqrt{\beta_{4}}+\sqrt{\beta_{1}}\right)\sqrt{T} \right)^{2}\sum_{j\in[M]}\sum_{t\in[T]}\left(\frac{1}{\nu_{t,j}}(\nu_{t,j}-\nu _{t-1,j})\right)^{2}$ (20a) $\displaystyle\leq\left(2\left(\frac{m(mL+1)}{\rho}\beta_{5}+\beta_{2}\right)^{ 2}+2T\left(\frac{m(Lm+1)}{\rho}\sqrt{\beta_{4}}+\sqrt{\beta_{1}}\right)^{2} \right)\sum_{j\in[M]}\sum_{t\in[T]}\left(1-\frac{\nu_{t-1,j}}{\nu_{t,j}}\right )^{2}$ $\displaystyle\leq\left(2\left(\frac{m(mL+1)}{\rho}\beta_{5}+\beta_{2}\right)^{ 2}+2T\left(\frac{m(Lm+1)}{\rho}\sqrt{\beta_{4}}+\sqrt{\beta_{1}}\right)^{2} \right)\sum_{j\in[M]}\sum_{t\in[T]}\left(1-\frac{\nu_{t-1,j}}{\nu_{t,j}}\right)$ $\displaystyle\leq\left(2\left(\frac{m(mL+1)}{\rho}\beta_{5}+\beta_{2}\right)^{ 2}+2T\left(\frac{m(Lm+1)}{\rho}\sqrt{\beta_{4}}+\sqrt{\beta_{1}}\right)^{2} \right)\sum_{j\in[M]}\sum_{t\in[T]}\ln\left(\frac{\nu_{t,j}}{\nu_{t-1,j}}\right)$ (20b) $\displaystyle\leq\left(2\left(\frac{m(mL+1)}{\rho}\beta_{5}+\beta_{2}\right)^{ 2}+2T\left(\frac{m(Lm+1)}{\rho}\sqrt{\beta_{4}}+\sqrt{\beta_{1}}\right)^{2} \right)\sum_{j\in[M]}\ln\left(\prod_{t\in[T]}\frac{\nu_{t,j}}{\nu_{t-1,j}}\right)$ $\displaystyle\leq\left(2\left(\frac{m(mL+1)}{\rho}\beta_{5}+\beta_{2}\right)^{ 2}+2T\left(\frac{m(Lm+1)}{\rho}\sqrt{\beta_{4}}+\sqrt{\beta_{1}}\right)^{2} \right)\sum_{j\in[M]}\ln\left(\frac{\nu_{T,j}}{\nu_{0,j}}\right)$ $\displaystyle\leq\left(2\left(\frac{m(mL+1)}{\rho}\beta_{5}+\beta_{2}\right)^{ 2}+2T\left(\frac{m(Lm+1)}{\rho}\sqrt{\beta_{4}}+\sqrt{\beta_{1}}\right)^{2} \right)M\ln\left(T\right),$ (20c) $$

where Inequality (20a) is true since $\nu_{t,j}-\nu_{t-1,j}\neq 0$ only when $w_{t,j}=\nicefrac{{1}}{{\nu_{t,j}}}$ by definition, Inequality (20b) holds since $1-a\leq-\ln a$, and Inequality (20c) holds since by definition $\nu_{T,j}\leq T$ and $\nu_{0,j}=M$.
Notice also that, following a similar reasoning, it holds:

$$ $\displaystyle\sum_{t\in[T]}w_{t,j}b_{t,j}-\sum_{t\in[T]}b_{t,j^{*}}$ $\displaystyle=\left(\left(\frac{m(Lm+1)}{\rho}\beta_{5}+\beta_{2}\right)+\left (\frac{m(Lm+1)}{\rho}\sqrt{\beta_{4}}+\sqrt{\beta_{1}}\right)\sqrt{T}\right) \sum_{t\in[T]}\sum_{j\in[M]}\left(1-\frac{\nu_{t-1,i}}{\nu_{t,i}}\right)$ $\displaystyle\quad-\left(\left(\frac{m(Lm+1)}{\rho}\beta_{5}+\beta_{2}\right)+ \left(\frac{m(Lm+1)}{\rho}\sqrt{\beta_{4}}+\sqrt{\beta_{1}}\right)\sqrt{T} \right)\sum_{t\in[T]}(\nu_{t,j^{*}}-\nu_{t-1,j^{*}})$ $\displaystyle\leq\mathcal{O}\left(m^{2}L\beta_{5}M\log(T)+\beta_{2}M\log(T)+( \sqrt{\beta_{1}}+Lm^{2}\sqrt{\beta_{4}})\sqrt{T}M\log(T)\right)$ $\displaystyle\quad-\left(\left(\frac{m(Lm+1)}{\rho}\beta_{5}+\beta_{2}\right)+ \left(\frac{m(Lm+1)}{\rho}\sqrt{\beta_{4}}+\sqrt{\beta_{1}}\right)\sqrt{T} \right)\nu_{T,j^{*}}$ $$

Thus, with probability at least $1-2\delta$, it holds:

$$ $\displaystyle\sum_{t\in[T]}\mathbb{E}[r_{t}]^{\top}q_{t}^{j^{*}}-\sum_{t\in[T] }\sum_{j\in[M]}w_{t,j}\mathbb{E}[r_{t}]^{\top}q_{t}^{j}+\frac{Lm+1}{\rho} \widehat{V}_{T}$ $\displaystyle=\sum_{t\in[T]}\sum_{j\in[M]}w_{t,j}\left(L-\mathbb{E}[r_{t}]^{ \top}q_{t}^{j}\right)-\sum_{t\in[T]}\left(L-\mathbb{E}[r_{t}]^{\top}q_{t}^{j^{ *}}\right)+\frac{Lm+1}{\rho}\widehat{V}_{T}$ (21) $\displaystyle\leq\mathcal{O}\bigg{(}\frac{M\ln T}{\eta}+\eta~{}{m^{4}L^{4}TM}+ \eta~{}M\ln(T)m^{4}L^{2}\beta_{5}^{2}+\eta~{}M\ln(T)\beta_{2}^{2}$ $\displaystyle\mkern 70.0mu+\eta T(\beta_{1}+L^{2}m^{4}\beta_{4})M\log(T)+ \gamma TLM+L\sqrt{T\ln\left(\nicefrac{{1}}{{\delta}}\right)}+\frac{L}{\gamma} \ln\left(\nicefrac{{1}}{{\delta}}\right)\bigg{)}+\frac{Lm+1}{\rho}\widehat{V}_ {T,j^{*}}$ $\displaystyle\mkern 70.0mu-\left(\frac{m(mL+1)}{\rho}\beta_{5}+\beta_{2}\right )\nu_{T,j^{*}}-\left(\sqrt{\beta_{1}}+\left(\frac{m(Lm+1)}{\rho}\right)\sqrt{ \beta_{4}}\right)\sqrt{T}\nu_{T,j*},$ (22) $$

where Equation (21) holds since $\sum_{j\in[M]}w_{t,j}=1,~{}\forall t\in[T]$, and Inequality (22) holds, with probability at least $1-2\delta$, by Lemma 12, Lemma 13 and Equation (19). This concludes the proof.
∎

In order to provide the desired bound $R_{T}$ and $V_{T}$ for Algorithm 3, it is necessary to study the relation between the aforementioned performance measures and the terms appearing from the FTRL analysis in Lemma 14.

Thus, we bound the distance between the incurred violation and the estimated one.

###### Lemma 15 .

For any $\gamma\in\mathbb{R}_{\geq 0}$, given $\delta\in(0,1)$, with probability at least $1-10\delta$, it holds:

$$ $V_{T}-\widehat{V}_{T}=\mathcal{O}\left(mL|X|\sqrt{|A|T\ln\left(\frac{mT|X||A|} {\delta}\right)}+m\ln(T)|X||A|C+\gamma TLM\right).$ $$

###### Proof.

We start defining the quantity $\widehat{\xi}_{t,j}(x,a)$ – for all episode $t\in[T]$, for all state-action pairs $(x,a)\in X\times A$, for all instance $j\in[M]$ – as in Theorem 2 but using the true value of adversarial corruption $C$, considering that the counter $N_{t}^{j}(x,a)$ increases on one unit from episode $t$ to $t+1$, if and only if $\mathbb{I}(j_{t}=j)\mathbb{I}_{t}(x,a)=1$, and by applying a Union Bound over all instances $j\in[M]$ namely,

$$ $\widehat{\xi}_{t,j}(x,a):=\min\left\{1,\sqrt{\frac{1}{2\max\{N_{t}^{j}(x,a),1 \}}\ln\left(\frac{2mMT|X||A|}{\delta}\right)}+\frac{C}{\max\{N_{t}^{j}(x,a),1 \}}+\frac{C}{T}\right\},$ (23) $$

By Corollary 2, and applying a Union Bound on instances $j\in[M]$ simultaneously $\forall t\in[T],\forall i\in[m],\forall(x,a)\in X\times A,\forall j\in[M]$, with probability at least $1-\delta$, it holds:

$$ $\widehat{g}_{t,i}^{j}(x,a)+\widehat{\xi}_{t,j}(x,a)\geq g_{i}^{\circ}(x,a).$ (24) $$

Resorting to the definition of $\widehat{V}_{T}$, we obtain that, with probability at least $1-\delta$, under $\mathcal{E}_{\widehat{q}}$:

$$ $\displaystyle\widehat{V}_{T}=\sum_{t\in[T]}\sum_{j\in[M]}\frac{w_{t,j}\mathbb{ I}(j_{t}=j)}{w_{t,j}+\gamma}\sum_{i\in[m]}\left[\widehat{g}^{j}_{t,i}{}^{\top} \widehat{q}_{t}^{j}-\alpha_{i}\right]^{+}$ $\displaystyle=\sum_{t\in[T]}\sum_{j\in[M]}\frac{w_{t,j}\mathbb{I}(j_{t}=j)}{w_ {t,j}+\gamma}\sum_{i\in[m]}\left[(\widehat{g}_{t,i}^{j}{}^{\top}q_{t}^{j}+ \widehat{\xi}_{t,j}^{\ \top}q_{t}^{j}-\alpha_{i})-\widehat{\xi}_{t,j}^{\ \top} q_{t}^{j}-\widehat{g}_{t,i}^{j}{}^{\top}(q_{t}^{j}-\widehat{q}_{t}^{j})\right] ^{+}$ $\displaystyle\geq\sum_{t\in[T]}\sum_{j\in[M]}\frac{w_{t,j}\mathbb{I}(j_{t}=j)} {w_{t,j}+\gamma}\sum_{i\in[m]}\left(\left[(\widehat{g}_{t,i}^{j}+\widehat{\xi} _{t,j})^{\top}q_{t}^{j}-\alpha_{i}\right]^{+}-\widehat{\xi}_{t,j}^{\ \top}q_{t }^{j}-\widehat{g}_{t,i}^{j}{}^{\top}|q_{t}^{j}-\widehat{q}_{t}^{j}|\right)$ (25a) $\displaystyle\geq\sum_{t\in[T]}\sum_{j\in[M]}\frac{w_{t,j}\mathbb{I}(j_{t}=j)} {w_{t,j}+\gamma}\sum_{i\in[m]}\left(\left[g_{i}^{\circ\top}q_{t}^{j}-\alpha_{i }\right]^{+}-\widehat{\xi}_{t,j}^{\ \top}q_{t}^{j}-\|q_{t}^{j}-\widehat{q}_{t} ^{j}\|_{1}\right)$ (25b) $\displaystyle\geq\sum_{t\in[T]}\sum_{j\in[M]}\frac{w_{t,j}\mathbb{I}(j_{t}=j)} {w_{t,j}+\gamma}\sum_{i\in[m]}\left(\left[\mathbb{E}[g_{t,i}]^{\top}q_{t}^{j}- \alpha_{i}\right]^{+}-\widehat{\xi}_{t,j}^{\ \top}q_{t}^{j}\right)-\sum_{t\in[ T]}\sum_{j\in[M]}\frac{w_{t,j}\mathbb{I}(j_{t}=j)}{w_{t,j}+\gamma}$ $\displaystyle\mkern 80.0mu\cdot\sum_{i\in[m]}\left[(g^{\circ}_{i}-\mathbb{E}[g _{t,i}])^{\top}q_{t}^{j}\right]^{+}-\mathcal{O}\left(mL|X|\sqrt{|A|T\ln\left( \frac{T|X||A|}{\delta}\right)}\right),$ (25c) $$

where Inequality (25a) holds since $[a-b]^{+}\geq[a]^{+}-b,~{}a\in\mathbb{R},b\in\mathbb{R}_{\geq 0}$, Inequality (25b) follows from Inequality (24) and since, by definition, $\widehat{g}_{t,i}^{j}(x,a)\leq 1,\forall(x,a)\in X\times A,\forall i\in[m],
\forall t\in[T],\forall j\in[M]$ and, finally, Inequality (25c) holds under event $\mathcal{E}_{\widehat{q}}$ by Lemma 20 after noticing that $\sum_{t\in[T]}\sum_{j\in[M]}\frac{w_{t,j}\mathbb{I}(j_{t}=j)}{w_{t,j}+\gamma}
\sum_{i\in[m]}\lVert q_{t}^{j}-\widehat{q}_{t}^{j}\rVert_{1}\leq\sum_{t\in[T]}
\sum_{j\in[M]}\mathbb{I}(j_{t}=j)\left(\frac{w_{t,j}}{w_{t,j}+\gamma}\right)
\sum_{i\in[m]}\lVert q_{t}^{j}-\widehat{q}_{t}^{j}\rVert_{1}\leq m\sum_{t\in[T
]}\lVert q_{t}^{j_{t}}-\widehat{q}_{t}^{\ j_{t}}\rVert_{1}$.

We will bound the previous terms separately.

Lower-bound to $\sum_{t\in[T]}\sum_{j\in[M]}\frac{w_{t,j}\mathbb{I}(j_{t}=j)}{w_{t,j}+\gamma}
\sum_{i\in[m]}\left[\mathbb{E}[g_{t,i}]^{\top}q_{t}^{j}-\alpha_{i}\right]^{+}$.

We bound the term by the Azuma-Hoeffding inequality. Indeed, with probability at least $1-\delta$, it holds:

$$ $\displaystyle\sum_{t\in[T]}$ $\displaystyle\sum_{j\in[M]}\frac{w_{t,j}\mathbb{I}(j_{t}=j)}{w_{t,j}+\gamma} \sum_{i\in[m]}\left[\mathbb{E}[g_{t,i}]^{\top}q_{t}^{j}-\alpha_{i}\right]^{+}$ $\displaystyle\geq\left(\sum_{t\in[T]}\sum_{j\in[M]}\frac{w_{t,j}^{2}}{w_{t,j}+ \gamma}\sum_{i\in[m]}\left[\mathbb{E}[g_{t,i}]^{\top}q_{t}^{j}-\alpha_{i} \right]^{+}\right)-mL\sqrt{2T\ln\left(\frac{1}{\delta}\right)},$ $$

where we used the following upper-bound to the martingale sequence:

$$ $\displaystyle\sum_{j\in[M]}\frac{w_{t,j}\mathbb{I}(j_{t}=j)}{w_{t,j}+\gamma} \sum_{i\in[m]}\left[\mathbb{E}[g_{t,i}]^{\top}q_{t}^{j}-\alpha_{i}\right]^{+}$ $\displaystyle\leq\sum_{j\in[M]}\mathbb{I}(j_{t}=j)\left(\frac{w_{t,j}}{w_{t,j} +\gamma}\right)\sum_{i\in[m]}\left[\mathbb{E}[g_{t,i}]^{\top}q_{t}^{j}\right]^ {+}$ $\displaystyle\leq\sum_{j\in[M]}\mathbb{I}(j_{t}=j)\sum_{i\in[m]}\lVert q_{t}^{ j}\rVert_{1}$ $\displaystyle\leq m\lVert q_{t}^{j_{t}}\rVert_{1}$ $\displaystyle\leq mL.$ $$

Moreover, we observe the following bounds:

$$ $\displaystyle\sum_{t\in[T]}\sum_{j\in[M]}w_{t,j}\sum_{i\in[m]}\left[\mathbb{E} [g_{t,i}]^{\top}q_{t}^{j}-\alpha_{i}\right]^{+}-\sum_{t\in[T]}\sum_{j\in[M]} \frac{w_{t,j}^{2}}{w_{t,j}+\gamma}\sum_{i\in[m]}$ $\displaystyle\left[\mathbb{E}[g_{t,i}]^{\top}q_{t}^{j}-\alpha_{i}\right]^{+}$ $\displaystyle\leq\gamma TLm,$ $$

and,

$$ $\sum_{t\in[T]}\sum_{j\in[M]}w_{t,j}\sum_{i\in[m]}\left[\mathbb{E}[g_{t,i}]^{ \top}q_{t}^{j}-\alpha_{i}\right]^{+}\geq\sum_{j\in[M]}\max_{i\in[m]}\sum_{t\in [T]}w_{t,j}\left[\mathbb{E}[g_{t,i}]^{\top}q_{t}^{j}-\alpha_{i}\right]^{+}.$ $$

Combining the previous results, we obtain, with probability at least $1-\delta$:

$$ $\displaystyle\sum_{t\in[T]}\sum_{j\in[M]}$ $\displaystyle\frac{w_{t,j}\mathbb{I}(j_{t}=j)}{w_{t,j}+\gamma}\sum_{i\in[m]} \left[\mathbb{E}[g_{t,i}]^{\top}q_{t}^{j}-\alpha_{i}\right]^{+}$ $\displaystyle\geq\sum_{j\in[M]}\max_{i\in[m]}\sum_{t\in[T]}w_{t,j}\left[ \mathbb{E}[g_{t,i}]^{\top}q_{t}^{j}-\alpha_{i}\right]^{+}-\left(\gamma TLm+Lm \sqrt{2T\ln\left(\frac{1}{\delta}\right)}\right).$ $$

Upper-bound to $\sum_{t\in[T]}\sum_{j\in[M]}\frac{w_{t,j}\mathbb{I}(j_{t}=j)}{w_{t,j}+\gamma}
\sum_{i\in[m]}\widehat{\xi}_{t,j}^{\ \top}q_{t}^{j}$.

We bound the term noticing that, with probability at least $1-\delta$, it holds:

$$ $\displaystyle\sum_{t\in[T]}\sum_{j\in[M]}$ $\displaystyle\frac{w_{t,j}\mathbb{I}(j_{t}=j)}{w_{t,j}+\gamma}\sum_{i\in[m]} \widehat{\xi}_{t,j}^{\ \top}q_{t}^{j}$ $\displaystyle\leq\sum_{j\in[M]}m\max_{i\in[m]}\sum_{t\in[T]}\frac{w_{t,j} \mathbb{I}(j_{t}=j)}{w_{t,j}+\gamma}\widehat{\xi}_{t,j}^{\ \top}q_{t}^{j}$ $\displaystyle\leq\sum_{j\in[M]}m\max_{i\in[m]}\sum_{t\in[T]}\sum_{x,a}\mathbb{ I}(j_{t}=j)\mathbb{I}_{t}(x,a)\widehat{\xi}_{t,j}(x,a)+L\sqrt{2T\ln\frac{1}{ \delta}}$ $\displaystyle=\mathcal{O}\left(m\sqrt{|X||A|LT\ln\left(\frac{mMT|X||A|}{\delta }\right)}+m\ln T|X||A|C+L\sqrt{T\ln\frac{1}{\delta}}\right),$ $$

where we employed the Azuma-Hoeffding inequality and where the last step holds following the proof of Theorem 2.

Upper-bound to $\sum_{t\in[T]}\sum_{j\in[M]}\frac{w_{t,j}\mathbb{I}(j_{t}=j)}{w_{t,j}+\gamma}
\sum_{i\in[m]}\left[\left(g^{\circ}_{i}-\mathbb{E}[g_{t,i}]\right)^{\top}q_{t}
^{j}\right]^{+}$.

We simply bound the quantity of interest as follows:

$$ $\displaystyle\sum_{t\in[T]}\sum_{j\in[M]}\frac{w_{t,j}\mathbb{I}(j_{t}=j)}{w_{ t,j}+\gamma}\sum_{i\in[m]}$ $\displaystyle\left[\left(g_{i}^{\circ}-\mathbb{E}[g_{t,i}]\right)^{\top}q_{t}^ {j}\right]^{+}$ $\displaystyle\leq m\max_{i\in[m]}\sum_{t\in[T]}\sum_{j\in[M]}\mathbb{I}(j_{t}= j)\lVert g_{i}^{\circ}-\mathbb{E}[g_{t,i}]\rVert_{1}$ $\displaystyle\leq mC.$ $$

Final result.
To conclude we employ the Azuma-Hoeffding inequality on the violation definition, obtaining, with probability at least $1-\delta$:

$$ $\displaystyle V_{T}$ $\displaystyle=\sum_{j\in[M]}\max_{i\in[m]}\sum_{t\in[T]}\mathbb{I}(j_{t}=j) \left[\mathbb{E}[g_{t,i}]^{\top}q_{t}^{j}-\alpha_{i}\right]^{+}$ $\displaystyle\leq\sum_{j\in[M]}\max_{i\in[m]}\sum_{t\in[T]}w_{t,j}\left[ \mathbb{E}[g_{t,i}]^{\top}q_{t}^{j}-\alpha_{i}\right]^{+}+L\sqrt{2T\ln\left( \frac{1}{\delta}\right)}.$ $$

Thus, plugging the previous bounds in Equation (25c), we obtain, with probability at least $1-10\delta$:

$$ $\displaystyle V_{T}-\widehat{V}_{T}$ $\displaystyle\leq\sum_{j\in[M]}\max_{i\in[m]}\sum_{t\in[T]}\mathbb{I}(j_{t}=j) \left[\mathbb{E}[g_{t,i}]^{\top}q_{t}^{j}-\alpha_{i}\right]^{+}-\sum_{t\in[T]} \sum_{j\in[M]}\frac{w_{t,j}\mathbb{I}(j_{t}=j)}{w_{t,j}+\gamma}\sum_{i\in[m]} \left[\widehat{g}^{j}_{t,i}{}^{\top}\widehat{q}_{t}^{j}-\alpha_{i}\right]^{+}$ $\displaystyle\leq m\sum_{t\in[T]}\sum_{j\in[M]}\frac{w_{t,j}\mathbb{I}(j_{t}=j )}{w_{t,j}+\gamma}\widehat{\xi}_{t,j}^{\ \top}q_{t}^{j}+\sum_{t\in[T]}\sum_{j \in[M]}\frac{w_{t,j}\mathbb{I}(j_{t}=j)}{w_{t,j}+\gamma}\sum_{i\in[m]}\left[ \frac{1}{T}\sum_{\tau\in[T]}(\mathbb{E}[g_{\tau,i}]-\mathbb{E}[g_{t,i}])^{\top }q_{t}^{j}\right]^{+}$ $\displaystyle\mkern 200.0mu+\gamma TLm+2Lm\sqrt{2T\left(\frac{1}{\delta}\right )}+\mathcal{O}\left(mL|X|\sqrt{|A|T\ln\left(\frac{T|X||A|}{\delta}\right)}\right)$ $\displaystyle=\mathcal{O}\left(mL|X|\sqrt{|A|T\ln\left(\frac{mMT|X||A|}{\delta }\right)}+m\ln(T)|X||A|C+\gamma TLM\right)$ $$

This concludes the proof.
∎

We proceed bounding the estimated violation attained by the optimal instance $j^{*}$.

###### Lemma 16 .

For any $\delta\in(0,1)$, with probability at least $1-16\delta$, it holds:

$$ $\displaystyle\widehat{V}_{T,j^{*}}$ $\displaystyle\leq\mathcal{O}\left(mL|X|\sqrt{|A|T\ln\left(\frac{mMT|X||A|}{ \delta}\right)}+m\beta_{6}C+m\ln(T)|X||A|C+Lm\frac{\ln\left(\frac{M}{\delta} \right)}{2\gamma}\right)$ $\displaystyle\mkern 350.0mu+m\sqrt{\beta_{4}T}\nu_{T,j^{*}}+m\beta_{5}\nu_{T,j ^{*}}.$ $$

###### Proof.

We start by observing that with, probability at least $1-\delta$ under $\mathcal{E}_{\widehat{q}}$, the quantity of interest is bounded as follows:

$$ $\displaystyle\sum_{t\in[T]}\frac{\mathbb{I}(j_{t}=j^{*})}{w_{t,j^{*}}+\gamma} \sum_{i\in[m]}\left[\widehat{g}_{t,i}^{j^{*}}{}^{\top}\widehat{q}_{t}^{j^{*}}- \alpha_{i}\right]^{+}$ $\displaystyle\leq\sum_{t\in[T]}\frac{\mathbb{I}(j_{t}=j^{*})}{w_{t,j^{*}}+ \gamma}\sum_{i\in[m]}\left(\left[\widehat{g}_{t,i}^{j^{*}}{}^{\top}(\widehat{q }_{t}^{j^{*}}-{q}_{t}^{j^{*}})+\widehat{g}_{t,i}^{j^{*}}{}^{\top}{q}_{t}^{j^{* }}-\widehat{\xi}_{t,j^{*}}^{\ \top}q_{t}^{j^{*}}-\alpha_{i}\right]^{+}+ \widehat{\xi}_{t,j^{*}}^{\ \top}q_{t}^{j^{*}}\right)$ (26a) $\displaystyle\leq\sum_{t\in[T]}\frac{\mathbb{I}(j_{t}=j^{*})}{w_{t,j^{*}}+ \gamma}\sum_{i\in[m]}\Bigg{(}\left[\mathbb{E}[g_{t,i}]^{\top}q_{t}^{j^{*}}- \alpha_{i}\right]^{+}+\widehat{\xi}_{t,j^{*}}^{\ \top}{q_{t}^{j^{*}}}+$ $\displaystyle\mkern 240.0mu+\left[g^{\circ}_{i}{}^{\top}q_{t}^{j^{*}}-\mathbb{ E}[g_{t,i}]^{\top}q_{t}^{j^{*}}\right]^{+}+\lVert\widehat{q}_{t}^{j^{*}}-{q}_{ t}^{j^{*}}\rVert_{1}\Bigg{)}$ (26b) $\displaystyle\leq\sum_{t\in[T]}\frac{\mathbb{I}(j_{t}=j^{*})}{w_{t,j^{*}}+ \gamma}\sum_{i\in[m]}\left(\left[\mathbb{E}[g_{t,i}]^{\top}q_{t}^{j^{*}}- \alpha_{i}\right]^{+}+\widehat{\xi}_{t,j^{*}}^{\ \top}q_{t}^{j^{*}}+\left[ \left(g^{\circ}_{i}-\mathbb{E}[g_{t,i}]\right)^{\top}q_{t}^{j^{*}}\right]^{+}\right)$ $\displaystyle\mkern 370.0mu+\mathcal{O}\left(L|X|\sqrt{|A|T\ln\left(\frac{T|X| |A|}{\delta}\right)}\right),$ (26c) $$

where Inequality (26a) holds since $[a+b]^{+}\leq[a]^{+}+[b]^{+},~{}\forall a,b\in\mathbb{R}$ and by the definition of $\widehat{\xi}_{t,j^{*}}$ (see Equation (23)) which implies that all its elements are positive, Inequality (26b) holds with probability at least $1-\delta$ by Corollary 2 and by union bound over $M$, and since that $\lVert\widehat{g}_{t,i}\rVert_{\infty}\leq 1$ and Inequality (26c) holds with probability at least $1-6\delta$ by Lemma 20.

Upper-bound to $\sum_{t\in[T]}\frac{\mathbb{I}(j_{t}=j^{*})}{w_{t,j^{*}}+\gamma}\sum_{i\in[m]}
\left[\left(g^{\circ}_{i}-\mathbb{E}[g_{t,i}]\right)^{\top}q_{t}^{j^{*}}\right
]^{+}$.

It is immediate to bound the quantity of interest employing the definition of corruption $C$ and by Lemma 18. Indeed, with probability at least $1-\delta$:

$$ $\sum_{t\in[T]}\frac{\mathbb{I}(j_{t}=j^{*})}{w_{t,j^{*}}+\gamma}\sum_{i\in[m]} \left[\left(g^{\circ}_{i}-\mathbb{E}[g_{t,i}]\right)^{\top}q_{t}^{j^{*}}\right ]^{+}\leq Lm\sqrt{2T\ln\left(\frac{1}{\delta}\right)}+mC.$ $$

Upper-bound to $\sum_{t\in[T]}\frac{\mathbb{I}(j_{t}=j^{*})}{w_{t,j^{*}}+\gamma}\sum_{i\in[m]}
\left[\mathbb{E}[g_{t,i}]^{\top}q_{t}^{j^{*}}-\alpha_{i}\right]^{+}$.

We bound the quantity of interest as follows. With probability at least $1-11\delta$, it holds:

$$ $\displaystyle\sum_{t\in[T]}$ $\displaystyle\frac{\mathbb{I}(j_{t}=j^{*})}{w_{t,j^{*}}+\gamma}\sum_{i\in[m]} \left[\mathbb{E}[g_{t,i}]^{\top}q_{t}^{j^{*}}-\alpha_{i}\right]^{+}$ $\displaystyle\leq m\sqrt{\beta_{4}T}\nu_{T,j^{*}}+m\beta_{5}\nu_{T,j^{*}}+2m \beta_{6}C+Lm\frac{\ln\left(\frac{M}{\delta}\right)}{2\gamma},$ (27a) $$

thank to Corollary 5 and Corollary 6 .

Upper-bound to $\sum_{t\in[T]}\frac{\mathbb{I}(j_{t}=j^{*})}{w_{t,j^{*}}+\gamma}\sum_{i\in[m]}
\widehat{\xi}_{t,j^{*}}^{\ \top}q_{t}^{j^{*}}$.

First, notice that, with probability at least $1-\delta$, it holds:

$$ $\sum_{t\in[T]}\frac{\mathbb{I}(j_{t}=j^{*})}{w_{t,j^{*}}+\gamma}\sum_{i\in[m]} \widehat{\xi}_{t,j^{*}}^{\ \top}q_{t}^{j^{*}}-m\sum_{t\in[T]}\mathbb{I}(j_{t}= j^{*})\widehat{\xi}_{t,j^{*}}^{\ \top}q_{t}^{j^{*}}\leq L\sqrt{2T\ln\left( \frac{1}{\delta}\right)},$ $$

where we employed Lemma 18. Now we observe that, with probability at least $1-\delta$, it holds:

$$ $\displaystyle\sum_{t=1}^{T}\widehat{\xi}_{t-1,j^{*}}^{\ \top}q_{t}\mathbb{I}(j _{t}=j^{*})$ $\displaystyle=\sum_{t=1}^{T}\sum_{x,a}\widehat{\xi}_{t-1,j^{*}}(x,a)q_{t}^{j^{ *}}(x,a)\mathbb{I}(j_{t}=j^{*})$ $\displaystyle\leq\sum_{t=1}^{T}\sum_{x,a}\widehat{\xi}_{t-1,j^{*}}(x,a)\mathbb {I}_{t}(x,a)\mathbb{I}(j_{t}=j^{*})+L\sqrt{2T\ln\frac{1}{\delta}}$ $\displaystyle=\mathcal{O}\left(\sqrt{|X||A|LT\ln\left(\frac{mMT|X||A|}{\delta} \right)}+\ln(T)|X||A|C+L\sqrt{T\ln\frac{1}{\delta}}\right),$ $$

where employed the same steps as in the proof of Theorem 2, considering that the counter increases if and only if $\mathbb{I}_{t}(x,a)\mathbb{I}(j_{t}=j^{*})=1$.

Combining the previous bounds concludes the proof.
∎

###### Lemma 12 .

###### Proof.

###### Lemma 13 .

###### Proof.

###### Lemma 14 .

###### Proof.

###### Lemma 15 .

###### Proof.

###### Lemma 16 .

###### Proof.

### F.3 Main results

In the following, we provide the main results attained by Algorithm 3 in terms of regret and violations.
We start providing the regret bound and the related proof.
See 6

###### Proof.

Employing algorithm 3, with probability at least $1-14\delta$, it holds:

$$ $\displaystyle R_{T}$ $\displaystyle=\sum_{t\in[T]}\overline{r}^{\top}q^{*}-\sum_{t\in[T]}\overline{r }^{\top}q_{t}$ $\displaystyle=\sum_{t\in[T]}\overline{r}^{\top}(q^{*}-q_{t}^{j^{*}})+\sum_{t \in[T]}\overline{r}^{\top}(q_{t}^{j^{*}}-q_{t})$ $\displaystyle=\sqrt{\beta_{1}T}\nu_{T,j^{*}}+\beta_{2}\nu_{T,j^{*}}+2\beta_{3} C+\sum_{t\in[T]}\overline{r}^{\top}(q_{t}^{j^{*}}-q_{t})$ (28a) $\displaystyle\leq\sqrt{\beta_{1}T}\nu_{T,j^{*}}+\beta_{2}\nu_{T,j^{*}}+2\beta_ {3}C+2C-\frac{Lm+1}{\rho}\widehat{V}_{T}+\frac{Lm+1}{\rho}\widehat{V}_{T,j^{*}}$ $\displaystyle\mkern 50.0mu-(\sqrt{\beta_{1}}+\frac{m(Lm+1)}{\rho}\sqrt{\beta_{ 4}})\sqrt{T}\nu_{T,j*}-\left(\beta_{2}+\frac{m(mL+1)}{\rho}\beta_{5}\right)\nu _{T,j^{*}}$ $\displaystyle\mkern 50.0mu+\mathcal{O}\bigg{(}\frac{M\ln T}{\eta}+\eta~{}{m^{4 }L^{4}TM}+\eta~{}M\ln(T)m^{4}L^{2}\left(\beta_{2}^{2}+\beta_{5}^{2}\right)$ $\displaystyle\mkern 50.0mu+\eta T(\beta_{1}+L^{2}m^{4}\beta_{4})M\log(T)+ \gamma TLM+L\sqrt{T\ln\left(\nicefrac{{1}}{{\delta}}\right)}+\frac{Lm}{\gamma} \ln\left(\nicefrac{{1}}{{\delta}}\right)\bigg{)}.$ (28b) $$

where Inequality (28a) hold with probability at least $1-11\delta$ by Corollary 7,Inequality (28b) holds with probability at least $1-3\delta$ thanks to Lemma 14 and to the following reasoning, which holds with probability at least $1-\delta$:

$$ $\displaystyle\sum_{t\in[T]}\overline{r}^{\top}(q_{t}^{j*}-q_{t})$ $\displaystyle=\sum_{t\in[T]}(\overline{r}-\mathbb{E}[r_{t}])^{\top}(q_{t}^{j*} -q_{t})+\sum_{t\in[T]}\mathbb{E}[r_{t}]^{\top}(q_{t}^{j*}-q_{t})$ $\displaystyle\leq\sum_{t\in[T]}\lVert\overline{r}-\mathbb{E}[r_{t}]\rVert_{1}+ \sum_{t\in[T]}\mathbb{E}[r_{t}]^{\top}\left(q_{t}^{j*}-q_{t}\right)$ (29a) $\displaystyle\leq 2C+\sum_{t\in[T]}\mathbb{E}[r_{t}]^{\top}\left(q_{t}^{j*}-q_ {t}\right)$ (29b) $\displaystyle\leq 2C+\sum_{t\in[T]}\mathbb{E}[r_{t}]^{\top}q_{t}^{j*}-\sum_{t \in[T]}\sum_{j\in[M]}w_{t,j}\mathbb{E}[r_{t}]^{\top}q_{t}^{j}+L\sqrt{2T\ln( \nicefrac{{1}}{{\delta}})}$ (29c) $$

where Inequality (29a) holds since $|q_{t}(x,a)-q_{t}^{j^{*}}(x,a)|\leq 1,~{}\forall(x,a)\in X\times A$, where Inequality (29b) holds by definition of $C$, and where Inequality (29c) use Azuma-Hoeffding inequality.

We can apply Lemma 16 to bound $\widehat{V}_{T,j^{*}}$ with high probability. In fact we observe that with probability at least $1-16\delta$, it holds:

$$ $\displaystyle\frac{Lm+1}{\rho}\widehat{V}_{T,j^{*}}$ $\displaystyle\leq\mathcal{O}\left(m^{2}L^{2}|X|\sqrt{|A|T\ln\left(\frac{mMT|X| |A|}{\delta}\right)}+m^{2}L\beta_{6}C+m^{2}L\ln(T)|X||A|C+L^{2}m^{2}\frac{\ln \left(\frac{M}{\delta}\right)}{2\gamma}\right)$ $\displaystyle\mkern 200.0mu+\frac{(Lm+1)m}{\rho}\beta_{5}\nu_{T,j^{*}}+\frac{m (Lm+1)}{\rho}\sqrt{\beta_{4}T}\nu_{T,j^{*}}.$ $$

Finally, combining the previous results and by Union Bound, with probability at least $1-30\delta$, it holds:

$$ $\displaystyle R_{T}+\frac{Lm+1}{\rho}\widehat{V}_{T}$ $\displaystyle\leq\mathcal{O}\bigg{(}\frac{M\ln T}{\eta}+\eta~{}{m^{4}L^{4}TM}+ \eta~{}M\ln(T)m^{4}L^{2}(\beta_{2}^{2}+\beta_{5}^{2})+\eta T(\beta_{1}+L^{2}m^ {4}\beta_{4})M\log(T)$ $\displaystyle\quad+\gamma TLM+L\sqrt{T\ln\left(\nicefrac{{1}}{{\delta}}\right) }+\frac{Lm}{\gamma}\ln\left(\nicefrac{{1}}{{\delta}}\right)$ $\displaystyle\quad+m^{2}L^{2}|X|\sqrt{|A|T\ln\left(\frac{mMT|X||A|}{\delta} \right)}+mL\beta_{6}C+\beta_{3}C+m^{2}L|X||A|\ln(T)C\bigg{)}$ (30) $$

which concludes the proof after observing that $\widehat{V}_{T}\geq 0$, by definition, and setting $\gamma=\sqrt{\frac{\ln(M/\delta)}{TM}}$, $\eta\leq\frac{1}{2\Lambda m\left(\sqrt{\beta_{1}T}+\beta_{2}+\beta_{5}+\sqrt{
\beta_{4}T}\right)}$.
∎

We conclude the section providing the violations bound and the related proof.
See 5

###### Proof.

Starting from Inequality (30), in order to obtain the final violations bound, it is necessary to find an upper bound for $-R_{T}$. We proceed as follows,

$$ $\displaystyle\overline{r}^{\top}q^{*}$ $\displaystyle=\text{OPT}_{\overline{r},\overline{G},\alpha}$ (31a) $\displaystyle=\max_{q\in\Delta(P)}\left(\overline{r}^{\top}q-\frac{L}{\rho} \sum_{i\in[m]}\left[\overline{G}_{i}^{\top}q-\alpha_{i}\right]^{+}\right)$ (31b) $\displaystyle\geq\overline{r}^{\top}q_{t}-\frac{L}{\rho}\sum_{i\in[m]}\left[ \overline{G}_{i}^{\top}q_{t}-\alpha_{i}\right]^{+},$ $$

where Equality (31a) holds since $q^{*}$ is the feasible occupancy that maximizes the reward vector $\overline{r}$ and Equality (31b) holds by Theorem 4 . This implies $\overline{r}^{\top}q_{t}-\overline{r}^{\top}q^{*}\leq\frac{L}{\rho}\sum_{i\in[
m]}\left[\overline{G}_{i}^{\top}q_{t}-\alpha_{i}\right]^{+}$.
Moreover, it holds:

$$ $\displaystyle\sum_{t\in[T]}$ $\displaystyle\sum_{i\in[m]}\left[\overline{G}_{i}^{\top}q_{t}-\alpha_{i}\right ]^{+}$ $\displaystyle\leq\sum_{t\in[T]}\left(\sum_{i\in[m]}\left[\mathbb{E}[g_{t,i}]^{ \top}q_{t}-\alpha_{i}\right]^{+}+\sum_{i\in[m]}\left[(\overline{G}_{i}-\mathbb {E}[g_{t,i}])^{\top}q_{t}\right]^{+}\right)$ (32a) $\displaystyle\leq\sum_{t\in[T]}\left(\sum_{i\in[m]}\left[\mathbb{E}[g_{t,i}]^{ \top}q_{t}-\alpha_{i}\right]^{+}+\sum_{i\in[m]}\left\lVert\overline{G}_{i}- \mathbb{E}[g_{t,i}]\right\rVert_{1}\right)$ (32b) $\displaystyle\leq\sum_{t\in[T]}\left(\sum_{i\in[m]}\left[\mathbb{E}[g_{t,i}]^{ \top}q_{t}-\alpha_{i}\right]^{+}+\sum_{i\in[m]}\left(\left\lVert\overline{G}_{ i}-g^{\circ}_{i}\right\rVert_{1}+\left\lVert g^{\circ}_{i}-\mathbb{E}[g_{t,i}] \right\rVert_{1}\right)\right)$ $\displaystyle\leq mV_{T}+2mC,$ (32c) $$

where Inequality (32a) holds since $[a+b]^{+}\leq[a]^{+}+[b]^{+},a\in\mathbb{R},b\in\mathbb{R}$, Inequality (32b) holds since $q_{t}(x,a)\leq 1\forall t\in[T],\forall(x,a)\in X\times A$, and finally Inequality (32c) holds by definition of $C$ and $V_{T}$ and noticing that $m\max_{i\in[m]}a_{i}\geq\sum_{i\in[m]}a_{i},~{}\forall\{a_{i}\}_{i\in[m]}
\subset\mathbb{R}^{m}$.
Thus, combining the previous bounds we lower bound the quantity of interest as follows:

$$ $\displaystyle R_{T}+\frac{Lm+1}{\rho}V_{T}$ $\displaystyle=\sum_{t\in[T]}\mathbb{E}[r_{t}]^{\top}\left(q^{*}-q_{t}\right)+ \frac{Lm+1}{\rho}V_{T}$ $\displaystyle=\sum_{t\in[T]}\left(\mathbb{E}[r_{t}]-\overline{r}\right)^{\top} (q^{*}-q_{t})+\sum_{t\in[T]}\overline{r}^{\top}(q^{*}-q_{t})+\frac{Lm+1}{\rho} V_{T}$ $\displaystyle\geq-\sum_{t\in[T]}\left\lVert\mathbb{E}[r_{t}]-\overline{r} \right\rVert_{1}+\sum_{t\in[T]}\overline{r}^{\top}(q^{*}-q_{t})+\frac{Lm+1}{ \rho}V_{T}$ (33a) $\displaystyle\geq-2C-\frac{L}{\rho}\left(mV_{T}+2mC\right)+\frac{Lm+1}{\rho}V_ {T}$ (33b) $\displaystyle=-2C-\frac{2LmC}{\rho}+V_{T}\left(\frac{Lm+1}{\rho}-\frac{Lm}{ \rho}\right)$ $\displaystyle=\frac{1}{\rho}V_{T}-\left(2C+\frac{2LmC}{\rho}\right),$ (33c) $$

where Inequality (33a) holds since $\underline{v}^{\top}\underline{w}\geq-\lVert\underline{v}\rVert_{1}\lVert
\underline{w}\rVert_{\infty},\forall\underline{v},\underline{w}\in\mathbb{R}^{
p},p\in\mathbb{N}$, and
where Inequality (33b) holds since $\overline{r}^{\top}(q^{*}-q_{t})\geq-\frac{L}{\rho}\sum_{i\in[m]}\left[
\overline{G}_{i}^{\top}q_{t}-\alpha_{i}\right]^{+}\geq-\left(mV_{T}+2mC\right)$ and by definition of $C$.
Thus, rearranging Inequality (33c), we finally bound the cumulative violation as follows:

$$ $\displaystyle V_{T}$ $\displaystyle\leq 2\rho C+2LmC+\rho R_{T}+(Lm+1)V_{T}$ $\displaystyle=2\rho C+2LmC+(Lm+1)\left(V_{T}-\widehat{V}_{T}\right)+\rho\left( R_{T}+\frac{Lm+1}{\rho}\widehat{V}_{T}\right)$ $\displaystyle\leq\mathcal{O}\Bigg{(}m^{2}L^{2}|X|\sqrt{|A|T\ln\left(\frac{mMT| X||A|}{\delta}\right)}+m^{2}L\ln(T)|X||A|C+\gamma mTL^{2}M\Bigg{)}$ $\displaystyle\mkern 400.0mu+\mathcal{O}\left(R_{T}+\frac{Lm+1}{\rho}\widehat{V }_{T}\right),$ $$

where the last inequality holds by Equation (30) and by Lemma 15, with probability at least $1-4\delta$ under $\mathcal{E}_{\widehat{q}}$. Employing a Union Bound, setting $\gamma=\sqrt{\frac{\ln(M/\delta)}{TM}}$ and $\eta\leq\frac{1}{2\Lambda m\left(\sqrt{\beta_{1}T}+\beta_{2}+\beta_{5}+\sqrt{
\beta_{4}T}\right)}$ concludes the proof.
∎

###### Proof.

###### Proof.

## Appendix G Auxiliary lemmas from existing works

In the following section, we provide useful lemma from existing works.

### G.1 Auxiliary lemmas for the FTRL master algorithm

In the following, we provide the optimization bound attained by the FTRL instance employed by Algorithm 3.

###### Lemma 17 ( Jin et al. ( 2024 ) ) .

The FTRL algorithm over a convex subset $\Omega$
of the $(M-1)$-dimensional simplex $\Delta_{M}$ :

$$ $w_{t+1}=\underset{w\in\Omega}{\operatorname*{arg\,min}}\left\{\sum_{\tau\in[t] }\ell_{\tau}^{\top}w+\frac{1}{\eta}\sum_{j\in[M]}\ln\left(\frac{1}{w_{j}} \right)\right\},$ $$

ensures for all $u\in\Omega$:

$$ $\sum_{t\in[T]}\ell_{t}^{\top}(w_{t}-u)\leq\frac{M\ln T}{\eta}+\eta\sum_{t\in[T ]}\sum_{j\in[M]}w_{t,j}^{2}\ell_{t,j}^{2},$ $$

as long as $\eta w_{t,j}\lvert\ell_{t,j}\rvert\leq\frac{1}{2}$ for all $t,j$.

###### Lemma 17 ( Jin et al. ( 2024 ) ) .

### G.2 Auxiliary lemmas for the optimistic loss estimator

In the following, we provide some results related to the optimistic biased estimator of the loss function. Notice that, given any loss vector $\ell_{t}\in[0,1]^{M}$, the following results are provided for $\widehat{\ell}_{t,j}:=\frac{\mathbb{I}_{t}(j)}{w_{t,j}+\gamma_{t}}\ell_{t,j}$, where $j\in[M]$, $\ell_{t,j}$ is the $j$-th component of the loss vector, $\mathbb{I}_{t}(j)$ is the indicator functions which is $1$ when arm $j$ is played and $\gamma_{t}$ is defined as in the following lemmas.

###### Lemma 18 ( Neu ( 2015 ) ) .

Let $(\gamma_{t})$ be a fixed non-increasing sequence with $\gamma_{t}\geq 0$ and let $\alpha_{t,j}$ be nonnegative
$\mathcal{F}_{t-1}$-measurable random variables satisfying $\alpha_{t,j}\leq 2\gamma_{t}$ for all $t$ and $j$. Then, with probability at
least $1-\delta$,

$$ $\sum_{t\in[T]}\sum_{j\in[M]}\alpha_{t,j}\left(\widehat{\ell}_{t,j}-\ell_{t,j} \right)\leq\ln\left(\frac{1}{\delta}\right).$ $$

###### Corollary 5 ( Neu ( 2015 ) ) .

Let $\gamma_{t}=\gamma\geq 0$ for all $t$. With probability at least $1-\delta$,

$$ $\sum_{t\in[T]}\left(\widehat{\ell}_{t,j}-\ell_{t,j}\right)\leq\frac{\ln\left( \frac{M}{\delta}\right)}{2\gamma},$ $$

simultaneously holds for all $j\in[M]$.

###### Lemma 18 ( Neu ( 2015 ) ) .

###### Corollary 5 ( Neu ( 2015 ) ) .

### G.3 Auxiliary lemmas for the transitions estimation

Next, we introduce *confidence sets* for the transition function of a CMDP, by exploiting suitable concentration bounds for estimated transition probabilities.
By letting $M_{t}(x,a,x^{\prime})$ be the total number of episodes up to $t\in[T]$ in which $(x,a)\in X\times A$ is visited and the environment transitions to state $x^{\prime}\in X$, the estimated transition probability at $t$ for $(x,a,x^{\prime})$ is:

$$ $\overline{P}_{t}\left(x^{\prime}|x,a\right)=\frac{M_{t}(x,a,x^{\prime})}{\max \left\{1,N_{t}(x,a)\right\}}.$ $$

Then, the confidence set for $P$ at episode $t\in[T]$ is defined as:

$$ $\displaystyle\mathcal{P}_{t}:=\Bigg{\{}\widehat{P}:\Big{|}$ $\displaystyle\overline{P}_{t}(x^{\prime}|x,a)-\widehat{P}(x^{\prime}|x,a)\Big{ |}\leq\epsilon_{t}(x^{\prime}|x,a),$ $\displaystyle\forall(x,a,x^{\prime})\in X_{k}\times A\times X_{k+1},k\in[0...L -1]\Bigg{\}},$ $$

where $\epsilon_{t}(x^{\prime}|x,a)$ is defined as:

$$ $\epsilon_{t}(x^{\prime}|x,a)\coloneqq 2\sqrt{\frac{\overline{P}_{t}\left(x^{ \prime}|x,a\right)\ln\left({T|X||A|}/{\delta}\right)}{\max\left\{1,N_{t}(x,a)- 1\right\}}}+\frac{14\ln\left({T|X||A|}/{\delta}\right)}{3\max\left\{1,N_{t}(x, a)-1\right\}},$ $$

for some confidence $\delta\in(0,1)$.

Given the estimated transition function space $\mathcal{P}_{t}$, the following result can be proved.

###### Lemma 19 ( Jin et al. ( 2020 ) ) .

With probability at least $1-4\delta$, we have $P\in\mathcal{P}_{t}$ for all $t\in[T]$.

Notice that we refer to the event $P\in\mathcal{P}_{t}$ for all $t\in[T]$ as $\mathcal{E}_{P}$.

We underline that the estimated occupancy measure space by Algorithm 2 is the following:

$$ $\Delta(\mathcal{P}_{t}):=\begin{cases}\forall k,&\underset{x\in X_{k},a\in A,x ^{\prime}\in X_{k+1}}{\sum}q\left(x,a,x^{\prime}\right)=1\\ \forall k,\forall x,&\underset{a\in A,x^{\prime}\in X_{k+1}}{\sum}q\left(x,a,x ^{\prime}\right)=\underset{x^{\prime}\in X_{k-1},a\in A}{\sum}q\left(x^{\prime },a,x\right)\\ \forall k,\forall\left(x,a,x^{\prime}\right),&q\left(x,a,x^{\prime}\right)\leq \left[\overline{P}_{t}\left(x^{\prime}|x,a\right)+\epsilon_{t}\left(x^{\prime} \mid x,a\right)\right]\underset{y\in X_{k+1}}{\sum}q(x,a,y)\\ &q\left(x,a,x^{\prime}\right)\geq\left[\overline{P}_{t}\left(x^{\prime}|x,a \right)-\epsilon_{t}\left(x^{\prime}\mid x,a\right)\right]\underset{y\in X_{k+ 1}}{\sum}q(x,a,y)\\ &q\left(x,a,x^{\prime}\right)\geq 0\\ \end{cases}.$ $$

To conclude, we restate the result which bounds the cumulative distance between the estimated occupancy measure and the real one.

###### Lemma 20 ( Jin et al. ( 2020 ) ) .

With probability at least $1-6\delta$, for any collection of transition functions $\{P_{t}^{x}\}_{x\in X}$ such that $P_{t}^{x}\in\mathcal{P}_{t}$, we have, for all $x$,

$$ $\sum_{t\in[T]}\sum_{x\in X,a\in A}\left|q^{P_{t}^{x},\pi_{t}}(x,a)-q_{t}(x,a) \right|\leq\mathcal{O}\left(L|X|\sqrt{|A|T\ln\left(\frac{T|X||A|}{\delta} \right)}\right).$ $$

###### Lemma 19 ( Jin et al. ( 2020 ) ) .

###### Lemma 20 ( Jin et al. ( 2020 ) ) .

## Appendix H Auxiliary lemmas for stability

In this section we state the results related to the stability of the arm-algorithms when $C$ is not known. The procedure is inspired by Jin et al. () and Agarwal et al. (), but adapted to the case of *Constrained* MDP in high probability. We first give some important definitions. In these definitions we will use $C_{t}$ as the value of adversarial corruption at episode $t\in[T]$, where $C_{t}$ is defined as $C_{t}:=\max\{C_{t}^{G},C_{t}^{r}\}$, which meets the requirement of upper bounding the adversarial corruption at each considered episode. In addition it holds that $\sum_{t\in[T]}C_{t}\leq C_{r}+C_{G}$ or equivalently $C\leq\sum_{t\in[T]}C_{t}\leq 2C$, which does not influence the order of the analysis.

###### Definition 2 .

A CMDP algorithm is corruption-robust if it takes $\theta$ (a guess on the
corruption amount) as input, and achieves for any random stopping time $t^{\prime}\leq T$, whenever $\sum_{t\in[t^{\prime}]}C_{t}<\theta$:

$$ $\sum_{t\in[t^{\prime}]}\overline{r}^{\top}(q^{*}-q_{t})\leq\sqrt{\beta_{1}t^{ \prime}}+\left(\beta_{2}+\beta_{3}\theta\right)\mathbb{I}(t^{\prime}\geq 1),$ $$

and

$$ $\max_{i\in[m]}\sum_{t\in[t^{\prime}]}\left[g_{t,i}^{\top}q_{t}-\alpha_{i} \right]^{+}\leq\sqrt{\beta_{4}t^{\prime}}+\left(\beta_{5}+\beta_{6}\theta \right)\mathbb{I}(t^{\prime}\geq 1).$ $$

Notice that Algorithm 2 is corruption-robust after applying a doubling trick to make it work for any stopping time, with probability at least $1-9\delta$ thank to Theorem 7 and Theorem 9 Furthermore, we introduce the notion of $\alpha$-stability. An algorithm is considered to be $\alpha$-stable, if its regret under condition imposed by Algorithm 3 is of order $\nu_{T}^{\alpha}\cdot\tilde{\mathcal{O}}\left(R_{T}\right)$, where $R_{T}$ is the upper bound on the regret attained by the algorithm if it receives feedback at each episode. In particular, we are interested in the $1$-stability.

###### Definition 3 .

An algorithm is $1$-stable if, under the condition imposed by Algorithm 3, it holds:

$$ $\sum_{t\in[T]}\overline{r}^{\top}(q^{*}-q_{t})\leq\sqrt{\beta_{1}T}\nu_{j,T}+ \beta_{2}\nu_{j,T}+\beta_{3}C,$ $$

and

$$ $\max_{i\in[m]}\sum_{t\in[T]}\left[g_{t,i}^{\top}q_{t}-\alpha_{i}\right]^{+} \leq\sqrt{\beta_{4}T}\nu_{j,T}+\beta_{5}\nu_{j,T}+\beta_{6}C.$ $$

We can use the procedure defined by Algorithm 4 and originally proposed by Jin et al. () to transform a generic corruption robust algorithm to a $1$-stable algorithm. Differently from Jin et al. (), in our setting, we use the natural symmetry between regret and positive cumulative constraints violation to stabilize both the regret and the positive cumulative constraints violation. We have a different bound for $C_{t}$ (value of adversarial corruption at episode $t$): indeed, $C_{t}\leq\max\{\lVert\mathbb{E}[r_{t}]-r^{\circ}\rVert_{1},\max_{i\in[m]}
\lVert\mathbb{E}[g_{t,i}]-g_{i}^{\circ}\rVert_{1}\}$ is bounded by $|X||A|$. Finally, we are interested in obtaining results that hold in high probability rather than in expectation. To do so, we focus on $1$-stability guarantee rather than $1/2$-stability as in Jin et al. () since removing the expectation prevents us from achieving the result above with lower coefficients. We can state the following result.

###### Lemma 21 (Adapted from Jin et al. ( 2024 ) ) .

Given an algorithm which is corruption robust according to Definition 2 with parameters $(\beta_{1},\beta_{2},\beta_{3},\beta_{4},\beta_{5},\beta_{6})$ and $\beta_{1}\geq\mathcal{O}(L^{2}\log(\nicefrac{{T}}{{\delta}}))$, $\beta_{4}\geq\mathcal{O}(L^{2}\log(\nicefrac{{T}}{{\delta}}))$, with probability at least $1-p$ with $p\in(0,1)$, then, it is possible convert it to an $1$-stable algorithm with probability at least $1-p-2\delta$ according to Definition 3 with parameters $(\beta_{1}^{\prime},\beta_{2}^{\prime},\beta_{3}^{\prime},\beta_{4}^{\prime},
\beta_{5}^{\prime},\beta_{6}^{\prime})$ as $\beta_{1}^{\prime}=\mathcal{O}\left(\beta_{1}\right),\beta_{2}^{\prime}=
\mathcal{O}\left(\beta_{2}+\beta_{3}|X||A|\log(\nicefrac{{\log(T)}}{{\delta}})
\right),\beta_{3}^{\prime}=\mathcal{O}\left(\beta_{3}\log(T)\right),\beta_{4}^
{\prime}=\mathcal{O}\left(\beta_{4}\right),\beta_{5}^{\prime}=\mathcal{O}\left
(\beta_{5}+\beta_{6}|X||A|\log(\nicefrac{{\log(T)}}{{\delta}})\right),\beta_{6
}^{\prime}=\mathcal{O}\left(\beta_{6}\log(T)\right)$, employing Algorithm 4.

###### Proof.

Suppose Algorithm 4 is initialized with the true value of adversarial corruption $C$.
We will first prove the result for the regret. We will start by considering a generic instance algorithm $k\in[M]$. Define the quantity $d_{t,k}=\mathbb{I}(w_{t}\in(2^{-k-1},2^{-k}])$ and $h_{t,k}=\mathbb{I}(\text{Instance $k$ receives feedback at episode $t$})$. We observe that with probability at least $1-\left(p+\mathbb{P}\left(\bigcup_{k\in[\log(T)]}\{\sum_{t\in[T]}C_{t}d_{t,k}h
_{t,k}>\theta_{k}\}\right)\right)$ it holds:

$$ $\displaystyle\sum_{t\in[T]}\overline{r}^{\top}(q^{*}-q_{t})d_{t,k}h_{t,k}\leq \sqrt{\beta_{1}\sum_{t\in[T]}d_{t,k}h_{t,k}}+\left(\beta_{2}+\beta_{3}\theta \right)\max_{t\in[T]}d_{t,k},$ $$

by the corruption-robust property of instance $k$.
We study now the quantity $\mathbb{P}\left(\bigcup_{k\in[M]}\{\sum_{t\in[T]}C_{t}d_{t,k}h_{t,k}>\theta_{k
}\}\right)$.
Notice that $\mathbb{E}[h_{t,k}|d_{t,k}]=2^{-k-1}d_{t,k}$, and since $d_{t,k}$ is an indicator function then $\mathbb{E}[h_{t,k}|d_{t,k}]d_{t,k}=\mathbb{E}[h_{t,k}|d_{t,k}]$. In addition, since $\sum_{t\in[T]}C_{t}\leq 2C$, it holds:

$$ $\sum_{t\in[T]}C_{t}\mathbb{E}[h_{t,k}|d_{t,k}]d_{t,k}=2^{-k-1}\sum_{t\in[T]}C_ {t}d_{t,k}\leq 2^{-k}C,$ $$

and with probability at least $1-\nicefrac{{\delta}}{{\log(T)}}$ noticing that $M=\log(T)$:

$$ $\displaystyle\sum_{t\in[T]}C_{t}$ $\displaystyle d_{t,k}h_{t,k}-\sum_{t\in[T]}C_{t}\mathbb{E}[h_{t,k}|d_{t,k}]d_{ t,k}$ $\displaystyle\leq 2\sqrt{\sum_{t\in[T]}C_{t}^{2}d_{t,k}\mathbb{E}[h_{t,k}|d_{t ,k}]\log\left(\frac{\log(T)}{\delta}\right)}+|X||A|\log\left(\frac{\log(T)}{ \delta}\right)$ (34a) $\displaystyle\leq 2\sqrt{|X||A|\sum_{t\in[T]}C_{t}d_{t,k}\mathbb{E}[h_{t,k}|d_ {t,k}]\log\left(\frac{\log(T)}{\delta}\right)}+|X||A|\log\left(\frac{\log(T)}{ \delta}\right)$ (34b) $\displaystyle\leq\sum_{t\in[T]}C_{t}\mathbb{E}[h_{t,k}|d_{t,k}]d_{t,k}+2|X||A| \log\left(\frac{\log(T)}{\delta}\right),$ (34c) $$

where Inequality (34a) holds with probability at least $1-\nicefrac{{\delta}}{{\log(T)}}$ by Freedman inequality, Inequality (34b) holds since $C_{t}\leq|X||A|$, and Inequality (34c) holds by AM-GM inequality.
Therefore, it holds simultaneously for all $k\in[M]$:

$$ $\displaystyle\sum_{t\in[T]}C_{t}d_{t,k}h_{t,k}$ $\displaystyle\leq 2\sum_{t\in[T]}C_{t}\mathbb{E}[h_{t,k}|d_{t,k}]d_{t,k}+2|X|| A|\log\left(\frac{\log(T)}{\delta}\right)$ $\displaystyle\leq 2^{-k+1}C+2|X||A|\log\left(\frac{\log(T)}{\delta}\right)= \theta_{k},$ $$

with probability at least $1-\delta$, so $\mathbb{P}\left(\bigcup_{k\in[M]}\{\sum_{t\in[T]}C_{t}d_{t,k}h_{t,k}>\theta_{k
}\}\right)\leq\delta$.
Moreover, notice that with probability at least $1-p-2\delta$ thanks to the definition of corruption robust and Azuma-Hoeffding inequality, it holds simultaneously for all $k$:

$$ $\displaystyle\sum_{t\in[T]}\overline{r}^{\top}(q^{*}-q_{t})d_{t,k}$ $\displaystyle=\frac{1}{2^{-k-1}}\sum_{t\in[T]}\overline{r}^{\top}(q^{*}-q_{t}) 2^{-k-1}d_{t,k}$ $\displaystyle=\frac{1}{2^{-k-1}}\sum_{t\in[T]}\overline{r}^{\top}(q^{*}-q_{t}) d_{t,k}\mathbb{E}[h_{t,k}\mid d_{t,k}]$ $\displaystyle=\frac{1}{2^{-k-1}}\left(\sum_{t\in[T]}\overline{r}^{\top}(q^{*}- q_{t})d_{t,k}\left(\mathbb{E}[h_{t,k}\mid d_{t,k}]-h_{t,k}\right)+\sum_{t\in[T ]}\overline{r}^{\top}(q^{*}-q_{t})d_{t,k}h_{t,k}\right)$ $\displaystyle\leq\frac{1}{2^{-k-1}}\left(L\sqrt{2\ln\left(\frac{\log(T)}{ \delta}\right)\sum_{t\in[T]}d_{t,k}}+\sqrt{\beta_{1}\sum_{t\in[T]}d_{t,k}}+( \beta_{2}+\beta_{3}\theta_{k})\max_{t\in[T]}d_{t,k}\right)$ $\displaystyle\leq\mathcal{O}\left(\frac{1}{2^{-k-1}}\left(\left(\sqrt{\beta_{1 }}+L\sqrt{\log\left(\frac{T}{\delta}\right)}\right)\sqrt{T}\max_{t\in[T]}d_{t, k}+(\beta_{2}+\beta_{3}\theta)\max_{t\in[T]}d_{t,k}\right)\right),$ $$

noticing that $\mathbb{E}\left[d_{t,k}\left(\mathbb{E}\left[h_{t,k}|d_{t,k}\right]-h_{t,k}
\right)\right]=\mathbb{E}\left[h_{t,k}|d_{t,k}\right]-\mathbb{E}[h_{t,k}]d_{t,
k}=\mathbb{E}\left[h_{t,k}|d_{t,k}\right]-\mathbb{E}\left[h_{t,k}|d_{t,k}
\right]=0$, since the expectation is taken w.r.t. the randomization of Algorithm 4 and the distribution generated given the external probability of receiving feedback $w_{t}$.

To conclude with probability at least $1-p-2\delta$:

$$ $\displaystyle\sum_{t\in[T]}$ $\displaystyle\overline{r}^{\top}(q^{*}-q_{t})\mathbb{I}\left(w_{t}\geq\frac{1} {T}\right)$ $\displaystyle\leq\sum_{k\in[M]}\sum_{t\in[T]}\overline{r}^{\top}(q^{*}-q_{t})d _{t,k}$ $\displaystyle\leq\mathcal{O}\left(\sqrt{\beta_{1}T}\max_{t\in[T]}\frac{1}{w_{t }}+(\beta_{2}+\beta_{3}|X||A|\log(\nicefrac{{\log(T)}}{{\delta}}))\max_{t\in[T ]}\frac{1}{w_{t}}+\beta_{3}\log(T)C\right)$ $\displaystyle\leq\mathcal{O}\left(\left(\sqrt{\beta_{1}^{\prime}T}+\beta_{2}^{ \prime}\right)\nu_{T}+\beta_{3}^{\prime}C\right),$ $$

with $\sqrt{\beta_{1}}\geq\mathcal{O}(L\sqrt{\log(\nicefrac{{T}}{{\delta}})})$.
Notice that the analogous reasoning can be applied to the positive cumulative constraints violation with parameters $\beta_{4},\beta_{5},\beta_{6}$.
∎

Figure: Algorithm 4 Adapted STABILIZE Jin et al. ()

###### Corollary 6 .

Being $j^{*}$ such that $C\in(2^{j^{*}-1},2^{j^{*}}]$ then with probability at least $1-11\delta$ it holds:

$$ $\max_{i\in[m]}\sum_{t\in[T]}\left[\mathbb{E}[g_{t,i}]^{\top}q_{t}^{j^{*}}- \alpha_{i}\right]^{+}\leq\sqrt{\beta_{4}T}\nu_{T,j^{*}}+\beta_{5}\nu_{T,j^{*}} +2\beta_{6}C,$ $$

with $\sqrt{\beta_{4}}=\mathcal{O}\left(L|X|\sqrt{|A|\ln(\nicefrac{{mT|X||A|}}{{
\delta}})}\right)$, $\beta_{5}=\mathcal{O}\left(|X|^{2}|A|^{2}\log(T)\log\left(\nicefrac{{\log(T)}}
{{\delta}}\right)\right)$and $\beta_{6}=\mathcal{O}\left(\ln(T)^{2}|X||A|\right)$ .

###### Corollary 7 .

Being $j^{*}$ such that $C\in(2^{j^{*}-1},2^{j^{*}}]$ then with probability at least $1-11\delta$ it holds:

$$ $\sum_{t\in[T]}\overline{r}^{\top}(q^{*}-q_{t}^{j^{*}})\leq\sqrt{\beta_{1}T}\nu _{T,j^{*}}+\beta_{2}\nu_{T,j^{*}}+2\beta_{3}C,$ $$

where $\sqrt{\beta_{1}}=\mathcal{O}\left(L|X|\sqrt{|A|\ln(\nicefrac{{T|X||A|}}{{
\delta}})}\right)$, $\beta_{2}=\mathcal{O}\left(|X|^{2}|A|^{2}\log(T)\log\left(\nicefrac{{\log(T)}}
{{\delta}}\right)\right)$ and $\beta_{3}=\mathcal{O}\left(\ln(T)^{2}|X||A|\right)$ .

###### Definition 2 .

###### Definition 3 .

###### Lemma 21 (Adapted from Jin et al. ( 2024 ) ) .

###### Proof.

###### Corollary 6 .

###### Corollary 7 .

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. Can you elaborate on the comparison of dynamic and static regret when the nonstationary is large? 
2. Can the results be extended to dynamic regret?
3. Can you comment on the technical challenges of deriving the results for static regret?
soundness: 3
strengths: The paper is well-written and the proof is sound. To the best of my knowledge, this is the first result on CMDP with nonstationary rewards, transitions, and bandit feedback.
summary: The paper studied CMDP with non stationary rewards and transitions. A \sqrt{T} + C style regret bound is shown with LAG-FTRL, which is a combination of FTRL and UCB. The algorithm will maintain several instances of the UCB algorithm and pick one according to FTRL.
weaknesses: My main concern is about the static baseline employed. To my knowledge, dynamic regret is usually used as a benchmark in learning in nonstationary environments. The paper has only highlighted the importance of considering static regret when the nonstationary is small (as a constant), which is unlikely to be the case in most environments. When we consider static regret, it is not so surprising that adding a layer of FTRL that "guesses" the corruption level can work, as FTRL already guarantees the static regret.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
questions: See Weaknesses. These two questions concern the technical hardness and applicability of the Lag-FTRL framework. I am happy to adjust my rating if the answers turn out to be pretty positive.

And also:

3. Is there any intuition why the non-stationarity metric is like this? Would other common metrics like path lengths be harder to tackle?
soundness: 3
strengths: 1. The constraint-violation metric is pretty strong: Albeit the static hindsight optimal policy is allowed to violate the constraints in some rounds and make it up in the remaining, the algorithm is not because of the $[\cdot]^+$ notion.
2. The known $C$ algorithm is pretty intuitive and well-motivated, especially regarding the enlargement of confidence radii.
3. The algorithm also works well when $C$ is unknown, with almost no performance degeneration -- though its quite hard to get the idea and applicability of the framework from the current writing; see the Weaknesses section.
summary: This paper considers CMDPs with both non-stationary rewards and constraints. As the fully adversarial CMDP problem is shown to be statistically intractable, the authors propose to consider the case where the per-round reward $r_t$ / constraint $g_t$ are sampled from some time-dependent distributions whose means do not vary from a "reference" reward / constraint vector significantly.

When $C$ is known, to tackle with the extra uncertainty in rewards and constraints, the confidence intervals are enlarged by an additive factor of $C/N_t(s,a)$. Utilizing policy search over the (estimated) occupancy measures, the algorithm guarantees $\mathcal O(\sqrt T + C)$ regret and constraint violations where $C$ is the level of non-stationarity.

Moreover, when $C$ is unknown, an algorithm-selection meta-algorithm that performs log-barrier FTRL on many base-algorithms with doubling $C$'s is developed.
weaknesses: 1. The algorithmic definitions, especially the $\ell_{t,j}$ and $b_{t,j}$ are written in a highly technical way. For example, without any description on the $\beta$'s in the main text, it is almost impossible to understand the construction of $b_{t,j}$ -- I suggest the authors to exemplify what each $\beta$ would be like if the revised Algorithm 2 is executed on its own. The effect of $\nu_{t,j}$ is also not explained.
2. The authors mentioned that the meta-algorithm Lag-FTRL can be of independent interest. Would it be possible to isolate the framework from the base algorithm -- say, what conditions of $\ell_t$ and $b_t$ are required for the framework to work, or it has to be constructed so meticulously as in Eqs. (6) and (7)?

Minor: Line 155 -- the definition of $C$ should be $\max(C_{G^\circ},C_{r^\circ})$?

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: - Can the authors provide the motivation for considering a static baseline algorithm? When the time horizon $L$ is large, minimizing the regret in the current episode seems to be a natural choice. Thus, the dynamic regret seems to be more meaningful under this nonstationary setup.
- The paper suggests it can ease the negative result of Mannor et al. (2019) by introducing the nonstationary parameter $C$. Is there any lower bound that involves $C$ for the proposed problem under the proposed regret formulation?
- How efficient it is to solve the optimization problem in Line 5 of Algorithm 2?
soundness: 3
strengths: - The paper is easy to follow and the intuition of the algorithms is natural.
- This paper adopts $C$ to quantify the level of non-stationarity, bridging the stationary setup and the adversarial setup.
- A meta algorithm is used to deal with the case where the knowledge of $C$ is not provided.
summary: This paper considers constrained MDP under non-stationary rewards and constraints, where the reward, cost functions and the transition kernel are unknown, the level of non-stationarity is measured by $C$ and the constraints is in terms of the expected number of violations. It solves the problem with the knowledge of $C$, followed by an extension to the unknown $C$ case with the help of Corralling method by Agarwal et al. (2017).
weaknesses: - Given the previous literature (Efroni et al. (2020), Stradi et al. (2024a), Stradi et al. (2024b), Wei et al. (2023)), the proposed problem formulation lacks novelty and motivations. While considering a positive violation seems to be practical, it is more proper to consider a dynamic baseline. Therefore, it is encouraged to provide a more detailed comparison between this work and the literatures in terms of the setups, motivations, and results.
- The proposed algorithm follows the UCB design with $C$ involved, thus, achieving a sublinear regret with respect to the static policy is kind of expected. It would be great if the authors can highlight the technical novelty.
- Simulations are not provided to illustrate the efficacy of the proposed algorithms, as well as comparisons with other baseline algorithms in the literature.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: If there are unique technical challenges specific to the CMDPs setting that prevent a direct application of the techniques in (Jin et al., 2024), I would be happy to reconsider and adjust my evaluation accordingly.
soundness: 3
strengths: + To my knowledge, This is the first work considering the CMDPs problem with adversarial rewards and constraints.

+ Authors provide theoretical guarantees for the proposed algorithms and achieve a linearly additive dependence on C.

+ The paper is generally well-written and easy to follow.
summary: This paper studies the constrained Markov decision processes (CMDPs) with adversarial rewards and constraints. Given the negative result of Mannor et al., 2009, the authors propose algorithms whose regret bounds depend on the non-stationarity of rewards and constraints. The proposed algorithm works for unknown $C$ by using a Corral-based technique.
weaknesses: My primary concern is the limited novelty of the technical contribution, as the approach in this paper appears to be a direct application of techniques from (Jin et al., 2024) for the CMDPs setting. In particular, the core technique and main theoretical analysis to deal with unknown $C$ are largely based on that of (Jin et al., 2024). Given that the corral (Agarwal et al., 2017) with different guesses for $C$ has been used in prior work (e.g., Jin et al., 2024), I believe a more direct comparison to (Jin et al., 2024) is necessary to clarify the technical contributions of this paper.

Meta-review: This paper studies CMDPs with non-stationary rewards and constraints, and propose an algorithm whose performance smoothly degrades as non-stationarity increases. More specifically, the algorithm achieves $O(\sqrt{T} + c)$ regret and positive constraint violation under bandit feedback, where $C$ is a corruption value measuring the environment non-stationarity. 

The main weakness of the paper is the lack of technical novelty. For instance, the authors failed to demonstrate why lag-FTRL could be a versatile meta-procedure that deals with constrained problems. 

Given the high standards of ICLR and the weakness mentioned above, I would recommend rejecting this paper.

Decision: Reject