The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition
Authors: Tiancheng Jin
Longbo Huang
Haipeng Luo
Venue: NeurIPS 2021 Oral (2021)
Keywords: reinforcement learning
online learning
best of both worlds

Abstract: We consider the best-of-both-worlds problem for learning an episodic Markov Decision Process through $T$ episodes, with the goal of achieving $\widetilde{\mathcal{O}}(\sqrt{T})$ regret when the losses are adversarial and simultaneously $\mathcal{O}(\log T)$ regret when the losses are (almost) stochastic. Recent work by [Jin and Luo, 2020]  achieves this goal when the fixed transition is known, and leaves the case of unknown transition as a major open question. In this work, we resolve this open problem by using the same Follow-the-Regularized-Leader (FTRL) framework together with a set of new techniques. Specifically, we first propose a loss-shifting trick in the FTRL analysis, which greatly simplifies the approach of [Jin and Luo, 2020] and already improves their results for the known transition case. Then, we extend this idea to the unknown transition case and develop a novel analysis which upper bounds the transition estimation error by the regret itself in the stochastic setting, a key property to ensure $\mathcal{O}(\log T)$ regret.

The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition
Tiancheng Jin University of Southern California tiancheng. jin@usc.edu
Longbo Huang Tsinghua University
longbohuang@tsinnguuaaccm edu. cn
Haipeng Luo
University of Southern California haipengl@usc.cm
Abstract
We consider the best-of-both-worldd problem for learning an episodic Markov Decision Process through T episodes, with the goal of achieving ((VT) regret when the losses are adversarial and simultaneously (ppolylog(T) regret when the losses are (almost) stochastic. Recent work by [Jin and Luo, 2020] achieves this goal when the fixed transition known, and leaves the case of unknown transition as major open question. In this work, we resolve this open problem by using the (FTRL) framework together with a set first propose loss- loss-shifting trick in the FTRL
same Follow-the-Rese theeRRegllrizzdd-Leea techniques. Specifically, analysis, which greatly simplifics the approach of [Jin and Luo, 2020] and already improves their results for the known transition case. Then, we extend this idea to the unknown transition case and develop a novel analysis which upper bounds the transition estimation error by (a fraction of) the regret itself in the stochastic setting, a key property to ensure O(polylog(T) regret.
Introduction
We study the problem of learning finite-horizon Markov Decision Processes (MDPs) with unknown transition through T episodes. In each episode, the learner starts from fixed initial state and repeats the following for fixed number of steps: select an available action, incur some loss, and transit to the next state according to fixed but unknown transition function. The goal of the learner is to minimize her regret, which is the difference between her total loss and that the optimal stationary policy in hindsight.
When the losses are stochastically generated, [Simchowitz and Jamieson, 2019, Yang et al., 2021] show that Olog 7) regret is achievable (ignoring dependence on some gap-dependent quantities for simplicity). On the other hand, even when the losses are adversarially generated, [Rosenberg and Mansour, 2019a, Jin et al., 2020] show that ((VT) regret is achievable! Given that the existing algorithms for these question of whether one can achieve the best of both worlds, that is, enjoying Jogarihhgii regret in the stochastic world while simultaneously ensuring some worst-case robustness in the adversarial world. Taking inspiration from the bandit literature and using the classic Follow-the-regularize Leader (FTRL) framework with a novel regularizer, they successfully achieved this goal, albeit under a strong restriction that the transition has to be known ahead of time. Since it is highly unclear how
worlds are substantially different, Jin and Luo [2020] asked the natural
'Throughout the paper, we use Ö(-) to hide polylogarithmic terms.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

to ensure that the transition estimation error is only ((polylog(T)), extending their results to the unknown transition case highly challenging and was left as a key open question.
In this work, we resolve this open question and propose the first algorithm with such a best-of-both- worlds guarantee under unknown transition. Specifically, our algorithm enjoys (VVT) regret always, and simultaneously (log² T') regret if the losses are i..d. samples of a fixed distribution. More generally, our polylogarithmic regret holds under a general condition similar to that of [Jin and Luo, 2020], which requires neither independence nor identical distributions. For example, it covers the corrupted i..dd setting where algorithm achieves Ö(VC) regret with C T being the total amount of corruption.
Techniques Our results are achieved via three new techniques. First, we propose a new loss-shifting trick for the FTRL analysis when applied MDPs. While similar ideas have been used for the special case of multi-armes bandits (e.g.. [Wei and Luo, 2018, Zimmert and Seldin, 2019, Lee et al., 2020b, Zimmert and Seldin, 2021]), its extension to MDPs has eluded researchers, which is also the reason why [Jin and Luo, 2020] resorts to a different approach with a highly complex analysis involving analyzing the inverse of the non-diagonal Hessian of complicated regularizer. Instead, inspired by the well-known performance difference lemma, we design key shifting function in the FTRL analysis, which helps reduce the variance of the stability term and eventually leads to an adaptive bound with a certain self- self-bounding property known to be useful for the stochastic world. To better illustrate this idea, we use the known transition case as a warm-up example in Section 3, and show that the simple Tsallis entropy regularizer (with diagonal Hessian) is already enough to guarantee. This not only greatly simplifies the approach of Jin and Luo [2020] (paving the way for extension to unknown transition). but also leads to bounds with better dependence on some parameters, which on its own is a notable result already.
achieve the best-of-
Our second technique is a new framework to deal with unknown transition under adversarial losses, which is important for incorporating the loss-shifting trick mentioned above. Specifically, when the transition is unknown, prior works [Rosenberg and Mansour, 2019a,b, Jin et al., 2020, Lee et al., 2020a] perform FTRL over the set of all plausible occupancy measures according to confident set of the true transition, which can be seen as form of optimism encouraging exploration. Since our loss-shifting trick requires fixed transition, we propose to move the optimism from the decision set of FTRL to the losses fed to FTRL. More specifically, we perform FTRL over the empirical transition some doubling epoch schedule, and add (negative) bonuses to the loss functions so that the algorithm is optimistic and never underestimates the quality of policy, an idea often used in the stochastic setting (e.g., [Azar et al., 2017]). See Section 4 for the details of our algorithm.
Finally, we develop a new analysis to show that the transition estimation error of our algorithm is only polylogarithmic in T. overcoming the most critical obstacle in achieving An important aspect of our analysis is to make use of the amount of underestimation of the optimal policy, a term that often ignored since it is nonpositive for optimistic algorithms. We do so by proposing a novel decomposition of the regret inspired by the work of Simchowitz and Jamieson [2019], and show that in the stochastic world, every term in this decomposition can be bounded by a fraction of the regret itself plus some polylogarithmic terms, which is enough to conclude the final polylogarithmic regret bound. See Section for formal summary of this idea.
Related work For earlier results in each of the two worlds, we refer the readers to the systematic surveys in [Simchowitz and Jamieson, 2019, Yang et al., 2021, Jin et al., 2020]. The work closest to ours is [Jin and Luo, 2020] which assumes known transition, and as mentioned, we strictly improve their bounds and more importantly extend their results to the unknown transition case.
Two recent works [Lykouris al., 2021, Chen et al., 2021] also consider the corrupted stochastic setting, where both the losses and the transition function can be corrupted by a total amount of C. This is more general than our results since we assume a fixed transition and only allow the losses to be corrupted. On the other hand, their bounds are worse than ours when specified to our setting [Lykouris et al., 2021] ensures a sup-deppndentt polylogarithmic regret bound of OCC T + C²). while [Chen et al., 2021] achieves Olog' C') but with a potentially larger gap-dependent quantity. Therefore, neither result provides meaningful guarantee in the adversarial world when C. T. while our algorithm always ensures a robustness guarantee with (VVT) regret. Their algorithms are also very different from ours and are not based on FTRL.
2

---

The question of achieving best-of- both worlds guarantees for the special case of multi-armed bandits was first proposed in [Bubeck and Slivkins, 2012]. Since then, many improvements using different approaches have been established over the years [Seldin and Slivkins, 2014, Auer and Chiang, 201 6, Seldin and Lugosi, 2017, Wei and Luo, 2018, Lykouris et al., 2018, Gupta et al., 2019, Zimmert et al., 2019, Zimmert and Seldin, 2021, Lee et al., 2021]. One notable and perhaps surprising approach is to use the FTRL framework, originally designed only for the adversarial settings but later found to be able to automatically adapt to the stochastic settings long certain regularizers are applied [Wei and Luo, 2018, Zimmert et al., 2019, Zimmert and Seldin, 2021J. Our approach falls into this category, and our regularizer design is also based these prior works. As mentioned, however, obtaining our results requires the new loss-shifting technique as well as the novel analysis on controlling the estimation error, both of which are critical to address the extra challenges presented in MDPs.
2 Preliminaries
We consider the problem of learning episodic MDP through T episodes, where the MDP is formally defined by tuple action set, I. being the horizon, l S x A [0, 1] being the loss function of episode t, and P: x A x S - [0, 1] being the transition function so that P(s'|s, a) is the probability of moving to state s' after executing action a at state 8.
(())) with S being a finite state set, A being a finite
Without loss of generality [Jin al., 2020J, the MDP is assumed to have a layer structure, that is, the state set S is partitioned into L + 1 subsets So, SI..... Sy. such that the state transition is only possible from one layer to the next layer (in other words, P(s"ls, a) must be zero unless s S₃ and s' E S for some & E {o..... L - 1)). Moreover, So contains so only (the initial state), and St contains sr only (the terminal state). We use k(s) to represent the layer which state s belongs.
Ahead of time, the environment decides an MDP with P and {4)T unknown to the learner. The interaction proceeds through T episodes. In episode t, the learner selects a stochastic policy Te : 55x x A + [0, 1] where Fy (als) denotes the probability of taking action a at state s.? Starting from the initial state =6 = 80. the learner then repeatedly selects an action aj drawn from Te (- +|$ ), suffers loss (s ).),, and transits to the next state * E Sk+1 for k- = 0, .g.... , L, 1, until reaching the terminal state S1- At the end of the episode, the learner receives some feedback on the loss function 4. In the full-information setting, the learner observes the entire loss function &, while in the more challenging bandit feedback setting, the learner only observes the losses of those visited state-action pairs, that is, (e(s) ab)....,
With slight abuse of notation, we denote the expected loss of policy π for episode by (<(T)) E
---1 ===o Le(sk, ax) P. π. where the trajectory {(sk, a& ) is the generated by executing policy π under transition P. The regret of the learner against some policy æ is then defined as Σ (mx)) (TT) and we denote by one of the optimal policies in hindsight such that Regy-( (T) max, Regy (Tr)
Regr (T)
Adversarial world versus stochastic world We consider two different setups depending on how the loss functions f,....fy, by are generated. In the adversarial world, the environment decides the loss functions arbitrarily with knowledge of the learner's ss algorithm (but not her randomness). this case, the goal is to minimize the regret against the best policy Regr(#), with the best existing upper bound being O(L|S) bound being (<LV|S/|A// [Jin et al., 2018] (for both -nllrmmfoonttoon and bandit feedback).
[Rosenberg and Mansour, 2019a, Jin al., 2020] and the best lower
In the stochastic world, following [Jin and Luo, 2020] (which generalizes the bandit case of [Zimmert and Seldin, 2019, 2021]), we assume that the loss functions satisfy the following condition: there exists deterministic policy x² : + A, gap function A : S A - R4, and constant C' > 0 such that
Regr (TT* N E
Σ Σ ((s) t=l St88 (s)
C,
"Note that Te(-) is not meaningful since action will be taken at sL- For conciseness, however, we usually define functions over instead (S) (#t)) A.
3

---

where (r(s.a) a) is the probability of the learer visiting (s, a) in episode t. This general condition covers the heavily-studied i.i.d. setting where fi...., E are i.i.d. samples of a fixed distribution, in which case C = O, x' is simply the optimal policy, and A is the gap function with respect to the optimal Q-function. More generally, the condition also covers the corrupted i.i.d. setting with C' being the total amount of corruption. We refer the readers to [Jin and Luo, 2020] for detailed explanation. In this stochastic world, our goal is to minimize regret against π², that is, Regr (m²).² With unknown transition, this general setup has not been studied before, but for specific examples
such the i..d. setting, regret bounds of order O log where AMIN m (s) A A(s, (s, a) have been derived [Simchowitz and Jamieson, 2019, Yang al., 2021].
A
Occupancy measure and FTRL To solve this problem with online learning techniques, com- monly used concept is the occupancy measure. Specifically, an occupancy measure of S x A + [0. 1] associated with a policy π and a transition function P such that q ( a) equals the proba- bility of visiting state-action pair (s, a) under the given policy π and transition P. Our earlier notation q: in Eq. (1) is thus simply shorthand for q ( Moreover, by definition, (T)) can be rewritten as Pa (i) by naturally treating qº Pox and & as vectors in R|S|X|A|, and thus the regret Regr (TT) can
be written as E E (a: -f=x, (.)). connecting the problem to online linear optimization.
Given a transition function P, we denote by S(P) = { : x is a stochastic policy] } the set of all valid occupancy measures associated with the transition P. It is known that S2()) is a simple polytope with ([S][AA]) constraints [Zimin and Neu, 2013]. When
unknown, our algorithm uses an estimated transition P as proxy and searches for a "good" occupancy measure within S2(P). More specifically, this is done by the classic Follow-the-Ren ReghRReglarized--ee Leader (FTRL) framework which solves the following at the beginning of episode t:
argmin (EO(P)
Σ &r T<E
+ (e()),
where ?, is some estimator for &, and Φe is some regularizer. The learner's policy ni is then defined through Te (als)) x (s. Note that we have q P. but not necessarily @ qe unless p P.
3 Warm-up for Known Transition: A New Loss-shifting Technique
One of the key components of our approach is new loss-shifting technique for analyzing FTRL applied to MDPs. To illustrate the key idea in a clean manner, in this section we focus on the known transition setting with bandit feedback, the same setting studied by Jin and Luo [2020]. As we will show, our method not only improves their bounds, but also significantly simplifies the analysis, which paves the way for extending the result the unknown transition setting studied in following sections.
First note that when known, one can simply take P (so that q. qe) and use the standard aeportaacc--eighhte estimator Ê, (s, a) = l, (s, a)ll, (s, a)/q, (s, a) in the FTRL framework Eq. (2), where (s, is if (s, a) is visited in episode т, and O otherwise. It remains to determine the regularizer d.. While there are many choices of dh leading to vT-regret in the adversarial world, obtaining logarithmic regret in the stochastic world requires some special property of the regularizer. Specifically, generalizing the idea of [Zimmert and Seldin, 2019] for multi-armed bandits, [Jin and Luo, 2020] shows that it suffices to find o, such that the following adaptive regret bound holds
a)))
Regr (it S
ΣΣ Σ
S azf (x)
which then automatically implies logarithmic regret under Eq. (1). This is because Eq. (3) admits a self-bounding property under Eq. (1) one can bound the right-hand side of Eq. (3) follows using
'Some works (such as |in and Luo, 2020) still consider minimizing (+t) as the goal in this case. More discussions are deferred to the last paragraph of Section 4.

---

AM-GM inequality (for any 2 > 0), which can then be related to the regret itself using Eq. (1):
E
Σ E
T
(r(s, a (s,
2 21A
Reg (
log
2z
2z
(ss,a)
#İAL (8)
Sf8 (s)
(4)
Rearranging and picking the optimal 2 then shows a logarithmic bound for Regy (ft) (see Section of Jin and Luo [2020] for detailed discussions).
To achieve Eq. (3), a natural candidate of Φe would be a direct generalization of the Tsallis-entropy regularizer of [Zimmert and Seldin, 2019], which takes the form di (q) = 1 Σ.,a Vg a) with
" = 1/Vł. However, Jin and Luo [2020] argued that it highly unclear how to achieve Eq. (3) with this natural candidate, and instead, inspired by [Zimmert et al., 2019] they ended up using a different regularizer with a complicated non-diagonal Hessian achieve Eq. (3), which makes the analysis extremely complex since it requires analyzing the inverse of this non-diagonal Hessian.
Our first key contribution is to show that this natural and simple candidate is in fact (almost) enough to achieve Eq. (3) after all. To show this, we propose a new a loss-shifting technique in the analysis. Similar techniques have been used for multi-armed bandits, but the extension MDPs is much less clear. Specifically, observe that for any shifting function OT S x A + (a, (r) is independent of y for any q E S2(P), we have
R such that the value of
q:
argmin gEO(P)
4. E. 2 + (r(9)) TKE
argmin gEN(P)
q, E(e + )r(g).
(5)
TCt
Therefore, can pretend that the leamnr is performing FTRL over the shifted loss sequence (2, + 9+ hrcc (even when gr is unknown the learner). The advantage of analyzing FTRL over this shifted loss sequence is usually that it helps reduce the variance of the loss functions.
For multi-armed bandits, prior works (Wei and Luo, 2018, Zimmert and Seldin, 2019] pick 9r to be constant such as the negative loss of the learner in episode r. For MDPs, however, this is not enough
to show Eq. (3), as already pointed out by Jin and Luo [2020] (which is also the reason why they resorted to a different approach). Instead, we propose the following shifting function:
g- (s, (s, - (s() (s, V(s,a) S A,
(6)
where @ and V- are the state-action and state value functions with respect to the transition P. the loss function l,, and the policy Tr, that is: (s, = (=, + Byr-P((ss.a)) (s') and (s) = Ea,,, ( a)] (with V=(sL) = 0). This indeed satisfies the invariant condition since using well-known performance difference lemma one can show (g. 9+) Vy (so) for any E Q(P) (Lemma 1.I. With this shifting function, the learner is equivalently running FTRL over the "advantage" functions (Q,
(s, a) V, (s) is often called the advantage at (s, a) in the literature).
More importantly, it turns out that when sceing FTRL in this way, a standard analysis with some direct calculation already shows Eq. (3). One caveat that since Q- a) (s(s) can potentially have large magnitude, we also need to stabilize the algorithm by adding a small amount of the so-called barrier regularizer to the Tsallis entropy regularizer, an idea that has appeared in several prior works (see [Jin and Luo, 2020] and references therein). We defer all details including the concrete algorithm and analysis to Appendix A, and show the final results below.
Theorem 3.1. When P is known, Algorithm (with parameter y 1) ensures the optimal regret Regr (it) = -O [|ST|A(TT the adversarial world, and simultaneously Regr(m") S (egr(() = O(U + VUC) where U- = [og]
Aans + T.A 1
EFft, Eajr((s)
log T in the stochastic world. [[2.0)
Our bound for the stochastic world is even better than [Jin and Luo, 2020] (their U has an extra |A| factor in the first term and an extra L factor in the second term). By setting the parameter differently, one can also improve L to 133, matching the best existing result from [Simchowitz and Jamieson, 2019] for the i.i.d. setting with C = 0 (this would worsen the adversarial bound though). Besides this improvement, we emphasize again that the most important achievement of this approach is that significantly simplifies the analysis, making the extension to the unknown transition setting possible.
5

---

Main Algorithms and Results
We are now ready to introduce our main algorithms and results for the unknown transition case, with either full-information or bandit feedback. The complete pseudocode is shown in Algorithm 1, which is built with two main components: a new framework to deal with unknown transitions and adversarial losses (important for incorporating our loss-shifting technique), and special regularizers for FTRL. We explain these two components in detail below.
A new framework for unknown transitions and adversarial losses When the transition un- known, common practice (which we also follow) to maintain an empirical transition along with a shrinking confidence set of the true transition, usually updated in some doubling epoch schedule. More specifically, new epoch is started whenever the total number of visits some acte-action pair is doubled (compared to the beginning of this epoch), thus resulting in at most O (|S)] A log T) epochs. We denote by i(t) the epoch index to which episode t belongs. At the beginning of each epoch i, we calculate the empirical transition P. (fixed through this epoch) as:
(,( m,(s, s')), V(s,a,s') S& x A Sk+1, K O.... mi(s,a) a)
where ms a) and my(s, s') are the total number of visits to (s, a) and (s, a, s') respectively prior to epoch i. The confidence set of the true transition for this epoch is then defined as
P. {P: P(s')s, a) Pi(s'(s.a) a) s Bi(s,, v(s 8') E Sy x A x Sk+1, k < 1).
where B, is Bernstein-style confidence width (taken from Jin et al. [2020]):
P((s'ss, In (,,5,a)
TIS
14
TIS
B₁(s, a, min 2
(8)
3m a)
for some confidence parameter 5 E (0, 1). As [Jin et al., 2020, Lemma 2] shows, the true transition P is contained in the confidence set P, for all epoch i with probably at least 46.
When dealing with adversarial losses, prior works [Rosenberg and Mansour, 201 b,,,, Jin et al., 2020, Lee al., 2020a] perform FTRL (or similar algorithm called Online Mirror Descent) over the set of all plausible occupancy measures (2(;)) = {q E s2(P)= P P;} during epoch i, which can be seen as form of optimism and encourages exploration. This framework, however, does not allow us to apply the loss-shifting trick discussed in Section 3 indeed, our key shifting function Eq. (6) is defined in terms of some fixed transition P, and the required invariant condition on (g. gr) only holds for E (P) but not & E ()(P.).
Inspired by this observation, we propose the following new approach. First, to directly fix the issue mentioned above, for each epoch we run new instance of FTRL simply over S2(P.). This is implemented by keeping track of the epoch starting time t, and only using the cumulative loss Ex & in the FTRL update (Eq, (10)). Therefore, in each epoch, are pretending to deal with known transition problem, making the same loss-shifting technique discussed Section applicable.
However, this removes the critical optimism in the algorithm and does not admit enough exploration. To fix this, our second modification is to feed FTRL with optimistic losses constructed by adding some (negative) bonus term, an idea often used in the stochastic setting. More specifically, we subtract L. (s, a) from the loss for each (s, a) pair, where B; (s, a) = min {1, Ev B; a, s') }
see Eq. (11). In the full-information setting, this means using (s a) = ( - L- B, a). In the bandit setting, note that the importance-weiggtee estimator discussed in Section is no longer applicable since the transition is unknown (making also unknown), and [Jin et al., 2020] proposes (s..)) instead, where L,ss, a) is again the indicator of whether (s, a) is visited during episode t, and (s, a) is the so-called upper occupancy measure defined as
to use vs(s,a)
uz(s, a) max q Pime (s.
(9)
PEP,0)
'When mi(s, a) we simply let P.(-ls, a) be arbitrary distribution.

---

Algorithm/ frest-of-both-weer for Episodic MDPs with Unknown Transition
Input: confidence parameter 8.
Initialize: epoch index = and epoch starting time t =
Initialize: v(s, a, s'), set counters my (s, a) mi (s, a, s') mo a) (s a, s') 0. Initialize: empirical transition Pi and confidence width B₁ based on Eq. (7) and Eq. (8).
for ( 1,..., do Let di be Eq. (13) for full-information feedback or Eq. (12) for bandit feedback, and compute
i-1
q
argmin
q.
Σ
&
+
+
(10)
gEA P.)
T=
Compute policy ne from q: such that IT (als)) x q: (s, a).
Execute policy and obtain trajectory (s a for & 0, ,,..,,-11 Construct adjusted loss estimator E2 such that
a(( - L. Bi(s,a), ((s.a)) L. Bi(s,a), u.(o,a)
for full- mall-information feedback, for bandit feedback,
(((
(11)
where (s(s = min {1,Es Bi(s, 8')} [e(s,a) = KH3,; (8, a) = (6 ag)). and Ut is the upper occupancy measure defined in Eq. (9).
Increment counters: for each i < L, (s og. sh+1) $ 1, (s ap) $ 1.a
3k, (s a 2 max(1, 2m;-1 ) then epoch starting time = -+++
b entering a new epoch
Increment epoch index = and
Initialize new counters: V(s, a, s'), m: a, s') = m (s, a, s"), my a) = m (s, a). Update empirical transition P. and confidence width B; based on Eq. (7) and Eq. (8).
and can be efficiently computed via the COMP-UOB procedure of [Jin al., 2020], Our final adjusted loss estimator is then (e a) (.s.a)))) I. Bi as) In our analysis, we show that these (x(sa))
adjusted loss estimators indeed make sure that we only underestimate the loss of each policy, which encourages exploration.
With this new framework, it is not difficult to show -rerrett in the adversarial world using many standard choices of the regularizer di (which recovers the results of [Rosenberg and Mansour, 201 9a, Jin et al., 2020] with different approach). To further ensure polylogarithmic regret in the stochastic world, however, we need some carefully designed regularizers discussed next.
Special regularizers for FTRL Due the new structure of our algorithm which uses a fixed transition P; during epoch i, the design of the regularizers is basically the same as in the known transition case. Specifically, in the bandit case, we use the same Tsallis entropy regularizer:
(1(9)
1 Σ E Tht
Va(s,a)
In Σ
(12)
((s.a)
SF8L aEA
5t52 aEA
where 7j = 1/- G0) and / 1281 discussed in Section 3, the small amount of log-barrier in the second part of Eq. (12) is used to stabilize the algorithm, similarly to [Jin and Luo, 2020].
In the full-information case, while we can still use Eq. (12) since the bandit setting is only more difficult, this leads to extra dependence on some parameters. Instead, we use the following Shannon entropy regularizer:
Φc(g)
1 - Wt
Σ
Σ g(s a).
(13)
8$51 a
'If Ebea (s, b) = O, we let me to be the uniform distribution.
We use E y shorthand for the increment operation +- y.
7

---

Although this is standard choice for the full-information setting, the tuning of the learning rate na requires some careful thoughts. the special case of MDPs with one layer (known as the expert problem [Freund and Schapire, 1997]), it has been shown that choosing 7) to be of order 1/v/ ensures best-of best-of-both-world both-worlds [Mourtada and Gaïffas, 2019, Amir et al., 2020]. However, in our general case, due to the use of the loss-shifting trick, we need to use the following data data-dependent tuning (with denoting i(t) for simplicity): nt
L In In([S]IA[)
V
where
647. In([)]|4)+ H
t-1 Mr Σ min Σ Σ ((, ΣΣ (s, (Qr(0,a)- ( 8588 AEA
8781 asA
and similar to the discussion in Section 3, Q, and V. are the state-action and state value functions with respect to the transition P., the adjusted loss function Ê,, and the policy Ty, that is: Qr a) (s,, a) aa)+EE.- P. [V= (s)) and (s) (-1x-(-1s)) (s. a)] (with V=(s)) 0). This particular tuning makes sure that FTRL enjoys some adaptive regret bound with a self-bounding property akin
to Eq. (3), which is again the key ensure polylogarithmie regret in the stochastic world. This
concludes all the algorithm design; see Algorithm again for the complete pseudocode.
4.1 Main Best-of-both-worlds Results
We now present our main best-of-bothhworlds results. As mentioned, proving -Tergettt in the adversarial world is relatively straightforward. However, proving polylogarithmic regret bounds for the stochastic world is much more challenging due to the transition estimation error, which is usually of order VT. Fortunately, we are able to develop estimation related terms by the regret itself, establishing a belfdiounding property again. We defer the proof sketch Section 5, and state the main results in the following theorems."
analysis that upper bounds some transition
Theorem 4.1.1. In the full coll-information setting, Algorithm with d = 7o guarantees Regr(ft Ô (AATT always, and simultaneously Regr(T") (U VUC) under Condition (1), Es4sr Eapr((s)
where U = -0 (111))= log'
L9 L9 ((s,a)
Ams
Theorem 4.1.2. In the bandit feedback setting, Algorithm 1 with ô Tx guarantees (egr(f)
δ ( (AAI)SS/IA/TT always, and simultaneousty Regr(=*) = O (U + +UC) under Con-
dition (1), where U = o (198PP+2118P1))) log" T + ESSSEE Eapr.
(19))) log T
Aui
A(s.a)
While our bounds have some extra dependence on the parameters L, |S), and |A| compared to the best existing bounds in each of the two worlds, emphasize that our algorithm is the first to be able to adapt to these two worlds simultaneously and achieve Ō(vT) and O(polylog(T)) regret respectively. In fact, with some extra twists (such as treating differently the state-action pairs that are visited often enough and those that are not), we can improve the dependence on these parameters, but we omit these details since they make the algorithms much more complicated.
Also, while [Jin and Luo, 2020] is able to obtain (log T) regret for the stronger benchmark Regr(*t under Condition (1) and known transition (same as our Theorem 3.1), here we only achieve so for Regz (IT*) due to some technical difficulty (see Section 5). However, recall that for the most interesting i.i.d. case, one simply has Regr(T") Regy (+) as discussed in Section 2; even for the corrupted i..dd case, since Regr(*) (#) is at most C' Regr( our algorithms ensure (eg O(U + C)
(note VUC < S + C). Therefore, our bounds on Regr(T") are meaningful and strong.
5 Analysis Sketch
In this section, we provide a proof sketch for the full-information setting (which is simpler but enough to illustrate our key ideas). The complete proofs can be found in Appendix B (full-ifformation) and
For simplicity, for bounds in the stochastic world, we omit some ((1) terms that are independent of the gap function, but they can be found in the full proof.
8

---

Appendix C (bandit). We start with the following straightforward regret decomposition:
T V (so)
T
Regy (T) = E
(so) (10))+ +
V (so) - VI (so) +
V (so) - V2" (so)
(14)
ERR1
ESTREG
for an arbitrary benchmark v, where Vi2 is the state value function associated with the true transition P. the true loss l,, and policy и,, while V7TT the state value function associated with the empirical transition Pa(e), the adjusted loss l, and policy л. Define the corresponding state-action value functions OT and Q similarly (our earlier notations V3 and Q: are thus shorthands for Vi and QT:) )
In the adversarial world, we bound each of the three terms in Eq. (14) as follows (see Proposition B.1 for details). First, E [ERR]] measures the estimation error of the loss of the learner's policy Ti, which can be bounded by (L|) v (A(T) following the analysis of Jin al. [2020]. Second, as mentioned, adjusted losses are optimistic in the sense that it underestimates the loss of all policies (with high probability), making E [ERRœ] an O (1) term only. Finally, EE [ESTREG] is the regret measured with Pite) and e,, which is controlled by the FTRL procedure and of order (ISSAA))))) Put together, this proves the (ILISV/AATT) regret shown in Theorem 1.1.1.
In the stochastic world, we fix the benchmark = T=. To obtain polylogarithmic regret, an important observation is that we now have make use of the potentially negative term ERR₂ instead of simply bounding it by O (1) (in expectation). Specifically, inspired by [Simchowitz and Jamieson, 2019], we propose a new decomposition on E and ERR₂ jointly as follows (see Appendix D.1): ERR1 + ERR₂ = ERRSUB + ERROPT - OCCDIFF + BIAS. Here,
ERRSUB = ΣT= Eofol (s (c(s, a) ET (s, measures some estimation error con- tributed by the suboptimal actions, where ET (s) le(s, a) + E.- [V] (s')
QT' (s, a) a "surplus" function term taken from [Simchowitz and Jamieson, 2019]);
ERROPT Σt", Exple Ea-r((s) (9o(s, a) - of (s, a)) ET (s, a) measures some estimation error contributed by the optimal action, where g (s, a) is the probability visiting a trajectory of the form (so, x* (50)), ($1, x (si)), (sk(s) R²" (54)))....(((())1))))
(*(((s))-)) (s, a) when executing policy
Te;
OcCDIFF = Et= ss Ener (ge(s, a) - (s, @5 as - Di (s) measures the
occupancy measure difference between q: and q.:
BIAS = ET Enpor Esyorss) of (s,a) (V) (s) V, (s) measures some estimation error for n*, which, similar to ERR2, is of order (1) in expectation due to optimism.
The next key step is to show that the terms ERRSUB, ERROPT, OccDIFF, and ESTREG can all be upper bounded by some quantities that admit a certain self-bounding property similarly to the right-hand side of Eq. (3). We identify four such quantities and present them using functions G1, G2. Gy, and G4, whose definitions are deferred to Appendix D.2 due to space limit. Combining these bounds for each term, we obtain the following important lemma.
Lemma 5.1. With 7o. Algorithm ensures that Reg is at most 0(44)$"111111 In2 plus:
E O
Gr (I. (I+1S) + Go (1.1))
Go G3 In (n) +G In
from ERRSUR
from ERROPT
from OCCDIFF
from ESTREG
Finally, as mentioned, each of the G1, Gg Gg. and G2 functions can be shown to admit the following self-bounding property, such that similarly what we argue in Eq. (4), picking the optimal values of and 3 and rearranging leads to the polylogarithmic regret bound shown in Theorem 1.1.1.
Lemma 5.2 belff-ooundig property). Under Condition (1), we have for any a, 8 E (0, 1).
E [J) S a -Regg
( Eofer Eafer x(b.))

---

B E [G2 8 (Regy( (T))+ + + 1
E (J) - (a + 3) (Reg, (a*) + c) + 0 Eopor Enpores)
1988
A(s.a) + 40
11 Amm
E (J) < 3 (
+
We emphasize again that the proposed joint decomposition on ERR1 + ERRg plays a crucial rule in this analysis and addresses the key challenge how to bound the transition estimation error by something better than vT. We also point out that in this analysis, only ESTREG is related to the FTRL procedure, while the other three terms are purely based on our new framework to handle unknown transition. In fact, the reason that can only derive polylog(T) bound on Regr(**) but not directly on Regr(() is also due to these three terms they can be related to the right- hand side of Condition (1) only when use the benchmark
म. This is not the case for ESTREG, which the reason why Jin and Luo [2020] are able to derive a bound on Regy(f) (+t directly when the transition is known. Whether this issue can be addressed is left future direction.
x' but not when
6 Conclusions
In this work, we propose an algorithm for learning episodic MDPs which achieves favorable regret guarantees simultaneously in the stochastic and adversarial worlds with unknown transition. We start from the known transition setting and propose loss-shifting trick for FTRL applied to MDPs, which simplifies the method of Jin and Luo [2020] and improves their results. Then, design new framework to extend our known transition algorithm to the unknown transition case, which is critical for the application of the loss-shifting trick. Finally, we develop novel analysis which carefully upper bounds the transition estimation error by (a fraction of) the regret itself plus a gap-dependent poly-logarithmic term in the stochastic setting, resulting our final best-of-both-wordde result.
Besides the open questions discussed earlier (such as improving our bounds Theorem 4.1.1 and Theorem 4.1.2), one other key future direction is remove the assumption that there exists unique optimal action for each state, which appears to be challenging despite the recent progress for the bandit case [Ito, 2021], since the occupancy measure computed from Eq. (10) has a very complicated structure. Another interesting direction would be to extend the sub-optimality gap function to other fine-grained gap functions, such as that of Dann et al. [2021].
Acknowledgments and Disclosure of Funding
HL supported by NSF Award IIS- 1943607 and a Google Faculty Research Award. LH is supported in part by the Technology and Innovation Major Project of the Ministry of Science and Technology of China under Grants 2020AAA010844 and 2020AAA0108403. We thank Max Simchowitz for many helpful discussions, and the anonymous reviewers for their valuable feedback and suggestions.
References
Idan Amir, Idan Attias, Tomer Koren, Roi Livni, and Yishay Mansour. Prediction with corrupted expert advice. Advances in Neural Information Processing Systems, 2020.
Peter Auer and Chao-Kai Chiang. An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits. In Proceedings of the Annual Conference on Learning Theory, 2016.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In Proceedings of the International Conference Machine Learning, 2017.
Sébastien Bubeck and Aleksandrs Slivkins. The best of both worlds: Stochastic and adversarial bandits. In Proceedings of the 23rd Annual Conference on Learning Theory, 2012.
Yifang Chen, Simon S Du, and Kevin Jamieson. Improved corruption robust algorithms for episodic reinforcement learning. Proceedings of the International Conference on Machine Learning, 2021.
10

---

Christoph Dann, Teodor V Marinov, Mehryar Mohri, and Julian Zimmert. Beyond gaps: Improved instance-dependent regret bounds for episodic reinforcement learning. arXiv preprint 10t.0/200..0264,, 2021.
Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119-139, 1997.
Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Proceedings of the Annual Conference on Learning Theory, 2019.
Shinji Ito. Parameter-free multi-armed bandit algorithms with hybrid data-dependent regret bounds. In Conference on Learning Theory, pages 1552-25833 PMLR, 2021.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is q-learning provably efficient? In Proceedings of the International Conference on Neural Information Processing Systems, pages 4868 -4788,87,, 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, 2020.
Tiancheng Jin and Haipeng Luo. Simultaneousty learning stochastic and adversarial episodic mdps with known transition. Advances in Neural Information Processing Systems, 2020.
Sham Machandranath Kakade. On the sample complexity of reinforcement learning. PhD thesis, University College London, 2003.
Chung-Wei Lee, Haipeng Luo, Chen- Wei, and Mengxiao Zhang. Bias no more: high- high-probability data-dependent regret bounds for adversarial bandits and mdps. Advances in Neural Information Processing Systems, 2020a.
Chung-Was Wei Lee, Haipeng Luo, and Mengxiao Zhang. A closer look at small-loss bounds for bandits with graph feedback. In Conference on Learning Theory, 2020b.
Chung- Wei Lee, Haipeng Luo, Chen-Yu Wei, Mengxiao Zhang, and Xiaojin Zhang, Achieving near instance-optimality and Manimax-optimman in stochastic and adversarial linear bandits simultaneously. Proceedings of the International Conference on Machine Learning, 2021.
Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme. Stochastic bandits robust adversarial corruptions. In Proceedings of the Anmual ACM SIGACT Symposium on Theory of Computing, 2018.
Thodoris Lykouris, Max Simchowitz, Alex Slivkins, and Wen Sun. Cormptton-robust exploration in episodic reinforcement learning. In Conference on Learning Theory, 2021.
Jaouad Mourtada and Stéphane Gaiffas. On the optimality the hedge algorithm in the stochastic regime. Journal of Machine Learning Research, 20:1-28, 2019.
Aviv Rosenberg and Yishay Mansour. Online convex optimization in adversarial Markov decision processes. In Proceedings of the International Conference on Machine Learning, 2019a.
Aviv Rosenberg and Yishay Mansour. Online stochastic shortest path with bandit feedback and unknown transition function. In Advances in Neural Information Processing Systems, 2019b.
Yevgeny Seldin and Gábor Lugosi. An improved parametrization and analysis of the exp3++ algorithm for stochastic and adversarial bandits. Proceedings of the Annual Conference on Learning Theory, 2017.
Yevgeny Seldin and Aleksandrs Slivkins. One practical algorithm for both stochastic and adversarial bandits. In Proceedings the International Conference on Machine Learning, 2014.
Max Simchowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds for tabular MDPs. In Advances in Neural Information Processing Systems, pages 1151-1160, 2019.
11

---

Chen- Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Proceedings of the Annual Conference On Learning Theory. 2018.
Kunhe Yang, Lin Yang, and Simon Du. Q-learning with logarithmic regret. International Conference Artificial Intelligence and Statistics, pages 1576-1584. PMLR, 2021.
Alexander Zimin and Gergely Neu. Online learning in episodic markovian decision processes by relative entropy policy search. In Proceedings of the International Conference on Neural Information Processing Systems, 2013.
Julian Zimmert and Yevgeny Seldin. An optimal algorithm for stochastic and adversarial bandits. In The International Conference on Artificial Intelligence and Statistics, 2019.
Julian Zimmert and Yevgeny Seldin. Tsallis-inf inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28):1-49, 2021.
Julian Zimmert, Haipeng Luo, and Chen-Yu Yu Wei. Beating stochastic and adversarial semi-bandits optimally and simultaneously. In Proceedings of the International Conference on Machine Learning, 2019.
12


Reviews:
[{"review_id": "yAwNJR81gBI", "reviewer": "Reviewer_o6kk", "summary": "This paper presents an algorithm for episodic Markov decision processes with unknown losses and transition kernel. The paper proves that this algorithm achieves order sqrt(T) regret bounds when losses are chosen by an oblivious adversary and order log^2*(T) when losses are stochastic. This is the first algorithm to achieve such best of both works regret guarantees when transitions are unknown. \nThe key technical innovations are (1) the use of loss-shifting technique in the MDP setting, (2) running FTRL in phases where the empirical transition model is fixed per phase, (3) new biased loss estimators that combine importance weighting using upper occupancy measures with   additional bonus terms to promote exploration and (4) carefully tuned regularizers for FTRL.", "questions": "", "limitations": "", "rating": 8, "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": "Significance: Best of both worlds results are desirable and have received a good amount of attention in the RL / bandit theory community. This paper significantly advances the state of the art in this area by showing the first such results in MDPs with unknown transitions. Besides the actual regret bound, I think the proof techniques in this paper will be useful in other settings as well. I particularly liked the simpler analysis using shifted losses compared to prior works.\n\nClarity: The paper is very well written, illustrating the main technical challenges and clearly explaining how they were overcome. I think the paper does a particularly good job at sketching the intuition in the main paper while providing the verbose arguments with all details in the appendix.\n\nOriginality: Many of the technologies used in this paper have been used elsewhere before, including loss shifting, using phases where the empirical model is kept fixed and adding a reward bias to account for uncertainty in transition estimates (e.g. in UCBVI algorithms). I still think that the combination and adaptation of these tools to the setting addressed here is technically highly nontrivial and sufficiently novel.\n\nQuality: I checked several technical lemmas in the proofs and did not find any issues. The main arguments also make sense to me, but I did not go through all lemmas in the appendix carefully.\n\nMinor comments and typos:\n- One log(T) factor seems to come from the fact that the algorithm runs log(T) independent instances of FTRL. If one could avoid that, would that allow us to achieve a log(T) instead of log^2(T) bound or are there other places that contribute the additional log-factor?\n- I understand that it is not the main focus of the paper to push the best results for either case, adversarial or stochastic, but I wonder whether the techniques developed in this paper can shed light on the additional sqrt(S) / S factor in the presented upper-bounds compared to the lower bounds when transitions are stochastic & unknown?\n- Line 342: challenging -> challenges", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I am not aware of any potential negative societal impact of this work and the authors have sufficiently discussed the technical limitations of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "rV6G9vMVeiF", "reviewer": "Reviewer_WK45", "summary": "The authors consider the problem of stochastic and adversarial episodic MDPs with unknown transition, is an extension of the work of Jin and Luo (2020), with unknown transitions rather than known ones. \n\nThey propose an algorithm which is part of the FTRL framework, where they use some existing tools, such as the self-bounding technique as well as new tools such as the Loss-Shifting Technique.\n\nThey outperform the previous results from Jin and Luo (2020) for the problem of stochastic and adversarial episodic MDPs with known transition with a simpler analysis, and they derive new bounds in the setting with unknown transitions.\n\nBoth Full information and Bandit feedback are coinsidered.\n", "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": "This work is an improvement compared to previous works on several fronts. First, in the setting with fixed transitions, this new algorithm and its analysis are both more efficient and simpler to study. \nIn the setting with unknown transition, the results are novel. \n\nOverall, the framework provided is very complete, as they study episodic MDPs in a Best of Both world setting, both with known and unknown transitions and both with bandit and full information feedback.\n \nThe algorithm proposed is part of the FTRL framework, where they use some  existing tools, such as the self-bounding technique as well as new tools such as the Loss-Shifting Technique, which is efficient and easier to analyse than the previously existing algorithm from Jin and Luo (2020).\n\nThe paper is quite well written, and the proofs are extensively detailled in the appendix. The amount of material presented is important for the length of the paper. \n A conclusion that discuss possible extensions would be a useful addition.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are supposedly discussed in section 1, but they could be clearer and extended. In particular, a clearer description of the suboptimality gaps of the provided bounds would be beneficial.\n\nThe societal impact is not super relevant for this type of theoretical problems, and in general achieving more robust and polyvalent algorithms has a positive impact. \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "OqWpQNy_VCI", "reviewer": "Reviewer_yvyL", "summary": "This paper studies the problem of sequential learning in episodic MDP with full and bandit feedback and unknown dynamics of the MDP. The paper provides the first algorithm with provable performance guarantees, that simultaneously ensure polylogarithmic regret in the stochastic setting and the \\sqrt(T) order regret bound in the adversarial setting. This is the first result of this kind, previous works only answer this question for a setting when the transitions are known. The paper proposes running the FTRL-type algorithm over the set of all valid occupancy measures from the estimated transition matrix. It ensures the exploration by subtracting the exploration bonus from the loss and it gives the importance weighted loss estimator by dividing the observed loss by the upper bound on the occupancy measure. The algorithm is computationally efficient. The secondary contribution of the paper is a more simple analysis of the variation of the same problem where the transitions are known. \n\n\n", "questions": "", "limitations": "", "rating": 7, "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": "The paper is very well-written and studies an interesting problem. It provides new techniques:\n\n- The choice and use of a shifting function. It is a very nice solution. \n\n- The idea to move the use of exploration bonus from the search of the occupancy measure for the confidence set of transitions\nto the alternative solution of substructing the exploration bonus from the loss. This trick looks potentially useful in other applications. \n\nRemarks:\n\n- The statement of lines 167 - 170 and equation (7), and later reasoning on the same topic at lines 295-300 suffer from lack of clarity. Reference to a more detailed explanation in the appendix is needed and also reformulate a thought more clearly. \n\n- (1) comes initially from best of both worlds analysis for bandits.\n\n- The message of lines 231-234 is not very clear. The shifting function as well can be computed using \\mathcal{P}_i.\n\n- It is not very clear why the best of both world problem in the full information setting requires special attention. The stochastic regime with full information is not very challenging. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "15"}, "extra_text": {}}, {"review_id": "N9DaAR8N31I", "reviewer": "Reviewer_VSsV", "summary": "This paper studies the \"best of both worlds\" algorithm for episodic MDPs with unknown transition with stochastic and adversarial rewards, hence the paper resolves the open question in (Jin and Luo 2020). While the adversarial case alone with unknown transition is closed in (Jin et al. 2020), the paper shows that a simple variation of FTRL with a loss-shifting trick, optimism-based exploration bonus and restarting can also achieve poly-logarithmic regret in stochastic environments assuming the constant minimum-gap $\\Delta_{min} = \\min_{s, a \\neq \\pi^*(s)} V^*(s) - Q^*(s,a)$. The proposed algorithm and associated analysis enjoy more simplified analysis compared to the previous work in (Jin and Luo 2020). The simplified analysis is adapted from (Jin and Luo 2020) and (Simchowitz and Jamieson 2019). Main results are the the regret bound of $O(\\sqrt{T})$ under adversarial setting, and $O(log^2 (T))$ under stochastic setting.", "questions": "", "limitations": "", "rating": 7, "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": "In some sense, the contribution may be seen as a minor improvement from (Jin and Luo 2020) for known transition case. In fact, maybe one can first run reward-free exploration schemes to learn transition kernels and then execute any known algorithms for best-of-both-worlds. It would result in O(T^{2/3})-regret nevertheless. Hence getting $O(\\sqrt{T})$ and $O(polylog(T))$ regrets in adversarial and stochastic cases respectively does not seem to be so trivial.\n \nOn the other hand, analysis seems not particularly novel but a variation of FTRL method (e.g., Jin et al. 2020) and logarithmic-regret for MDPs (e.g., Simchowitz and Jamieson 2019). Nevertheless, they are well-adapted to a challenging problem of achieving best of both worlds with unknown transition kernels. \n\nOverall the paper is well-written and easy to follow. Comparisons to previous work are well discussed whenever needed. Main results and analysis are well-presented, hence I recommend the acceptance for this paper. \n\n\n\nThere are some points I want to be clarified.\n\n- In Section 3, the main idea seems to add additional term (loss-shifting?) $g_\\tau$. However, I do not see what conceptually plays the role of $g_\\tau$ in Algorithm 1. (Eq (11) is, in my interpretation, simply an adjusted loss with standard exploration bonus). Could you be more specific about the connection?\n\n- Line 231-234: I do not understand what it does mean by \"This framework, however, does not allow the loss-shifting trick discussed in Section 3\" (or why it has to be).\n\n- Line 293-294 \"In fact, ... complicated\": at least, could you explain which improvement you have or can be made? \n\n\n\nI also raise some other questions on the analysis\n\n- Could you be more specific on your technical novelty? In which part of the analysis is different from (Jin et al. 2020) for adversarial case? \n\n- How is the regret decomposition for the stochastic case different from (Simchowitz and Jamieson 2019)? (or are they the same?)\n\n- Line 345-346 \"In fact, the reason ... terms\":  I don't understand what you mean by $Reg_T(\\pi^o)$ cannot be directly bounded - isn't your theorem bounds it by $O(\\sqrt{T})$? \n\n\n\n\n\nMinor Comments\n\n- Line 259: \"in the bandit case\" -> do you mean in the bandit-feedback case?\n\n- Line 137: $\\Delta(s,a)$ is not defined before used here.\n\n- Line 177: \"this natural and simple candidate\" - do you mean the one used in (Zimmert and Seldin 2019)?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are not separately addressed in the main paper. Here are a few of my questions:\n\n- Do you think the regret bound can be improved to $O(log T)$ in the stochastic cases in (Simchowitz and Jamieson 2019)?\n\n- Can you improve the regret bound by a factor of $|S|$ in the adversarial case?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper has been very well-received by the reviewers, who all appreciated the significance of the contribution and the high quality of both the writing and the technical content. This is an excellent paper that clearly deserves to be published at the conference.
Decision: Accept (Oral)