Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback
Authors: Haolin Liu
Chen-Yu Wei
Julian Zimmert
Venue: ICLR 2024 spotlight (2024)
Keywords: adversarial MDPs
policy optimization
bandit feedback
Primary area: reinforcement learning
TL;DR: We study online reinformencent learning in adversarial linear MDPs, proposing the first rate-optimal inefficent algorithm and an efficient algorithm that significantly improves prior results.

Abstract: We study online reinforcement learning in linear Markov decision processes with adversarial losses and bandit feedback. We introduce two algorithms that achieve improved regret performance compared to existing approaches. The first algorithm, although computationally inefficient, achieves a regret of $\widetilde{O}(\sqrt{K})$ without relying on simulators, where $K$ is the number of episodes. This is the first rate-optimal result in the considered setting. The second algorithm is computationally efficient and achieves a regret of  $\widetilde{O}(K^{\frac{3}{4}})$ . These results significantly improve over the prior state-of-the-art: a computationally inefficient algorithm by Kong et al. (2023) with $\widetilde{O}(K^{\frac{4}{5}}+1/\lambda_{\min})$ regret, and a computationally efficient algorithm by Sherman et al. (2023b) with $\widetilde{O}(K^{\frac{6}{7}})$ regret.

TOWARDS OPTIMAL REGRET IN ADVERSARIAL LIN- EAR MDPS WITH BANDIT FEEDBACK
Haolin Liu'r, C
Yu Wei' Julian Zimmert
1 Department of Computer Science, University of Viginia, 2 Google Research (srs8rh, sEwsen)evirginiz edu (zimmert] @googll com com
ABSTRACT
We study online reinforcement learning in linear Markov decision processes with adversarial losses and bandit feedback, without prior knowledge on tramsitions or access to simulators. We introduce two algorithms that achieve improved regret performance compared to existing approaches. The first algorithm, although com- putationally inefficient, ensures a regret of Ö(VK), where K is the number episodes. This is the first result with the optimal K dependence in the consid- ered setting. The second algorithm, which is based on the policy optimization framework, guarantees a regret of O(K%/ and is computationally efficient. Both our results significantly improve over the state-of state-of-the-art: computationally inef- ficient algorithm by Kong et al. (2023) with O(K's + poly()/Amiu) regret, for some -edeedeedd constant Amin that can be arbitrarily close to zero, and computationally efficient algorithm by Sherman al. (2023b) with OKK/r) regret.
INTRODUCTION
We study finite-horizon online reinforcement learning in large state space with adversarial losses amd bandit feedback. We assume the linear Markov decision process (MDP) structure: every state- action pair is equiped with a known feature representation, and both the transitions and the losses can be represented as a linear function of the feature. This problem has received significant at- tention recently, with fairly complete results when the agent has access to a simulator query transitions of the MDP (Dai et al., 2023). In the much harder simulator-free setting, the pioneer- ing work of Luo et al. (2021) showed that no-regret (K22/15 regret) is possible, where is the number of episodes. Several followup works have successively improved the K dependence (Dai et al., 2023; Sherman et al., 2023b; Kong et al., 2023), with the state-of-the-ar being Kong et al. (2023)'s / + poly 11//mii) regret through computationally inefficient algorithm, and Sherman et al. (2023b)'s ' k regret through a computationally efficient algorithm. Still, there remain signif- icant gaps between the current upper bounds and the VK lower bound. this work, we push the frontiers both the information thcoretical limits and the achievable bounds under computational constraints: 1) we present the first (computationally inefficient) algorithm that provably obtains Ō(VK) regret, showing that this is the minimax K dependence (Section 3); 2) we obtain Ö O(K% %/a)) regret with a polynomial-timm algorithm (Section 4). Below, we briefly describe the elements in our approaches. The comparison of our algorithms with previous works can be found in Appendix A.
Inefficient VK algorithm. We convert the linear MDP problem to a linear bandit problem by mapping each policy to single -ii-dimensional feature vector, where d is the ambient dimension of the linear MDP and H is the horizon length. The challenge is that this conversion depends on the transition of the MDP, which is not available to the learner. Therefore, the learner has to estimate the feature of every policy during the learning process. Previous work in this direction (Kong et al., 2023) faced obstacles in controlling the estimation error and was only able to show a K/6 + pooy(1//mma))) regret bound assuming there exists an exploratory policy inducing a covariance
"The authors are listed alphabetical order.

---

matrix = Am We addressed the obstacles through 1) state space discretization (Section 3.2), and 2) model-free estimation for the occupancy measure policies over the discretized state space (Section 3.3). These allow to emulate the success in the tabular case (Jin et al., 2020a) and obtain the tight v K regret.
Efficient K algorithm. The efficient algorithm is based on the policy optimization framework (Luo et al., 2021). Different from previous works that all use exponential weights, we use Follow- the- Regularized-Leaateeeee (FTRL) with log-determinant (logder) barrier regularizer to perform policy updates, which has the benefit of keeping the algorithm more stable (Zimmert and Lattimore, 2022; Liu et al., 2023a). We carefully combine logdet-FTRL with existing algorithmic/analysis techniques to further improve the regret bound. These include 1) an initial exploration phase to control the transition estimation error (Sherman al., 2023a), 2) optimistic least-square policy evaluation in bonus construction (Sherman et al., 2023b), 3) dilated bonus construction (Luo et al., 2021), and 4) tighter concentration bound for covariance matrix estimation (Liu et al., 2023a).
We defer detailed comparisons with the literature to Appendix A.
PRELIMINARIES
No- No-Regret Learning in MDPs. An (episodic) MDP specified by a tuple M (S,A, A P) where
S is the state space (possibly infinite). A is the action space (assumed to be finite with size A = [A). P: S x + A(S) is the transition kernal. The state space is assumed to be layered, i.e. S = S U2 U. .... Sh where Sn n Sn Ø for any 1 I h < h < HI and transition is only possible from one layer to the next, that is, P(s' s, a) + 0 only when E Sh, and E SSt1- Without loss of generality, we assume S {s1}.
We consider a process where the learner interact with the MDP for K episodes, each time with a different loss function. Before the game starts, adversary arbitrarily chooses the loss functions for all episodes (4g- S x A - [0, 1) and does not reveal them to the learner. For each episode k E [K]. the learner starts state $2,1 $1; for each step h E [H] within episode k after observing the state SA,A E Sn, the learner chooses an action a E A, suffers and observes the loss &x (8R,,, (g.h) and transits a new state 8 sampled from the transition P(- 8k,A, ag.h).
A policy π is mapping from S to (AA). The state-value function (or V-function in short) V* 2) the cumulative loss starting from state s, following policy π and under loss function L. This formally defined as the following for e Sn:
(s; E
Σ E(sw, axe) LNn=h
8h s, an T(. sw), SM41 P(. sw, aa)), Ah 2
The action-value function (a.ka. Q-function), on the other hand, the expected loss suffered by a policy starting from given state-action pair (s, a). Formally, we define for all (s, E S x A:
(" a; e) ((s, a) + L[s & SH] EgsP(()aa)) (v*(s';))
Let Th be the policy used by the learner in episode k. The learner aims to minimize the regret with respect the best fixed policy, defined
Definition 1 (Regret). RK= A BEA EK= VTA (x) min, Σ (=(si(())
Occupancy measures. For a policy и and state we define 1 (s) to be the probability of visiting state within an episode when following n, which can written as (T) V (s 8,)) with (, ((s',a)) a') = 14 = =}. Further define y² n² (s)r((s)). By definition, we have V (m(1;)) E) = E.oe EneA 1d (8, ()).).)
2.1 LINEAR MDP
Linear MDP is formally defined as follows.
For readability, throughout the paper, we summation over states instead of integration. Technically, all results hold for of continuous and infinite state space.
2

---

This can be Definition 2 (Linear MDP). In linear MDP, each state-action pair (s,a) 3) is associated with known feature o(s, a) I with [ a)ll $ 1. There exists a mapping v S t IR such that the transition can be expressed as
P( s,a) (é(s, a), V(s,a,s') U Sh A Sh+1-
Here, ve is unrevealed to the learner. Moreover, for any episode l [K] and any layer [H], there exists (hidden) vector 0u. E R such that
(x) = (0(8, 0k, V(s,a) E S, x A
(3)
Following previous work, assume Eees, (ss)ll22 S vd (the absolute value is element-wise) and ||0 S for all k, h.
| over vector
We also define misspecifeid linear MDPs, which is used in Section Definition (Misspecified Linear MDP). A (-misspecified linear MDP follows all the assumptions in Definition 2 except that Eq. (2) and Eq. (3) are respectively modified to
|P s,a) (Ø(s, a), (.M1 S
and ((x(s,a) - (o(s, ax,)) sc.
(4)
RATE-OPTIMAL ALGORITHM
The aim of this section to show that there is no statistical barrier to obtaining VK regret for linear MDPs with bandit feedback and adversarial losses. The proposed algorithm is computationally inefficient and remains an open question if the same can be achieved with an efficient algorithm.
3.1 SOLUTION IDEAS
Observe that the expected loss of policy क in episode k can be written as E.es EneA (s, (), = Eh' ExES, Enca nr (s, a)o(s, a) T0 further written as "0",0u) where
== (0 ( H), O2 (Ok,1,...,,Ok. Ok,H): with Oズ ΣΣ
nr as)))) BES aEA
In other words, the adversarial linear MDP problem can viewed as an adversarial linear bandit problem with (ren the underlying action set. Therefore, if computation is not an issue (i.e.. we are allowed to run linear bandits over an exponentially large action set), the only additional challenge in linear MDPs is that (o") is not known in advance and the learner must learn the transition to estimate them. This viewpoint has been taken by Kong et al. (2023) to design com- putationally inefficient algorithms with improved regret bounds. To estimate (db")))) Kong al. (2023) use an initial pure exploration phase to estimate d= up to an accuracy of e for all æ, and then run e-misspecified linear bandit algorithm over policies in the second phase. Their approach gives K/ + poly( \/m...) regret.
A natural idea to improve the regret bound is to estimate (0")ren on the fly instead in a sep- arate initial phase. That is, directly start linear bandit algorithm. Then during the leamn ing process, for policies that are more often used by the learner, their d² estimation will be- come more and more accurate, and for others, larger error allowed. Intuitively, this better bal- ances exploitation and exploration because the learner will not spend too much efforts in estimat- ing o² for bad policies. However, there are technical difficulties in doing so. Recall that 0% Eses, EaEA nM (s) a). To estimate this, the learner needs to first estimate n² A natu- ral estimator fot would defined recursively as (s') = E.es, ΣaEA A (s))(als))(((((s. for s' E Sk+1, with the transition estimator P obtained from linear regression: P(5'|s, a) a(s,a)T (An EBa..EE 0(3, a) =s')) where DA consists of historical data of the form (8,0,8) E Sr, x A x Sh+1 and A I + Σ (s,,,))) (s,a)o(s,a) This is the exact idea

---

of Kong et al. (2023). Notice that the f obtained in this way may not be valid, i.e., they may not satisfy n (-) E ((S). Their approach suffers from the issue that it is difficult to control the magni- tude of A² (s) when the amount of data in D is still small. This is why they an initial phase to explore all directions in the feature space and control the error || o uniformly for all policies.
However, "on-the-fly fly estimation" without the initial phase has been proven to work in the tabular case (Jin et al., 2020a) to get a vK regret. The key difference between the tabular case and the linear case is that the transition estimator P in the tabular case is always a valid transition (i.e., P(-|s, a) E A(S)), and thus the induced occupancy measure estimator ja is also always valid. This avoids the aforementioned technical difficulty.
With this observation, we propose to incorporate the constraint that å be a valid occupancy measure when dealing with linear MDPs. To find such a ji= we search over the space of valid occupancy measures and pick one that is consistent with the past data. This is different from the approach of Kong al. (2023), where P is obtained via linear regression over the past data first, and then å² is derived from it, which can fail to be valid.
Since the state space and policy space can both be infinite, in order to get runnable algorithm for finding j (s), we discretize both the state space and the policy space. These are described in the next subsection.
3.2 THE DISCRETIZATION PROCEDURES
Discretization of the state space. For linear MDPs, we can assume that state s is uniquely defined by its action feature set A, = { a) E A]. If there are distinct states with identical feature sets, we can collapse them into single state by combining their (b()).
In order to approximate an infinite-state linear MDP as a finite-state MDP, we perform discretiza- tion for the entire feature space (1). To decide the discretization resolution, assume that Φ(s, s) the true feature and d((ssa) a) its approximation, and [| a) - (s(sa))l2 S 6 for all 8, a. Then we have [|P(-|s, a) (()lll))ll++<s)))) S E.E. [s))(')) S < (x))'') S Sv (ss'llll S ed and (s) - (s, a), Ou,n)l = (d'(s, ((5, a), OR.N) < lo(ss,)) o(s 2)]22||0x. l.l S <v by Definition 2. Thus, the MDP with o'(s.a) a) as the underlying feature with misspecification error ( = ed by Definition 3. It turns out that it suffices to set 1 and make the misspecification error Ç z. The number of states after the discretization is upper bounded by (size of e-net of the feature space) (1/e)o(dHA)
as)s))
([((ss,) a) d' dd((s,),,
(-))il S E.. [|((s, a)
misspecified linear MDP
K
(O(dHA),
There is caveat when working with this discretized state space. Since the true feature space t (ő(s.a) a) s S S,a E A} may not cover the entire (1). the state space construction above (i.e.. by discretizing the whole (1)) may produce states that do not really exist. In fact, there is no problem viewing these non-existing states as part of the state space because their vsss can be set to zero, making them unreachable under the linear MDP assumption. The only thing we have to be careful about is that the assumptions Eq. (2), Eq. (3), Eq. (4), and their implications, such as -SS (Ø, (ss)) < 1+ and (e, dk,,)) < 1 1++5 are only guaranteed for & in the true feature space T. but not for the whole feature space B (1). To avoid ambiguity, we use notation S to denote the set of discretized states from the true MDP, and use X' to denote the set of discretized states constructed from the entire (1). Apparently, S X. We clarify that, 1) the learner knows X, but does not know S before interacting with the environment, 2) the misspecified linear MDP assumption Eq, (4) is only guaranteed for @(s, a) with s E S, 3) X' ) S are unreachable states and their (88)) are set to zero. We use (2)) ( to denote partitions of X' on different layers.
Discretization of the policy space. We consider a discretization of the policy space for Algo- rithm 2. The policy class is the set of linear policies defined as
T8
0 E "
(g(s)) = argmin ((*, To, for a E Xn aEA
(5)
where is an 1-net of (K)) The next lemma shows that this policy set contains a near optimal one. See Appendix B.1 for the proof.
4

---

Algorithm EstOM (Di) (Estimate Occupancy Measure)
Input: target policy n, historical data (Di) where Dn. consists of tuples a, 8') E Sn. Ax x S with s' ~ p())s.a).
Find (f+ (s)) [0, 1] and (EI1 C (vdd that satisfy the following for all h and all f E F" (recall the definition of f in Eq. (6), and in Section 3.2).
[M]
E (*)))) sEA,
Σ (F())((6))
ΣΣ
pT (s)a((ass)) clip (a SC
(8)
SEAr
18d K
Σ (f(S) ((),a)) En,s)²
min (EB*(VA) (e...)))D
E
- ((())-((xsd)) I 16d log 8
Output: (8)ssx) (if Eq. (7)-Eq. (9) not feasible, output any solution that satisfies Eq. (7)).
Lemma 4. For any policy X A(A) and any sequence of losses ((s.))e((M) there exists 0 S vdH2
pollic x' E such that Ek=1 E Exes, EcEA(n (s, - (8, (s) (s)(s (Ta(s,,))),aAA
3.3 ESTIMATING (s)
With the state space discretized, we are now faced with a finite state problem. To estimate p², a po- tential way find transition estimation (P(s')s, a))x.a,'' which consistent with the historical data and satisfies the constraint that the ftt induced by P is a valid occupancy measure. The issue of this is that since P(s'|s, (s, a) ((8,a) T *b(s",, this method requires to estimate vb(s") for all s', whose complexity will scale with (S] because (b(s') ) for different s' are unrelated. Indeed, as noted by previous works (Foster et al., 2023), the linear MDP model does not allow efficient model-based estimation.
Inspired by previous model-free approaches for linear MDPs (Jin et al., 2020b), instead of estimating (s'), we will directly estimate Ev (ss))((s)) for class of functions f that is rich enough for our purpose (i.e., to estimate (6") (re well). This class of functions turns out can be chosen Unen F" where F FT U.2 and
F
f(s)= = Σ x(ass) clip [ō(s,
[)T] for some 0 e BB
aEA
F
f(8) = Σ
[(a|s)]lo[s, a)Ilr for some P with 0 OTTII (6)
aEA
where we define clip[a] max(min(o,,), 1), 11. Given historical data (Di) which consists of (s, a, s') tuples, our way of obtaining A summarized Algorithm In Algorithm 1, Eq. (7) sets the constraint that AT is a valid occupancy measure, Eq. (9) requires that Én. approximates Sh.r = Ex'Es ('s') (s') well on the historical data (Dx) and Eq. (8) relates fo with Én.
according their definitions. In the following Lemma with high probability. Then in Lemma 6, we show the key property that faM is close to n² when evaluated on any F=. The proofs of Lemma 5 and Lemma 6 can be found in Appendix B.2. Below, we define 2.T (s. = p." (s)((()s)))
show that Eq. (7)-Eq. (9) is feasible
Lemma 5. With probability at least
x. Eq. (7)-E4. (9) is feasible for all a E IT.
5

---

Lemma 6. Let (s))aE) be the output of Algorithm 1. Then with probability least 1 f-ror any TI and all f E F", (x (it (s) n²t (s)) is upper bounded by
18d K
10d
log
Σ
min
Σ Σ BERN aEA
n" (s, [(((sa)llo(s:)))))
Ep + 2CH
8
Mch
sEA aeA
where Ap I I+ (ea,,))) ((s.a))(s.a)*.
3.4 ALGORITHM: EXPONENTIAL. WEIGHTS
From Section 3.3, we know how to obtain the estimation for (n²) "ren- Now we can use them to construct estimators of (Ø") FEE via कズ E.Ex, Eeea ftt (s)T(a|s))(ss a), and run linear bandit algorithm viewing (Ø* TE as actions. The algorithm is presented Algorithm 2. At the call EsOOM (Algorithm 1) for all policies with the data up to
beginning of each episode k, episode k - 1 (Line 5). This returns the occupancy measure estimator Pi for all я, which we can use to construct the feature estimator oz. Then use the standard exponential weight together with John's exploration to update the distribution over policies. To deal with the bias induced by the estimation eтror of 6% we incorporate a bonus term bg in the update. Similar ideas have also been used in, e.g., Luo al. (2021); Sherman al. (2023b); Dai et al. (2023); Kong et al. (2023); Liu et al. (2023a). We defer the regret analysis of this algorithm to Appendix B.3, and only state the final guarantee in the next theorem.
Theorem 7. The regret of Algorithm is bounded by Rr S ((VCHiK)
Algorithm 2 Exponential Weights
1: Let 11 be the policy set defined in Eq. (5). Let min K ) 2nн
2: For all h E [H] DI,h + 9, A1, I.
3: for k 1, 1,2..... do
4: For all ı E IT, let ih = EstOM(T, (Dr,) (call Algorithm 1).
5: Define dū ΣsEx, Ef (s)((()))) a) and oī (Ør (0 0T,n).
6: Compute Qs E (III as qu(1t (T) x exp (-n (0 0, b7 ))
7: Let de = (1 (1-7)/m 7Js where Ja A(TT) is John's exploration over ( Ten-
8: Sample TE ~ l2. execute Th: and obtain trajectory (SK,1, 0g,1, l..,...., H, Og. (x
10d H log 18d2
9: Define for Obanus
M Σ (TM)
0x Lks
where L
Σ lk
H
bg = Chomus
ΣΣΣ
P a))oo()))sss + 11102113
h=1 - aEA
For all h [H],
DR-1. - Da.h (L,,,,,
ag, bk)), ARtIn + AEa + a(s,n, (nn
end for
4 COMPUTATIONALLYY EFFICIENT POLICY OPTIMIZATION ALGORITHM
In Algorithm 2, convert the linear MDP problem to linear bandit problem. It is generally hard to ensure computational efficiency in this paradigm due to the non-linear mapping of policy to occupancy measure and the exponential size of the policy space. A promising alternative is to

---

the policy optimization framework (Luo et al., 2021: Dai et al., 2023; Sherman et al., 2023b), which (FTRL) algorithm over the locally available state-
allows to run a Follow-the- Beeow-the-Regeeee -egularized-Laaaaa action feature set. An algorithm of this type needs to overcome several hurdles: 1) The algorithm needs to construct loss estimates with carefully controlled bias, which is difficult because the learner does not know the feature covariance matrix under the current policy and has estimate it. 2) The algorithm needs to inject bonus to ensure sufficient exploration. These bonus terms not only need to compensate the uncertainty in transitions, but also the bias induced in loss estimates. The bonus itself also needs to be estimated and induces more bias due to the estimation error.
These challenges are fully exposed in the adversarial loss, bandit feedback, unknown transition setting, because in this case the loss estimators usually have larger magnitudes and necessitate larger bonuses. This make achieving near-optimal bounds difficult, and the current best regret is ( by Sherman al. (2023b). We successfully improve it ((K3/4) by several improved design choices, which we describe in the following.
Algorithm Logdet FTRL with initial exploration
Parameters: 7) 3328VAH² K 1 y ld (6dHK*) K K-ž, 3 vdk- i a =HKK, 7 == K2,
8= K-3, P = H - k coo = K-1.
2: Define: Cov = Eawp ((s,a))(s,0) a) a(s,a)
((s.a) 1
3: Run Algorithm 5 with parameters P, ccov. which ends within Ko =O episodes with high probability. Receive outputs (Do,s) and (2
4: for I,...: [[K- K2)/(2r] do
5: For s E Sn, define
(s) argmin HEH.
H.
Cin
+
F(H) "
where Li,
Σ
(TK. - Br.h))
2T
RET.
where H. =
1 (oov(s.)) p) A(A) and F(H) = - log det (H).
6:
Let 7, (+|s) be such that H, Cov (s. गे (-|s))
7:
Let T, = {(j 1)T + Ko + +1. (j 1)T Ko}. Execute T = म for the 27 episodes
A E 7j. and collect (sk,b; ak.k, (x.,) (1))))
8:
Let T3a and T22 be the first r and the last episodes in Tj, respectively. For all k E T3 and
h E [H]. define
{(sw ho a sy wtllere if E T3.1 ((s Jo ax h. sv willee,,
Ck,
(10)
if E T32
Σg. 71 + + E (ECC. (s).))((s,a)
(11)
C E anh)) Et le
(12)
ÍKA O
9K.
(13)
(
O
DR.h DR-1,h U {(SK,A) MESSK,,,,EK.SSS SEA+1)}
(14)
) OBME (. (Zw)
(15)
(OBME is presented in Algorithm 4)
9: end for
Our algorithm (Algorithm 3) starts with an initial pure exploration phase that lasts for Ko = Ö(K ?)
episodes (Line 3), which is crucial in controlling the magnitude of the bonus estimate (will be explained later). In the remaining K K, episodes, episodes are divided into [[K - Ko) Ko)/(2r) epochs (indexed by j), such that in each epoch j. fixed policy म, is executed for 27 episodes, and policies are updated only at the end of each epoch. The goal of dividing episodes into epochs is to let the learner collect sufficient samples and create accurate enough loss estimators for each update.
7

---

Different from previous work (Luo et al., 2021; Dai al., 2023; Sherman et al., 2023b) that use exponential weights, we use the toe Leale--Reezzaed-eeaeeeee barrier the regularizer for policy updates. Logdet has been recently shown in adversarial linear (contextual) bandit to lead to a more stable update and can handle larger bias for loss estimators (Zimmert and Lattimore, 2022; Liu et al., 2023a). It has similar benefits in our case as well.
(FTRL) framework with logdet-
Specifically, with logdet-FTRI, the optimization of the policy on state s is over the space of lifted covariance matrix H. (ov(s..): : p A(A))
[((++))(d++)) where Cov(s. =
a))(s,a)) a(s.a)T
6(s,a) In epoch j. for state s, the FTRL outputs a matrix Hs))) E H.
Ba-p
(Line 5), and the policy FT (-1s) is chosen such that H (s) Cov(s, (-1s) (Line 6). This policy is then executed for 2T episodes (Line 7). Then the learner uses the collected samples to construct loss estimators for all episodes & E T3 (the qk,r in Eq. (12)), where Tj is the set of episodes in epoch j. This follows the standard loss estimator construction for linear bandits, except that in our case, the
covariance matrix is unknown and also needs to be estimated using samples (the Eg,t in Eq. (11)). The validity of Tahh relies on the independence between Σk, and the loss obtained in episode k. To achieve this, we divide the set T into two equal parts T₁,1 and T222 (Line 8). Then we use sam- ples from T22 estimate the covariance matrix when constructing the loss estimator in episode I Tj,,, and vice versa (Eq. (10)-Eq. (12)). In Eq. (13), we further lift the loss estimator qr,A to FRA 1xd++))((++) to be fed to FTRL. Finally, besides feeding the loss k we also need to feed the bonus BR,h required for sufficient exploration in policy optimization and to compensate the loss estimator bias coming from the estimation error of En.n. This is explained in the next subsection.
4.1 THE EXPLORATION BONUS
Similar to previous work on policy optimization in adversarial linear MDPs (Luo et al., 2021: Dai al.. 2023; Sherman et al., 2023b), we use exploration bonus address the bias in the loss es- timator Ga.A and the stability term coming from the FTRL regret analysis. From a high level, the exploration bonus serves similar purpose as "optimismm in the face of uncertainty" as commonly used in the non-adversarial case, but now the sources of uncertainty additionally include the bias and the stability term. From a mathematical analysis perspective, the exploration bonus creates an effect of change of measure that prevent the regret to depend on the distribution mismatch coefficient between the optimal policy and the learner's 's policy. This perspective is best explained in Section of Luo al. (2021). According to the analysis of Luo et al. (2021), when performing policy up- date on state 8 E Sn., we should incorporate a bonus that is roughly of order Q (8, a; by) where be(s, a) Bl s, a) a)l
Our bonus construction further incorporates the improvement from Sherman et al. (2023b) where an optimistic least-square policy evaluation (OLSPE) is used to fit the bonus (rather than sampling the bonus as in Luo al. (2021)). This creates another term of allooss, a)ll to be incorporated
Ak. into the bonus to compensate the estimation error of future bonuses. Finally, we further adopt a technique developed in Luo et al. (2021) called dilated bonus to simplify our analysis. Overall, the bonus we use for the policy update on state 8 E Sp is defined recursively as
ax x (ll0(s, a) 2)33 + +allo(s, (ll.)))) )
(1+
1 H
Ey Be
Enr (16)) [Ba .')]
Notice that because of the dilation factor (1 + 1 (Luo et al., 2021), this deviates from a standard Bellman equation. Recall that we run FTRL in the space of covariance matrix, we would like to
write (s, a) as a linear function in that space. Fortunately, this is indeed possible because by the linear MDP structure, we can write the above as
Bx(s,a) = ([6(s.0)le ((s.a)
d(s.a))
BSSA k. + +
1 FureN 0
(16)
2 SRR
( [Be(s', a()). The purpose of Algorithm 4 is exactly to inductively find an estimator Wi.n of wk.n the second matrix in Eq. (16) (but replacing wa.h by wk.n) )) and feed it to the FTRL algorithm.
where Wk.h = (1 Er
n. for all h. Then, we can form a bomus matrix as
8

---

There are two technical complications regarding Algorithm 4. First, in order to control the magni- tude of Wk,h. we have to control the magnitude of a [ a)ll This can be done by adding a pure Ag.A
exploration phase in the beginning of the algorithm (Line 3 of Algorithm 3) and form a known state space 2 S. Known states well-explored in the initial phase, and the values of [| a) A
on them sufficiently small (in case of order 1/VK). On the other hand, unknown states are hard to be reached by any policy (in our case, their probability of being reached < K and thus can be ignored in the learning phase. The imitial exploration phase is inspired by Sherman et al. (2023a), who further built their algorithm on Wagenmaker al. (2022b)'s reward-free exploration algorithm. We provide the guarantees for the initial exploration phase in Appendix C. The other is that order to ensure only positive bonuses are propagated over layers under estimation error of Wk.b, we force the bonus-to-go estimation to be non-negative in Line 8. The additional penalty is related to | -
Wr,a|| and can be well-controlled.
Algorithm 4 OBME (DR,N)==I ( M (Z (2h) (Optimistic Bonus Matrix Estimation)
1: Parameters B, a, 7, are the as those in Algorithm 3.
2: for h = ...... . do
3: B 4H (1+ + #) 2(M-h+1)
1++1)
(++ app))
4: AEd = 1 E (ED @(s,a)o(s, a))
5: Set Wk.h = (1 H An Σ (E o(8 ( E 2 (if h = H, set
WR.h -)
6: Define BAN = (8 kih + tAA k.h
2 Tk.h
0
7: For 8 E Sn, define Ba(s, = B1, ()),,)))))) ||3-1 + tallo(s, A. (05, T
8: For E Sh define Wa(s) (Ta())s), D (s, where B (s, max {Bu(s.a).0}
9: end for
10: return (B (BR,))eEHA)
4.2 REGRET GUARANTEE
We defer the analysis of Algorithm 3 to Appendix D, and only state the final regret bound in the following theorem.
Theorem 8. Algorithm ensures a regret of order Rx = O(d H²) (K)..
The improvement in our regret primarily stems from two sources. Firstly, we utilize an improved matrix concentration bound from Liu al. (2023a). This ensures that using
1 episodes (where 7 the parameter Eq. (11)) enough to gather data and build reliable loss estimator. In contrast, previous works require
72 (Dai et al., 2023; Sherman et al., 2023b) or T = (Luo et al., 2021), thereby consuming excessive episodes to accumulate data for single policy and consequently slowing down policy updates. Secondly, previous works (Luo al., 2021; Dai al., 2023: Sherman et al., 2023b), the usage of exponential weights requires 77 to be small compared to the magnitude both loss estimators and exploration bonus. This prevents them from choosing the best 17 in their algorithms. With the help of logdet barrier, in our algorithm, 7) only needs to be small compared to the magnitude of the exploration bonus, which is already small given the initial exploration phase. This gives more flexibility in choosing 17.
5 CONCLUSION
In this work, we obtain the first optimal V regret bound for adversarial linear MDPs under bandit feedback and unknown transitions without the help of simulators or generative models. We also give new K/ regret bound with efficient policy optimization algorithm. We hope that the techniques and observations the work could be helpful in developing an algorithm that both statistically optimal and computationally efficient.

---

REFERENCES
Jacob D Abernethy. Elad Hazan, and Alexander Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In Conference on Learning Theory, 2009.
Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. Pe-pg: Policy cover directed explo- ration for provable policy gradient learning. Advances in neural information processing systems, 33:13399-13412 2020.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. In International Conference on Learning Representations, 2018.
Qi Cai, Zhuoran Yang. Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy opti- mization. In International Conference on Machine Learning, pages 1283-1294, PMLR, 2020.
Liyu Chen and Haipeng Luo. Finding the stochastic shortest path with low regret: The adversarial cost and unknown transition case. In International Conference on Machine Learning, pages 1651- 1660. PMLR, 2021.
Yan Dai, Haipeng Luo, and Liyu Chen. Follow-the Follow-the-perturee tethe-pertubed--eee leader for adversarial markov decision processes with bandit feedback. Advances in Neural Information Processing Systems, 35:1 1437- 11449, 2022.
Yan Dai, Haipeng Luo, Chen- Yu Wei, and Julian Zimmert. Refined regret for adversarial mdps with linear function approximation. In International Conference Machine Learning. 2023.
Christoph Dann, Chen-Yu Yu Wei, and Julian Zimmert. Best of both worlds policy optimization. In International Conference Machine Learning. 2023a.
Christoph Dann, Chen-Yo Yu Wei, and Julian Zimmert. A blackbox approach to best of both worlds in bandits and beyond. In Conference on Learning Theory, 2023b.
Dylan J Foster, Alexander Rakhlin, Ayush Sekhari, and Karthik Sridharan. On the complexity of adversarial decision making. Advances in Neural Information Processing Systems, 35:35404- 35417, 2022.
Dylan J Foster, Noah Golowich, Jian Qian, Alexander Rakhlin, and Ayush Sekhari. Model-free reinforcement learning with the decision-estimatti coefficient. Advances in Neural Information Processing Systems, 2023.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Near-optimal policy optimization algorithms for learning adversarial linear mixture mdps. In International Conference on Artificial Intelligence and Statisties, pages 4259-4280. PMLR, 2022.
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, pages 4860-4866 PMLR, 2020a.
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. PMLR, 2020b.
Tiancheng Jin, Longbo Huang, and Haipeng Luo. The best of both worlds: stochastic and adversarial episodic mdps with unknown transition. Advances in Neural Information Processing Systems, 34: 20491-20500 2021.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learning, pages 267-274, 2002.
Fang Kong, Xiangcheng Zhang, Baoxiang Wang, and Shuai Li. Improved regret bounds for linear adversarial mdps via linear optimization. arXiv preprint arXiv:2302.06834 2023.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
10

---

Chung- Wei Lee, Haipeng Luo, Chen- Yu Wei, and Mengxiao Zhang. Bias more: high high-probabilityy data-dependent regret bounds for adversarial bandits and mdps. In Advances in Neural Informa- tion Processing Systems, 2020.
Haolin Liu, Yuen-Yu Wei, and Julian Zimmert. Bypassing the simulator: Near-optimal adversarial linear contextual bandits. Advances in Neural Information Processing Systems, 2023a.
Qinghua Liu, Gellért Weisz, András György, Chi Jin, and Csaba Szepesvári. Optimistic natural policy gradient: a simple efficient policy optimization framework for online rl. Advances in Neural Information Processing Systems, 2023b.
Haipeng Luo, Chen- Yu Wei, and Chung-War Wei Lee. Policy optimization in adversarial mdps: Im- proved exploration via dilated bonuses. Advances in Neural Information Processing Systems, 34: 22931-22942, 2021.
Arkadi Nemirovski. Interior point polynomial time methods in convex programming. Lecture notes, 42(16))3215-3222 2004.
Gergely Neu and Julia Olkhovskaya, Online learning in mdps with linear function approximation and bandit feedback. Advances in Neural Information Processing Systems, 34: 34:10407-10417, 2021.
Feiyang Pan, Qingpeng Cai, An- Xiang Zeng, Chun-Xiang Xiang Pan, Qing Da Hualin He, Qing He, and Pingzhong Tang. Policy optimization with model-based explorations. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 4682,,462.22 2019.
Aviv Rosenberg and Yishay Mansour. Online stochastic shortest path with bandit feedback and unknown transition function. Advances in Neural Information Processing Systems, 32, 2019.
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.
Uri Sherman, Alon Cohen, Tomer Koren, and Yishay Mansour. Rate-optimal policy optimization for linear markov decision processes. arXiv preprint arXiv:2308. 14642, 2023a.
Uri Sherman, Tomer Koren, and Yishay Mansour. Improved regret for efficient online reinforcement learning with linear function approximation. In International Conference on Machine Learning. 2023b.
Andrew Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson. First- order regret in reinforcement learning with linear function approximation: A robust estimation approach. In International Conference on Machine Learning, pages 22384-22429. PMLR, 2022a.
Andrew J Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson. Reward- free rl is no harder than reward-aware rl in linear markov decision processes. In International Conference on Machine Learning, pages 22430-22456. PMLR, 2022b.
Andrea Zanette, Ching-An Cheng, and Alekh Agarwal. Cautiously optimistic policy optimization and exploration with linear function approximation. In Conference on Learning Theory, pages 4473 4525.. PMLR, 2021.
Canzhe Zhao, Ruofeng Yang, Baoxiang Wang, and Shuai Li. Learning adversarial linear mixture markov decision processes with bandit feedback and unknown transition. In The Eleventh Inter- national Conference on Learning Representations, 2022.
Han Zhong and Tong Zhang. theoretical analysis of optimistic proximal policy optimization in linear markov decision processes. Advances in Neural Information Processing Systems, 2023.
Julian Zimmert and Tor Lattimore. Return of the bias: Almost minimax optimal high probability bounds for adversarial línear bandits. In Conference on Learning Theory, pages 3285-3312. PMLR, 2022.
Julian Zimmert, Naman Agarwal, and Satyen Kale. Pushing the efficiency-regret pareto frontier for online learning of portfolios and quantum states. In Conference on Learning Theory, pages 182-226 PMLR, 2022.
11

---

A RELATED WORKS
In this subsection, we review prior works on adversarial MDPs and policy optimization.
Learning in Adversarial MDPs. Adversarial MDPs refer class of MDP problems where the transition is fixed while the loss function changes over time. Learning adversarial tabular MDPs un- der bandit feedback and unknown transition has been extensively studied (Rosenberg and Mansour, 2019; Jin et al., 2020a; Lee et al., 2020; Jin et al., 2021; Shani et al., 2020: Chen and Luo, 2021; Luo et al., 2021; Dai al., 2022; Dann et al., 2023a). In this line of work, not only V K regret bounds have been shown, several dependenn bounds are also established. For adversarial MDPs with a large state space which necessitates the use of function approximation, vK bounds have only been shown under simpler cases such as 1) full-information loss feedback (Cai et al., 2020; He et al., 2022; Sherman et al., 2023a), and 2) known transition or access to generative models simulators (Neu and Olkhovskaya, 2021; I; Dai et al., 2023; Foster et al., 2022). Therefore, to our knowledge, we provide the first VK regret for adversarial MDPs with large state spaces under bandit feedback and unknown transitions." For linear MDPs, series of recent work has made significant progress in improving the regret bound: Luo et al. (2021), Dai et al. (2023), Sherman et al. (2023b) pro- posed efficient (polynomial-timg -time) algorithms with KT1/15, K and K regret, respectively, and Kong et al. (2023) proposed an inefficient algorithm with K/+ + poly(?/Ama)) regret. Our VK re- gret through an inefficient algorithm and K regret through an efficient algorithm further push the frontiers. These results are summarized in Table 1.
Table 1: Related works for learning adversarial linear MDPs without simulator. An algorithm is efficient if its computational complexity is polynomial with action size [AA,, dimension d, and K. For the Type column, PO means the algorithm is based policy optimization while OM means the algorithm based on occupancy measure estimation.
Algorithm
Regret
Efficient
Type
Assumption
Luo et al. (2021)
Ö (10)
/
PO
Dai et al. (2023)
δ (K(%
/
PO
Sherman et al. (2023b)
δ (K*))
/
PO
Kong et al. (2023)
(K*))
X
OM
3m, Mg 2 Al
Algorithm 2 (ours)
Ö V
x
OM
Algorithm (ours)
Ō (K*/1)
PO
Policy Optimization with Exploration. Policy optimization has been regarded as sample in- efficient due to its local search nature. Recently, efforts to alleviate this issue have incorporated exploration bonus in policy updates (Agarwal et al., 2020; Shani et al., 2020: Zanette et al., 2021; Luo et al., 2021; Dai et al., 2023; Sherman et al., 2023b; Zhong and Zhang, 2023; Liu et al., 2023b; Sherman et al., 2023a). In the case of linear MDPs with fixed loss function, the state-of-the-an result is by Sherman et al. (2023a), who provide a computationally efficient policy optimization algorithm with a tight VK regret. In the case of linear MDPs with adversarial losses, the best ex- isting regret bound is K by Sherman et al. (2023b), while we improve it to K²/² in this paper. Beyond theoretical advancement, exploration in policy optimization has also showcased its potential in addressing real-world challenges, as evidenced by empirical studies (Burda et al., 2018; 8; Pan et al., 2019).
2 Although Zhao et al. (2022) provided a v K regret bound for linear mixture MDPs with bandit feedback and unknown transition, the polynomial dependence the number of states prohibits its application to MDPs with large state spaces.
12

---

B OMITTED DETAILS IN SECTION 3
B. POLICY SPACE DISCRETIZATION
Proof of Lemma 4. Let On Ex= 0K. and let ((s,a) = (Ó(s, (o(s,a),00 0n) for s E Sn be the loss function under the loss vector 0. Under this loss function, the Q-function of policy π can be written
(" o(s,a) for E Sh.
where E% is recursively defined as
cR = Op +
Σ s'ES+t1
Σ
a'EA
Notice that by Definition we have | ll HVdK. Let x¹ be the optimal policy under loss function l. Then by Bellman's optimality equation, n² can be represented
(s) argmin (0(s.a) Eh
and 5h can be found recursively from layer to layer
Now, let 5 be the closest element to enr in the H of (A ([HVdK) ddK), and let x' be the policy induced by g (E EH), i.e.,
nt 7'(6) argmin {Ø(s, (05,,a)55) }
Then for any n, have
ΣΣ Σ
(1t (8,a) -M"s,)))(()) a) 0k.
sES
K
ΣΣΣ
(n (8,a) 10 (s) ORn +
ΣΣΣ
Σ (ut (8, 15" (s,a)))) T00
k= 1==1 SESA DEA
== sES, aEA
11
V= (s1: (VT(s + Σ Σ nT (s) (a'(a))) - -
(als)) &A
h=1 SES
aEA
(by the performance difference lemma)
50+ Σ Σ 1ES
Σ ( (dls)) T) +2
(by the optimality of ग* under and the discretization error)
H2
where the last inequality is by the fact that n' takes the argmin with respect to 4-- Finally, notice that policy T' belongs to 1I corresponding the parameter 0n HHaSh.
13

---

B.2 FEATURE ESTIMATION
Proof of Lemma 5. (s) satisfies Eq. (7) because n² is valid occupancy measure. To show Eq. (8), notice that
E E (s) clip a(ss,) E SEAR
(=(s))((s')
NEA
ΣΣ SES REA
nº (s) [h.rl
E (d())((ss))
for O ()
BES
Σ E SESA REA
nº (s)s clip 0(s
Σ ((s))((s))
Σ (5))(((s))
S'ES
SESA11
ΣΣ (s))s(()ss) SESa cEA
P(5))s,a)f(s)+ +2
Σ (*)))((()))
ES++4
#ES
(for some such that | S by Definition 3)
Σ Σ SESA aEA
1 (s)
Σ P($)),))5(()) - Σ (T)))((())) +
8ES
(17)
Finally, show Eq. (9). For simplicity, let D,, {(s), at s and let o, = Φ(s, a:). We first
consider fixed policy and a layer h. Let = 1 for any f F=, there exists an f' E Ne,1 such that [f'(s) - f()) S e for all Xr Let Ne, be the e-net of (vd). Furthermore, define [IT,] = (3K'd (whose meaning will be clear later).
K. and let .e. be an e-net of J on layer h so that
Then under this fixed n, for any & E Ne,2 any f E Ne,1, with probability at least
8 | K
Σ (S(K) - - Eh,)) Σ -T=)
--2 Σ (f(s)) (h. (0. Eh.s o. - -
(Ø) 5 Sh.f - 0, 5)²
1=1
2=1
I 2 > (f(s)) EvMP( (m (f [f('))) (oT - oT Σ
(oT Eh.s - -TTE)² + 2v 22vdnç
im1
iml
TeallWee1|1TW/1 2Vdlog
We 2 |
< 6
Σ
T. Eh.s oTE) log
8
TT sh.s -T + +2vdnç
(0)
(Freedman's inequality)
S <Vdlog W 1
[laK + 2Vang.
(AM-GM)
Below, we take union bound over f E Ne.1 E E No.2. and n E [T]. Notice that although the size of the policy set is [II| < (3K)dff (a product of H -net for (I)),,, when considering the policies over layer h, the total number of different policies is only II, < (3K)d. Therefore, a union bound policies require only size of [ Bounding the distance between the full sets and e-nets,
14

---

conclude that with probability at least k. for all & E (vd),,, all II, and all f E F""
Σ (S(s)) of sh. E((()) -Te)²= <TVdlog W +2vdnç + vdnc.
8
(18)
By choice of & and the second and third terms above are both negligible compared to the first term. Finally, we bound [Ne,1l and [Ne22 via Lattimore and Szepesvári (2020) (Exercise 27.6). [We,2 is the size of the e-net of (V(d), equivalently the (e/vd)-ne of (1), which is upper bounded by (3vd/e)². By the definition of F", the E-net of F= would be the union of the e-nets of {0 (vd)) and {I' Rddd 0 I r I= Thus [Wa1l (6d /e) Using these in Eq. (18) concludes the proof.
22 IT K
7v
+ 2vvng + vdne
W Weal|We2 K
< Sd
8
18d K
< 16d log
8
Lemma 9. Fix II E [H), Fr. Let &1 and &a be two solutions for the En. in Eq. (9). Then |151 &2llan I Cwess (Coonus defined in Algorithm 2)
Proof. Let Dí, {(ss Aj, s and denote Φ;
Ø(s; a,).
Let Emin
sngmingeR' Ei= (f(s)) - [) where di == d(si, ai). By the first-order optimality condi- tion,
Σ (J(+)) - o. Emin) (ØT o5 Emin) S 0.
(19)
By the fact that & satisfies Eq. (9),
1 K
16d log
(f($)) - oTE1)² -T
"((ss) - - o, Emin)
iml
n
(f(s)) o5 Emin) (o, Emin - -TT +
Σ (o. (E1 Emin))
(o:(5= {Lmin)
(using Eq. (19))
i=1
[ Emin 1 |1[1
Emin
(by the definition of Ar)
> [[ Emin 112, 4d,
which gives ||51 Emin 11,
<
THE
(recall Chomus = 10d H log 1842 x
Similarly, ||E2
Emin 12,,
C2 TH2
Combining them proves the lemma.
15

---

Proof of Lemma 6.
Σ 5 S'E
pr as) ((ssa) En.] - Σ Σ (s, as) clip [o(s, a) Thh + +
SEA, AEA
SEA, aEA (by Eq. (8) and the same calculation as Eq. (17))
ΣΣ
1r (8, clip ((s,a) [nns]] clip [ob(s, T
SENr REA
Σ
Σ (A (s, - (s, (s) clip (o(s,a) a) (aaa))GGn + 2c
SENn REA
$ E Σ
4t (s, ()) A llā, SlAn +
Σ E(00 (s) ( + +
SEAn aEA
sE
Obonus
pe (s, a))o(,,))) +
-² ~
+ 2ç (by Lemma 9)
H
SEA, REA
SEAA
(als)) where f(s) = (ala) clip ((s, a) TT)TEn.)) which again belongs to F* Recursively applying
the inequality proves the first inequality in the lemma. To obtain the second inequality in the lemma, with slightly different decomposition in the second step above, we get
E a) SEAs aEd
(clip (b(s,a)) ( clip [o(s, a) (h.1)
Σ
Σ (n" 10 a)) clip (o(s,a) T Eh,s] 2Ç
NEN, aEd
Σ Σ
A" (s, a) (1l.)) 1lau. Ila, Σ (A (s)) +
NY aEA
Chonus
Σ
Σ
A (s, a) (1) + E (+) (x))
H
BEAr aEd
SEA
where (((s) = E
cliss clip ((s.
[hn,s] Following the same argument proves the second
inequality.
B.3 REGRET ANALYSIS
[Rx]
K
H
K H
E
ΣΣΣ
(T)
TO.N
(5 )T Bk.n
h= nell
k= h=1
H
K
K
E
ΣΣΣ
(T) OOan
( T Okc
(dl(T) (p))) Okn
b=1b=l
A=1
h=1
SqHK
K H
E E
(T))) Th Σ
20 To
Ua (T) (105 0% T (6ā (T.n) 0a.n)
+ +HH
k=1xel
k= nell
bias
K
E
Σ (x)
((5T)TO
b%
(6T ) T bi
2k (T)
> bg +bias
+ +nHKK
kel
Arl
bonus
16

---

We bound the terms individually in Lemma 10, Lemma 11 and Lemma 12. The potentially un- bounded bias term is offset by a negative contribution the bonus term.
B.3.1
BOUNDING THE BIAS
Lemma 10.
H ΣΣΣΣ
K
K Me (s.a)ll((s + 17
bias
1 E Coonus
> 11 1i
k= 1=1 sE aEA
k=1
[d:H² 3
+ +
+ ndHK + d HHVK
17
Proof.
The bias of any policy x at episode & and stage can be calculated as the following:
(o Ok, (dk
T S (Ø) )ū,n) TT)Too 0k.
(Ok, ((
E(Ox,N.)
bias ...1
blas
Set
f(s) = Σ a(a)s))(s,a)
Σ T(als) clip (o(s,a) (m.n)))) ETT (o(s,a) 1
then the first term is by Lemma 6
Cbonus ΣE Σ A((s,))ló(ss,)))4 2CH.
bias (HT (5)
H
BE
NE aEA
Define Ma,h- Eren (T) (6T,N)
Then the second term
bias S 1107 M
0x. M Σ the (TT' Do TORA
Ma.a
=110T,u Math
M 1 Σ ( (o -o% Ok.
Toan Mu,
=1107,n Ma
Σ
d:( 1k
(
15% -
Menh
2n1 1 M
+ 1
Σ th (
0%% ) Tkk
Ma.
+ "
Σ
ch
(T'))
Σ g) - o T | Mirk
(by Lemma 47)
I <n 13
+ d Σ
(T''T)
(o(at)x x
E
n (s.a)ll((s,))), + +2CH
"1
Wich NE aeA
(by Lemma 6)
O(d3)
ΣΣΣ nr (o.
<
<n M
+
Ed((T)
1e' (s. 4)]1
We REA
Wch aEA
(Cauchy-Schward
dd2
+ 0
17

---

O(dă H)
dd²
S /nlogg 1| M
BRN + O
7
7f
where B = Ex ExeS, Lh (T) (s,,)]ld(s, a) a)]l Ka We have
K
h
k
H
[|o(SRR A.ll [Da-1] |]
E
Bxn
= E
E
4=1
E
(8 (k, (t,,))1
$ OdH (odFHoog()) log(K))
Thus, for any IT
AKK
O(diH)
K
H
+ +0 /
h.2
E
nllōx,A
112
M
+
3ki
1
hichh
K
H()
<
E
nl
3x M
+
($= = k
17
Overall,
K
H
K
bias < E
bias + Σ (
+
bias + Σ [x((T) (T(s)
A I
h=1
Aem I Am1
K
Chonus H
E
x
ΣΣΣ
Pr (s, + Σ (T(TT)((ss.) llo(s, aلl
h=1
N' R'ch & aEA
K
nll 1i 1 + Σ ( 1)
HO)
"
K
boonus
ΣΣ k= 111111 dE aEA
m (s) + > (((()))E()) [1
K
nl|0x 11 + 2m Σ 2/ (T) ) o(diHP)
7
1=1
K
ΣΣΣΣ
P (s, + Σ ()(())))) (s.00) | ( a)lla
<
bonnus
k=1k=1 SE aEA
H
+ 2C
ΣΣΣ
(TT nr (s..)))l(((s
1m Aml 2E X1, acA
K
H(dåHz)
+
+ 2ndHK
1mm
E bonus
L E
Σ
mt (s, (s,a)))(ss
OC H VdK)
k=1 1= Nn aEA
K H
Chomus
+ 2Coonus
ΣΣ Σ (T)
Σ
Σ (s)
H
A=1 T7
N c aEA
(by Lemma 6)
K
+ Ö H3)
+ 17
10 1|, - + 2ndHK
18

---

k
H
K
S
Obonus
ΣΣ BΣEY k= 1-1h=l SEAn aeA
Σ
ph (s, ())l + 10 11
Σ
k=1
H
+ 2C 20oons
ΣΣΣΣΣ NEN, aEA
Lh (T)) (s,
H
+ θ
+ ndHK + Oboous H v dK
K
< E
Donus
Σ ng (8, ()) + Σ
1022 laa
k= h= &E aEAA
d3
+ Ö
+ HdH + Chamus VdK + O dVdK dK
where in the two (*) places we use
E
ΣE
E
Ag
h= tE aEA
K
K ΣΣΣΣΣ Rm h= &E aEA
E
E
Σ (s))),)),
(s) as))l(,,,, a))
A R= tE aEA
K
HKE
BEN
Ō(HVKK.
Finally, plugging in the definition of Chonus Ō(d H) gives the desired bound.
B.3.2 BOUNDING THE FTRL REGRET
Lemma 11.
ftrl S 3 (n
7²
+
K + +HH 222
Proof. The magnitude of the loss is bounded by
10 0x
b%l
M
Lu
Cuunus
ΣΣΣ
ME(s, (((s, + nll0ī 11 Mi
h= NE aEA
ndH
H
Choma
Mr
dH
HdH
2dH
Obonus H +
Covaus H.
7
If < Tall +20 H'
then have nloT 0x byl - and we can the standard FTRL regret
bound of exponential weights (Lattimore and Szepesvári, 2020, Equation
In
III
K
ftrl <
KK
+
17
E
Bx
Σ
9u (2) A + 2(b
John's 's exploration
Jomn
LaeIT
19

---

Since Mn Bx 10%0%"1 1. have M
3 1
(Exwge 128 1)-
and thus
1-7
E Em m
Σ (T) Mr "0
S 112
MMM -
(1 7)2
TEEl
For the final term, we have
K
H2²
(mtttu nP 72 K)
(TT)) & nomnu H² +
722
B.3.3
BOUNDING THE BONUS
Lemma 12.
K
H
bonus
& -
nl
livE" + Chonus Σ ΣEΣ
Me (s.))ló(s..))1a;
1=1
h=1 NEN AEA
d H
+ δ
ddHK &
Proof.
bonus
E
Σ "1
Σ
de
|1
Chomus
b=leEN aEd
11 M
Cbonus
Σ ΣEΣ
ph (s, (s.a))l(s..a))l
Am1 AEA
The first and the second term above have been handled in the proof of Lemma 10. Following the analysis there, we can bound their sum by 3 dåz + HdHHK + d H
B.3.4 FINISHING UP
Proof of Theorem 7. Combining the bounds in Lemma 10, Lemma 11, and Lemma 12, we bound the regret
df E Rx 5 HdåHHKK H'K
d
K
HHK
&H
72
H - nd
+ H3
( = ((ddH)
n
= o(d Hi VK).
(n = ((dVVHK)
20

---

C INITIAL PURE EXPLORATION PHASE
Algorithm Initial Pure Exploration (Algorithm of Sherman et al. (2023a))
input: 8, (r tcov
Set m flog
Ccov
Set Vi [m], Pi P
for H. H...., do
k Dhis: An.s i=1
COVERTRA((,, E (p:h....)
D/ U,D
AA 1 + ((H,,))),, (()
Zr. + {s Sn: Va E A, I S
end for return (Dns Zn)
Theorem 13 (Theorem 2 in Sherman et al. (2023a)). The COVERTRAI algorithm (Wagenmaker et al., 2022b, Algorithm 4) when instantiated with FORCE (Wagenmaker al., 2022a, Algo- rithu enjoys the following guarantee for linear MDPs. Given sequence of tolerance parameters Pla..., Pm > 0 and h E [H]. , the algorithm interacts with the environment for T steps, where
T < max
C
2 max
C>0 is a logarithmic term, log 7. dt "H I'mm² log" 7/2 3..
P
1=1
{ (Khns Driss Ande mm i-1
such that [Xhs] m+1 Sim
and outputs
i=1 forms a partition for the unit Euclidean ball, Nn,a T E (s.a..DD.. (18 ((s,a))(s,a)) and with probability - 6, it holds that:
Vi E [m], oJ T pi.
Véb Xn,65
and vi E [m + 1], sup Σ Σ Ei{o(s ((s, E Ano (ar))((s)))) 22
SES, aEA
Lemma 14 (Lemma 15 in Sherman et al. (2023a)). Assume h [H], Ecov > 0,8 > 0,m
[log(1/<cov)]: Pm 2 ... 2 P1 > and let (An.) (E(m) be the covariance matrices returned from
COVERTRAI(h, A. {m m). Then under the assumption that the event from Theorem 13 holds, have for any policy and E [m]:
[()(s) Ha Jas... s.t. (Iø(s, ()(x,, > Pm S Eoov-
SES..
Lemma 15, For linear MDPs, with inputs 8 E (0, 1), O, coov > 0, Algorithm 5 will terminate in T= -6 /dH//p² + n² polylog ()) __,d, H episodes, and output H datasets (Dr) where
Dr. Sp Ax Sh+1 such that with probability
Σ nr (s)l((s Zr} S Ecovs where Zn Sn: Va E A. [| S o) SE.S
Vh, ViT
with A & + E(sa,,)D, o(s ()).)))
Proof of Lemma 15. Let Ty denote the number of episodes run by COVERTRAJ, by Theorem 13,
d
2
H m log 7/2 1
Th < C
2'
max
J
P
log
p
8
1m1
2
< σ
m2m
log
+ d
H m 3 log 7/2
d/p²
H3
1 coor
< 5
polylog
d, H
Gcov
21

---

Given that Algorithm& 5 executes COVERTRAJ H times, the claim follows. For the claim the un-reachability of S₁. Zh, fix [H], and observe that by Lemma 14, w.p. - 6 H, for any n
Σ p² (s)) (s) Fa || a) Pm S sES,
coovs
where in the inequality we use that An.s I As. The proof is complete by a union bound over h.
D OMITTED DETAILS IN SECTION 4
We will be using several additional notations in the analysis.
Definition 16 (1%, phe p.). Define 17,(() (s) = 1= (s)T(s E Sr. By the definition of μt (8), we know
that Pi is distribution over S that is supported Sn. Define ph: = and pt 14
Definition 17 (T E7, Ej). We define Tý the distribution over trajectories {(si, a;)) for the first h steps generated by policy π and transition P. Then we define
EA [] = (s),a))) wTg E 1,4 [+,
where [-] can be a function of ($1, a1...., Sh-1, ah-1, 8).
In the analysis, will mainly consider the optimal policy x² For notation simplicity, write E2 [] = Be [.]
Definition 18 (Good trajectory). For any trajectory {(shs an, 8h+1) where siijs if sh & Zn for any h, then say t is good trajectory.
Definition 19 (Qa). Define Qx a) QTH (s,
D.1 REGRET DECOMPOSITION AND DILATED BONUS LEMMA
Lemma 20. For any trajectory {($), ah. Sh+1) with sisj S generated by any policy, have
Pr (t is not good trajectroy) HK-
Proof. From Lemma 15, since we choose ccoe = K K- +, for any h and generated by any policy,
we have P( (1 & 2x) < k- By union bound, we have
Pr (t is not good trajectory) = Pr
U ig
& Zn.
< HK-
In the regret decomposition below, we use the notation E defined in Definition 17 to denote the expectation over trajectories (31, a1,...,....... , 8h-1, -1-1, 8h drawn from n², and use &, to denote the event that 4' < h, 8W ZN. By Lemma 20, have F [T&x)] HK- & for any h. By
22

---

performance difference lemma (Kakade and Langford, 2002), we have
E
[
H
E
Bewui ((; x- (-1s))]
E
EA ((QN((s))) --1ss)]]
K
"
K
H1
E
EX (2QM(s. T- (-1s) 1(8
+ E
[(Qu(s,)) - x* (-1s)) [[8
H
E
Et (s. m(s))) T' (-1s) I(&M
+H
(20)
reg-term
where the last step comes from Lemma 20 and Qu(s,a) S H for any k. h, 8,a.
To handle reg-term, we utilize the dilated bonus technique proposed Luo et (2021). We summarize the technique in Lemma 21, with slight modification to make it align with settings.
Lemma 21 (Adaptation of Lemma 3.1 in Luo et al. (2021)). Suppose that for some bonus functions (s, (s, a) and some constants f. g. we have for all E Sh.
Bu(s, a) 2 (s, + (1+ 1 H
Eg B (12) [Ba(s', d')I(s' Zn+iHl (21)
and suppose that our algorithm guarantees
E
Et [Qu(s.))
x²' (+sss
S +
E
(e(s,,
ΣΣ
Eal (Ba
-==1-=1
(22)
Then, have (recall the reg-term defined in the proof of Eq. (20))
(1 (1+
reg-term 5 JHK
E
Bar (-1as) [B((s,
Proof. Notice that for any function X of (81, 01,..., 8H, az): it holds that (1s)) [I{( E Zn+1ll Ej [XI[E++1]]
(23)
By the definition of reg-term, we have
reg-term
H E (KQN(s.)) T- (-1s) H
E
$ g +
(b)
E. (B, (s.
K H
K
H
+ E
Ex (1 [(E
(. E (Ba) (11s))
1= h=1
(by Eq. (22))
23

---

K
M
S9+ +E
B Borr (11) (ss, {)
1+ +1+
E
uo (-16) (+b)) (BR(s,
EI
Bari (b (b(s,a))(EEN)
11
h=1
-11+ H
B E Bor (-10) Barw Ballee ( E
(by Eq. (21))
K
H
+ JHK
+
1
E
By E (1)) (B2)
H
K
1+
E
B E Bawn (11) (Bx [B
(by Eq. (23))
H
Jum
h=
9 fHK+ +
1+ H
E
E a (s)
(telescoping)
K
g fHK +
1+
E
Barai (18) [Ba(s1,)]
(S = {81} and 81 E Z1)
H
In the following Appendix D.2 and Appendix D.3, we aim to show that our Algorithm and Al- gorithm 4 could induce bonus functions b,,8,a), a), B& a) that satisfy the condition of Lemma 21.
This allows to directly apply and get the desired regret bound Appendix D.4. Our choices of (s,s, a) and (s, a) are the following:
For E Sh, a E A.
(s. ()) + +(1-
1 4H
a al(
(24)
B& (s, (b(8, 0(8 a)_ wk. ukkn
(25)
where
Wk.K =
1+ H
Σ (())W( e Z
(Wa,n - 0)
(26)
e'ES+t1
with the (s') defined in Algorithm 4.
D.2 CONSTRUCTION OF DILATED BONUS (ACHIEVING EQ. (21) USING ALGORITHM 4)
In the linear regression (Line 5) of Algorithm 4, the T is estimation of wk.s defined in Eq. (26), where for s' E Sh+1,
+ ((s",aa) Wx | (27)
We(s') E. (eee |SlIOCd a' a')ll 2khn
al d')lR= har1
with [x]+ denoting m).
The next Lemma 22 is a key lemma that 1) bounds the error between Wx.h and Wk.h. and 2) bounds magnitude of WK.h and WA.a for h E [H].
24

---

Lemma 22. Let C, - 15 / (>2g)) and suppose that B S cc Then with probability at least 1 6, the following inequalities hold for all k. E [K, h E [H, and all Sn:
|/ 1a S VdBBaax
(28)
(((sa) Tx.n a( wanh S C,dBn
(29)
(0(s, a) Ts 2nd 1+
2H B%
(30)
Proof. We use induction to prove these three inequalities. For the base case H, we have WK.H 0 and Wh = O, so all three inequalities holds.
Suppose that all three inequalities holds for the case of + Below, we show that that also holds for h.
Showing Eq. (28).
Observe that for any s' E Sh+1,
1 1
Wa(s)itf'' E Enti}
H
< max d'EAA
1
1
='d "'l'os',a'))13.1 d')ll3z + aalloss ('))l, + +lo(s',a') @anttll) 11 e 2nt1}
H
3
aapp) + +1--
1+ H
BRYY
7
H
2H
(10(,' al) "lll
S p for s' E Bh+1 by Algorithm 5; using induction hypothesis Eq. (30) for h + 1)
Bair + (1+
1)
(1
1
1 +
B
(by the definition of B
H
2H
H
2H
1
Ba+1
Bjuax
(31)
Thus,
1+
Σ (())W( e 2n-1)
S
Bmux
Σ
vi6o)
VdBmax
8' e'E
8' d'ESttI
2
where in the last inequality we use the linear MDP assumption (Definition 2).
Showing Eq. (29).
|ø(s, a) Tk.h - ((s, a) S [o(s, a) a)lA [ - WK.ullau.
(32)
By Lemma 44 and ||w,,all S vdBmaax (which we just proved), holds that [ WkKnllae,
)
Σ ass (1+11) 1) Wa(s')((''s e Bxti) -(s)))(ssa)) a) waA.
V
VdBgaax
A
(33)
By Lemma 43, the first term above can be upper bounded by
A(Bmaax] ( log K + log No. (Vh) + +8K22.
(34)
25

---

where V/8 is the function class where (1+ #) WI'ss) BA+1] lies, and (.2 is its covering number. By the form of Wx(s') given in Eq. (27), Va. can be chosen as the that defined in Definition 39. Then by Lemma 42 with 1 and _ , + 2a I K² we have
K
log (Ne (Vk) 4(d 1)2 log (400(d + 1)² S 48d log (12dK)
Combining this with Eq. (33) and Eq. (34), we get
12dK
| Wk.nllaR. 15dBn
log
8
Further combining this with Eq. (32) proves Eq. (29).
Showing Eq. (30).
(Ø(s,a) a) T Wn Ifs 2 E En} + (0(5,)) (0u. - wk,n) a 11s E 2n}
I1s (o(s,,)TTu,.ll
Wa,n
1
sup s'ES++1
Wa(s')I(s's E Znt1} + C.dB, ||o(s, a) a)ll
(by the definition of WaA and Eq. (29))
(C, (C,dBaaxx²
Baax +
+ (1l
1(8 E 2n} (by Eq. (31) and AM-GM inequality)
4a
< B +
Brux + ap²
4H
(by the condition specified in the lemma and that [[ a))l S for E 2,,)
S B
Bmax
B
Buax
(by the definition of Bjmaa)
2H
This proves Eq. (30).
Lemma 23. With the definition of Eq. (24) and Eq. (25), any E Sho we have
By Bes-P(-ss,a B Ber (Ba(s', a') E Bx+1]l (C,d
(s, 2 a)) +
1
H
where Buax maXne[M] B and C, is logarithmic term defined in Lemma 22.
Proof. Recall the definition of wa.n in Eq. (26), from the definition of linear MDP, for all k, ht, s, a,
have
(8, a)
Wk.h
W(s'iTS' Enti]]
Ey (PPP()))
1
Eg Be (11)
1
Ey Egr E.
Bal(s, E Enti]]
E. E. Ear (Ba(s)
4H (1)ss 1_, a(s'aa') ( 11s's Zn+r3
1
(by the definition of Bo(s', d') in Line 7 and Ba(s', a') in Eq. (25))
1) +
(C.dBmax)a
By Pa (''''') E B
H
(Eq. (29) and AM-GM inequlity)
Thus, we have
(g(8,a)
26

---

a)) + a(s,a) Wkeh
T (+ H
1
Plan [B&(d, E 2nti3l (Cad
2 be(s,a)
a
D.3 REGRET ANALYSIS (ACHIEVING EQ. (22) USING ALGORITHM 3)
The goal of this subsection is to prove Eq. (22) for the definitions of by (s, a) and BB a) in Eq. (24)
and Eq. (25). We first decompose the left-hand side of Eq. (22).
E
EN [Qu(s,,))
at' (+s)) [[&
K
E
h=1
bias-1
K
ER ((ouls.)) (ulss)))-Q((,)))tttt 1(8n1]
+ E
h=1
bias-2
K
B (Trch- B BK Ha(s) - 11En]]
E
Jmm hum
ftrl
K
H
E
(Be(s,)) m,((s))))))))))))))))))) (111)) 1(EA)
(35)
k= h=1
bias-3
where we use that for Sji Eu = (Cov(s, (-1s)),, and E Bawn( (B(s,)) (e(
(Cov(s, (-)s() BR.,.). and we define Hs(s) Cov((s Hs) = Cov(s, (-1s))
We further deal with the ftrl term. This term is analyzed through the standard FTRL analysis. In order to deal with the issue that F can be unbounded on the boundary of H.. we define the following auxiliary comparator:
1 K3
1 K3
H.(s)
Hs)s)
H
Mmin (s)
where H min (8) argmin F(H)
НEH,
Applying Lemma 46 for logdet FTRL, we have
-x())-H(()) [EWD EE (TRA H,. H.))))
Atrl
E
1=1
(TE, BR Hs)) H.((s) T(EN)]
K
Bi (FA.A - BR.,H H. H.(s)) [EED
+ E
h=1
T
F
H.
minHen, F(H)
< E
I(E
penalty
27

---

KKK
H
+
En
max (H)(s) - H, HMD HEH,
I(
21)
J= h=1
stability-1
HH(H,H&(s) 11E1)
+ E
Bi
max (Ha(s) H. -k.N) HEH.
21
J= h=1
stability-2
Σ
Ex
(Tan
BR.. H.))) (.0)-HH(S)) 11E
(.)())
(36)
error
Below, we further bound the individual terms in Eq. (35) and Eq. (36).
D.3.1 BOUND bias-1, bias-2, bias-3 IN EQ. (35)
Lemma 24. For any policy Th, there exists qa,h such that for any & E S.. Qε(8,a) 6(8, a) qk,h- Moreover, 11g,,l12 Hvd.
Proof. Define qe. = 0k.h + Esessn (s (0' a')], we have
Qu(s,a) = Q a; 1x) (x(8,a) ))-r))))) + BBuP(()an) Bol
= a(s,a))
Okn +
Σ (s (o((s'a'))
s'ESut
)(s,a) qr.h.
Moreover,
||qx,ell2
0k
Σ
S Vvd+ VQ(H 1) VdH.
2
Lemma 25. Let Ek.h Eanpt BaNau(())) [0(s, ())s,a) 1f probability of o, all k. hi
3dlog(GdH K/8)
then with
c0(d111 /d (dH
|[ (Een En.n) qu,A
5 00 6.h
Proof. This follows the fact the [|q,,u||2 & HVd given in Lemma 24 and the matrix concentration bound in Lemma 14 of Liu et al. (2023a) with union bound over k, h. Taking union bound for all k, h finishes the proof.
Lemma 26. y = (6dHH then
d3
K
H
bias-1 <
K
+
E E (-18)
| a) al)_,, I{Er}
TB
4H
h=1
113
3
K
bias-2 5
K
+
E
E E Barx (11b)
()((,,a)13 1181
4H
A=1
28

---

Proof. Let Bx [-] be the expectation conditioned on history up to episode &s 1. We have
H
E&
=
En (Qu::.. = En [ anaa)
-=h
Therefore,
Eg 9K,n = Ek
k (5 ( T 9k E ER. Ak.
and for E Sh,
Es ())(s,a)-Qule)
Ex [ō(s, a) qknh - ((s, a) [v.n]
= =)) (1- (1-S E. ge.h
=o(s, a) E (Ex. Ezshh) 9ket
S 110(5, a) 1s: (1 (Ex, - Ix.i.) qu. Sxh
(Cauchy-Schwarz)
12 log (dK/0)
(10(s,,)lls
(Lemma 25)
H log (dK/8)
B +
00
||o(s al
TB
4H
(AM-GM inequality)
Thus,
K
H
(Qn(s,)) -(u(ss,)-Qu((.)))) (x(()))))))))))))))))))))))))) MEW
bias-1
E
k=
h=1
H²
B
K
δ
K
E
E B a (15)
[10(s.0)1 m[En)
TB
4H
h=1
Similarly, we can prove
bias-2 2 (d'Hs,
(0(1
K
B
EE
KKK
| a) a)1 11EN} E Bar
TB
4H
Lemma 27. Suppose that BI S catraz where C. 15 15ylog log (12dK) Then
bias-3 5 H2 (Imaxx2 K
Ba (11)) [I0(s a)l [EWN
E
a
Proof. By Eq. (29) and AM-GM inequality, we have that with probability least 5, for all k. h, s, a, (ő(s,a) a) (Wk.h wkxr) < HBC.dB= + 4n [lo(s, 2 Combining this with the definitions of B (8. a) in Line 7 and BB(s, a) in Eq. (25), get
H(C, HCC,d 2
Bx(s,a) - (s) = a 4H |o(s, a) + ((ss T) (0p. - wk.)) 2
2H l0(s a) all H(C,dBmax3
0) - (s(s.a) a With the two inequalities above, we have bias-3
29

---

K
H
E
Σ
Σ
Ex
{ (Ba(s,)) - (,,(,,), - (T(ss) T(E
k=1 h=1
H
E
E Ba 8)
(Blls,a) Ba(
E
E BB a~ (11s)
Ba(s,a) -
k= h=1
h=1
H12 (d K
K
0
+
Ex E (-1))
[l<b(, a) [
2H
h=1
D.3.2 BOUND penalty IN EQ. (36)
Lemma 28. penalty <
3dr 3dr (og(K)
Proof. Since H.(s) = =11- Ke H.(s) + KJ H min())). we have Hs)s) 2 7 min( Then
(F(H.(s) minH EPI. F(H))
det (H min
min(s)) (s))
3dv log (K)
log det (H,
D.3.3 BOUND error EQ. (36)
Lemma 29, error < O (H).
Proof. By the choices of B, Y, it holds that & + ap² s O(K) and # < O(K). Let Tmin be
((s,)))(s,a) ((s.a) a(s,a)
such that H min(s) E, En (1x)
For Sn, we have [Q)(s lØ(s, (a.a)@Taee qq.al I H. by the definition of g and | ll2 I K2, which implies Ba a) UKs 2n} S 2K2.
1
Therefore,
K
H
E (TK.
BRR Hs)s - -H.(s) HEND]
E
K
H
(Fua BR. H min(()) - H. (s) [(EA)]
E
Bi
(by the definition of H. Hs))))
K3
h=11
K
E
Σ
Σ
Ei
((u(s..) -Bx(s,)) (-ms) x" x+1ss) HEWN
K3
< (H)
D.3.4 BOUND stability-1 IN EQ. (36)
To bound stability-1, we first introduce a useful identity in Lemma 30. This is first proposed in Zimmert and Lattimore (2022) and restated in Liu et al. (2023a).
+ 9g"
9
H hh
T
Lemma 30 (Lemma 25 in Liu al. (2023a)). LerG=
and H
g" T
1
h
we have
Dr H Dr(G, H) llg
h
112
11
h1ll
30

---

Lemma 31 (Lemma 12 in Liu et al. (2023a)). Define Ek,h EomutBartttn (o(s,)) 1/7
5d log (6dH K/6) for any k. h, with probability ô, have
Enp
Σ
(s. + F Bnnph Bawae(())) [ E k.
(E
Lemma 32. If7
Lo (dH
then
K
H
[1ob(, a)13 T(EE)) ]
stability-1 S E
E2 B (-1a))
A=1
Proof. In this proof, define
o(s, T) Barx( o) [0(
Cov(s, T) (s (d(s. (ss. (ø(s, ((s,T))]
Cov(s, T) (1) [o(s. a))ss))
Let E2 [-] be expectation conditioned on history up to episode 1. Consider a fixed S and any policy Let
(s,
((saa)
((s) ()
d(s,a)T
We have
((H(s), Hs)))
Eg
((((s) (s))
21
(0(s, Φ(s, T)ll [1(ooo(0mm2))
< Ex
(0(s, 0(8 R), an.n
(Lemma 30)
2n
[|o(s, Tk)
6(8, T) [))
< Eg
| TH) o(s, ( (ovl 1l
21
" E2
(AM-GM inequality)
2
? E
5-1 1 an,h
I
Σ ph
(Cov(s, T)) 2 CCv(ss
2
Cov(e,mE)
nH²
(0sk,,) ak,a) T Cov(s, Th Senhos anmm)]
E+
nH²
Tr (o(sun)ann))ee aw.)) an Eze Cov(s, T& TT) 1
E+
?
2 Tr (E Cov(s, Th TT)
3 n112 Tr (Cov(s, Tx)
(Lemma 31)
=nH²² 2
[|((s, a)
Taking expectation and adding indicator for 8, and then summing over all k. h finish the proof. n
31

---

D.3.5
BOUND stability-2 IN EQ. (36)
Given F(X)
log det Dx) X-1 2 x- where @ is the Kronecker prod-
Q1
01 a2 an let vec(A)
uct. For any matrix A
which vectorizes ma-
an
trix A to column vector by stacking the columns A. The second order directional derivative for F is D'F(())(A, A] = vec(A) (x-1 x-1) vec(A) T PI[AT-IAX' - We define and |||||| 2F(X) = (TX(AXXX). It is a pseudo-norm, and more discussion can be found Appendix D of Zimmert et (2022). the following analysis, we will only use one property of this pseudo-norm which is similar to the Holder inequality. It is standard and also appears as Lemma 8 in Liu al. (2023a).
||Al|var(x)
Lemma 33. For any two symmetric matrices A, B and positive definite matrix X,
(A, B) < || ( BBl
Proof. Since (X ④ XX- -0-1==X0 X-1 X-1 from Holder inequality, we have
(A, B) (vec(A), vec(B)) < ||veo(A/]xx- //lecc/)vll(xeeee////b (oopa///|---ooo//////////aoa-a-/
Lemma 34 gives general argument to bound stability-2 with arbitrary B g(4+1)x(d+1) Similar theorems are also stated in Lemma 34 of Dann et al. (2023b) and Lemma 27 of Liu et al. (2023a).
Lemma 34. For any matrix B E ((d+1)x(d+)) .for any state given &Tr(H BH & (s) m, if
16m
max (H)(s) -.-B) DF (H,HHH((s) < 8n BI (F(H( = Tr TH B HEH,
Proof. For any H E Hs, define
G(H) = (H) - H, -B) DF (H, (s))))
and X |B]| 2F(H)(s))- Since
Tr(H BH m and 17 S 16m we have
1
= B =
S mm -
16
Let H' be the maximizer of G. Since G(H+(s)) = 0, we have G(H') 2 0. It suffices to show
H' - (+ (=F(H(())))))))) 8ι1A because from Lemma 33 leads
G(H') (s)s)) H'l (P (Bl 8n
87 B (F(H.())
< 87,, suffices to show that for all such that IU (s))))l==( ( = Sm², G(U) < 0. This because given this condition, |H' H Hs)s) (=F > Sn,, then there is a U in the line segment between Hy(s) and H' such SnA. From the condition, G(U)
To show H' H (
that U Hx(())lysF(HLte which contradicts to the concavity of G.
min(G(H, G(H"))
Now consider any U such that |U (s)))lv SnA. By Taylor expansion, there exists U' in the line segment between U and H ((() such that
G(U) S U ( BlT-tr 2n
IU (UHH((s) (2=
32

---

= 87 2. From the Equation 2.2 in page 23 of Nemirovski (2004) (also appear in Eq. of Abermethy et al. (2009)) and log det is a self-concordant function, we have |U H (s)) 2 + H xs) ()) Thus, have
We have I10" - - U -
U H & (s) 81112 (81,)2
G(U) S -U--H(S)(VPF(RAAON) |Bll Bll (F(H(()) 8n
0.
8n
Lemma 35. Given Bx(s, a) B| a) 2 + (1 # 16(6, (15 T in Eq. (25) E Sh if 5
wk, defined
3328 (4+0p)) we have
+0 +0 { K).
stability-2 -
E
E Bante()) (B((s
2H
Proof. We can decompose the bonus matrix in the following form and consider stability separately
BE,
B. +
aA
w 0
B BΣ + aaA
+
0
Wk
RT
0
0
2 w
0
B k.hk
B
Then we have
K
H
Dy (H, Hs))))
stability-2- = E
Ex
max (H&(s) - -H, -Be,)) HEH,
1(&,)
21
Am1
H
Dr (H, ((H()s))
E
E*
max HEH,
(H)(s) -H -BBL
I(&,)
4n
Am
H
D H (s))
max (Ha(s) H, B B
1(8,)
HEH,
4n
For any matrix A Raxd with all non-negative eigenvalues, we have
2 =Th()) (A)) (
d
Tr (A²) Σ Xx(A3) S
Since both a(s,a)ō(s,a) T) and BE + aAah positive semi-definite the eigenvalues of o(s,)) (Dig.h + aa are all nognnegativ. Thus, for any s E Zno we have
Tr (x) Ha Hx( $V /Tr ((enntetie) (((s, a) (3S + +a
Tr (Bawns(1s) (0s, ((s,,)) (BS + tad
(owns((1))
010(( +alloss
B + ap²
(1 S Sp for E 2,)
7
Thus, from Lemma 34, if
we have
641f tapp)
K
H
Dr (r(HHH&(s)) HEAL
E
max
(s)
H. -BI
HEH,
4n
A=1
33

---

K
H
80
E
Tr
(s) B H (s) THEN]
1=1
K
Ir Hx((s) H BL.
B
8H
K
[ (3110(5, + aall0(s, M{8)
Bi E (1)))))))
(37)
8H
Now consider k for any Zh. we have
Tr H Hs(8) H
2T ((wx,a) ((WK,a)TBaaanl Bawna(tle) (0(8, a)] (-1a) (o(s, a) [] Tkkn + (Wk,n) (. (aannll))) [0(8, (8)(s, a) a) (x...)
$ 2 Banae()ls) (0(s,a) )
2 1
1
B ( + xtap)) (by Eq. (30))
26H
_
2H
Similarly, from Lemma 34, if S
S
B then for all h E [H] and any state
3328/12 +ap²)
E Zr. have
DF (H,
Hx(s)= - H, -B..A)
max HEH
4n
s 8n Tr (H((s) Bi H. (s) B1,1)
332
(o(s.a) wk.h))
= =32
(o(s,a) Waen + +0ss a) (0k, wknn)? (
< 6471 (o(s.a) TwHN)) (] + 64n [(o(s, a wx ((a + b)2 = 2a² + 2b²)
1
E BaNt [)) wa.n] + Bawns())) a)) (ūR. - wk,
4H
(see the explanation below)
(axdBmax
1 Bante(l))) [p(s, a) [wwk +
4H E P
a (ol((s. a) a| A (Lemma 22 and AM-GM)
Ha
4H
where in the second-last inequality, we use the condition of and that
(K(s,)) a) Wa,n S 1 + sup 10(s,0) ( - -
W(s)I(s's E 2 S Buax
(by Eq. (31))
V'S,
S a) & + (o(s, wk,n $ (2+ 211
Buax
(by Eq. (30))
Thus,
K
max (H) - H, - Dr H,(H)Hx(s))
E
11E
HEH.
4n
h=1
E Ea (T(s,a)T [
4H
K
H
+ a
E E E
(ello(s,)))l I{E) + +
K
(38)
4H
34

---

Combining Eq. (37) and Eq. (38), that if 3328/1
(1, +ap?) then
stability-2
H
[ (110((, a + callé(s,))l3, mENt]
E
B E m (+1b)
8H
F aa [d(8,a) wK TEd
4H
h=1
1
K
H
(ellé(,,a)) MEWT]
+ Ö (dB K
E
Ex E
m (11))
4H
1=1 h=1
1
[B((s, aI + (ddBmar)s K
$
E
E a m
2H
Am1
6d and B I
Lemma 36.
If 1
S
(2280((5+000) and
log " y and
1/ S 3, then we have
E
E (QQ(0,.)) (a(s))) x-' (-1s)
k=1k=1
d²
d (Bmaxx
K+ dr
K +
TB
K
K
H
E Eara (hx (s. a ())((& +
Bowm (ET
H
k=1b=
where by(s, a) is defined in Eq. (24).
3328/² & tap?) adding the bound in Lemma 28, Lemma 29, Lemma 32, and Lemma 35 following the decomposition in Eq. (36), we get
Proof. Since 1) S
dr 17
d (Bmax)²
ftrll < θ
H +
K
nH
Ba (t(1))
I[EN]
Am
E. (tle) (B
(39)
2H
From the decomposition Eq. (35) and Lemma 26, Lemma 27, and Eq. (39), under the specified conditions, we have
H
E
E ((Q((s)))) (ls,,a). x (+1s))
Am
bias-1
bias-2 + bias-3 + ftrl
dH
d2 (2112(Buax))
K dt
< σ
K +
TB
3 ?H²
E E aa (116)
[1 I[s Zn}
K
H
+
E Baaanelll
(s,
H
km
hml
35

---

d
H
de d2
K dr
<ō
+
TB
K H1
K M
B
B
(165 [s, a)l +
E E (11)))))) [B,, {
H
Rim hmm
where the last inequality we use 1 +n S B.
D.4 FINAL STEPS
Lemma 37. Let 8 E Sn. We have
B)(s,a) rx(s,a)) + (1+ 1 H
Ey Pise (Ba(s',a'){{ d'' 2++i]l
where we define
a)) b)(s,)) + (1 [allo('',a')11 Ifs's E Zntii] BB
Proof. Since Bx(s, a) 2 0, we have
B (s, a) (x, a)
= Bx(s, ())(ss)))(
a
110(,, a)) + ((00 a) (0kk. wknn)
=
4H
(axd allo(s, a)
(by Lemma 22)
Thus,
(8, a) Wkih
1
E B.w. (11) B (s', d'Illt's 2n+i}]
1
H
1
+ H
Ben (a [Ba(s', d')l(s' e Bmtill
[allo(s', d')1 HH' 2ntis] 2(C,dBaaxy
a
and
(x
= bb((8, + ((ssa)) (ey,a)Tuk. wk.
< <bb(8, + (1+ H E Pe (Ba(s', 2n41]l
Ifss e Znerd] + 2(C,dBmaxy + Pllaa [allo(s', a'))s
a
1 Ey Bor mb [Ba(s', d'llts's e Zn+ill. H
rr((s, +
[
Theorem 38. Suppose the parameters are properly chosen so that all conditions in Lemma 36 holds (see the prooffor for the final parameters). Then the regret of Algorithm 3 has the following guarantee
E Rxd < δ d (dHH*x?)
36

---

Proof. By Lemma 23, we have for Sh.
Bx(s, 2 (x(s,a) + 1 11 Eg Bl (le) [Ba d') Z4+13l δ ((
1
Combining this with Lemma 36, we see that the two conditions of Lemma 21 are satisfied with d H² (B (mmaxy?
f=O ((Bmaay))
and g = Ö
d² K
+ dr Thus, by directly applying
T
Lemma 21, have
S 2ō =0(31
( TB
de (B 2
dr
reg-term
K
K +
-
1+
Ea Ba-na(Iaa (-1a1) [Bx ($1, a)]
To bound the last term, below we use induction to show that for s E Sh. the following holds:
(1ss) [Bx(s,)) 1 #
V**(s;
for the ræ defined in Lemma 37.
Base case (step H). for any E Sh. we have Ba- (-1s) [Bx(s, a)] (a [b) s (s;Tkk
Induction. Assume that for any Sh+1.
1) H-h-1
B (Be(s, S 1 H
V (*r(5)
Then for any s E Sh, we have
Ea-aa(())) (1)) a)]
(k( +
1
1
B Bewn [Ba(s', (o('',a)) d')]
(Lemma 37)
H
1
BoNTE (-16)
rk(s,a)+ +
1 +
E BS [V (5': (d':
(induction hypothesis)
H
H-h
1
+
Barne(: 0) (r)(s,a)= + (s- (s(Tt())
(rx(s,a) 2 0)
H
H-h
1+
V (8,TT))
Since
(1 +
1
H
< 3, we have
77
1
E (1 [s)
H
< 3
vT (S
K
(dBmaxyz
E Eanut B B-N (1l(s,))13 - allo(s, a)) A.1 K
=
k=
1=1
<ō (dHl + adH + (dBmax)2
K)
Given that Bmaa = 4H (1 + H1
2HH 2 + app) we have mmax < 36H ( + ap?) Thus,
reg-term < 2 (HH3
8H
+ dr + BdH + adH
K
K + d² H
TB
on
37

---

We pick p H K- 7 3328/aH²* that case, if VK 2 16200d log (dK*) = 52 d a H) all conditions in Lemma 36 are satisfied and reg-term S (dd H²
Vdk i HK K², R 5d log (ddH
By Lemma 15, the initial pure exploration phase takes
( - +
d +
Ko
Ecov
episodes, which contributes to an additional regret of HKg (( H²K (omitting lower-order terms). Finally, the cost of ignoring states outside of 2 is K- calculated in Eq. (20).
Combining all parts of regret finishes the proof.
E
AUXILARY LEMMAS
E UNIFORM CONCENTRATION VIA COVERING
Consider policy class
P()) p (o. argmin (H, + F(H)) for 2 HEH,
(40)
where 2 = I- K3 (d+1)x((++)) n. S with S denoting the set of symmetric matrices. We define the following function class.
Definition 39. For any h and any Sh.
VA (s; A,A, = (1+ 1 A
Banp [[]1o(s a) + oJ a)w + 2allo(s, [1] 11s e 2n}]
V/- (V E,A, W.P. Aumin (E) 2 7, Amia (A) 2 1, ||0||| s K² P(s))
where (s)) defined Eq. (40).
We propose the following two covering lemma. Lemma 40 is standard which argues the upper bound of the cover number of Euclidean ball. Lemma 41 inherits from Lemma 15 in Liu et al. (2023a).
Lemma 40 (Cover number of Euclidian Ball). For any >> O, the e-covering of the Euclidean ball in Edd with radius R 0 is upper bounded by (1+ 22)
Lemma 41 (Covering for logdet policy class, Lemma 15 in Liu et al. (2023a)). For any there exists an e-cover P'(s) of P(s) with size log [P'(s) (d 1)a log 21(d+1)² such that for any E P (s), there exists an p' E PP((s) satisfying
Cov(s, p) - Cov(s,p') Sc.
Lemma 42 gives the covering number of function class Vr.
Lemma 42. Let Ne(Vi)) be the || lloo e-covering number of function class Vrrforr any h, we have
log (Nv())) doog [ (1+1
) + de fog 1 16vdB
16K2
1 (1+ 16
ot PPlg
ey
6
96(d + 1)2 (287-1 11 + 2a + K2)
(d + 1)
e
If 9 + 2a S K?, then
400(d 1)2
log (N((W)) < 4(d + 1)2 log
38

---

Proof. Define
B (s D, w) = (1((s, a)l + ( + (s,
and consider the following function classes
B {B (s, a; D, E, w) ||D1|2 S 2, I 2a, ||ll2 S 2k²),
V = {Eaup (s, D, E, w)] (sx, E. E B, E P(s))
For any V1 Bu-pp (B(s a; D1 E1, w1 and V22 Eumps (B, a: D2. E2, w2)] holds that
[V - V/2 = Bawp [B(s, 0; D1, w1)] - Eamps [8,, 0; D2, E2, w2)]
Rawn [Bss, 05 D1, E1, wi) Bump [B(s, (8 0; D2, E2, w2)]
+ Bawpi [B(s, a; D2, E2, W2)]
Eamps [(s,, a: D2, Eg, wz
On the one hand, we have
B (s, a; D1, E1, w1) (s, D2, Eg, w2)l
(16(s,))lf3 - ((((s,)) + (s, (w1- w2) + |lo(,, a) a) - a))
()(s,a) (Di D2) ((s,)) + | (s, (wi w2) - ()s a) (Ei ((),
< 1|D; D2ll2 + ||w - - + E - E2l1
(1(((s 1)
s ||D D2ll: + ||w1 w2ll2 + E1 E2llE
Since for any matrix A Raxd ||||| 1 Vd|l-All, we consider & net on {D E R | z
2vd net on fw E R& ||l||2 2k net on {E E Raxd || I 2v da From
Lemma 40, the log size of these nets
16A
1 16v03
+ of log (1+ 1+ 16vda
dloog 1 +
+ dd log
6r
D2 + E2
2w2
On the other hand, define B₂
we have B2ll2 S 28y + 2a + K2 and
1
[w
2
Bappi [B(s, a; D2, E2, W2)] Eucpz [B(s, D2, E2, w2)]
K Cov(s, P1) (s, p2). B2))
[[ov(s (s) - Cov(s, p2) |B2l2
$ (237- 2a + k2)
(s.(s)))) Cov (s,
Moreover, we construct a 1223 K2 net on policy class P(s) based on Frobenius norm. From Lemma 41, the log size of this net is
96(d + 1)a (2,8 + 2a L)
(d + 1) log
Since clipping and adding more constraints will not increase the cover number, for any h, have
log.) < (Q²) < d'log (1 (1+ 16K²)
+ de log (1+ 16vd3
+ dd log 1 + 16vda de
1+
67
96(d 1)2 (23 -1 2a + K2)
+ (d + 11
Lemma 43 shows the uniform concentration of all functions in V. also appears as Lemma D.4 of Jin et al. (2020b), Lemma D.7 of Sherman et al. (2023b) and Lemma 24 of Sherman et al. (2023a).
39

---

Lemma 43. Let {I,} be stochastic process state space S with corresponding filtration {Fr [FrTT=1- Let {or} be an -vauued stochastic process where or E Fr, and | S 1. Fur- ther, let An Al + + "ー= 0,07. Then for any 6 > O, with probability at least 1 for all
and any V E V such that [V S D, we have
d
+ A
NOOV
8n²e2
(V (I+) (M
4D
log
+ log
An
where Nc(V) alee C- covering number of with difference c.
Lemma 44 (Lemma D.4 in Sherman al. (2023b)), Let (oili Rd (16)
E RR E and
sei A = Eim or + Al, and t = -- diye Then for any wt E Rdd
N
- - w S
Σ
Φi (yi v,w0)
+ Villw*l
A-1
E.2 FTRL REGRET BOUNDS
Lemma 45 (Standard FTRL bound). Ler C Rud be convex set, I1...., 9r RRdd and n > 0. Then the FTRL update
We = argmin wEn
w
Σ Jr
+ =b((w)
ensures for any u. E St and 1/0 > O.
T
we u, 9r) s (u) win (ww)
w. (1) (u we)
Σ
max well
Penalty
Stahility
Since do not use standard FRTL but run the same policy π in 27 episodes. We will introduce blocked FTRL regret bound Lemma 46.
Lemma 46. Let K EZ, S K,J = 1, and set T, = {T(j 1)+ + 1. T5 for all j [J].
Assume 17 > 0, let 9k be a sequence of input, define
Σ KET,
9k, Vjj E [J]
96)
+ 1
"G+1) argmin wel
w,
9(T)
(ww)
Then if wk Ω such that we w() for all k E Tí, E [J], for any S we have
K
gk. We u) < T(bb())
wn (w))
K
w. gk) Du wk)
max(wx wEll
"
Proof. By applying Lemma 45 on I()), T()), we get
Σ (9.,, w() u) < (l)) - min (w))
(w W())
max(w() -w.G))
7
7)
j=1
In addition,
K [h. Wk w)
Σ (9)) w() u1)
Ik: WK
(kk. WK 1)
1=1
KET,
1=1 KET,
k=1
40

---

On the other hand,
Delw, m()))
De(w,
max - w, (1))) wel?
max wEi
wi()
W; Σ 9k
1
kET;
(u(w, wkk
max
Σ KETY
(wk w. w.gh)
well
KET
Dw wx)
max - (0,
WEi
j= KET)
K
max mwax(wx w, w.9h) (w, wk) WESt
k=1
Thus, we have
Sk. Wk - -u 5 T(sb(u) min (ww)
K
max w. 9k) (u, wk) wEl
E.3 OTHER TECHNICAL LEMMAS
Lemma 47. Let Ij be a sequence of vectors, pi a probability distribution and ag arbitrary scalars, then
Σ Plasa <>
Σ Pa 1k:ll1
Proof.
2
2
| Enjof
p.az
Σ prapa
Σ pia
Σ Σ, p, as
Oi
2
pia?
Z
Σ pra
(Jensen's 's)
E Djjj
Σ Pe || )
Σ p.a
41


Reviews:
[{"review_id": "uzJRPdl772", "reviewer": "Reviewer_vRkG", "summary": "This work studies RL on adversarial MDPs with bandit feedback. In detail, the authors proposed the first algorithms for linear MDPs with the standard $\\sqrt{K}$ regret. Although with a $\\sqrt{K}$ regret, such algorithms are not computationally efficient since the computation complexity depends on the state complexity $|\\cS|$. The authors also proposed computationally efficient algorithms with a $K^{3/4}$ regret, which is also the SOTA result.", "questions": "1. Can the authors discuss the possibility of designing an algorithm with a minimax-optimal regret guarantee? Such a result has already been established in [1,2] for linear mixture MDPs with/without adversarial losses, with the full information feedback. [2] also established a lower bound of regret which depends on $\\log|\\cS|$ and $\\log|\\cA|$. Does the same lower bound also hold for the bandit feedback setting?\n\n[1] Zhou, Dongruo, Quanquan Gu, and Csaba Szepesvari. \"Nearly minimax optimal reinforcement learning for linear mixture markov decision processes.\" Conference on Learning Theory. PMLR, 2021.\n[2] Ji, Kaixuan, et al. \"Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs.\" arXiv preprint arXiv:2305.08359 (2023).", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The improvement of the existing regret results for linear MDP with adversarial loss is very important for the research community. The presentation of this paper is also very clear.", "weaknesses": "I do not find any obvious weaknesses in this work.", "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": "", "extra_scores": {}}, {"review_id": "rSYXCIdaaj", "reviewer": "Reviewer_QJAu", "summary": "The paper studies the linear Markov decision processes(MDP) with adversarial losses and bandit feedback. This paper first 1) introduces a computationally inefficient algorithm that achieves a regret of $\\tilde{O}(\\sqrt{K})$, for $K$ as the number of episode in this MDP, and then 2) introduces a second algorithm that is computationally efficient and achieves $\\tilde{O}(K^{3/4})$ regret. The first algorithm is nearly optimal, and the second algorithm significantly improves the state-of-the-art.", "questions": "- What is the practical motivation of this problem? \n- With the help of simulators, K^{2/3} regret can be obtained, what is changed when the simulator of the environment is available?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "- The presentation of this paper is good, and display a relatively clean and timely literature review.\n- This paper clearly presents the intuition behind the results presented in this paper, as well as the similarities and differences between the algorithm and the state-of-the-art (SOTA), and where SOTA offers further improvement on regret, e.g. paragraphs in section 3.1\n- The result of this paper is a significant improvement of state-of-the-art.", "weaknesses": "- The pseudo-code of algorithm 1 lacks explanations. \n- This paper is purely theoretical, and hence doesn't have empirical evaluations.", "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": "", "extra_scores": {}}, {"review_id": "k3vj9EETmG", "reviewer": "Reviewer_B4ir", "summary": "This work establishes the first rate-optimal algorithm for adversarial linear MDPs with bandit feedback, though it is computationally inefficient. Besides, this work also provides a computationally efficient policy optimization (PO)-based algorithm with $\\widetilde{O}(K^{3/4})$ regret, improving previous SOTA result of order $\\widetilde{O}(K^{6/7})$.", "questions": "1. Can the authors give a brief discussion about the possibility or the main barriers to achieving the rate-optimal result for PO-based methods?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. Results: The problem of rate optimal results for learning adversarial linear MDPs with bandit feedback has been open since [1]. It is exciting to see an algorithm, though not computationally efficient, obtaining the rate optimal result for this challenging problem.\n2. Novelty: The rate optimal algorithm takes the same viewpoint that reducing the adversarial linear MDP problem as an adversarial linear bandit problem as [2], but new algorithmic designs are proposed to achieve the rate optimal result, which might be of independent interest. I think the combination of existing techniques to devise a computationally efficient PO-based algorithm with $\\widetilde{O}(K^{3/4})$ regret also has its merits.\n3. Writing: In general, this paper is well-written, with sufficient discussions on the algorithm designs.\n\n[1] Luo et al. Policy optimization in adversarial mdps: Improved exploration via dilated bonuses. NeurIPS, 2021.\n\n[2] Kong et al. Improved regret bounds for linear adversarial mdps via linear optimization. arXiv, 2023.", "weaknesses": "1. In this work, Algorithm 1 used to estimate $ \\hat{\\mu}^\\pi $ for policy $\\pi $ needs to solve a complicated optimization problem, which might be less appealing for practitioners in the RL community. However, I think this is not a fatal weakness, given both the hardness of this problem and the technical novelty in the design of the first algorithm.\n2. Giving a table that shows the comparisons of regret bounds with most related works might further benefit the readers, in my opinion.", "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": "", "extra_scores": {}}, {"review_id": "d38FuFDwUB", "reviewer": "Reviewer_eGft", "summary": "The paper studies the problem of learning in online adversarial linear Markov decision processes in the presence of partial feedback. The authors propose two algorithms. The first one achieves optimal $\\sqrt{K}$ regret bound while being computationally inefficient. The second one achieves a regret bound of order $K^\\frac{3}{4}$, while being computationally efficient.", "questions": "I am interested in understanding why the adversary is assumed to be oblivious. In online episodic adversarial MDP research area, the adversary can be adaptive.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The paper is clear and well-written. The setting the paper studies is of interest both from a theoretical and a practical perspective, and it has gained lots of attention in the last few years. The theoretical results, both for the efficient setting and the inefficient one, are surely improving the state-of-the-art. Indeed, the paper answers different questions raised by prior work (e.g., whether the $\\sqrt{K}$ regret bound was achievable). From an algorithmic perspective, even if the authors employ many existing techniques such as dilated bonus and FTRL with logdet barrier, the novelty is clear. The theoretical analysis is interesting and non-trivial, even if part of it is partially adapted from existing work.", "weaknesses": "- The MDP has a layered structure. Indeed, this is standard in the literature of online learning in Markov decision process and it is without loss of generality. Nevertheless, the dependency on the decision space could be worse than the one presented in the paper for not loop-free MDPs.\n- The dependency of the regret bound on the horizon and the feature vector dimension is far from being good.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)