The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition

Abstract:
We consider the best-of-both-worlds problem for learning an episodic Markov Decision Process through T episodes, with the goal of achieving Õ( √ T ) regret when the losses are adversarial and simultaneously O(polylog(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 (a fraction of) the regret itself in the stochastic setting, a key property to ensure O(polylog(T )) regret.

text: √ T ) regret
when the losses are adversarial and simultaneously O(polylog(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 (a fraction of) the regret itself in the stochastic setting, a key property to ensure O(polylog(T )) regret.

heading: 1 Introduction
text: 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 a fixed initial state and repeats the following for a fixed number of steps: select an available action, incur some loss, and transit to the next state according to a 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 of the optimal stationary policy in hindsight.
When the losses are stochastically generated, [Simchowitz and Jamieson, 2019, Yang et al., 2021] show that O(log T ) 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 Õ( √ T ) regret is achievable.1 Given that the existing algorithms for these two worlds are substantially different, Jin and Luo [2020] asked the natural question of whether one can achieve the best of both worlds, that is, enjoying (poly)logarithmic 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-regularizedLeader (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
1Throughout the paper, we use Õ(·) to hide polylogarithmic terms.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
to ensure that the transition estimation error is only O(polylog(T )), extending their results to the unknown transition case is 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-bothworlds guarantee under unknown transition. Specifically, our algorithm enjoys Õ( √ T ) regret always, and simultaneously O(log2 T ) regret if the losses are i.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.i.d. setting where our algorithm achieves Õ( √ C) 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 to MDPs. While similar ideas have been used for the special case of multi-armed 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 a complicated regularizer. Instead, inspired by the well-known performance difference lemma, we design a 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-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 a diagonal Hessian) is already enough to achieve the best-of-both-worlds 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.
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 a confident set of the true transition, which can be seen as a form of optimism encouraging exploration. Since our loss-shifting trick requires a 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 in some doubling epoch schedule, and add (negative) bonuses to the loss functions so that the algorithm is optimistic and never underestimates the quality of a 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 best-of-both-worlds. An important aspect of our analysis is to make use of the amount of underestimation of the optimal policy, a term that is 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 5 for a 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 et 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 gap-dependent polylogarithmic regret bound of O(C log3 T + C2), while [Chen et al., 2021] achievesO(log3 T +C) but with a potentially larger gap-dependent quantity. Therefore, neither result provides a meaningful guarantee in the adversarial world when C = T , while our algorithm always ensures a robustness guarantee with Õ( √ T ) regret. Their algorithms are also very different from ours and are not based on FTRL.
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, 2016, 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 as long as certain regularizers are applied [Wei and Luo, 2018, Zimmert et al., 2019, Zimmert and Seldin, 2021]. Our approach falls into this category, and our regularizer design is also based on 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.

heading: 2 Preliminaries
text: We consider the problem of learning an episodic MDP through T episodes, where the MDP is formally defined by a tuple (S,A,L, P, {`t}Tt=1) with S being a finite state set, A being a finite action set, L being the horizon, `t : S × A → [0, 1] being the loss function of episode t, and P : S ×A× 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 s.
Without loss of generality [Jin et al., 2020], the MDP is assumed to have a layer structure, that is, the state set S is partitioned into L+ 1 subsets S0, S1, . . . , SL such that the state transition is only possible from one layer to the next layer (in other words, P (s′|s, a) must be zero unless s ∈ Sk and s′ ∈ Sk+1 for some k ∈ {0, . . . , L− 1}). Moreover, S0 contains s0 only (the initial state), and SL contains sL only (the terminal state). We use k(s) to represent the layer to which state s belongs.
Ahead of time, the environment decides an MDP with P and {`t}Tt=1 unknown to the learner. The interaction proceeds through T episodes. In episode t, the learner selects a stochastic policy πt : S×A→ [0, 1] where πt(a|s) denotes the probability of taking action a at state s.2 Starting from the initial state st0 = s0, the learner then repeatedly selects an action a t k drawn from πt (· |stk ), suffers loss `t(stk, a t k), and transits to the next state s t k+1 ∈ Sk+1 for k = 0, . . . , L− 1, until reaching the terminal state sL. At the end of the episode, the learner receives some feedback on the loss function `t. In the full-information setting, the learner observes the entire loss function `t, while in the more challenging bandit feedback setting, the learner only observes the losses of those visited state-action pairs, that is, `t(st0, a t 0), . . . , `t(s t L−1, a t L−1). With slight abuse of notation, we denote the expected loss of a policy π for episode t by `t(π) = E [∑L−1 k=0 `t(sk, ak) ∣∣∣P, π], where the trajectory {(sk, ak)}k=0,...,L−1 is the generated by executing policy π under transition P . The regret of the learner against some policy π is then defined as RegT (π) = E [∑T t=1 `t(πt)− `t(π) ] , and we denote by π̊ one of the optimal policies in hindsight
such that RegT (̊π) = maxπ RegT (π).
Adversarial world versus stochastic world We consider two different setups depending on how the loss functions `1, . . . , `T are generated. In the adversarial world, the environment decides the loss functions arbitrarily with knowledge of the learner’s algorithm (but not her randomness). In this case, the goal is to minimize the regret against the best policy RegT (̊π), with the best existing upper bound being Õ(L|S| √ |A|T ) [Rosenberg and Mansour, 2019a, Jin et al., 2020] and the best lower
bound being Ω(L √ |S||A|T ) [Jin et al., 2018] (for both full-information and bandit feedback).
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 a deterministic policy π? : S → A, a gap function ∆ : S × A → R+ and a constant C > 0 such that
RegT (π ?) ≥ E  T∑ t=1 ∑ s6=sL ∑ a6=π?(s) qt(s, a)∆(s, a) − C, (1) 2Note that πt(·|sL) is not meaningful since no action will be taken at sL. For conciseness, however, we
usually define functions over S ×A instead of (S \ {sL})×A.
where qt(s, a) is the probability of the learner visiting (s, a) in episode t. This general condition covers the heavily-studied i.i.d. setting where `1, . . . , `T are i.i.d. samples of a fixed distribution, in which case C = 0, π? is simply the optimal policy, and ∆ 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, RegT (π
?).3 With unknown transition, this general setup has not been studied before, but for specific examples such as the i.i.d. setting, regret bounds of order O( log T∆MIN ) where ∆MIN = mins,a6=π?(s) ∆(s, a) have been derived [Simchowitz and Jamieson, 2019, Yang et al., 2021].
Occupancy measure and FTRL To solve this problem with online learning techniques, a commonly used concept is the occupancy measure. Specifically, an occupancy measure qP̄ ,π : S ×A→ [0, 1] associated with a policy π and a transition function P̄ is such that qP̄ ,π(s, a) equals the probability of visiting state-action pair (s, a) under the given policy π and transition P̄ . Our earlier notation qt in Eq. (1) is thus simply a shorthand for qP,πt . Moreover, by definition, `t(π) can be rewritten as〈 qP,π, `t 〉 by naturally treating qP,π and `t as vectors in R|S|×|A|, and thus the regret RegT (π) can
be written as E [∑T
t=1
〈 qt − qP,π, `t 〉] , connecting the problem to online linear optimization.
Given a transition function P̄ , we denote by Ω(P̄ ) = { qP̄ ,π : π is a stochastic policy } the set of
all valid occupancy measures associated with the transition P̄ . It is known that Ω(P̄ ) is a simple polytope with O(|S||A|) constraints [Zimin and Neu, 2013]. When P is unknown, our algorithm uses an estimated transition P̄ as a proxy and searches for a “good” occupancy measure within Ω(P̄ ). More specifically, this is done by the classic Follow-the-Regularized-Leader (FTRL) framework which solves the following at the beginning of episode t:
q̂t = argmin q∈Ω(P̄ ) 〈 q, ∑ τ<t ̂̀ τ 〉 + φt(q), (2)
where ̂̀τ is some estimator for `τ and φt is some regularizer. The learner’s policy πt is then defined through πt(a|s) ∝ q̂t(s, a). Note that we have q̂t = qP̄ ,πt but not necessarily q̂t = qt unless P̄ = P .

heading: 3 Warm-up for Known Transition: A New Loss-shifting Technique
text: One of the key components of our approach is a 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 to the unknown transition setting studied in following sections.
First note that when P is known, one can simply take P̄ = P (so that q̂t = qt) and use the standard importance-weighted estimator ̂̀τ (s, a) = `τ (s, a)Iτ (s, a)/qτ (s, a) in the FTRL framework Eq. (2), where Iτ (s, a) is 1 if (s, a) is visited in episode τ , and 0 otherwise. It remains to determine the regularizer φt. While there are many choices of φt leading to √ T -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 φt such that the following adaptive regret bound holds
RegT (̊π) . E  T∑ t=1 ∑ s6=sL ∑ a6=π?(s) √ qt(s, a) t  , (3) 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) as follows using
3Some works (such as [Jin and Luo, 2020]) still consider minimizing RegT (̊π) as the goal in this case. More discussions are deferred to the last paragraph of Section 4.1.
AM-GM inequality (for any z > 0), which can then be related to the regret itself using Eq. (1):
E  T∑ t=1 ∑ s6=sL ∑ a6=π?(s) qt(s, a)∆(s, a) 2z +
z
2t∆(s, a)  ≤ RegT (̊π) + C 2z + z ∑ s6=sL ∑ a6=π?(s) log T ∆(s, a) .
(4) Rearranging and picking the optimal z then shows a logarithmic bound for RegT (̊π) (see Section 2 of Jin and Luo [2020] for detailed discussions).
To achieve Eq. (3), a natural candidate of φt would be a direct generalization of the Tsallis-entropy regularizer of [Zimmert and Seldin, 2019], which takes the form φt(q) = − 1ηt ∑ s,a √ q(s, a) with
ηt = 1/ √ t. However, Jin and Luo [2020] argued that it is 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 to 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 to MDPs is much less clear. Specifically, observe that for any shifting function gτ : S × A → R such that the value of 〈q, gτ 〉 is independent of q for any q ∈ Ω(P̄ ), we have
q̂t = argmin q∈Ω(P̄ ) 〈 q, ∑ τ<t ̂̀ τ 〉 + φt(q) = argmin q∈Ω(P̄ ) 〈 q, ∑ τ<t (̂̀τ + gτ )〉+ φt(q). (5) Therefore, we can pretend that the learner is performing FTRL over the shifted loss sequence {̂̀τ + gτ}τ<t (even when gτ is unknown to 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 gτ to be a constant such as the negative loss of the learner in episode τ . 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, a) = Q̂τ (s, a)− V̂τ (s)− ̂̀τ (s, a), ∀(s, a) ∈ S ×A, (6) where Q̂τ and V̂τ are the state-action and state value functions with respect to the transition P̄ , the loss function ̂̀τ , and the policy πτ , that is: Q̂τ (s, a) = ̂̀τ (s, a) + Es′∼P̄ (·|s,a)[V̂τ (s′)] and V̂τ (s) = Ea∼πτ (·|s)[Q̂τ (s, a)] (with V̂τ (sL) = 0). This indeed satisfies the invariant condition since using a well-known performance difference lemma one can show 〈q, gτ 〉 = −V̂τ (s0) for any q ∈ Ω(P̄ ) (Lemma A.1.1). 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 seeing FTRL in this way, a standard analysis with some direct calculation already shows Eq. (3). One caveat is that since Q̂τ (s, a)− V̂τ (s) can potentially have a large magnitude, we also need to stabilize the algorithm by adding a small amount of the so-called log-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 3 (with parameter γ = 1) ensures the optimal regret RegT (̊π) = O( √ L|S||A|T ) in the adversarial world, and simultaneously RegT (π?) ≤ RegT (̊π) = O(U + √ UC) where U = L|S| log T∆MIN + L 4 ∑ s6=sL ∑ a6=π?(s) log T ∆(s,a) in the stochastic world.
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 L4 to L3, 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 it significantly simplifies the analysis, making the extension to the unknown transition setting possible.

heading: 4 Main Algorithms and Results
text: 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 is unknown, a common practice (which we also follow) is to maintain an empirical transition along with a shrinking confidence set of the true transition, usually updated in some doubling epoch schedule. More specifically, a new epoch is started whenever the total number of visits to some state-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̄i (fixed through this epoch) as:
P̄i(s ′|s, a) = mi(s, a, s
′)
mi(s, a) , ∀(s, a, s′) ∈ Sk ×A× Sk+1, k = 0, . . . L− 1, (7)
where mi(s, a) and mi(s, a, s′) are the total number of visits to (s, a) and (s, a, s′) respectively prior to epoch i.4 The confidence set of the true transition for this epoch is then defined as
Pi = { P̂ : ∣∣∣P̂ (s′|s, a)− P̄i(s′|s, a)∣∣∣ ≤ Bi(s, a, s′), ∀(s, a, s′) ∈ Sk ×A× Sk+1, k < L} , where Bi is Bernstein-style confidence width (taken from Jin et al. [2020]):
Bi(s, a, s ′) = min 2 √√√√ P̄i(s′|s, a) ln(T |S||A|δ ) mi(s, a) + 14 ln ( T |S||A| δ ) 3mi(s, a) , 1  (8) for some confidence parameter δ ∈ (0, 1). As [Jin et al., 2020, Lemma 2] shows, the true transition P is contained in the confidence set Pi for all epoch i with probably at least 1− 4δ. When dealing with adversarial losses, prior works [Rosenberg and Mansour, 2019a,b, Jin et al., 2020, Lee et al., 2020a] perform FTRL (or a similar algorithm called Online Mirror Descent) over the set of all plausible occupancy measures Ω(Pi) = {q ∈ Ω(P̂ ) : P̂ ∈ Pi} during epoch i, which can be seen as a 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 〈q, gτ 〉 only holds for q ∈ Ω(P̄ ) but not q ∈ Ω(Pi). Inspired by this observation, we propose the following new approach. First, to directly fix the issue mentioned above, for each epoch i, we run a new instance of FTRL simply over Ω(P̄i). This is implemented by keeping track of the epoch starting time ti and only using the cumulative loss∑t−1 τ=ti ̂̀ τ in the FTRL update (Eq. (10)). Therefore, in each epoch, we are pretending to deal with a known transition problem, making the same loss-shifting technique discussed in Section 3 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 ·Bi(s, a) from the loss for each (s, a) pair, where Bi(s, a) = min { 1, ∑ s′∈Sk(s)+1 Bi(s, a, s ′) } ;
see Eq. (11). In the full-information setting, this means using ̂̀t(s, a) = `t(s, a)− L ·Bi(s, a). In the bandit setting, note that the importance-weighted estimator discussed in Section 3 is no longer applicable since the transition is unknown (making qt also unknown), and [Jin et al., 2020] proposes to use `t(s,a)·It(s,a)ut(s,a) instead, where It(s, a) is again the indicator of whether (s, a) is visited during episode t, and ut(s, a) is the so-called upper occupancy measure defined as
ut(s, a) = max P̂∈Pi(t)
qP̂ ,πt(s, a) (9)
4When mi(s, a) = 0, we simply let P̄i(·|s, a) be an arbitrary distribution.
Algorithm 1 Best-of-both-worlds for Episodic MDPs with Unknown Transition Input: confidence parameter δ. Initialize: epoch index i = 1 and epoch starting time ti = 1. Initialize: ∀(s, a, s′), set counters m1(s, a) = m1(s, a, s′) = m0(s, a) = m0(s, a, s′) = 0. Initialize: empirical transition P̄1 and confidence width B1 based on Eq. (7) and Eq. (8). for t = 1, . . . , T do
Let φt be Eq. (13) for full-information feedback or Eq. (12) for bandit feedback, and compute
q̂t = argmin q∈Ω(P̄i)
〈 q,
t−1∑ τ=ti ̂̀ τ
〉 + φt(q). (10)
Compute policy πt from q̂t such that πt(a|s) ∝ q̂t(s, a).5 Execute policy πt and obtain trajectory (stk, a t k) for k = 0, . . . , L− 1.
Construct adjusted loss estimator ̂̀t such that ̂̀ t(s, a) = { `t(s, a)− L ·Bi(s, a), for full-information feedback, `t(s,a)·It(s,a)
ut(s,a) − L ·Bi(s, a), for bandit feedback,
(11)
where Bi(s, a) = min { 1, ∑ s′∈Sk(s)+1 Bi(s, a, s ′) }
, It(s, a) = I{∃k, (s, a) = (stk, atk)}, and ut is the upper occupancy measure defined in Eq. (9). Increment counters: for each k < L, mi(stk, a t k, s t k+1) +← 1, mi(stk, atk) +← 1.6
if ∃k, mi(stk, atk) ≥ max{1, 2mi−1(stk, atk)} then . entering a new epoch Increment epoch index i +← 1 and set new epoch starting time ti = t+ 1. Initialize new counters: ∀(s, a, s′), mi(s, a, s′) = mi−1(s, a, s′),mi(s, a) = mi−1(s, a). Update empirical transition P̄i and confidence width Bi based on Eq. (7) and Eq. (8).
and can be efficiently computed via the COMP-UOB procedure of [Jin et al., 2020]. Our final adjusted loss estimator is then ̂̀t(s, a) = `t(s,a)·It(s,a)ut(s,a) − L · Bi(s, a). In our analysis, we show that these 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 √ T -regret in the adversarial world using many standard choices of the regularizer φt (which recovers the results of [Rosenberg and Mansour, 2019a, Jin et al., 2020] with a 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 to the new structure of our algorithm which uses a fixed transition P̄i 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:
φt(q) = − 1
ηt ∑ s 6=sL ∑ a∈A √ q(s, a) + β ∑ s 6=sL ∑ a∈A ln 1 q(s, a) , (12)
where ηt = 1/ √ t−ti(t)+1 and β = 128L4. As 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:
φt(q) = 1
ηt ∑ s6=sL ∑ a∈A q(s, a) · ln q(s, a). (13)
5If ∑
b∈A q̂t(s, b) = 0, we let πt to be the uniform distribution. 6We use x +← y as a shorthand for the increment operation x← x+ y.
Although this is a standard choice for the full-information setting, the tuning of the learning rate ηt requires some careful thoughts. In the special case of MDPs with one layer (known as the expert problem [Freund and Schapire, 1997]), it has been shown that choosing ηt to be of order 1/ √ t ensures best-of-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-dependent tuning
(with i denoting i(t) for simplicity): ηt = √
L ln(|S||A|) 64L5 ln(|S||A|)+Mt where
Mt = t−1∑ τ=ti min ∑ s6=sL ∑ a∈A q̂τ (s, a)̂̀τ (s, a)2, ∑ s 6=sL ∑ a∈A q̂τ (s, a) ( Q̂τ (s, a)− V̂τ (s) )2 , 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̄i, the adjusted loss function ̂̀τ , and the policy πτ , that is: Q̂τ (s, a) =̂̀ τ (s, a)+Es′∼P̄i(·|s,a)[V̂τ (s
′)] and V̂τ (s) = Ea∼πτ (·|s)[Q̂τ (s, a)] (with V̂τ (sL) = 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 to ensure polylogarithmic regret in the stochastic world. This concludes all the algorithm design; see Algorithm 1 again for the complete pseudocode.

heading: 4.1 Main Best-of-both-worlds Results
text: We now present our main best-of-both-worlds results. As mentioned, proving √ T -regret 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 √ T . Fortunately, we are able to develop a new analysis that upper bounds some transition estimation related terms by the regret itself, establishing a self-bounding property again. We defer the proof sketch to Section 5, and state the main results in the following theorems.7 Theorem 4.1.1. In the full-information setting, Algorithm 1 with δ = 1T 2 guarantees RegT (̊π) = Õ ( L|S| √ |A|T ) always, and simultaneously RegT (π ?) = O ( U + √ UC ) under Condition (1),
where U = O (
(L6|S|2+L5|S||A| log(|S||A|)) log T ∆MIN + ∑ s6=sL ∑ a6=π?(s) L6|S| log T ∆(s,a) ) .
Theorem 4.1.2. In the bandit feedback setting, Algorithm 1 with δ = 1T 3 guarantees RegT (̊π) = Õ ( (L+ √ |A|)|S| √ |A|T ) always, and simultaneously RegT (π ?) = O ( U + √ UC ) under Con-
dition (1), where U = O (
(L6|S|2+L3|S|2|A|) log2 T ∆MIN + ∑ s 6=sL ∑ a6=π?(s) (L6|S|+L4|S||A|) log2 T ∆(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, we emphasize that our algorithm is the first to be able to adapt to these two worlds simultaneously and achieve Õ( √ T ) 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 obtainO(log T ) regret for the stronger benchmark RegT (̊π) under Condition (1) and known transition (same as our Theorem 3.1), here we only achieve so for RegT (π
?) due to some technical difficulty (see Section 5). However, recall that for the most interesting i.i.d. case, one simply has RegT (π
?) = RegT (̊π) as discussed in Section 2; even for the corrupted i.i.d. case, since RegT (̊π) is at most C + RegT (π
?), our algorithms ensure RegT (̊π) = O(U + C) (note √ UC ≤ U + C). Therefore, our bounds on RegT (π?) are meaningful and strong.

heading: 5 Analysis Sketch
text: 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-information) and
7For simplicity, for bounds in the stochastic world, we omit some Õ(1) terms that are independent of the gap function, but they can be found in the full proof.
Appendix C (bandit). We start with the following straightforward regret decomposition:
RegT (π) = E [ T∑ t=1
V πtt (s0)− V̂ πt t (s0)︸ ︷︷ ︸
ERR1
+ T∑ t=1
V̂ πtt (s0)− V̂ πt (s0)︸ ︷︷ ︸ ESTREG +
T∑ t=1
V̂ πt (s0)− V πt (s0)︸ ︷︷ ︸ ERR2
] (14)
for an arbitrary benchmark π, where V πt is the state value function associated with the true transition P , the true loss `t, and policy π, while V̂ πt is the state value function associated with the empirical transition P̄i(t), the adjusted loss ̂̀t, and policy π. Define the corresponding state-action value functions Qπt and Q̂ π t similarly (our earlier notations V̂t and Q̂t are thus shorthands for V̂ πt t and Q̂ πt t ).
In the adversarial world, we bound each of the three terms in Eq. (14) as follows (see Proposition B.1 for details). First, E [ERR1] measures the estimation error of the loss of the learner’s policy πt, which can be bounded by Õ(L|S| √ |A|T ) following the analysis of Jin et al. [2020]. Second, as mentioned, our adjusted losses are optimistic in the sense that it underestimates the loss of all policies (with high probability), making E [ERR2] an O (1) term only. Finally, E [ESTREG] is the regret measured with P̄i(t) and ̂̀t, which is controlled by the FTRL procedure and of order Õ(L√|S||A|T ). Put together, this proves the Õ(L|S| √ |A|T ) regret shown in Theorem 4.1.1.
In the stochastic world, we fix the benchmark π = π?. To obtain polylogarithmic regret, an important observation is that we now have to make use of the potentially negative term ERR2 instead of simply bounding it by O (1) (in expectation). Specifically, inspired by [Simchowitz and Jamieson, 2019], we propose a new decomposition on ERR1 and ERR2 jointly as follows (see Appendix D.1): ERR1 + ERR2 = ERRSUB + ERROPT + OCCDIFF + BIAS. Here,
• ERRSUB = ∑T t=1 ∑ s6=sL ∑ a6=π?(s) qt(s, a)Ê π? t (s, a) measures some estimation error con-
tributed by the suboptimal actions, where Êπ ? t (s, a) = `t(s, a) + Es′∼P (·|s,a) [ V̂ π ? t (s ′) ] − Q̂π ?
t (s, a) is a “surplus” function (a term taken from [Simchowitz and Jamieson, 2019]); • ERROPT = ∑T t=1 ∑ s6=sL ∑ a=π?(s) (qt(s, a)− q?t (s, a)) Êπ ?
t (s, a) measures some estimation error contributed by the optimal action, where q?t (s, a) is the probability of visiting a trajectory of the form (s0, π?(s0)), (s1, π?(s1)), . . . , (sk(s)−1, π?(sk(s)−1)), (s, a) when executing policy πt;
• OCCDIFF = ∑T t=1 ∑ s 6=sL ∑ a∈A (qt(s, a)− q̂t(s, a)) ( Q̂π ? t (s, a)− V̂ π ? t (s) )
measures the occupancy measure difference between qt and q̂t;
• BIAS = ∑T t=1 ∑ s6=sL ∑ a6=π?(s) q ? t (s, a) ( V̂ π ? t (s)− V π ? t (s) )
measures some estimation error for π?, which, similar to ERR2, is of order O(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, G3, 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 δ = 1T 2 , Algorithm 1 ensures that RegT (π ?) is at mostO(L4|S|3|A|2 ln2 T ) plus:
E [ O ( G1 ( L4|S| lnT
)︸ ︷︷ ︸ from ERRSUB +G2 ( L4|S| lnT )︸ ︷︷ ︸ from ERROPT +G3 ( L4 lnT )︸ ︷︷ ︸ from OCCDIFF +G4 ( L5|S||A| lnT ln(|S||A|) )︸ ︷︷ ︸ from ESTREG
)] .
Finally, as mentioned, each of the G1, G2, G3, and G4 functions can be shown to admit the following self-bounding property, such that similarly to what we argue in Eq. (4), picking the optimal values of α and β and rearranging leads to the polylogarithmic regret bound shown in Theorem 4.1.1. Lemma 5.2 (Self-bounding property). Under Condition (1), we have for any α, β ∈ (0, 1),
E [G1(J)] ≤ α · (RegT (π?) + C) +O ( 1 α · ∑ s6=sL ∑ a 6=π?(s) J ∆(s,a) ) ,
E [G2(J)] ≤ β · (RegT (π?) + C) +O ( 1 β · L|S|J ∆MIN ) ,
E [G3(J)] ≤ (α+ β) · (RegT (π?) + C) +O ( 1 α · ∑ s6=sL ∑ a 6=π?(s) L2|S|J ∆(s,a) ) +O ( 1 β · L2|S|2J ∆MIN ) ,
E [G4(J)] ≤ β · (RegT (π?) + C) +O ( 1 β · J ∆MIN ) .
We emphasize again that the proposed joint decomposition on ERR1 + ERR2 plays a crucial rule in this analysis and addresses the key challenge on how to bound the transition estimation error by something better than √ T . 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 we can only derive a polylog(T ) bound on RegT (π
?) but not directly on RegT (̊π) is also due to these three terms — they can be related to the right-hand side of Condition (1) only when we use the benchmark π = π? but not when π = π̊. This is not the case for ESTREG, which is the reason why Jin and Luo [2020] are able to derive a bound on RegT (̊π) directly when the transition is known. Whether this issue can be addressed is left as a future direction.

heading: 6 Conclusions
text: 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 a loss-shifting trick for FTRL applied to MDPs, which simplifies the method of Jin and Luo [2020] and improves their results. Then, we design a 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 a 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 in our final best-of-both-worlds result.
Besides the open questions discussed earlier (such as improving our bounds in Theorem 4.1.1 and Theorem 4.1.2), one other key future direction is to remove the assumption that there exists a 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 is 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 2020AAA0108400 and 2020AAA0108403. We thank Max Simchowitz for many helpful discussions, and the anonymous reviewers for their valuable feedback and suggestions.

Review summaries:
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.    

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.  The 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.

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.   They 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.  They 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.  Both Full information and Bandit feedback are coinsidered. 

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.