Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses
Authors: Haipeng Luo
Chen-Yu Wei
Chung-Wei Lee
Venue: NeurIPS 2021 Poster (2021)
Keywords: adversarial MDP
policy optimization
bandit feedback
dilated bonuses

Abstract: Policy optimization is a widely-used method in reinforcement learning. Due to its local-search nature, however, theoretical guarantees on global optimality often rely on extra assumptions on the Markov Decision Processes (MDPs) that bypass the challenge of global exploration. To eliminate the need of such assumptions, in this work, we develop a general solution that adds dilated bonuses to the policy update to facilitate global exploration. To showcase the power and generality of this technique, we apply it to several episodic MDP settings with adversarial losses and bandit feedback, improving and generalizing the state-of-the-art. Specifically, in the tabular case, we obtain $\widetilde{\mathcal{O}}(\sqrt{T})$ regret where $T$ is the number of episodes, improving the $\widetilde{\mathcal{O}}({T}^{\frac{2}{3}})$ regret bound by Shani et al. [2020]. When the number of states is infinite, under the assumption that the state-action values are linear in some low-dimensional features, we obtain $\widetilde{\mathcal{O}}({T}^{\frac{2}{3}})$ regret with the help of a simulator, matching the result of Neu and Olkhovskaya [2020] while importantly removing the need of an exploratory policy that their algorithm requires. To our knowledge, this is the first algorithm with sublinear regret for linear function approximation with adversarial losses, bandit feedback, and no exploratory assumptions. Finally, we also discuss how to further improve the regret or remove the need of a simulator using dilated bonuses, when an exploratory policy is available.

Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses
Haipeng Luo"
Chen-Yu Wei Chung-Wei Lee (haipengl, chenyu. wei, leechung) @usc. edu University of Southern California
Abstract
Policy optimization is widely-used method in reinforcement learning. Due to its local-search nature, however, theoretical guarantees on global optimality often rely extra assumptions on the Markov Decision Processes (MDPs) that bypass the challenge of global exploration. To eliminate the need of such assumptions, this work, we develop general solution that adds dilated bonuses to the policy update to facilitate global exploration. To showease the power and generality of this technique, we apply it to several episodic MDP settings with adversarial losses and bandit feedback, improving and generalizing the state-of-the-an Specifically, in the tabular case, we obtain ((VT) regret where is the number of episodes, improving the (TT%/s) regret bound by [27]. When the number of states is infinite, under the assumption that the state-action values are linear some low-dimensional features, we obtain ((T%)) regret with the help of a simulator, matching the result of [24] while importantly removing the need of exploratory policy that their algorithm requires. To our knowledge, this is the first algorithm with sublinear regret for linear function approximation with adversarial losses, bandit feedback, and no exploratory assumptions. Finally, we also discuss how to further improve the regret remove the need of simulator using dilated bonuses, when an exploratory policy is available.'
Introduction
Policy optimization methods are among the most widely-used methods in reinforcement learning. Its empirical success has been demonstrated in various domains such as computer games [26] and robotics [21]. However, due to its local-search nature, global optimality guarantees of policy optimization often rely unrealistic assumptions ensure global exploration (see e.g., [1, 24, 30]), making it theoretically less appealing compared to other methods.
Motivated by this issue, line of recent works [7, 27, 2, 35] equip policy optimization with global exploration by adding exploration bonuses to the update, and prove favorable guarantees even without making extra exploratory assumptions. Moreover, they all demonstrate some robustness aspect of policy optimization (such as being able to handle adversarial losses or a certain degree of model mis- specification). Despite these important progresses, however, many limitations still exist, including worse regret rates comparing to the best value-based or model-based approaches [27, 2, 35), or requiring full-information feedback the entire loss function (as opposed to the more realistic bandit feedback) [7].
"Equal contribution.
In an improved version of this paper, we show that under the linear MDP assumption, exploratory policy not even needed. See https:///ariis www.wbs/210///77 .08446.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

To address these issues, in this work, we propose a new type of exploration bonuses called dilated bonuses, which satisfies a certain dilated Bellman equation and provably leads improved exploration compared to existing works (Section 3). We apply this general idea to advance the state-of-the-ie art of policy optimization for learning finite-horizon episodic MDPs with adversarial losses and bandit feedback. More specifically, our main results are:
First, in the tabular setting, addressing the main open question left in [27], we improve their ((T%/s regret to the optimal O (VT)) regret. This shows that policy optimization, which performs local optimization, is as capable as other occupancy-meatt measure-based global optimization algorithms [15, 20] in terms of global exploration. Moreover, algorithm is computationally more efficient than those global methods since they require solving some convex optimization in each episode. (Section 4)
Second, to further deal with large-scale problems, we consider linear function approximation setting where the state-action values are linear some known low-dimensional features and also simulator available, the same setting considered by [24]. We obtain the same ((T%/s regret while importantly removing the need of an exploratory policy that their algorithm requires. Unlike the tabular setting (where we improve existing regret rates of policy optimization), note that researchers have not been able to show any sublinear regret for policy optimization without exploratory assumptions for this problem, which shows the critical role of our proposed dilated bonuses. In fact, there are simply no existing algorithms with sublinear regret at all for this setting, be it satiic-ootiiizaiin-yyeee type or not. This shows the advantage of policy optimization over other approaches, when combined with our dilated bonuses. (Section 5)
Finally, while the main focus of our work is to show how dilated bonuses are able to provide global exploration, we also discuss their roles in improving the regret rate to Ö (T) in the linear setting above removing the need of simulator for the special case of linear MDPs (with ((T))) regret), when an exploratory policy is available. (Section 6)
Related work. In the tabular setting, except for [27], most algorithms apply the occupancy- measure-based framework to handle adversarial losses (e.g., [25, 15, 9, 8)), which mentioned is computationally expensive. For stochastic losses, there are many more different approaches such as model- ones [13, 10, 5, 12, 34] and value-based ones [14, 11].
Theoretical studies for linear function approximation have gained increasing interest recently [32, 33, 16]. Most of them study stochastic/stationan losses, with the exception of [24, 7J. Our algorithm for the linear MDP setting bears some similarity to those of [2, 35] which consider stationary losses. However, our algorithm and analysis are arguably simpler than theirs. Specifically, they divide the state space into a known part and an unknown part, with different exploration principle and bonus design for different parts. In contrast, episode, their algorithms first exccute an exploratory policy (from a policy cover), and then switch to the policy suggested by the policy optimization algorithm, which inevitably leads to linear regret when facing adversarial losses.
enjoy unified bonus design for all states. Besides, in each
2 Problem Setting
We consider an MDP specified by a state space X (possibly infinite), finite action space A, and transition function P with P(-|z, a) specifying the distribution of the next state after taking action in state In particular, we focus on the fnite-horizon episodic setting in which X admits layer structure and can be partitioned into Xo, Xi,..,, XH for some fixed parameter H, where Xo contains only the initial state Zo. Xи contains only the terminal state TH, and for any E X = O...., H - P(-12, a) is supported on X for all a E A (that is, transition is only possible from X₁, to X1+1). An episode refers to trajectory that starts from 2n and ends zh following some series of actions and the transition dynamic. The MDP may be assigned with a loss function e: X A - [0, 1] that (x, a) specifies the loss suffered when selecting action in state x.
policy æ for the MDP is a mapping X - A(A), where A(A) denotes the set of distributions over A and (alzz) is the probability of choosing action in state x. Given loss function {

---

and a policy x, the expected total loss of π is given by (= é) = E[ {(zn: an) an ~ Tel ((l(a)) P(- an)l It can also be defined via the Bellman equation involving the state value function V (=; E) and the state-action value function Q (x, a; () (a.k.a. Q-function) defined as below: v( 0,
(2 {) ((x, a) (( (x'x and V (a; = Bawa((1)) !Q" (zz, a; E)]
We study online learning in such a finite-horizon MDP with unknown transition, bandit feedback, and adversarial losses. The learning proceeds through 7 episodes. Ahead of time, adversary arbitrarily decides T loss functions (,, ....................... fr, without revealing them to the learner. Then in each episode I, the learner decides policy स. based on all information received prior to this episode, executes n starting from the initial state zo. generates and observes trajectory { at, (Tr,,, at,x)) ((,)))== Importantly, the learner does not observe any other information about & (a.k.a. bandit feedback).
The goal of the learner to minimize the regret, defined as
Reg- = VV min
V (zo),
1=1
where we use (x) as shorthand for (z; (x; (and similarly Q7 (z. a) as a shorthand for @"(x, az le)). Without further structures, the best existing regret bound is ((H])) [15], with extra V factor compared to the best existing lower bound [14].
Occupancy measures. For a policy и and a state æ, we define o (a)) to be the probability (or
probability measure when X is infinite) of visiting state within an episode when following When it necessary to highlight the dependence on the transition, we write as qfi (x). Further define q" (x, a) = 9tt (x) y (a(x) and qı(z, a) = gnT (z, a). Finally, we use 9² as a shorthand for dt where x* E argmin, E V (2=) is one of the optimal policies.
Note that by definition, we have (T notation and let V (3 Σx.a 9" (Jr, a))(2z, a) for any function b X A R (even though might not correspond to real loss function).
Ex.a (z, a). In fact, we will overload the
Other notations. We denote by [.[-] and Var, [.] the expectation and variance conditioned on everything prior to episode t. For matrix E and vector (of appropriate dimension), || denotes the quadratic norm V2 Ez. The notation (-) hides all logarithmic factors.
3 Dilated Exploration Bonuses
In this section, we start with a general discussion on designing exploration bonuses (not specific to policy optimization), and then introduce our new dilated bonuses for policy optimization. For simplicity, the exposition in this section assumes finite state space, but the idea generalizes to an infinite state space.
When analyzing the regret of an algorithm, very often we run into the following form:
T
T
Σ (2o) - Σ VT (zo) S o()) + ΣE (z, o(T) + Σ va (Io; v=o bt), 1=1
Reg- =
1=1
t= 2.0
(I)
for some function bz( a) usually related to some estimation error or variance that can be prohibitively large. For example, policy optimization, the algorithm performs local search each state essentially using a multi-armed bandit algorithm and treating QT (z, Q (I, a) is unknown, however, the algorithm has to use some estimator of QT (æ,, a) instead, whose bias and variance both contribute the b, function. Usually, 6,(2, a) is large for rarely-visited state-action pair (z, a) and is inversely related to qe (r, a). which is exactly why most analysis relies
the loss of action in state Since
Fuull information feedback, on the other hand, refers to the easier setting where the entire loss function & is revealed to the learner at the end of episode
3

---

on the assumption that some distribution mismatch coefficient related to q' (x.0)/a. is bounded (see e.g., [3.31]] 31)).
On the other hand, an important observation is that while V (æo; by) can be prohibitively large, its counterpart with respect to the learner's policy V ("t b.) is usually nicely bounded. For example, if (, a) is inversely related qe (z: a) mentioned, then V*a (m0;
Ez,e (0 a.bu (z, a) is small matter how small (e a) could be for some (ar, a). This observation, together with the linearity property V 4 - b,) V (20; 41) (xo; by). suggests that we treat & b, as the loss function of the problem, in other words, add (negative) bonus each state- pair, which intuitively encourages exploration due to underestimation. Indeed, assuming for a moment that Eq. (I) still roughly holds even if we treat & b, as the loss function:
Σ VT V=ooil bb)
Σ
V (woi bb) S (T) + Σ V (zo: be).
Then by linearity and rearranging, we have
T Reg- Σ Vo (Ro) - Vv. (20) 1=1
T
S ((T) + v (mo bz)-
Σ
(3)
[=1
Due to the switch from n² to We in the last term compared Eq. (I), this is usually enough to prove a desirable regret bound without making extra assumptions.
The caveat of this discussion is the assumption of Eq. (2). Indeed, after adding the bonuses, which itself contributes some more bias and variance, one should expect that b, on the right-hand side of Eq. (2) becomes something larger, breaking the desired cancellation effect to achieve Eq. (3). Indeed, the definition of b, essentially becomes circular in this sense.
To address this issue, take closer look at the policy optimization algorithm specifically. As mentioned, policy optimization decomposes the problem into individual multi-armed bandit problems in each state and then performs local optimization. This is based on the well-known performance difference lemma [17]:
Dilated Bonuses for Policy Optimization
T
Reg = (x)
D> (r((al=)=*((d) xx ( (x, 1=1
2
showing that in each state x. the learner is facing bandit problem with O," (x, a) being the loss for action Correspondingly, incorporating the bonuses b, for policy optimization means subtracting the bonus Q* (x, a; b,) from Q (xr, a) for each action a in each state x. Recall that QT (x. o; b,)
satisfies the Bellman equation QT (2r, a; by) be (2, a) + B P(-l=, P) Ba (-12²) [Be('', a') d')) To
resolve the issue mentioned earlier, we propose to replace this bonus function QT a; by) with its dilated version (s a) satisfying the following dilated Bellman equation:
Bi(x, a) bx + (1+ H P(rr [Bel'', ,a)]
(4)
(with Bi(ZH, a) 0 for all a). The only difference compared to the standard Bellman equation is the extra (1 + + factor, which slightly increases the weight for deeper layers and thus intuitively induces more exploration for those layers. Due to the extra bonus compared to Q (ar, a; by), the regret bound also increases accordingly. In all our applications, this extra amount of regret turns out to be of the form H E Ex, 4" (x)) (alx) B (2, a), leading to
E9 Σ
Σ
Te(ala) (alx)) (Q7 Be(s,a))
T ΣΣ
< (()) + (zo; b.)
4 (a)aaaa())) [=1 3.a
(5)
With some direct calculation, one can show that this enough to show a regret bound that only a constant factor larger than the desired bound in Eq. (3)! This is summarized in the following lemma.

---

Lemma 3.1. If Eq. (5) holds with Bt defined in Eq. (4), then Reg S ((T)+ V V=i(no; bb)-
The high-level idea of the proof is to show that the bonuses added to layer h is enough to cancel the large bias/variance term (including those coming from the bonus itself) from layer h + 1. Therefore, cancellation happens in a layer-by-layer manner except for layer O, where the total amount of bonus can be shown to be at most (1 + #) Ei=1 V* be) $ 3 V* V"((xo; bz):
Recalling again that (xu; be) is usually nicely bounded, we thus arrive at favorable regret guarantee without making extra assumptions. Of course, since the transition is unknown, we cannot compute B, exactly. However, Lemma 3.1 is robust enough to handle either a good approximate version of Bt (see Lemma B.1) or version where Eq. (4) and Eq. (5) only hold in expectation (see Lemma B.2), which is enough for us to handle unknown transition. In the next three sections, we apply this general idea different settings, showing what b, and B, are concretely in each case.
4 The Tabular Case
In this section, we study the tabular case where the number of states is finite. We propose a policy optimization algorithm with ((VT) regret, improving the O(T%/a) regret of [27]. See Algorithm for the complete pseudocode.
Algorithm design. First, to handle unknown transition, follow the common practice (dating back to [13]) to maintain a confidence set of the transition, which is updated whenever the visitation count of a certain state-action pair is doubled. We call the period between two model updates an epoch, and use Pk to denote the confidence set for epoch k, formally defined in Eq. (10).
In episode I, the policy ny is defined via the standard multiplicative weight algorithm (also connected to Natural Policy Gradient [18. 3, 30]), but importantly with the dilated bonuses incorporated such that Fe (alx)) x exp(-1) - (Qr a) (x, a))). Here, v) is a step size parameter, Q+ (a, a) is an importance-weighetr estimator for Q (2r, a) defined in Eq. (7), and (x, a) is the dilated bonus defined in Eq. (9).
More specifically, for state x in layer h, (z a) is defined as L.sl((2a)) 7,(n.a)+7 where 1 a) is the indicator of whether (z, a) is visited during episode t; Lr, the total loss suffered by the learner starting from layer h till the end of the episode; Te (3r,
max P a) is the largest plausible value of (x1, a) within the confidence set, which can be computed efficiently using the COMP-UOB procedure of [15] (see also Appendix C. I); and finally y is a parameter used to control the maximum magnitude of Q. a). inspired by the work of [23]. To get a sense of this estimator, consider the special case when 7 = O and the transition is known so that we can set Pa = (P) and thus 7. = q:- Then, since the expectation of Le, conditioned on (I, a) being visited is (Z a) and (z,
the expectation of 11 (1, a) is (x, a). we know that (1,,, a) is an unbiased estimator for Q (z,, a). The extra complication is simply due to the transition being unknown, forcing us to use 72 and > 0 to make sure that Qz(I, a) is an optimistic underestimator, an idea similar to [15].
Next, we explain the design of the dilated bonus B.. Following the discussions of Section 3, we first figure out what the corresponding be function is in Eq. (l), by analyzing the regret bound without using any bonuses. The concrete form of b, turns out be Eq. (8), whose value at (ar, a) is independent of a and thus written as bz(x) for simplicity. Note that Eq. (8) depends on the
occupancy measure lower bound g, (s, a) = min qº ( a), the opposite of (s, which can also be computed efficiently using a procedure similar COMP-UOB (see Appendix C. Once again, to get a sense of this, consider the special case with a known transition so that we can set PA = [P) and thus 7, q, gt. Then, one see that (z) simply upper bounded by Easx((12) (x.aa) = 3-y / (a), which is inversely related to the probability of visiting state x, matching the intuition we provided in Section 3 (that by (z) is large if is rarely visited). The extra complication of Eq. (8) is again just due to the unknown transition.
With (z( ready, the final form of the dilated bonus B, is defined following the dilated Bellman equation of Eq. (4), except that since P is unknown, we once again apply optimism and find the
We use y + shorthand for the increment operation y < y +
5

---

Algorithm Policy Optimization with Dilated Bonuses (Tabular Case)
Parameters: 8 E (0, 1), min {12AHH", !/VixIIA HT), ? 2n/l.
Initialization: Set epoch index &o = and confidence set P1 as the set of all transition functions. For all (x, a, a. initialize counters No a) (1 a) 0, No(2, a, N1 (1, (,,,,,,)))) 0.
for t 1. 1.2..... do
Step 1: Compute and execute policy. Execute n, for one episode, where
(a(a)) exp Σ (Q,(0,,)-BB((r))))
By (B.(..))))
(6)
and obtain trajectory ( de, (( ar, H111
Step 2: Construct Q-function estimators. For all h E (o...., H 1f and (I, Xn x A,
Lth Q((x,))= = (1(2,0) +7 ((
(7)
with Le, H-1 (1 max q (z. a), (x, 1(2,, 2, = a).
PEP,
Step 3: Construct bonus functions. For all (x. a) E X x A,
3yH ( (I, a) - y, (,, a))
by(x) = (112)
(8)
qe a) +7
11 1
(2(2, = be())
E
y' s'm (-(e,,) E. (a [B(('',a))
(9)
H
PEP,
where (z, = minper, Pi (x, a) and Be(IH, a) = for all a.
Step 4: Update model estimation. Yh < H. Nu & 1, aeA T. & 1.3 3h, (T 0r,x) 2 max(1, 2 (Fr, ar,n)) then
Increment epoch index A: $ 1 and copy counters: No &- NR-1, No + N
Compute empirical transition P (x(x'(z,a) = mex(())
Ne(aa,,z)) and confidence set:
Pk =P
p: P(al|o, ( - -P((''(x,))) S cconf (o'la()''a,,a)) ar,a)
(10)
V(z,a,2)) E Xn x Xh+1. 0, ...... H 1
Pn) TIXIIAI)
28 TIX
where
confi (1' conf((x'1z,d))
4V [. 3max [1
largest possible value within the confidence set (see Eq. (9)). This can again be efficiently computed; Appendix C.I. This concludes the complete algorithm design.
Regret analysis.
The regret guarantee of Algorithm is presented below:
Theorem 4.1. Algorithm/ ensures that with probability - O5), Reg = - - +H*)
Again, this improves the ((T%)) regret of [27). It almost matches the best existing upper bound for this problem, which O(H A [15]. While is unclear to us whether this small gap can be closed using policy optimization, we point out that our algorithm is arguably more efficient than that of [15], which performs global convex optimization over the set of plausible occupancy measures in each episode.

---

The complete proof of this theorem is deferred to Appendix C. Here, we only sketch an outline of proving Eq. (5), which, according to the discussions in Section important part of the analysis. Specifically, we decompose the left-hand side of Eq. (5), Be(x,,) as BIAS-1 + BIAS-2 + REG-TERM, where
the most
E. q"' (x) E. (Fe(-117) x² (11x),
BIAS-1 = En (z) (t()(() Qe(z,)) -) - (x)-))) measures the amount of underestimation of Qr related to Te, which can be bounded by E. Ez,a 9r (x)TT(alz)) (27 (2+ (a,,( (2.0))
I.(a,a)
δ (*//) with high probability (Lemma C.I);
BIAS-2 = Σz (x) E. (TT (+1x), (s; -) - Qc -)) measures the amount of overestimation of
Q related to x², which can be bounded by Ö (")n) since Qt is an underestimator (Lemma C.2);
REG-TERM = Σ> (x) >, (T<(->)) - -- (-Ix), er -) (z,x, )) is directly controlled by the
multiplicative weight update, and is bounded by 2, Ex,a 9" ("()) (,
B( H
δ (*/v) with high probability (Lemma C.3).
Combining all with the definition of b, proves the key Eq. (5) (with the o(T) term being ((H/)).
5 The Linear-Q Case
In this section, we move the more challenging setting where the number of states might be infinite, and function approximation is used to generalize the learner's s experience to unseen states. We consider the most basic linear function approximation scheme where for any π, the Q-function QT (I, a) is linear in some known feature vector ő(I, a), formally stated below.
Assumption 1 (Linear-Q)) Let őlz, a) E RRd be a known feature vector of the state-action pair (xr, a). We assume that for any episode t. policy n, and layer h, there exists an unknown weight vector 0f,, Rdd such that for all (a, (x,aa)= Xx. x A, Q (Ix a) = 6(x, a) 07 Without loss of generality, we assume [] a)ll < 1 for all (I, a) and | S vdH for all t, h, n.
For justification on the last condition on norms, see [30, Lemma 8]. This linear-Q assumption has been made in several recent works with stationary losses [1, 30] and also in [24] with the same adversarial losses.* It is weaker than the linear MDP assumption (see Section 6) as it does not pose explicit structure requirements on the loss and transition functions. Due to this generality, however, our algorithm also requires access to simulator to obtain samples drawn from the transition, formally stated below.
Assumption 2 (Simulator). The learner has access to simulator; which takes a state-action pair (x. a) E X x A as input, and generates a random outcome of the next state ~ P(-|2,, a).
Note that this assumption is also made by [24] and more earlier works with stationary losses (see e.g., [4, 28)). 5 In this setting, we propose new policy optimization algorithm with ((T%))) regret. See Algorithm 2 for the pseudocode.
Algorithm design. The algorithm still follows the multiplicative weight update Eq. (11) in each state x E Xn, (for some h), but now with Φ(x, a) 8e, as an estimator for Q (z. a) = o(z, a) T 0% and (o, x. a) as the dilated bonus B, (x. a). Specifically, the construction of the weight estimator 0.. follows the idea of [24] (which itself is based on the linear bandit literature) and is Here, Ettt is an c-accurate estimator of (7 + E,, where 7 is a small parameter and Σg = Ee[Ø(z (1 ar, (ore,, ax,x) J is the covariance matrix for layer h under policy me: Le, Σ -1 Ee ( at,;) is again the loss suffered by the learner starting from layer h. whose conditional expectation is Q (Ir,,s ar,)) o(Ie,h, ar,a)) T 0 Therefore.
defined in Eq. (12) as Ext Ó (e..t)
'The assumption in [24] is stated slightly differently (e.g.. their feature vectors are independent of the action). However, it straightforward to verify that the two versions are equivalent.
'The simulator required by [24] is in fact slightly weaker than ours and those from earlier works it only needs to be able to generate trajectory starting from zo for any policy.
7

---

Algorithm 2 Policy Optimization with Dilated Bonuses (Linear-Q Case)
parameters: B, 17, for f 1. 1.2....,7 do
21 <
2
Step Interact with the environment. Execute ny. which is defined such that for each a E X/+
<e(aaz) x exp Σ
a) On, 0n BONUs(T,2,a))
(11)
and obtain trajectory ( de ( at, (r,h)))
Step Construct covariance matrix inverse estimators.
GEOMETRICRESAMPLING (t, (t,).
(see Algorithm 7)
Gh h=0
Step 3: Construct Q-function weight estimators. For h h= = H compute
H-1
00p E ac,))
where Lib Σ
((rrss)
(12)
Algorithm 3 BO,US(L,
BoNus(t, x, a) has been called before then
return the value of BONUS (f, x, a) calculated last time.
Let be such that E X if h H then return
Compute ne (-[z)), defined in Eq. (11) (which involves recursive calls to BONUS for smaller t).
Get sample of the next state <- SIMULATOR((, a).
Compute Ne (-(2²) (again, defined in Eq. (11)), and sample an action a' ~ =2(-(=²).
return (1|o(z, alll !
+ ())))())))
(1 ++ BoNus(t,z',af)
when and approach 0, one see that 6. is indeed an unbiased estimator of 6 We adopt the GEOMETRICRESAMPLIN procedure (see Algorithm 7) of [24] to compute i, which involves calling the simulator multiple times.
Next, we explain the design of the dilated bonus. Again, following the general principle discussed in Section 3, we identify by (x( a) in this case as Bl]ob(, l) + (Eya.((1a)) (x; (Il+) for ",,
some parameter B > 0. Further following the dilated Bellman equation Eq. (4), we thus de- fine BONUS(t, x, a) recursively as the last line of Algorithm 3, where replace the expectation E(araa)) (oNUst(,, a')] with one single sample for efficient implementation.
However, even more care is needed to actually implement the algorithm. First, since the state space is potentially infinite, one cannot actually calculate and store the value of BONUS(L, Ir, a) for all (r, a). but only calculate them on-the-fly fly when needed. Moreover, unlike the estimators for Q (x, a). which can be succinetly represented and stored via the weight estimator θ.,,. this not possible for B BNNUS(t, a) due to the lack of any structure. Even worse, the definition of BONUS(t, x, a) itself depends on Te (-(az) and also Fe(- (e(-(x') for the afterstate z'. which, according to Eq. (11), further depends on BONUS(T, x, a) for 7 < f, resulting in complicated recursive structure. This is also why we present it as procedure in Algorithm 3 (instead of (ar, a)). In total, this leads to (T (TAH))(H) number of calls the simulator. Whether this can be improved left as a future direction.
Regret guarantee By showing that Eq. (5) holds in expectation for our algorithm, obtain the following regret guarantee. (See Appendix for the proof.)
Theorem 5.1. Under Assumption I and Assumption 2, with appropriate choices of the parameters 7, 8, Algorithm 2 ensures E[Reg] Ö = (dT) (the dependence [A] is only logarithmic).

---

This matches the ((T% regret of [24, Theorem 11, without the need of their assumption which essentially says that the learner given an exploratory policy start with. 6 To our knowledge, this is the first no-regret algorithm for linear function approximation (with adversarial losses and bandit feedback) when no exploratory assumptions are made.
Improvements with an Exploratory Policy
Previous sections have demonstrated the role of dilated bonuses in providing global exploration. In this section, we further discuss what dilated bonuses can achieve when an exploratory policy To is given in linear function approximation settings. Formally, let Σ, E E[ an (Z(n, T] denote the covariance matrix for features in layer h following To (that is, the expectation is taken over trajectory {(r), 4x) H-1
) with a₁ ~ To)-(z))), then we assume the following.
Assumption 3 (An exploratory policy). An exploratory policy vn is given to the learner ahead of time, and guarantees that for any h, the eigenvalues of En, are least Amin O.
The same assumption is made by [24] (where they simply let To be the uniform exploration policy).
As mentioned, under this assumption they achieve ((T%/s) regret. By slightly modifying our Algorithm 2 (specifically, executing Ty with a small probability in each episode and setting the parameters differently), achieve the following improved result.
Theorem 6.1. Under Assumptions 1, 2, and 3, Algorithm 8 ensures E[Reg] = Øly Amiia
Removing the simulator One drawback of our algorithm is that it requires exponential in H number of calls to the simulator. To address this issue, and in fact, to also completely remove the need of simulator, we further consider a special case where the transition function also has low-rank structure, known as the linear MDP setting.
Assumption (Linear MDP). The MDP satisfies Assumption and that for any and x' E Xn41, there exists a weight vector via" IRd such that P(x' [z, a) = 6(z, a)T v for all (x, a) E Xn x A.
There is surge of works studying this setting, with [7] being the closest us. They achieve Ō (T) regret but require full-informttio feedback of the loss functions, and there are no existing results for the bandit feedback setting without a simulator. We propose the first algorithm with sublinear regret for this problem, shown in Algorithm 10 of Appendix due to space limit.
The structure of Algorithm 10 is very similar to that of Algorithm 2, with the same definition of (x, a). However, due to the low-rank transition structure, we are now able to efficiently construct estimators of (2, a) even for unseen state-action pairs using function approximation, bypassing the requirement of simulator. Specifically, observe that according to Eq. (4), for each x E XA. under Assumption 4 B, (xx a) can be written as (x, a) + Φ(x, a) A where A (1 + #) Srrxx,11 Be'Nne(-la") (B(x', (x', a' "uu'" dx' is a vector independent of (x, a). Thus, by the same idea (B
of estimating 6, we can estimate A, as well, thus succinetly representing (2 a) for all (x,
Recall that estimating 07, (and thus also ATD requires constructing the covariance matrix inverse estimate Et,, Due to the lack of a simulator, another important change in the algorithm is to construct Ett, using online samples. To do so, we divide the entire horizon into epochs with equal length, and only update the policy optimization algorithm at the beginning of an epoch. Within an epoch, we keep executing the same policy and collect several trajectories, which are then used to construct Σtt, With these changes, we successfully remove the need of a simulator, and prove the guarantee below.
Theorem 6.2. Under Assumption 3 and Assumption 4, Algorithm 10 ensures TE[Reg] Ö (7*/) (see Appendix F for dependence on other parameters).
One potential direction to further improve our algorithm is to reuse data across different epochs, an idea adopted by several recent works [35, 19] for different problems. We also conjecture that
Undde an even strong assumption that every policy is exploratory, they also improve the regret to (VTT):
see [24, Theorem 2].

---

Assumption can be removed, but we meet some technical difficulty in proving so. We leave these for future investigation.
Acknowledgments and Disclosure of Funding
We thank Gergely Neu and Julia Olkhovskaya for discussions the technical details of their GEOMETRICRESAMPLING procedure. This work is supported by NSF Award IIS-1943607 and Google Faculty Research Award.
References
[1] Yasin Abbasi-Yadkorts Peter Bartlett, Kush Bhatia, Nevena Lazic, Csaba Szepesvari, and Gellért Weisz. Politex: Regret bounds for policy iteration using expert prediction. In International Conference on Machine Learning, pages 3692-3702, 2019.
[2] Alckh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. Pe-pg: Policy cover directed exploration for provable policy gradient learning. In Advances in Neural Information Processing Systems, 2020.
[3] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approxi- mation with policy gradient methods in markov decision processes. In Conference on Learning Theory, pages 64-66, 2020.
[4] Mohammad Gheshlaghi Azar, Rémi Munos, and Bert Kappen. On the sample complexity of reinforcement learning with generative model. In International Conference Machine Learning, 2012.
[5] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272, 2017.
[6] Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In International Conference on Artificial Intelligence and Statistics, 2011.
[7] Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang, Provably efficient exploration in policy optimization. In International Conference on Machine Learning, pages 1283-1294, 2020.
[8] Liyu Chen and Haipeng Luo. Finding the stochastic shortest path with low regret: The adversarial cost and unknown transition case. In International Conference Machine Learning, 2021.
[9] Liyu Chen, Haipeng Luo, and Chen- Yu Wei. Minimax regret for stochastic shortest path with adversarial costs and known transition. In Conference On Learning Theory, 2021.
[10] Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed-horizon reinforce- ment learning. Advances in Neural Information Processing Systems, 2015.
[11] Kefan Dong, Yuanhao Wang. Xiaoyu Chen, and Liwei Wang. Q-learning with ueb exploration is sample efficient for infinite-horizon mdp. International Conference on Learning Representations, 2020.
[12] Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient bias-span- constrained exploration-explootatio in reinforcement learning. In International Conference on Machine Learning, pages 1578-1586, 2018.
[13] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(4), 2010.
[14] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is Q-learning provably efficient? In Advances in neural information processing systems, pages 4863-4873 2018.
10

---

[15] 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 Machine Learning. 2020.
[16] Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137- 2143, 2020.
[17] Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In In Proc. 19th International Conference Machine Learning. Citeseer, 2002.
[18] Sham M Kakade, natural policy gradient. Advances in neural information processing systems, 14, 2001.
[19] Nevena Lazic, Dong Yin, Yasin Yadkor,, and Csaba Szepesvari. Improved regret bound and experience replay in regularized policy iteration. In International Conference on Machine Learning. 2021.
[20] Chung- Wei Lee, Haipeng Luo, Chen- Yu Wei, and Mengxiao Zhang. Bias no more: high- probability data-dependent regret bounds for adversarial bandits and mdps. Advances in Neural Information Processing Systems, 2020.
[21] Sergey Levine and Vladlen Koltun. Guided policy search. In International conference machine learning. pages 1-9, 2013.
[22] Haipeng Luo. Lecture 2, introduction to online learning, 2017. Available at https:
/ //haipeng- luo. net. /ete///oooce//////ttt//////ee//p
[23] Gergely Neu. Explore no more: Improved high-probabiiityy regret bounds for non-stochastic bandits. In Advances Neural Information Processing Systems, 2015.
[24] Gergely Neu and Julia Olkhovskaya, Online learning in mdps with linear function approximation and bandit feedback. arXiv preprint arXiv:2007.01612, 2020.
[25] Aviv Rosenberg and Yishay Mansour. Online convex optimization in adversarial Markov decision processes. In Proceedings of the 36th International Conference on Machine Learning. 2019.
[26] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
[27] Lior Shani, Yonathan Efroni, Aviv Rosenberg, and Shie Mannor. Optimistic policy optimization with bandit feedback. In International Conference Machine Learning, pages 8604-8613 2020.
(28) Aaron Sidford, Mengdi Wang, Xian Wu, Lin F Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving markov decision processes with a generative model. In Advances in Neural Information Processing Systems, pages 5192-5202, 2018
[29] Joel Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computa- tional mathematics, 12(4):389-453 2012.
[30] Chen-Yu Wei, Mehdi Jafarnia Jahromi, Haipeng Luo, and Rahul Jain. Learning infinite-horizon average-reward mdps with linear function approximation. In International Conference on Artificial Intelligence and Statistics, pages 3007-3015, 2021.
[31] Chen- Yu Wei, Mehdi Jafarnia Jahromi, Haipeng Luo, Hiteshi Sharma, and Rahul Jain. Model- free reinforcement learning in infinite-horizon average-rewand reward markov decision processes. In International Conference on Machine Learning, pages 10170-10180, 2020.
[32] Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pages 10746-10756. 2020.
11

---

[33] Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Conference on Artificial Intelligence and Statistics, pages 1954-1964, 2020.
[34] Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304-7312, 2019.
[35] Andrea Zanette, Ching-An Cheng, and Alekh Agarwal. Cautiously optimistic policy optimiza- tion and exploration with linear function approximation. In Conference on Learning Theory,
2021.
12


Reviews:
[{"review_id": "zO0Q1o8Ml5M", "reviewer": "Reviewer_AzMT", "summary": "This paper makes several contributions: \n\t\n1. In the episodic tabular setting, with adversarial rewards, unknown MDP dynamics and bandit feedback, it provides the first algorithm that achieves O(\\sqrt T) regret bound using the regret decomposition approach, which is more computationally cheap than the approach presented in Jin et al. Typically result obtained by using this approach scales with the inverse of the visitation probability. However, here the results don't have this drawback.  \n\t\n2. For the linear case, the paper considers the setting with an infinite set of states and the algorithm has access to the simulator of the dynamics of MDP. Then it provides the algorithm that obtains T^2/3 regret without assuming that the smallest eigenvalue of the covariance matrix \\Sigma_h is at least \\lambda_min and T^1/2 taken this assumption. The latter improves the previous result in the considered setting, which was T^2/3 regret, assuming that the smallest eigenvalue of \\Sigma_h is bounded away from zero. The only drawback is that the algorithm is more computationally expensive since it requires O(T^H) number of calls to the simulator.\n\t\n3. The third result presented in the paper is in the same setting as above but without access to the simulator of MDP, which is a very challenging setting. The obtained regret bound is T^6/7, and it makes use of the assumption on the smallest eigenvalue of \\Sigma_h.\n\n4. All three results from above make use of dilated bonuses, which is the main contribution of this paper. \nThe use of the dilated bonuses that decrease the contribution to the regret, induced by the term appearing from the mismatch of q^*(x) and q(x), shows up in the analysis. To the best of my knowledge, this idea has not been considered before, and I think this idea is beneficial for future studies. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\t\n- The authors state that it is important to remove the use of an exploratory policy by the algorithm. Is there an argument why it is important and why it is better to be replaced by regularization of covariance matrix? Also, is there a technical reason why implicit exploration works better? \n\t\n-  Introducing the loss estimate for the tabular setting, it worth mentioning EXP3-IX algorithm for adversarial multi-armed bandits. \n\n- Would the dilated bonuses work the same way for the REPS approach?  \n\n- Can the result of the Theorem 6.2 be improved by assuming that the comparator policy plays actions uniformly with some probability? \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no potential negative societal impact", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "sFtc8W7kB4", "reviewer": "Reviewer_9Q9q", "summary": "The paper studies reinforcement learning in adversarial MDPs with policy optimization algorithms. Using a novel bonus design, the new algorithms achieve $\\tilde{O}(S\\sqrt{AT})$ regret in the tabular case, and $\\tilde{O}(T^{2/3})$ regret in the linear function approximation case, assuming access to a simulator, significantly improving known results.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The key algorithmic idea of this paper is the following observation: suppose the regret with respect to $l_t-b_t$ can be bounded the loss of the optimal policy on $b_t$ (which can be large), one can cancel this term via linearity and bound the target regret with the loss of $\\pi_t$ on $b_t$ (which can be controlled using standard techniques). This however requires $b_t$ to be designed in a \"circular\" fashion, which the authors resolve by using dilated bonuses. The new regret decomposition and bonuses are novel and interesting.\n\nIn the tabular case, the main result is an $\\tilde{O}(H^2S\\sqrt{AT})$ upper bound, which improves existing upper bound for policy optimization methods. Although it is one $H$ factor away from the current best result for adversarial MDP with bandit feedback [Jin et al. 2020], it enjoys a better computational efficiency. In the linear function approximation case, the first result is an $\\tilde{O}(T^{2/3})$ regret bound assuming access to a simulator, which is the first known sublinear result of its kind. Although access to a simulator is usually a strong assumption, it can be justified since it is required by existing work on adversarial MDPs or even stochastic MDPs [Lattimore et al. 2020]. Other results include a $\\tilde{O}(\\sqrt{T})$ rate assuming an exploratory policy, and a $\\tilde{O}(T^{6/7})$ rate assuming exploratory policy and linear MDP (but removing the need of a simulator). The exploratory policy is also a strong assumption, but is also assumed in existing work to achieve sublinear regret in adversarial linear MDPs. Overall the results of this paper seem to be solid contributions to the existing literature.\n\nOther comments:\n\n- The number of queries to the simulator is larger than $A^H$ but is not reflected in the regret bound, which is different from the stochastic settings where queries to the simulator is regarded as the sample complexity. In stochastic MDPs, with $A^H$ samples of uniform exploration, one can already evaluate any policy via Monte Carlo. The reason why this doesn't help in adversarial MDPs seems to be that the simulator does not return reward information. This makes one feel that the role of simulators in adversarial MDPs with linear function approximation (with bandits feedback) is a bit odd: the algorithm cannot extract reward information (as per Assumption 2) and cannot learn the dynamics as the state space can be infinite.\n\n-  If the state space is finite and if one allows an infinite budget of queries, one may treat the dynamics as known and evoke existing results (e.g. [Neu et al. 2010]) whose regret bound are independent of the number of states. Thus there seems to be a trade-off between simulator query complexity and online regret, and it would be interesting to know where $A^H$ is positioned in this trade-off.\n\n- In the algorithm box of Algorithm 2, the reference to Algorithm 6 should be Algorithm 7.\n\n-------\nNeu et al. The online loop-free stochastic shortest-path problem. 2010.\n\nLattimore et al. Learning with Good Feature Representations in Bandits and in RL with a Generative Model. 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is purely theoretical and do not present foreseeable negative social impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "PrTEqBWAvWR", "reviewer": "Reviewer_9Bif", "summary": "This paper introduces a new bonus design mechanism, and utilizes it to derive new policy optimization algorithms with improved rates for adversarial MDPs. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is an interesting paper for the following reasons.\n\n1. The paper is well written. The mechanism of the  bonus design and its technical motivation is clearly explained in Section 3. \n\n2. Implementing the dilated bonus on tabular MDPs gives a new policy optimization algorithm with $\\sqrt{T}$-regret, which improves over Shani et al., 2020. All other known algorithms with the same rate [e.g., Jin et al., 2020a] requires solving a large-scale convex optimization problem over the occupancy measure per episode, while the algorithm in this paper doesn’t because of its clever ‘local’ bonus design. I checked the proofs for Section 3&4 in details, and I believe they are correct.\n\n3. The authors further apply their bonus technique to adversarial linear MDPs and obtain improved results over prior arts.\n\nOverall, this paper made solid technical contributions by designing more efficient algorithms with improved rates. \n\nMinor suggestion on related works:\n\nThe idea of adding $\\gamma$ in the denominator of $\\hat{Q}$ is actually first proposed in [1], which not only encourages exploration but also makes it possible to obtain high-probability bounds. If I remember correctly, [1] also proves some lemma that is highly similar to Lemma A.2 in this paper. \n\n[1] Explore no more: Improved high-probability regret bounds for non-stochastic bandits, Gergely Neu, NIPS 2015.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is purely theoretical. I am not aware of any potential negative societal impact.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "2H9iQdt7wX_", "reviewer": "Reviewer_GhdY", "summary": "The paper studies the regret of policy optimization for adversarial MDPs with bandit feedback. It develops a general solution that adds dilated bonuses to the policy update for exploration and applies the algorithm to the tabular, linear-Q, and linear MDP settings.   It shows that such a solution improves and generalizes the state-of-the-art.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- (+) For the tabular setting, the paper improved the regret analysis to $O(\\sqrt{T})$ with dilated bonus. The idea is novel and the theoretical contribution is solid.\n\n- (+) For the linear-Q setting, the paper establishes a regret of $O(T^{2/3})$ with the assumption on the existence of a simulator and $O(T^{1/2})$ with an exploratory policy. The assumptions are weaker than the previous work. The theoretical contribution of this part is solid.\n\n- (+) The paper also provides regret for linear MDP without a simulator.\n\n- (+) The mechanism of the dilated bonus is well discussed in Section 3.\n\n\n- (-) The notation of $Q(x_h, a)$ and $V(x_h) $ are used without specification.  Such notations of value functions with specifying the timestep $h$ by subscription of $x$ is confusing. I suggest the authors to use e.g., $V(x, h)$ and $Q(x, a, h)$.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "- The paper can include a table of the comparison of this work with previous works.\n\n- The paper does not provide any empirical study to show that the dilated bonus works better. I understand this paper focuses on the theory but some toy examples could be helpful to show the benefit of the dilated bonus.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes some interesting technical tools for online learning in MDPs with adversarial rewards, improving existing results in tabular MDPs and large-scale MDPs under realizable linear function approximation and bandit feedback. All reviewers appreciated the clear improvement over previous results and the novelty of the technical contribution, with some expert reviewers opining that the proposed techniques are likely to inspire future work in the field. Based on my own reading, I concur with this assessment and agree that the paper should definitely be accepted for publication at the conference.
Decision: Accept (Poster)