No-Regret Online Reinforcement Learning with Adversarial Losses and Transitions
Authors: Tiancheng Jin
Junyan Liu
Chloé Rouyer
William Chang
Chen-Yu Wei
Haipeng Luo
Venue: NeurIPS 2023 poster (2023)
Keywords: reinforcement Learning
best of both worlds
MDP
robust RL
adversarial corruption

Abstract: Existing online learning algorithms for adversarial Markov Decision Processes 
achieve $\mathcal{O}(\sqrt{T})$ regret after $T$ rounds of interactions even if the loss functions are chosen arbitrarily by an adversary, with the caveat that the transition function has to be fixed.
This is because it has been shown that adversarial transition functions make no-regret learning impossible.
Despite such impossibility results, in this work, we develop algorithms that can handle both adversarial losses and adversarial transitions, with regret increasing smoothly in the degree of maliciousness of the adversary.
More concretely, we first propose an algorithm that enjoys $\widetilde{\mathcal{O}}(\sqrt{T} + C^{P})$ regret where $C^{P}$ measures how adversarial the transition functions are and can be at most $\mathcal{O}(T)$.
While this algorithm itself requires knowledge of $C^{P}$, we further develop a black-box reduction approach that removes this requirement.
Moreover, we also show that further refinements of the algorithm not only maintains the same regret bound, but also simultaneously adapts to easier environments (where losses are generated in a certain stochastically constrained manner as in [Jin et al. 2021]) and achieves $\widetilde{\mathcal{O}}(U + \sqrt{UC^{L}}  + C^{P})$ regret, where $U$ is some standard gap-dependent coefficient and $C^{L}$ is the amount of corruption on losses.

No- No-Regret Online Reinforcement Learning with Adversarial Losses and Transitions
Tiancheng Jin University of Southern California tiancheng. jinCusc. edu
Junyan Liu University of California, San Diego jul037@ucsd. edu
Chloé Rouyer University of Copenhagen chloe@di ku.de .k
William Chang
University of California, Los Angeles chang3148g ucla. edu
Chen- Yu Wei
Haipeng Luo University of Southern California haipengl@usc. edu
MIT Institute for Data, Systems, and Society chenyuw@mit, edu
Abstract
Existing online learning algorithms for adversarial Markov Decision Processes achieve O(VT) regret after T rounds of interactions even if the loss functions chosen arbitrarily by an adversary. with the caveat that the transition function has to be fixed. This is because it has been shown that adversarial transition functions make no-regret learning impossible. Despite such impossibility results, in this work, develop algorithms that handle both adversarial losses and adversarial transitions, with regret increasing smoothly the degree of maliciousness of the adversary. More concretely, we first propose an algorithm that enjoys D(VT+CC) regret where CPP measures how adversarial the transition functions are and can be most (Z'). While this algorithm itself requires knowledge of CP, we further develop black-box reduction approach that removes this requirement. Moreover, we also show that further refinements of the algorithm regret bound, but also simultaneously adapts to easier environments (where losses are generated in a certain stochastically constrained manner in Jin al. [2021]) and achieves ÕU + VUC++ regret, where is some standard gap-dependent coefficient and Ch the amount of corruption on losses.
only maintains the
Introduction
Markov Decision Processes (MDPs) are widely-used models for reinforcement learning. They are typically studied under a fixed transition function and fixed loss function, which fails capture scenarios where the environment is time-evolving or susceptible to adversarial corruption. This motivates many recent studies to overcome these challenges. In particular, one line of research, originated from Even-Dar et al. [2009] and later improved or generalized by e.g. Neu et al. [2010a,b], Zimin and Neu [2013], Rosenberg and Mansour [2019a], Jin et [2020], takes inspiration from the online learning literature and considers interacting with a sequence of T MDPs, each with an adversarially chosen loss function. Despite facing such challenging environment, the learner can still ensure (VTT) regret (ignoring other dependence; same below) as shown by these works, that is, the learner's average performance is close that the best fixed policy up to (LIvTT).
Equal contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

However, one caveat of these studies is that they all still require the MDPs to have to the same transition function. This is not for no reason Abbasi Yadkori et al. [2013] shows that even with full information feedback, achieving sub-linear regret with adversarial transition functions is computationally hard, and Tian et al. [2021] complements this result by showing that under the more challenging bandit feedback, this goal becomes even information-theoretiaall impossible without paying exponential dependence on the episode length.
To get around such impossibility results, one natural idea is to allow the regret to depend on some measure of maliciousness CP of the transition functions, which is when the transitions remain the same over time and (T)) in the worst case when they are completely arbitrary. We review several such attempts at the end of this section, and point out here that they all suffer one issue: even when Ct = 0, the algorithms developed in these works all suffer linear regret when the loss functions are completely arbitrary, while, as mentioned above, (VVT) regret is achievable in this case. This begs the question: when learning with completely adversarial MDPs, is OlvT + CP) regret achievable?
In this work, we not only answer this question affirmatively, but also show that one can perform even better sometimes. More concretely, our results are as follows.
1. In Section 3, we develop a variant of the UOB-REPS algorithm [Jin et al., 2020], achieving Ö(VT + CP) regret in completely adversarial environments when CP is known. The algorithmic modifications we propose include an enlarged confidence set, using the log-barrier regularizer, and a novel amortized bonus term that leads to a critical "change of measure" effect in the analysis.
2. We then remove the requirement on the knowledge of CP in Section 4 by proposing a black- box reduction that turns any algorithm with Ö(VT + CP) regret under known C2 into another algorithm with the same guarantee (up to logarithmic factors) even if CP is unknown. Our reduction improves that of Wei et al. [2022] by allowing adversarial losses, which presents extra challenges discussed in Pacchiano et al. [2022]. The idea of our reduction builds on top of previous adversarial model selection framework (a.k.a. Corral [Agarwal et al., 2017, Foster et al., 2020, Luo al., 2022]), but is even more general and is of independent interest: it shows that the requirement from previous work on having a stable input algorithm is actually redundant, since our method can turn any algorithm into stable one.
3. Finally, in Section 5 we also further refine our algorithm so that it simultancously adapts to the maliciousness of the loss functions and achieves O(min ( (v,, U + VUCT + CP) regret, where U is some standard gap-dependent coefficient and C+L < 'T' is the amount of corruption on losses (this result unfortunately requires the knowledge of CP, but not U or C4). This generalizes the so-called
guarantee of Jin and Luo [2020], Jin et al. [2021], Dann et al. [2023] from CP = 0 to any Cº,, and is achieved by combining the ideas from Jin al. [2021] I] and Ito [2021] with novel optimistic transition technique. In fact, this technique also leads to improvement on the dependence of episode length even when CP =.
Related Work Here, we review how existing studies deal with adversarially chosen transition functions and how our results compare to theirs. The closest line of research is usually known as corruption robust reinforcement learning [Lykouris et al., 2019, Chen et al., 2021, Zhang et al., 2021, Wei et al., 2022], which assumes ground truth MDP and measures the maliciousness of the adversary via the amount of corruption to the ground truth - the amount of corruption is essentially our Cf, while the amount of corruption is essentially our C' (these will become clear after we provide their formal definitions later). Naturally, the regret in these works is defined as the difference between the learner's 's total loss and that of the best policy with respect to the ground truth MDP. in which case Ö(VT + CP + C4) regret is unavoidable and is achieved by the state-of-the-arr [Wei et al., 2022].
On the other hand, following the canonical definition in online learning, we define regret with respect to the corrupted MDPs, in which case Ø(VT+ + CP) is achievable as we show (regardless how large CL. is). To compare these results, note that the two regret definitions differ from each other by an amount of most OC + C²). Therefore, our result implies that of Wei et al. [2022], but not vice versa - what Wei et al. [2022] achieves in our definition of regret is again ((VT + CP + CL), which is never better than ours and could be Q(T)) even when CP = 0.
In fact, our result also improves upon that of Wei et al. [2022] in terms of the gap-dependent refinement their refined bound is O(min VT. G} + CP + Ct.) for some gap-dependent measure
2

---

