Near-Optimal Adversarial Reinforcement Learning with Switching Costs
Authors: Ming Shi
Yingbin Liang
Ness Shroff
Venue: ICLR 2023 notable top 25% (2023)
Keywords: adversarial reinforcement learning
switching costs
regret analysis
lower bound

Abstract: Switching costs, which capture the costs for changing policies, are regarded as a critical metric in reinforcement learning (RL), in addition to the standard metric of losses (or rewards). However, existing studies on switching costs (with a coefficient that is strictly positive and is independent of the time horizon) have mainly focused on static RL, where the loss distribution is assumed to be fixed during the learning process, and thus practical scenarios where the loss distribution could be non-stationary or even adversarial are not considered. While adversarial RL better models this type of practical scenarios, an open problem remains: how to develop a provably efficient algorithm for adversarial RL with switching costs? This paper makes the first effort towards solving this problem. First, we provide a regret lower-bound that shows that the regret of any algorithm must be larger than $\tilde{\Omega}( ( H S A )^{1/3} T^{2/3} )$, where $T$, $S$, $A$ and $H$ are the number of episodes, states, actions and layers in each episode, respectively. Our lower bound indicates that, due to the fundamental challenge of switching costs in adversarial RL, the best achieved regret (whose dependency on $T$ is $\tilde{O}(\sqrt{T})$) in static RL with switching costs (as well as adversarial RL without switching costs) is no longer achievable. Moreover, we propose two novel switching-reduced algorithms with regrets that match our lower bound when the transition function is known, and match our lower bound within a small factor of $\tilde{O}( H^{1/3} )$ when the transition function is unknown. Our regret analysis demonstrates the near-optimal performance of them.

Published as a conference paper at ICLR 2023
NEAR-OPTIMAL ADVERSARIAL REINFORCEMENT LEARNING WITH S WITCHING COSTS
Ming Shi, Yingbin Liang, Ness Shroff
Department of Electrical and Computer Engineering The Ohio State University Columbus, OH 43210, USA (shi.179g) 1i liang. 889, chroff.11]00m
ABSTRACT
Switching costs, which capture the costs for changing policies, are regarded as critical metric in reinforcement learning (RL., in addition to the standard metric of losses (or rewards). However, existing studies on switching costs (with coef- ficient that is strictly positive and is independent of the time horizon) have mainly focused on static RL, where the loss distribution is assumed be fixed during the learning process, and thus practical scenarios where the loss distribution could be non- -ta-stationary or even adversarial are not considered. While adversarial RL better models this type of practical scenarios, an open problem remains: how develop a provably efficient algorithm for adversarial RL with switching costs? This paper makes the first effort towards solving this problem. First, provide a regret lower- that shows that the regret any algorithm must be larger than ()HHA))133 where T, S, and H are the number of episodes, states, actions and layers each episode, respectively. Our lower bound indicates that, due to the fundamental challenge of switching costs in adversarial RL, the best achieved regret (whose dependency on T ((VT)) in static RL with switching costs (as well adversarial RL without switching costs) is no longer achievable. Moreover, we propose two novel switching-reduced algorithms with regrets that match our lower bound when the transition function is known, and match our lower bound within a small factor of ((13//3) when the transition function is un- known. Our regret analysis demonstrates the near-optimal performance of them.
INTRODUCTION
Reinforcement learning (RL) recently arises as a compelling paradigm for modeling machine learn- ing applications with sequential decision making. In such problem, online learner interacts with the environment sequentially over Markov decision processes (MDPs), and aims to find a desirable policy for achieving an accumulated loss (or reward). Various algorithms have been developed for RL problems and have been shown theoretically to achieve polynomial sample efficiency in Zimin & Neu (2013) 3); Azar al. (2017); Jin et al. (018))/Agaaaaa et al. (2019 Bai al. (2119): Jin al. 2200 b): Cai et al. (2020); Gao et al. (2021) Lykouris et al. (202 1): Qiao et al. (2022).
etc.
In addition to the metric of losses, switching costs, which capture the costs for changing policies during the execution of RL algorithms, are also attracting increasing attention. This is motivated by many practical scenarios where the online learners cannot change their policies for free. For example, in recommendation systems, each change of the recommendation involves the processing of a huge amount of data and additional computational costs (Theocharous al, 2015). Similarly, in healthcare, each change of the medical treatment requires substantial human efforts and time- consuming tests and trials (Yu et al.) 2021). Such switching costs are also required to be considered in many other areas, e.g., robotics applications (Kober al. 2013), education software (Bennane) 2013). computer networking (Xu et al., 2018). and database optimization (Krishnan et al. 2018).
Switching costs have been studied in various problems (please Sec. 2 for some examples). Among these studies, a relevant line of research is along bandit learning (Geulen et al., 2010)) Dekel al. 2014 Arora al. 2019 Shi et al. 2022). Recently, switching costs have received consider-

---

Published as a conference paper at ICLR 2023
able attention in more general RL settings (Bai et al. 2019 Gao et al. 2021 Wang al. 2021| Qiao ct al. 2022). However, these studies have mainly focused on static RL, where the loss distribution is assumed to be fixed during the learning process. Thus, practical scenarios where the loss distribution could be non-stationary or even adversarial are not characterized or considered.
While adversarial RL better models the non-stationary or adversarial changes of the loss distribu- tion, to the best of our knowledge, an open problem remains: how to develop a provably efficient algorithm for adversarial RL with switching costs? Intuitively, in adversarial RL, since much more often policy switches would be needed to adapt to the time-varying environment, it would be much more difficult to achieve a low regret (including both the standard loss regret and the switching costs, please see (6)) Indeed, without a special design to reduce switching. existing algorithms for adversarial RL with T episodes, such as those in Zimin & Neu (2013); Jin et al. (2020a); [ee et al. (2220) and Lykouris et al. (2021), could yield poor performance with linear-to-7 ' number of policy switches. Thus, the goal of this paper is to make the first effort along this open direction.
Our first aim is to develop provably efficient algorithms that enjoy low regrets in adversarial RL with switching costs. This requires a careful reduction of switching under non-stationary or adversarial loss distributions. It turns out that previous approaches to reduce switching in static RL (e.g.. those in Bniai et al. 2019) and Qiao et al. (022)) are not applicable here. Specifically, the high-level idea in static RL is to switch faster at the beginning, while switch slower and slower for later episodes. Such a method performs well in static RI., mainly because after learning enough information about losses estimate the assumed fixed loss-distribution accurately enough with high probability in later episodes. Thus, even though the learner switches slower and slower, low regret is still achievable with high probability. In contrast, when the loss distribution could change arbitrarily, this method does not work. This is mainly because what the learner learned in the past may not be that useful for the future. For example, when the loss distribution is adversarial,
at the beginning (by switching faster), the learner
action pair with small losses in the past may incur large losses in the future. Thus, new ideas are required for addressing switching costs in adversarial RI..
Our second aim is to understand fundamentally whether the new challenge of switching costs in adversarial RL significantly increases the regret. This requires a converse result, i.e., lower bound on the regret, that holds for any RL algorithm. Further, we aim to understand fundamentally whether the adversarial nature of RL indeed requires much more policy switches to achieve low loss regret.
Our contributions: In this paper, we achieve the aforementioned goals and make the following three main contributions. (We use 2 ê and Ô to hide constants and logarithmic terms.)
First, we provide a lower bound (in Theorem D that shows that, for adversarial RL with switching costs, the regret of any algorithm must be larger than ((HHS () where T, S, and H are the number of episodes, states, actions and layers in each episode, respectively. Our lower bound indicates that, due to the fundamental challenge of switching costs in adversarial RL, the best achieved regret (whose dependency on T is Õ(VT)) in static RL with switching costs is no longer achievable. Further, we characterize precisely the new trade-off (in Theorem 2 between the standard loss regret and the switching costs due to the adversarial nature of RL.
Second, develop the first-known near-optimal algorithms for adversarial RL with switching costs. As we discussed above, the idea for reducing switching in static RL does not work well here. To handle the losses that can change arbitrarily, our design is inspired by the approach in Shi et al. (2022) for bandit learning, but with two novel ideas. (a) We delay each switch by a fixed (but tunable) number of episodes, which ensures that switch occurs only every O3T episodes. (b) The idea in (a) results in consistently long intervals of not switching. Since the bias in estimating losses from such long interval tends to increase the regret, it is important to construct an unbiased estimate of losses for each interval. To achieve this, the idea in bandit learning to consider all time-slots in each interval as one time-slot, which necessarily requires a single chosen action in each interval. Such an approach is not applicable to our more general MDP setting, since there is no guarantee to visit single state-action pair due to state transitions. To resolve this issue, our novel idea is to decompose each interval, and then combine the losses of each state-action pair only from the episodes in which such a state-action pair is visited. Interestingly, although this combination is random and the loss is adversarial, the expectation of the estimated losses is (almost) unbiased.
2

---

Published as a conference paper at ICLR 2023
Third, we establish the regret bounds for our algorithms. For the with known transition function, we show that our algorithm achieves ((HSA))/3723) regret, which matches our lower bound. For the case with an unknown transition function, we show that, with probability 1 5, our algorithm achieves an Ô (SA) bound on the dependency of T, S and A, except with small factor of (HH13)). Therefore, the regrets of our new algorithms are near-optimal. Moreover, because of our novel ideas for estimating losses and delaying switching discussed above in state-transition case, our proofs for the regrets involve several new analytical ideas. For example, in Lemma] Jand Lemma 2 way of estimating losses is (almost) unbiased so that its effect the regret is controllable. Moreover, to capture the effects of the delayed switching, our new analytical idea is to first bound the regret across intervals between adjacent switching events, and then relate the regret inside episodes of each interval to this bound (please see Step-2 of the proof' in Appendix and Appendix G
)1/2) regret, which matches our lower
we show that our new
2 RELATED WORK
Switching costs have already received considerable attention in various online problems. For example, online convex optimization with switching costs has been studied Lin et al. 20122;; Chen et al. (0166;; Goel et al. (219); Shi al.
Switching costs:
2222aa b), etc. Convex body chasing with switching costs has been studied in Friedman & Linial 1993;; Sellke (002): Bubeck et al.
1222I) , etc. Switching costs have also been studied in metrical task systems (Borodin & El- Yaniv
2005). online set covering (Buchbinder et al.
2014), k-server problem (Lin et 2020), online con-
trol (Goel & Wierman 2019 Li al. 2020 Lin et al. 2002)) etc. Moreover, switching costs have been studied in adversarial bandit learning, c.g., in Geulen et al. (2010); Dekel et al. (2014); |Arora non-trivial generalization al. (2019): Shi et al. (2022). Our work in this paper can be viewed
of these studies on bandit learning to adversarial MDP, where state transitions and multiple layers in each episode require new developments both the algorithm design and regret analysis.
Static MDP:
There have been recent studies on static RL with switching costs. Specifically, for tabular MDP, [aii et al. (2019) and /Zhang et al.] (2020) proposed RI. algorithms that attain an Ô (VH* SAT In TSA regret with probability 1 6, by incurring O (H Sn switching
costs, where a = 3 and 2, respectively. Recently, Qiao et al. (2022) obtained a similar Õ(VT) regret with probability 1 - 5. by incurring O SASA In 7') switching costs. Moreover, for lin- ear MDP (with d-dimensional feature space), Gao et al. (2021) and Wang et al. (2021) obtained an δ dd H (In )/2) regret with probability 1 8, by incurring O (dH In) switching costs.
Adversarial MDPs: Adversarial RL better models scenarios where the loss distributions and/or the transition functions of MDPs could change over time. Specifically, in tabular MDP with a known transition function, Zimin& & Neu (003)) proposed an RL. algorithm that attains an Ö( SH/SSAY AT) regret. In the case with an unknown transition function, JJin et al. (2020a) and Lee et al. (2200) ob-
tained an Ô (HS In TSA] regret with probability 1 1 8. These studies assume that the state spaces of layers in an episode are non-overlapping. Moreover, [Rosenberg & Mansour (019a) stud- ied the case with full-information feedback. Adversarial linear MDP has also been studied recently, e.g., in Cai et al. (2020); Luo et al. (202T). In addition. Yu & Mannor (209)): CCheng et al. (2019) and Lykouris al. (2021) studied the case when both the loss distribution and transition function change arbitrarily. More studies on various adversarial RL settings have been done by Rosenberg &
Mansour 2019bb: Lee al. (202T): Zhao et al. (2021) Ji et al. (2021) }); He et al. (2022). etc.
To the best of our knowledge, no study in the literature has addressed the challenge due to switching costs in adversarial RL, which is the focus of this paper.
PROBLEM FORMULATION
We consider adversarial reinforcement learning (RL) with switching costs in episodic Markov de- cision processes (MDPs). Suppose there are T episodes, each of which consists of H layers. We use S₁ to denote the state space of layer h. For ease of elaboration, as in previous work & Neu (2013); Jin et al. (2020a) and Lee et al. 2020),, assume that the H layers are
3

---

Published as a conference paper at ICLR 2023
intersecting, i.., Sn n S/ for any h' # h"; So = { is singleton; and each episode ends state Sh {sn}. Thus, the entire state space is S S with size S Σ /f where Sy, denotes the size of Sn. Moreover, we use A to denote the action space with size A. Then, the MDP is defined by a tuple (S.
=== Sh.
where P is the transition function with Ph : S x Sh x A + [0. 1] denoting the transition probability measure at layer h, and 4; S x A - [0, 1] represents the loss function for episode t.
The online learner interacts with the Markov environment messode-by-episode as follows. At the beginning of each episode t= 1, .... T. the online learner starts from state so and follows an algorithm that (possibly randomly) chooses a deterministic policy ग. : S - A. Next, at each layer h 0, .... H 1. after observing the current sate $t, the learner chooses an action ag Te (s..)) Then, the learner incurs a loss le (St,h, a, Finally, the next state St,h+1 E S is drawn according to the transition probability P(-[st.h, (- (For simplicity, we drop the index h of Pk. in this paper when it is clear from the context.) These steps repeat until the learner arrives at the last state 8H- At the end of episode t, only the losses of visited state-action pairs in the episode are observed by the learner, whereas the losses of non-visited state-action pairs are unknown. As in (Zimin & Neu 2013 Jin al.] 2020a; [ee et al. 2020; Cai et al.] 20200, this is called "bandit feedback", which is more practical than full-information feedback (Rosenberg & Mansour (019a) that assumes the losses of all state-action pairs (no matter visited or not) are known for free.
Adversarial losses: Different from static RL that assumes the loss distribution is fixed for all episodes, in the adversarial setting we consider here, we do not need any assumption on the un- derlying loss distribution. That is, the loss function 1, could change arbitrarily across episodes.
Switching costs: As we mentioned in the introduction, in adversarial RL, addressing switching costs remains an open problem. The switching cost refers to the cost needed for changing the policy is equal to 3- 1 f where
is the switching-cor coefficient and is independent of T, and 1g is an indicator function (i.e., 1 1 if the event & occurs, and 1. 0 otherwise).
Therefore, the total cost of exccuting an RL algorithm x over T episodes is given by
T-1
Cost (1 : T) A E
Σ
(( ag + Σ
B ( n P
h=0
where the expectation is taken with respect to the randomness of the state-action pairs (87, aT,,)) visited by π, and the possible randomness of changing the policy ne.
Next, we introduce a concept called "occupancy measure" (Zimin & Neu 2013 Jin et al. 2020a). Specifically, the occupancy measure o;" x. (s, a) = Pr[sī,, = 8, 5, = a ा. P 2 0 is the prob- ability of visiting the state-action pair (x,a) by the algorithm π at layer h of episode I under the transition function P. In addition (with slight abuse of notation), the occupancy measure 9. " (s', a) Pr[s state-action triple (s', ,, a) by the algorithm æ at layers and + of episode / under the transition function P. In order be feasible, the occupancy measures need to satisfy some conditions at layer of episode t. First, according to probability theory, they need to satisfy the conditions that,
sT, = s, s, a|x, Pl 2 the probability of visiting the
9: (s, = Σ
q: a. (s' s,), for all (s, E S, x A, and Σ Σ SES, aEA
q: x. (.. a) = =1 (2)
S'E..11
Second, since the probability of transferring to state from the previous layer h --1 must be equal to the probability of transferring from this state a to the next layer h + 1, we have
Eves, ES EnEA Ui J.P (s, a) = Evesup ExEA d. T.P (8', a), for all s E Sh.
(3)
Third, the occupancy measure should generate the true transition function P, i.e., 27. (d',,,)))))) ELe " (e (r (1,''sss),, a), for all (s', 8, S141 S₁ A.
(4)
We use C(P) to denote the set of all occupancy measures that satisfy conditions 2 Moreover, at the beginning of episode t, the algorithm π associated with the occupancy measure 9 chooses a deterministic policy ne by assigning action E A to each state E S according to the probability
g: (s,
Pr[a[s]
(5)
ΣlEA t. x. P(,
4

---

Published as a conference paper at ICLR 2023
Then, it is not hard to show that the expected total loss, i.., the first term in IT. can be expressed as loss" (1 7) A E
,44) T P Finally, the regret of an RL algorithm is defined to be the sum of the loss regret Rioss (T) and the switching costs of as follows:
2 -= (gi T.P.
R (T)
max E' (EL(P)
Er= la q. n.
E
E ( T.
(6)
loss regret: (T)
switching costs
Therefore, our goal in this paper is to design RL algorithms that achieve as low regret as possible against any possible sequence of loss functions {4)==1 and state transition function P.
A LOWER BOUND
In this section, we will develop a lower bound on the regret for adversarial RL with switching costs. Such lower bound will quantify how difficult it is to control the regret with switching costs under adversarial RL. In Theorem [ below, we provide this lower bound, the proof which is given in Appendix A (In See. [5 and Sec. 6 we will provide two near-optimal RL algorithms to achieve this
lower bound.)
Theorem 1, For adversarial RI. with switching costs and T max (6H2SA, the regret of any RL algorithm can be lower-bounded as follows,
ReT (T) 2 á (3L/S (HSA)//8T21))
Theorem D shows that in adversarial RL with switching costs, the dependency on T of the best achievable regret is at least (2(7233). Thus, the best achieved regret (whose dependency on T is Ö(VT)) in static RL with switching costs (in Bai et al. adversarial RL without switching costs (in Zimin & Neu
2019: Qiao et al. (2022), etc) as well as (2033 : Jin et al. (2018). etc) is no longer
achievable. This demonstrates the fundamental challenge of switching costs in adversarial RL, and
it is expected that new challenges will arise when developing provably efficient algorithms.
Further, in Theorem 2 below, we characterize precisely the new trade-off between the loss regret and switching costs defined in (6). The proof is provided in Appendix B Intuitively, by switching more, the online RL algorithm can adapt more flexibly to the new information learned, and thus achieves a lower loss regret. On the other hand, if fewer switches are allowed, the online RL algorithm is less flexible to adapt to the new information learned, which will incur a larger loss regret.
Theorem 2. For adversarial RL with switching costs, with the switching costs equal to O (3 N Nuii), the loss regret can be lower-bounded by á
(V
T). Alternatively, to achieve loss regret N
HSA
equal Ö (V (HSS Ne T). the switching costs incurred must be larger than 52 (3- NN
Theorem 2 provides an interesting and necessary trade-off between the loss regret and switching costs. We further elaborate this result in three cases. First, in order to achieve loss regret Ö(HVSAT) Theorem 2 shows that the number of switches A/wwi (and thus the switching costs incurred) must be linear in T. i.c., essentially switching at almost all episodes. This is consistent with the regret achieved in adversarial RL without switching costs, i.c., allowing switching linear- to-7 number times for free. But our result further implies that, without linear-to-T switches of the policy, is impossible to achieve an Õ(VT) loss regret. Second, Theorem shows that, if only constant or (In In T) number of switches contrast, static RL, an Ö(VT) loss regret is achieved with only O(I In T') switches (Qiao al., 2022). This indicates that the adversarial nature of RL necessarily requires significantly more policy switches to achieve a low loss regret. Third, Theorem 2 suggests that the loss regret and switching costs can be balanced at the order of Ô (T2/3). That is, achieve the Ô (T2/3) loss regret, the switching costs incurred have to be ÿ (1223). This is consistent with Theorem I where the regret (including both the loss regret and switching costs) is lowered-bound by Ω (T2/3).
allowed, the loss regret must be linear in T. In
5

---

Published as a conference paper at ICLR 2023
Algorithm 1 Switching rEduced EpisoDic relative entropy policy Search (SEEDS)
Parameters: ê for =1:
2//7 and ê (32/3 ( ((SAA)-1/77)
Initialization: Pr[als] A for all (s,a) E E A. Choose ||] = according to (5)
- do
for t= = 1)T + 1: min T do
Step 1: Execute the updated policy
SEEDS
[u] π [.))
end for At the end of super-episode u,
Step 2: Estimate the losses iSHEDS (s. a) for all (s, a) according to [M]
Step 3: Update the occupancy measure SSEDD,
[u+1] (s, a) according to 10 Update the determin-
istic policy (/441)) according to end for
THE CASE WHEN THE TRANSITION FUNCTION IS KNOWN
In this section, we study the case when the transition function is known, and we will further explore the more challenging case when the transition function is unknown in Sec. 6 We propose novel
algorithm (please see Algorithm D with a regret that matches the lower bound in (7). Ouur algorithm
called Switching rEduced Episo relative entropy policy Search (SEEDS).
SEEDS is inspired by the episodic method in bandit learning (Shi et al. 2022). In bandit learning, the idea is to divide the time horizon into ((T2/3) episodes, and pull one single Exp3-arm in an episode. By doing so, the total switching cost is trivially O Meanwhile, the loss regret in an episode is (1) (T which is proportional to the loss variance in an episode. The final 0(T2/3) regret is then achieved by taking the sum of all these costs and tuning the parameter v7 = ( 2/3). However, in the adversarial MDP setting that we consider, there is key difference due random state-action visitations that cause several new challenges as we discuss in the rest of this section.
Super-episode-basee policy search: SEEDS divides the episodes into 4 +1 super-episodes, where 7 E 2 is a tunable parameter and a strictly positive integer. Each super-episode includes т consecutive episodes. For all episodes in each super-episode u 1, .... U4 SEEDS uses the (Step-I in Algorithm that was updated at the end of the last super-episode PPEDDS. is the updated occupancy measure (that we will introduce soon) of SEEDS for super-episode u. Thus, SEEDS switches the policy at most once in each super-episode.
same policy π nul P
1, [s]]
A novel idea for estimating the losses: At the end of super-episode u, SEEDS estimates the losses (s,] a) of all state-action pairs in super-episode u. Here, it is instructive to see why anorrance-estimating method in adversarial bandit learning (i.e., without state tran- sitions) does not apply to our problem. Note that due to state transitions in our more gen- eral MDP setting, we are not guaranteed to visit a single state-action pair for the whole super- episode. A naive but intuitive solution may be pretending that each state-action pair visited in super-episode u was the single one visited. Then, we can let the estimated loss of each state-action
the episodic
pair (s, a) to be (s, = 1-(1-9p)) 2eams (s.a))" ((s.a) was visited in super episode u}, where the numerator
(1.08.0)
(s, a) = Ei= 11 (4(s is the average loss of (s, a). If we assume that the loss 4e for all episodes f in super-episode u were the same, according to the analysis in bandit learning and the inequality 1 (1 x)" " 2 x for all 0 < x < 1, this idea would have worked. However, the problem is that, inside super-episode u, the loss function I, for each episode could change arbitrarily. Thus, the estimated loss |Nv| (s, a) above is actually unknown and an ill-defined value.
To resolve the aforementioned difficulty due randomly-visited state-action pairs and arbitrarily- changing loss functions, SEEDS estimates the loss as follows (Step-2 in Algorithm
J/n] L (s) 30m8, (s.a) 1 ((x.a) was visited in opisodes i (f..)).....11 (5,a) of super-piisede u): (8)
SEEDS (8,a) a) [
2
1uj

---

Published as a conference paper at ICLR 2023
where J/yj is the maximum number of episodes that the state-action pair (s, a) visited in super- episode u. In other words, in super-episode this state-action pair (8, was not visited in any other episode I, such that E {(u 1)r + I,... uT) 3/ the observable true losses in super-episode u. In this way, SEEDS elegantly resolves the aforementioned difficulty due to the random state transitions and adversarial losses. Our novel idea in (8) may be of independent interest for other problems with state transitions and non-stationary or adversarial losses. Indeed, in Sec. 6 we will apply this idea to the case when the transition function is unknown.
1y (s. 9, Thus, SEEDS estimates
the losses based
In Lemma [ below, we show that the estimated loss in 8 is an unbiased estimation of the true loss in super-episode u. This is important property that will exploit in our regret analysis. The proof of Lemma iis provided in Appendix C We use Fiu) to denote the o-algebra generated by the
observation of SEEDS before super-episode u.
Lemma 1, The conditional expectation of the estimated loss designed in 8 is equal to PSEEDS a) Fiull = [s][s, a), for all (s, a), [u]
where the expectation is taken with respect to the randomness of the episodes &1 (8, a), .., in ( a). (ur,(T which the state-action pair (s, a) was visited, and (8,(8, = 2t= 1)r+1 (18 a) is the true loss of (s, a) in super-episode u.
Finally, according online mirror descent (Rakhlin et al. 2009 Zimin & Neu 2013 SEEDS updates the occupancy measure /utt1] iiEEDs (8,, a) for all state- action pairs (8,a) E A as follows (Step-3 in Algorithm D
Updating the occupancy measure:
(s,a)
SEEDS.P [u+11
= arg min mingee(r)) {1 (q. (SEEDS)
+ + (q
SEEDS. [ml
(10)
where (gllg') &
q(s, a) In g(s.a)
Σ (g(s, (s, is the unnormalized
(((a,))
aES,aEA
*ES,aEA
relative entropy between two occupancy measures and q'' on the space S x A. Recall that C(P) (SEEDS) represents the expected loss in super-episode is formulated by - Note that the term (g. [o]
u, with respect to the newly-estimated loss function NLEDS Thus, it captures how SEEDS adapts to
[o]
and explores the newly-estimated loss function. In addition, the term DxL SEEDS, serves [M] SEEDS,P Thus, it regularizer ensure that the updated occupancy measure in (10) stays close ((l
captures how SEEDS exploits the previously-estimant loss functions before super-episode u. As result, by tuning the parameter in (10). the updated occupancy measure strikes balance between exploration and exploitation.
We characterize the regret of SEEDS in Theorem below.
Theorem 3. Consider adversarial RL with switching costs introduced in Sec. When the transition function P is known, the regret of SEEDS is upper-bounded as follows,
RSEEDS (T) Ö (31/3 (H
(11)
Theorem 3 shows that the regret of SEEDS matches the lower bound in 7 in terms of the depen- dency on all the parameters T. S, A, H and B. Thus, the regret of SEEDS is order-wise optimal. To the best of our knowledge, this the first regret result for adversarial RL with switching costs. To prove Theorem 3 the main difficulty lies in capturing the effects of the abbirrrily-chanpee and multiple random visitations of each state-action pair in a super-episode. To overeome this dif- ficulty, our new idea is to first upper-bound the loss regret based on the correlated loss feedback super-episode, and then relate these upper bounds across all super-episodes to the final regret. The first step relies on the proof of Lemma and the second step relies on another lemma in Ap- pendix D.I that transfers the original regret formulation to a form based on the losses from the entire super-episode. Please see Appendix D for details and the proof of Theorem S
losses
Further, in Theorem below, we show that SEEDS attains a trade-off between the loss regret and switching costs that matches the offe-off in Theorem 2 The proof of Theorem 4 follows the loss- regret bound of SEEDS proved in Appendix D and the trivial switching-cost bound 3 [[] Please the end of Appendix for details.
7

---

Published as a conference paper at ICLR 2023
Algorithm 2 SEEDS- Transition (SEEDS-UT)
Parameters: // é (S-1/ 2/3), Ô ((8)))))(((())22331-=1113
θ 1/35//111/3//////
and < 1.
Initialization: 911
UT. 8,', A and M1j (, 8, = N 0. for all
(s), E Sh+1 S₁.
A and all h. Pln contains all possible transition functions. Choose
"[1]
SEEDS-UT = π 90
according to 2 and 5
for = : + do
for (u + min (ut, T) do
Step 1: Execute the updated policy " SEEDS-UT 11)
UT.
end for
At the end of super-episode
Step 2: Estimate the losses ( /SHEDS.UT a) for all (s, a) according to (12).
Step 3: Estimate the transition-function set P P(u+ according to (14).
-SEEDS- (s', according to 10 but subject to Step 4: Update the occupancy measure q[++1]
senm u.P
different constraint E C (P(u+1). Update the deterministic policy (1)
according to
2 and (5).
end for
Then, with the switching costs equal O O ( ASSEEDS), SEEDS can achieve loss regret upper-bounded by Ô (V
Theorem Let NEEED A -1
HSA
TT)
N NAREO
THE CASE WHEN THE TRANSITION FUNCTION IS UNKNOWN
In this section, study more challenging case when the transition function is unknown. We propose a novel algorithm (please see Algorithm{ with a regret that matches the lower bound in 7 in terms of the dependency on all parameters, except with a small factor of (HH133.. Specifically, to address the difficulty due the unknown transition function P in this case, advance SEEDS into SEEDS-UT (where UT stands for "unknown transition") with three new components we explain below.
1. Since the transition function P unknown, updating the occupancy measure g(s, a) (as in SEEDS) not good enough. Instead, SEEDS-UT updates the occupancy measure q(s', s, a) to take state transitions into consideration.
Since the transition function P is unknown, the updated occupancy measure could be different from the true one. To resolve this issue, we generalize the method in Neu (0155), with a difference handle the random sequence of the state-action pairs visited in each super-episode, Specifically, SEEDS-UT estimates the loss for each super-episode as follows (Step-2 in Algorithm
Jum] (s.a)))) (s, Σ
iSEEDS. [1]
2/y (s.a) ((s.a) a) was visited in episodes t (s.0))..... (5.a) of super-episode u)+ (12)
where (s, max ) (8, a) + is the sum of the largest probability of visiting (s,
among all occupancy measures in ((Pp.)) and tunable parameter 7 O, and P|u) is transition-
function set that we will introduce soon. Note that (12) is another application of our idea in (8) for estimating losses in problem with state transitions and adversarial losses.
In Lemma 2 below, we show that the gap between the expectation of the estimated loss and the true
loss controlled by the parameter 7. The proof of Lemma provided in Appendix F We use
Fiu to denote the r-algerra generated by the observation of SEEDS-UT before super-episode u.
Lemma 2. The conditional expectation of the estimated loss designed in (2 is equal
SEEDS (s,a) 9l0
E
fSEEDS-UT [1]
Fuu]
mmxx a(s.a)ty (s, (s. a), for all (s, a),
(13)
8

---

Published as a conference paper at ICLR 2023
where the expectation is taken with respect to the randomness of the episodes t (s, a), ... (s,
in which (s, a) was visited, 4u1 SEEDS-UT.PP (8, a) is the true occupancy measure of SEEDS-UT condi- tioned on Fig. and (u](s,
Emin(arT) (e(s,a) a) is the true loss of (s.a) in super-episode
Lemma 2 shows that, long as Piu is sufficiently good for estimating the true transition function P (we will show how to construct such a P/n) below), by carefully tuning 7; the bias caused by maxgeC(P(.)) ((s, a) + y (i.c., Ls a)) should be sufficiently small, so that the estimated loss is still sufficiently accurate.
3. Since the transition function P is unknown, the constraint in (10) is no longer known. To resolve this issue, we generalize the method in Jin et al.] (2020a), with a difference to handle the samples from the whole super-episode. Specifically, at the end of each super-episode, SEEDS-UT col- lects the samples from the whole super-episode to update the empirical transition probability (
where Mu+nj(s's 8, a) and Niu+1j a) denote the number of times visiting (s', s, a) and (s, a) before super-episode u + 1, respectively. Then, based on the empirical Bernstein bound (Maurer & Pontil (209)) SEEDS- UT constructs a transition-function set P as follows (Step-3 in Algorithm 2).
Pla-1j(s'|s, |s, a) max (+)a)))))
Plu+1| = (Rut1): |Pt+ta (8'18,a) Puttj(6'(ss a) S (/u+1](s', s,, for all (s', (s), (14)
Plussj(o' 7$4
14 TSA
where (ju+1](s', 0,0) (,) = 2v max Mi++
maax Mu++ (+,,)))-111111 and d (0, 1) is the /SEDDS-UT 88', a) is updated according to Pu+1]
confidence parameter. Finally, the occupancy measure 10). but subject to a different constraint E C (P|u+1) (Step-4 in Algorithm
We characterize the regret of SEEDS-UT in Theorem 5
below.
Theorem 5. Consider adversarial RL with switching costs introduced in Sec. 3 When the transition function P is unknown, with probability 1 5, 6, the regret of SEEDS-UT UT is upper-bounded as follows,
RSEEDS-UT UT (T) S Ō (3 1//3 (SA)) 13 T2/3 (In TSA) 1/2)
(15)
Theorem 5 shows that the regret of SEEDS-UT matches the lower bound in 7 in terms of the depen- dency T. S, A, and B, except with small factor of ((H1/3). That is, the regret of SEEDS-UT is near-optimal. To the best of our knowledge, this is the first regrei resull for adversarial RL with switching cost when the transition function is unknown. To prove Theorem 5 the main difficulty is that, due to the delayed switching and unknown transition function, the losses of SEEDS-UT in the episodes of any super-episode are correlated and the true occupancy measure is unknown. As result, the existing analytical ideas in adversarial RL without switching costs and adversarial bandit learning with switching costs do not work here. To overcome these new difficulties, our analysis involves several new ideas, e.g., we construct a series in (35) to handle multiple random visitations of each state-action pairs, and establish a super-episodic version of concentration in Step-2-iii of Appendix G by relating the second-order moment of the estimated loss that we design to the true loss and the length 7 of super-episode. Please see Appendix for the detailed proof of Theorem
7 CONCLUSION AND FUTURE WORK
In this paper, we make the first effort towards addressing the challenge of switching costs in ad- versarial RL. First, we provide a lower bound that shows that the best achieved regret in static RL with switching costs (as well as adversarial RI. without switching costs) is no longer achievable. In addition, we characterize precisely the new trade-off between the loss regret and switching costs, which shows that the adversarial nature of RL necessarily requires more switches to achieve a low loss regret. Moreover, we propose two novel switching-reduce lower bound when the transition function is known, and match our lower bound within small factor of 1/3133) when the transition function is unknown.
algorithms with regrets that match
Several future directions are worth pursuing. First, it is important to study adversarial RL with switching costs in linear and more general MDP settings. Another interesting future work to extend our study to the dynamic regret, which allows the optimal policy to change over time.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
The work of M. Shi has been partly supported by NSF grant NSF AI Institute (AI-EDGE) CNS- 2112471. The work of Y. Liang has been partly supported by NSF grants NSF AI-EDGE CNS- 2112471 and RINGS-2148253. The work of N. Shroff has been partly supported by NSF grants NSF AI-EDGE CNS-2112471, CNS-2106933, 2007231, CNS-1955535 and CNS-1901057, and in part by Army Research Office under Grant W911NF-21-1-0244
REFERENCES
Alckh Agarwal, Nan Jiang, Sham M Kakade. and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, pp. 10-4, 2019.
Raman Arora, Teodor Vanislavov Marinov, and Mehryar Mohri. Bandits with feedback graphs and switching costs. Advances in Neural Information Processing Systems, 32, 2019.
Mohammad Gheshlaghi Azar, Ian Oshand, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International Conference on Machine Learning, pp. 263-272. PMLR, 2017.
Yu Bai, Tengyang Xie, Nan Jiang, and Yu-Xiang Wang. Provably efficient q-learning with low switching cost. Advances in Neural Information Processing Systems, 32, 2019.
Abdellah Bennane. Adaptive educational software by applying reinforcement learning. Informatics in Education, 12(1):13-28, 2013.
Allan Borodin and Ran EI- Yaniv. Online computation and competitive analysis. cambridge univer- sity press, 2005.
Sébastien Bubeck, Yuval Rabani, and Mark Sellke. Online multiserver convex chasing and opti- mization. In Proceedings of the 2021 ACM-SIAM Symposium Discrele Algorithms (SODA), pp. 2093-2104. SIAM, 2021.
Niv Buchbinder, Shahar Chen, and Joseph Naor. Competitive analysis via regularization. In Pro- ceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pp. 436-444.
SIAM, 2014.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang- Provably efficient exploration in policy opti- mization. In International Conference on Machine Learning, pp. 1283-1294, PMLR, 2020.
Niangjun Chen, Joshua Comden, Zhenhua Liu, Anshul Gandhi, and Adam Wierman. Using pre-
dictions in online optimization: Looking forward with an eye on the past. ACM SIGMETRICS 2016.
Performance Evaluation Review,
Wang Chi Cheung, David Simchi-Levi and Ruihao Zhu. Reinforcement learning under drift. arXiv preprint arXiv: 1906. 02922, 2019, 2019.
Ofer Dekel, Jian Ding, Tomer Koren, and Yuval Peres. Bandits with switching costs: T 2/3 regret. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pp. 459 467, 2014.
Joel Friedman and Nathan Linial. On convex body chasing. Discrete Computational Geometry, 933):293-32,, 1993.
Minbo Gao, Tianle Xie, Simon S Du, and Lin F Yang. A provably efficient algorithm for linear markov decision process with low switching cost. arXiv preprint arXiv:2101.00494 2021.
Sascha Geulen, Berthold Vöcking, and Melanie Winkler. Regret minimization for online buffering problems using the weighted majority algorithm. In COLT, pp. 132-143. Citeseer, 2010.
Gautam Goel and Adam Wierman. An online algorithm for smoothed regression and lqr control. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 2504-2513. PMLR, 2019.
10

---

Published as a conference paper at ICLR 2023
Gautam Goel, Yiheng Lin, Haoyuan Sun, and Adam Wierman. Beyond online balanced descent: An optimal algorithm for smoothed online optimization. Advances Neural Information Processing Systems, 32, 2019.
Jiafan He, Dongruo Zhou, Tong Zhang. and Quanquan Gu. Nearly optimal algorithms for linear contextual bandits with adversarial corruptions. arXiv preprint (eX.iv:2205008111 2022.
Chi Jin, Zeyuan Allen -hu, Sebastien Bubeck, and Michael Jordan. q-learning provably effi- cient? Advances in neural information processing systems, 31, 2018.
Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning adversarial markov decision processes with bandit feedback and unknown transition. In International Conference on Machine Learning, pp. 4860-4869. PMLR, 2020a.
Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143. PMLR, 2020b.
Tiancheng Jin, Longbo Huang, and Haipeng I Luo. The be both worlds: stochastic and adversarial episodic mdps with unknown transition. Advances in Neural Information Processing Systems, 34: 20491-20502, 2021.
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey, The International Journal of Robotics Research, 32(1 12(133323811274 2013.
Sanjay Krishnan, Zongheng Yang. Ken Goldberg, Joseph Hellerstein, and Ion Stoica. Learning to optimize join queries with deep reinforcement learning. arXiv preprint arXiv:1808.03319 2018.
Chung-War Wei Lee, Haipeng Luo, Chen- Buen-YuuBo Wei, and Mengxiao Zhang. Bias no more: high-probability data-dependent regret bounds for adversarial bandits and mdps. Advances in neural information processing systems, 11522-1555255 2020.
Chung-Wa Wei Lee, Haipeng Luo, Chen- Yu Wei, Mengxiao Zhang, and Xiaojin Zhang. Achieving near instance-optimallty and minimax-opptmall in stochastic and adversarial linear bandits simulta- neously. In International Conference on Machine Learning, pp. 6142-6151, PMLR, 2021.
Yingying Li, Guannan Qu, and Na Li. Online optimization with predictions and switching costs: Fast algorithms and the fundamental limit. IEEE Transactions on Automatic Control, 66(10): 4761 2020.
Minghong Lin, Adam Wierman, Alan Roytman, Adam Meyerson, and Lachlan LH Andrew. Online optimization with switching cost. ACM SIGMETRICS Performance Evaluation Review, 40(3): 98-100, 2012.
Yiheng Lin, Gautam Goel, and Adam Wierman. Online optimization with predictions and non- convex losses. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4 (1):1-32, 2020.
Yiheng Lin, Yang Hu, Guanya Shi, Haoyuan Sun, Guannan Qu, and Adam Wierman. Perturbation- based regret analysis predictive control in linear time varying systems. Advances in Neural Information Processing Systems, 34:5174-5188 5185, 2021.
Haipeng Luo, Chen-Ye Wei, and Chung- Wei Lee. Policy optimization adversarial mdps: Im- proved exploration via dilated bonuses. Advances in Neural Information Processing Systems, 34: 22931 2021.
Thodoris Lykouris, Max Simchowitz, Alex Slivkins, and Wen Sun. Coruption-robust exploration in episodic reinforcement learning. In Conference on Learning Theory, pp. 9242-3245. PMLR, 2021.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penal- ization. In Proceedings of the 22nd Annual Conference on Learning Theory, 2009.
11

---

Published as a conference paper at ICLR 2023
Gergely Neu. Explore no more: Improved tigh-probability regret bounds for non-stochastic bandits. Advances in Neural Information Processing Systems, 28, 2015.
Dan Qiao, Ming Yin, Ming Min, and Yu- Xu-Xiang Wang. Sample-cfficient reinforcement learning with log log(t) switching cost. arXiv preprint arXiv:2202.06385, 2022.
Alexander Rakhlin, J Abernethy, A Agarwal, P Bartlett, E Hazan, and A Tewari. Lecture notes on online learning draft, 2009.
Aviv Rosenberg and Yishay Mansour. Online convex optimization in adversarial markov decision processes. In International Conference on Machine Learning, pp. 5478-5486. PMLR, 2019a.
Aviv Rosenberg and Yishay Mansour. Online stochastic shortest path with bandit feedback and unknown transition function. Advances in Neural Information Processing Systems, 32, 2019b.
Mark Sellke. Chasing convex bodies optimally. In Proceedings of the Fourteenth Annual ACM- SIAM Symposium on Discrete Algorithms, pp. 1509-1518. SIAM, 2020.
Ming Shi, Xiaojun Lin, and Sonia Fahmy. Competitive online convex optimization with switching costs and ramp constraints. IEEE/ACM Transactions on Networking, 29(2):876-889, 2021a.
Ming Shi, Xiaojun Lin, and Lei Jiao. Combining regularization with look-ahead for competitive online convex optimization. IEEE INFOCOM 2021-IEEE Conference on Computer Commu- nicutions, pp. 1-10. IEFE, 2021b.
Ming Shi, Xiaojun Lin, and Lei Jiao. Power-of-2-arms for bandit learning with switching costs. In Proceedings of the Twenty- Third International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, pp. 131-140, 2022.
Georgios Theocharous, Philip S Thomas, and Mohammad Ghavamzadeh. Personalized ad recom- mendation systems for life-time value optimization with guarantees. In Twenty-Fouth Interna- tional Joint Conference Artificial Intelligence, 2015.
Tianhao Wang, Dongruo Zhou, and Quanquan Gu. Provably efficient reinforcement learning with linear function upproximation under adaptivity constraints. Advances in Neural Information Pro- cessing Systems, 34:13524-13536, 2021.
Zhiyuan Xu, Jian Tang, Jingsong Meng, Weiyi Zhang, Yanzhi Wang, Chi Harold Liu, and Dejun Yang. Experience-driven networking: deep reinforcement learning based approach. In IEEE INFOCOM 2018-IEEF conference computer communications, pp. 1871-1879. IEEE, 2018.
Chao Yu, Jiming Liu, Shamim Nemati, and Guosheng Yin. Reinforcement learning in healthcare: A survey, ACM Computing Surveys (CSUR), 55(1):1-36, 2021.
Jia Yuan and Shie Mannor. Arbitrarily modulated markov decision processes. In Proceedings of the 48h IEEE Conference Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference, pp. 2946-2953. IEEE, 2009.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference-advantage decomposition. Advances in Neural Information Processing Systems, 33: 15198 15207, 2020.
Heyang Zhao, Dongruo Zhou, and Quanquan Gu. Linear contextual bandits with adversarial cor- ruptions. arXiv preprint 1ttt:2110012211.. 2021.
Alexander Zimin and Gergely Neu. Online learning in episodic markovian decision processes by relative entropy policy search. Advances in neural information processing systems, 26, 2013.
12

---

Published as a conference paper at ICLR 2023
A PROOF OF THEOREM
Note that the bandit setting is special case (when S = H 1) of our MDP setting. Thus, the lower bound for the adversarial bandit setting in [Shi et al. (2022) serves as lower bound in our MDP setting. However, the direct use of such a lower bound from bandits will not be good enough for the MDP case that we study in this paper. To get the lower bound in Theorem [ the most challenging and interesting part is to design the lower-bound instance. Notice that lower- bound transition
constructed for stochastic MDP in Qiao et al. (2022). which shows that the MDP setting is at least difficult multi- lower bound can be obtained based on the lower bound from bandits. In this section, we construct new lower-bound instance. Specifically, divide the state space S and construct special state transitions, such that the episodic reinforcement learning is reduced to ((SHH) chains of bandit learning. Notice that the lower-boume analysis in (Shi et al. (2022) implies that, with the loss function 4 upper-bounded by H. A arms and T time-slots, the regret of any bandit-learning algorithm with switching costs is at least á (,3/33 A1/3 (HT)2/3) when T 2 max max A) Hence, the total
bandits with 52 (AH)) arms, and then similar
regret from all ()) chains of bandit learning is at least ② (31/3 (H 3/ )3/)) ((S/H)
á (15A) Please see our detailed proof below.
Proof. Lower-bound instance: We consider special instance where S - divisible by H 1. First, we assign the states in the state space S to each layer as follows. The first layer contains single sate, i.e., So = {so}. All episodes end with state Sh = {sH}. Moreover, the rest of the S states are assigned to each layer h E [1, H 1] evenly. That it, each layer h [1, H 1] contains 8-2 states. Following the sequence of the states at each layer, we call the index i of the i-th state カ-
the "order" of it. In addition, the order i of the states at layer h of any episode is the same, e.g., the first state at layer
always the first state at layer for all episodes, and the second state at layer h is always the second state at layer h for all episodes. Moreover, all actions are available at each state 8 E S. Finally, based on this construction of the states and actions, we run independently the lower-bound algorithm for adversarial bandit learning with switching costs in (Shi et al. 2022) as subroutine through all i-th states, for all é = 1.., 7. That is, for each layer h (* a) = 1 for all a, and (8y18,, a) = 0 for all j + and all a.
1,
Lower-bound analysis: The lower-bound analysis in Shh et al.] (2022) implies that, with the loss function l upper-bounded by H, A arms and T time-slots, the regret (including both the loss regret and switching costs) of any bandit-learning algorithm with switching costs is at least á (31/33 /1/3(HH))2/3) Notice that based on our lower-bound instance constructed above, there 8-2 H-1 chains of bandit learning. Hence, the total regret of any RL algorithm a from all these 8-2 chains of bandit learning can be lownrebounded as follows.
F-1
2/3
RdT RT(T) 20
H
T
H =((B))(SS)))TT01))
S-2
(16)
--2
1-1
B PROOF OF THEOREM 2
The proof of Theorem 2 follows the lower bound proved in Appendix A but by considering the loss regret and switching costs separately.
Proof. To prove Theorem 2 we use the lower-bound instance that constructed above for proving Theorem [ in Appendix First, the lower-bound analysis in Shi et al. (2022) implies that, for adversarial bandit learning with the loss function I, upper- bounded by H, A arms and T time-slots, when the total switching cost is equal to O(3 _/sw),, the loss regret can be lower-bounded by
$-2 chains of bandit learning in the lower bound instance HT). Notice that there are #-1
that constructed in Appendix A Thus, with total switching cost equal to O(B Asswi) A
13

---

Published as a conference paper at ICLR 2023
O(3 E. > the loss regret of any RL algorithm и against the lower-bound instance that constructed above can be twverbbuudee as follows,
8-2
Ross
A
T
52
Newi T)
HSA
swi
S-2
H-1
3/2
Finally, the second half part of Theorem 2 is trivially true, since it is the converse-negative proposition of the first half part that we have proved above.
where the equality is because ΣEs1
A
2
A
1-1
C PROOF LEMMA
Proof. First, since the expectation taken with respect the randomness of the episodes t (s, a), ... Li (8, a), in which the state-action pair (s, a) was visited, the left-hand-side of (9) is equal to
E SEEDS (s, (s,a) Fio]
Σ
SEEDS [u
(s. Pr [ftz(8, a), ... tu (s. a)) Fln)
(t, (f (x,a)) Cl(u-1)r (,rr)
Next, according to the definition of the estimated loss that design in 88 we have
Jual (s, a)
SEEDS M
(s, a) Fiul
Σ
SEEDS, P (s,
(6 (t,(s (s.a)) ==1 [ul C[(u- +1,r)
1 ((s.a) was visited episades (s.a)..tt (8,0) of spper-e u} Pr (4)))))))...)
In the following, we prove that
Jul (3,5))
Σ
1 ((x.a) was visited episodes do (s.a)).....f (s,a) of suspe episade 1:
SEEDS,
(s,a)
(ti(a.)...d Uuy (s,a)) E1(u-1)++1,0
1=1
4(s,a) a)
Pr (y,
by
= Σ
SEEDS.P (
(s,a)
SEEDS (
(s,a)
That is, under our new design of the estimated loss in (8) summing over all possible sets of the the left-hand-side)
random episodes where the state-action pair visited (i.e., the outer equivalent to summing over all deterministic episodes from the beginning to the end of a super- episode (i.e., the sum on the right-hand-side).
This is because first, relying on the above indicator function on the left-hand-side, the sum of the total observed loss in super-episode over all possible sets (s, a),... (yn (s,a) is equivalent the sum of the total true loss in each episode of super-episode based on whether the episode is observed. Therefore, we have
le(s.a)
E SEEDS
[1]
(s,
Fiu]
Σ
Σ
SEEDS, (8,a)
t=
(1, (s.a)....t. (eo)):: te (s.a)..... (x.a))
[(1)
Pr [(11(,))) My (8.
(17)
In addition, since the transition function P known, conditioned on Fiu the probability of visiting each state-action pair (s, a) in episode of super-episode is equal to the occupancy measure
14

---

Published as a conference paper at ICLR 2023
SEEDS, V1
(s,a), i.e,
Σ
Pr (1)())))).... (3) - [u]
SEEDS,
(s,
(18)
(11 (1. (s.a)):
IE (*1.8.) luy (s,a))
Finally, by combining
17 and 18
we have
ur
11ss a)
R
SHEDS
8, a)
Flul
t= (u- 1)++1
Σ
qul
SEEDS,
(8,
4u]
SEEDS.
(8,
Σ
4(88aa = ())
t= 1|++
D PROOF OF THEOREM AND THEOREM
Since the total switching of SEEDS is trivially upper-bounded by 8 [ prove Theorem we focus on upper-bounding the loss regret of SEEDS, i.e.,
SEEDS Joss
(T)
max E gEC(P)
S
9.41 SEEDS, P
A IE
S q:
q" 44 SEEDS, P
To upper-bound the loss regret, the main difficulty lies in capturing the effects of the arbitrarily- changing losses and multiple random visitations of each state-action pair in super-episode. To overcome this difficulty, our proof of Theorem 3 first upper-bounds the loss regret based on the correlated loss feedback in super-episode (which relies on our new design of the estimated loss in (8) and Lemma D and then relates these upper bounds across all super-episodes to the final regret (which relies another lemma, Lemma below, which transfers the original regret formulation to a form based on the losses from the entire super-episode).
Specifically, for each super-episode, we first relate the true occupancy measure qi SEEDS,P to the un- .SEDD.. to (10). Then, we relate .SEDS, to the optimal offline occupancy constrained solution [[++1]
9u+1]
measure o" The gaps between them are upper-bound bound mainly by using Lemma Finally, by com- bining all the loss gaps (according Lemma and super-episodie version of online mirror descent) and the switching-ae
upper-bound, 3 []] and tuning the parameters and 7 as in Algorithm we can get the regret of SEEDS Theorem and the trade-off in Theorem Please see the detailed proofs of Theorem 3 and Theorem 4 in the next two subsections.
D.1 PROOF OF THEOREM 3
Proof. Step-1 (Bounding the switching costs): Since SEEDS switches at most once in each super- episode, the total switching cost of SEEDS is upper-bounded by B3. [T]] In the following, we focus on upper-bounding the loss regret R2SEEDS (T)).
Step-2 (Bounding the loss regret):
First, since SEEDS applies the same occupancy measure for all episodes t of the same super-episode and the transition function P is known. conditioned on the history before super-episode u, the true occupancy measures of these episodes are the same. Then, transfer the original regret formulation to form based on the
according to Lemma 3 below, losses from the entire super-episode.
Lemma 3. The loss regret RSEEDS (T) of SEEDS is equal to
T
14
E
SEEDS.P 4x
q" .4) SEEDS, P = E
SEEDS, [u]
9-', ,4,) SEEDS, P
(19)
15

---

Published as a conference paper at ICLR 2023
Note that the occupancy measure and loss the seft-hand-side of (19) are for each episode t, while those on the figt-hand-side of (19) are for each super-episode u. Please see Appendix for the proof of Lemma 3
Next, use [u+1]]
( denote the unconstrained solution to 10), i.e.,
P & arg min {π (q.
(SEEDS + DKL (q [M) [m]]
SEEDS. }}
[u+1]
Notice that SEEDS,P is the constrained solution to (10) where the constraint is q E C(P). is not qu++1] hard to get that
SEEDS, [++1]
(8, -[u)
SEEDS, P (s, a) e -uul "aa (s,o).
(20)
To get (20), let us consider the function f()) = (q, SSEEDS + DKL (q Pu] [N] (
According
to the definition of (1lle)) right after 10 the derivative of function f(g) is
Of(g) n
q(s,0 a) SEEDS,
iSEDDS [M]
(8, a) + In
0g(s, a)
[ul
(s, a)
By letting the derivative be 0 and rearranging the terms, we have 20
Remark 1. Notice that, similar to the above steps that use standard convex optimization method to ger 20 we can get the the final solution to (10) as follows,
SEEDS.
(s, ( ((a
(u))
SEEDS [ut1]
(s,
Z'ul (8]) h(s))
where (1,
Σ
(s, () a(s, = -n((s, E (()))((d(sss seES
aES
v(s), and 0/u) = arg min In (u, (v, h). This is consistent with the expression provided Propo-
sition in Zimin & Neu 2013)
Then, because of Lemma 3
is equal to and the fact that the calculated occupancy measure 1aa)
SEEDS,
SEEDS, we have
the true occupancy measure 9[u]
T
1
E
SEEDS, -mm
SEEDS, P
E
SEEDS.
q"
SEEDS, P
According to the linearity of expectation, we can decompose the loss regret into two terms that are easier to be bounded as follows,
T
21
S ft
SEEDS,
SEEDS,
g" (401) SEEDS, P)
==1
21
E Bii
E
[uu]
SEEDS.P
qxh M(m) Fiul Fiu..P]
Σ
E
P
SEEDS, P .Mui) Flu). P]]
u=1
24
By
SEEDS. [u+1]
9" g", Flu), P[]
(21)
where the second equality is because E|X of the expectation, and we drop the condition on SEEDS since is clear from the context.
Y|]] the last equality is because of the linearity
Below, focus upper-bounding the two terms the right-hand-side of 21 one-by-one.
16

---

Published as a conference paper at ICLR 2023
Step-2-i (Bounding the first term): Since e" + from 20 we have
SEEDS,
(s,
SEEDS,
(s, 79
SEEDS, (s, a) PM
PHEDS
(s, a).
[u]
Thus, the first term on the right-hant hind-side of can be upper-bounded as follows,
u
E
E
{
(m))
S
P
SEEDS, P
[a-
Muul Fiul, pl]
E
E
Σ
[a
SEEDS, P (8,a)
Piu
SSEEDS(s,
4u](8, a) Flui
sES,aEA
Then, according to the definition of the estimated loss that we design in 8 we have
M
E
E
(
[al
SEEDS.P
lu+1]
SEEDS.P
Flu), p|]
J/ul
(s,sa)))s,a)
EE Fin]
E
Σ
SEEDS, P (8, a)
u=1
LAEA
1=1 [u]
SEEDS,
(s, a)
((f.a) was visited in episodes fi (s,a) (s.a) of super-episade u) 1// (8, a)
Flul. P
14
E F
E
Σ n (1))
Fluj, P
sES,aEA
< SAA
72
(22)
Jin
min(ur, (s, <
where the second inequality is because
Σ 4 1=1
Σ
4(s,a) = (s a), and the
(=
last inequality is because (s,) S T and 4 17..
2-ii-2-i (Bounding the second term):: According to online mirror descent (Rakhlin al. 2009
Zimin Neu 2013), we have the following inequality for the unconstrained solution Mu++ to
SSEEDS,
0D (919
SEEDS,P
9 9u+11] 17 -
P
SEEDDS
2 0, for all q.
Oq
(a
aDa. (allg (elss
SEEDS, P Fi-
Since
In
by rearranging the terms, we have
Arma, 77 4(ol
1u++1
SEEDS, 9u+1]
(ut1]
SEEDS,P
SEEDDS [c]
<
SEEDS.P
[[+1]
In
SEEDS,
for all g.
9
17

---

Published as a conference paper at ICLR 2023
By adding and subtracting terms the right- hand-,, we have
S
/SEDDS
[+
9,
[u]
Wn
Σ
((,,a)l In SEEDS,
(ss, a)
Σ
a(),a)= [ul
SEEDS,
(s.
sES,aEA
[uu
(8,
sES,nEA
SEEDS.P lu+1]
(s, a) In SEEDS, P
[u+1]
SEEDS,
(8, a)
9u++1]
SELDDS P (s.
SEEDS.
(s, (s,a)
[M (s,
SES,aEA
#ES,nEA
SEEDS, (s,
((88,a) 4m
SEEDS, (s.a)) +
((s In
91++1
((s,a)
aES
=ES,aEA
SEEDS, (8.
SEEDS, P (8, (s, [ul
[u++]]
aEA
DKI. (1l
SEEDS.
DRL.
9[++1]
SEEDS, P SEEDD..)
[1
DRI. (all (all P), for all
Then, together with Lemma
I we have
"
SEEDS, (u+t1)
q² .(u)) Flul P|]
Fi
1
E EF
E
Putil
SPEDS,
q² (SEEDS [iul, P]
EFul
B
DKL
(uu+1l
SEEDS,
[(a]
SEEDS,
DKI. " P)
Fiu) P]
Since the intermediate terms get cancelled and the relative entropy is always non-negative, the sec- ond term the right-hand hait--addd-ee of (2I can be upper-bounded follows,
(xl SEEDS.
EF
B
(
SEEDS, [u+1]
q" M/m) Frui, pl
<
H
SA H
(23)
1
Step-3 (Final step): Finally, by combining 22 23
and the switching- upper-bound 3 [ and tuning the parameters and as in Algorithm we have that the regret of SEEDS is upper- bounded by O (31/3 (HAA)/3 T2/3). (22/33
D.2 PROOF OF THEOREM 4
By considering the loss-regret bound that we prove above and the switching-cost bound separately, we can prove Theorem
Proof. According to 22 and 23 above, with the total switching cost equal to 0 (T]) = ( AVSEEDS), the loss regret of SEEDS is upper-bounded as follows,
SEEDS (T) S (1SATT 4) = -VHHAATT) =Ö
(
HSA ATSEDS
(24)
where the first equality is by tuning = V SA77 and the last equality is because N SEEDS A
H
18

---

Published as a conference paper at ICLR 2023
E
PROOF OF LEMMA 3
For the convenience of the reader, we re-state Lemma 3
beloo.
Lemma
The loss regret 1oss (T") of SEEDS is equal to
E
SEEDS,P
q" .1)
SEEDS, P
E
SEEDS,
9",, .4m)
SEEDS, P
(25)
Proof. We drop the condition SEEDS since it is clear from the context. First, according to the linearity of expectation, we have that the sit-hand-side of (25) is equal to
u
Σ SEEDS,
q" (2744)
Σ
SEEDS
q" .44
Then, since conditioned on the history before super-episode u, the true occupancy measures for all episodes & of the same super-episode are the same, we have
T
4
min ur,
E
PEEDS, 4
o² ,4,
P
Biisi
Ey
Σ
SEEDS,
n- .14) Fln): P
==1
1)++1
U1
min. T)
BF
I
Σ
qul
SEEDS,
q= ,4,) Fin)
4=1
1=(u 1)++1
Finally, since the true loss is (8, a) = -== 1u-1)741 le we have
minffrr.)
E
Σ
Ut
SEEDS,
o" 11)
E (
SEEDS, x= (1 Flms p]]
E
q [u]
SEEDS.P P
q" (1mm |p|
F PROOF OF LEMMA 2
The proof is similar to the proof of Lemma in Appendix
C
Proof. First, since the expectation is taken with respect to the randomness of the episodes t (s, a), tu (s, a). in which the state-action pair (s, a) was visited, the left-hand ha-d-ad--sde of (13) is equal to
E
SEEDS-UT UT
(s, a) Fiul
Σ
(SEEDS-UT (8,a) Pr [(4((,))) ..., (,, (s, Fu.)
(t.(e.a).....)pp (a.a)) (((x-1)++laa)
Next, according to the definition of the estimated loss that design in (2). have
J (s, Σ
SEEDS UT (s, (s.a) FMu]
E
27 (s,a)
(tr (a.0)......... 1 3=1 (1(a-1)7+1,am
1 ((s.a) was visited in episodos (s.a)..... (8.0) of super-cpisode at Pr (4)) (s5
19

---

Published as a conference paper at ICLR 2023
Then, relying the above indicator function, the sum of the total observed loss in super-episode over all possible sets {ti a). EJ (s, a is equivalent to the sum the total true loss in each episode of super-episode based on whether the episode is observed. Therefore, have
Wr
4(s,a)
E
SEEDS
(s, Fr)
E
E
(s)((,,))
(u-1)r++ (1(e.)).... (ug (s,a)):
(eft(ss.))..... (sa))
Pr (ftisaa)) (s.
Finally, since conditioned on Fu. the probability of visiting each state-action pair (s, a) in an episode / of super-episode u is equal to the occupancy measure SEEDS. (s, we have [N
ur
a(s,a) 2 [u] (8,
E
|SEEDS-UT (s, Fill []]
SEEDS-UT, [ul
(s,0)
t= 1
qul
SEEDS-UT.P (s,a)
NT
SEEDS-UT,,
(s,
4(5,
2 (8))(,00
2/ (8,
Am 1m 1)7+1
G PROOF OF THEOREM 5
Specifically, since the total switching cost of SEEDS-UT is trivially upper-bounded by 3 [=]. to prove Theorem we focus on upper-bounding the loss regret RRSEDD (T) of SEEDS-UT, i.e.,
loss
SEEDS.UT
(T)
max E
qt
SEEDS-UT.P
9.4)
SEEDS UT, P
rEC(P)
E
SEEDS-UT,P
0" SEEDS-UT,
To upper-bound the loss regret, the main difficulties are that, due to the delayed switching and unknown transition function, the losses of SEEDS-UT the episodes any super-episode are cor- related and the true occupancy measure is unknown. As result, the existing analytical ideas in adversarial RL without switching costs (e.g., in Jin et al. (2020a)) and adversarial bandit learning with switching costs (e.g., in Shi et al. (2022) do apply here. To overcome these difficulties, our proof of Thheoremsjinve involves several key new components. For example, since SEEDS-UT col- lects samples from whole super-episode estimate the transition- funcctin set P, each state-action pair could be visited multiple times and such visitations are random. As result, the proof in Jin al. (2020a), which requires each state-action pair be visited at most once does apply di- rectly here. To resolve this difficulty, we construct special series based on the collected samples achieve an analyzable intermediate step for our proof of the final regret. Moreover, due to our new design of the estimated loss in (12), the concentration lemma for the loss based on the samples from only one episode Jin al. (2020a) does not apply. To resolve this difficulty, we establish super-episodic version of concentration in proof by bounding the second-order moment of the estimated loss.
Specifically, for each super-episode, we decompose the loss regret four parts that easier to be upper-bounded as follows,
SEEDS-UT,P (1)]
q" .11) into
SEEDS-UT.P q"d .4m)
9n)
STEDS-UT,P
SEEDS-UTE UT.P
%ul
STEDS-UT,P
[[u]
SEEDS-UT 1(u1)
SEEDS-UT. q"', ISEEDS
STEDD.
The first term on the right-hand hand--ide is mainly the difference between the true occupancy measure and the updated occupancy measure. Intuitively, according to Bernstein inequality (Maurer & Pontil
20

---

Published as a conference paper at ICLR 2023
2009) and standard stochastic RL analysis. SEEDS-UT UT estimates the true transition function P very well by using the funiitioonnutiiion setP in [4). Thus, based on the relation between the occupancy measure and the transition function in ( BEEDS-UT should estimate the true occupancy measure very well. Hence, the first term should be upper-bounded and controllable. The second and fourth terms on the right-hand-side depends the difference hetween the estimated loss and the true loss. According to Lemma 2] this gap should be controllable by tuning the parameter ", The third term similar the loss regret the case when the transition function is known. Thus, it can be upper- bounded similarly to our proof of Theorem B in Appendix D Finally, by combining all these gaps and the switching-e cost upper-bound 3- [ and tuning the parameters 17, and y in Algorithm we get the regret of SEEDS-UT in Theorem Please see the detailed proof below.
Proof. Step-1 (Bounding the switching costs): Since SEEDS-UT switches most once in each super-episode, the total switching cost of SEEDS-UT is upper-bounded by B- - In the following, we focus upper-bounding the loss regret RSSEEDD--UT(T))
Step-2 (Bounding the loss regret): We first show Lemma@below Lemma critical for Lemma to be true in this case with unknown transition function.
Lemma 4. For any episodes t and t2 if the updated occupancy measures the same, i.e., qe, (s',8,)) = qr, (s', qt (8,a) - qro (8, a) [s a) for any (8,a). where (s a) the true occupancy measure for the super-episode u.
s, a) for any (s', s, a), then the true occupancy measures are the same, i.e.,
The proof of Lemma 4 follows the conditions in (2-(5) Since SEEDS-UT applies the same occu- SSEDD-UT. for all episodes t of the same super-episode u, according to Lemma 4 SEEDD--U, of these episodes f are the same. Thus, similar to the case the true occupancy measure dt with known transition function, we can get an unknown-transition version of Lemma heme..herr... Thus,
pancy measure [1.]
E
SEEDS-UT, -9" --",,1)
E
SEEDS-UT.P [ml
-9"",
We drop the condition on SEEDS-UT in the expectation here and in the following when it is clear from the context.
According to the linearity of expectation, we can decompose the loss regret into four terms that are easier to bounded, i.e..
2
E
SEEDS-UT,P
9", (0",1,)
=
SEEDS-UT..
q"
a=1
U
E
E
91)
SEEDS-UT.
UT. [pl
SEEDS-UT.P
.44
SSEEDS-UT UT
==1
(ul
SEEDS-UT.P
SEEDDS-UT
/SEDD--L
Fiul P
(26)
Below, we focus on upper-boundine the four terms on the right-hand-sidd of 26 one-onn--eeooe one-by-one.
Step-2-i (Bounding the first term): Since 4ess, a) < 1 for state-action pairs (s, a), we have
liu (s, a) S T for all (s, a). Thus, we have
SPEDS-UT.P
STEDS-UT,P
.411 ST.
Σ aES.aEA
STEDS-UT.P
(8.
SLEDS-LT.P q() (s, a)
[uu)
The difference between the true occupancy measure and the updated occupancy measure the -ight-hand-side depends on how good the fonuttoonnuuctiinn set P in (4) is, and can be further focus bound-
upper-bounde bounded by using Bernstein inequality (Maurer & Pontil 2009). Below, ing this difference. We use (a)s) ) to denote the probability choosing action a at state s. Specif- ically, first, according the relation between the occupancy measure and the transition function in
21

---

Published as a conference paper at ICLR 2023
4 have that for any state-action pair (sh, and Sh x A visited at stage h,
h-1
(sp, an) = (s)
Σ
II
(s, (.)
where for simplicity, we drop the index é for the states & and actions a. Thus, the difference between the updated occupancy measure and the true occupancy measure can be upper-bounded as follows,
SETDS.UT,P (8h: un) (ul
SEEDS-UT,
(8h; ah)
=.SEDD-UT (anlss)
m
"[u]
h-1
h-1 - II 1(0)t1l9g, (27) j=0
Σ
II
SEEDS-UT (M)
(aylag)
EAA))
For the terms the bracket H. we have
h-1
II Pun(s5+1l)),,a) j-0
II P( ((5)+1ls),
h-1
h-1
h-1 k-1
h-1
Pmg - II
P(s a,) +
P(3y4als,, az) II f=k
5=0
km
1=0
k-1
h-1 II
(aa ax) - P(s |sk, ak)
II P(* 185, 0z)
Panl (13(3))1)))))
5=0
5=k
h-1
k-1 II
h-1
[lu] (8++1 18k, (k)
P(os+al3g, a4)
II (54(8)411)),ay,) j=k
(28)
k=
/=0
where
Eij (8k+ 188; (1)) =0 (1
P P(sk+1lsa ax) In TSA
In TSA
(29)
max { Muj ax)}. 1 max (s) ax)). shows how good SEEDS-UT estimates the true transition function, and the inequality is because of the empirical Bernstein inequality (Maurer Pontil, 2009) and Lemma 8 in Jin al. (2020a).
Applying (27 and (88) to SEEDS-UT, we have
SEEDS-UT,P (sh, (h)
[
SEEDS-UT,P
(sh, an)
(8k+1188 (x)
R=0
1-1
π [u]
SEEDS
(a*
II ==
SEEDS UT [o]]
((
h
m [4]
SBEDS-UT
(an (8))
SEEDS-UT
[u]
(ajls;) ((5+5)))(())1155)))))
-=++1
Σ
Elng ( ax)9 (
SEEDS-UT,
(8k, 94
SEEDS-UT.P (sh, ag (sx+1).
R=O 1E Ea
(30)
Similarly, we can show that
q M
SEEDS-UT,P
(sh, an (8k4t)))
[N/]
SEEDS-UT,P
(sh, (sh, an|sk+z)
Σ
Σ
é ( (,)
SEEDS-UT,P (s,, 0551411141100 19 (sh.anls5t1)
SEEDS-UT,P
1= 5 EE 15 ESJajEA
SEEDS-UT
(ap (8h)
Σ
1855
SEEDS-UT.P. 18 (31)
[M
22

---

Published as a conference paper at ICLR 2023
Combining (30)
and (31)
have
Σ
SEEDS.UT, (8h, an)
SEEDS- PT,,
(8h, ash)
4u
[u]
==l h=0 (#h.Rn)ESxxd XA
Σ
Σ
(sk 1|sk ax) 9x)
SEEDS-UT, P (sk: aR)
w=l 0=0 (s ESA X. K=0 1
SEEDS-UT, P
(sh. on sk+1))
[
H-1
+ΣΣ
Σ
Σ
i(ul (5)+1 as 9p
SEEDS.UT. (sk, ak)
h=0 (sh S x A (1) XSLXA
SFEDS-UT
1-k+1 (8941.8),0,))))))) (,)) (ag
Σ
Σ
(1)(8)t118)) (g)
SEEDS-UT. P (8 aylok+1)
[x]
(32)
Since
Σ
SEEDS UT,P
(9h.an/8441) 1 and Σ
Σ
SEEDS-UUT
(a% (sh) -
[4]
h=0 (s JES, XA
h=0 (5,,
S, from
(32). we have
H-1
Σ
Σ
qu
LT,
(sh, an) 9ul
SEEDS-UT,
(sh, an)
h=0
u H-1
Σ
Σ
E (8R+1 (8k, as (p))
SLEDS-UT, (8k, ax)
k=
(,S, XSEXA
4 H-1
+
ΣΣΣ
(sk+1155 as (9) (8)
Σ
SEEDS-UT, P
(skr ax)
== K= j=k+1
(#k+1
EE8 X
[ ( a,)4
SEEDSAUT,
(s), 1k- (33)
Let us focus on bounding the terms on the right-hand-side of 33 one-by-one. For the first term, we have
H
Σ
E/u] (8 0g )x). (d]
SEEDS.UT, P
(8k. ag)
a=1
k=0
XS
u H-1
P(s ax) In TSA
ΣΣ
Σ
[Nm]
SEEDS-UT, P
(sk. ax)
max { (ak ax)); :: 13
SEEDS.UT,
(sk, ax) In TSA
[N]
max (s au) (x)}.1}
# Ø-1
Sk41 In TSA max (Ni ax)).
00
ΣΣ
Σ
qul
SEEDS-UT,
(sk, ax))
K= (5L.0x)ESxx.A X.
SEEDS.UT, [(i
(Sk, ax) In TSA max { Niu (8k, ax)) 1)
where the equality is according to the definition of ETo (sx41 S8y, ax) in 29 and the inequality is according to Cauchy-Schwarz inequality. Note that the difficulty to further bound the above terms that each acteon pair could be visited multiple times in super-episode u. To this end, construct series to achieve analyzable intermediate step. Let first imagine there is
23

---

Published as a conference paper at ICLR 2023
sequence of numbers based on the samples that collected from each single episode. Then, use (sk, ag) to denote the number times visiting the state-action pair (#k ax) before episode t. Since Ne(ss. ax) is non-decreasing as t increases, i.e.,
((a-1))+1($3,44) as) S N(u ((u-1))+2(Kk,00 s.. S (Sk = (sk, ax),
(34)
have
SEEDS UT.P
(sk, .2)
SEEDS UT.P (sk. 0%)
SEEDS UT,P ($t. Og.
[]
5 S
max (sK 1}
/max
(Nur (8k, 0x) 1
max { (N 1)+ (sk, ax)), 1}
Now, let compare our regret bound before to intermediate step that is based on this series, i.e.,
H
ΣΣ
Σ
Σ
(8k+1188 as 911
SEEDS UT. (SK; (xx)
u=1
k=0 (#k+1) az (EL XSEA
U Ø-1
Sk+1 In
00
-
ΣΣΣ
Σ
Σ
SEEDS.UT, P
(8k. a2k
max (N, (x)).11
u=1 0=0
(e2.a))88 (1
SEEDS UT (sk, ax) In TSA
max (NN(sk,a))3
TSA
50
SKSK+ AT
TSA An
0
HS
(35)
8
Let us now consider the second term the right-hand-side of 33 which can be upper- bounded similarly to the steps above to bound the first term. First, according to the definition of (s (s, ax) in (29). we have this second term is upper-bounded by
H-1
P(sk+1 Sk,, ax In TSA max [Ni ax)),
5.0
ΣΣΣ
Σ
SEEDS UT,
(Sk, (R)
J=k+1 (B141.8 J.. xS
0,,
P(8jt1l88.00 az) In TSA max (1),()),))))11)
(sj.a In TSA
SEEDS-UT, [M]
ΣΣΣ
Σ
SHEDS-UT,P (u)
(8k aR)
Tal max
SHEDS-UT.P
(8j,a;)
k= j=k41 (ES XAXA max (N (Nug(sk, (5)
(N)
24

---

Published as a conference paper at ICLR 2023
Next, according to Cauchy-Schwand inequality, have the terms inside the big-O notation can be upper-bounded by
TSA
In
8
H-
H
U
SEEDS-UT, [N
(sk, 02. P(sk+11ss ax 91199m))
SEEDS-UT,
(gg.4)1
max (Sk ax)).1)
k=0
-=
M= (khaah)
(1)4):
Σ
qul
SEEDS-UT,P
(8k, a& P(8 188 (j) M1 max { Nu (8y) a3)).
SEEDS-UT.P
(8), (z),0)(8
(8k+1.52,0z)) ==1 (55+1183.05)
ΣΣΣ E
4 8-1
SEEDS-UT, 4/
(8k: a&)
[
SEEDS
(3,,
max (M) an) }}, 1]
max N (s)
j=b+1
(1511183.95)
Then, according to 34 we have that the terms under the v operator can be upper-bounded by
4
SEEDS UT,P (sk: ag P(sk+ 1hh, a& ax)4 4
SHEDS.UT, (8 Og (s2+1)
max [Ne(sk, (.)..
(s (u- 1) (1811.8))45)
MT
SEEDS-UT.P
(sk, .x) P( 18 ag [M)
SEEDS-UT, (sj, (51841))))
max (Nr (N((s),a)));1
==1 (8k-1 6 (x), (=- (u-11))++
(5:41)83:9))
and the second term in the bracket [-] can be upper-bounded by
Σ ΣEΣΣ Σ
" #-1
E
BT
SEEDS-UT,P
(Sk: ax) qul
SEEDS-UTE P.
(s),
max (N,(KK, ax)}.
max (N)(),,,)),,]
A= j= (#))))))))))
(M 1)++
(*.41.55.4))
Combining the above steps and according Lemma 10 in Jin et al. 2020a), we have that the second term on the right-hand-side of (33) can be upper-bounded by O ( ( S- In TSA
Therefore, with probability 1 by
8, the first term on the right-hand-side of (26) can be upper-bounded
TSA 8
TSA 12 In
o HS HSS
AT In
(36)
8
Step-2-ii (Bounding the second term): The second term on the right-hand-side of (66 can be further decomposed into two terms as follows,
u
EF
E
(
(ul
SEEDS-UT,P
SEEDS-UT
FINI,P]
E E
E
[(l
ST.
E
[SEEDS-UT] [ul
|
Fwi
1=1
E
Ex
E
Pal
ST.
E
SEEDS-UT
SSEEDS.UT) [u]
Flu,, Fluj,P]]
(37)
25

---

Published as a conference paper at ICLR 2023
Let us consider the two terms the right-hand-side. First, according to Lemma 2 have
E
[u]
SEEDS-UT.P
E
(
UT
Flu): p]]
4
%uu
SEEDS UT,
(3.0)
E
E
SEEDS UT.P (s, (s,
1
Flu), P
eES,uEA
Since (s, (s,aa S and (iny (3, 2 qiv
SEEDS-UT, (s, a), we have
SEEDS-UT,,
[SEEDS.UT] > Flud, P]]
E Fi
E
Mu) E [uu
E
(s,
9Mu
SEEDS-UT, (s. (s.
Flul, P
u=1
sES,aEA
< Ba
E
Σ
max Li + ( PEP
90l
SEEDS UT.
(s, a)
Flul, P
sES,aEA
SEEDS-UT, where the term max ( (8, - [n)
(s, a) on the right-hand-side represents how well
PEP
SEEDS-UT estimates the true occupancy measure using the transition-function set, and the term
y on the right-hand-side verifies that this part of the gap is controlled by the parameter ?. Then, according to the bound for the first term on the right-hand-side of (26). we have
SEEDS-UT,P
E (
Fln p]]
E
(c)
1=
TSA 8
0
HS
AT
+ TSS.
Second, according to Azuma's 's inequality, we have with probability 5,
Ex(ul
{
91)
SEEDS-UT,P
E
SEEDS-UT
(SEEDS.UT)
Flu). P|
[u]
T In
T1l
O
11
TT In
(38)
Therefore, with probability 1 5, the second term on the right-hand-side of 26 can be upper- bounded by
TSA o HS AT
+ TTSA+ H T Tn 1
(39)
8
Step-2-iii (Bounding the third term): Follow our proof for the case when the transition function is known, it is not hard to show that
14
SEEDS
9²
SEEDS UT
[u]
SEEDS UT, 4N
(8,a)
(SEEDS.UT UT
(s.a))²
Hnn(S)
n
aES
Let us focus on the first term the right-hand-side. Note that different from that in Jin et al. (2020a). the loss (SEEDS-UT (s, a) above is calculated based the samples from whole super-episode. Thus,
(M)
26

---

Published as a conference paper at ICLR 2023
each state-action pair could be visited multiple times. version of loss concentration as follows,
To this end, we provide super-episodic
2
SLEDS-UT,,
(s, a)
[SHEDS-UT (s,
)
- In
TH
H
[u]
27
Nm RES
SEEDS
T4(
Σ
(s,(a) (w)((s PEP
+
sES,aEA
max
In the following, show how to get this. First, since
J/ul
Σ (3, a)
iSEEDS-UT (s, (s)))
1 [(s.0) was visited in episodes (1. (s,0) super-opisode u)
j=1 (s,
0 [u] (s, a)
have
SEEDS UT,P (s,a)
[M]
SEEDS-UT,
(s, a)
(HEEDS-UT
[M]
(8, (s.a))
< 11
0 (8,a) a)
SEEDS-UT
(s, a)
(1)
SEEDS-UT
(s, a)
J/
(8,
1 {(s.a) was visited episodes 6 (s.aa) (s..))).... (s,a) of super-apisode u}
(8)
NT
(((8,a)
1 ((s,a) visited episode of super-episode u)-
2 (5,a)
1=(a 1)++1
Let us define
a(s,a)) A 4(s,a)1((s ((s.a) visited in episade episade
( (8, a)
Then, we have
ST
Σ
max Σ 27 (((,a)-
(s, a(s PEP
qul
< Hn H
aES
By combining all episodes in the same super-episode together, we have
SEEDS-UT
Σ 2x
Σ
((s,a)
(s, (5,()
H < H
N= sES
max PEP
By rearranging the terms, we have
Σ
Σ
(s)(s,
H <
ln
Σ
(ug (s) (s)(s,)) PEP
Piu
STEDS-UT
27
==1 sES,0EA
a=l eES
max
(),(), u=l aES
11
Σ
H
In
H
T
SAT
H - In + TSA.
H
27
0
2
g
7
27
Thus, we have
Σ
Σ
44
[c]
SEEDS-UT,
( (s,
SEEDDS-UT
[u]
(s, (SF)))-U(S,,O)
<
2x
H H
In + +TSA
==1
27

---

Published as a conference paper at ICLR 2023
Therefore, with probability 1 1-d 8, the third term the right-hand-siie hind-side of 26 can be upper-bounded by
y
H
T Hin(SA)
In
(40)
Step-2-iv (Bounding the fourth term): First, is not hard get that with probability 6,
u
SEEDS LT, (s,a)
SEEDS-UT (s,a) - 27
max q (s, (19(s,
[k]
(41)
PEP
Thus, have
0" Uni -41) -4u)=
Σ
Σ
9" (s,,)
Σ
Σ
9" (3,0))a((35
u=1 aES,aEA
sES, 8=1
Σ
9"t (8,0)
1
In
H
Σ
(s,a)
Σ
u
SEEDS-UT,
(8,a)
(8,
24
8
q (s,a)
P
aES,aEA
sES,aEA
u=1
max
PEP
u
Σ
Σ
(s,a))4a
==1
sES
SEEDS-UT,P (s,
H H
1n
Σ Σ 4=1 sES
(s,
411
-1
27
max q (8, PEP
H
H
< m 2-
(42)
8
and the switching-cost upper- bound [ [2], and tuning the parameters 7), and as in Algorithm we have that the regret of
Step-3 (Final step): Finally, by combining (36
39
SEEDS-UT is upper-bounded by O (31/3 (SA)
1/3 T223 (In TSA
with probability 1 1-6. 6.
28


Reviews:
[{"review_id": "wreBefU3S3-", "reviewer": "Reviewer_fZFZ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies adversarial reinforcement learning (RL) with switching costs in an episodic setting, where a constant switching cost is incurred whenever the agent deploys a different policy. The authors first show a $\\Omega(T^{2/3})$ regret lower bound, which generalizes the regret lower bound for adversarial Multi-Armed Bandits (MAB) with switching costs. Then, they propose two algorithms, SEEDS and SEEDS-UT, which can achieve provable regret guarantees. The first algorithm, SEEDS, requires the exact knowledge of transition probabilities and can achieve a regret that matches the regret lower bound. The second algorithm, SEEDS-UT, does not require the knowledge of transition probabilities. Its regret almost matches the lower bound with a gap of $H^{1/3}$, where $H$ is the length of each episode.", "summary_of_the_review": "In summary, this paper makes solid contribution to adversarial RL with switching costs by providing the first matching regret upper and lower bounds. Compared to the significance of the contributions, the weakness I mentioned are not major concerns. Therefore, I recommend for accept.\n\nSince the proofs are not carefully checked due to presentation issues and time limit, I prefer to choose a low confidence level.", "strength_and_weaknesses": "Strength:\n\nThis paper makes solid contribution to adversarial RL with switching costs. While the regret lower bound result is not very surprising because similar lower bounds have been shown for the special case of adversarial bandits, it is good to see that the regret upper bound can match the lower bound exactly in terms of $T, H, S, A, \\beta$ (episode number, episode length, state space size, action space size, and switching cost weight) when the transition probabilities are known. The authors also make their algorithm more practical by replacing the exact probability with an empirical estimator.\n\nThe paper is well-written and easy to follow. The authors add adequate discussions about the inspiration from previous works, and state the major technical difficulties clearly.\n\nWeakness:\n\n1.The proofs are not written clear enough for me to verify the results. For example, in the proof of Theorem 1 in Appendix A, what is the transition probability in this example? And what do you mean by the order of states?\n\n2.It is not clear whether the proposed algorithms can be implemented efficiently, because the authors do not elaborate on how to compute equation (10). I conjecture the complexity will be high because the set $C(P)$ can be complicated given that it needs to consider all possible policies. This issue might become worse when the transition probability is unknown, because the estimation of transition probability is keep changing.\n\n3.I feel the problem setting of adversarial RL with switching costs is closely related to online control, but that literature is not included in “Related Works”. Specifically, I feel the stronger regret performance metrics in that literature, like the dynamic regret or the adaptive regret, can work better than static regret in the non-static environments like adversarial RL. I recommend the authors to add a discussion in revision.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "rLgiMfPYi8y", "reviewer": "Reviewer_Vm2r", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work focused on adversarial MDPs with switching costs. The author proposed the SEEDs algorithms and provided a $O(T^{2/3})$ regret guarantee for both known and unknown transitions. In addition, the author also provided a theoretical guarantee for the lower regret bound, which suggests the proposed SEEDs algorithms are near-optimal on adversarial MDPs with switching costs.", "summary_of_the_review": "The author provides the first analyses on switching costs in adversarial RL, and proposed novel algorithms SEEDs with $O(T^{2/3})$ regret guarantee for both known and unknown transitions. In addition, the theoretical lower bound shows that the proposed SEEDs algorithms are near-optimal. Although some of the paper’s claims need to be clarified, they can be easily fixed with minor changes.", "strength_and_weaknesses": "Strength:\n\nThe author provides the first analyses on switching costs in adversarial RL, and proposed novel algorithms SEEDs with $O(T^{2/3})$ regret guarantee for both known and unknown transitions. In addition, the theoretical lower bound shows that the proposed SEEDs algorithms are near-optimal.\n\nWeakness:\n\nSome of the paper’s claims need to be clarified.\n\n1. The theoretical lower bound in Theorem 1 highly depends on the switching coefficient $\\beta$, and when $\\beta$ is small (e.g., $0$ or $O(1/T)$), the lower bound is smaller than $O(T^{2/3})$. Thus, it seems necessary to indicate the coefficient $\\beta$ in the abstract and introduction.\n\n2. The theoretical lower bound in Theorem 1 requires the number of episodes $T$ to be large enough. Otherwise, the lower bound is larger than $\\Omega(T)$.  \n\n3. For the related work, there exist different assumptions for the MDP. More specifically, the adversarial MDP assumes the state in each stage $h$ is non-overlap, and static MDP does not make this assumption. Therefore, it is better to indicate this difference for a fair comparison between related works.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "fHlRwDLSNXq", "reviewer": "Reviewer_TSyk", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of online reinforcement learning with adversarial losses and switching costs, where there is a cost for switching the policy during learning. The main result is an algorithm that achieves $\\tilde{O}(T^{2/3})$ regret and switching cost, for both the setting of known and unknown transitions. The paper also provides a matching $\\Omega(T^{2/3})$ lower bound.", "summary_of_the_review": "Overall, the paper obtains solid and interesting results for learning AMDPs with low switching cost, and is very clearly presented. However, I feel like technically it’s a bit incremental and unclear how the proof techniques could inspire future work.", "strength_and_weaknesses": "Strengths:\n * The topic of the paper should be of good interest to the community. The paper focuses on Adversarial MDPs (AMDPs), an MDP with fixed (unknown) transition and adversarial reward/loss functions, which can be viewed as a tractable adversarial analog of standard stochastic MDPs. Studying the switching cost problem has been done in both adversarial bandits, and stochastic MDPs. Thus a first result on switching cost in adversarial MDPs is definitely of interest.\n\n* The obtained result of $\\widetilde{O}(T^{2/3})$ regret and switching cost is solid, matches the result in adversarial bandits and slightly worse than in stochastic MDPs, which are expected. The result is established in both the known transition setting, and the unknown transition setting (which in my opinion is the main interesting one). \n\n* The paper is extremely clearly presented and quite easy to follow, with many intuitions discussed in detail and the related work adequately discussed. The paper could be a good reference point in the future for AMDPs and switching costs in adversarial settings. \n\n\nWeaknesses:\n\n* The main concern is that, at the heart, the technical contribution of this paper may be a bit incremental—The entire algorithm seems to be a direct combination of the standard way to do adversarial bandits with switching costs with $T^{2/3}$ regret using the “batched” EXP3 algorithm, and the algorithm of Jin et al. (2020a) to learn AMDPs with unknown transitions. I feel the combination is direct, because this “batched EXP3 algorithm” for bandits can be done with fixed, equally-sized batches, and thus when applied in AMDPs, across different states, the policy switches can be straightforwardly synced, as done in Algorithm 1 & 2.  \nIn particular, this is comparatively easier than logarithmic switching cost bounds in the stochastic MDP setting, where the low switching mechanism is an exponential grid depending over the visitation count, thus has to be done asynchronously for each state. \n\n* Related to the above concern, I feel like the presentation of many technical intuitions are slightly over-repetitive and perhaps a bit overclaiming. As an example, the “novel idea for estimating the loss” part on Page 6, the provided baseline is indeed not quite sensible and non-standard, as the losses change in each episode. The provided solution instead, in Eq(8), is just averaging of importance-weighted loss estimator in standard EXP3, and seems a natural/standard practice to me instead of a really novel idea. On this end, I think it’s probably good to shorten the discussions of these standard practices, and expand on the more nontrivial bits (for example, an explanation of how the $T^{2/3}$ regret is achievable in bandits for readers not familiar with that, and/or how that integrates with the AMDP algorithm of Jin et al. (2020a) to give the final result).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "XY_ZBlIgzh", "reviewer": "Reviewer_y6Wb", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work studies adversarial reinforcement learning with switching costs in the tabular setting. This work designs the super-episode containing $\\tau$ episodes and proposes an occupancy measure-based algorithm SEEDS. To control the switching cost, SEEDS uses the same policy in a super-episode and only updates the occupancy measure at the last of each super-episode. As the first step, this work proves the lower bound $\\tilde{\\Omega}((HSA)^{1/3}T^{2/3})$ in this setting. By carefully choosing $\\tau$ to balance the loss regret and the switching cost, this work proves SEEDS achieve $\\tilde{O}((HSA)^{1/3}T^{2/3})$ regret guarantee which matches the lower bound with the known transition. With the unknown transition, SEEDS-UT almost matches the lower bound within a factor of $\\tilde{O}(H^{1/3})$.", "summary_of_the_review": "This work proposes an occupancy measure-based algorithm SEEDS using super-episodes and (almost) matches the lower bound. However, the definition of the switching cost is not very reasonable. Furthermore, the proof of the lower bound is a bit confusing. The lower bound proved by the previous work can not be directly used in this work. Finally, the technique when proving the upper bound is almost the same as the standard proof process of online mirror descent and the proof process of the previous work [2].", "strength_and_weaknesses": "Strengths: \n\nThis work is the first to deal with the switching cost in adversarial RL. The algorithm in this paper (almost) matches the lower bound if the lower bound is correct. \n\nWeakness：\n\n1. The definition of the switching cost is unreasonable. In this paper, as long as the policy distribution changes slightly, there will be a switching cost. Imagine that if $\\pi_{t+1}$ and $\\pi_{t}$ are only slightly different (for example, a small KL divergence), we can fine-tune the policy. Then we can use offline evaluation methods such as importance sampling to evaluate the new policy, and there is no need to pay a high cost.\n\n2. The analysis of the lower bound in this paper is confusing. As stated in Weakness 1, the indicator function consider whether the policy distribution $\\pi_{t+1}$ and $\\pi_{t}$ are different, not $a_{t+ 1}$ and $a_{t}$ are the same. However, for adversarial bandits with switching costs, the indicator function considers whether $a_{t+1}$ and $a_{t}$ are different. These are two completely different measures, so the lower bound proved by Shi et al. (2022) cannot be used directly.\n\n3. I did not see too many difficulties in the regret analysis process of Theorem 4. It seems that the proof process of Theorem 4 is a standard online mirror descent (OMD) proof process, except that super-episodes replace episodes. It is worth describing the non-trivial tricks of the proof process.\n\n4. The core components of extending known transition to unknown transition are exactly the same as Jin et al. [2].\n\n[1] Shi, M., Lin, X., & Jiao, L. (2022, October). Power-of-2-arms for bandit learning with switching costs. In Proceedings of the Twenty-Third International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing (pp. 131-140).\n\n[2] Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning adversarial markov decision processes with bandit feedback and unknown transition. In International Conference on Machine Learning, pp. 4860–4869. PMLR, 2020.\n\nQuestion:\n\nQ1: Can you explain in detail why you can use the lower bound proved by Shi et al. (2022) directly?\n\nQ2: Can you propose a more reasonable way to measure the difference between the two policy distributions and prove an upper bound? \n\n----\n\nIt seems that the authors indeed work with deterministic policies. Then the setting and lower bound make sense to me. Though I still feel that the techniques are a bit incremental, it is not a fundamental issue. I would like to increase my score to 6.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%