Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedback
Authors: Yan Dai
Haipeng Luo
Liyu Chen
Venue: NeurIPS 2022 Accept (2022)
Keywords: Reinforcement Learning
Follow-the-Perturbed-Leader
Adversarial Markov Decision Process
Online Learning

Abstract: We consider regret minimization for Adversarial Markov Decision Processes (AMDPs), where the loss functions are changing over time and adversarially chosen, and the learner only observes the losses for the visited state-action pairs (i.e., bandit feedback). While there has been a surge of studies on this problem using Online-Mirror-Descent (OMD) methods, very little is known about the Follow-the-Perturbed-Leader (FTPL) methods, which are usually computationally more efficient and also easier to implement since it only requires solving an offline planning problem. Motivated by this, we take a closer look at FTPL for learning AMDPs, starting from the standard episodic finite-horizon setting. We find some unique and intriguing difficulties in the analysis and propose a workaround to eventually show that FTPL is also able to achieve near-optimal regret bounds in this case. More importantly, we then find two significant applications: First, the analysis of FTPL turns out to be readily generalizable to delayed bandit feedback with order-optimal regret, while OMD methods exhibit extra difficulties (Jin et al., 2022). Second, using FTPL, we also develop the first no-regret algorithm for learning communicating AMDPs in the infinite-horizon setting with bandit feedback and stochastic transitions. Our algorithm is efficient assuming access to an offline planning oracle, while even for the easier full-information setting, the only existing algorithm (Chandrasekaran and Tewari, 2021) is computationally inefficient.