G' that is known to be no less than our gap-dependent measure U: on the other hand, based on earlier discussion, refined bound in their regret definition is (minn (VT, U + VUC+++ + C+) (mmin(VT, U} + CCC+CCC +C') and thus better. The caveat is that, as mentioned, for this refinement our result requires the knowledge of CP, but Wei al. [2022] does not.² However, that for the gap-independent bound, our result does not require knowledge of CP and is achieved via an even more general black-box reduction compared to the reduction of Wei al. [2022].
emphasize again
Finally, we mention that another line of research, usually known as non-stationary reinforcement learning, also allows arbitrary transition/loss functions and measures the difficulty by either the number of changes in the environment [Auer et al., 2008, Gajane et al., 2018] or some smoother measure such the total variation across time [Wei and Luo, 2021, Cheung al., 2023]. These results are less comparable to ours since their regret (known as dynamic regret) measures the performance of the learner against the best sequence of policies, while ours (known static regret) measures the performance against the best fixed policy.
2 Preliminaries
We consider the problem of sequentially learning T' episodic MDPs, all with the same state space S and action space A. We assume without Ioss of generality (similarly to Jin et al. [202 IJ) that the state space has a layered structure and is partitioned into L + subsets Su...., S2 such that So and Sz only contain the initial state Sy and the terminal state $ respectively, and transitions are only possible between consecutive layers. For notational convenience, for any k < L, we denote the set of tuples S₁ A X Sk+1 by We. We also denote by kss) the layer to which state E S belongs.
Ahead of time, knowing the learner's algorithm, the environment decides the transition functions {P:)T-. and the loss functions {4,)==1 for these T MDPs in an arbitrary manner (unknown to the learner). Then the learner sequentially interacts with these T MDPs: for each episode t = I..... T, the learner first decides a stochastic policy मe S x A - [0, 1] where Ty (a]s) is the probability of taking action when visiting state 8; then, starting from the initial state 8r,0 = 80, for each k = 0..... L - 1, the learner repeatedly selects an action 0r,k sampled from (T(-) suffers loss (,( at.x,) E [0, 1J, and transits to the next state St,A+1 sampled from (- (t.k) (until reaching the terminal state); finally, the learner observes the losses of those visited state-action pairs (a.k.a. bandit feedback).
Let (x(T) E E (1(,,, PP,) be the expected loss of executing policy π in the t-th MDP (that is, {(s,, an)) h=o is a stochastic trajectory generated according to transition P, and policy r). Then, the regret of the learner against any policy is defined as Regr (T) = E E(EE (T Eg (TT) We denote by & one of the optimal policies in hindsight such that Reg, (f) max, Reg, (T) and
use Reg, - Regr (+t as shorthand.
Maliciousness Measure of the Transitions If the transition functions are all the same, Jin et al. [2020] shows that Regy ((L]))/\A(()) is achievable, no matter how the loss functions are decided. However, when the transition functions are also arbitrary, Tian et al. [2021] shows that Reg- Q(min(T, V2(T)) is unavoidable. Therefore, natural goal is to allow the regret to smoothly increase from order vo T when some maliciousness measure of the transitions increases. Specifically, the measure we use is
T T-1 ΣΣ
CP
min
max [|P:(-ls,)) a'(ls,,))l, (s.0) X t=l K=D
PEP
where P denotes the set of all valid transition functions. Let P be the transition that realizes the minimum in this definition. Then Cº can be regarded as the same corruption measure used in Chen et al. [2021]: there, it is assumed that a ground truth MDP with transition P exists, and the adversary corrupts it arbitrarily in each episode to obtain P,, making CPP the total amount of corruption measured in certain norm. For simplicity, in the rest of this paper, we will also take this perspective and call
'When CP + O² is known, Lykouris et al. [2019] also achieves Omiin VT, U. + C + CC) regret, but similar earlier discussions on rap-independent bounds, their regret definition is weaker than ours.
3

---

Cº the transition conruption. We also use C.P² = = k= max (a.)),) [[ P(-ss, a) to denote the per-round corruption (so CP = CP). It clear that CP when the transition stays the same for all MDPs, while in the worst case it is at most 2T'. Our goal is to achieve Regr- (VT + CP) (ignoring other dependence), which smoothly interpolates between the result of Jin et al. [2020] for CP = 0 and that of Tian et al. [2021] for CP = OTT).
L-11
Enlarged Confidence Set central technique to deal with unknown transitions is maintain a shrinking confidence set that contains the ground truth with high probability [Rosenberg and Mansour, 2019a,b, Jin et al., 2020]. With a properly enlarged confidence set, the same idea extends to the case with adversarial transitions [Lykouris et al., 2019]. Specifically, all our algorithms deploy the following transition estimation procedure. It proceeds in epochs, indexed by = 1, 1,2,... ... and each epoch includes some consecutive episodes. An epoch ends whenever we encounter a state-action pair whose total number of visits doubles itself when compared to the beginning of that epoch. At the beginning of each epoch i, we caleulate empirical transition P. as:
P. [s, a) = mi(s, a, (ooss,,ss)/mm/// ///((sss)) a). ((s,a, E Wk. k= t......L-
(2)
where m, a) and (s, s') are the total number of visits to (s, a) and (s, a, s') prior to epoch i.² In addition, we calculate the following transition confidence set.
Definition 2.1. (Confidence Set of Transition Functions) Let 8 E (0, be confidence parameter. With known corruption CP, we define the confidence of transition functions for epoch i
P. = f
((('sss))) - P.((s' (((s)(s,a)] a) S B,(s,a,s)) s'), V(s,a, E WR,k k 0, O,....
where the confidence interval (s(s, 8') ) is defined, with = 1S1LA///8 as
P,(5's,, a) log (t) 64 CP +og (1) mi(s, a)
B((s,a,s))= = min 1, 1,16
mi(s,a) a)
Note that the confidence interval is enlarged according to how large the corruption CP is. We denote by EcON the event that P E Pi for all epoch i, which is guaranteed to happen with nigh-probabillty. Lemma 2.2. With probability at least 1- 28, the event Ecos holds.
Occupancy Measure and Upper Occupancy Bound Similar to previous work [Rosenberg and Mansour, 2019a, Jin al., 2020], given a stochastic policy æ and transition function P. we define the occupancy measure qf as the mapping from S A S to [0, 1] such that q P: (s. a, s') is the probability of visiting (s, a, s') when executing policy π in an MDP with tran- sition P. Further define of (s, = Eves q ( a, (the probability of visiting (s, a)) and p EaeA q. (s.a) a) (the probability of visiting s). Given occupancy measure g. the corresponding policy that defines it, denoted by T², can be extracted via (als) xx g(s, a).
Importantly, the expected loss (T) defined earlier equals (qPu.t,e) making our problem a variant of online linear optimization and enabling the usage of standard algorithmic frameworks such as (FTRL). These frameworks operate over a set of occupancy measures in the form of either S2(P) = Po æ is a stochastic policy)
Online Mirror Descent (OMD) or Follow- Regu-Regllrizzdd-
for some transition function P, or 2(P) = f PM P E P, π is stochastic policy) for some set of transition functions P.
Following Jin et al. [2020], to handle partial feedback on the loss function 4, we need to construct loss estimators & using the (efficiently computable) upper occupancy bound u4:
(ssaa) (s, a)),(s,a) where ur(s, a) max (s. PEPRo
(5)
Ue (x(8aa) a)
(s, a) is if (s, a) is visited during episode t (so that le a) is revealed), and 0 otherwise, and i(t) denotes the epoch index to which episode belongs. We also define us(s) = Enes ue(s, a).
When mi(s, a) we simply let the transition function to be uniform, that is. Pi(s'ss, a) 1/ Secar)

---

3 Achieving O(VT + (P) with Known CP
As the first step, develop an algorithm that achieves goal when CP is known. To introduce solution, we first briefly review the UOB- ROB-REPS algorithm of Jin et al. [2020] (designed for C' = 0) and point out why simply using the enlarged confidence set Eq. (3) when C* # is far away from solving the problem. Specifically, UOB-REPS maintains a sequence of occupancy measures (+) via OMD: g++1
(E0(((()))) Kaa, &e) + Dø(a, (.). Here, // 0 is learning rate, & is the loss estimator defined in Eq. (5), Φ is the negative entropy regularizer, and D& is the corresponding Bregman divergence. 4 With 7: at hand, in episode I, the learner simply executes TT. = ~.. Standard analysis of OMD ensures bound on the estimated regret REG = E a q qP {. and the rest of the analysis of Jin et al. [2020] boils down to bounding the difference between REG and Regr-
First Issue This difference between REG and Regr leads to the first issue when one tries to analyze UOB-REPS against adversarial transitions it contains the following bias term that measures the difference between the optimal policy's 's estimated loss and its true loss:
(.)
( (F).0((8)))
ue(s, - uo( (3,00)((((300))) (0l
E
Σ
q
Ee -1)-4)
R
(6)
When CP 0, we have P Pt. and thus under the high probability event EcON and by the definition of upper occupancy bound, we know qPe.*i(s (7, a) S uz(3, a), making Eq. (6) negligible. However, this argument breaks when CP # O and P * Pt. In fact, P₁ can be highly different from any transitions in Pi(e) with respect to which u, is defined, making Eq. (6) potentially huge.
(s.a)
Solution:
Change of Measure via Amortized Bonuses Given that q P (s) S ue(s, a) does still hold with high probability, Eq. (6) is (approximately) bounded by
lg (s, a) - (s.a)
q 19 P - of i (s)
E
q P*
(s, a)
= E
(()(s)
(8,a)
(c(s)
1=1
which is at most E round corruption CP (see Corollary D.3.6). While this quantity is potentially huge, if we could "change the measure" from g to qc. then the resulting quantity E
Ei (8) [x(3] since Pe (8) y P.Te (s)] is bounded by the per-
Σ Σ. ()(() cf is most mr(s]]
|S|CP since (5) S (s) by definition. The general idea of such change of measure has been extensively used in the online learning literature (see Luo et al. [2021] in most related context) and can be realized by changing the loss fed to OMD from E, to E b, for some bonus term b,, which, in our case, should satisfy (e(s, a) Rd
(=) However, the challenge here is that CP is unknown!
cP
Our solution is to introduce a type of efficiently computable amortized bonuses that do not change the measure per round, but do so overall. Specifically, our amortized bonus b, is defined
4L
if E [[gg u. (s)] [log2 ue (s))) CP 2L
(ss = (.)
else,
which we also write as by(s) since it is independent of a. To understand this definition, note that - -[log, us(s)] is exactly the unique integer such that us(s) falls into the bin (2-3-1,2 2]. Therefore, the expression Σ I[ [log2 (s)] = [logz (s(s)]} counts, among all previous rounds 1,...,4, L, how many times we have encountered a ur(ss) value that falls into the same bin as us(s). If this number does not exceed G we apply bonus of AL which is (two times of) the ur(s)
maximum possible value of the unknown quantity , otherwise, we do not apply any bonus. The idea is that by enlarging the bonus to it maximum value and stopping it after enough times, even though each by (s) might be quite different from [x].
cP overall they behave similarly after T episodes:
'The original loss estimator of Jin et al. [2020] is slightly different, but that difference is only for the purpose of obtaining a high probability regret guarantee which we do not consider in this work for simplicity.
5

---

Algorithm 1 Algorithm for Adversarial Transitions (with Known CP)
Input: confidence parameter E (0. 1), learning rate 1j > 0.
Initialize: epoch index i 1; counters mi mi(s. a) mi a, s') = mo s, a)
mo(s, a, s') 0 for
all (s, s'): empirical transition Pi and confidence width B1 based on Eq. (2) and Eq. (4); occupancy |l for all (s, a, s'); and initial policy л = T
measure @ (s, s')
for f ....., do
Execute policy and obtain trajectory (st, (c,k) for l = ,....,,-1
Construct loss estimator E, as defined in Eq. (5).
Update (8) for all 8 based on Eq. (7).
Increase counters: for each k < L, mi(St, 0i 1414 $ 1, m, (S a.x) $ 1.
3k, (8,At (t.)) 2 max (1, Increase epoch index i $ 1. Initialize new counters: V(s, a, s'), mi(s, a, s') m, ( a) Update confidence set P. based Eq. (3).
) then
b entering a new epoch
Let :)(:.) be the Bregman divergence with respect to log barrier (Eq. (11)) and compute
h++ = argmin 77 (a. - be) + +D(gq
(8)
(ER(P.)
Update policy T++1 = n 7-1
Lemma 3.1. The amortized bonus defined in Eq. (7) satisfies Et me(s) S Et and
Σ (s) = O(CP log TT)ttat for any s.
Therefore, the problematic term Eq. (6) is most E (q b,)]. which, if "converted" to E b.)] (change of measure), is nicely bounded by O(SS log T). As mentioned, such a change of measure can be realized by feeding & b, instead of &g to OMD, because now standard analysis of OMD ensures a bound on REG = E (ār q l b,)l. which, compared to the earlier definition of REG, leads to difference of E Σ ( pM bi)) (see Appendix A.5 for details).
Second Issue The second issue comes from analyzing REG (which exists even if no bonuses are used). Specifically, standard analysis of OMD requires bounding a "stabilityy term, which, for the negative entropy regularizer, is in the form of E., Te(8, (s) =
E,E, E.,a fc(s, a) (((ss,))Lu") ( < EE Es,a _f,""(s.))]. Once again, when CP 0 and Pt = P, we have Pr.... bounded by ur (s. a) with high probability, and thus the stability term is O(T]S||A[); but this breaks CP o 0 and P; can be arbitrarily different from transitions Pa(o)
ul(s,a)²
ue(s.a)
Solution: Log-Bal Barrier Regularizer Resolving this second issue, however, is relatively straight- forward it suffices switch the regularizer from negative entropy log-barrier: Φ(q)
-Et (s,a,s))ew, log q(8, 8'), which is first used by Lee et al. [2020] in the context of learning adversarial MDPs but dates back to earlier work such as Foster et al. [2016] for multi-armed bandits. An important property of log-barrier is that it leads
smaller stabil-
ity term the form of EE,, E.o a (e(s, (s, a)?] (with an extra (s,s, a)), which is most E, E.,o P (s, a) (,,, a) = O(TL) since (s,s,) a) I ur(s, a). In fact, this also helps control the extra stability term when bonuses are used, which is in the form of E E.. Te(s, a) b,, a) and is at most 4LE (T., bx)] CL log 7) according to Lemma 3.1.
Putting these two ideas together leads to our final algorithm (see Algorithm 1). We prove the following regret bound in Appendix A, which recovers that Jin et al. [2020] when CP = 0 and increases linearly in CP as desired.

---

| log(t) LT
Theorem 3.2. With 1/r and 17 = min
8L. Algorithm ensures
Regr O (LISIVIAAT
VIA/T log (1) || (1) + C L|STMA log(t))
4 Achieving + with Unknown CP
In this section, we address the case when the amount of corruption is unknown. We develop a black-box reduction which turns algorithm that only deals with known CP to one that handles unknown CP. This is similar to Wei et al. [2022] but additionally handles adversarial losses using different approach. A byproduct of our reduction is that we develop entirely black-box model selection approach for adversarial online learning problems, as opposed to the gray-box approach developed by the "Corral" literature [Agarwal al., 2017, Foster al., 2020, Luo et al., 2022] which requires checking the base algorithm is stable. To achieve this, we essentially develop another layer of reduction that turns any standard algorithm with sublinear regret into stable algorithm. This result itself might be of independent interest and useful for solving other model selection problems.
More specifically, our reduction has two layers. The bottom layer is where novelty lies: it takes algorithm that operates under known CP (e.g.. the one we developed in Section 3), and outputs stable corruption-robut algorithm (formally defined later) that still operates under known CP. The top layer, on the other hand, follows the standard Corral idea and takes as input stable algorithm that operates under known CP, and outputs algorithm that operates under unknown CP. Below, we explain these two layers of reduction in details.
as input an arbitrary corruption-robut
Bottom Layer (from an Arbitrary Algorithm to Stable Algorithm) The input of the bottom layer is an arbitrary corruption-robust algorithm, formally defined as:
Definition 4.1. An adversarial MDP algorithm is corruption robustt if it takes 0 (a guess on the corruption amount) as input, and achieves the following regret for any random stopping time t' S T:
max (e(T))) - (((T)) -e(r) S E 1 (12 BBB)I((' 2 21]] + Pric > LT
IT
for problem-dependent constants and log(T) factors B1 2 1,, 2 L, 83 2 1, where OP.e
Σx=1 CP is the total corruption up to time t'.
While the regret bound in Definition 4.1 might look cumbersome, is in fact fairly reasonable: if the guess 0 is not smaller than the true corruption amount, the regret should be of order +F+0: otherwise, the regret bound is vacuous since LT is its largest possible value. The only extra requirement is that the algorithm needs to be anytime (i.e.. the regret bound holds for any stopping time E'), but even this known to be easily achievable by using a doubling trick over a fixed-time algorithm. is then clear that our algorithm in Section 3 (together with doubling trick) indeed satisfies Definition 4.1.
As mentioned, the output of the bottom layer stable robust algorithm. To characterize stability, we follow Agarwal et al. [2017] and define a new learning protocol that abstracts the interaction between the output algorithm of the bottom layer and the master algorithm from the top layer:
Protocol 1. In every round f, before the learner makes a decision, probability w, E [o, 1] is revealed to the learner. After making a decision, the learner sees the desired feedback from the environment with probability wh, and sees nothing with probability Wt-
In such a learning protocol, Agarwal et al. [2017] defines a stable algorithm one whose regret smoothly degrades with pT = minterr: we For our purpose here, we additionally require that the dependence on CP in the regret bound is linear, which results the following definition:
Definition 4.2 -ta-baalle corruption- algorithm). A 1 -tabbl corruption-robust algorithm is one that, with prior knowledge on Cp,, achieves Regr S E TB + 32rT] + +.gcCP under Protocol I for problem-depender constants and factors 31 2 L2 B2 2 and 33 2 1.
For simplicity, we only define and discuss the } -stabbility notion here (the parameter 1 refers to the exponent of T"), but our result can be straightforwardly extended to the general a-stability notion for
7

---

Algorithm 2 STable Algorithm By Independent Learners and Instance SElection (STABILISE)
Input: CP and a base algorithm satisfying Definition 4.1. Initialize: flog2 7 instances of the base algorithm .... ALGrlog, T7, where ALG, is config- ured with the parameter
0 - 2 log
for 1, = 1, 1.2.... ......d do
Receive
Ui S 5 then
play an arbitrary policy continue (without updating any instances)
Let je be such that E (2- 2-
Let ne be the policy suggested by ALGj,-
Output T..
If feedback is received, send it ALG,, with probability 2 wy
and discard it otherwise.
((2,1) 1) as in Agarwal et al. [2017]. Our main result in this section is then that one can convert any corruption-robust algorithm into --stable corruption-robust algorithm:
Theorem 4.3. If an algorithm is corruption robust according to Definition 4.1 for some constants (31, B3), then one can convert
-taable corruption-rebuss algorithm (Definition 4.2) with constants (8) B2g B3) where 81 OB3, log T), 8/2 ( + 8g log T), and S O log T).
This conversion is achieved by a procedure that we call STABILISE (see Algorithm for details). The high-level idea of STABILISE is follows. Noticing that the challenge when learning in Protocol I that Wt varies over time, we discretize the value of W/ and instantiate one instance the input algorithm to deal with one possible discretized value, that it is learning in Protocol but with fixed Wi, making it straightforward to bound its regret based on what promises in Definition 4.1.
More concretely, STABILISE instantiates (log, 7) instances {ALG,} J [ogg 71 of the input algo- rithm that satisfies Definition 4.1, each with different parameter 0j. Upon receiving w, from the environment, it dispatches round to the j-th instance where j is such that w, E (2-2-1,2- and uses the policy generated by ALG, to interact with the environment (if w, +, simply ignore this round). Based on Protocol 1, the feedback for this round is received with probability wt- To equalize the probability of ALG, receiving feedback mentioned in the high-level idea, when the feedback
is actually obtained, STABILISE sends it to ALG, only with probability 2-1-1 (and discards it otherwise). This way, every time ALG, is assigned to round, it always receives the desired feedback with probability Wt 2- 2-1-1, This equalization step the key that allows us to use the original guarantee of the base algorithm (Definition 4.1) and run it as is, without requiring it to perform extra importance weighting steps as in Agarwal et al. [2017].
The choice of 0, is crucial in making sure that STABILISE only has CP regret overhead instead of Pr.CPP Since ALG, only receives feedback with probability 2-j-1, the expected total corruption experiences is on the order of P- Therefore, its input parameter 03 only needs be of this order instead of the total corruption CP. This is similar to the key idea of Wei al. [2022] and Lykouris et al. [2018]. See Appendix B.1 for more details and the full proof of Theorem 4.3.
Top Layer (from Known CP to Unknown CP) With stable algorithm and regret guarantee in Definition 4.2, it is relatively standard to convert it to an algorithm with Ø(VT + CP) regret without knowing CP_ Similar arguments have been made in Foster et al. [2020], and the idea is to have another specially designed OMD/FTRL-based master algorithm to choose on the fly among a set of instances of this stable base algorithm, each with different guess on CP (the probability w, in Protocol I is then decided by this master algorithm). We defer all details to Appendix B. The final regret guarantee is the following (Ö(-) hides log(T) factors).
8

---

Theorem 4.4. Using an algorithm satisfying Definition 4.2 as base algorithm, Algorithm 3 (in the appendix) ensures Regr = Ö (v3,T -2 B2 +
3yCF) without knowing C.P.
5 Gap-Dependent Refinements with Known CP
Finally, we discuss how to further improve our algorithm so that it adapts to casier environments and enjoys better bound when the loss functions satisfy certain gap condition, while still maintaining the O(v CP) robustness guarantee. This result unfortunately requires the knowledge of CP because the black-box approach introduced in the last section leads to /T regret overhead already. We leave the possibility of removing this limitation for future work.
More concretely, following prior work such as Jin and Luo [2020], we consider the following general condition: there exists a mapping ग : + A, a gap function A S + (0, LJ. and a constant O, such that for any policies Ti,.... Ty generated by the learner, we have
C
T
E
Σ
P.xs q
g.T 11) Z ΣΣΣ of -
t=1 des1 apt
has been shown that this condition subsumes the case when the loss functions are drawn from a fixed distribution (in which case x² is simply the optimal policy with respect to the loss mean and P. is the gap function with respect to the optimal Q-function, and C+ 0), or further corrupted by an adversary in an arbitrary manner subject to a budget of C'e; we refer the readers to Jin and Luo [2020] for detailed explanation. Our main result for this section is novel algorithm (whose pseudocode is deferred to Appendix C due to space limit) that achieves the following best-of-both-- sit-off-oothworllee worldd guarantee.
Theorem 5.1. Algorithm 4 (with = 1/T" and Tt defined as in Definition 5.2) ensures
Regr (+) = O (L2 (11IS|IA)oo (1) VT + (OP + L L9 log ())
always, and simultaneously the following gap-dependent bound under Condition (9):
Reg (Tr =0 VUCL + (CPP + +1) ()))((())0 [21
where U 1o15) Ama
Esfsi Eafr(e) (s)
[1 and AMIN min (ssaa)
A a).
Aside from having larger dependence on parameters L, S, and A, Algorithm 4 maintains the same O(VT+ CP) regret as before, no matter how losses/transitions are generated; additionally, the vT part can be significantly improved to OU + VUCL) (which can be of order only log T when CL is small) under Condition (9), This result not only generalizes that of Jin et al. [2021], Dann et al.
[2023] from C. = 0 to any C.,. but in fact also improves their results by having smaller dependence on L in the definition of U. In the rest of this section, we describe the main ideas of our algorithm.
FTRL with Epoch Schedule Our algorithm follows line of research originated from Wei and Luo [2018 8), Zimmert and Seldin [2019] for multi-armed bandits and uses FTRL (instead of OMD) together with a certain self-bounding analysis technique. Since FTRL does not deal with varying decision sets easily, similar to Jin et al. [2021]. we restart FTRL from scratch at the beginning of each epoch (recall the epoch schedule described Section 2). More specifically, in an episode t that belongs to epoch i, we now compute T. as argmin, {g. Ei=1, (F₂ b,)) + (e(4), where 4 the first episode of epoch i, Eg is the same loss estimator defined in Eq. (5), by is the amortized bonus defined in Eq. (7) (except that r = 1 there is also changed iimevaryying regularizer to be specified later, and the set that q is optimized over is also a key element to be discussed next. As before, the learner then simply executes π, ah for this episode.
t; due to restarting),
is
Optimistic Transition An important idea from Jin et al. [2021] is that if FTRL optimizes q over ((P.) (occupancy measures with respect to a fixed transition P.) instead of I((::) (occupancy measures with respect to set of plausible transitions) as in UOB-REPS, then critical loss-shifling technique can be applied in the analysis. However, the algorithm lacks "optimism" when not using confidence set, which motivates Jin et al. [2021] to instead incorporate optimism by subtracting

---

a bonus term BONUS from the loss estimator (not to be confused with the amortized bonus by we propose in this work). Indeed, if we define the value function (P:TTss E) as the expected loss one suffers when starting from and following in an MDP with transition P and loss f, then they show that the BONUS term is such that P (s; E BONUS) I (s; E) for any state and any loss function E, that is, the performance of any policy is never underestimated.
Instead of following the same idea, here, we propose simpler and better way to incorporate optimism via what we call optimistic transitions. Specifically, for each epoch i, we simply define an optimistic transition function P; such that Pi(s'|s. a) = max {0, P.(s' s.)a) Be a, s')} (recall the confidence interval B, defined in Eq. (4)). Since this makes E. P.(s'Is, a) less than 1, we allocate all the remaining probability to the terminal state 8r (which breaks the layer structure but does not really affect anything). This is a form of optimism because reaching the terminate state earlier can only lead to smaller loss. More formally, under the high probability event Ecox, we prove P (s; E) S P.
(s; E) for any policy æ, any state 8, and any loss function E (see Lemma C.8.3).
With such an optimistic transition, we simply perform FTRL over S2 ((P)) without adding any additional bonus term (other than b,), making both the algorithm and the analysis much simpler than Jin et al.
[2021]. Moreover, can also be shown that VP: (s; BONUS) S V Pi. (s; (see Lemma C.8.4), meaning that while both loss estimation schemes are optimistic, ours is tighter than that of Jin et al. [2021]. This eventually leads to the aforementioned improvement in the U definition.
Time- Varying Rog-Barrier Regularizers The final element to be specified in our algorithm is the time-varying regularizer dt. Recall from discussions in Section that using log-barrier as the regularizer is critical for bounding some stability terms in the presence of adversarial transitions. We thus consider the following log-barrier regularizer with an adaptive learning rate " : S x A - R4: (1) - Ene To (8 a) log g(s, a). The learning rate design requires combining the loss-shifting idea of [Jin et al., 2021] and the idea from [Ito, 2021], the latter of which is the first work to show that with adaptive learning rate tuning, the log-barrier regularizer leads to near-optimal best-of-both-wee both-woorld gaurantee for multi-armed bandits.
More specifically, following the same loss-shifting argument of Jin et al. [2021], we first observe that our FTRL update can be equivalently written as
t-1 (e, - by) -b.)) + + = argmin xE
1 q, Σ (or 185-b,,, b,) + (2))) T=t.
@ = arggmin (P)(P.)
9:
D(E,, T=ti
where Fr (x, a) Q.L. (s, (., VPr. (s: {x) for any state-action pair (s, a) (Q is the standard Q-function; see Appendix C for formal definition). With this perspective, follow the idea of Ito [2021] and propose the following learning rate schedule:
Definition 5.2. (Adaptive learning rate for tog-barrier) For any L, if it is the starting episode of an epoch, we set (o(s,a) a) = 256L2|S); otherwise, we set 7h+ (3, a) = a) + 27((5,0)
Dm((s.) where
D 1/log(), as) = g Pan (s, a)² (oPico (s,a; 2.) v (a (s:2.) and i(t) is the epoch index to which episode belongs.
Such learning rate schedule is critical for the analysis in obtaining certain self-bounding quantity and eventually deriving the gap-dependent bound. This concludes the design of our algorithm; see Appendix C for more details.
6 Conclusions
In this work, we propose online RL algorithms that can handle both adversarial losses and adversarial transitions, with regret gracefully degrading the degree of maliciousness of the adversary. Specifi- cally, we achieve (VVT + CP) regret where CP measures how adversarial the transition functions are, even when CP is unknown. Moreover, we show that further refinements of the algorithm not only maintain the same regret bound, but also simultaneously adapt to easier environments, with the caveat that CP must be known ahead of time. We leave how to further remove this restriction as key future direction.
10

---

Acknowledgments and Disclosure of Funding
TJ and HL are supported by NSF Award IIS-1943607 and Google Research Scholar award. CR acknowledges partial support by the Independent Research Fund Denmark, grant number 9040- 00361B.
References
Yasin Abbasi Yadkori, Peter Bartlett, Varun Kanade, Yevgeny Seldin, and Csaba Szepesvari. Online learning in markov decision processes with adversarially chosen transition probability distributions. In Advances Neural Information Processing Systems (NeurIPS), 2013.
Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert E Schapire. Corralling a band of bandit algorithms. In Proceedings of the International Conference Computational Learning Theory (COLT), 2017.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in Neural Information Processing Systems (NeurIPS), 2008.
Yifang Chen, Simon Du, and Kevin Jamieson. Improved corruption robust algorithms for episodic reinforcement learning. In Proceedings of the International Conference on Machine Learning (ICML), 2021.
Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Nonstationary reinforcement learningg The blessing of (more) optimism. Management Science, 2023.
Christoph Dann, Chen-Yu Yu Wei, and Julian Zimmert. Best of both worlds policy optimization. arXiv preprint arXiv:2302.0944 09400, 2023.
Eyal Even-Dar, Sham M Kakade, and Yishay Mansour. Online markov decision processes. Mathe- matics of Operations Research, 2009.
Dylan J Foster, Zhiyuan Li, Thodoris Lykouris, Karthik Sridharan, and Eva Tardos. Learning in games: Robustness of fast convergence. Advances in Neural Information Processing Systems (NeurIPS), 2016.
Dylan Foster, Claudio Gentile, Mehryar Mohri, and Julian Zimmert. Adapting to misspecification in contextual bandits. Advances in Neural Information Processing Systems (NeurIPS), 2020.
Pratik Gajane, Ronald Ortner, and Peter Auer. sliding-window window algorithm for markov decision processes with arbitrarily changing rewards and transitions. arXiv preprint arXiv: 1805. 10066, 2018.
Shinji Ito. Parameter- freee multi aume bandit algorithms with hybrid data detandependent regret bounds. In Proceedings of the International Conference on Computational Learning Theory (COLT), 2021.
Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning adversarial markov de- cision processes with bandit feedback and unknown transition. In Proceedings of the International Conference on Machine Learning (ICML), 2020.
Tiancheng Jin and Haipeng Luo. Simultaneously learning stochastic and adversarial episodic mdps with known transition. Advances in Neural Information Processing Systems (NeurIPS), 2020.
Tiancheng Jin, Longbo Huang, and Haipeng Luo. The best of both worlds: stochastic and adversarial episodic mdps with unknown transition. Advances in Neural Information Processing Systems (NeurIPS), 2021.
Sham Machandranath Kakade, On the sample complexity of reinforcement learning. PhD thesis. University College London, 2003.
Chung- Wei Lee, Haipeng Luo, Chen- Yu Wei, and Mengxiao Zhang. Bias no more: high-probability data-dependent regret bounds for adversarial bandits and mdps. Advances in Neural Information Processing Systems (NeurIPS), 2020.

---

Haipeng Luo, Chen- Yu Wei, and Chung Wei Lee. Policy optimization in adversarial mdps: Improved exploration via dilated bonuses. Advances Neural Information Processing Systems (NeurIPS). 2021.
Haipeng Luo, Mengxiao Zhang, Peng Zhao, and Zhi-Hua Zhou, Corralling larger band of bandits: A case study on switching regret for linear bandits. In Proceedings of the International Conference on Computational Learning Theory (COLT), 2022.
Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme. Stochastic bandits robust adversarial corruptions. In Proceedings of the Annual ACM SIGACT Symposium on Theory of Computing, 2018.
Thodoris Lykouris, Max Simchowitz, Aleksandrs Slivkins, and Wen Sun. Corruption robust explo- ration in episodic reinforcement learning. arXiv preprint arXiv: 19t:::9911.000000 2019.
Gergely Neu, Andras Antos, András György, and Csaba Szepesvári. Online markov decision processes under bandit feedback. Advances in Neural Information Processing Systems (NeurIPS), 2010a.
Gergely Neu, András György, and Csaba Szepesvári. The online loop-free stochastic shortest-path problem. In Proceedings of the International Conference Computational Learning Theory (COLT), 2010b.
Aldo Pacchiano, Christoph Dann, and Claudio Gentile. Best of both worlds model selection. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Aviv Rosenberg and Yishay Mansour. Online convex optimization adversarial markov decision processes. In Proceedings of the International Conference on Machine Learning (ICML), 2019a.
Aviv Rosenberg and Yishay Mansour. Online stochastic shortest path with bandit feedback and unknown transition function. Advances in Neural Information Processing Systems (NeurIPS), 2019b.
Yi Tian, Yuanhao Wang, Tiancheng Yu, and Suvrit Sra. Online learning in unknown markov games. In Proceedings of the International Conference on Machine Learning (ICML), 2021.
Chen-Yo Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Proceedings of the International Conference on Computational Learning Theory (COLT), 2018
Chen-Ya Yu Wei and Haipeng Luo. Non Non-stationary reinforcement learning without prior knowledge: An optimal black-bor box approach. In Proceedings of the International Conference on Computational Learning Theory (COLT), 2021.
Chen- Yu Wei, Christoph Dann, and Julian Zimmert. A model selection approach for corruption robust reinforcement learning. In Proceedings of the International Conference Machine Learning (ICML), 2022.
Xuezhou Zhang, Yiding Chen, Xiaojin Zhu, and Wen Sun. Robust policy gradient against strong data corruption. In International Conference Machine Learning, pages
PMLR, 2021.
Alexander Zimin and Gergely Neu. Online learning in episodic markovian decision processes by relative entropy policy search. In Advances in Neural Information Processing Systems (NeurIPS), 2013.
Julian Zimmert and Yevgeny Seldin. An optimal algorithm for stochastic and adversarial bandits. In Proceedings of the International Conference Artificial Intelligence and Statistics (AISTATS), 2019.
12

---

Appendix
Omitted Details for Section
14
A.I
Equivalent Definition of Amortized Bonuses
15
A.2
Bounding ERROR
15
A.3 Bounding BIAS1
16
A.4 Bounding REG
18
A.5 Bounding BIAS2
20
A.6 Proof of Theorem 3.2
22
Omitted Details for Section 4
23
B.1 Bottom Layer Reduction: STABILISE
23
B.2 Top Layer Reduction: Corral
24
Omitted Details for Section 5
27
C.1 Description of the Algorithm
28
C.2 Self-Bounding Properties of Regret
................................
28
C.3 Regret Decomposition Regr (T and Proof Lemma C.2.3
................................
C.4 Proof of Lemma C.3.1
................................
33
C.5 Proof of Lemma C.3.2
33
C.6 Proof of Lemma C.3.3
34
C.6.1 Bounding Term
35
C.6.2 Bounding Term
36
C.6.3 Bounding Term
................................
37
C.7 Proof of Lemma C.3.4
................................
39
C.7.1 Properties of the Learriig Rate
................................
39
C.7.2 Bounding ESTREG, for Varying Learning Rate
44
C.7.3 Bounding ESTREG
49
C.8 Properties of Optimistic Transition
50
Supplementary Lemmas
52
D.I Expectation
52
D.2 Confidence Bound with Known Corruption
52
D.3 Difference Lemma
57
D.4 Loss Shifting Technique with Optimistic Transition
62
D.5 Estimation Error
63
13

---

Important Notations Throughout the appendix, we denote the transition associated with the
occupancy measure qt by Pe that q = -f Recall i(t) is the epoch index which episode t belongs. Importantly, the notation m.(s, a) (and similarly m. a, a ), which is changing variable in the algorithms, denotes the initial value of this counter in all analysis, that is, the total number of visits to (s,0) a) prior to epoch i. Finally, for convenience, we define m;(s.a) = max {mi(s, a), CP + log (1)), and it can be verified that the confidence interval, defined Eq. (4)
as
Pa(s'|s, s, a) log = 64 mi(s,a)
CP + log (1)
Bs min L, V
mi(s, a)
can be equivalently written as
C Cº log (4) m, a) (s log 64 mi(s,a) a)
Bi(s,a,s') min 1, 16
since whenever a, # (s a). the two definitions both lead to value of 1.
A Omitted Details for Section 3
In this section, we provide more details of the modified UOB-REPS algorithm as shown in Algo- rithm In the algorithm, the occupancy measure for each episode t is computed as
go+1 argmin 17
( (g be) + (g
(10)
gES(Prtets))
where 1) > 0 is the learning rate and Dz(g. g') is the Bregman divergence defined as Dola, d') <(g)= d(a') (Vó(g)).q q")
(11)
The Bregman divergence is induced by the log-barrier regularizer & given as:
L-1 ( = ΣE Σ log q(ss (((s.a,)))
(12)
R= &E AE A 8'ES
We note that the loss estimator is constructed based upon upper occupancy bound ue, which can be efficiently computed by COMP-UOB [Jin al., 2020].
In the rest of this section, we prove Theorem 3.2 which shows that the expected regret is bounded by
o (ISS L|S|*| A|g (1) + CP L|S log(t))
Our analysis starts from regret decomposition similar to Jin et al. [2020], but with the amortized bonuses taken into account:
T
Reg,
E
(q P
o Putt )
T
T
Pum g Piime (iote,e))) ka)
+E
q Pers la - Fr
ERROR
BIAS1
T
T
T
+
E
Pr.s p.att -bn)
bn)
+
P. Pr l
+ Σ
q PisTe g b.)) ),(t,b))
1=1
REG
BiA8q
T
+ E
P.#
Puttt 11)
where the last term can be directly bounded by O (I.CP) using Corollary D.3.7, and ERROR, BIASI, RFG, and BIAS₁ are analyzed in Appendix A.2, Appendix A.3, Appendix A.4 and Appendix A.5 respectively.
14

---

A.1 Equivalent Definition of Amortized Bonuses
For ease of exposition, we show an alternative definition of the amortized bonus by (s), which is equivalent to Eq. (7) but is useful for our following analysis. Recall from Eq. (7) that
4L (.)
if E [[[log u- (s)] flog2 us - C
be(s) be(s,a)=
2L
(13)
else,
In Eq. (13), the value of (s) relies on the cumulative sum of [([log2 u, ux) = Moga u+))]] and whether the cumulative sum exceeds the threshold Cº To reconstruct this, we define (e(s) as the unique integer value j 1oo, [s)] such that (s()) E (2-3-1,2-) .22) and define 2/ (s) as the total number of times from episode т = 1 to r = t where (s) = j holds. With these definition,, the 4L can be represented by Σ, (Be(s)) = o
2L
S /2/2/ where the summation is over all integers that - [oog2 [s)] can take. Notice that since (s) 2 |SiT holds for all and t (see Lemma D.2.8), the largest possible integer value need to consider is [log, (IS(T)). Therefore, (s) can be equivalently defined as:
condition under which (s))
(x)
(s) = b)(s,))=
4L
[O T)]
[(v(s) (aass))jji - اHز [1) S 2L
{
CP
Vs S, (I,...,T}.
ur (x)))
1=
(14)
A.2 Bounding ERROR
Lemma A.2.1 (Bound of ERROR). Algorithm ensures
ERROR = O (1.SIV/AAIToO())
|A| log(T) + [|S1|A/|1oo/1 + STT)..
Proof. For this proof, consider two cases, whether the event EcoN A EAST holds or not, where Ecos. defined above Eq. (4), and ELST, defined in Proposition D.5.2, are both high probability events.
Suppose that Ecox A EEST holds. We have
Puise - a Pirte,
q (1, - PiTe ())
t=1 K=0 sE aEd
(stt(s)- (p)))
EES
Σ3
g Pe (u, P((wuu, P,(wlu, v) (s
K=0 sESa A=0 AEA WESH+1
Prote Pusie(u, (u, v) ((((u,))-(((luuu))))
1= 0=0 uES, P
T 1-1
| Pott (1, (18((t,,0) P(-uu, + (P((l,,)-P((11)) p(-uu)
1=0 uES, v
T h-1
Pomee (T. vu p) p()lu,)) L cP
WES, AEA
h=0
L >3
P(- ạ Poote Puote(u,)) () (P(()u,)) ( -P(luu))-P((u.)) LIC.
(15)
t= h=0 HES AEA
15

---

where the first step follows from the fact that (((s,a) E [0, 1] for any (s, a): the third step applies Lemma D.3.3; the fourth step rearranges the summation and uses the fact that Σs,a q P...T (s, alw) I L; and in the sixth step we define C,,, max,eS, [| - P(-|s, a)ll so that CP
E Ei=d Oh,,- We continue to bound the first term above as:
E EE E
E
Pu v) ( - P(-lu.))l,
1=1 h= WESh DEA
q Pette (u, v) ((((lu,)) (r w) - -| - P(luu, b)
h=0 UESh vEA
T
Peite (u. O [S | Ma(e)(u, (u, (u
(V
C + +1 mi(e) (u, v)
+
h=0 == MESh PEA
[VIsa[SS++alAAITT (og(() + | (|Sh+1l log(t) + cP) + +oog())
0
(1Saa + +S T Tlg
(og)) (ISm-1/ + CP) + log(()
0O (SIV | (t)
|S| |A| log(() log(T) + CP | log(7))
(16)
where the first step uses the triangle inequality; the second step applies Corollary D.2.6 to bound two norm terms based on the fact that P., Put) Petey; the third step follows the definition of EEST from Proposition D.5.2; the fourth step uses the AM-GM inequality. Putting the result of Eq. (16) into Eq. (15) yields the first three terms of the claimed bound.
Now suppose that Ecos A EEST does not hold. We trivially bound Σ -p e by LT.
As the probability that this case oceurs is at most (d), this case contributes to at most (8LT) regret. Finally, combining these two cases and applying Lemma D. finishes the proof.
A.3 Bounding BIASI
Lemma A.3.1 (Bound of BIAS)). Algorithm ensures
BIAS₁ O (LIS) + C SLT).
Proof. We can rewrite BIASI
T
BIAS; Σ
E
( Paitee e - E.)]
Σ
E
(0
P. Pente
Ey
[ee [ec-Ea])] {
where the second step uses the law of total expectation and the fact that g Perts is deterministic given all the history up to f.. For any state-action pair (8, a), we have
E, ((( - (((s, a)] = (s) (1 Te (s, (8,00
(x(s,a) (u((sa)) n. (s,a) u1,saa
(1
Then, we can further rewrite and bound BIAS₁ as:
()(s,a) ge (s.
BIAS
P.RK (s, (s,a)e((s,a))
( u1(8,a) a)
4,4
- -1 a) (s)
E
Pr.se (s,a)
((
16

---

T
S
[n(s)
NES
where the third step follows from the fact that g P a) S (x(8, a) according to the definition of the upper occupancy measure.
Similar to the proof of Lemma A.2.1, we first consider the case when the high probability event Ecox A EAST holds:
Σ
(s))s) 9 ( (s)
.E9
Σ (+(()) - (s( >
11 (s) - (s))
#ES
SES
(((s) (s)((s)) LCP
SES
-
P(wlu, v) log (1) ( (s|w) masee (3, a)
0
LC +
Σ
(u))
#ES k=0
(u.,ww)eW
CP + log (1)
+0
|||
Σe
Piti (s, a)
8,0
L-1
P(w uu u) log (1) (
0
LC + L Σ
Σ
g (u))
0=
CP
+ log (1)
+
Σ
( a)
8,0
where the first step uses the triangle inequality; the second step uses Corollary D.3.6; the third step uses Lemma D.3.8; the last step follows from the fact that Eves P: (s/w) S L.
Taking the summation over all episodes yields the following:
T
(s(s)= 9 Pi. ((tt((s) (s)
(=1 sES
0
Σ 1=1
T
T-1 LCP +
ΣΣ
Σ
(u)))
P(w u, u) log (4) ma(e) (u, v)
1=1 k=0 EW,'
|s|3
P.te (s, CP log (1)
+0
(.)e)(s.a)
1=1
4-1
00
LCP
+18
+
CP + log (1)) | log (1)
k=U
T-1 4-1 3ΣΣ
Skt+1 log (1)
+0
L
P. ( u)
maxr (u, v)
1=1 k (A.
T
Sa+1 logz|log[0 (4) maco v)
<
|||||||| (C + log (1)) log (4) +
Σ
Σ
Σ
P (u, v)
t=1 k= (
T 1-1
S (c) (.
+0
L 1 Σ
q Pate (u, - (u, r)
1I K=0
S.
17

---

0
|| (C +og (i)) log (1) L ΣΣ E (u
I
Skk+1 log (4) mi(e) (u, v)
T L-1
+0
LVB
S
ΣΣ
E
g (u, 9 ( (u,
1=1 k= (u.))SExx
00
|S||)A| (CP log (1)) log (1) + L
Σ ViSk+1l (1) (VVISSaII (S (i)
=0 (1ST+)A) + log (t)) log (1) L|S| MIATTooo (1)),
where the second step uses the Cauchy-Schwartz inequality: Ewesey v u( S SSt41 and also applies Lemma D.5.3; the fourth step bounds mase) (u, v) z log(t) for any (u, v) and |Sh-1 [S]; the fifth applies Proposition D.5.2, and Corollary D.3.7 bound EL E(un)ES 1a P. (u, - Re
T (u, v) by O (LCP):: the last step uses the fact that Voy + for any x, y 2 O, and thus we have Ei=1 VIS I 2 = Syl S|.
Finally, using a similar argument in the proof of Lemma A.2.1 to bound the case that Econ A EAST does not hold, we complete the proof.
A.4 Bounding REG
Lemma A.4.1 (Bound of REG).. If learning rate satisfies v) E (0, st.. then, Algorithm ensures
REG O |S| (1) + + (LISIC logT + LT) + SLT)
"
Proof. We consider a specific transition Po defined in Lee et al. [2020, Lemma C.4] and occupancy measure such that
u (1 (1-7)
1
Po.to
TIA
where na is policy such that action a is selected at every state. By direct calculation, we have
Dolu, ②1) Σ
Σ
log (1(,,,,8))
T (3) -11 -1)
u(s,a,8')
u(s,a,8')
k=0 (s,a,"")E,
4-1
log Ti(s,a,8))
Σ
Σ
([Sa|lAl[Se++/lug (uss a, 1)
u(ssa,s')
0=0
(s,,,
0= (s.a,")EEW
1-1
(1(s,a,5') log
Σ
Σ
u(s,a,8")
A= (s,,,"))W,
< 3| A| log (t),
where the second step uses the definition (s, = S| for k = 0.... , - and the fourth step lower-bounds u(s, a, s') 2 TS|S||A from [Lee et al., 2020, Lemma C.10], thereby u(s, a, s') 2 1. and upper-bounds क (s, a, 8') 1.
1
According to [Lee et al., 2020, Lemma C.4], we have Po. ng Q (P.). Therefore, is a convex combination of points in that convex set, and we can use Lemma A.4.2 (included after this proof) to show
(p u, Po b.)
18

---

- ||S) log (1)
T
T
+ 27)
ΣΣ
[, a)² + m (s, (s,
Σ
Σ
q
Pi
(s,a))b(())) (17)
8,
3/
On the one hand, we bound the first summation Eq. (17) as
((88,))
Pom (s,
ΣΣ 5,a
P..m (s,
S LT,
8.0
since g a) S (8, a) by definition of the upper occupancy bound. On the other hand, we bound the second summation Eq. (17) as
T
T
Pom ()) 4L
(s) = (OT]S( T)
(18)
1=1
t=1
where the first step uses the facts that by (s) < (s) and Ea (s, S (r (s), and the last step applies Lemma 3.1.
Putting these inequalities together concludes the proof.
Lemma A.4.2. With 1j E (0, b Algorithm I ensures
T
u.C, - b,) s Do(u, 2n it
Σ
ΣV
Eāa(s,)) (E((s.))+ +b())))
(19)
"
t=1 8,8
for any E O6 (P.).
Proof. To use the standard analysis of OMD with log-barrier (e.g.,see [Agarwal et al., 2017, Lemma 12]), we need to ensure that (s, a, 8') & (8, a) - br(ss) 2 since log (1 + x) 2 x x² holds
for any x 2 - 1 Clearly, by choosing 77 E (0, s.l. we have
Mi(s,,,s') ((s(s,a)-bill (s, a, (b( ass)
4Ln us(s)
-LL
~
where the first step follows from the fact that (, a) 2 0 for t, s, a; the second step follows from the definition of amortized bonus in Fq. (7); the third step bounds (s, s') I un (s).
Now, we ready apply the standard analysis show that
Σ q u -G-b) b.)
Σ (Dolu,
Dolu, q++1))
Σ Σ ())),,,))) (2c(s,a) b((s))
+
1
sta.s'
Do(u,T1) (T+
T
(T(ss,))((s((sss))) (E<(s,a)- be(s)
17
3.0,''
(1)
Σ Σ a) ())(s,))- ( bu(s))²
T
+1
7
1=1
19

---

Dolu, 91)
T
a)(s,a) (((s,a)-b((3) bb(s))
+1
t=1
s,a
(o(u, 71)
2m
Σ
Σ a)) (Ec(5,a)2 bs())))
7
where the second step uses the fact that (s, a, 8*) (0, a) Pass's, a) (see [Jin et al., 2020, Lemma 1] for more details); the third step follows from the fact that the Bregman divergence is non-negative; the fourth step follows from the fact Eg Pe(s' (s,a) the last step uses the fact that (x y)² < (a² + v²) for any H, y E R.
A.5 Bounding BIAS;
Lemma A.5.1 (Bound of BIAS2), Algorithm I ensures
BIAS₂ = (1S(C log 8LT).
Proof. We first rewrite BIAS2 as
T
T
T
BIAS₂ =
E
Eg
( q
PR
E 1
Σ
{q
Pit
bi)
+ E
Σ
Peiete by
=0
where (II) is bounded by O (ISICP log 7) by Lemma 3.1 (whose proof is included after this proof). Now, we show that (I) is bounded by O (ÓLT). Suppose that Ecos holds. We then have
( 8 - 1
Σ
P. (s
q
0s)
q Pu a) -f 0) + + Pite (s,(s,s)) ue ur(ss,) a)
Σ
p (s,
ax(
5,0
P (s) -q (s)
q (P, (s
Σ
(s a)
q P.t (s
ue(s)
()(),
8
6,0
CP
9 (s, - ve(s,a)
P. (s,a)
Σ Pq
(3)
u+(8, a)
8,0
CP
P (8,a)
(s))
where the fourth step applies Corollary D.3.6 to bound |g (. Pi (s) S C.. and in the last step, the second term (in the fifth step) is bounded by under Ecox.
Since y P.t (s, a) is fixed over all episodes, we apply Lemma 3.1 to show
T
CP (s(s)
V E,
- Σ
bi)
Σ
q P
(s.a)
be(s) S 0,
For the case that Ecox does not occur, we bound the expected regret by O (8LT). Combining two cases via Lemma D.I.I, we conclude the proof.
Lemma A.5.2 (Restatement of Lemma 3.1). The amortized bonus defined in Eq. (7) satisfies
Σ CP [.(3]
Et= (s()) and Σt= (s))((()) OOC for any 8.
20

---

Proof. In the following proof, we use the equivalent definition of (s(s given in Eq. (14), We first
show
r 1=1
Cº
S > 1= (8). On the one hand, we have
[s(s)
[log([S/T)
[u((s) = C.P
uc(s)
(s)
[[og([)[T)
C.P
[M)(() -} -1 - 2-1-1
Dog(1S121)
E
T
(Br(s)== = C.
2-5-1
1=0
Nog([S[T))
min ΣT [y = j}, CP)
WM
(20)
2-
J=
where the second step uses the construction of the bin, ie.. if ur (s))) falls into a bin (2-1-1,27 ,2-1) then, is lower-bounded by 2-1-1; the fourth step follows the facts that C.P. s 2T, and Σi=1 C. s C.. On the other hand, one can show
Dog([S)T)) Hyr(s) = -زز (s) S CP
T
T
2T
(8) = 4L
(s(s)
[log(1)/T)
Et= ((r(() = 5} [s((s) S
2 4L
2-j
1=
[log([S[T]]
min ΣT T -1=1 [(y((s) = 5}. C
21
2 2L
2-1-1
J=0
[log( S)20
min (2I. ((x(()) = 0}.
(21)
2 2-j-1
where the second step uses the construction of the bin, i.e., if ue (s())) falls into a bin (2-1-1, 2---112-- 2-x)) then,
it is upper-bounded by 2 and the third step follows the definitions of (e(s) and 2/ (s).
Combining Eq. (20) and Eq. (21), we complete the proof of Σ For the proof of Et (s) OISIC* log T), one can show
CP (x)
S ET= (s).
T
T [lo[[|[[T]] Po. (01) S C
Σ (s)) = 4L
(s)s)
T [[og([)[T)
H()(s) = ( =]]
{
2/(s) < CP
< 4L
2L f
(og()))(T))
T (s)((s) - =i]I z6(6) (o(()) < CP)
= 4L
Σ
2L
t=1
Tog([))T))
CP
< 4L
Σ
2L
1=0
= o (CP log (ISTT) O (C log (T))
where the first inequality uses the fact of Pe (s) S vs)s and the last equality uses |S| ST
21

---

A.6 Proof of Theorem 3.2
For REG, we choose min
| log(c) LT
1
First consider the case * 87."
8f.
| (t)
REG 0
+1 (L|SICe log T LT) LT8
||] log (t)
0
+ I + |S|CP log T + LT8
0 (ISIv MAlllloog log (1) LT |S|C log T + I.T5).
where the second step uses S 1 81. and the third step applies choice of r) in the case of 17 * 1 For the case of 1 SL. we have 7 v (444
81.
and show
REG O (L|S | log (t) + |S|CP log T LT6).
Finally, choosing 5 = 7// and putting the bound above together with ERROR, BIASI, and BIAS2, we complete the proof of Theorem 3.2.
22

---

B Omitted Details for Section
B.1 Bottom Layer Reduction: STABILISE
Proof of Theorem 4.3. Define indicators
9t.j I[ E 1--11
he.j I(ALG, receives the feedback for episode t...
Now we consider the regret of ALGj. Notice that ALG, makes update only when gtglhss 1.
By the guarantee the base algorithm (Definition 4.1), we have
E
Σ (((( - 24(4(() (4(T))))) (1()))
EE
31
gight. + (B2 + Bz0,) max Ir.j
+ Pr
Σ ci cighhts 03
LT.
(22)
1ST
We first bound the last term: Notice that 1E(1 19t55]
2-1-1 g.. by Algorithm Therefore,
gt.s
T
T
Σ
(e = 22
Σ
clos 22
(23)
1=1
By Freedman's inequality, with probability at least 1
7z.
T
I c. Bly
Σ
cl hes Σ
t=
22
2
+ log(T)
<
4
Σ
[g.. + 4L log(T')
(Cf 2L)
1Br log(T
(AM-GM incquality)
which gives
Σ c Pog.hu. 22 Σ Ele log(T(
-2- + 8T. log( (T) S 00
with probability at least 1 - 75 using Eq. (23). Therefore, the last term in Eq. (22) is bounded by LT < 4.
Next, we deal with other terms in Eq. (22). Again, by EE(he,l9..)) 2-1-1 Eq. (22) implies
T - -(((
T
2 2-1-1E E
S
2-1-13,
Σ 9cu + (B2 + 830,) max It.s 1=1
+ T
1ST
which implies after rearranging:
T
Σ (e((m))) - le(
23

---

T
B2
Bz0,
E
2
31
9t +
22-111
+
2-5-1
max It.l tST
+
72-5-1
1=1
T
2
2,3 + 16 log] (Tg(T)
L
E
B1
+ 4,3
max It.j 1ST
Wi
2-3
T2-3-1"
(using that when Mt.j 2-5-1
and the definition of 0,)
wy
Now, summing this inequality over all j E {0, 10.1...., [log2 }. we get
Σ ((((T)) - (x(T))
We 2 -
1
E
N311
+ (B2 B3 (T)(
+ NBBCP
L
Wl
mineST we
B1T log TTp + (B2 33 BgLlog(T))pr) + PaC log T + 1)
0
E
where N & (log T) is the number of ALG, 's that has been executed at least once.
On the other hand,
b}}
E (((()))
LTE [T (pr TH s LE (pr]-
Combining the two parts and using the assumption 32 2 L finishes the proof.
B.2 Top Layer Reduction: Corral
In this subsection, use base algorithm that satisfies Definition 4.2 construct an algorithm with vT + CP regret under unknown C.,. The idea run multiple base algorithms, each with different hypothesis on CP; on top of them, run another multi- armed bandit algorithm to adaptively choose among them. The goal best base algorithm. This is the Corral idea outlined in Agarwal et al. [2017], Foster et al. [2020]. Luo al. [2022], and the algorithm is presented Algorithm 3.
the top-level bandit algorithm perform almost as well as the
The top-level bandit algorithm is an FTRL with log-barrier regularizer. We first state the standard regret bound of FTRL under log-barrier regularizer, whose proof can be found in, e.g., Theorem 7 of Wei and Luo [2018].
Lemma B.2.1. The FTRL algorithm over a convex subset Q of the (M dimeesisil simplex A(M):
Wt argmin wEf
l
log
W.;
ensures for all E Ω
T
M log T
M
w
Rx)
+ 17
2
2,
7
t=1
i=1
as long as spre, for all i,
Proof of Theorem 4.4. The Corral algorithm is essential an FTRL with log-barrier regularizer. To apply Lemma B.2.1, we first verify the condition me,al S where l, Ōτ, Tt,i- By our choice of
1
meac Cr,1l 5 17Cr, S
(because B3 L by Definition 4.2)
24

---

Algorithm 3 (A Variant of) Corral
Initialize: log-barrier algorithm with each arm being instance of any base algorithm satisfying
Definition 4.2. The hypothesis on CP is set to 2 for arm (i .., M [loge T))
Initialize: Pa,i = M,
for f 2...... do
Let
1-1
Wt argmin
W Σ Cr
rr)
Σ
log
WE (M)
where T+B.)
For all send W to instance i.
Draw i ~ Wt
Execute the иe output by instance
Receive the loss Ct,s, for policy Te (whose expectation is & (x(T)) and send it to instance i,
Define for all i:
Cr
G,5
Wiii
Pt. min +St Wr.i
Tt, = /3T (VPls- VPI-1.)) + (pr. - PP-1,s).
7 = T - VPL-1.5) + mB2we, (Pt.s PP--1s)
The right-hand side of the last equality is non-zero only when Pe.: > Pt-1,5s implying that Pt. wa,s Therefore, we further bound by
1
1
B.BBT Pa.
1V
BTT
(VPt.
(PL-1,8)
+m32
(pt,i
po-1,s)
Pr,
=TBB
1
VPt-1,
+
PL-1d
PPti
Pe.
Ptçi
3VBBTT T.T
+ n
Pt-1.
vb
for a, b 0)
Pt-14
Pt.
Ptú
Va
vb
va
(24)
TV BTT TVBBTT
n13
(Pt.: 2 1)
1
(definition of m)
4
which can be combined to get the desired property mw,, - rt,l S J
Hence, by the regret guarantee of log-barrier FTRL (Lemma B.2.1), we have
E
Σ (o,, c,,x))
M log T
s O
+ Ty
w (c,,- 12,
+
Σ
Σ Wr. Fe.s*
17
stability-term
bonus-term
where i' is the smallest i such that 2 upper bounds the true corruption amount CP.
25

---

Bounding stability-term:
T M
stability term 2n
2 2
+ (.)
t=1 i=1
where
M
M ΣΣ
2n
W Cr,Cr
2nj
2. = T(
and
M
T M
T M
2n
W L.
S 4n)
TTT
+ 4m
1
Pt-1,5
VPt-L.
/Pt.i
Pt,i
t=1 i=1
[=1 i=1
(continue from Eq. (24))
T
M
s 4 x
+ 4m
In
Pt.i
PP-
Pprs
Pt-
1 and 1 - In
VPt-1,1
VPc,
S 4n TM
4n M In T. (telescoping and using Po. M and PT. S T)
Bounding bonus-term:
T
bonus-term
Tt.
T
M
T M
I BT
+
A2
log
Pt.i
Pt- 1,
Vpt.
P1-
- (VPT, BIT + PT V poo.s 3,T - Po, B2
(continue from Eq. (24) and using 1 - a 5 aha)
0
(OBVTMM + +og2logTT) log - (VPr,,:.77 3TT + pr)
Combining the two terms and using 1) O (vaT+e)) ) M O(log I), we get
T ((((T)) - c..
T
(cr. - cc,+) cc.s))
E
E
V Bog T + 33logg
E 3T 3 (25)
On the other hand, by Definition 4.2 and that CP E 12 2-",, we have
E
Σ [c. (axx-((t))
< E 32
+ P.
(26)
Combining Eq. (25) and Eq. (26), we get
so (oVVVTloS' T 82 T +BggOP
E
Σ (((m))) (((()))((()))
which finishes the proof.
26

---

Algorithm 4 Algorithm with Optimistic Transition Achieving Cap-Dependent Bounds (Known CP)
Input: confidence parameter E (0. 1).
Initialize: V(s, a), learning rate (1 a) 256L epoch index and epoch starting time 4 = 1; (s, s'), set counters m. (8, a) = m. (s, a, s') = mo(s,a) a) = mo(s, a, s') 0; empirical
transition P1 and confidence width B1 based on Eq. (2); optimistic transition P. by Definition C.I.I.
for / - ,,..., do
Let di be defined in Eq. (28) and compute
C b.)) +
argmin (E)(P.)
9.
Σ T=t,
(27)
Compute policy ne from Ze such that Ty (a|s) x To (8, a). Execute policy иy and obtain trajectory (st, (t,k) for O,..., Construct loss estimator & as defined in Eq. (5).
Compute amortized bonus b, based on Eq. (29).
Compute learning rate 7++1 according to Definition 5.2.
Increment counters: for each lc L, (St, Or.k, st,4+1) $ 1, mi(St,ks aekk) E 1.
3k, mi (s,,e, (r.)) 2 max (1, 21,2mm (81,es dr,x)) then
b entering a new epoch
Increment epoch index i = and set new epoch starting time 44 = -tt
Initialize new counters: V(ss a, s'), mi a') = m a, 8'), m4(s, a) = m a).
Update empirical transition P. and confidence width B, based on Eq. (2).
Update optimistic transition P, based on Definition C.1.1
C Omitted Details for Section 5
In this section, consider a variant of the algorithm proposed in Jin et al. [2021], which instead ensures exploration via optimistic transitions and also switch the regularizer from Tsallis entropy log-barrier. We present the pseudocode in Algorithm and show that automatically adapts to easier environments with improved gap-dependent regret bounds.
Remark C.1. Throughout the analysis, we denote by QPTTTs a;r) the state-action value of state- action pair (s, a) with respect to transition function (P could be an optimistic transition function). policy and loss function r; similarly, denote by V (8;r) the corresponding value function.
Specifically, the state value function VP:(g;))) is computed in backward manner from layer L to layer as following:
0. PP (s; (s: - EEEA ( (als)- (r(s, + EvESu P(3")s,a)VPP
= SL.
8 8 81.
Similarly, the state-action value function (s, r) is calculated in the same manner:
0. (P r(s,a) EvEsuoe P(s [(d
s SL
s s SL
Clearly, PP (Sg: the state value of so, equal
VP (50; Ed - (r.
8581, AEA
This equality can be farther extended the other state as:
PP (P:T) = Ef
8f81 aEA
where P.a (8, al u) denotes the probability of arriving at (8,a) a) starting at state under policy n and transition function P.
27

---

C.1 Description of the Algorithm
The construction of this algorithm follows similar ideas to the work of Jin et al. [2021], while also including several key differences. One of them is that we rely on the log-bariier regularizer, defined with positive learning rate (s a) as
(1
(((s,)))o
(28)
The choice of log-barrier is important for adversarial transitions discussed in Section 3, while the adaptive choice of learning rate is important for adapting to easy environments. The formal definition of the learning rate is given in Definition 5.2, and further details and properties of the learning rate are provided Section C.7.
As the algorithm runs a new instance of FTRL for each epoch i, we modify the definition of the amortized bonus by accordingly.
4L (c(e)
if E Hf[log2 uz(s)] flog2 u, (s)]} s 26
C
(8))) = b,
(29)
else.
The bonus be(s) in Eq. (29) is defined based on each epoch i, in the sense that E'=1 [[ [logg ur [s)] [log2 [r]s counts, among all previous rounds r = li...., in epoch i, the number of times that the value of u. (s) falls into the same bin us()).
Again, for the case of analysis, the analysis we use the equivalent definition of the bonus (s(s)
defined in Eq. (14), except that the counter 2 (s) now will be reset to zero at the beginning of each epoch i.
Next, we formally define the optimistic transition as follows.
Definition C.1.1 (Optimistic Transition). For epoch i, the optimistic transition P,: SxAxS + [] defined as:
Pi(s'(s,a)= max Edees min (P.(6'ls, 5'),,,
B((s,,,,))
(s, E We. (s, E Sa and s' = 8L
where Ps is the empirical transition defined in Eq. (2).
Note that the optimistic transition P.(-18,a) a)) is valid distribution have min (P.(''1s,)), a = Σ
max {0, P.(''ss,a) - Bi(s, 5'))
S
a'ESt
We summarize the properties of the optimistic transition functions in Appendix C.8.
C.2 Self-Bounding Properties of the Regret
In order to achieve best-of-bont both-worlds guarantees, our goal is to bound Regy("*) in terms of two self-bounding quantities for some & (plus other minor terms):
T
S (x) =
2 E
(P,))(8,a))
tm
(5)
(30)
52(2) = Σ
T E
Σ
(s,)
These two quantities enjoy a certain self-bounding property which is critical to achieve the gap- dependent bound under Condition (9), as they can be related back to the regret against policy " itself. To see this, we first show the following implication of Condition (9).
28

---

Lemma C.2.1. Under Condition (9), the following holds.
Regr((") 2 E
Σ E
Σ
q f (s, (s,
-c -C--2CC - -I2CP. (31)
Proof. From the definition of Reg-(1) (x*), we first note that:
Regr(#)) (x*)
E
PLtTe P, ,,)
T
E
P.ue g. , k1)
+ E
-9
+
Σ
q Pix
12)
1=1
t=1
2 E
g Pot 61)
2T.CPP
2
ΣEΣ Pa (s)
ofee (f)
where the third step applics Corollary D.3.7 and the last step uses the Condition (9). We continue to bound the first term above
E
Σ
(s,
SF (s)
2
E
Σ
Pit (s)
1=1 stSL (s)
T
E
Σ
Σ
(s - (s, a) A(s,a)
8.88 (1))+(()
2 E
Σ
Σ (s, L2CPP
t=1 N ast
where the last step a(s,a) (0, I.] and Corollary D.3.6.
We are now ready to show the following important self- lafl-bounding properties (recall AMIN ming A(s,a))
Lemma C.2.2 Selff-Boudding Quantities). Under Condition (31), we have for any 2 > 0:
1
(x) < = (Regr( + C 2T. + 1.20P)+
2
4AMIN
82(x) S (Regr( + 2LC L'CP)++
+1 2
Σ
4A(s,a)
syfa ast (s)
Besides, it always holds that (x) Vx LT and S2(x) S L.SAATT
Proof. For any 0, we have
8 (z)
x
E
2zAnm ΣΣ
Σ
(s,
2= AMIN
tm
8æ88 (s)
29

---

Σ
o (B +
MIN
42AMIN
17st att"
(x²) + C + 2LC L2(C)) + 4
where the second step follows from the AM-GM inequality: 2/zz S + y for any 2, y 2 and the last step follows from Condition (31).
By similar arguments, have (2) bounded for any >> 0a:
Σ sphen (*)
E
(s,(,, a) Σ (P
(zA(s,a)
+ 2IE
Pusi (s,
42A (s,a)
8 (8)
StSL ag (e) t=1
(Reg + o + 2T.CP + +T7CP)
+ Σ
x
4z)(s,a)
Sfel (s)
Finally, by direct calculation, can show that
T
(1)))=
E F. E
Σ
(P)))())
S SVx.177 LT,
1-1 opea (s)
(e according to the fact that Eefoe EoEAgRETi a), a) S L. On the other hand, S2(x) is bounded as
(x) S T. [S|AA
Σ Eg
P (s,
Sø8L. (4)
with the help of the Cauchy-Schwarz incquality in the first step.
Finally, we show that Algorithm 4 achieves the following adaptive regret bound, which directly leads the best-of-bothh www.ooffoooworteeeoe guarantee in Theorem 5.1.
Lemma C.2.3. Algorithm 4 with 5 1/T² and learning rate defined in Definition 5.2 ensures that, for any mapping xt S + A. the regret Regr is bounded by O ((CP 1) L || log? (4) plus
(s (L*)S|"AA| (4) + Sy (L")S]|A[|og (1)))
The proof of this result is detailed in Section C.3. We emphasize that this bound holds for any mapping n². and is not limited to that policy in Eq. (9). This is important for proving the robustness result when losses are arbitrary, as shown in the following proof of Theorem 5.1.
Proof of Theorem optimal deterninistic policies in hindsight and obtain the following bound of Regr(#))
5.1. When losses are arbitrary, simply select x* A where # is of the
o ((CP + 131 log (4) + S, (L*IST (1) + S2 (L"IS|IA log (4))
=o =0 +1) L (() 1 log" (1) + V L Iog (4) + v (215|21A//T1g (1)
where the first step follows from Lemma C.2.3 and the second step follows from Lemma C.2.2.
Next, suppose that Condition (9) holds. We set n² as defined the condition and use Lemma C.2.3 to write the regret against x²* as:
(m²" ) S (S, (L log (4) + S2 (L3ISTIA) (4)) + E (CP + +1),
30

---

where j > 0 is an absolute constant and & O [ (1)).
For any 2 > 0, according to Lemma C.2.2 (where we set the a there as =/2w), we have:
(x² (Regr (1²) + C + +LCCP +I2CP)
+ 1=2
1 A| (1)
LA (1)
+ Σ E
+ (CP) +1).
AMIN
Ass
SfØL ax)
Let = - - and U 1 Al Alo
EoffL Eapr((s)
1 PSSIA (s) [(,0)
Rearranging the above
Ani
inequality leads to
Regr(m=) 2 =C + 2LC + 1PPP))
I²U
& {(P +1)
1-2
211 -2
1-2
(CL + 2TCP + C22C).
+++++ 1)
I²U + (1+ !) E ECP +1)
+
x
- (c+ +2LC C + + E(CP +1)) + Y² 2 + (C +1).
Picking the optimal x to minimize the upper bound of Regy(T*) yields
Regy( = 2/ (CL + 2LC L3C + +P + (CP + PPU + 242U + (CP +1)
5 2 2//(CL + 2LCP + 12CP +E(CP + P) 4 + (CP +1)
(VIC++ L2)0+ log (1)
U + || log" (1) (C +1)
0 VUCL + U + 13 A log" (1) (CP +1))
where the second step uses V + S v + for any 2, y E Ryo and the last step uses 2/zy S y for any x 2 0.
C.3 Regret Decomposition of (x*) and Proof of Lemma C.2.3
In the following sections, we will first decompose (egr(=*) for any mapping n- S - A into several parts, and then bound each part separately from Section C.4 to Section C.7, in order to prove Lemma C.2.3.
For any mapping 'T S + A, we start from the following decomposition of (x*) as
T
T
9 Parse li) - Po Ee - bi)
Pe Ts - b1)) bb)-((Rrxx
(o , bz
+E
ERROR1
ESTRBG
(32)
T
Punn" Eo 4bb)) - ( k2)
+ E
ERROR2
where P. (2))) denotes the optimistic transition for episode for simplicity (which is consistent with earlier definition such that q. P..... Here, ESTREG is the estimated regret controlled by FTRL, while ERROR and ERROR are estimation errors incurred on the selected policies ( and that on the comparator policy x² respectively.
31

---

In order to achieve the gap-dependent bound under Condition (9), we consider these two estimation error terms ERROR, and 2RROR together as:
T
E
q Pr .1) ,,
(ofrree Ee - bi) + Popix .es -2e-
(b-b) b1)
(pPot)
(33)
T
(a P li) - (oPite Es E4 - by + (PPeer Ee E6 be
= E
where EE, [:] denotes the conditional expectation given the history prior to episode t.
To better analyze the conditional expectation of the loss estimators, we define ae. 31 S x A + as:
(s(s,a) a) q P (s. a (s.,
(q Pe (s, ( ((ss
8e(s, &
ue(5,a)
(s
which ensures that E, ())
(8, + Be(s, a) for any state-action pair (8, ().
With the help of ae. 31, we have
9 PenTe Eg
E
- bt)
= (P ..a) +
+ ( (c by). Putt .0t) + ( Pt BB - b.
Para
E.
bt =
which helps us further rewrite Eq. (33) as
T
T
E
9 Peime
Pate ka) (
+ Σ
g Pm gPann, E2))
m. {b) - -( as)
(gfPnn .ai) (op :le)
+ E
(34)
9 Pirt ,B -Bb- bi))
+ E
Pi. be By +
Based on this decomposition of ERROR + ERROR2, we then bound each parts respectively in the following lemmas.
Lemma C.3.1. For any 8 E (0,1) and any policy sequence ( (Te) Algorithm 4 ensures that Pax Pixx" .1) -CPLL
T
E
(a Panke Pi e.)
Lemma C.3.2. For any 8 E 10 and any mapping T² S A, Algorithm ensures that
T
Pins be B1) + (P 3r - bi) = O [| (T)).
E
1=1
Lemma C.3.3. For any 8 E 10, and any mapping "t S A, Algorithm 4 ensures that
(q P:Fi (= (e) ( (
Pioe, as) + ( PoP "aaaaa)) as - (p .1)
= O (S1 (L3 (|7A log? (1) + (OP + L3 (1) + SLIS)PIA\T9).
Lemma C.3.4. With the learning rates (1o)T defined in Definition 5.2, Algorithm 4 ensures that for any 5 E (0, 1) and any mapping xt that,
ESTREG("** )+*)
=E
c Peite -.-.a)))
-mn) (pr [T -aa-- bn)
-bbb)))
O (S2 (L?IST|A||og (4) + (c +1) |AA logg()) +
32

---

Proof of Lemma C.2.3. According to the previous discussion, we have the regret against any mapping π² S + A decomposed as:
(x
E
Pi - -PPi +
Σ
q &pix'
-gf ki)
t=1
P Pi -B1) Σ
Pi,
3r bi)
q
(q Pint, , Ea) - (qPrite, + (oPrrr ass) - (p ,l)
E
b PP Pe bi-bbil
Peime Es - be) -
+ E
where the first term is mainly caused by the difference between {Pi and P. which is unavoidable and can be bounded by (C. L) as shown in Lemma C.3.1; the second term is the extra cost of using the amortized losses b, to handle the biases of loss estimators, which controlled by Ö(CP) as shown in Lemma C.3.2; the third term measures the estimation error related to the optimistic transitions (P:)T- which can be bounded by some self- saff-boundig quantities in Lemma C.3.2; the final tenm is the estimated regret calculated with respect to the optimistic transitions (P.)T-, which is controlled by FTRL as shown in Lemma C.3.4. Putting all these bounds together finishes the proof.
C.4 Proof of Lemma C.3.1
The result is immediate by directly applying Corollary D.3.7.
C.5 Proof of Lemma C.3.2
Etm (gPotee be :b)] and E
[>in (gfine ,,, , - -ba) separately.
For this proof, bound E
Σt (gfrrsebee b ---))--
Bounding E
We have
P. Pritee ., - -Ba)
q
T
(q (s, - (8, a)) Ee(s,a)
P Panti (s.)(ss))) bi(s)
()
8.0
b((s)+ + (o 9 Pite (s,
())
(1,,0) a)
T
(s, a)b(())) + Σ ΣΣl1
(itiit ( (s,a))
1=1
8,0
(=1 8.0
T
d Oo (s, ICP.
1=1
8.0
where the second step bounds (s, a) < 1; the third step follows the fact that q Part (s, a) S us (1 a) for all (s, Let F, be set of episodes that belong to epoch i and let N be the total number of epochs through T episodes. Then, we turn to bound
P.ote (s, (s.
ΣΣΣ
Puote (s. (s,))b((s) ( (T) CP),
1=1
1=1 YEE,
33

---

where the last step repeats the same argument of Lemma 3.1 for every epoch and the number of epochs is at most O[[S]||||og T") according [Jin al., 2021, Lemma D.3.
Bounding E. E|E
9 P Be bi)] For this term, we show that for any given epoch i,
EIER, (gf.0r' , by) S which yields Ei= (gferr Br bi) < 0. To this end, we first
consider a fixed epoch and upper-bound
(P Br )
Σ 8,0
Pott (8,a)
( (gPon0(s)) (P)((s) (((8,a)
Σ q Pitt (8,u) (
C2 ue(s)
we(()
3,0
where the second step uses Corollary D.3.6 to bound (g (s) P (6)) S Cp.
For any epoch and episode E Eij, we have P. Pi(t)= which gives that
T
N
Pu.= B3 - bi) =
PU.F" 3B - bi)
i=1
EE
F
N
C. by(()
Pasti (s.a) Σ
(4(s)
8,0
LEE.
00
where the last step applies Lemma 3.1 for every epoch i. Thus, E ET= (qPix", ,e= -bbb)
bi)l=0 so
holds.
C.6 Proof of Lemma C.3.3
We introduce the following lemma to evaluate the estimated performance via the true occupancy measure, which helps us analyze the the estimation error.
Lemma C.6.1. For any transition function pair (P, P) (P and P can be optimistic transition), policy n, and loss function E, it holds that (g==,,0)
P.m 2 P.P..r where Z.P.at defined as
2 2...PoT (s) (s,
Σ ((5)(s,0)V
=((s,a)+ +
Σ (P(sls,,0) - P(s')s,0)) -P()))))))))PPPP
VP
3'ESucata
for all state-action pairs (s, a).
Proof. By direct calculation, we have:
VP (s; E) Σ (s
Σ (alss) (s,T() Σ P(315,0))PP:((55)
d'ESNOIIL
+ Σ t(als)
((
S'ESRCA-1
Σ
+ Σ T(als)
QP=(s,a;0--
Σ
34

---

E
E
q Pot (d', QP=(((
E
P(
(+) e'E aEA
= Σ ΣΣΣ
PT (d
k=)(s) S'ES aEd
where the second to last step follows from recursively repeating the first three steps. The proof is completed by noticing (g PM .e V P (so. E).
(p on) and (gPemr, ,0i) with g and o Paa" for any
According to Lemma C.6.1, rewrite policy x² as
9 Potee (o (ast,.a) Pmt, Z p...P.te) (q .aa) ( P
Therefore, further decompose
(9 Pite, Lx) (q a. + Po aa)) (Pp ,
E
Pi le 2...P.51)) (ftt" ;l
zPr.Por")
=E
E
Patte P.5t ,, - ac
pP..Pxx') (pPiie P.o.
az
PioePioe)
( Gpa (s, (le(s, ar(saa))
=E
1=1 ##88
TERM ((TT)
( - (s," ((P(s)ss,)) - P((o(1s,a)) v (Pitts'iaa))
+E
1=1 effEL aEA
r'E8K(141
TERM 2(
Pito, P...p. p.r.P.To.)
TERM ((5))
will bound these terms with some self- seff-bounding quantities Lemma C.6.2, Lemma C.6.3 and Lemma C.6.4 respectively. In these proofs, will follow the idea of Lemma 1.1.1 to first bound these terms conditioning on the events EEST and Ecos defined in Proposition D.5.2 and Eq. (4), while ensuring that these terms are always bounded by O (IS) in the worst case.
C.6.1 Bounding Term 1
Lemma C.6.2. For any 8 E (0, 1) and any mapping - A, Algorithm 4 ensures that E. [TERM 1 (xx*) is bounded by
o (S, (1
log (1) + 8|S) (C + +1) L S log (o))
Proof. Clearly, we have (s, a) < S for every state-action pair (s, a). due to the fact that ur(s) 1/ISTT (Lemma D.2.8). Therefore, we have TERM 1(x*) < | holds always. In the remaining, our main goal is to bound TERM I (TT* conditioning on ECON A EEST.
For any state-action pair (8, a) S x A and episode i, we have
4,s, a) - a,(s,)) (u, a) P.re a)) a)) (ue(s) (.)e(s)) (s(
2 0,
(s,
U4 ((())
35

---

conditioning on the event Ecos-
Therefore, under event Ecos A EEST, TERM I (**) is bounded by
1 PiTe (8, - gf (s, (s) (L((s, ox(s,a))
[=1 ST.L REA
T
- (pt(ssa)))) (ue(s) -gp-- (s) (s)
q Pit (s,a)
(1.,,))gttt -qptt
uz(s)
1=1 8782 aEA
T
(s, - rF= (s, (),
lur(s) - (s))
ur(s)
878 DEA
Σ (s, a) gp. as, ) (1())
2
[|S|p|A| log (1)
1 Σ
q (s)
(=1 ST.L
+0 + log (1)) /-1 A|log (1))
T
0
||STP|A||og" log (4)
Σ Σ ME
(g) -
(s,
(=1 STNE aEA
+ +0
((CP + +og (1)) ( (1)
0
L2|S|P|A| log (1)
EE Σ
(f + (CP + (1) 1 log (4)
1 SfEL (*)*
L2 131S|PIA| (1)
DE E
( + (CP + S| log² (1)
[=1 SL (s)
where the first step follows from the non-negativity of le(s, a) (s a): the third step applies Lemma D.5.4 with G = 1 as Ea [q Pm (s,a) q P (s. I q (s) S ur(s); the fifth step follows from the fact that Exysr Enes ( a) pp' (s, as) S (s,a) 2L E. (o ( a) according to Corollary D.3.5; the last step applies Corollary D.3.6.
Applying Lemma 1.1.1 with event Ecox A EEST yields that
E TERM =
E LV
12|5??|A|00 log2 (1)
DE Σ (P)))
1=1 SoEeL (+)
+ +0 ((CP + log (1)) L L31 (1) (|ATT)
= =0 (8) (T.3)5)2 A log" 2 (1) + 115871117 + (CP + log (1)) 1.31s)+ (1)
C.6.2 Bounding Term 2
Lemma C.6.3. For any 5 E 10 and any mapping T S > A, Algorithm 4 ensures that
E [TERM 2(T")] = o (S, (L]S) A log² (1) + & + L|S| (CP + +log (1)) log (T))
Proof. Suppose that Ecox A EEST occurs. We have P(s'ss,a) 2 Pr(s' (ss' = (rcy( V(s,a, E = 0,.,,
Therefore, we can show that
0 5 Σ ((s'|s,a) - Pe(5)1s, VPar
S'ESk
36

---

= = =o(4
(1
S log (t) (s(e)(8,a))
|S| (CP + log (1))
+
(s,
where the last step follows from the definition of optimistic transition and the fact that (s a) S 1. By direct calculation, we have TERM 2(xr)) bounded by
(s.00_ (V q Piti (s. - P (0.00)
S log (1) (s,
|S] (CP + log (1))
(s )
o
9 PiTs (8, -fa
+
8F8L GEA t=1
T
|S| log (1)
0
L Σ
-pp=
(s,
878L aEA 1=1
Pite (s.a) + 1o)) 8581. aEA
+0
L
(s,c)(8,a)) a)
-0 L
1E
1 (s. a) - Pix (s,
S log (1) (s,
L|STIAA (CP +og (t)) log (1) (t))
where the last step follows from Lemma D.5.3.
Moreover, we have
ΣΣΣ 8581, d=At=1 1=1
q Pite (8, -q
P. (3,00) v Ig (s, - -q -f= (s,
S|| log (c)
(
P (s, a) | (t)
(s,))
5751, aEA 1=1
T
q Pise (s, a) () (c)
Σ (g, - -gPar (s,
Σ SYAL aEA t=1
4/82 RE
| log (1)
ΣΣΣ
( (8, a) - gp==" (s, a)4
89881 aEA 1=1
T
LISTIIA||og (4)
Σ
(PF)(),)))
t=1 stat aft"(() (5)
T L|ST (4)
50
3E
( + Lo CP
El ($)
where the second step uses the Schwha-Schwarz inequality; the third step applies Lemma D.5.3; the fifth step follows from Corollary D.3.5; the last step uses Corollary D.3.6 and the fact that Vz+ V Ve for any y 0.
Finally, applying Lemma D.1.1 finishes the proof.
C.6.3 Bounding Term 3
Lemma C.6.4. For any 8 E 10, and the policy T², Alloriith 4 ensures that
[TEMM 3(x*) (S1
(1) + SL|S}?AATT + (CP + log (1)) L log (4))
Proof. Suppose that Ecox A EEST occurs. We first have:
( Pit, 20,,PP. P.
2 P.a,
ac
37

---

Σ
Ee
q
Pate
(s,0)
Σ
- (yPa (5):a)) (s
SpELL REA
S'E
2 Σ
( / (s':ar) (v: (slaaa
8788 ac 5'E8k(1)+2
Σ
Pat (s,0)
P(s'ls,a)log(() (1.0)(
(dtraa)):))))= v (s. (6,
(s,a,"")Ew,
CP (c (1) )
+0
L|S Σ
E
q Pot (s,a)
$88L REA
where the last step follows from Lemma D.2.7 and the fact that P.i (s':aa) S L for any x.
By applying Lemma D.5.3, we have the second term bounded by On the other hand, for the first term, can bound
O ((CP + log (4) [ (t)).
VP (s(:0s) V Pr (s': as
P. (d::0)) V P (d(:a))
Prise me (uls') 1T (vlw) - == Q R (u, v3))
UF VEA
Σ
- (olu)]
WES AEA
0
Σ
g pimm (u, 2|s')
k=k(s') UEE upen (u)
0o
Σ
Σ
Σ
(u ols')
k=m((a') MES, vpfm*( (u)
where the first step follows from Lemma D.3.2: the second step follows from the fact that P (u, u; ax) E (0, L]; the third step uses the same reasoning as the proof of Corollary D.3.5; and the last step uses Corollary C.8.2.
Finally, we consider the following term
P(s'ls, (2)
Σ
Σ
* (s.)))
Σ Σ Σ
q Pi (u,
(=1 k=0 (B.0,)))EW
k= Sp viglat (w)
L-1
l Pite (s, P. Pi (u, r/s') (1ss')log'" (1)
3
misce (8,
(s,,,')WW, k= Sc (u)
q (s, a) (u, v(s²)
Pite P (u els') log (1)
Σ
(s)
0=
(EW,,")WW, 1=1+1 HES, (1)
Σ Σ E
Piae (s, ((s a)q ((,
(Ka,s")W W. k=h+1 WCSx (x)
L-1
T
Pixe (s, log(()
T
S L ΣE
ΣΣ
Σ
g Pite (u,
(s,
1= BES AEA
WES (u)
38

---

r
|| log² (1)
(
h=0
vftt"( (u)
/|S 1ogg (4)
EE Σ
(s.0
1= SHAL (tt"(()
[|S|?|A|log" (4)
3E
(P, VCP 1188 (f)
CP - log² (4)
where the second step applies Cauchy-Schwarz inequality; the third step follows from the fact
that Eees, EaE ExeS * as) a) (u,"" o|s') = q (u, u); the fourth step
follows from Lemma D.5.3 conditioning the event ESST; the fifth step the fact that v + S Vx + V for y 2 0; the last step follows from Corollary D.3.6.
C.7 Proof of Lemma C.3.4
In this section we bound ESTREG using a learning rate that depends on t and (s,a), which is crucial obtain self-bounding quantity. Another key observation is that the estimated transition function is constant within each epoch, so we first bound ESTREG within one epoch before summing them.
Recall that Es is set of episodes that belong to epoch and N is the total number of epochs through episodes. By using the fact that P. P. for episode belonging epoch we make the following decomposition ESTREG(T")
N
9 PioT -omt--Pent Pitt" (.l-bb)) bo))
ESTREG(TT) = E
E.
N
n
N
< E
EN,
Pi.tTe Pentt ,
b.)
= E
Σ ESTREG;(TT)
LIEE.
This learning rate is defined in Definition 5.2 and restated below.
Definition C.7.1. For any t, if it is the starting episode of an epoch, set ()( -256L2|8): otherwise, we set
a))
()) = a) - 27)(s,a)
where log(t) and
a)) Paoo (t (Q (s,a; (s))))
(35)
Importantly, both Q Po (s, a; Pe) and (P can be computed, which ensures that the learning rate properly defined.
C.7.1 Properties of the Learning Rate
In this section, we prove key properties of (s, a) and of (s,, a). We first present some results in Lemma C.7.2 that useful to bound (s, a), and then these results to bound (s,aa)
Lemma C.7.2. For any state state-action pair (s, a) and any episode t, it holds that
Purs (s. (s. Ei) S L, and q Pi.m, Pi (s: S L, V(s,a) E SxA. which ensures (s, a) (QPr a; (.) probability event EcoN holds. Then, further holds for all state-action pair (s, a) that
y PPr 2i) E 1-L, L}. Suppose that the high-
q Pu (s) E, ( (s, (il)--PPooc Pu (s: (x
( P. (s. (s) ([(ss)) + L)S(C?).
where Pr here is the optimistic transition Paty defined in Definition C.I.I.
39

---

Proof. We first verify y ( ( S L.
P (s, (s (s, a; 2x)
q (s,0) Σ ΣΣ
q Peote (u, o/s, a)l
h=)(d) WEA
Pestee (u, o|s,)) (u, w)e v) 21 v)
= (8,00 Σ
EE h=k(s) NESUEA
q
(s (8, (8,0)1 Pi ( (u, v/8,a)
Σ Σ
1((uv)
Ue (1,
k=k(s) uc DEA
Σ
(l L.
k=s(s) NES,,
where the second step follows from the definition of loss estimator, the fourth step follows from g (s, (yy (u, als,a) S g (u, S us (u, v), and the last step uses the fact that ExES, EvEa (u, v) = Following the same idea, we can show that q Pe. Pr.5 Ee) S as well.
Next, we have E, (( - PP (s) (s:.a))
bounded as
Eg (
v Print (s; (s: )
27
= Ex
QRio - (a Σ (
(s,
a'ta
( (s. ( (s.
$ 2 B,
27
Σ (o
+2. LE,
a'zta
(I ( (s.: ) (36)
(s)
= 2 21-1mm (alss)) E,
2T,,
a'=ta
where the second step follows from the fact that (x + =)² (x² + 2²2 for any x, y E R.
By direct calculation, we have
E, [00 (P (s, 2 "]
E,
Σ Σ Σ
Eg Paite (mmmmaanlss
k=k(() SE yEA
< L.EE E,
Σ
ΣΣ
d Po (2,11s,
A=k(()
FES BEA
4-1
L.
ΣΣΣ
9 Peime (z. yls, P.me
(1.s, y)
k=)(() SES UEA
40

---

4-1
(9h
L. Σ Σ
q Purt (z,y)s,a)?
(e y)²
ka) DE Sa yEA
q Peitte (2. y y/s, (l) ) (
E
Peite (2,y)ss,) ΣE
g Pima Ra (s,a) k=)(()) #ES yEA
(1(
u)(s,a)
q Prima (2,yl,,)))
9 (Pim((s))) k=) SE yEA
(1(,,a)
Σ Σ
d Pimma (x, (2, (1,
(x,)))))) y)
C.
(37)
(x v)
Ue (2, v)
k+) ZES yEA
where the second step uses Cauchy-Schwarz inequality; the third step uses the fact that (s, a) Es(s', a') 0 for any (s,a) + (s', a'); the fourth step takes the conditional expectation of Ex y) the sixth step follows from the fact that gP (x, v/s, a (s, a) S g (x, y) S un (x,
according to the definition of upper occupancy bound; the last step follows from Corollary D.3.6.
Similarly, for the second term in Eq. (36), we have
)
)
27
E2,
Σ
byfa
27
< LLE. E,
Σ
ΣΣ
Σ (bbls) Puote (r (x.vss))
Ee ui
k=)(()
#.ES& yEa
byta
= E,
Σ
Σ
Σ Bittee
(e(bls) (1 (1.
l kmk(()) SE yEA
(g (PPine((r,))
S Σ ΣΣ
Σ
(a(lss) Purte (o.
ux( y)²
k=k(s) SES yEA
Σ
1-1
ΣΣ
Σ byaa
(b(s)) Pioty
(
g (z.1)
I (s) k= ZES, yEA
ue(x,))
g (x. v) (x( v)
C.P
S (P))
Σ Te (b|s)
ΣΣ>
9 Pe.Te (z. (l),)
+
(38)
ue( 8)
bitta
k=
SES DEΛ
where the first three steps are following the same idea of previous analysis; the fourth step uses the fact that Ex qº Piote (s) (b)s)g Pe.m (z, yl.,)))))) S g Pioma (z, y): the last step follows from Corol- lary D.3.6 as well.
Conditioning on the event Ecox, we have the term in Eq. (37) further bounded as
L
Σ
L-1
o Pumi (x, ( (1,))ssa)
q Pite (x.
v)
CP
+
q (s)
ve(x,v)
ux(I,
(==(())
nES, yEA
L
Σ
4-1
Pritee (x. vl,
1+ ue (2x v)
cp
k=k(s) #ESt VEA
L
Σ
ΣΣ
Piome (x. vls,))
q
k=)(()) DE VEA
41

---

L
ΣΣΣ
E
q Ponte (2,),,,)
C.P
(n((,,))
k= SESu yEA
I,2
I.C.P
ΣΣΣ
L-1
Peiee (2. yl.,y)ss))) 2e(
+
(39)
PPrmie (8,a)
q (s,
k=b(() #ES NEA
where the second step follows from the fact that gº p (x, v) S (x as P E P.(0) according to the event Econi the last step follows from the fact that Exes, Eyen a Pime (2, S 1. Following the same argument, for the term Eq. (38), we have
Σ Te(b(s)
Σ ΣΣ
ΣΣ
(2,
(f u,(,,y)
Ci us (x, 8)
q
Pittee (s)
lifa
k=k(s) DESI yEA
(Tb(bs))
L+ Σ
( biaa
U4 (2x
kmm((s)) SE YEA
1,2 (als))
LCP
( y yl,
Pe (a,
Σ (b|s))
Σ
(40)
PL (s)
U4 ux y)
bfza
k=k(s)
DES& yEA
Plugging Eq. (39) and Eq. (40) into Eq. (36), we have
Pa Pi (s,a)² E.
Pe (8; (s:
2 + (s,)))))
LCP
Σ
Pe.me (x, b/s, a)
I
x=(a(s))²
g (P,))(85a))
(1( V)
k= SE yEA
+ +24 PiTT (s,a)
La (1 m((a(s)) (s)
LCP q (s))
ET((b(s)
Σ
L-1
Pi yls,
ux y)
bitta
k=)(()) ZE DEΛ
0
[3 (
L-1
Peime (x..yl..a))
LCP ( a) Σ ΣΣ
+0
Me(x, y)
k=)(e) SES yEA
Peiee (a, (x (1, b) (2(
+0
LCP 9 (s))(s) Σ Tee (bls)
ΣΣΣ
Σ
bytl
km)(()) SE yEA
(s) (1-
L-1 ΣΣ
② Pr.te (2, () PL )
LC, Σ
+0
(x
k=)(s) mE yEA
1-1
Σbsa d Pa. (S) ( (b|s) Pr ( yls,
+0
I.C.P
ΣΣΣ
u,
k= DEA
5 Ri (s, (1 (a(ss)))+ +(SICf))
where the third step follows from the facts that g Po (z, yls, a)g Rom (s, s (., S (x for any (s, a), (x. S A, and Eoga 9² ( (s) P.. (z. P. (x.v) v) similarly.
42

---

The first part of Lemma C.7.2 ensures that (s E L2), which can be used to bound the growth of the learning rate.
Proposition C.7.3. The learning rate "It defined in Definition 5.2 satisfies for any state-action pair (s, a):
al S
D
E (s(5,a)
Traces (8)
where i(() is the epoch to which episode belongs and 4 is the first episode of epoch i.
Proof. We prove this statement by induction on f. The equation trivially holds for f. = 14(0)) which is the first round of epoch i().. For the induction step, we first note that Dvr(s, a) E [0, L² We introduce some notations to simplify the proof: we use c to denote Dus(s, a), x to denote (s, a), and the induction hypothesis is æ < vS + where S = D DE j=tut By (s, a) and y = 2he (5, a). Proving the induction step is the same proving:
I 2x
S VS+c+7
(41)
First, we can verify that f(z)= = x
c. is an increasing function of æ for 2 vc/2. c [0, L2]
2x
and 2 y 2 L, we can use the induction hypothesis S VS + upper bound x in the left-hand side of Eq. (41), and we get:
x² c/2
2x
S S+ 2v + 72 + c/2
VS+7
$ S+ c/2
7VS +2²
VS+
VS+r
VS+7
7/S +2
VS+ +
V
2/5 + 22
V5 +7
VS+
+7
2V5 + 27
Vs
+Y
2/S+c
S C
where the second to last step follows from S 2 and 2 L, which ensures that 2/5 + 2 2
2/5+>2 2 2 + e. The last step follows from the concavity of the square-root function which ensures that v & VS+C- 2/S+c*
Then, we can use the second part of Lemma C.7.2 to continue the bound of Proposition C.7.3 and derive a bound that only depends on the suboptimal actions.
Proposition C.7.4. If v4 is defined as in Definition 5.2, we have for any deterministic policy S + and any state + 81.
E
Σ
(s(s,a)
50
Σ
E
1
Σ
Pense (8,a)
(s)
t=
(ap((())
t=
4411 L|ST|AR
+ +0
8L2|S(|AA| (te+1 - tt) + /
Σ
CP
1=1
43

---

Proof. For each epoch i and sute-action pair (s, a), we have:
441-1
Exs
a)(s,a)
Be
v((8,a) a)
V
t=
(42)
(1
Ens
Σ
I (s) =+(ls)) + L|S|C?
f=t;
where the first step follows from Jensen's inequality, and the second step uses Lemma C.7.2.
Note that, for a = T()) we have:
P Pum (s, ( & q (s)) E {(blss
S E q (s.
(x)(()) (()(((
Therefore, we have
412-1
Er
Σ
Σ
a)(
aEA
r=t,
0
Σ
Be
Σ
La
(s) (((ass) + LISIC?
A
t=4
A
4
0
Σ
Byj
L2
q Pi (B, - -T(aass)
LIS
Cp
f+41-1
4+1-1
Σ
q (s:
+
L|S||A|3
Σ 1=
CP
at)((s)
1=
f11-1
f11-1
00
ol!|8|1A| (l+41 1- 1-4)
Σ
B4g
L
g P. (s,
+
L1S|IA|2
Σ
CP
as)
t=
4+11-1
4-111
00
|L"|ST|A| (1/41 1- -1-
Σ
Br,
L
Σ
(s,
L|S||A|2
Σ CP
(+)((s)
where the first step follows from Eq. (42); the second step uses the fact that / S Vo + /y for y 2 0; the fourth step follows from Lemma D.1.1 with the event Ecox and Corollary C.8.2; the last
step applies Corollary D.3.6.
C.7.2 Bounding ESTREG,(T)) for Varying Learning Rate
We now focus on bounding (TT") for an individual epoch i.
Notations for FTRL Analysis. For any fixed epoch and any integer E (4i1 1], we introduce the following notations.
F((g) = 4, Σ C (G+bb,)
+ (e(1),
Gt(g) = 9.
Σ (r (0.-bx) + ()()))
r=t
r=t
(43)
q: argmin Fe(q)
qe = argmin Ge(g).
gEN(P.)
(P)(P))
With these notations, we have qi = qt P..... Rus., Also, according to the loss shifting technique (specifically Corollary D.4.2), qi and qe can be equivalently written as
g: argmin (P)(P))
4, Σ (gr b,) + dr(g),
き argmin gen(F:)
q.
Σ (gr - -b,) + +g(()), (44) T=1.
44

---

where 9r : S x A - R is defined
(c(8,a) a) Q (s, (x.,
(45)
Finally, We also define P x* and
T2 u + T S
Σ 8,0
Ts
(46)
where yaua is the occupancy measure associated with policy that maximizes the probability of visiting (s, a) given the optimistic transition P.. Then, we have E (((P.) because u, Is E (((,))
for all (s, a), and 12 (P.) is convex [Jin and Luo, 2020, Lemma 10). Therefore, ESTREG; can be rewritten as:
h+111
qt u. - -bb)
EsTREG((T*) Et,
144111
f+41-1
b1)
Et,
9t U. Ee be)
+ E4
u.
(47)
1=
t=
0
=111
where term (I) is equivalent to
E2
(gc U, b1)
(48)
because (q:
0, D: - {,) according to Lemma D.4.1.
We then present the following lemma to provide a bound for ESTREG,
Lemma C.7.5, For gi define in Eq. (45), v defined in Eq. (46), and any non-decreasing learning rate such that 71 (8,a) 2 256L2IS for all (s, a), Algorithm 4 ensures that ESTREG;(T") is bounded by
L L|SICP T
+ EE,
Σ spf
M111 (s, (1)
(49)
b1.. - by ( 1])
+
O
min
Er,
Σ
v-2
t=4
1=4
Proof.
We start from the decomposition in Eq. (47).
Bounding ()) By adding and subtracting F.(a.) Gr (ā.), decompose (I) into stability term and penalty term:
L41-1
Erg
(un - b.) FF(()) -Gx
+ Er
Σ
G. - Pr(ge) - (v, ( bn))
Stability term
Penalty
As (s,aa) a) 2 256L2|S), Lemma C.7.6 ensures (s. a) (s, < (q, a) for all (s, which allows us to apply [Jin and Luo, 2020, Lemma 13] to bound the stability term by
- 1)
Stability term O Er, Σ
P b,
(50)
t=t:
45

---

The penalty term without expectation is bounded as:
h+1-1
GGlli) Fi(ee)
(v (v,2e-bb))
4-1-1
141-1
-q,
Σ
(GL-1(91-1) -F((g)))(()) + ((
v Σ
[ee bi)
(=++1
t
4-1-1
(+1-1
< (F. +
Σ (G-1(9%) -i(())) + C1.41-
Σ
(E. - b1)
t=tel1
11
= +
Σ
(0i-1(1)) - -b(())) + 11.1)
t=4+1
441-1
- )) (g((saa) ) + 11,11-1(1)
=a),(aa)) + E
Σ
1=t cf aEA
441-1
((-1))))) (q(s.a)
-.),(a)) + (v)
ΣE
v(s,a)
(=++) st88 aEd
(1((5,a)
841-1
(e(s,a)
ΣΣ 5751, aEA
ne, (8, a) log
Σ
(m)(s - 1-, a)) log
v(8,a)
v(s,a)
8=t++1
sf aEA
(9,((s,))
411-1
(9((s, a)
Th, (8, a) log
Σ
Σ
(7)(8,0)- - -+- log
1a (8,
T (s, a)
5Ø51, aEA
Imty sf88 aEA
4:11
2 Σ Σ
n. (s log (1) +
Σ
Σ
(n((s, - )-1((, log (1)
8F8L aEA
1=++1 st aEA
2 Σ
Mh41 (s, a) log (1),
(51)
StiL aEA
where the second step uses the optimality of ū--1 and ft so that G, (1-1((-1)) S G and -14:1119u-1111 Gt (I)); the third step follows the definitions in Eq. (43); the seventh step the definition of g
lower-bounds v(s,a) by 22 (s, a) for each (s, a); the eighth step
Now, by taking the equivalent perspective in Eq. (44) and Eq, (48) and repeating the exact same argument, the same bound holds with &, repalced by gr- Thus, we have shown
Mops 74 (1,, log (1) ))
(I) = 0 Et, Σ
Σ
asA
(52)
13)
2 be 2
+0
min
Es
Σ
B
Σ t=
199
bell -
vdlle)))
I=
Bounding (II).
By direct calculation, we have
111-11
Eg - b1))
(I) = Es
Σ
u.
t
112-1
T2 Br;
Σ
A||S
1
Is.a
u, be -ba
1--1-1
Σ 72
Er,
Σ
u
Σ
(4 bx)
SA||ST
8.0
1=4
46

---

where the first step uses the definition of v: in Eq. (46) and the third step applies the Hölder's inequality. Then, further show:
411-1
(II) S Et,
T
|A|S|
Is,a
max
u
Σ
(4:
be)
3,a
1=4
x
1+41
Σ
(Ce be)
T2
|A|SS
[+41-1
1
Et
2L
Σ t=(,
bi
T
80
t=
2L (tit1 14) + |S|T]
< E,
T
2L |S.
(53)
where the second step repeatedly applies the triangle inequality, and those terms are bounded by 2L in the next step; the fourth step bounds (s a) < 1 for all (s, a) and bounds Ei=, be()) S 2CP S by using the fact u (s) Z |.//
1 for all f, (see Lemma D.2.8); the fifth step bounds f.+1 - t, by T.
Finally, we combine the bounds in Eq. (52) and Eq. (53) to complete the proof.
Lemma C.7.6 (Multiplicative Stability). For qe and ou defined in Eq. (44), if the learning rate fulfills (a(s, a) 2 7i (8, a) = 256L2|S| for all I and (8, a), then, 20((8,)) a) S (1,8,) S 24c(s, a) holds for all (s,a).
Proof. We first show that
@ br
1 (00((0))
((5,
be(s)
2 a))
8,a
(()))))
a)s,a))
Σ
+ b(s))
a)²
(e(s a)
8,a
()(s
167.2
a))
+
a1(s,a)2
2s))
as)
8,0
as(
167.
g (8, a)²
256L2 S|
256L S|| (s)
8,8
8,a
1
Σ
S
1
(54)
256L|S|
S
8'
where the second step uses (x - y)² < x² 2² for any x, 2 0: the third step bounds
a)) < 1 and bx()) < 161.2
w.( according to the definition of Eq. (7); the fourth step holds
as (ess, a) 2 =) 2 and q a) S (s a) for all (s, a); the fifth steps uses the fact that E. (,.ss a)² < (2. a)) < us))
Once Eq. (54) holds, one only needs to repeat the same argument of [Jin and Luo, 2020, Lemma 12] to obtain the claimed multiplicative stability.
Lemma C.7.7. Under the conditions of Lemma C.7.5, event Ecos, and the learning 7 (e, a) defined in Definition 5.2, the following holds for any deterministic policy πt : S + A:
-+11-1
E,
Σ
Mhen (s,
+
Σ
1lge be b113--2))())
8588 aEA
t=
47

---

T++1 -1
0
Big L log (1)
Σ Σ
V
E
Σ t=
q p (
+ + Log((S(S))
SpaL apts (a)
1441-1
0
Ba
|T,11s|[A||1o log (4) (l++1 (2) +
11|5/9///2 (1)
Σ Cp
1=1.
Proof. We start by bounding the second part for each t:
|19 bell bellē-200 20(())
Σ 1
a),
( b((s))²
7(ssaa)
s vo(
+2
Σ 1e(5, a)
91 a))
(sss
6,0
6,0
where the second step uses the definition of and (ar u)² S 2(x² + y²) for any x. y E TR.
We first focus on bounding Σtet1
Ex,a n. (r bb)
44111
Σ Σ
an ())
1=4,
4411-
Σ ((ss)))b((s)
$
25612|S1
(=h,
4441-1
4L
Σ
Σ
(s)
256L2|S1
t=
= o (CP log((
(55)
where the first step uses the fact that (s, a) > 256L?|S|, the second step bounds be(s)² < 4Lbe(s) and >. a)) < (s), and the last step applics Lemma 3.1.
Then, we bound the remaining term:
f+111
(8)
ET
Σ
Then (8, (1) +2
(56)
7 (s
Using Definition 5.2, can bound Eq. (56) as:
44111 log (1)+ +
vr(s,a) a)
TE,
Σ
re(s,a) a)
8,a
3,a
= E,,
Σ
(19, log (1) + (T 1(0, - ye, 77, (s.
4
D
s.a
4 ) 7 (8,
< Er;
log (1)
8,a
= E,,
Σ
5log (1) Meu (1
s.a
(s(s ((5,())236L(IS) )
< Er,
5 5 (4)
1
Σ
log
8,a
j=t,
1+41-1
00
Vlog (1)E,,
Σ
Σ
Vz(s,a) a)
+ +
8,0
48

---

h+1-1
0
Et
Σ
Σ
V
2 1o (c)
Σ
(
s ast(r(())
t=
+ 0
Br, 8T. 1T log (1) (li+1 -4) \
T1|s///1 A/2 log (1)
CP
(57)
t=
where the first step applies the definition (8 a) which gives: M((.,)) the second step simplifies the telescopic sum and uses 7t, (8, a) 2 0; the third step uses D log(2) the fourth step uses Proposition C.7.3; the sixth step applies Proposition C.7.4.
[x.a] 3 (70+1(8,5)
-8, a));
C.7.3 Bounding ESTREG
Using the equality ESTREG(TT)=E now ready complete the proof of Lemma C.3.4. Lemma C.7.8. Over the course of episodes, Algorithm runs at most O (|S||A] log((") epochs.
ESTREG;(T*)] where N is the number of epochs, we
Proof. By definition, the algorithm resets each time a counter of the number of visits to specific state-action pair doubles. Each state-action pair visited at most once for each of the T rounds, so trigger epoch at most log T times. Summing on all state-action pairs finishes the proof. O
Proof of Lemma C.3.4. Using Lemma C.7.5 and Lemma C.7.7, we have ESTREG(T*)
E
ESTREGH((T))
N
L+ LCP
0
E
+ 18L (t) (f:+1 ti) +
A| (1)
Σ
CP
T
i=1
t=
h
+0
E
Σ
CP log([S[T) LLVlolo log (1)
Σ
Er
Σ
g g (s,
i=1
Sf81. axttr (a)
t=t:
((
[I++ L.P LCCISI) (S)
|S||A| 8T. 8 log ( T ( L|A|OP
T
+
0
(C11)114| log(1)2 + 1.2 log (1)
E
Perse (s,
SfaL af
((1+10* [1++(PIS)
[S]|A|)og(TT + 8L log (4) T + || (LAI + LCP)
T
+
0
(P1ST|A||og(()) + L (1) Σ
q (s,
sYAL axfor( (8)
((
[L|S]|A||og(]
=0
T + +882 log(()) - + CP L|S| log(t) + |A1915 log(t)
T
+0 (()5)\A|)og(1)) + A| (4)
(E R
Σ t=1
P. (s)
SFAL (+)
where the first step follows from the definition of ESTREG (T*); the third step uses the fact that N =0 [[S]]A] (T)) and the Cauchy-Schwarz inequality; the fourth step uses /ay S x + y for
any x, y 2 with x- P.C and y = |A]; the last step follows from Cauchy-Schward inequality again.
D
49

---

C.8 Properties of Optimistic Transition
We summarize the properties guaranteed by the optimistic transition defined in Definition C.I.1. Lemma C.8.1. For any epoch i, any transition P Pi, any policy and any initial state E S, holds that
g (s, alu) s & (s,aal), V(s,a) ESS A.
Proof. We prove this result via a forward induction from layer k(u) to layer L - 1. Base Case: for the initial state qe P..s (u, a/u) of (u, a/u) r (alui )) for any action E A. For the other state 8 E Sk(u), we have (s, as, qf" (8.alu) 0.
Induction step: Suppose q ( alu) q² -" ("(s, alu) holds for all the state action pair (s,a) a) with k(s) < h. Then, for any (s, E Sh x A, we have
(s, T(als) Σ
Σ
P.iT Ri
s'ESk 14'EA
<<(ass))
Σ
Σ
S'ESA-1 a'EA
= p (s,alu)),
where the second step follows from the induction hypothesis and the definition of optimistic transition in Definition C.I.1.
Corollary C.8.2. Conditioning on the event Ecass it holds for any epoch and any policy n that
(s a) < P. p(
V(s,a) S A.
Lemma C.8.3. (Optimism of Optimistic Transition) Suppose the highprrobbbilityy event Ecos holds. Then for any policy n, any (s.0) E S x A, and any valid loss function : x A + Rzo, it holds that
P (s,a; I Q (s,a;e), and PP.. (s: S V (()
Proof. According Corollary C.8.2, we have for all epoch that
Pun aa) < P.T (s, VuES (s,a)ESxA
(58)
Therefore, have
vP. (s: = ΣΣ
q P. PI (u, (u,
HEA
Pa (u, u())(,)((
= P.t (s;
where the second step follows from Eq. (58). The statement for the Q-uucctoon be proven in the same way.
Next, argue that optimistic transition provides tighter performance estimation compared to the approach Jin et al. [2021]. Specifically, Jin et al. [2021] proposes to subtract the following exploration bonuses BONUS; S A from the loss functions
BONUS,(s, a) = L min 1, Σ
S'ESMODI
where a, is the confidence bound defined in Eq. (4). This makes sure Q.r (8, az BONUS,) no larger than the true Q-function QP:i(s, az E) as well, but a looser lower bound as shown below.
50

---

Lemma C.8.A. (Tighter Performance Estimation) For any policy any (s,a) E S x A. and any
bounded loss function t: :: x A - [0, 11. it holds that
Q P.T (s, a: l BONUS:) I Q""." (s, V(s,a) E SxA.
Proof. We prove this result via a backward induction from layer L to layer O.
Base Case: for the terminal state s,, we have Q.. (s, a; l BONUS,) Q (s, E) = 0.
Induction step: suppose the induction hypothesis holds for all the state-action pairs (s,a) E S x A with k(s) > h. For any state-action pair (s, a) E Sr. x A, we first have
Pi (s BONUS;) = [(s, a) (s) +
Σ
Piluls (u; BONUS;)
NESh12
S ((s,a) a) (s, +
E
Pa aV (u;
MESN+1
Clearly, when E Eues B, a. u) 2 1, we have P (s, az BONUS,) S 0 by the definition
of BONUS,, which directly implies that Q (s, azl - BONUS,) S Q P (s, a; E). So we continue the bound under the condition Σ EneS Bi < 1:
Q (s,0ū l- BONUS;) ((s, a) BONUS;(S,
Pi(u|s; a) (u;)) uESh+1
Σ
< (() + Σ (Pi(uls,a) Bi(s, u)) vpi (u;
ue S
S {(, Σ
P(uul, (w;))
wES
= P Pa (8, a),a(),
where the second step follows from the fact that V PL.x (u: S L; the third step follows from the definition of optimistic transition P..
Combining these two cases proves that Q (s, a; BONUS,) S Q (s, E) for any (s, a) S5 x A, finishing the induction.
51

---

D Supplementary Lemmas
D.1 Expectation
Lemma D.1.1. ([Jin et al., 2021, Lemma D.3.6T) Suppose that random variable X satisfies the following conditions:
XX < R. where a constant.
x conditioning on event A, where Y is a random variable.
Then, it holds that [X] S E Pr [A9] R where A is the complementary event of A.
D.2 Confidence Bound with Known Corruption
In this subsection, show that the empirical transition is centered around the transition P. Let [T] : {1,.... ,T). Recall that Eg {t E [7] episode belongs epoch i). STAT and define the following quantities:
a) {t E [ 3k such that (s,,), = (s, V(s, S A, V. 2, L; V(s,a,s') WA Vi [T], Ak L; V(s,a,s)) E ViE [T], Ak < L.
(s,a,,s' |P [,)))saa) s,(s)s,,a),
(s, = Σ &',
(8.))
Note that based on definition of Ti we have m)(s,a) = (s, a)}. Then, we present the following lemma which shows the concentration bound between P(s s,a) and P.(s'(s,a)
Lemma D.2.1. (Detailed restatement of Lemma 2.2) Event EcoN occurs with probability at least 1- where,
ECON = sV(s, E Vi Vi V < (( P.( s Bi(s,,, (59)
and 8') is defined in Eq. (4) as:
Pi a) log (1) + 64
(CP + log (1)
B,(s, min 1, 16
(60)
mi(s,a)
mi(s a)
Proving this lemma requires several auxiliary results stated below. For any episode t [T] and any layer L, we use St denote an imaginary random state sampled from P(-|s (e,k). For any (s, a, s') E Wk. let
PIMG (6'1x, = m
Σ
IMG [+ = 8').
a) (ET:(N.))
We now proceed with couple lemmas. Lemma D.2.2 (Lemma 2, [Jin et al., 2020)). Event El occurs with probability at least 35/4 where
33 :v Wk k P(ss's, PIMG PIMG a) s a,(s,a,8)). and (s a, 8²) for any (s,a,8) E We and S k S I. defined as
P,(5'(x, a) m)(s.a)
14 14 3m,(s,a)
@i(s,a,s') min 1,2
(61)
We note that as long as |A[T 2 16/3, event m3 can occur with probability least 35/4 (unlike 1 46 in Lemma of Jin et al. [2020] )
52

---

Lemma D.2.3. Event Ee occurs with probability at least - 8/4 where
E² "Y<,,ss,,,))) E Wk. Vi, k PPNG (s'(s, P:(s'|s, a)) wi(ss,, and wi(s, 0, 8') for any (s,a,8) 8') E We and S k I. defined as
{1, 4Cf(s, as) w;(8,a,8))= min {1. (s
24P(8' a) loge m,(8,a)
6 6log m,(s,a)
(62)
Proof. For any fixed as, if ms 0, the claimed bound in E holds trivially, so consider the case ms(s,a) j 0 below. By definition we have:
PING (s'(s, as) m, (ET((s,))
Σ
(H&ING (M5LMM))11 = (/) [(SAMC)+11 = =s))
Then, we construct the martingale difference sequence (Xt a, s'))) { w.r.t. filtration (Fr (see [Lykouris et al., 2019, Definition 4.9] for the formal definition of these filtrations) where
X a. s') L [())+(())+1 = s'} (( s'} (P s, P. as)ss
With the definition of X,(s, a, s'), one can show
Σ
E [X s') 8')
(8T)(
Σ
E
[[5k)(())+1 s'} -188,A())11 = -()(()/)))) Fratss)
IMG
(ET.(..a)
E
2
T[ (1))) =8} - -188A16)+1 =$1) + (P (s Ps (a(ls,)))) Femco)
tETi(s.a)
Σ
E
211 (IHSMM))) = + +1118 5 - (c, FeR(())
(ETI(a,))
2
Σ
(P(s'ss,a)
P)(ssss)))())) +
(63)
(ET((s.)
where the second step uses y)
+ y22 2
for any x, E R; the third step uses (a y)² S
x? + y² for x. y E R2 and the fact that C.P (s, a, s') E [0, 1). thereby Cf (s, a, s')2 s (f, a, s'): the last step holds based the definitions of (s, a), SIMG +1 and $1,((s)11 well the fact that
CP (s, a, 5') is F1,k(s)) measurable.
By using the result in Eq. (63), we bound the average second moment o² as
ELET((E.)) E F(
2ETTT)())) + + cf(3,a,6)) (64) m²(s,a)
(s,
By applying Lemma D.2.4 with b = 2 and the upper bound of 0² shown in Eq. (64), as well as using the fact that m, a) = [s a)}, for any (s, a, s'), we have the following with probability least
1 - 5/(4)T|5 [A))
PIMG (s'1s,a) Ps(
8m, (4.a))(1))11
EvT, P,(s((s,a)
4lg
< p(
+
m,
3m,
4log
16ms(sa))7(s(P111
ELETI(EN)) (P(s')a, ()8)),,)= + Pa(5'18, a) + (s,
ms
53

---

$ P( (s a) EneT,(nn) P:(5((8,a)
8log
(1, am)(s,
12 12 EnET) (P(5'(8, a) + Pr(s"(s,,)) (3,
(s
EIET((E,) (()'(sa) ELET)(0.)) P,
8log
(s,0,
m; (1,
3m)(s,a)
12 EIET((O)) (P(s'|s,a) + ((s + Cl CP(ss,, m}(
24P(s'|s,a) logt m)(s,a)
8log
(3,
+
a)
as,
m)
(.(,,a,6') - a)
24P(s'|8, log
8 8log
v6 (C, (s, a, + log
+
mz(s,a) as,
mz(s, a)
Swi(s,,,8)
where the first inequality applies Lemma D.2.4; the second inequality bounds all logarithmic terms by logo with appropriate constant factor (using m,(s,a) T and |A] 2 2); the third step follows the fact that Pa(s'|s, [[ss"[s.a a) I P(s'ls, a) Cf a, s'): the fourth step uses the definition
CP (s, a,, = EnET((s.)) CP (s, a, s'); the fifth step applies the inequality v4xy S x Vz, 2 0 for x = C. (s, a, s') and = log t. Applying a union bound over all (s, a, s') and epochs i s T, we complete the proof.
Lemma D.2.4 (Anytime Version of Azuma- Bernaa-nBrrtt..... Ler (X, h be b-bounded martingale difference sequence with respect F, Let o² E E F--1). Then, with probability at least 1 - for any N E N it holds that:
N
20 log (4N2/8)
2b log (2N/8)
X
S
N
3N
1=1
Proof. This follows the same argument Lemma G.2 in [Lykouris et al., 2019].
Lemma D.2.5. Event E occurs with probability at least 1 8, where
E = (V(s,a,s') E WR, Vi,k: P(ss (s,' P.(s' |s, a)] s wi(s,,,s') (;
Proof. Conditioning events g3 and E², we have
((s'ss..) (s''' a)l P(s'ls, piNg (s'sss) + (IMG(s'(ssa)) P((s'(s,a))
(,(5, a, wsss,,,s')
(65)
Using union bound for m3 and 8², we complete the proof.
Armed with above results, we are now ready to prove Lemma D.2.1.
Proof of Lemma D.2.1. Conditioning event E, for any fixed (s, a, s') with (s, * 0 (otherwise the desired bound holds trivially), we have
wi we(8, a, 8')
24P(6'|8, log
6 Glog
(s,
(s,
as)
m)
24 (i((sss,, a) a,)
(C,(a,
+ wi(s, a, a') loge 6log 4C,(,, m a) m
mils.a)
m2 (3,
54

---

24P,(5'|s, log m)
24 a, 8²) log
+
(8,
96 ()
mi(s,a)
log
(8, a, 88) ( log m)(s,a)
+ 6loge
4C,(s,, mi(s,a)
+
() a)
m)(s,a)
(s's(s log m
1669 (8, (8,,,8)) loge
wi(s,a,8))
24 log + 4C, a,
+ (8,
+
m4(saa)
2
mg(8,0) a)
24 a) log ms + as)
28C (8,
25 log
mi(s.a) a)
(s,aa)'
where the second step holds under E; the third step the fourth step and the fifth step use 2 / I x + y for x, 2 0. Rearranging the above, we obtain
21=1 24 (=1 vi for all E R2u:
96P.(s a) logo + (s,
56C as,
50 l0gg
as S
(66)
(s
m,
m,
Thus, conditioning on event &, one can show for all (s, a, s') Wa and ls -
())lss,)) P.(5'ls, ()) I ws a, 8') (s a's)
96P. ss a) log
56C (s, a.
50log4
+ (5, a, s')
(3, a)
mi(s,a) a)
m,,s.a)
Po(slls, a) log mi(s,a)
64
s 161
m, a)
m)
P((slss, log ms(s,a)
(s log
s 16
+ 64
(67)
(s,
where the second step uses Eq. (66), the third step applies the definition of W, a, 5'). Finally, using the fact CP(s, a, 8') < C.,, we complete the proof.
Then, we present an immediate corollary of Lemma D.2.1.
Corollary D.2.6. Consider any epoch i and any transition P' E P; The following holds (recall mi defined at the beginning of the appendix),
PP(sss.)) - P.(.)s.a)ll 2 min {
3
|Sao))il 32 log
{
m,( +81
mi ()
m,
Proof. As P Ps, we start from Eq. (67):
(4,P(s,a,s)) a)
Pi(8'(s, 64
- -P(()s,0))PP((ss)))) P.((),
Σ
m)
m,(s.a)
e1Ek(e)+1
64CP
|S log m,(s,
64 64 logg
+ 16
(68)
(s a)
(s,
where the last step uses the Cauchy-Sehwar inequality and the fact that Σ +2 (s,
CP, Since [[|ss,, a) - P((sss, a)ll < 2, we combine this trivial bound and the bound of P(++s,a) P.(+ss, Eq. (68) arrive
32CP
( ()
32 log m,(s, a)
|| |P'((|s, - a((1s,,))l $ min 1,
+ +81
m, a)
55

---

32CP
| log
32 321SM())+11 log
2 min 1, a,
+ +8/
(s,0,))
(,(3,
finishing the proof.
We conclude this subsection with other useful lemmas. Lemma D.2.7. Conditioning on event Ecos, it holds for all tuple (s, a, 8') and epoch i that
( min { ('V
P(s'|s, a) log(() C + log (t)
P(5'|s,a) P((611 so
(1
ms(s,a)
Proof. Fix the epoch and tuple (s, a, 8'). According to the definitions of EcoN in Eq. (59) and m we have
lo)()) P: a) log(1)
CP + +og (1)
p(s (s(('|s,, s. a)) & min
1, 1
+ 64
()
(4(s,a) a)
Therefore, by direct calculation, have
P(s'(s, a) Pr(5'ls,a)
(( - Pr(s"(s, a)) + P(d)s, log (1)
C (1)
+ 64
())
m,
P(s'|s, allssa))ooll (4)
P(s'(s,a) - P.(s'(s.a) log (1)
CP + log (4)
64
())
(8)
(s,
P(s'|s, a) log (1)
CP log
64 (1)
8
V
+ 64
+ / P() P((')ss.))
a)
a)
m, a)
((s'|s, a) log (1)
CP + +og (1)
+ - ps)
$ 88
+ 96
as
())
where the second step and last step follow from the fact that way S (xr + for any x, 2 0. Finally, rearranging the above inequality finishes the proof.
Lemma D.2.8. (Lower Bound of Upper Occupancy Measure) For any episode I and state + 81, it always holds that (s(s) 2 1/1//2.
Proof. Fix the episode and state We prove the lemma by constructing a specific transition P E Pa(e). such that (* 2 1/1syr for any policy ıt, which suffices due to the definition of (s)).
Specifically, P defined as, for any tuple (s, s') E Wa and h: = O,..., L 1:
((s'ls, (s0)(5's,,)) (1 (1- -))) + S
By direct calculation, one can verify that P is a valid transition function. Then, we show that P E Pit)) by verifying the condition for any transition tuple (s, ",,as,) s¹) E W. and k = O.... 1:
(se)("))ss | ((6''s,a) a) Pe 1s, a) |
1 1 T
(an)(s,,,8'),
|S++1
where the last step follows from the definition of confidence intervals in Eq. (4).
Finally, we show that qf P. 2 1/ S/T as:
Σ Σ od v) ((.)))())
Σ
Σ
q P. (u,
1
T|S
TISI
WESE(A)-1 NEA
NES PEA
which concludes the proof.
56

---

D.3 Difference Lemma
Lemma D.3.1 (Theorem 5.2.1 of [Kakade, 2003)). (Performance Difference Lemma) For any policies T2 and any loss function e S x A + I,
V. (s0; {)
TT (80: E)
Σ
xT (s. a) -s=
SPEL AEA
Σ SP8L
ma (s) (mi(a))) - =2(als)) (s,
REA
In fact, the same also holds for our optimistic transition where the layer structure is violated. For completeness, include a proof below.
Lemma D.3.2. For any policies mi n2, any loss function E S A - IR, and any transition P where Ed P(s'|s, (s a) S for all state-action pairs (s, a) (the remaining probability is assigned to 81.), we have
vPau (so: f) (50: (so: 1)= ΣE
Pira Pot
(s) (s; - @
Sİ8L aEA
Proof. By direct calculation, we have for any state & + $1:
v Pm (sp: 1) V (P:=a(so:() 1)
Σ (a)a
v (P Σ (2(a Pi (so, a; E)
+ Σ T2(a|s0)
(QPix) a; P a;
aEA
Σ
(s0, a)
(VP. (s0: Q P a;)))a)))
aeA
Σ Ta(also)PPsllop (M (5'; VP (s::0)
aEA
Σ
qd TT (s0,
(VP::((00: (300 a;
(30,
aEA
PiT)(s') (s - (s')
EESS'S
Σ
Σ
x2 (3,
(vP. - (s.
st/8r. GEA
where the last step follows from recursively repeating the first three steps.
Lemma D.3.3, (Occupancy Measure Difference, [Jin et al., 2021, Lemma D.3.1]) For any transition
functions PI, P2 and any policy
-(x)-1
g Pi (8) d (s)
Σ
Σ
(u) Pa(wlu, (a
(a,ww)eWW
k(s)-1
Σ
g Pa. (u, (PI Pa(wlu, o)) g (slww,
(w..we)WW
where qº ((((())))) is the probability of visiting starting w under policy and transition P'. Lemma D.3.4. ([Dann et al., 2023, Lemma 17]) For any policies T1, n2 and transition function P.
ΣV ΣΣ
g Pims (s,a) a) q n. (s,a) a)) < L Σ Σ
P. P.m
I (als) =2(a|s)].
815 A
81, aEA
57

---

Corollary D.3.5, For any policies N1, mapping i22 S - A (that is, a deterministic policy), and transition function P, we have
1 Pm (8, PMx (s. P 2L Σ Σ
q Pita (s.
8888 aEA
8988 aff2(s)
Proof. According Lemma D.3.4, we have
ΣΣ #f8t,
1 Pm (s,a) q _
(m (s, a))
S Σ Σ
q
P. (s) [T((s) [2(a]s)
8588, aEA
Note that, for every state s, it holds that
Σ aEA
mi (als) [2(a
Σ (i(s)) + | (T2(5)]8) 1| ax)
Σ mi (als),
where the first step follows from the fact that x2(als) when (s)) and Tī (bis) for any other action b + Ts)).
Therefore, have
(s) ( S
(8)
2T Σ Σ
(s)
StAL aEA
STL8L (ff22()
which concludes the proof.
According to Lemma D.3.3, we can estimate the occupancy measure difference caused by the corrupted transition function P. at episode L.
Corollary D.3.6. For any episode t and any policy we have (s) (s)) & C.,, + St. and
s LCC.
$58t.
Proof. By direct calculation, we have for any episode t and any s + SL.
((s)
(s) - (t.
S
Σ
(u,
(P,w))) Pa(wlu, vi) Pri (slw))
0=
(u..w)eW,
k(s)-
Σ
v))
A=
BES
DEA
< cP.
where the first step follows from Lemma D.3.3, the second step bounds g (s:5(s/ww) 1, and the last two steps follows from the definition of CP.
Moreover, taking the summation over all states + sL, have
P (s) q Pai P(.t(s)) (s)
Me)-1
Σ
P.T (u, v) (P(w)u,)) P(lll,, v)l ((T((s
(N,V,w))WW
(u P(wlu,)) Pi(wu,, v)
Σ Σ Pr.
0= (,,,,))EW,
h=k+1
k(s)
< Σ Σ
(.. ( - v((l
k=0
MES PCA
< LCP
where the third step follows from the fact that Exes, g (s/w) 1 for any h 2 k(w).
58

---

Corollary D.3.7. For any policy sequence { and loss functions {4)1=1 such that & E x A [0, for any t [1...., ,T it holds that
Σ Kg Pi , S LOP.
Proof. By direct calculation, we have
T
T
(g Pm
-4
5
P 1|2 Pime
1=1
1 (8, (.:0))-9P.0) (3,
1= syar aEA
T
(( (s) (e(a(s)
1= syNa AEA AEA
T
q (() - (s))
T $ Σ LC
LC = LCP
where the first step applies the Hölder's inequality; the third step follows form the fact that (s,
qf ( a) q" ( (als) for any state-action pair (s, a) and any transition function P
the fifth step applies Corollary D.3.6; the last step follows from the definition of CP.
Following the same idea the proof of [Dann et al., 2023, Lemma 16), we also consider tighter bound of the difference between occupancy measures in the following lemma.
Lemma D.3.8. Suppose the event Ecos holds. For any state & + 81, episode and transition function P. E Patt), have
k(a)-I
P P(wlu, u) log (1) Ma(e) v) o ni (s|w)
q (i)e(s) - - 50
Σ
q (u,
k=0
(u.D,a)EWW
(69)
(1s1)
(C (CP 1o log (1)
+0
|s| Σ
Σ
q (s,
(x
StiL aEA
Proof. According to Lemma D.3.3, we have
(Pi (5)
PiTx (
A(a)-1
Σ
of Pime (u,v) (P(w(u)) P/(w/,, (s)
0=
(u,,,)EWW
Σ
qf Pate (P(wlu) Pf((lu (
0=
(w.,,)eWW
k(s)-1
Ais)
Σ
Σ
Pite (u, ((Wll,, P((wl,, v)
Σ
Σ
( vlw) [P(2|x,)) P[(=1 v)1
k=0
(,,,,))EW,
h= (s.v.=)EW
k(s)-1
Plwku v) log (1)
0
Σ
q (u, 0)
q Pite (s(w)
(2
k=
WW
59

---

h(s)-1
CP + log (1)
+0
Σ
(u,
9 Pime (s/ww)
(use)( 2)
(w,,
TERM (A)
h(s)-1
h(s)-1
Pu(wu,,, u)
Σ h= (n.y.=)eW,
Σ
(,, (lo) - (2 v)
K= (,.,,))EW,
TERM (8)
where the second step first subtracts and adds g: at (s) and then applies Lemma D.3.3 again for 1g (s/1o) - (s/we), and the third step follows from Lemma D.2.7
Clearly, can bound term (a) as:
-(a)-
Pite v) ( (
log (og+)g(()) (1) of PM* S Mi(r mesen(( (u,
(s, (
CP ( log (1) mi(e) (8, a)
Σ
ΣΣ q
(M,,
On the other hand, for term (b), we decompose it into three terms in Eq. (70), Eq. (71), and Eq. (72):
k(a)
k(a)
Σ
o (u, v) IP(wlu, e) P. u, w)
Σ
Σ
(x, v(w) P(z|z, v) - (2(,,,))))
k=0
A= 1 (2,g.a)EWa
k(m)-1
k(a)-1
P(wku v) log (1)
P(z|æ, y) log (1) mace (z, v)
0o
Σ
Σ
p (p 1)
Σ
Σ
(2,
k=
(u,,wo)EW
h=k+1 (E.
(70)
k(s)-1
P(ulu, v) log (1) (utej(u, v)
k(s)-1
(P log (t) mine (2,
CP +
+0
Σ
Σ
(u,)
Σ
Σ
(x,
A=0
(u,,,w)EW,
1= (I.y,))WW
(71)
h(a)-1
CC 1P+togg (CP log log (1)
M())1
+0
Σ
(u v))
Σ
Σ
Pite P (c.))
(72)
(u,es(u
R=0
EW,
h=k+1 (z.v,))EW,
According to the AM-GM inequality, we have the term in Eq. (70) bounded as
M(a)
M()-1
P(wlu, v) log (c) mire (u, v)
P(z|x, y) log (c)
Σ
q Pat
( /)
Σ
Pate Px (2.
mane (x, y)
K=
WW
h=k+1 (a.Ma)EW,,
k(s)
k(s) 1
Σ
Σ
Σ
(u,
P(wlu, v) log (4)
mun (u, v) g Pi (x. vlw) (v.
P(z|a, y) log (4) mutty (2r, v)
K=
WW, h= (m.y.))WW,
A(a)-1
R(3)-1
(u. (z. (z, y w P(2lx, y) log (1)
Σ
Σ
Σ
mase) (u, v)
WWW, h=k+1 (a.n))EW,
h(s)-1
k(s)
g Pite (u, P(wlu, u) (I, w/w log (4)
Σ
Σ
Σ
Mi(e) (2r v)
EWW, b= (a.g.))EW
A(a)-1
g Pite (u, v) log (1)
M(a)-1
Σ
Σ
Σ
f (I, P(1
Ma( (1
K=
(W,Ww))WW
h=
k(+)-1
log (1)
Σ
Σ
Σ
Σ
P. (x, y/w)
(I,))
R=0
(x.,,))W,,
R=0 (W,
60

---

k(() -1
gi (u, v) log (c)
k())-1
df (z, y) log (4)
L
L
Σ h=0 (m.,.))WW,
(u.,,o)EWs m4(e) v)
mi(()) (2r, v)
k=0
00 L|S) ΣΣΣ k=0 SES
q P (s. a) log (1)
m1(1)((,0))
where the first step follows from re-arranging the summation; the second step applies the fact that vay S x + y for any 2, 2 0: the third step rearranges the summation order, and the fourth step follows form the facts that EzEs, ΣyEA "M (2, (z, ylw) xr =?"m == (z|w) and E Ww,,,w))., gfa (u, u) P(w u, w)gft (x, (/r = gf ie (xx, (x,y) for any and (x, 21)
Similarly, we have the term in Eq. (71) bounded as P(wlu, v) log (1) mi(e) (u, v)
k(a)-1 Σ
CP log (t) misco (z, v)
Σ
PaT (u, v
Σ
g Pau (x, y/w)
K=
k+ (u.v.3)EW,
M(a)-1
((s)-1
Pit (u, 1)g ylw) log (1)
Σ
Σ
Σ
(u,
0=
(w W. h=b+1 (u.y,=)EW,
-
Pat (u, P(ulu, o)g P. (" ww) CP + log (1) mece (2, y)
Σ
Σ
Σ
E
k=
(u.,,w)EW, h k (K.B.))WW
Ma)-1
Pi (u, v) log (1)
R(a)-1
Σ
Σ
Σ
Σ
q (
(u,
(w,
/=
(2.g1))EW.
k())-
CP + log (1) mi(e (2,
Σ
Σ
Σ
v) Pi ylwo)
0=0
(w.,
k(x)-1
q Pite (u, U) 1og
(c) (1)
k(a)-1
CP (CP + log
< |
Σ
Σ Σ
Σ
g P (x,
(u,
K=
(u,
h=0 (z,g.))EW, kmo
2 (s (8, log (1)
CP + +log (1)
+ L|SI
ΣΣ
Pite (s,a)
()))
STAL REA
#f82 aEA
where the first step follows from the fact that ma( (8 2 C + log (1) according to its definition; the third step follows from the facts that Exes, Ever q (I. 1 and
E (.., ( (u,v) P v) (x, ylw) = (x, (I,y).
For the term in Eq. (72), we have
CP + log (1)
k(a)-1
Σ
Σ
q Pat Pa v)
Σ
Σ
q Pite (x. glw)
(w.,
Am (A.D.))EW
k(s)-1
Σ
ΣΣ
Σ
CP + +og (1) d (ix)(u,))
k(x)
Σ
Σ1
mnse)(u,,))
k=0
WES: WESH+1
h=k+1 sE5t1
CP CP log (1) mi(a) (u, v)
$ 1 Σ ΣE
P.ti (s.a)
NELA YEA
according to the fact that Eres, Eye Pixl (I, y/w) <
Putting all the bounds for the terms in Eq. (70), Eq. (71), and Eq. (72) together yields the bound of
TERM (B) that
k(s)-1
k(+)-
Σ
Σ
(u, (P(wlu, - P/(l),, w)l
Σ
Σ
q P ( (P(la,, y) - P/(2/o,
K=
WW
h= 1 (2,0.))
61

---

(0(
ΣΣ E
C + +og log (t) Ma(e) (u, v)
q P.ti
(u
Combining this bound with that of TERM (A) finishes the proof.
D.4 Loss Shifting Technique with Optimistie Transition
Lemma D.4.1 Fix an optimistic transition function P (defined in Section 5). For any policy and A R, we define function S A + IR similar that of Jin al.
any loss function [2021] as:
g P. as e (s== (s; - e(s,a)).
where the state-action and state value function Q and vP are defined with respect to the optimistic transition P and nt as following:
Q 2 (s, a
{(s,0)+
E P(
S'ESNCe)-1
VP So.
81:
8 + 81.
Then, it holds for any policy nt' that,
P. ,/
gf - -VP:: E),
8F GEA
where VP (10; E) is only related to P, and E, and is independent with n².
Proof. By the extended performance difference lemma the optimistic transition in Lemma D.3.1, we have the following equality holds for any policy n²:
v pa' (su; E) V P. (su: (.si
ΣΣ
9 P. (s, (QP="(s,;;))) VP. vs:((s)
888L aEA
On the other hand, we also have
PPr (so: -
Pot EF (s,a)((ss))
a
Therefore, subtracting P. (so: 2) yields that
-V () ΣE
Pirl (s, (s. (s;)(s;)) {(s,a))
81 a
The proof is finished after using the definition of P.
Therefore, we have the following result for the FTRL framework which similar to [Jin et al., 2021, Corollary A.1.2.].
Corollary D.4.2. The FTRL update in Algorithm can be equivalently written as:
t-1
@ argmin (E)(P.)
q.
Σ (e, br) + +br(9) 2E((P.)
argmin
q, Σ (gr by) b.)) +1)()))
T=4
where gr (s PP..r (s, [x)
VP..5- Er) for any state-action pair (s, a).
62

---

D.5 Estimation Error
Lemma D.5.1. ([Jin er al., 2020, Lemma 10]) With probability least 1 we have for all
k= O.....L L
T
g a)
-O(1salAA| log (T) + log ( 55) ))
Σ
Σ
max (s. a),1]
t=
(A
and
T
( -0
( )))
Σ
Σ
(VIS.AL |5 (T) + log
Vmax (m)
(s,a)E8xx4
Proof. Simply replacing the stationary transition P with the sequence of transitions {Pi) in the proof of [Jin al., 2020, Lemma 10] suffices.
n
Proposition D.5.2. Let EEST be the event such that have for all i: O,.... L simultaneously
qPiif( (s,
Σ t= (5,))
Σ
O [|Sx||A||og (T) + log (4))
max (8,())
and
q P1.t((sa))
= (VIISAlIA + [S log (T) + log (1)
(=1 (s.a)ESkXA A max (s.
We have Pr(EEST] 2 1 -.
Proof. The proof directly follows from the definition of which ensures that v 2 1/5.
Based the event EEST, introduce the following lemma which is critical in analyzing the estimation error.
Lemma D.5.3. Suppose the event EEST defined Proposition D.5.2 holds. Then, we have for all k= == o......
T
q (s. O (o (T) + log (1))
Σ
Σ
(s
[=1
(
and,
cP (c O(C( + +log (4)) |Sa||A| log (t))
Σ
Σ
(s,a)
1=1
(x.4))SExAA
Proof. According Corollary D.3.6, have
Pi (s) Mare) (8
Σ
(s,0)ES,
Pu a)
PuoT (s)
Σ
Σ
(8
mi(e) (8,
(
1=1 (a,0)ESeXA
(i
CP
Σ
max (1,
CP + log(1)
(x.a)ESx xA
(sajESxxA
< 0 ([Sa|||1 log (T) + log (())
63

---

where the second step follows from the definitions of CP and (s, a), and the last step applies Lemma D.
Similarly, we have
CP +o (1)
Σ
(s,)))))
(5,a) XA
( (8, + p. (s,))) (CP log (1) marer (s, a)
Σ
(196001(5)))
(8,0)ESxXA
CP C (1)
Σ
C (e
(s
(s,0)ESEXA
T
Pr
2 |
Σ
C. + (CP +og (1))
Σ
(s,0)ESxxA XA (s(e]
1=1
= (ISEllAA) CP + (CP log (1)) (1Sxl
Allog (T) + log (1))
o ((CP log (1)) A| (1).
where the first step adds and subtracts q g the second step follows from Corollary D.3.6; the fourth step uses Proposition D.5.2 due to the fact that m, a) 2 max (m,(s, a),
Lemma D.5.4. (Extension of [Dann et al., 2023, Lemma for adversarial transition) Suppose the high-probabilte events EEST (defined in Proposition D.5.2) and Ecox (defined in Lemma D.2. 1) hold together. Let Pt be transition function in Pucz) which depends 8, and let gr gx(8) [0, G) for G 0. Then,
( LISTP/A| (1) Σ EF (s){()))
Σ
q (() (s) (((s)= (s)
1=1 2t.5L
1=1 S8/L
O (G log (i) L2 | || log (1)
Proof. By Lemma D.3.8, under the event EcON, we have
Pr (s) g (() (s(s)
k(x)-1
50
(t(s)
Pate (u, (u.u0y
P(wlu, v) log (c)
Pixe (5)10)
(73)
1=1 efELL
K=
(u.
T
( (mmoo(600)))
( log (1)
+0
G|S)
ΣΣΣ
Σ
Pit (s,
(=1 (=1 sylar, aEd
By Lemma D.5.3, the last two terms can be bounded under the event Eyst as
CP (C* (1)
o
G
Σ
Σ
Σ
q PiF
(s,
0
G
(CP + log (1)) |||||||1 log (1)
k=0
= 0 (G (CP
+ log (4)) S|S) | log (t)
64

---

For the first term in Eq. (73), we first rewrite it as
-
P(wlu, v) log (1) mn(e)) (u, v)
Σ
Σ
Σ
q (un)))
a Pire (s/w)g((s)
1=1 1881
h=0
(w.sw)eW,
ΣEΣ E
L-1
q Pite (u, (u,o),
Vo
P(w) u, v) log (1) Ma(e) (u, g PmT (s)w)))
hm0 spte (o.,,))EW
For any 0 > and layer h. conditioning on the event EESTS we have
E
T
Σ
E
q Pi (u, 1
P(wlu, vi) log (1) q PM (s(w))((s)) ms(c)) (u, v)
1=1 stia (W,,
T
Pri (u, v) (s|w) log (1) - (u, u) P(wlu, (s)0))))))))) mi(e) (u, v)
Σ
1=1 spel (u.,,))WW,
T
o gP (u, (u, v) aite (slue) log (t) (u,)),,
Σ
Σ
+ a (f w) P(oolu, w)g ( (s)
$
1=1 Sp8L (u,,,w)EW,
Σ
T
Σ
(u, v), log(1) (1)
Σ
E (o
Σ
(asce)(1,))
UESH DEA
WESn+1 of0L
1
Σ
Σ
(u)))))) Pit ge(s)
0
(,,,,w)EW,
(u,
S 0- L|Sh+1| 1 (1)
ΣΣΣ
Σ
Σ Σ
q Pat (s)g((()))
u1, v)
MES vEA
50
0- L|Sh+1/log (1) (15k |||| log (T) + log (1)) + Σ
q PoTe
(s)g
(=l
-0
OL (S.1S log (1)+
ΣΣ (s)
0
1=1 #
where the second step uses the fact that Vay S x + y for all x, 2 0, the fourth step follows from Lemma D.5.3.
Then, for any layer h O..... 1. picking the optimal 0 gives
P(wlu, v) log (4) q Pare (s(w)) mar (u,
Σ
Σ
Pate (u, 1/
8F (W.
(v L|S [| (1) Σ Σ
-0
gh (s))(()))))
888L
5o (1Sa) (1S.)+
+ +1++t1)))
/ 1/Allog2 (1)
Σ ΣΣ
Pate (()
888L
Finally, taking the summation over all the layers yields
TIT ΣEΣ Σ 1E WWW,
P(wlu, u) log (t) Pi (s/w))a(s) mire v)
q P v)
65

---

{1
5o
T 71SPP1A1 (1)
E
Σ
8788L
which finishes the proof.
66


Reviews:
[{"review_id": "4qzP5F8wXT", "reviewer": "Reviewer_ME4k", "summary": "This paper studies learning algorithms for adversarial MDP with adversarial transition functions. The authors developed an algorithm that enjoys O(\\sqrt{T} + C^P) regret where C^P measures how adversarial the transition functions are. The developed algorithm could work without knowing C^P. Finally, the authors show that further refinements of the algorithm can adapt to easier environments. ", "questions": "NA", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper tackles an important question of how to learn adversarial MDPs with adversarial transition functions. Prior work shows that learning with adversarial transition is information-theoretically impossible without paying exponential dependence on the episode length. This paper provides the first algorithm, based on a modification of UOB-REPS, which allows the regret bound to degrade mildly upon the amount of corruption. Furthermore, it also resolves the question of an unknown amount of adversarial transition and considers the question of adaptivity. ", "weaknesses": "NA", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your positive comments. "}, {"review_id": "d6aHvrjtj3", "reviewer": "Reviewer_tv4V", "summary": "This paper studies the problem of reinforcement learning under adversarial reward and transitions. When evaluating the regret against the best fixed policy in hindsight, the algorithm proposed in this paper achieves the optimal regret O(\\sqrt{T} + C^P), which is followed by other favorable extensions including being agnostic to the corruption amount $C^P$ and $C^L$, as well as gap-dependent regret bounds. ", "questions": "See above.", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The theoretical results presented in this paper is solid. Several new techniques, including a new model selection framework that allows adversarial environments, is of independent interestis.", "weaknesses": "The main weakness is the lack of justification for the specific type of regret studied in this paper. To the best of my knowledge, this is the only paper that studies the regret against the best policy in hindsight in a mild-corruption setting, i.e. C^P \\leq o(T), so some words justifying this new notion would be helpful. I'm not sure when such a regret notion is desirable to study in this scenario, since if C^P \\leq o(T), the best policy in hindsight will converge to the optimal policy in the underlying uncorrupted MDP, so the two notions would converge anyways.\n\nMinor: \n\nThere is a missing reference for corruption-robust RL\n\n1. Zhang, X., Chen, Y., Zhu, X., & Sun, W. (2021, July). Robust policy gradient against strong data corruption. In International Conference on Machine Learning (pp. 12391-12401). PMLR.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your helpful feedback. Please see our responses below: \n***\n**Q1:** Lack of justification for the specific type of regret studied in this paper. \n\n**A1:** First, when the MDPs are time-varying, the ``underlying uncorrupted MDP'' is not always well-defined. On the other hand, the best-in-hindsight policy is always well-defined, so adopting it as the benchmark is more direct and requires no additional assumptions. Second, our regret bound that scales with $\\sqrt{C^L}$ reflects that our algorithm is still doing a meaningful job (i.e., performing as well as the best fixed policy) even when $C^L=\\Omega(T)$ and $C^P=o(T)$. In contrast, the regret notion in [Lykouris et al, 2019] and [Wei et al., 2022] will become vacuous in this scenario. Thus, our notion of regret can more clearly decouple and distinguish the hardness coming from adversarial loss and from adversarial transition. Lastly, using best-in-hindsight policy as the benchmark is a convention in the adversarial online learning literature. As mentioned in the paper (L73-L78), our regret notion always implies the other one, but not the other way around. Therefore, we never fail to capture scenarios that are captured in the other notion of regret.\n\n***\n**Q2:** A missing reference [Zhang et al., 2021] for corruption-robust RL. \n\n**A2:** We thank the reviewer for highlighting this work. We will make sure to include it in the final version of this manuscript and have a more complete overview of the literature.\n\n[Zhang et al., 2021] Zhang, X., Chen, Y., Zhu, X., Sun, W. (2021, July). Robust policy gradient against strong data corruption. In International Conference on Machine Learning (pp. 12391-12401). PMLR.\n\n\n"}, {"review_id": "UpvAlRRzfF", "reviewer": "Reviewer_7UE7", "summary": "The authors consider no-regret learning in adversarial MDPs, when the dynamics may change adversarially across episodes. They design an algorithm which provides a regret guarantee of $\\tilde{O}(\\sqrt{T} + C)$ where $C$ is the total deviation from some fixed transition function, and the benchmark is the best fixed Markov policy in hindsight. The authors show that this result can be obtained even when $C$ is unknown to the algorithm, by constructing a black-box reduction from an algorithm which knows $C$. The authors also consider the stochastically constrained adversarial setting and provide a gap-dependent regret guarantee, but in this setting knowing $C$ is required.", "questions": "See my remarks above under \"Weaknesses\" - I'd appreciate it if the authors could address the limited generality of the benchmark policy, as well as the problem of handling drift in the transitions.", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* The results established in the paper improve upon previous results in corruption-robust reinforcement learning, and in particular constitute the first $\\tilde{O}(\\sqrt{T} + C)$-type bounds even when the losses are adversarial.\n* The techniques presented in the paper seem novel and interesting, and may be of independent interest in various RL scenarios.\n* The authors provide an overview of the analysis presenting the main challenges and ideas, making it easier to understand their main contributions and high-level techniques.\n* The black-box reduction from an algorithm which knows $C$ to one which doesn't need to know $C$ seems particularly interesting to me, and may be of interest in other non-stationary scenarios when trying to design algorithm that adapt to some corruption budget.", "weaknesses": "* Since the dynamics of the MDP changes adversarially across episodes, it makes less sense to set the benchmark as a Markov policy, as it is no longer the case that the optimal policy on a sequence of MDPs is WLOG Markov. The authors do not address this point in the current version of the paper, and I would like to hear from them why this assumption is needed and whether or not competing against a more general benchmark policy is hard.\n* At first, it may seem that $C$ measures the total variation of the transition dynamics across time, as is the case in other non-stationary RL formulations. However, the authors define $C$ to be the sum of variations from a single fixed transition function. This is a weaker definition, and in particular the results presented in this paper do not include a setup where the dynamics have a drift of $1/ \\sqrt{T}$ per episode, and for every fixed transition $P'$ the total deviation from it would be $\\Omega(T)$. In such a setting, the authors' bounds would be meaningless even though obtaining sublinear regret (even dynamic regret) is indeed possible.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable feedback. Please see our responses below: \n\n***\n**Q1:** \n Since the dynamics of the MDP changes adversarially across episodes, it makes less sense to set the benchmark as a Markov policy, as it is no longer the case that the optimal policy on a sequence of MDPs is WLOG Markov. The authors do not address this point in the current version of the paper, and I would like to hear from them why this assumption is needed and whether or not competing against a more general benchmark policy is hard.\n\n**A1:** This is indeed a very good point. While we do not have a definite answer regarding how hard it is to compete with the best non-Markovian policy generally, we remark that in the case when corruption is ``binary'' (that is, an episode is either corrupted or not so $C^P$ counts the number of corrupted episodes), the best non-Markovian policy would not perform better than the best Markovian one on those uncorrupted episodes, and since we already have $\\sqrt{T}+C^P$ regret against the best Markovian policy, the same bound would thus hold for competing against the best non-Markovian one as well. We also emphasize again that our regret notion, though restricted to competing with Markov policies only, is more general than the standard one used in the literature of learning corrupted MDPs, as we argue in L73-L78.\n\n***\n**Q2:**  At first, it may seem that \n measures the total variation of the transition dynamics across time, as is the case in other non-stationary RL formulations. However, the authors define $C$\n to be the sum of variations from a single fixed transition function. \n \n**Q3:**  In particular, the results presented in this paper do not include a setup where the dynamics have a drift of $1/\\sqrt{T}$ per episode, and for every fixed transition $P'$ the total deviation from it would be $\\Omega(T)$. In such a setting, the authors' bounds would be meaningless even though obtaining sublinear regret (even dynamic regret) is indeed possible.\n\n**A2 and A3:** (For Q2 and Q3) We agree that the amount of variation $V^P\\triangleq \\sum_{t=2}^T \\|P_t-P_{t-1}\\|$ can be much smaller than our $C^P$. It is an interesting question whether the regret (compared to a fixed policy) can be just linear in $V^P$ instead of $C^P$. Previous work in non-staitonary RL shows that a dynamic regret of $(V^P)^{1/3}T^{2/3}$ is tight, which is incomparable to our static regret bound of $C^P$. However, there do exist examples (as the reviewer point out) where $(V^P)^{1/3}T^{2/3}$ is much smaller than $C^P$, so getting the best of both is also an interesting direction. "}, {"review_id": "HXGSvUHQFV", "reviewer": "Reviewer_P2en", "summary": "This paper studies online reinforcement learning in tabular MDPs when the losses and transitions can be adversarially changing from round to round. They show that one can achieve regret guarantees which are $O(\\sqrt{T} + C^P)$ where $C^P$ measures the degree to which transitions are changing.\n\nSpecifically they \n- devise an algorithm which achieves the aforementioned guarantee when the value of $C^P$ is known.\n- apply further reductions to get an algorithm which does not need to know the value of $C^P$.\n- get gap-dependent regret bounds when the value of $C^P$ is known.", "questions": "1. This paper considers transitions and losses which are specified ahead of time by an adversary. Do you think it is possible to consider adversarial losses/transitions which the adversary can suggest after seeing a history of the learner's decisions? (a harder setting)\n2. What is the role of the splitting into epochs feature of the algorithm? What goes wrong if the algorithm updates the empirical transition in every round, as opposed to in every epoch?\n3. Is there some intuition for why the algorithm uses the upper occupancy bound following line 161, as opposed to just using the occupancy measure associated with $\\bar{P}$?\n4. What is the message of Lemma 3.1? Why is the inequality $\\sum_t C_t^P/u_t(s) \\le \\sum_t b_t(s)$ useful?\n5. This might be a standard technique, but why are the costs in Algorithm 3 offset by a reward $r_\\tau$? What does this capture?", "limitations": "None", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "- The results seem very impressive. To my knowledge this is the first paper which studies adversarial MDPs with changing transitions. The authors quantify the notion of changing transitions and prove a regret bound.\n- The algorithms and techniques seem very novel, and might be useful for future work.\n- References and connections to previous work are stated clearly.", "weaknesses": "- The writing is a bit unclear, specifically regarding the technical details. This paper is a very technical paper with long proofs, but I do think it would be helpful to state the algorithms (or some simplified versions of the algorithms) in the main text and relegate some of the finer details to the appendix.\n- Upon first reading, the proof ideas in Section 3 onwards did not make much sense, because they were trying to cover a lot of fine details, even though the overall proof sketch was not really discussed much. I'd encourage the authors to put more effort into improving readability.\n\nTypos:\n- Line 116: should this be $S$ instead of $X$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your helpful feedback. Please see our responses below: \n***\n**Q1:** Issues of writing, organization, and presentation.\n\n**A1:** Thanks for your suggestions. We will consider re-organizing the content in the future version. \n\n***\n**Q2:** Line 116: should this be $S$ instead of $X$?\n\n**A2:** We thank the reviewer for spotting the typo. It will be fixed in the final version.\n\n***\n**Q3:** Do you think it is possible to consider adversarial losses/transitions which the adversary can suggest after seeing a history of the learner's decisions? (a harder setting)\n\n**A3:** We do believe that our algorithm can handle the standard adaptive adversary (i.e., decides the transition/loss in round $t$ based on the history up to $t-1$). We consider the oblivious adversary in the paper just for simplicity. For a stronger adversary that can decide the transition/loss in round $t$ based on the action chosen in round $t$, and the total corruption is unknown, previous work by [He et al., 2022] has shown that it is impossible to achieve $O(C^P)$ regret. \n\n[He et al., 2022] Jiafan He, Dongruo Zhou, Tong Zhang, Quanquan Gu. Nearly Optimal Algorithms for Linear Contextual\nBandits with Adversarial Corruptions. NeurIPS 2022. \n\n***\n**Q4:** What is the role of the splitting into epochs feature of the algorithm? What goes wrong if the algorithm updates the empirical transition in every round, as opposed to in every epoch?\n\n**A4:** Since FTRL does not deal with varying decision sets easily (as mentioned in lines 328-329), splitting time steps into epochs guarantee that the occupancy measures in a epoch are from the same decision set.\n***\n**Q5:** Is there some intuition for why the algorithm uses the upper occupancy bound following line 161, as opposed to just using the occupancy measure associated with $\\bar{P}$?\n\n**A5:** It is important to ensure that ``optimism'' holds (i.e., $q^{P,\\pi_t}(s,a) \\leq \\mu_t(s,a)$) in the analysis.\n***\n**Q6:** What is the message of Lemma 3.1? Why is the inequality $\\sum_t C^P_t/u_t(s) \\leq \\sum_t b_t$ useful?\n\n**A6:** Because of the transition corruption, we have a regret overhead of $\\mathbb{E}[\\sum_t  \\sum_s q^{P,\\mathring{\\pi}}(s)\\frac{C^P_t}{u_t(s)}]$ (Line 183) that can be prohibitively large. By incorporating the bonus term $b_t$ into the policy update, we get an additional regret term $\\mathbb{E}[\\sum_t \\langle q^{P,\\pi_t} - q^{P,\\mathring{\\pi}},b_t\\rangle]$. The first part of Lemma 3.1 is to show that the overhead term $\\mathbb{E}[\\sum_t  \\sum_s q^{P,\\mathring{\\pi}}(s)\\frac{C^P_t}{u_t(s)}]$ can be cancelled by the negative part of the additional regret $\\mathbb{E}[\\sum_t \\langle  q^{P,\\mathring{\\pi}},b_t\\rangle]$. The second part of Lemma 3.1 is to show that the positive part of the additional regret $\\sum_{t} \\langle q^{P, \\pi_t}, b_t\\rangle\\approx \\sum_t \\langle \\widehat{q}_t, b_t\\rangle$ can be bounded by the order of $C^P\\log T$.\n***\n\n**Q7:** Why are the costs in Algorithm 3 offset by a reward $r_\\tau$? What does this capture?\n\n**A7:** Introducing a ``bonus term'' $r_\\tau$ is a standard technique in the model selection literature where the goal is to use a meta-bandit algorithm to learn over a set of base-bandit algorithms, and try to perform as well as the best base-bandit algorithm running alone. This bonus technique appears in [Foster et al., 2020] and [Luo et al., 2022]. The reason to introduce the bonus is that when running the model selection algorithm, every base algorithm is only chosen and updated with a certain probability (because at each round, the meta algorithm can only select one of the base algorithms to execute), which results in base algorithm's performance degradation compared to the case when it's running alone. To compensates this phenomenon, for base algorithms that are chosen with a smaller probability, the meta algorithm will add a larger bonus to them.  \n\n[Foster et al., 2020] Dylan J. Foster, Claudio Gentile, Mehryar Mohri, Julian Zimmert. Adapting to Misspecification in Contextual Bandits. 2020. \n\n[Luo et al., 2020] Haipeng Luo, Mengxiao Zhang, Peng Zhao, Zhi-Hua Zhou. Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits. 2022. \n"}, {"review_id": "TmRd067mpS", "reviewer": "Reviewer_fP6g", "summary": "This paper introduces the challenge of online learning in adversarial MDPs where the loss functions and transition functions are chosen by a malicious adversary. Although previous algorithms achieving $O(\\sqrt{T})$ regret with fixed transition functions could not handle adversarial transitions, in this paper, the authors propose a new algorithms that can handle both adversarial losses and transitions, with regret increasing smoothly based on the degree of maliciousness $C^P$. The first algorithm achieves $O(\\sqrt{T} + C^P)$ regret, where $C^P$ measures how adversarial the transitions are and can be at most $O(T)$. Second, a black-box reduction approach is introduced to remove the requirement of knowing $C^P$. The algorithm is further refined to adapt to easier environments and achieve $O(U + \\sqrt{U C^L} + C^P)$ regret, where $U$ is a gap-dependent coefficient and $C_L$ represents the amount of corruption on losses.", "questions": "- ", "limitations": "Given that this paper is primarily focused on theoretical aspects, its direct impact on society is expected to be neutral.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- A variant of the UOB-REPS algorithm is suggested to achieve regret in completely adversarial environments when the adversarial transition parameter, $C^P$, is known. This is accomplished by using an enlarged confidence set with the log-barrier regularizer and introducing a novel amortized bonus term.\n- The requirement of knowing the adversarial transition parameter, $C^P$, is eliminated by proposing a black-box reduction approach. This approach provides the same guarantee (up to logarithmic factors) even if $C^P$ is unknown.\n- The algorithms are further refined to simultaneously adapt to the maliciousness of the loss functions and achieve low regret. This enables the algorithms to handle various degrees of adversarial behavior in the loss functions while maintaining their regret performance.", "weaknesses": "- The organization of the paper may be making it difficult for me to comprehend. I think it is recommended to have the main algorithm presented in the main paper for better clarity. Since the paper covers multiple algorithms, it would be helpful to focus on explaining how they differ from existing methods, the challenges they address, and the novelty they bring to the field. Providing a dedicated conclusion section would enhance the understanding of the paper by summarizing the key findings and contributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your helpful feedback. Please see our response below:\n***\n**Q:**  Issues of paper's organization.\n\n**A:** Thanks for the suggestion. In the submission phase, we were unable to squeeze the algorithms and the conclusion section in the main texts because of the space limit. We will use the extra page granted in the final version to address these issues."}]

Author rebuttal:

Meta-review: This paper addresses the challenging problem of online learning in adversarial Markov Decision Processes (MDPs), where both loss and transition functions can be manipulated by a malicious adversary. It introduces novel algorithms that demonstrate remarkable adaptability to varying degrees of adversarial behavior, offering smooth regret bounds as a function of the maliciousness level. While the paper's organization and presentation have room for improvement, the significant contributions in tackling adversarial MDPs and the authors' commitment to addressing these issues in the final version warrant accepting the paper. Overall, this work advances the field of online learning in adversarial environments, making it a valuable addition to the conference.
Decision: Accept (poster)