for Adversarial Markov Decision Processes with Bandit Feedback
Yan Dai
Tsinghua University
yan yan-dai200mails: tsinghua, edu. en
Haipeng Luo University of Southern California saipengl@usc.co
Liyu Chen University of Southern California liyuckusc.edu
Abstract
We consider regret minimization for Adversarial Markov Decision Processes (AMDPs), where the loss functions are changing over time and adversarially chosen, and the learner only observes the losses for the visited state-action pairs (i.e., bandit feedback). While there has been a surge of studies on this problem using Minine--irron-Desceen (OMD) methods, very little is known about the Leader (FTPL) methods, which are usually computationally efficient and also easier to implement since it only requires solving offline planning problem. Motivated by this, we take a closer look at FTPL for learning AMDPs, starting from the standard episodic finite-horizon setting, We find some unique and intriguing difficulties in the analysis and propose workaround to eventually show that FTPL also able to achieve near-optimal regret bounds in this case. More importantly, we then find two sigmificant applications: First, the analysis of FTPL turns with order-optimal regret, while OMD methods exhibit extra difficulties (Jin et al., 2022). Second, using FTPL., we also develop the first no-regret algorithm for learn- ing communicating AMDPs in the infinite-horizon setting with bandit feedback and stochastic transitions. Our algorithm is efficient assuming access to an offline planning oracle, while even for the easier full-information setting, the only existing algorithm (Chandrasekaran and Tewari, 2021) is computationally inefficient.
be readily generalizable delayed bandit feedback
Introduction
Markov Decision Processes (MDPs) have long been used to model problems in reinforcement learning, where the agent takes sequential actions in an environment, leading to transitions among different states and observations on loss (or reward equivalently) signals. While the classical MDP model assumes a fixed loss function, there has been increasing interest in studying regret minimization under non-stationary or even adversarial loss functions via the Adversarial MDP (AMDP) model, starting from the work Even-Dar Dar et al. (2009).
Similar to other regret minimization problems, there are typically two categories of algorithms for AMDPs: those based on the Follow-the-Pee thee-Petturee-Lece Leader (FTPL) framework (Even-Dar et al., 2009; Neu et al., 2010, 2012; Chandrasekaran and Tewari, 2021) and those based on the Online-Mirroo Descent (OMD) or the closely related Follow-the- wew.tee-egaaarred-eeaeaaae
(FTRL) framework (Zimin and Neu, 2013; Rosenberg and Mansour, 2019a,b; Jin et al., 2020, 2021, 2022). FTPL methods are usually computationally more efficient and easier to implement as only requires solving an offline
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1: An overview of the proposed algorithms/resulss and comparisons with related works.
Setting
Transition
Feedback
Algorithm
Regret"
Method
Eif
Zimin and Neu (2013)
ŌUNVSAR)
OMD
Known
This work (Theorem 4)
O(H%
FTPL.
Bandit
el (2020)
((HS5AA
Episodic H horiiiionn
This work (Thoorem
O(R)SVAR)
FTPL.
AMDPs
Delayed HEnGI (Jin al., 2022)
OMD
Unknown
Bandit
Delayed UOB FTRI (Jin et al., 2022)
O(1*SvAR SA
OMD
Delayed
Delayed UOB (Jin et 2022)
ŌUrSVAK (SA)"/
OMD
This work (Thoorem
O(H'SVRR AR HPPVSAD
FTPL.
Even-Dar et al. (2009)
O(r-VT) (Frgodic)
OMD
Full-info
Chandrackaran and Tewari (2021)
((5'vT) (Deterministic)
FTPL.
Chandrasckaran and Towari (2021)
O(D*VST) (Commu)
FTPL
Infinite-
Neu al. (2014)
O(v/+AT) (Ergodic)
OMD
horizon
Known
AMDPs
Dekel and Hazan (2013)
AT""") (Deterministic)
OMD
Bandit
This work (Thoorem 7)
(SD)" (Commu)
FTPL
V!
This work (Theorem 8)
(SDT))) (Commu)
OMD
Dakel al. (2014)
97559755) only Commu)
"Here, S and A are the number of states and actions respectively, K is the number of episodes, T is the total number of steps, D is the total amount of delay, T is the mixing time of an ergodic MDP, and D is the diameter of communicating MDP. Several related works use different notations from bounds have been converted based our notations. For infinite-horizon AMDPs, the extra assumptions listed after regret bounds, with "Ergodic" standing for ergodic MDPs, "Deterministic" standing MDPs with deterministic transitions, and "Commu" standing for communicating MDPs (the weakest assumption).
and their regret
"This column indicates the algorithm's efficiency: // means polynomial (in all parameters) time complexity, means ((AA)) time complexity. and means efficient assuming access to planning oracle (that returns the best policy given all the MDP's parameters). Note that FTPL-based algorithms are usually easier to implement compared to OMD/FTRL- based ones (both treated as OMD-based based in this table as they are quite similar).
optimization problem (a.k.a. planning problem in the MDP literature). In contrast, OMD/FTRL methods require solving convex optimization problems over a complicated occupancy measure space.
Despite its computational advantages and ease implementation, FTPL methods are much less studied (especially for learning AMDPs) since they are harder analyze, less versatile, and believed to suffer worse regret compared to OMD/FTRL methods. A recent work by Wang and Dong (2020) disputes the last common belief and shows that, for episodic AMDPs with full-information feedback, FTPL also enjoys near-optimal regret, similarly to OMD/FTRL. Nevertheless, little is known about FTPL for learning AMDPs with the more challenging bandit feedback knowledge, the only FTPL algorithm for this case is by Neu et al. (2010). However, that algorithm is analyzed under a strong assumption that every state is reachable by any policy with at least constant probability > 0. Such an exploratory assumption is too strong to be used in realistic applications.
our
Motivated by this fact, take closer look FTPL for learning AMDPs under bandit feedback, aiming at showing strong regret guarantees while enjoying its computational advantages. We start with the standard episodic finite-horizon setting and indeed find some intriguing difficulties compared to OMD/FTRI. After addressing these difficulties, we then show critical applications of FTPL. methods two more challenging setups: episodic AMDPs with delayed bandit feedback and infinite-horizon AMDPs with only communicating assumptions, with the latter result advancing the state-of-the- More specifically, our contributions are (see also Table for summary):
1. We start with the heavily studied episodic setting with K episodes, H steps in each episode, S states, and A actions. Our first intriguing observation is that: since the loss of each policy is linear in a non-binary vector (i.e., the occupancy measure), existing analysis for the stability term of FTPL fails, even though it works for the binary case (e-g.. Neu and Bartók (2016)). Our next important observation that there exists a simple fix to this issue that only leads to an extra H factor. This eventually leads to "/H
regret when the transition is known (Algorithm 1, Theorem 4), which is only / V factor larger than the near-optimal regret achieved

---

by OMD (Zimin and Neu, 2013), and S(H)SVAK) regret when the transition is unknown (Algorithm Theorem 5), matching the state-of-the-as again achieved by OMD (Jin et al., 2020).
See Section 3 for details.
2. We next find that compared to OMD, the analysis of FTPL is much easier to be generalized to the delayed feedback setting where losses for episode k are observed only at the end of episode k + dg for some dg 2 0 (I (Lancewicki et al., 2022: Jin et al., 2022). Indeed, these two prior works demonstrate the difficulty of analyzing OMD with delay feedback, with Lancewicki et al. (2022) only achieving Ö( + 9))) regret (where D Ex dg is the total amount of delay; dependence
on other parameters is omitted) and Jin et al. (2022) improving it to ÖlvK + D) via either an inefficient algorithm or an efficient OMD-based algorithm with more involved analysis and/or new bollyyddaddatedd loss estimators. FTPL., on the other hand, achieves O( K + D) regret by a simple extension of the analysis (Theorem 6). The dependence on S and A is also better than the OMD method of (Jin et al.. 2022) with the same kind of standard loss estimators (though worse than their best result with the jelayed-adapted estimators; see Table I and Section 4 for details).
3. While our results above do not improve the best existing ones, our final application of FTPL. provides the first result for learning horiite- communicating AMDPs with bandit feedback and known stochastic transitions. Specifically, our algorithm achieves ((A (S))47791)) regret (Algorithm 6, Theorem 7), where D is the diameter of the MDP and T is the total number of steps. efficient assuming access to an offline planning oracle (that returns the best stationary policy given a fixed transition function and sequence of loss functions for each step). Previous results either only handle deterministic transitions (Dekel and Hazan, 2013) or full-information loss feedback (Chandrasckaran and Tewari, 2021). Moreover, the FTPL algorithm of Chandrasekaran and Tewari (2021) for stochastic transitions is inefficient even given the same planning oracle (since it explicitly adds independent noise to every policy). For completeness, inefficient algorithm (Algorithm 7) that achieves (AA regret in our bandit setting, matching the ((T*/3 lower bound of Dekel et al. (2014) in terms of T' See Section for details.
also provide an
1.1 Related Work
FTPL is first proposed by Hannan (1957) and later popularized by Kalai and Vempala (2005). It has proven to be extremely powerful for structured online learning problems (such as online shortest path) since its implementation is as easy as solving the correspond- ing offline optimization problem (such as finding the shortest path of a given graph). Over the years, FTPL has been extended to problems with semi-bandit feedback (Neu, 2015; Neu and Bartók, 2016), contextual information (Syrgkanis et al., 2016), non-linear losses (Dudík et al., 2020), smoothed adversaries (Block et al., 2022; Haghtalab et al., 2022), and others. However, FTPL for learning AMDPs under bandit feedback is poorly understood, which motivates this work. As we successfully show, improving our understanding of FTPL is indeed beneficial since it at least leads to new results for the infinite-horizon setting (in addition to its computational advantages for other settings). Below, we briefly review the literature of AMDPs for the three settings we consider.
Episodic Finite-Horizon AMDPs: Earlier works on this topic focus the easier known transition case. In particular, the OMD-based O- REPS algorithm by Zimin and Neu (2013) achieves Ö(H (K) regret with full-information feedhack and Ö(H / /SAK) regret with bandit feedhack, both optimal up to logarithmic factors. On the other hand, FTPL is recently shown to achieve Õ(H2V regret with full-information feedback (Wang and Dong, 2020). As mentioned, the only FTPL algorithm for bandit feedback is by Neu et al. (2010), which guarantees ő OH'2 V AK/ /a) regret assuming that all states are reachable by any policy with a probability of at least a. In contrast, our FTPL algorithm removes this requirement and achieves %/ SAKK) regret, which is only / H away from optimal.
When the transition unknown, with full full-information feedback, the OMD-based algorithm UC- O-REPS (Rosenberg and Mansour, 2019a) achieves D(H2SVAK) regret, while the FTPL-based FPOP (Neu et al.. 2012) is shown to achieve S(H2SVAK)) regret as well (Wang and Dong, 2020). With bandit feedback. the OMD-based algorithm UOB-REPS (Jin et al., 2020) also achieves the same (HHSSAKK) regret. At the same time, our algorithm enjoys the same guarantee and the first FTPL algorithm for bandit feedback and unknown transition. However, the current best lower bound for this problem is "/HH///AALL (Jin et al., 2018), so there is still ((HH)) gap.
3

---

Besides OMD and FTPL, there is, in fact, another category of algorithms for learning AMDPs: policy optimization (Shani al.. 2020; Luo et al., 2021). which performs OMD in each state and is also efficient. However, the regret bounds are worse by at least an H factor (Luo et al., 2021).
The most related works are Lancewicki al. (2022) and Jin et al. (2022), and we refer the reader to the references therein for the literature on delayed feedback for different problems. Importantly, Jin al. (2022) point out the unique difficulty when analyzing OMD/FTRL for AMDPs with delayed feedback. Circumventing this difficulty one way or another, they develop three algorithms: the first one, Delayed HEDGE, is inefficient; the second one, Delayed FOB-FTRL. achieves worse regret ( (vSA larger for the delay-related term) compared to ours; and the third one makes use of a delay-adapted estimator and achieves the best bound (see Table 1). We emphasize again that our FTPL. analysis is much simpler and a direct extension of the non-delayed case. The current best lower bound for this problem is S2(H (HHR//SK + HVD) (Lancewicki et al., 2022).
Delayed Feedback:
Learning AMDPs becomes significantly more difficult in the infinite horizon setting. As far as know, all works in this line (including ours) assume known transition function. Earlier works focus on the simpler case with a strong ergodic assumption (Even-Dar et al., 2009; Neu al., 2014). For the more general communicating assumptions, recent work (Chan- drasekaran and Tewari, 2021) considers fulliinformation feedback and develops an efficient FTPL algorithm for deterministic transitions with D(S*VT) regret and another inefficient FTPL algorithm for stochastic transitions with ((DVVST) regret. Under bandit feedback, prior works only study deterministic transitions (Arora et al., 2012; Dekel and Hazan, 2013), with Dekel and Hazan (2013) achieving O AT*4)) regret, matching the lower bound (Dekel et al., 2014) for the T-dependency. Our results are the first for bandit feedback and stochastic transitions. Note that since bandit feedback is only more general, our oracle-efficient algorithm can also be applied to the -ullminfornation setting, while the only existing algorithm (Chandrasekaran and Tewari, 2021) computationally inefficient.
Infinite-Horizon AMDPs:
2 Preliminaries
General Notations: We use [N] to denote the set NV. For a (finite) set X, we use A(X) A far
E x; = 1} to denote the probability simplex over the set X. We use Ō(-) hide all terms logarithmic in H, S, A, K and T. Laplace(1) denotes the Laplace (also known as double-exponential) distribution with center 0 and parameter 1), whose probability density is [xx) = exp((>)<=l), Vo E R. For an event E, let [8] be its indicator. In episodic settings, let (F be the natural filtration such that F₂ contains the history of episodes I,..., k. With a slight abuse of notation, in the -nfinite-horizon setting, we also use {Fi] to denote the natural filtration.
R
R
[X|
Episodic Adversarial Markov Decision Process: An episodic Adversarial Markov Decision Process (AMDP) is defined by a tuple M (S, A, L. K, H, s ), where S is the state space, A is the action space, P: [H] x S x A + (S)) is the transition function, E: [K] x [H] x S x A + [0, 1] is the loss function unknown to the agent but fixed before the game (i.e., adversary). K is the number of episodes, H is the horizon length, and s E S is the initial state.
are assuming an oblivious
Denote by S = |8| oc and A A| < oo, the number of states and actions, respectively.
The agent interacts with the environment for K episodes. For the k-th one (k S K), she starts from the initial state s² and sequentially interacts with the environment for H steps. At the h-th step (where h E [H), the agent observes state $t E S, chooses an action at E A, observes and suffers the loss e (sk, at) (bandit feedback), 2 and then transits to state A++1 according to the probability distribution pk (- | a²)). After H steps, the episode ends and the agent proceeds to episode k + 1.
(deterministic) policy of the agent is defined by क = ( S - A) Denote the set of all deterministic policies by 11. The expected loss incurred by policy E 11 for episode with loss function f is denoted by V(T; 2) A E (s("", <>()*)) h+1 ~ p | sh >> wh < H Suppose the agent uses policies Ti, T2, ...,,..,, TK for episodes 2, ... K, respectively. The total expected loss of the agent is then E Σ Ek=1 V(TTi fx)] where the expectation is taken with respect to
I Note that the loss function can vary arbitrarily for different (kt, h)-priss, instead of being stochastic.
On the other hand, in the easier full inllrinforattion setting, the entire e is revealed.

---

the agent's private randommess. The baseline is the best deterministic policy in hindsight, defined by rt E argmin E V(T; Ex). The goal of the agent is to minimize her regret over K episodes, which is the difference between her total loss and that of π formally defined as
K
K
Rx
E
Σ
(iT (x)
- Σ ((T)
k=1
Episodic AMDPs with Delayed Feedback: This setup is exactly the same as the episodic AMDPs, except that the feedback 10%(( ( for episode k is only available after de episodes, i.e., at the end of the (A: + d& 3-th episode. Define Σ dg to be the total feedback delay, assumed to be known to the agent as this assumption can be easily relaxed via doubling trick (Thune al., 2019).
Infinite-Horizon AMDPs: Similar to episodic AMDPs, infinite-horizon AMDPs is defined by a tuple M - (S, A, P,,, st... Here, starting from the initial state s E S, the agent interacts with the environment for 7 total steps without any reset, under the transition model P: S x A + (SS) A [0, 1]. More specifically, at
(which does not vary over time) and loss functions f: [T] time & E [T', the agent observes state s' E S. chooses an action a' E A, observes and suffers loss (s* a²), and then transits s+ P( s',aa)) Her goal is also to minimize the regret, defined as
T
T
Rr A
Σ (ss (s)ssaa) s s
F(. (1,
min E FET
Σ
s0 P(. 10
where II is now the set of all deterministic policies mapping from S to A. As pointed out by Bartlett and Tewari (2009), without any extra assumptions, sublinear regret is impossible for this problem due to the lack of resets. Earlier works make strong ergodic assumption such that, intuitively. any mistake will be forgiven after logarithmic steps (Even-Dar et al., 2009). Here, we instead focus on the much weaker communicating assumption as in Chandrasekaran and Tewari (2021):
Definition (Communicating MDP). We call an MDP M communicating it has a finite diameter D 2 max mingen [s' s)) where T(s' M,, s) is the (random) time step when state s' is first reached by policy x starting from state s.
Just like Chandrasckaran and Tewari (2021), for technical reasons, we also need the following mild assumption saying that there exists special state for the agent to "park" there without moving. Assumption 2. There exist state 8 S and action a" E A such that P(s 18, aaa) = 1.
3 FTPL for Episodic AMDPs
In this section, we consider the basic (non-delayed) episodic setting. To best illustrate the unique difficulty meet when analyzing FTPL and the way we address it, first discuss the known- transition case (i.e., {P
=b=1 is known to the agent), and then move on to unknown transitions.
3.1 Known Transition
Our algorithm follows the standard FTPL framework (see Algorithm 1). Ahead of time (as the adversary oblivious), we sample a perturbation vector 2: [H] x S A + IR so that z"(s, a) an independent sample from Laplace(1) for some parameter 7). At the beginning of episode ks, given the loss estimators E,.... f from previous episodes (whose construction will be specified later), we simply play the policy that minimizes the cumulative perturbed estimated loss (break tie arbitrarily):
Th argmin sell
[((T2)++
+
Σ
(IT; (ur
argmin V TT; (.R-..) *Ell
1=1
where we use Z. (where 0 for = for notational convenience. This optimization over ग E II is a simple planning problem and can be solved by dynamic programming efficiently.
S < K) shorthand notation for Er- Per and to as an alias
3 As in Jin et al. (2022), we only consider delayed loss feedback, but not delayed trajectory feedback, since the latter only affects the transition estimation and can be handled similarly Lancewicki et al. (2022).
5

---

Algorithm 1 FTPL for Episodic AMDPs with Bandit Feedback and Known Transition
Require: Laplace distribution parameter 7)- Geometric Re-sampling parameter L.
Sample perturbation Eo = 2 such that 2 (s, a) is an independent sample of Laplace(n).
2: for k == 2, ... K do
3: Calculate = er V(T; lo:k-1) (via dynamic programming).
4: for 1, 2, H do
5:
Observe " play of
( suffer and observe loss & ( at))
6:
Calculate loss estimator f via Geometric Re-sampling (Neu and Bartók, 2016):
7:
for M ... do Sample fresh perturbation 7 in the same way as 2.
8:
9:
Calculate T/K argmin V (T;; fiik-1 2).
10:
Simulate Tig. for h steps starting from s' and following transitions PP Pl..... PP..
11:
if (sh) ( is visited at step h or M L then
12:
Set (s) M (o at) [[(sk, af) (s, a)] and break.
Upon seeing si. ab and (s), )f), we construct the loss estimator P using the Geometric Re- sampling technique (Neu and Bartók, 2016). The idea is repeat the sampling procedure (Line to 10) until the same pair (sf, ab) is visited again at step h or this has been repeated L times for some parameter L. Let the total number of trials be M then the estimator is defined as 2 (s, = MD (6 at)) [[(s,, d = (s, a)] (Line 12). Note that the sampling procedure can be done freely without interacting with the environment as the transition is known. The rational behind this estimator is that long L is reasonably large, M is good approximation of the inverse probability of visiting (sh, a (which is hard to calculate directly for FTPL), making Ph a good (and efficient) approximation of the standard importance weighted estimator (Zimin and Neu, 2013).
Analysis Sketch: While our algorithm follows the standard FTPL framework, we find some in- triguing difficulty in the analysis that is unique to MDPs and undiscovered before. To illustrate this difficulty, 1ct us first describe an overview the analysis. First, since the loss estimators are almost unbiased (as shown by Neu and Bartók (2016)), we only need to focus the regret with respect the estimated losses, that is, E |> ((TTi >E V(=*; [ Adding and subtracting k== V(TE+11;2)) 2x) (the loss of an imaginary "leader" that looks one episode ahead), our next goal is to bound the so-called stability term Σ>= V(TT;; Ev) - k= ) V( [x)] (the rest, usually referred as the error term, can be bounded by the standard "be-the-leadee lemma).
E E
For the stability term, fix an episode k and define pk (T(T) as the probability of selecting т as TT w.r.t. the randomness of the perturbation 2. Further introduce the notion of occupancy measures (Altman, 1999; Neu al., 2012): each policy E II induces H occupancy measures μ E A x A). vh E [H), where n (s, a) denotes the probability of visiting (s, () step h if one executes policy starting from the initial state s With these notations, each summand for the stability term becomes:
E (TT): - (TT++1:2)) E (Px(TF=
- (k+1(TT) (prs
LEE
where (Ur, (x) A - (ut P2). This stability term is exactly in the same form that in Lemma 8 of Neu and Bartók (2016) or Lemma 10 of Syrgkanis et al. (2016) for (contextual) semi-bande problems, except that in their contexts, Ar is binary vector. This seemingly slight difference turns out to be important! Specifically, in these two prior works, they both show (using our notations):
Pk+1 ( 2 Pk (T) exp (-m Fx)
(2)
which, together with the fact exp( > 1 x. implies
E Vi 2e) ((T++1;;
S 1 E
Σ pk (T)) Pory Ex
Leell
Readers familiar with the online learning literature would have recognized the last expression, since it is also the standard stability term achieved by (inefficiently) running the classical HEDGE

---

algorithm (Freund and Schapire, 1997) over all policies (see e.g. Theorem 7.3 of Bubeck (2011), 1)). Indeed, this term small enough and can be shown be of order ((NHSA) our context after plugging in the definition of the loss estimators, which would then basically complete the proof.
However, not only do we realize that the proof of Eq. (2) heavily rely on the binary nature of jr. we in fact also find a counterexample where Eq. (3) is simply incorrect when is non-binary (see Appendix 1.1.5 for the counterexample). We find this fact intriguing, because Eq. (3) holds for the aforementioned inefficient HEDGE algorithm regardless whether μex is binary or not.
Further examining the proof of Neu and Bartók (2016) and Syrgkanis al. (2016), however, one can prove the following weaker version of Eq. (2) and Eq. (3) (namely Eq. (4) and Eq. (5) respectively). Lemma 3 (Single-Step Stability). For all k E [K] and π E 11, we have
11
P&+1(T) 2 (T((T) exp
(4)
h=1
and thus
Σ pa (TT ( (ras Ea) HEll
E ((Tai - ((T S Sn
Σ
(5)
Fortunately, while Eq. (5) looks seemingly much larger than the classic bound Eq, (3), is in fact at most larger by H factor, that is, the right-hand side of Eq. (5) can be shown be of order On SA) (see Lemma 12 in the appendix). Putting everything together, this allows us to prove the following regret guarantee for Algorithm I, which is v H larger than the optimal bound (Zimin and Neu, 2013) due to the weakened stability bound. One may refer Appendix B.1 for the formal proof. Theorem 4. For episodic AMDPs with bandit feedback and known transitions, Algorithm 1 with 1/WSSAK and I= = I. ensures RT = Ô (HH))SAK).
" =
3.2 Unknown Transition
To handle unknown transitions, we mostly follow existing ideas. First, for each episode k we maintain confidence set Pa of the transition function as Jin et al. (2022), whose construction is given in Appendix B.2.1. These confidence sets ensure that i) IP E Ps with high probability and ii) Pk+1 S Pk- Generalizing the notation (xx;; E), we use V(T; Ê, P) to denote the expected loss of policy æ for an episode with loss function i and transition P (so V(x;
(=;; P)). Then deploying the idea of optimism, we replace Line 3 of Algorithm I with T&& = argmin, rell min V (TT; 20:k-1, P). which can be efficiently found using Extended Value Iteration (Jaksch et al., 2010). As Wang and Dong (2020) argues, this is far more efficient than performing OMD over occupancy measure spaces.
We also need to modify the Geometric Re- Re-sampling procedure accordingly since Line 10 requires using the true transition. To do so, we combine the procedure with the idea of upper occupancy measures from Jin et al. (2020). Specifically, in each trial we sample TVK in the same way as n3 but with fresh perturbation, then find the optimistic transition within Ps: that maximizes the probability of n' visiting (sf; ag) (which can be done efficiently using dynamic programming as shown by Jin et al. (2020)), and finally simulate ot. for h steps following this optimistic transition.
Due to space limit, the full algorithm, Algorithm 3, is deferred to Appendix B.2. The analysis of the extra regret caused by the transition estimation error can be handled similarly Jin et al. (2022) (more specifically, their Delayed HEDGE algorithm).. As in previous works, this happens to be of order 2 S AK) and becomes the dominating term of the regret. This makes our final regret the same as the state-of-the-arr (Jin et al., 2020), despite the weaker single-step stability lemma discussed in Section 3.1 (since this part is dominated now). Formally, we have the following regret guarantee. Theorem 5. For episodic AMDPs with bandit feedback and unknown transitions, Algorithm 3 with n 1/VHSAK and L = == /SAK/H ensures Rr = Ô (H² (H2S.
4 FTPL for Episodic AMDPs with Delayed Feedback
In this section, we show how our FTPL algorithm and analysis can be easily extended to the delayed feedback setting where the losses for episode k are only observed at the end of episode & + dg-
7

---

The only change to the algorithm is to naturally delay the loss estimator construction until the loss feedback received, and at each episode l only use the estimators constructed so far, i.e. O4 _ (K' W' + de < k), to compute the current policy Ty. See Algorithm 4 in Appendix C.
To show how the analysis works, we focus on the known transition case at this moment for simplicity. Similar the non-delayed case, the key is to bound the stability term, which was D K ((Tei())= Σ ( []]] in Section 3.1, but now becomes EE Σ V(Txi 4e)
Ek=1 V(T++1; [x)] where #K+1 = argmin V(r;; folx) is "cheating policy' (Gyorgy and Joulani, 2021; I; Jin et al., 2022) that uses all loss estimators from the first episodes (which matches Th+1 for the non-delayed case). By the exact same analysis as Eq. (4) and Eq. (5), one can show
H
B [[V(mni Ee) - (( Su
Σ
Ei
Σ Pa(TT) (mmTEa)) REll
M h=1
DIFF
where the DIFF term is the cumulative & norms of all the estimators used in computing Tx+1 but not TTg (again, a direct generalization of Eq. (5) where only & satisfies such conditions for k². is then not hard to imagine that when summed over k. the DIFF term is eventually related to the total amount of delay D = Ex dg. Indeed, the sum of all stability terms over K episodes can be shown to be of order On) generally for unknown transitions, we prove the following guarantee (see Appendix C for the proof). Theorem 6. For episodic AMDPs with delayed bandit feedback and unknown transitions, Algorithm 4 with 1) = 1//HSALK42) and L / (BSA/H ensures RT = Ô (H²S + 1// /SAD)
+ +))- This is basically all the extra elements we need in the proof. More
The simplicity of our analysis is similar to the Delayed HEDGE algorithm (Jin et al., 2022), but the latter is inefficient with time complexity (2(A). The efficient Delayed UOB-FTRI. algorithm (Jin al., 2022) requires a more complicated analysis and only achieves Ô SH + SAVD) regret (which is worse than ours), while its improved variant Delayed UOB-REPS with a new delay- SVAK +
adapted estimator achieves the current best bound unclear to us whether such delay-adapted estimators can help improve FTPL. Finally, we again remark that the current best lower bound is ((H HVD) (Lancewicki et al., 2022).
However, it
5 FTPL for Infinite-Horizon AMDPs
At last, we discuss how FTPL can be used to derive the first no-regret algorithm for infinite-horizon communicating AMDPs with bandit feedback and (known) stochastic transition. Note that learning dufinite-horizon AMDPs is much more difficult due to the lack of resets (in a sense, this is like a problem but with only one long episode with T steps). Another way to see the difficulty is that the benchmark in the regret definition Eq. (1) is evaluated on states generated by following "² repeatedly for T rounds, without any resets. From technical viewpoint, this requires the algorithm to also make sure that, when following a policy æ, its suffered loss indeed close to the total loss ı has been followed since the very beginning, which is unnatural without ergodic assumptions.
Chandrasckaran and Tewari (2021) resolve this issue by the combination of two ideas. First, under the mild Assumption 2, they show that whenever the agent wants to switch the current policy to another policy म, there exists a procedure to make sure that after O(D2) steps of a transition phase, the agent's s state distribution is exactly the same that induced by following iT from the very beginning. That is, after this switching procedure, the agent can "pretend" that she has followed π all the time. Second, since this procedure requires a cost of ODD2) steps (where the loss of the agent can be arbitrarily bad and only trivially bounded by O(D²)), ), the algorithm needs to switch its policy infrequently.
Our algorithm follows the same ideas. However, while low-switching is relatively easy to ensure in the mullinfformatin case without paying extra regret, it is known that with bandit feedback there is an unavoidable trade-off between the number of switches and the regret, which can be optimally balanced via a simple epoching scheme (Dekel et al., 2014). To this end, we divide the total T steps into J o(T) epochs, each with length H T/J w(D)). At the beginning of the j-th epoch, we compute a new policy Ty. apply the switching procedure of Chandrasekaran and Tewari (2021) to adjust the state distribution (see Algorithm 5), and finally follow the same policy πī for the rest of the epoch. This clearly only introduces J switches, which contributes to most O(J D2) extra regret.
8

---

It remains to specify how to find ny in epoch j using FTPL. The key difference compared to the episodic case is that, due the lack of resets, we need to add perturbation every time step instead of just to each of the H steps of an episode. We then still play the policy that minimizes the cumulative estimated losses plus all the perturbed losses. Formally, my is defined as:
1yT/3
TT.
aarggmin EE *EII
((st. + E=1
E 2s((ttT('') st ~ 1 Vt
(6)
where {=': x A A Re is such that each 2' (s, a) is an independent sample of Laplace(n).
and each 8t is the estimator of tt constructed from the Geometric Re-sampling procedure.
Unfortunately, as far as we know, there is in fact no existing polynomial time algorithm for solving Eq. (6) (the difficulty comes from the restriction on stationary policies whose behavior does not vary over time). Even if the losses are stochastic, the problem is only known to be P-hard (Papadimitriou and Tsitsiklis, 1987; Mundhenk et al., 2000) and no polynomial algorithm has been developed.
However, note that this optimization is exactly in the same form as the benchmark in the regret definition Eq. (1). Following many prior works such as Dudik et al. (2020); Block et al. (2022); Haghtalab et al. (2022), we thus assume access to a planning oracle that solves this offline problem. making our algorithm only oracle-efficient instead of truly polynomial-time tinfffl-imm-fffiienttt. Note that even given this oracle, the algorithm of Chandrasekaran and Tewari (2021) is inefficient since it creates independent perturbation for each of the A policies, while our perturbation is much more compact.
In terms of the analysis, the key extra challenge is caused by having T perturbed losses. Indeed, the term of order Ö(T/T). which
same analysis from the episodic case (Lemma 44) would lead is prohibitively large. Instead, inspired by Syrgkanis et al. (2016), we provide a different analysis showing that this can be improved to Õ(S V AT /n), which has worse dependencies S and A but better dependency on T, the key to ensure sub-linear regret eventually. To conclude, our FTPL algorithm achieves the following guarantee (see Appendix D.I for the full algorithm and analysis). Theorem 7. For infinitehhoriznn AMDPs with bandit feedback and known transitions, Algorithm A/2 and I. = 3 1/2 ensures RT = Ô (AV 13
3//3 カリ J
with 7
17773
We emphasize again that this is the first (oracle-efficient) algorithm for this setting. Even in the easier full-information setting (where le is fully revealed at the end of time f), our algorithm also has its computational advantages compared to that Chandrasekaran and Tewari (2021) 1),, since, as mentioned, their algorithm requires 22(A$) complexity (albeit with a better regret bound O(D² ))
The best lower bound for this setting (255/T//>) (Dekel et al., 2014). Dekel and Hazan (2013) achieve 0(5 AT*/3) but only when the transition is deterministic. For completeness, we provide a HEDGE-based inefficient algorithm (Appendix D.2) for general stochastic transitions, which achieves the optimal regret in terms of the dependence on T, improving our oracle-efficient FTPL algorithm.
Theorem 8. For aefinite-horzonn AMDPs with bandit feedback and known transitions, Algorithm 7
with 1 A'a(D1y43 and J
g//3
ensures RT 3 (SDT))))
DY5
6 Conclusion
In this paper, we designed FTPL-based algorithms for adversarial MDPs with bandit feedback in various settings, including episodic settings, delayed feedback settings and anfinitehhorizon settings. Our algorithms are easy to implement as they only require solving the offline planing problem, and in some cases they match the state-of-the-art performance
even the first ever no-regret algorithms.
One interesting open question whether, despite our counterexample, Eq. (3) can still hold with a larger constant for the right-hand side, either with our current algorithm or via some modified versions (for example with a different kind of perturbation). Achieving this would lead to an improved version of Lemma 3 and thus give the near-optimal delay- regret term Ō 3/2 for the delayed feedback setting, which is not currently achieved by any existing algorithms.
alternative direction to try to equip our Algorithm 4 (for episodic AMDPs with delayed feedback) with the "delay-adapted" loss estimators proposed by Jin et al. (2022). As their analysis

---

heavily relies on the exponential weight scheme (see their Lemma D.7. which bounds KL divergences between consecutive policies), is unclear us whether FTPL enjoys a similar property.
Another important future direction to improve our results in the infinite-horizon setting, such as improving the (17%) oracle-efficient regret upper bound, removing the usage of oracles, or dealing with the unknown transition case (which has not yet been studied all).
There are also several possible generalizations of our setting. For example, we only assume the losses be adversarial. Further incorporating evolving transition an FTPL--based algorithm (Yu and Mannor, 2009) for evolving dynamics (though they are assuming ergodic Sitnite-horizon MDPs), which builds upon the FTPL analysis by Even-Dar et al. (2009) (see their Lemma II1.3). Although our work directly improves the performance guarantee of Even-Do -err al. (2009), it highly unclear whether we can adopt the algorithm of Yu and Mannor (2009) for umknown-transitee episodic MDPs (they assumed the transitions to be revealed after each episode) or infinite-hone horizon weakly communicating MDPs. Solving either case will be interesting. Moreover, considering dynamic regret instead of static regret can also be challenging.
important next step. There is already
Acknowledgments and Disclosure of Funding
We greatly acknowledge Vasilis Syrgkanis for the helpful discussion about whether their single-step stability lemma (Syrgkanis et al., 2016, Lemma 10) holds for non- non-binary action spaces. We also thank the anonymous reviewers for their insightful comments, which we greatly benefit from. HL is supported by NSF Award I1S-1943607 and Google Faculty Research Award.
References
Eitan Altman. Constrained Markov decision processes: stochastic modeling. Routledge, 1999.
Raman Arora, Ofer Dekel, and Ambuj Tewari. Deterministic mdps with adversarial rewards and bandit feedback. In Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence, pages 93-101, 2012.
Peter Bartlett and Ambuj Tewari. Regal: regularization based algorithm for reinforcement learning in weakly communicating mdps. In Uncertainty in Artificial Intelligence: Proceedings of the 25th Conference, pages 35-42 AUAI Press, 2009.
Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as easy statistical learning. In Conference on Learning Theory, pages 1716-1786. PMLR, 2022.
Sébastien Bubeck. Introduction to online optimization. Lecture Notes, 2, 2011.
Gautam Chandrasekaran and Ambuj Tewari. Online learning in adversarial mdps: Is the communicat- ing case harder than ergodic? arXiv preprint arXiv:2111.0202. 2021.
Ofer Dekel and Elad Hazan. Better rates for any adversarial deterministic mdp. In International Conference on Machine Learning, pages 675-683. PMLR, 2013.
Ofer Dekel, Jian Ding, Tomer Koren, and Yuval Peres. Bandits with switching costs: 2/3 regret. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 459-467, 2014.
Miroslav Dudik, Nika Haghtalab, Haipeng Luo, Robert E Schapire, Vasilis Syrgkanis, and Jen- nifer Wortman Vaughan. Oracle-efficient online learning and auction design. Journal of the ACM (JACM), 67(5) 2020.
Eyal Even-Dar, Sham M Kakade, and Yishay Mansour. Online markov decision processes. Mathe- matics of Operations Research, 34(3):726-736 2009.
Yoav Freund and Robert E Schapire. A decision-theome generalization of on-line learning and an application to boosting. Journal of computer and system sciences, (5(1):119-13) 1997.
Andras Gyorgy and Pooria Joulani. Adapting to delays and data in adversarial multi-armed bandits.
In International Conference on Machine Learning, pages 3988-3997. PMLR, 2021.
10

---

Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang. Oracle-efficient online learning for beyond worst-case adversaries. arXiv preprint arXiv:2202.08549, 2022.
James Hannan. Approximation to bayes risk in repeated play. Contributions the Theory of Games, 3(2):97-139, 1957.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11:1563-1600, 2010.
Chi Jin, Zeyuan Allen-Zhu Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learming provably efficient? Advances in neural information processing systems, 31, 2018
Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning adversarial markov decision processes with bandit feedback and unknown transition. In International Conference on Machine Learning, pages 4860 186004469..81 PMLR, 2020.
Tiancheng Jin, Longbo Huang, and Haipeng Luo. The best of both worlds: stochastic and adversarial episodic mdps with unknown transition. In Advances in Neural Information Processing Systems 34, pages 20491-20502, 2021.
Tiancheng Jin, Tal Lancewicki, Haipeng Luo, Yishay Mansour, and Aviv Rosenberg. Near-optimal regret for adversarial mdp with delayed bandit feedback. arXiv preprint arXiv:2201.33172. 2022.
Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 7 71(3):291-300 2005.
Tal Lancewicki, Aviv Rosenberg, and Yishay Mansour. Learning adversarial markov decision processes with delayed feedback. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022. pages 7281-7289. AAAI Press, 2022.
Haipeng Luo, Chen- Yu Wei, and Chung-Wer Wei Lee. Policy optimization in adversarial mdps: Improved exploration via dilated bonuses. Advances in Neural Information Processing Systems, 34, 2021.
Martin Mundhenk, Judy Goldsmith, Christopher Lusena, and Eric Allender. Complexity of finite- horizon markov decision process problems. Journal of the ACM (JACM), 47(4):681-720, 2000.
Gergely Neu. First-order regret bounds for combinatorial semi-bandits. In Conference on Learning Theory, pages 1360-1375. PMLR, 2015.
Gergely Neu and Gábor Bartók. An efficient algorithm for learning with semi-bandit feedback. In International Conference on Algorithmic Learning Theory, pages 234-248. Springer, 2013.
Gergely Neu and Gábor Bartók. Importance weighting without importance weights: An efficient algorithm for combinatorial semi-bandits. Journal of Machine Learning Research, 17(154):1-21, 2016.
Gergely Neu, András György, and Csaba Szepesvári. The online loop-free stochastic shortest-path problem. In COLT 2010 The 23rd Conference Learning Theory, pages 231-243 Omnipress, 2010.
Gergely Neu, Andras Gyorgy, and Csaba Szepesvári. The adversarial stochastic shortest path problem with unknown transition probabilities. In Artificial Intelligence and Statistics, pages 805-813. PMLR, 2012.
Gergely Neu, András György, Csaba Szepesvári, and András Antos. Online markov decision processes under bandit feedback. IEEE Transactions on Automatic Control, 59:676-691, 2014.
Christos Papadimitriou and John N Tsitsiklis. The complexity of markov decision processes. Mathematics of operations research, 12(3):441-455 1987.
Aviv Rosenberg and Yishay Mansour. Online convex optimization in adversarial markov decision processes. In International Conference on Machine Learning, pages 1478-5486 PMLR, 2019a.
Aviv Rosenberg and Yishay Mansour. Online stochastic shortest path with bandit feedback and unknown transition function. Advances in Neural Information Processing Systems, 32, 2019b.
11

---

Lior Shani, Yonathan Efroni, Aviv Rosenberg, and Shie Mannor. Optimistic policy optimization with bandit feedback. In International Conference on Machine Learning, pages 8604-8613, PMLR, 2020.
Vasilis Syrgkanis, Akshay Krishnamurthy, and Robert Schapire. Efficient algorithms for adversarial contextual learning. In International Conference on Machine Learning, pages 1159-2168 PMLR, 2016.
Tobias Sommer Thune, Nicolò Cesa-Bianchi, and Yevgeny Seldin. Nonstochastic multiarmed bandits with unrestricted delays. Advances Neural Information Processing Systems, 32, 2019.
Yuanhao Wang and Kefan Dong. Refined analysis of fpl for adversarial markov decision processes.
arXiv preprint wrXiv:2008.0925/1 2020.
Jia Yuan Yu and Shie Mannor. Arbitrarily modulated markov decision processes, In Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference, pages 2946-2953. IEEE, 2009.
Alexander Zimin and Gergely Neu. Online learning in episodic markovian decision processes by relative entropy policy search. Advances in neural information processing systems, 26, 2013.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Check the Related Work section
(especially Table 1) and the Conclusion section.
(c) Did you discuss any potential negative societal impacts of your work? [No] Pure theoretical paper.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Check the Preliminaries section.
(b) Did you include complete proof' of all theoretical results? [Yes] A sketched analysis of Theorem 4 is presented in Section 3.1 while all detailed proofs are contained in the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
12

---

5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "mJV3e2RYtDG", "reviewer": "Reviewer_Pgbo", "summary": "Motivated by the computation advantage of follow-the-perturbed-leader (FTPL) methods against the online-mirror-descent (OMD) methods, the authors consider studying the regret minimization in the adversarial Markov decision process (AMDP) with bandit feedback using FTPL. They prove that FTPL can also achieve the near-optimal regret bounds in the finite-horizon AMDP. Further, using standard loss estimators, they also prove that their algorithm can achieve the order-optimal regret in the finite-horizon Markov decision process (MDP) with delayed bandit feedback under a more simplified analysis than the OMD-based methods. Taking inspirations from previous work studying infinite-horizon communicating AMDP with full-information feedback, the authors also establish the first algorithm with a sub-linear regret guarantee in communicating infinite-horizon AMDP with bandit feedback and known transition using FTPL.", "questions": "1.\tOn page 8 line 296 – line 297, why the regret in infinite-horizon defined in Eq. (1) is “counterfactual”? I do not seem to find it “counterfactual” since the losses in the first term and the second term in Eq. (1) are evaluated on the states generated by following policy \\pi_t and some optimal policy \\pi^\\ast respectively, which are analogous to them in the regret definition of the finite-horizon MDP.\n\n2.\tAs previous works have done [6, 7], it is natural to divide the whole horizon into different epochs to learn in the infinite-horizon (discounted) MDP. However, the additional policy switching procedure in Algorithm 5 is used to adjust the state distribution and seems only to be an artifact in the analysis based on the occupancy measure. I wonder whether it is possible to learn in infinite-horizon AMDP using non-occupancy-measure-based analysis (say policy optimization [8]) to remove the policy switching procedure.\n\n3.\tWhat is the concrete hardness to equip FTPL with a delay-adapted loss estimator similar to the UOB-REPS algorithm in [1]?\n\n[6] Zhou, D., He, J., & Gu, Q. (2021, July). Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning (pp. 12793-12802). PMLR.\n\n[7] Wei, C. Y., Jahromi, M. J., Luo, H., & Jain, R. (2021, March). Learning infinite-horizon average-reward mdps with linear function approximation. In International Conference on Artificial Intelligence and Statistics (pp. 3007-3015). PMLR.\n\n[8] He, J., Zhou, D., & Gu, Q. (2022, May). Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPs. In International Conference on Artificial Intelligence and Statistics (pp. 4259-4280). PMLR.\n", "limitations": "Not applicable.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\nOriginality: Several original contributions in this work have been made. Different from most works studying regret minimization in AMDP using OMD (or a similar algorithm called follow-the-regularized-leader (FTRL)), this work considers studying the same task but using FTPL to avoid solving the convex optimization problems over the complicated occupancy measure space. Specifically, the authors point out why directly extending the analysis in existing works studying (contextual) semi-bandit fails and give their modification to overcome this problem. Furthermore, the authors also demonstrate that their algorithm can also achieve the order-optimal regret bound in the finite-horizon AMDP with delayed bandit feedback using the standard loss estimator. Besides, the regret bound of their algorithm has better dependences on the state space size S and the action space size A with a more simplified analysis compared with [1]. Using FTPL, the authors also establish the first algorithm with a sub-linear regret guarantee in communicating infinite-horizon AMDP with known transition based on the policy switching procedure in [2].\n\nQuality: The proposed algorithms and analysis are technically sound. \n\nClarity: Overall, this paper is well-organized and well-written. The authors also give sufficient comparisons of the algorithms and analysis with previous works. However, I have a question about the presentation. Please see the first question below.\n\nSignificance: The regret bound of FTPL in this paper matches the state-of-the-art bound obtained by OMD in the finite-horizon AMDP with unknown transition, is easier to analyze in the AMDP with delayed bandit feedback, and is the first sub-linear regret bound in communicating infinite-horizon AMDP with the known transition. These theoretical results in this paper are meaningful to the community in the sense that they can enable us to better understand the performance of learning AMDP using FTPL. \n\nWeaknesses\n\nNovelty: Though some contributions have been made, considering some key ingredients of the algorithms and analysis are similar to previous works (e.g., introducing the upper occupancy measure to handle the unknown transition as in [3], the policy switching procedure to adjust the state distribution after switching the policy in infinite-horizon AMDP as in [2]), it is currently not very clear whether there are additional technical challenges met and solved by the authors. I would suggest the authors give more explanations about the technical difficulties they met and how they address them. In particular, it would be better if the authors could give more discussions about the difficulty to bound the single-step stability in AMDP (Lemma 3) given the single-step stability in (contextual) semi-bandit [4], the difficulty to bound the EstReg term in AMDP with delayed feedback given the similar “cheating regret” decomposition in [5], and the difficulty to achieve the sub-linear bound of the error-term after adding T perturbations (Lemma 34).\n\n[1] Jin, T., Lancewicki, T., Luo, H., Mansour, Y., & Rosenberg, A. (2022). Near-optimal regret for adversarial mdp with delayed bandit feedback. arXiv preprint arXiv:2201.13172.\n\n[2] Chandrasekaran, G., & Tewari, A. (2021). Online Learning in Adversarial MDPs: Is the Communicating Case Harder than Ergodic?. arXiv preprint arXiv:2111.02024.\n\n[3] Jin, C., Jin, T., Luo, H., Sra, S., & Yu, T. (2020, November). Learning adversarial markov decision processes with bandit feedback and unknown transition. In International Conference on Machine Learning (pp. 4860-4869). PMLR.\n\n[4] Syrgkanis, V., Krishnamurthy, A., & Schapire, R. (2016, June). Efficient algorithms for adversarial contextual learning. In International Conference on Machine Learning (pp. 2159-2168). PMLR.\n\n[5] Van Der Hoeven, D., & Cesa-Bianchi, N. (2022, May). Nonstochastic bandits and experts with arm-dependent delays. In International Conference on Artificial Intelligence and Statistics. PMLR.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "kCAZK7Jcre", "reviewer": "Reviewer_Yxms", "summary": "This paper studies the following variations of problems of sequential learning in tabular adversarial MDP with bandit feedback: learning in episodic MDP for the setting with known and unknown transitions of MDP, learning with delayed feedback and infinite-horizon setting. The main novelty of this work is that all proposed algorithms are based on the FTPL method, which often allows to develop more computationally efficient algorithms.   ", "questions": "The analysis is clear, so I have only minor comments:\n\n- Line 9 in Algorithm 1: $\\hat{l}_{1:k-1}$ is not defined\n- Equation after line 215: $p_k(\\pi)$ is not defined ", "limitations": "The Algorithm 6 is only computationally efficient in the presence of the oracle and Algorithm 7 is computationally inefficient. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- On my opinion,  the extension of  FTPL method to the AMDP setting (without assumption on the smallest visitation probability) is an important contribution, as the proposed algorithm is much more computationally efficient than running OMD to compute an occupancy measure as it was done in the previous works for the cases of both known and unknown transitions. \n- On the technical side, Lemma 3 is a straightforward but important result as generalises the analysis of FTRL made for bandit problems to bound the regret in all considered settings. In the same time, once Lemma 3 is applied, there is no hope to get a regret bound that would be optimal in H, so in the future studies a refinement of this lemma would be needed.\n- In the delayed feedback setting the result does not improve the current state of the art, but technically it is interesting to see that the FTPL can be applied.  Moreover, the obtained regret guarantees for the Algorithm 4 are only slightly worse in a non-leading term.\n- I found the result of section 5 exiting, as this is the first result in the setting of infinite AMDP with bandit feedback, even though the obtained regret bound scales as $T^5/6$ (or $T^2/3$ for the computationally inefficient algorithm). While the authors adapt the analysis of Chandrasekaran and Tewari (2021),  they also show that their algorithm is computationally efficient under the assumption of access to the oracle. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "d2kRCCnFnM", "reviewer": "Reviewer_Lks2", "summary": "This paper analyzes the Follow-the-perturbed-leader algorithm for the episodic, adversarial MDP problem where the learner only receives bandit feedback.\n\nSeveral technical challenges are identified and solved; regret bounds for FTPL in this setting are derived and shown to be competitive with other methods (usually within a $\\sqrt{H}$).\n\nGeneralized to the delayed setting and infinite-horizon setting (the later being a first), under the slightly less general assumption of known transition dynamics but with a mild mixing requirement.\n", "questions": "Regarding novelty, it seems that, aside from the different stability assumption, the novelty of the paper is in using many tricks already present in the literature instead of a new analysis technique. I don't think that this assessment really detracts from my opinion of the paper, but am I missing something?", "limitations": "The main technical limitation, the looseness of the stability lemma, is presented with adequate discussion.\n", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The presentation and results of this paper are both very strong. On the presentation side, I found the discussion and exposition throughout very clear and very well written for an online learning audience familiar with the standard proof techniques in the literature. Focusing on the difference between the  techniques used in this paper and the techniques used in the rest of the literature works out very well and makes all the results very easy to understand. The discussion throughout really has the right balance of technical details and intuition. The organization is logical, and the paper is a pleasure to read.\n\nThe results are well positioned in the literature: they tackle a topical problem (adversarial MDP learning) and fill an obvious algorithmic hole (the use of FTPL). Connections to other algorithms, and a comparison of theoretical results via the regret bound rates, is thorough. Even though the rates aren't necessarily state-of-the-art, the extension to FTPL opens up many future directions and is significant. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1UUsR3Kqoy", "reviewer": "Reviewer_xS2b", "summary": "This paper studies the sample complexity of MDPs with adversarial reward functions and fixed transition kernel. This paper considers the settings of bandit reward feedback, known and unknown transition, and episodic and infinite horizon. Moreover, this paper also studies the delayed-reward setting. The algorithm studied in this paper is the well-known Follow the Perturbed Leader (FTPL). This paper proves that FTPL achieves sublinear regret in all these settings. ", "questions": "1. Previous works have studied mirror descent for adversarial MDP and FTPL for online bandit learning. It would be nice to better explain the novelty given these two strands of literature. \n\n2. Why the setting of adversarial MDP given in this paper makes sense -- why only assume the reward function is adversarial? \n\n3. Is it possible to modify the proposed algorithm to the setting where transition kernel is also evolving? Is it possible to obtain a dynamic regret? Is It possible to devise an algorithm with low policy switches? \n", "limitations": "The main limitation is that the transition kernel is fixed but only the reward function can change adversarially. I understand that when the transition is also adversarial, there is some negative results. But it is still possible to consider the case where the transition kernel evolves rather slowly. It would be nice to have a discussion. \n\n", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nFTPL algorithm is a popular algorithm in online learning. It is novel to show that FTPL is able to achieve sublinear regret in various RL settings. The theoretical results seem reliable. The presentation of this paper is quite clear. \n\nWeaknesses:\nIt would be nice to motivate the readers better understand why FTPL is interesting, compared to OMD or FTRL. Does it offer better regret bounds or is it easier to implement? Moreover, previous works have studied mirror descent for adversarial MDP and FTPL for online bandit learning. It would be nice to better explain the novelty given these two strands of literature. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept