Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedback
Authors: Haolin Liu
Zakaria Mhammedi
Chen-Yu Wei
Julian Zimmert
Venue: NeurIPS 2024 poster (2024)
Keywords: low-rank MDPs
adversarial losses
bandit feedback
Primary area: reinforcement_learning
TL;DR: We study episodic reinforcement learning for low-rank MDPs with adversarial losses and unknown transition, achieving sublinear regret with bandit feedback for the first time and establishing a tight bound for full information settings.

Abstract: We consider regret minimization in low-rank MDPs with fixed transition and adversarial losses. Previous work has investigated this problem under either full-information loss feedback with unknown transitions (Zhao et al., 2024), or bandit loss feedback with known transitions (Foster et al., 2022). First, we improve the $poly(d, A, H)T^{5/6}$ regret bound of Zhao et al. (2024) to $poly(d, A, H)T^{2/3}$ for the full-information unknown transition setting, where $d$ is the rank of the transitions, $A$ is the number of actions, $H$ is the horizon length, and $T$ is the number of episodes. Next, we initiate the study on the setting with bandit loss feedback and unknown transitions. Assuming that the loss has a linear structure, we propose both model-based and model-free algorithms achieving $poly(d, A, H)T^{2/3}$ regret, though they are computationally inefficient. We also propose oracle-efficient model-free algorithms with $poly(d, A, H)T^{4/5}$ regret. We show that the linear structure is necessary for the bandit case—without structure on the reward function, the regret has to scale polynomially with the number of states. This is contrary to the full-information case (Zhao et al., 2024), where the regret can be independent of the number of states even for unstructured reward functions.

Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedback
Haolin Liu' University of Virginia ersSrh@virginia, edu
Zakaria Mhammedi"
Google Research
Chen-Yu Yu Wei" University Virginia chenyu. www wei@virginia edu
Julian Zimmert"
Google Research zimmert@google.co com
Abstract
We consider regret minimization in low-rank MDPs with fixed transition and adversarial losses. Previous work has investigated this problem under either full- information loss feedhack with unknown transitions (Zhao al., 2024), bandit loss feedback with known transition (Foster et al., (022). First, we improve the poly(d, A, H.H) regret bound of Zhao et al. 2024) to poly(d, A, HYT% for the full full-information unknown transition setting, where d is the rank of the transitions, A is the number of actions, H is the horizon length, and T is the number of episodes. Next, we initiate the study the setting with bandit loss feedback and unknown transitions. Assuming that the loss has a linear structure, we propose both model-basee and model-free algorithms achieving poly(d, A, HYT regret, though they are computationally inefficient. We also propose oracle-efficient model- free algorithms with poly(d, (d, A, Hy)* regret. We show that the linear structure is necessary for the bandit case-without structure on the reward function, the regret has to scale polynomially with the number of states. This is contrary the full-information case (Zhao et af.] 2024), where the regret can be independent the number of states even for unstructured reward function.
Introduction
We study online reinforcement learning (RL) in low-rank Markov Decision Processes (MDPs). Low- rank MDPs a class MDPs where the transition probability can be decomposed as an inner product between two low-dimensional features, i.e., P(x') æz, a) o" (x,a) μ² (z'), where P(z' x,a) is the probability transitioning to state x' when the learner takes action a on state x, and 6² p are two feature mappings. The ground truth features o² and μ unknown to the learner. This setting has recently caught theoretical attention due to its simplicity and expressiveness (Agarwal et al. 2020; Uchara al. [021 Zhang et al. 2022a Cheng et al.) 2023 Modi et al.) 2024 Zhang et al. 2022b; Mhammedi et al.) 2024a Huang et al. 2023). In particular, since the learner does not know the features, it is necessary for the learner to perform feature learning (or representation learning) to approximate them. This allows low-rank MDPs to model the additional difficulty not present in traditional linear function approximation schemes where the features given, such as in linear MDPs (Jin et al. 2020bb and in linear mixture MDPs (Ayoub et al.) 2020). Since feature learning an indispensable part of modern deep RL pipelines, low-rank MDP model that is closer to practice than traditional linear function approximation.
$ TThe authors are listed alphabetical order.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: Comparison of adversarial low-rank MDP algorithms. O here hides factors of order (z. a) for any (Φ, x. a) $ X x A, while other algorithms only require access to Φ(x, a) for any (ø, a) E + x A on visited z.
poly(d, [A, log T, log [ M)). "Algorithm 5 assumes access to Φ(2;
Feedback
Algorithm
Algorithm type
Regret (
Efficiency
Loss
Zhao et al. (2024)
Model-based
Oracle-efficient
Arbitrary
Full-info
Algorithm
Model-based
(TT
Oracle-efficient
Arbitrary
Lower Bound
((v[AT))
Arbitrary
Algorithm 2
Model-based
O(74))
Inefficient
Linear loss
Unknown loss feature
Algorithm 5
Model-free
O(T%)
Inefficient
Linear loss
Unknown loss feature
Bandit
Algorithm 3
Model-free
O(T%)
Oracle-eflicient
Linear loss Unknown loss feature
(for oblivious adversary)
Algorithm 4 (for adaptive adversary)
Model-free
O
Oracle-efficient
Linear loss Known loss feature
Lower Bound
S( ((IATT
Arbitrary
Most prior theoretical work on low-rank MDPs focuses on reward-free learning; this is setting where instead of focusing on a particular reward function, the goal is to learn a model for the transitions (or, in the model-free setting, small set of policies with good state cover), that enables policy optimization for any downstream reward functions. While this is a reasonable setup in some cases, in other applications, the learner can only obtain loss information from interactions with the environment, and only observes the loss on the state-actions that have been visited (i.e., bandit feedback). This introduces additional challenges to the learner.
Furthermore, in many online learning scenarios, the loss function may change over time, reflecting the stationtro nature of the environment or task switches (Padakandla al., 2020). This could be modeled by the adversarial MDP setting, where the loss function changes arbitrarily from one episode to the next, and the changes might even depend on the behavior of the learner. This setting is also extensively studied, but mostly restricted to tabular MDPs (Rosenberg and Mansour] 2019
Jin et al.] 2020a] Shani et al. 2020 Luo al.) 2021) or traditional linear function approximation
schemes CCai et al. 2020; Luo et al. 2021 He et al. 2022 Zhao et al., 2022, [Sherman et al., 2223b
Dai et al. 2023 Liu et al. 2023). The work by Zhao et al. (2024) initiated the study on adversarial
MDPs in low-rank MDPs, but their work is restricted to full-information loss feedback.
When feature learning, bandit feedback, and adversarial losses are combined. the problem becomes highly challenging, and to the best of our knowledge their are provably efficient algorithms to tackle this setting. In this work, we provide the first result for this combination. We hope that result would bring new ideas RL in practice, where all three elements usually present simultancously. We give several main results, targeting at either tighter regret (i.e., the performance gap between the optimal policy and the learner) or computational efficiency, summarized in Table Below we give a brief introduction for each of them. A more thorough related work review is in Appendix A
-eerre algorithm under full-information feedback (Algorithm 1). This setting is studied by the only prior work in adversarial low-rank MDPs (Zhao et al. [024]] and we greatly improve their 7/ regret bound to T4',, Our algorithm begins with a model based initial exploration phase to estimate the transition. It then performs policy optimization where the critic is the Q value induced by the estimated transition and the full information loss.
-regrett moddel-based/model-fe inefficient algorithm under bandit feedback Algorithm 2 Algorithm 5). Allorithm starts with a model-based initial exploration phase to learn an estimated transition, and then runs exponential weights over policy space for regret minimization in the second phase. To tackle bandit feedback, we construct a novel loss estimator that leverages the structure of low-rank MDP to perform accurate off-policy evaluation. Algorithm 5 starts with

---

different exploration phase, where it calls VoX (Mhammedi et al.) 2023) to learn a policy cover; VoX model-free, reward-free exploration algorithm. After this initial exploratory phase, the algorithm also applies exponential weights and utilizes the same loss estimator as in Algorithm 2 However, due to its model-free nature, certain components of the estimator cannot be directly accessed and must be derived through specific optimizations.
T -regrtt model-free oracle-efficient algorithm under bandit feedback (Algorithm 3 Algo
rithm 4). Algorithm 3 also starts with the model-free exploration algorithm VoX (Mhammedi et al. 2023) to learn a policy cover. After that, the algorithm operates in epochs; during epoch k; the algorithm commits to fixed mixture of policies. This mixture consists of certain exploratory policies (based on the policy cover from the initial phase) and a policy computed using an online learning algorithm based on estimated Q-functions from previous epochs (these serve as loss functions). [Algorithm 4 deaals with the much more challenging setting of an adaptive adversary with bandit feedback. Here, we make the additional assumption that the loss feature, which may be different from the feature of the low-rank decomposition, is given. The algorithm is similar to Allorithm 3) with key differences outlined in Section 4.3)
Preliminaries
We study the episodic online reinforcement learning setting with horizon H. We consider an MDP M = P(.H where X represents a countable (possibly infinite) state spacd) A is a finite action space, and P% X' x A + A(X) denotes the transition kernel from layer h to / + 1. We assume that the initial state Iı E X' is fixed for simplicity without loss of generality. For any policy m::a (AA) and arbitrary set of transition kernels [errr)
let p. denote the law over (#1, 01 H. ag) induced by the process of setting #21 = Ti, sampling a1 x1(: (.1 (t).. then for h = 2,.... H, xr ~ Pa-1 (-1 Fh-1, ah-1) and aş ~ (T .x)). We let E.²:" denote the corresponding expectations. Further, let df. (x) (x:) P.. [xx, xx] denote the occupancy of x e X. We also let of (I, = I<> v. as a]. Further, we let EE E ,", P = =I="' ." and d' = =d We use π on to denote a policy that follows (- (-1-) for < and o I-) for k h. Similarly, o n' o''r x" denotes a policy that follows Wa for l < h, T for h s k < h and for k> h'.
T !!
We consider a learner interacting with the MDP M for T episodes with adversarial loss functions. Before the game starts, an oblivious adversary chooses the loss functions for all episodes (Ci. : X x A + [0, _)) For each episode / ε [T], the learner starts at state æf IJ, then for each step h [H] within episode I, the learner observes state æf, Xn, chooses an action a A. then suffers loss E (z)) The state 2/111 at the next step is drawn from transition P (-1 x/1 at))) We consider bandit feedback setting where the learner could only observe the losses E (xf the visited state-action pairs.
C, (1 a'y)
We let II = { : X' + ((A)) denote the set of Markovian policies. For policy x II, loss l and transition kernels PI:H, we denote by " (:):;() the state-action value function (a.k.a. Q-function) at step ε [H] with respect to the transitions Pi: and loss E; that
"
of (z = P
Σ
(a a²) Ib = x., a, -
a
for all aI X x A. We let V P.T (z; == max Pir (I, a) be the corresponding state value function at layer h. Further, we write (T((-=))) of ((...)) and (:: VP ((:E).
For all of our algorithms except for Algorithm 4
we aim to construct (possibly randomized) policies
(x*" [e([]] that ensure sublinear pseudo-regrer with respect to the best-fixed policy; that is,
T
T E ml
Ev((onee)
Regr == min (T)
where Regn (T) = E
Σ VT
(001)))
(2)
xell
FolAlgoríthm 4
we bound the standard regret
T min Σ EV(())))
Regr Σ
ΣVT'
VTT (a); sell (-1
We assume that X is countable only to simplify the presentation. Our results can easily be extended to a continuous state space with appropriate measure- theoretic treatment (see e.g. Mhammedi et al. (2023)
measure-theoretic
3

---

with high probability. This allows it to handle adaptive adversary.
Throughout, we will assume that the MDP M is low-rank with unknown feature maps Φi and v/:
Assumption 2.1 (Low-Rank MDP). There exist (unknown) features maps Vin : A + Rd and Mis X R2, such that for all he & [H 1] and (z,a,x²) E x Ax X:
P| = x' I z, an = a] = 0 (x. 12').
(4)
Furthermore, for all h E [HT, the feature maps Pi and Φj are such that (a.(a.)) 11 (I, s and| Ezzxg(1)) 11 (x)1 & dd, for all g X ~ [0. 1].
Loss function under bandit feedback. For bandit feedback setting, we make the following additional linear assumption on the losses; in the sequel, we will argue that this is necessary avoid sample complexity scaling with the number of states. This linear loss assumption also appears in Ren
al. (2022) Zhang et al. (2022a) for stochastic low-rank MDPs. Note that for the full-information feedback setting, such an assumption is not required.
Assumption 2.2 (Loss Representation). For any t e [T] and layer h, there is vector gi (Ba(1)
such that the loss Cj (x, a) at round satisfies:
((z,a)EXxA, (x, (x,a))
(5)
We note that there is no loss of generality in assuming that the losses expressed using the same features iiи as the low-rank structure in 4 This is because if the losses have different features, we simply combine these features with the low-rank features, and redefine o* accordingly. For the
bulk of our results (and as stated in the prequel), we will assume that the losses (f% (::)) [e(T)) (or equivalently (9% [eerr) under Assumption 2.2) are chosen by an aversary before the start of the game (i.e. oblvious adversary). Section 4.3 we will present model-free, oracle-efficient algorithm for an adaptive adversary.
Function approximation. So far, Assumption 2.1 and Assumption 2.2 are in line with assumptions made in the linear MDP setting (Jin et al. 2020b). However, unlike in linear MDPs, we do not assume that the feature maps Φi are known. To facilitate representation learning and ultimately a sublinear regret, we need to make realizability assumptions. In particular, in the model-free setting, we assume we have a function class & that contains the true features $1.H- In the model-based setting, we additionally assume access to a function class Y that contains the feature maps PL We will formalize these assumptions in their corresponding sections in the sequel.
Other notation. For & II + Rd, we define John yb, II) as distribution μ A(II) such that ( s d for all π e II, where G Even (=x) (T)) This the standard John's exploration or G-optimal design, which always exists.
3 Model-based Algorithms for Adversarial Low-rank MDPs
In this section, we discuss adversarial low-rank MDPs under model-based assumption. The model- based assumption is formalized in the AAssumtton below. This assumption is standard which also appears in prior works on model-based learning in low-rank MDPs (Agarwal et al., 2220 Uchara
et al. 2021 Zhang et al. 2022a Cheng et al. 2023 Zhao et al. 2024).
Assumption 3.1 (Model-based assumption). The learner has access two model spaces T and T such that 6" e & and μ² E Y. Moreover, for any Φ 4, μ & T, and h [2.. HJ. we have (e) (1 (x, ] $ Exex (2, un )= 1 and Exex g(x) pn(2))) s Vd, for all g: X [0.
3.1 Adversarial Low-rank MDPs with Full Information
We first discuss learning adversarial low-rank MDPs with full information and model-based assump- tion. This setting aligns with Zhao et al. (2024), and our Algorithm T successfully improves their regret from T to T/
'The setting where we assume access to function classes that realize both di. and pia is called model-based because it allows one to model the transition probabilities, thanks to the low-rank structure in

---

Algorithm Model-Based Algorithm for Full-Informatn Feedback
1: 1)= HVT (Hd")A)(d) + (A)) and To = [A)). Let xt be
uniform policy.
2: Run (Cheng al. 2023 Algorithm 1) for To episodes and get outputs & $ ji Y.
3: Define transitions Pi.H-1 as
(1 x,a) (x( (nn1())))
(xx.a,))xxxxx
4: for To To ..... T do
5: Execute policy n' and observe trajectory (æI.H a1:H) ) and full information loss El
6: Update policy for all h [H]:
2 Σ (h(,)aa) where (x, = 2 Pi (x, 1
1+1 (a x) oc exp Th
-n
7: end for
As argued in Zhao et al. 2024), the challenge of learning adversarial low-rank MDPs lies in the need for balancing exploration and exploitation both in representation learning and policy optimization over adversarial losses. To tackle this doubled exploration and exploitation challenge, the algorithm of Zhao al. (2024) performs simultaneous representation learning and policy optimization. With closer look at their analysis, we find that there is drawback of this approach: because their algorithm handles the two tasks at the same time, it spends less exploration for representation learning in the early phase of the algorithm. This results in larger error in the estimated Q-values (i.c., critic) fed to policy optimization, and worsens the overall regret.
To address this issue, we design Algorithm aas a simple two-phase algorithm that separates represen- tation learning and policy optimization. In the first phase, following Cheng et al. (2023), perform optimal reward-free exploration for low-rank MDPs to estimate the transition. The resulted estimator, P, is able to accurately approximate the true transition and give accurate Q-value estimators for any policy. The more accurate Q-estimator allows for more effective policy optimization in the second phase. Theorem 3.1
shows the guarantee of Algorithm where Ö hides logarithmic factors of
d, H, T, M Algorithm 1 ensures Reg, s 2O (11 (d (d+++111 +AA)
Theorem 3.1.
The proof for Theorem 3.1 given in Anpppeddix B
Zhao al. 2024) also constructs lower bound for this settings. Thus, the poly((A))-dependeee dependdnce is unavoidable.
2 H HH A
3.2 Model-Based, Computationally Inefficient Algorithm for Bandit Feedback
introduce the first (model-based) algorithm (Algo- rithm 2) for adversarial low-rank MDPs with bandit feedback and sublinear regret. Compared with linear MDPs, the key challenge for more general low-rank MDPs is construct proper loss estima- tor. For linear MDP, since the feature is known, the loss estimator closely resembles that of linear bandits. However, low-rank MDPs lack such structural simplicity, making standard loss estimators invalid. To overcome this challenge, we propose a new loss estimator that works for any loss function based on off-policy evaluation and the low-rank structure of transition. In this section, Ö hides logarithmic factors of d, H, T, |.
In this section, following Assumption 3.1
In[Algorithm 2 we first conduct an initial representation learning phase to establish accurate transition estimator / and its corresponding features and je based on reward-free exploration algorithms in Cheng al. (023). Then, in the second phase, we use exponential weights maintain distribution over the policy space II' where we mix uniform policy with II to enhance exploration. At every round f, a behavior policy x' is chosen from the current policy distribution, and we use the data collected by r' to estimate the value for every π é II'. The success of such off-policy evaluation is based on the following observations of low-rank MDP. Using the low-rank transition structure, for h 2 2, we have
VT E II,
dh(z) ( (()(()) where Φh-1(T) EET [0"[ (0h-1, ap-1)]
(6)
5

---

Algorithm 2 Model-Based Algorithm for Bandit Feedback
Input: A policy class II.
I: Set = T 8 3 - 11= (AFdd))))) and To 0(E (A))).
2: Run (Cheng et al. 2023 Algorithm 1) for To episodes and get outputs o $ j E T.
3: Define transitions Pi.H-I as
(a | 2,a) = ) (m))
xxx,, Ax
4: For all h e [H - 11. define (T) [(E (z, òn (2, a). where dī. = dr P.t
5: Define the policy space II' = { : 3m II, T/( x) = (1 (1-3)mn( (. 2) + Al, Vx, h3.
6: for t= To 1, To + .T do
7: Define p¹ (T) x cxp (-) E (f()) bx)))) for all π II'.
8: p'T) = (1 >))((()) (-++ + म- -H-1 Jn. where J/2 = John (+), 11'). // John as in Execute policy π ~ p¹ and observe trajectory (#i )Hhh and losses fj = f% (a) af)) ())(())() ;(()) vdHe. Em (Ián(T)) (x))- and
9:
10: Define Σ/ = Exe
(()) (a x
(a x/)) lx.
(a xt) 4 + Σ ( (Eh-1)) Φn- 1 (T¹)
ক (a xx1)
h=2
11: end for
Thus, using the definition of the V-function from Section 2
we have for any loss function E and m:
(B())))
Σ Σ
-l a))
(7)
(
Letting A1. (E [0] (T')) (T(")))))) TD= and ingnoring the loss term E[G (z1, a1)] from the
first step (this term can easily be treated as in a bandit setting with H 1), we have for all a e II':
(T(;;; 1E -mp
Σ
(h) Ah )on (TT)) (T)(()))((())) (n( Σ
E Ep
H
(m)
dh (z) x)) Tn(alz).
Ea (n(2,a0)
T.. (a x)
k,a
-p Brd
Σ Sh- (T) 1i
(ah xn) T (an xx,)
Ly (1 an)
Thus, for all f and n, Eh 1/- ( Tn (an xx)) T (an xx) Cn (20,, an) for n' ~ pt and (I), an) ~ di. is an unbiased estimator of V (I1, (). However, $h-1 (T) is not accessible because both the true feature d' and occupancy d" for the true transition are unknown. Thus, our estimator incorporates the learned feature & and the occupancy of P instead shown in Line 4andd 10 Utilizing estimated features and transition could introduce additional bias but the initial representation learning already ensures such bias is small enough to tackle. We compensate for the bias by incorporating an exploration bonus b' (TT) ) in exponential weights. To further encourage exploration, we additionally perform John's 's exploration together with exponential weights when selecting behavior policies. The main guarantee of Algoorihmm is given in Theorem 3.2
Theorem 3.2. Algorithm 2 achieves Reg, ( 5
+ |AlYTT log (Ii) for any π E IL.
Note that the guarantee in Theorem 3.2 only holds for policy æ e II. To ensure our regret bound is meaningful, at least near-optimal policy should be contained in the given policy set II. In general, the size of such policy set would grow exponentially with the number of states (e.g. covering of all Markovian policies), making the regret have polynomial dependence on the number of states. In
Theorem 3.3] we show that even for low-rank MDPs, if the loss function lacks structure, the regret cannot avoid polynomial dependence on the number of states. The detailed construction for this
lower-bound is given in Appendix H

---

Theorem 3.3. There exists a low-rank MDP with | states, |A] actions and sufficiently large T with unstructured losses such that any agent suffers least regret of S2( |
Theorem 3.3 shows that under bandit feedback, in general, we could not gain too much from low-rank transition structure compared with tabular MDPs. This contrasts with the Q ((A)) lower bound in the full information settings (Zhao et al. (2024)). To get rid of any dependence on the number of states, we additionally introduce Assumption 2.2 to impose linear structure on the loss function. Unlike linear MDPs that require the loss feature to be known, our algorithm loss with unknown feature, since our ourlAAoorithm never explicitly uses the loss feature. The linear structure is only used control the size of the candidate policy class in the analysis (i.e., making log] [I] irrelevant to the number of states). Specifically, when both loss and transition are linear, the Q-function also linear, making sufficient to consider the following linear policy space:
even handle linear
T x - (n(a| 1la- = argmin on (2,0) h [H], 10x VdHTT de 3 n:
Im
aeA
The 7 -cover of Uii only have size |b] Lattimore and Szepesvári (2020)) and if we feed into Algorithm 2. our regret could avoid dependece on the size of state space shown in Corollary 3.1
To())) following standard arguments (e.g, Exercise 27.6 of
Corollary 3.1. If the loss function satisfies Assumption 2.2 applying Algorithm 2 with II as the 7 -cver of Ulin ensures Regr s Ô (d 1 || + ".)
Model-free Algorithms for Adversarial Low-rank MDPs
In this section, we consider the model-free setting, where we only assume access a feature class that contains the true feature map 6".
Assumption 4.1 (Model-free realizability). The learner has access a function class & such that
Ø" + and
sup sup (1((,, 1
(8)
de (a.0)eXxA
This is standard assumption in the context of model-free RL (Modi et al. 2024 Zhang et al. 2022b Mhammedi al. (2024a). We note that having access to the function class & alone (instead of both & and T as in Assumption 3.1) is not sufficient to model the transition probabilities (unlike in the model-based case). This makes the model-free setting much more challenging; in fact, until the recent work by MMhammei et al. (2023) there were no model-free, oracle-efficien algorithms for this setting that do not require any additional structural assumptions on the MDP.
4.1 Model-free, Inefficient Algorithm for Bandit Feedback
Our first algorithm follows the same structure Algorithm 2 but incorporates a model-free initial exploration phase introduced by MMammeeii et al. (2023). Unlike the model-based exploration phase, which directly provides an estimated transition, the model-free exploration phase outputs a policy cover. This policy cover can be combined with the optimization in Algorithm of et al. (2023) to solve the expected feature à. which is then used in the loss estimator in Line 10 10 of Algorithm 2 The algorithm. summarized in Algorithm 5 is inefficient but achieves 7 regret. More details and proof's can be found in Appendix D
4.2 Model-free, Oracle Efficient Algorithm for Bandit Feedback (Oblivious Adversary) We now descibe the key component of our efficient model-free algorithm (Algorithm 3).
Exploration phase and policy cover. Similar to algorithms in the previous section, Algorithm 3 begins with reward-free ffre exploratorion phase: Line Algooogg 3, However, unlike in the previous sections where the role of this exploration phase was to learn model for the transition probabilities, here the goal is to compute a, so called, policy cover which small set of policies that can be used to effectively explore the state space.
Definition 4.1 (Approximate policy cover). For a, e (0, and h [H), a subset V Il is an (a, -ppolicy cover for layer h
max di. (x) a max di (x), for all x X such that max d% (x) 2 (x)] New
(10)
m'ell
w'ell
7

---

Algorithm 3 Oracle Efficient Algorithm for Adversarial Low-Rank MDPs (Oblivious Adversary).
Input: Number of rounds T, feature class Φ, confidence parameter de (0,1).
1: Set E T Nreg + T2/3 V/ + Nreg. and To + E- Add H H log(
2: Get 113 + (oX(0,E,0) ē, // Compute policy cover with Vox (Mhameedi et al. 2023
3: for 1=1,.... (T To) do
4: Define t (a x)) ac exp Esch 0% ( a) for h [H].
5: fo + (k 1) Noog + +1, .... To k- Nee5 do
6:
Sample variables Ç¹ ~ Ber(v), ht' unif([H]), and π ~ unuuuniiuuua ( ='t 11(5* 0} 7(K) + =1] 11. on Tunit 9 7((). Execute Ø², and observe trajectory
7:
8:
oyH a²z).
9:
For h E [H]. observe loss e e (3) a.))
end for
11: For he [H] and I(h) = (To + (k: - 1). Nreg + 1, ... To + k. Nreg compute (0) , ((ra)
H Σ s=h
@0h 0)0))) -
argmin
Σ
(on(ah. a a
ls
II(s = or h sh). (9)
(H.0) tez(6)
Set 0/0h (2,
3(k) 0h 30t (I, ( for all (z, xx
13: end for
In Line Algorithm 3 calls VoX (Mhammedi al. 2023). reward-free and model-free exploration
algorithm to compute (1/ (8/().d).)) -pooicy covers V WH for layers 1,..., H, respectively, with , = for all & E [H]. This call to VoX requires O(1/=") episodes; see the guarantee of VoX in Lemma G.I After this initial phase, the algorithm operates in epochs, each consisting of Nieg N episodes, where in each epoch E J. the algorithm commits to executing policies sampled from a fixed policy distribution p(*) (III with support on the policy covers be and a policy 7(K) specified by an online learning algorithm. Next, we describe in more detail how (**) is constructed and motivate the elements of its construction starting with the online learning policies (*(*) ke[K]]
[K].
Online learning policies.
Given estimates (Q(c)) eck of the average Q-functions
1
(rie))
Σ
(11)
Nreg in opoch
sck
from the previous epoch (we will describe how these estimates are computed in the sequel), Algo rithm 3 computes policy ((k) for epoch & according to
(k) (a x)) exp -n 2h (c,a))
(12)
sck
for all [H]. Given state e such exponential weight update ensures a sublinear regret with respect to the sequence of loss functions given by [T(- ()) ()) r Ene( 2(1) (r, (. ] [K]- Thanks to the performance difference lemma, and shown in Luo al. (0221) sublinear regret with respect to these "surrogate" loss functions translates into sublinear regret in the low-rank MDP game interested in, granted that (Q(a) ke[ [] are good estimates of the average Q Q-functions (Luo et al. 2021). In line with previous analyses, we require the Q-function estimates to ensure that the following bias term
27
max aeA
Σ 2hth (x)) (2x
(13)
Nreg in epoch
is small for all h [H]] A [K], and л II.

---

Q-function estimates. Thanks to the low-rank MDP structure and the linear loss representation assumption (Assumption 2.2p. the avegare Q-functions in (TT) are linear in the feature maps Ø-. Thus, using the function class Φ in [Assumption 2.1 we can estimate these average Q-functions by regressing the sum of losses Σ f. onto (a/,, a for É in the kth epoch (as in 9 However, naively doing this using only trajectories generated by ((() would only ensure that the bias term in (13) is small for #(*), To ensure that it is small for all possible policies IT's we need to estimate the Q-functions on the trajectories of policies that are guaranteed to have good state coverage; this is where we use the policy cover from the initial phase.
Mixture of policies. At episode i in each epoch & [K], we execute policy म' sampled from (()) where (8)) is the distribution of the random policy:
TT( = 0) (+() (+) T((' = 13 'T' op Tunit Op1+1 7(K)
(14)
with 5¹ Ber(v), h² unif ([H]) and T' ~ unif( In words, at the start of each episode of any epoch k, we execute 7(k) (see (12 with probability 1- D; and with probability v, we execute a policy in io selected uniformly at random. As explained in the previous paragraph, this ensures a small bias for all choices of in B thanks the policy cover property of wor We now state the guarantee of of[Algorithm 3
Theorem 4.1. Let ε (0,1) be given and suppose Assumption 2.7 and Assumption 2.2 hold. This, for T poly(A, d, HI log((())//)) Th regret against an oblivious adversary.
Ooly(A,d, H, log(()10o) sufficiently large, [Agorithm guarantees Regr
The proof is in (pppenddxx E Note that the T -deeeeddence in this regret even outperforms that of the previous best bound by Zhao et al. (2024) (see Table T}. Compared to their algorithm, AAlgriithm 3 model-free and only requires bandit feedback. This makes the result in Theorem 4.1 rather surprising.
4.3 Model-free, Oracle Efficient Algorithm (Adaptive Adversary)
In this section, we present variant of Algorithm |Algorithm 4) that guarantees a sublinear regret against an adaptive adversary. Given the difficulty of this setting, we make the additional assumption that the algorithm has access to the loss feature @ gloss, which may be different than the low-rank MDP feature 6- (unlike in Assumption 2.2).
Assumption 4.2 (Loss Representation). There is a (known) feature map & Josss satisfying (x (1, a)ll s 1 and such that for any round h e [H]. l [T], and history
H1-1= (xtttr 1dt11), ), the loss function round satisfies
((x,a) e xx Cx ax1xa;H-11) = oooss (x, a) gh.
(15)
for some of e Ba()))
Note that Assumption 4.2 asserts that the loss at round t depends only on the history H*1 and the current state action pair. Before moving forward, we introduce some additional notation we will use throughout this section.
+ Rdd we denote by [o, v) X' A 2d the vertical concatenation of the two feature maps. For any h E [M]] t e [T], policy E 11, and history H (- a 1:, we denote by QT...: the Q-function layer l corresponding to rollout policy म. that is,
Additional notation. For any two feature maps é, tb 2' x x'x
H Σ
(T = E
Es (z,, (x, ) xr x. an
a
(16)
Finally, we let V (2: 11 = maX QT, (xx, a;H:; 11 denote the corresponding V-function.
Algorithm 4 is similar to Algorithm 3 with the following key differences; after computing a policy
cover, the algorithm calls RepLearn (a representation learning algorithm initially introduced by
Modi et al. (2024) and subsequently refined by Mhammedi et al. (2023) to compute feature map T. Then, for every h e ( the algorithm computes a spanner; a set of policies Tpapan {ThI,... 2d] that act as an approximate spanner for the set [E" rop (æ), an), gloes (xh, )=
h
E II) s 1ddd, where use [+ to denote the vertical concatenation of vectors. These spanner

---

policies are then used as the exploratory policies after the initial phase: that is, at episode t in each epoch & E [K], J. we execute policy T(()) sampled from p(t), where p(&) is set to be the distribution of
the random policy: _ = 0} -)(((())___))) + I[ = 1} n' on'41 *(K), ) with Ç² ~ Ber(v). h' ~ ( and n' unif v 2ppn)) ). Here, the main difference to Algorithm 3 (see also (47) is that we use ht
n' unif h policies in the policy cover, as an adaptive adversary's s destory-dependent losses prevent standard least squares regression due to the lack permutation invariance of state-action pairs across episodes within epoch. Estimating the Q-functions is thus more complex, and we approach it in expectation over roll-ins using policies in Vropan the "in-expectation" estimation task is in a sense easier.
( instead of n' u We require these spanner policies instead of
We now state the guarantee of Algorithm 4
Theorem 4.2. Let ò (0.1) be given and suppose that Assumption 2.1 Then, for T = poly(A, d, H, (og((1)))) sufficiently large, Algorithm guarantees with probability at least
and Assumption 4.2 hold.
Σ V (21; 1e[2]]
min Σ Vg (21; H poly ( solp:)")pooo((olooll oo0)(AAd
(17)
nell [e[T]
where T' is the policy that Algorithm 4 executes at episode t E [T].
Algorithm 4 Oracle Efficient Algorithm for Adversarial Low-Rank MDPs (Adaptive Adversary).
Input: Number of rounds T, feature class 4, loss feature gloss confidence parameter 8 (0,1).
1: Set e + T-1/3, Nreg +- T2233 V N and a + (8Ad) Toow + Ad 1 H log((/6))
2: Set rep + 1- AH log([ Tapan + a 2-- A (d $ 1-)1))
3: Define Fr = (I, a) + max dA (Ix T0 0 Φn [shes 2b), 1 $ 0e B2a(1); vh [H].
4: Get Tocoy VoX 11 e, 5/4).
5: Get o/ + RepLearn I1, Fn-1, o uuuuuf Trep), for all h [H - 1]. // RepLearn as in
Mhammedi et al.
2023
6: For all h e [H]. set 1h1
loss h
oh R
7: For h [H], set Spean Spanner (h, $, yeov Jrep
Ph T Topan).
Algori thm
8: Set To Teov Trep Tapan.
9: for k L,, (T)) do
Define #/2 (a x) exp -17 E,ch 0.21) (I, az, for h [H].
11:
for To + (k- 1) Noog + +1 .... To k- Noog do
12:
Define the random variables ç¹ Ber(v), h¹ unif( and n' unif(
Set म' 1[(5"= = 0} 7(k) +I[["= 13 T oh4t1 (k))
14:
Execute म', and observe trajectory (æ af....,, I'n arr).
15:
For h E [H], observe loss e₁ = En (2/, ai
H² where H = (w l:t-1 a
16:
end for
For h e [H] and (1) (To + (k- 1). Nreg + 1, .... To + k. Nieg]. compute g(h)) such that
g(k) h
argmin
Σ
Σ
Ifh' h n' = =1) =1) ( a 0- Σ E
(18)
OeB (4fHd2) ae ppu (EE((K
s/h
18: Set 2/²²)
a) Jrep ()Pp)))))P(())) h for all (z.a) E xxA
((k) (T
19: end for
5
Conclusion
In this paper, we focus on learning low-rank MDPs with unknown transitions and adversarial losses. For the full-information setting, we improve upon previous regret bounds. More importantly, we initiate the study of the challenging bandit feedback setting, developing various algorithms that achieve sublinear regret under different assumptions. However, the optimal vT regret remains out of reach due to the limitations of our two-phase design. An interesting direction for future work is to perform on on-the-fly representation learning to adapt to adversarial losses and achieve optimal regret.
10

---

References
Abbeel, P. and Ng. A. Y. (2005). Exploration and apprenticeship learning in reinforcement learning. In Proceedings of the 22nd international conference on Machine learning, pages 1-8.
Agarwal, A., Kakade, S., Krishnamurthy, A., and Sun, W. (2020). Flambe: Structural complexity and representation learning of low rank mdps. Advances in neural information processing systems, 33:20095-20107.
Ayoub, A., Jia, Z., Szepesvari, C., Wang, M., and Yang, L. (2020). Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pages 463-474. PMLR.
Cai, Q. Yang, Z., Jin, C., and Wang, Z. (2020). Provably efficient exploration in policy optimization. In International Conference on Machine Learning, pages 1283-1294, PMLR.
Chen, F., Mei, S., and Bai, Y. (2022a). Unified algorithms for rl with decision estimation coefficients: No-regret, pac. and reward-free learning. arXiv preprint 0rXiv:2209.11745
Chen, J.. Modi, A., Krishnamurthy, A., Jiang, N., and Agarwal, A. (2022b). On the statistical efficiency of reward-free exploration in non-linear rl. Advances in Neural Information Processing Systems, 35:20960- 20973.
Chen, L. and Luo, H. (2021). Finding the stochastic shortest path with low regret: The adversarial cost and unknown transition case. International Conference on Machine Learning, pages 1651-1660. PMLR.
Cheng, Y., Huang. R., Yang. J., and Liang, Y. (2023). Improved sample complexity for reward-free reinforcement learning under low-rank mdps. arXiv preprint 2rXiv:2303.1083
Dai, Y., Luo, H., and Chen, L. (2022). Follow-the- wwwphh-eeeurrrd-eeeeeeeeee for adversarial markov decision processes with bandit feedback. Advances in Neural Information Processing Systems, 35:1 1437- 11449.
Dai, Y., Luo, H., Wei, C.-Y., and Zimmert, (2023). Refined regret for adversarial mdps with linear function approximation. In International Conference Machine Learning, pages 6726-6759. PMLR.
Dann, C., Wei, C.-Y., and Zimmert, J. (2023). Best of both worlds policy optimization. In Interna- tional Conference on Machine Learning.
Du, S., Kakade, S., Lee, J., Lovett, S., Mahajan, G., Sun, W., and Wang, R. (2021). Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning, pages 2826-2836. PMLR.
Foster, D. J., Kakade, S. M., Qian, and Rakhlin, A. (2021). The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13449
Foster, D. J., Rakhlin, A., Sekhari, A., and Sridharan, K. (2022). On the complexity of adversarial decision making. Advances in Neural Information Processing Systems, 55:35404-35417
He, J., Zhou, D., and Gu, Q. (2022). Near-optimal policy optimization algorithms for learning adversarial linear mixture mdps. In International Conference on Artificial Intelligence and Statistics, pages 4259 4280. PMLR.
Huang, A., Chen, J., and Jiang, N. (2023). Reinforcement learning in low-rank mdps with density features. In International Conference on Machine Learning, pages 13710-13752. PMLR.
Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. (2017). Contextual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning, pages 1704-1713 PMLR.
Jin, C., Jin, T., Luo, H., Sra, S., and Yu, T. (2020a). Learning adversarial markov decision processes with bandit feedback and unknown transition. In International Conference on Machine Learning, pages 4860-4869. PMLR.

---

Jin, C., Liu, Q. and Miryoosefi, S. (2021a). Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances neural information processing systems, 14:13406-13418
Jin, C., Yang, Z., Wang, Z., and Jordan, M. (2020b). Provably efficient reinforcement learning with linear function upproximation. In Conference on Learning Theory, pages 2137-2143. PMLR.
Jin, T., Huang, L., and Luo, H. (2021b). The best of both worlds: stochastic and adversarial episodic mdps with unknown transition. Advances in Neural Information Processing Systems, 14:20491-20504
Kakade, S. and Langford, J. (2002). Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learning, pages 267-274.
Kong, F., Zhang, X., Wang, B., and Li, S. (2023). Improved regret bounds for linear adversarial mdps via linear optimization. arXiv preprint arXiv:2302.06834.
Lattimore, T. and Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press.
Lee, C.WW,, Luo, H., Wei, C.-Y., and Zhang, M. (2020). Bias no more: high-probabilityy data- dependent regret bounds for adversarial bandits and mdps. Advances Neural Information Processing Systems.
Liu, H., Wei, C.-Y., and Zimmert, (2023). Towards optimal regret in adversarial linear mdps with bandit feedback. arXiv preprint arXiv:2310.11550
Luo, H., Wei, C.-Y,, and Lee, C.-W. (2021). Policy optimization in adversarial mdps: Improved exploration via dilated bonuses. Advances in Neural Information Processing Systems, 34:22931- 22942.
Mhammedi, Z., Block, A., Foster, D. J., and Rakhlin, A. (2023). Efficient model-free exploration in low-rank mdps. arXiv preprint 207..2730..03997.
Mhammedi, Z., Block, A., Foster, D. J., and Rakhlin, A. (2024a). Efficient model-free exploration in low-rank mdps. Advances in Neural Information Processing Systems, 36.
Mhammedi, Z., Foster, D. J., and Rakhlin, A. (2024b). The power of resets in online reinforcement learning. arXiv preprint ar arXiv:2404.154: 15417.
Modi, A., Chen, J., Krishnamurthy, A., Jiang. N., and Agarwal, A. (2024). Model-free representation learning and exploration in low-rank mdps. Journal of Machine Learning Research, 25(6):1-76.
Padakandla, S., KJ, P., and Bhatnagar, S. (2020). Reinforcement learning algorithm for statioaio environments. Applied Intelligence, (0(11):0599))) 1):3590-3606.
Ren, T., Zhang, T., Szepesvári, C., and Dai, B. (2022). A free lunch from the noise: Provable and practical exploration for representation learning. In Uncertainty in Artificial Intelligence, pages PMLR.
Rosenberg, A. and Mansour, Y. (2019). Online stochastic shortest path with bandit feedback and unknown transition function. Advances in Neural Information Processing Systems, 32.
Shani, L.,, Efroni, Y., Rosenberg, A., and Mannor, S. (2020). Optimistic policy optimization with bandit feedback. In International Conference on Machine Learning, pages 8604-8613, PMLR.
Sherman, U., Cohen, A., Koren, T., and Mansour, Y. (2023a). Rate-optimal policy optimization for linear markov decision processes. arXiv preprint arXiv:2308. /4642.
Sherman, U., Koren, T., and Mansour, Y. (2023b). Improved regret for efficient online reinforcement learning with linear function approximation. In International Conference Machine Learning.
Uehara, M., Zhang, X., and Sun, W. (2021). Representation learning for online and offline rl in low-rank mdps. arXiv preprint arX0v:2110004652.
12

---

Xie, T., Foster, J., Bai, Y., Jiang, N., and Kakade, S. M. (2022). The role of coverage in online reinforcement learning. arXiv preprint arXiv:2210.01157.
Zhang, T., Ren, T., Yang, M., Gonzalez, J., Schuurmans, D., and Dai, B. (2022a). Making linear mdps practical via contrastive representation learning. In International Conference Machine Learning, pages 26447-2648 PMLR.
Zhang. X., Song. Y., Uehara, M., Wang, M., Agarwal, A., and Sun, W. (2022b). Efficient reinforce- ment learning in block mdps: A model-free representation learning approach. In International Conference on Machine Learning, pages 26517-26547, PMLR.
Zhao, C., Yang, R., Wang, B., and Li. S. (2022). Learning adversarial linear mixture markov decision processes with bandit feedback and unknown transition. In The Eleventh International Conference on Learning Representations.
Zhao, C., Yang, R., Wang, B., Zhang, X., and Li, S. (2024). Learning adversarial low-rank markov decision processes with unknown transition and full-information feedback. Advances Neural Information Processing Systems, 36.
Zhong, H., Xiong, W., Zheng, S., Wang, L.. Wang, Z., Yang. Z., and Zhang, T. (2022). Gec: A unified framework for interactive decision making in mdp, pomdp, and beyond. arXiv preprint a.X1922211.0196.
13

---

Appendices
Related Work
15
B Proof Theorem 3.1 (Model-Based, Full Information)
16
Proof Theorem 3.2 (Model-Based, Bandit Feedback)
17
D More Details of Inefficient Model-F'ree Algorithm in Section 4.1
23
D.1 Algorithm Description
D.2 Analysis of Occupancy Estimation from Algorithm
24
D.3 Regret Analysis
27
Proof Theorem 4.1 (Model-Free, Banfit Feedback)
32
E.1
Bounding the Regret Term
................................
E.2
Bounding the Bias Term
33
................................
E.3
Bounding the Regression Error
................................
Putting It All Together
36
F
Proof of Theorem 4.2 (Model-Free, Bandit Feedback, Adaptive Adversary)
37
Bounding the Regret Term
37
Bounding the Bias Term
38
Bound the Regression Error
39
F44
Putting It All Together
40
F5
Spanner Guarantee
F6
Representation SSpanner
42
F7
Martingal Concentration
42
Policy Cover and Representation Learning Algorithms
44
Policy Cover
44
G.2
Representation Learning
44
Lower Bound for Bandit feedback with Unstructured Losses
46
Helper Results
46
Martingale Concentration and Regression Results
47
Online Learning...
48
1.3
Reinforcement Learning
48
14

---

A Related Work
Learning low-rank MDPs in the stochastic setting. In the absent of adversarial losses, several
general learning frameworks have been developed for super classes of low-rank MDPs which offer
tight sample complexity for either reward-bacd based (Jiang et al, 2017: Jin et al. 2021a Du et al. 2021
Foster al. 2021 Zhong et al.) 2022) reward-free (Chen et al. 2022b Xie al. 2022) settings.
However, these algorithms require solving non-convex optimization problems on non-convex version spaces, making them computationally inefficiency. Oracle-efficient algorithms for low-rank MDPs are first obtained by Agarwal et al. (2020) using a model-based approach, and the sample complexity bound has been largely improved in subsequent works (Uehara et al. 2021 Zhang et al..
2022a Cheng et al. 2023). The model-based approach, however, necessitates the function class to accurately model the transition, which is strong requirement. To relax it, Modi al. (2024); Zhang ct al. (2022b) developed oracle-efficient model-free algorithms, but both of them require additional assumptions on the MDP structure. Recently, Mhammedi et al. (2024a) proposed satisfactory model-free algorithm that removes all these assumptions. Our work leverages their techniques to tackle the more challenging adversarial setting.
Learning adversarial MDPs. Learning adversarial tabular MDPs under bandit feedback and
unknown transition has been extensively studied (Rosenberg and Mansour 2019 Jin et al. 2020a 2021b; Shani et al.] [2020] Chen and Luo] [202]] Luo et al. [022] Dai et al.
Lee et al. 2020 Jin et al.
2022 Dann et al. 2023). This line of work has demonstrated not only VT regret bounds but also
several data-dependent bounds.
For adversarial MDPs with large state space which necessitates the use of function approximation, the transition known, |ooter et al. (2022) shows that adversarial setting as easy as the stochastic setting under general function approximation. For mull-information loss feedback with unknown
transition, V bound is derived for both linear mixture MDPs (Cai et al. 2020 He et al. 2022) and
linear MDPs (Sherman et al. 2023a). For more challenging low-rank MDPs with unknown features, the best result only achieves % regret (Zhao et al., 2024).
For function approximation with bandit feedback and unknown transition, Zhao et al. (0022) provides VT bound for linear mixture MDPs, but their regret has polynomial dependence on the size of the state space due to the lack of structure on the loss function. For linear MDPs, series of recent work has made significant progress in improving the regret bound (Luo et al. |02 Dai et al. 2023 Sherman et al. 2023b Kong et al. 2023 Liu et al. 2023). The state-of- the- art result by Liu et al. (2023) gives an incfficient algorithm with VT regret and an efficient algorithm with 44 regret. These regret bounds for linear MDPs do not depend on the state space size because of the linear loss assumption. We show in Appendix H that cross-state structure on the losses is necessary for low-rank MDPs with bandit feedback achieve regret bound that do not scale with the number of states.
15

---

B Proof Theorem 3.1 (Model-Based, Full Information)
Theorem B.1 (Theorem in Cheng et al. (2023)), With probability 1 6, for any policy x and
layer h, Algorithm in Cheng et al. (2023) outputs transition Pu:h and features on. Ps such that Pa (x' 2, a) 2n(1,, (2,, a) Wn+1(22) and
E [ (.1
Ph (- The an) sc]
if the number of collected trajectories is at least O 1r | log (TdH[()TT))
Define V/ (x1::) as the value function of policy under transition h= and loss L. We have
T Regr(ax) Σ VI (x1:() En (21:
VT (=n;t)) - Di (x1;
PPr (mi;)) (x1;)))
Blast
Blas2
V (2);)) - (x1;))) + o
1 |l(eL + [Al) log² (TdH))lTT)
FTRL
Bounding the bias term. By Theorem B.I and Lemma 1.6
we have
Biasl Bias2 s 2H.
Bounding the FTRL term.
Since HVT have
H
FTRL
S
(an,)
The (111))))))))))))))))))()))) T (-1 an))]
Lemma 1.7)
h1h
H log |A|
H
$
+1]
Σ Σ
E on (xh,
Lemma 1.5
1
h=1t=1
H Hlog |A|
$
+2H '/T
@ an) H)
7
= =0 (H² (H2VTloog|A) log)
Thus, by setting (Hd)Al(dd) + (AI) 3T we have
(1 + +|A)) log² (TdH) + +H H² H LA)
Regt So 0
22
s H (1e + (Al) T log (LA) + +
16

---

C Proof Theorem 3.2
(Model-Based, Bandit Feedback)
Lemma C.1. With PI: as in Theorem B.
we have for any h [H] and any policy n,
(1) d7)
E P(( Bi; a.) P.(. a;; a:)lii] (h 1))
DEA
where d7
dh P.T
Proof. We prove the claim by induction. When h = 1, given that the l|dT di || O. Assume
Σ
(h)))
Σ E [|P oi a.) P.( 20, a.)
axx
We have
Σ (x) dh -c))))))))))))
Σ Σ
(a))) R P% (x)(),
sed aEA
Σ Σ
Σ
ΣΣ Σ asA d'e
()
Σ Σ Σ
xe asA a'
ΣΣΣ Σ ((()) [B([(l))) - Pa(x' ZeX aEA 2'e
Σ (x) -d (x)) + ET [IP Tn an) P.(. æn ax)111
x
h
Σ ET [IP:(.1 æ; a:) - P.(.1 x., a:)] 1=1
where the last step follows by the induction hypothesis. The second inequality of Lemma C.I directly comes from Theorem B.I
Our candidate policy space IT' has 3 mixture of the random policy. For any deterministic policy T 3
define policy x" such that for any state x X, we have x² (-1x)) 3) x)) π II'. Define Vi-T (x1;;) E) as the value function of policy under transition (Pr) M and loss f. For any policy Tे. we have
[A]- We have
Reg, (T))
(19)
H& +1AI) log² (TaH)))))
Σ -
+
2²
H (P +|AI),
Σ
Σ (T' (m); (x
log (THH)T)1M) (20)
+
2²
[dd())))
+
Σ VT' -
Error1
Error2
T
T
Σ
Σ p² (T) (T) (mm:)))))))))))))))))))
D7 (T:
+
D (a: ee) Vi (x)
Bias2
17

---

+
Σ p (T (z))))) Vir (x);)))
Errorl Error2
EXP
(AI) log? (TaH)BmA))
+
(21)
2²
Recall that John( @b (1) sell' Me[H] ATI' H), and have p'(x) (1 7)pp(m))))
y Eh=1 J(T, h) where p'(r) ④)) is defined Line 7 of Algorithm
Lemma C.2. We have
Errorl + Error2 & HyT + 2H ST.
Proof.
T ΣΣ
Σ JTT, h) - -p' -m(m) ( HHT..
Errorl
>1
T H1
Error2 Σ
Σ
ET
Σ mo (a an) n'' (a xx)1 2% (x))); s $2112BT.
where the last step follows by Lemma 1.7
Lemma C.3. We have
Biasl Bias2 & H²Te.
Proof. This is direct result combing Theorem B.I and Lemma I.6
For (C.:H,0H..)) ) n A and IT' where IT' defined in Line 5| Algorithm i the mix of given policy class and a uniform policy, and also the policy class we play with. Recall that the loss estimator
T (a1 σ1)
( aia aia) ==
e (xI,a1)
( 31
(ap xh) eg (z), (22)
Σ
Sh- 1 (Λ) (E%_1)
- (xt)
x (an xpp)
h=2
defined in Line of Algorithm
Lemma C.4. For any episode i e [T], for any policy we have
(T;;"",, a.H a1H)) + VdHl Σ (T(;;() Epr ET [
(T)
h-2
(T(;;))) ".T (T;;"" anss a1H)) VdHe Σ
@h (T) (x yt
h-2
Proof. First, from the definition in Line 4 of Algorithm 2 for any x E X' with h 2 2, we have
(x)) Σ d d') (a- 1
x',aa)))))) a') ) in (x)
where ( Ene (z' We now prove the first inequality:
(x1;))))
18

---

H
= Σ Σ Σ (xn)) (an In) (zn an),
11 anEA
H
Σ (an 21) (1), a,tA
Σ Σ Σ
in (())))))a 2b)) .f, (b) (23)
h-2 24 EX BxeA
First
Remain
Through importance sampling, we have
(i x11. ((1111 ( x1)
First = Batrupt E
We now bound the remaining term in (42) Since _ E''' [ (TT' Jon- we have Remain
H
Σ
Σ
Σ
( (I)-1)² ( ( (T-) 1 (T+) in (n (2 (Th, an),
h= Ea anEd
H
E '.p''
ΣΣ
Σ
( (Ek-1) (T+') -o- (Tt') ( (an (
hnE aseA
(xn)
H
ΣΣ ))-1(T) (2%-1) 0 (dt (xn) I ). (
= 'pp'pp'
h-2aneX anEA
H
Σ Σ (T) (E)_-)) -1 ~n-1 (T" )dh (xn)= (zn,
E upp
h-2 hn2une2 ag
H
+ E sept
Σ Σ
Σ (-) (E%- おn- (T (dh (In) dh (un) In (an a
XnEX aseA
(24)
H
Th (ap an) e (x1 ( (E) (n-1(T=')d (ot (#h,
< E nr xp
ΣΣ
Σ
Σ
Σ
T (ap zn.)
1=2 ShEN asEA
H
Σ @én- (TT (1)))))-)) Enre |1ón- (
Σ
dh (Ix) dh (wn))
(25)
h-2
InEX
Th (a/ xx1))
$ E - B
Σ 2 (T) (E%-z)) (
C% (3 and)
T (an xt,))
h-2
VdHe
Σ 11 (T) (E Amm2
(26)
where 25 follows by Mouchy-Schwarz and the last inequality uses Lemma C.I Adding up First
and Remain, and using the defintion of 8 in 22 implies the first inequality of the lemma.
The second inequality follows the same procedure except for applying Cauchy-Schward inequality in the opposite direction in Eq. (24)
Lemma C.5. If S
2AAlH By
dH
then
log II
6dn |
LATT
EXP
+ And H4 H 4dH2eI,
7
B
where EXP is as in 21
Proof. Recall in Line 10 Algorithm 2 ((T) = VdHe EHz (| for all a e IT' By
Lemma C.4
we have
T
EXP= E
Σ
Σ ('
(x)1;)) Di' (m):()
1=1
19

---

T
2
ΣΣ
Σ p ( En 1 [t (T::T'' (
Σ
_
B (T'::'''' an. ann))
[-]
1m1
H
T
+ VdHl En'(TT) Σ E6 ,)² VdHl Σ
Σ
|| | (x= (22 1
x
h=2
t= h-2
T
ΣΣ
Σ p² (T) (Enispi x1H.
E1
(Ettape ( ( (mn.
T
(+) [T())
VdHe
Σ
Σ
p'
(T)
Σ
(T)
((5 (5
1=1
h-2
+ VdHe
Σ Σ 10 ((
=-112
Σ Σ pz (T) (Et' arr.))))
(Eatape'** (C (
+ AvdHc ΣΣ (T)
Σ ( (+))))))))))))))
(since p'()) s 2p)(T))
(27)
1=1
2=
FTRL Ed.
where
FTRL = Σ
Σ E'((T) (T). E [T(m;'' aam.)
E
T Σ
, an.1)] b6
(28)
H We now bound the FTRL term. Since (T()) = (1 ())'(')))) + Ei=1 [TT h). define E, Even E J(x h) (T)) Note that for any E [T] and h e [H], have Σ yE,. By the triangle inequality, we have for any n, n" and (II:),
T (ai x1
G (21,
(
x1
Σ
H
Øh-1 (T) (Σ% ) 2n-1 (TT)
Tn(an In) (aa(a (an xT.)
el (2 (n)
h=2
A
A
H
Φ)-1( (T) (2%h-1)- 2 (TT²)
8
h=2
(3-mixure of uniform policy)
LAI
LA|
H
Σ
1 (T) x7 (7))
By
[A]
IA|ld
8
B7
By
and
20

---

H 1b( = Vdlte Σ (
s dH?
-1
To ensure 7/ 1/ (x; n² FIH 01:1) by (T) s 1, it suffices to set r)
d.H _
Under
B7
V7
this constraint, from Lemma 1.5
we have
log III
FTRL
Σ P'T) Ex BTT [T;; L.H a1:H)
7
1=1 xell'
Stubility-1
2n Σ Σ ('))))(())
t=1 Tell'
Stability-2
For any t [T], we have
Σ P'((T) Ent-pe ET [ an a..,
(an x2)²
(a x2)² Ey (x),a1)²
Tn(a; xx)²
H Σ
E E Exd
(')))) (= ( (I%-1) 1 (
b (a xb) ly (2 an)²
hm=
Telll
H|
H
(a xx)²
<
+ 22
Σ
E
Ept Exd
Tr (T( (') (E)-1) acd
Σ
(a | ac tg (2),, a)²
3
h-2
(29)
H|A|
2H|
Σ
En
3
3
h=2
3dH
IA
<
B
where 29)
follows by the fact that p'(T) (T) and I- 2. Thus.
En.... ET (T;; ærn. ) Hdn
Stability 2n Σ p'())
8
xell'
Moreover,
Σ Σ (T))
Stability-2 2n/E
[-1 Hell'
= =
Σ Σ 1² (T) (T)- (<
h=2
$ 4n2dH3
Σ Σ Σ p' (2) (x
1=1 h=1 xell
< H
Combing Lemma C.2
Lemma C.3 and Lemma C.5
is (HAHHd 37
+ dHH e )= we have
(T)) s H-T 2H 3T H log III
6dn A(TT
21

---

+ H' 4dH eI + Hdd d'(_AA(de +|AI)
log (TaH)O))))
2²
By setting E = T y= b 3= - 4Hd A 3, T
we have for any To 11,
Regr(T)) ( sO(PH'))
|A))T log log" (TdH)
22

---

D More Details of Inefficient Model-Free Algorithm in Section 4.1
D.I Algorithm Description
In this section, we give more detailed introduction of the algorithm mentioned in Section 4.1 This algorithm is model-free and achieves T regret, but it is computationally inefficient. We consider the low-rank MDPs with linear losses that satisfies Assumption 2. and Assumption 2.2
Let C (S,e') be e'-net of space S. We define necessary policy and function classes in Definition D.1
Definition D.1. We define linear policy class and its discretization as
I
T: X A(A) Ta(a 2) =I(aa
argmin Φ (r, h [H], On Ba (VdHT). & se0).
asA
H (e') = T: A(A) Ta(a] I( argmin on (I, a,) h [H], On c cBs (valIT), .e). Φ5
ae
Define corresponding
funtiitooiinnnuciin function class as follows
F
s s:X (-1111111]
f(x) (b)==><(paae ( for Oe BB and e $
F= 1i2 [-1,]]
ʃ U F" sellm
Our main algorithm is given in Algorithm 5) which shares the same structure as Algorithm 2 but with different initial phase to learn expected feature estimator di, (T) [( di ( ór, (x, a) to approximate 6 (+) Σ (=
(a)z)) (x, a) for every h E [H]. In Algorithm 2 under Assumption 3.1] it feasible use established model-based approach to learn an accurate estimated transition P together with feature ø. The occupancy estimator di is induced by P which also enjoy small errors. However, when move model-free settings with Assumption 4.1 there is existing approach that could guarantee good estimation for dī (x) and
To tackle this challenge, we first call VoX (Mhammedi et al. 2023) to construct a policy cover "i and then play every policy in 1i for episodes collect data. Subsequently, these data are fed into Algorithm to jointly solve estimated occupancy di and feature 61 Algorithm is similar to (Liu et al. 2023 Algorithm 1), which is used to estimate occupancy on the Hly for linear MDP. In Algorithm 6 given target policy π, jointly solve δI ④ di [] and (E1.H,)) ferm c Bdd (Vd) that satisfies four constrains, where Êr,f is the estimation of Ei. = Exex Mh+z (='))(a') (x')) The first constraint [gq. (30) (30) ensures the estimated occupancy di valid distrbutions. The second constrant [Eq. (31) enforces the estimated values to follow the dynamic programming relationship between the occupancy of layer h and layer h+ 1, which helps to control the propagation of estimation errors across layers through the bias of Φ (z. a)TTa Ér.y- - The third constrain Eq. (32) and fourth constrain Eq. (33) are then used to bound the estimated bias of 2n (x, a Ev. by utilizing the data collected from policies in policy covers 1. Note that applying [qq. (33) requires access to the whole state space, which is an additional assumption not needed in previous algorithms.
The gurantee of Algorithm 5 given in Theorem D.1 where the Ō hides the logarithmic dependence on d, H, AA,T.
Theorem D.I. Algorithm ensures Regr s (d log((
23

---

Algorithm 5 Model-Free Algorithm for Bandit Feedback
Input: Policy class II= 1m T
1: Set 18-1
,, 7- T 3, 3- T n= ( n (1250d3\A/T log 3dn
and To 0 A|l1 H log( ()))))()))
2: Get VisH - VoX F, using To episodes.
3: For every policy n's E w play for n episodes and get the data set (D where D
he(H]
consists of tuples (z, a, x²) such that (a, a) df and x' ~ (- x, a).
4: Define the policy space II' { Em E II, Th x (1 (1- m x) 3/1 vx,h).
5: Get (n)()) + EOM-PC [1', (Dr)
from Algorithm
6: for t To + 1, To + .. do
7: Define p¹ (अ) x exp (-n Ei (T) -+())) for all x e II'.
म IH- Jn. where Jr = John (+), IT'). // John as in 9: Execute policy π ~ p¹ and observe trajectory (œ.. aiH and losses fj = f (z) a.))
8: Let p'( (1 - -p- )+((((()))))))))>())) )+
10: Define Σj E p¹ (I) (r))&n(( (T) (T) ", (x) 4 HT 3. E 10 1l ((()))11 and
Taaaj x li. (T)) (a æ1) lf Σ Φn-1 (=) (2% Φつ (
(a xj}
(aj x0/))
h-2
11: end for
Algorithm 6 BOM- (Dx') hel H.
(Estimate Occupancy Measure with Policy Cover)
Input:
The policy class II, datasets (D%) hc[H]] for every n'' E M
Jointly find &n &b, rem) [0. 1] and (En.)) TBd (Vd) for any h E [H] such that for all E II,
Σ (x)=11 y x2x
(30)
Σ di (h))()))(( Σ (1 (feF,he(H]
(31)
xee
ze aeA
Σ T,a,"'DDy'
- (xx)) En.))² (d.)) na,z'EDz''
min
Σ
< 132d (3g(33nHT))9//0)
Vx'e Vin f F [H] (32)
max a) 3.
(fEF,NE[H]
(33)
Output: On :I= Rdd ( E E (Ca whe [H].
D.2 Analysis of Occupancy Estimation from Algorithm 6
Lemma D.1. With probability 1- 6, 6iHH - (d" ( zenro and Eh.s == Evex Evextin (x))())(( Vf
F, Vh e [H] is solution to Algorithm 6
24

---

Proof. Since for any policy π and any h [H], LxEx (x(x)) = 1. Eq. (30) holds. For any policy any f E F" and any h E [H], we have
Σ x'ex
dh ( (z)))(=))===
deed aed and
Σ Σ
Σ (1=2(a)) r'eRao1
zet
Σ Σ
(1)
zett aEA
Thus,
Eq. (31)
holds. From Exercise 27.6 of Lattimore and Szepesvári 2020), the e-net of BB (t) is Thus. [TM [ (+) | (3v " We also have |C (Ba(v d) +) (3v7T) and
BR
for any policy æ. |c (F=, +) | (3v To consider all possible instances, define
N1 == |T||| ( :) [F ((), VIIIEE CO || d (3V 3d
Thus, by union bound, with probability ofl for every IT' every n' Veco every I CC (F".)). every E (B)(v)),e), every & and every [H]. we have
Σ (f(z)) (r,,)) (h,1) Σ ((t,))
s,0,
z.0.T'D
-2
Σ (f(x') 0z (f S (o) ((( (()
z,a,''DD
Σ
(
2,0,''ED
-2 Σ
(f(a') - Eyp B
(x, Eh, (2)))))))))))())())))))
a)x,a) g)
Σ
Wr ( - ((x.))))
WTl 4444 Vdloo
88
Σ
log
5
8
Σ
(0)(z,a) -c,
(Freedman's ''s Inequality)
z,a,r'Dx
Wr
< 20 20 log
(AM-GM)
8 g
120d log
Bounding the distance through -net, we have with probability of 1 8, for every II', every n' e wHt every I E FF, every & E BaBBa (d),, every @ & and every e [H].
Hd
12v dn
Σ (f(x') o7 a) = Σ (f(x') - o(x, < 120d a log
8c
T
a.a
Hd
132d log
Thus, Eq. (32) (32)also also holds. Finally, for all w, a, we have
(2, Th.rl
Σ (x, ( (in wee
Σ P" (x' 22 s(x) $1 lxee
Thus, 6/ d and E == Evex a solution to Algorithm
Vf
he [H] satisfy all Eq. (30)
Eq. (33) and
25

---

Lemma D.2.
With probability 1- for all f F,, any solution d' from Algorithm ofor any π II'
satisffes
-() d'
Proof.
For every solution @I.H Si:H.ffF (dd7. Tell of Algorithm 6 we have
Σ - En.,)
Σ
(Z
",a,''D
2,
Σ (f(z') - ((())))((z,a)) (((.)
min (+iE)
Σ
((z))
x.0,x'EDs
min (0.E) a,a,"'DD
Σ (f(z') 6(x, (x,,
Σ (f(z') (, a
2,
s0
3dn 3dnHTHa +
s 132d log
(34)
5
where the last step comes from the constrain Eq. (32)
On the other hand
Σ (f(z') (2, {,,)) 2 Σ (f(x') - o)
z,a.''D
4
Σ (f(1')
(1(x (h. a 21 a) En.s)
+2
Σ
z,a,''DD
=4 Σ
(f('') - E(o (0) (r, Eh. a (x) En.))
2,0,
+2
Σ (0 Eh. (z, Em.,)
(35)
z,a,''DDp'
Combing Eq. (34)
and Eq. (35) we have
Σ
(øi (I,, T Sn (n
a.O,z'eDa'
5-4 Σ
Σ
(o)(,, Ch. a)
3
264d
log
3dnHT]41
288d log
Lemma 1.2 with À }
Since for every data tuple (I,a,x') Dj', (x, ~ dyf independentl, by Lemma I.3 for every a' you we have
E" (0)(e, - (b,,-,( 5 Σ (,, 24d log
26

---

600d
3dnHT)
log 6
This implies there exists representation @1 (I, a) such that for every f E F and any / [H], there exists f such that
600d
3dnHT|
ET (0
log
(36)
Wrow
Eq. (36) matches Eq. (99) with different error bound the right hand. From Lemma G. Uh is a SAd -policy cover for layer h, following the rest of the proof in Lemma G.2 for every π
have
and every f E F, he E [H], we have
75
3dnHT
E" (z, Eh, (x En.
|A| log
9d
(37)
Vn
8
The a in the second term of Eq. (37) improves the d term in Eg. (98) because En. E BB d) rather than Ba(d)). Putting the choice 11250d | log HdnHTTd and have for every and every f F, h [H]. we have
d T into Eq. (37)
Es
0 (2,
T Ón a) Gn d
(38)
Utilizing above results, for every n. every f F and any h E [H 1], we have
-
(d((r)a(al a))
Eq. (31)
Σ
(x)
(1) Eh, (p)
ax, En.s)
(d)(()) (x(x)))))))) Σ na (a(a) En.
+
oF
dT
Eq. (38)
where in the last step, we define f'(x) E. tn (af2))n E E F. This allow us to use recursion finish the proof.
D.3 Regret Analysis
(e') suffices approximate all We begin by proving Lemma D.3 showing that the policy class (1 policies with small error.
Lemma D.3. For any policy there exists policy n' He (c) such that
T Oe (m)))) Σ (T()))) He'
Proof. Let 0²." (Ba(HHd)) be such that
(2x,)) x (x(z,a(())) = (z
27

---

Such t is guaranteed to exist by the low-rank MDP structure Assumption 2.1 and Assump
tion 2.2 For every [ since Σ 0h Ba Ba(vdTT), define 0g C (Bss VVdlT) .e') such that 10% -E=1 0 & é', and let ny (a x) = Ila argmin 0 (z, a 0, for every é [H]. we have
We have n' 11mm (e'). From Lemma 1.7
VT (x);
Σ (F(a))))
H
Σ
H
T
B
(r'(dlx) (alx)) 07 (2, 0
Σ
aaeA
H
T
mn Σ ((())))) ())
Σ
E
xyd
Σ
(T/(a/x)
(x(a))) (x)
Σ 0 8%
LaEA
aaA
$ He'
where the last inequality comes from the fact that Ta(a) x) = I1(a (a= argmin o (2, a) o) and
10% Σ 0f S é' for every h e [.].
From Lemma D.3. for any policy nj. there exists policy To I (
such that
T
Reg, ( E
Σ VT
(x)
Σ
v
(w);²)
t=
$ E
Σ Vi (xn;
Σ V (01;
+1
(39)
t-1
Our candidate policy space II' has f mixture of the random policy. For any policy To e I ( (+), define policy such that for any state x X, we have x=" π 11'. Define
(+1ax) x=
(1-3) x:) + [Al
We have
(Tr:))
Σ Σ Σ
(<N))Taaa xn) fg (z).
h-1 SA ORSA
Utilizing Eq. (39) and the decomposition in Eq. (21)
together with the fact that [ s d from
Lemma G.I have for any policy .i.
Regr (ri)
T -VV (2x1e()
< E
Σ Σ p' (T) (T) (vT - PT(()())))
+E
Σ
Di (x);8)-
Blas2
T
T -
E
Σ
Σ p' (z) (x1:)))
E
Errorl
T
E
(xx;)) - (21:e)
+O(c= 3 log((/)/))) dHn
(40)
Error2
Following
Lemma C.2
we have
Errorl + Error2 H-TT+ 2H² 3T 33H?T?
(41)
28

---

Lemma D.4.
Biasl + Bias2 & 2d 2
Proof. For any policy x and any L [T],
H
() -xx
Σ Σ (2h) de (2n) Σ Tn(an xx) (In, an)
aneA
d 2
Lemma D.2
Thus,
Biasl 1 dd 22
and Bias2 dd H2TS
We now prove a modle-free free counterpart of Lemma C.4 in Lemma D.5 Lemma D.5. For any episode t E [T]. for any policy we have
H
(T((1;(") s Ex E [C((;; n FiH (ea,,arH)+= + d HT
Σ
d 1 (T)
(x),))
h-2
H Σ
V"(x;;(") 2 Exinp E [f( ær (1HH d HT
Jh- (
(+))
h-2
Proof.
We now prove the first inequality:
(x1;)")
#1
Σ Σ Σ (En)) In)) Eg (2n,
h=1 -l1aee anEA
Σ A
(al (f
Σ Σ (Hn) an) (42)
2=2 ansA
Remain
Through importance sampling, we have
T (ai x1),
First Exteptt E
Et (2)1
We now bound the remaining term in (42 Since E R Exrcpt [bn- (x² don-)nn-- )an-i( (T.) we have
Remain
Σ Σ
(In) Σ
(an (n) an) gh.
aned
==f(#a)
H
Σ
Σ
Σ
ah-1) E (4) 1,
(by Eq. (31)
h=2 1h-1EN
H
Σ (h-1(TT) (TT)
h=2
Σ
-n- P)-1((T) (E)))) Emirpp 16n-1 (TT 1dp-1(1'))) T
A=2
29

---

H
= E nt' "p'
Σ ( (z)-))
H
m -'
Σ Φh- (T) (=))))))))))> (T--( E
(2%
Da En-
h-2
Ih-1edh
Σ 0h-1 (1) ( (1 (T=) Σ (TW)
H
h-2
H
= E xtppp up
Σ ( (+) 1 (
Σ
Σdh to
(In, an)
h=2
H
E -pp
Σ
Φh-1 (T) (00)0//)))))))))))111)) 1-) Σ
Σ
24 Edin a4.
H
L -pp
(2% 1h-1 Σ òn- (
1 (T')
Σ Σ (xx) - (xn) na (an
1=2
H
E pp
Σ Σ Σ
( (Σ/-1) ) ( dd) (21) mn (an on xn) (xn,
1-2 1n22 asEA
H
Σ Σ ( (E)-r)²² dn- (T'))
d HT
E
(by Lemma D.2
SAN anEA
H
(a(a In) lg (2h (1))
< E ''p'''
Σ Σ Σ
( (E% (T-1(TT') (xx, an)
(an (an xx))
1 Dnenee axEA
(T)- Extippt ( (( I
d HT $
(43)
Ta(aj, z//) en (zrha an)))
< p F
Σ (T) (=h-1)= (
T (a% x.))
t HT
(-)
Adding up First and Remain, and using the defintion of é in 22 implies the first inequality of the lemma.
The second inequality follows the same procedure except for applying Cauchy-Schwaar inequality in the opposite direction in Eq. (43)
Given Lemma D.5 we could follow the same procedure in Lemma C.5 except replacing the factor of bonus b' (T) from VdHe d HTT à. This leads to the following changes. Firstly, by a similar argument as Eq. (27) we have
4d H
where
T
FTRL= Σ
Σ (T). (B (m:''' nn (t..=mm.......i)) aun) bb()))
(T))
T Σ
RRT [p(T" ann, (
Secondly, now we have
S rt म2 T
(b( 1
HT 1
Σ
| ||
l H2T-6 V
Tx=
)
h-2
30

---

To ensure 17 n (T; L1H 01:H) - bT(T)) s 1, it suffices to set s (17 -1
[2A + d d
(2.A d H²T- à ) from y 7 3. Thus choice 17 (4Hd)AA)) 'T satisfies the
condition if we assume T d H2, Moreover, now we have
Stability-2 2n
Σ Σ (=)) xell"
=2nd' 1TTT"
H E
2h (+) (+) [(2 (2) ,11
h=2xell'
H-1
s 18T
Σ Σ {+) 11 .
h- well
s 4nd H
s 0 H
$ d HT
(Assume T2 H²)
Putting these two changes back to the proof into Lemma C.5 given r7 = (4Hd 'T- have
EXP log |1 ( (+)
HATH
+ 4nd H + H P + 4. H²T
77
B
6 log
log (b))
(44)
Putting Eq. (41)
Lemma D.4
Eq. (44)
into Eq. (40) together with e = 18 18-1 we have
Regr S 20 50(8 H A|T log((b)))
31

---

E Proof Theorem 4.1 (Model-Free, Banfit Feedback)
We start by introducting some notation. We let ((k) denote the rounds in the k-th epoch:
( (To + (k- .Nrg + ..... To + k. Nreg):
(45)
where To is in Line of Algorithm 3) Throughout the analysis, we condition on the event
E = Eoo,
(46)
where goow is as Lemma G.1 Further, for any & E [K], let p(0) be the distribution of the random policy:
TTC = 0} ((k) TT( = 13 π on Tunit hh+1 ((8),
(47)
with S Ber(v), h ~ (n] and π unif ( ()
We start our analysis by applying the performance difference lemma.
Applying the performance difference lemma. For any & E [K], E I(A), and p(h) as just defined,
we have
E Ex-pi [V (x;;)))) -v -VT (m):)) (m)
(1 (1- v) (v7 (x1i6)) - V/ (z))())
+ 1 Σ
V1 von Tunt ((()
(x): - VT" (x):))))
Hd hc(H] neWoov
$ s(1 10-2/ VV)
E
(a mT) - (a ) Qa (zn az + Hu,
h
h--1
a
(1-v)
Σ
ET
(al xx) - (a x ) 0// (2)) a) + Hv
LasA
(al xT) 10 " (t) (1) (x))))))
+ +(--))
> 1ET
Σ F Lac.A
+ (1-v)
ET Σ (a xn) (0% (zn, a) Q (xn, a; {3) L
Thus, by the triangle inequality, we have
Σ (Em-ptt E [Vi (x1; -V VT (x1))))
kETTK)
H
S (1 (1- Σ
ET
Σ aa
(h) (a xx)) - -ri(al mn))
*NNeeg
(EZ(C)
h=1
H
-0 -)) (a2.
+ 2211 vv)
Σ max n'lll
Σ E (EI(A)
Σ (a|
(48)
h=1
LoaA
We start by bound the first term in the right-hand side of (8) (the regret term).
E.1 Bounding the Regret Term
Fix h E [H] and define #. x) == - (1- (T) ( 2) + Twir |x)/T for all x, where y is as
in Algorithm 3 We have that 10(00 (I,a) = 10000 (x,a) )) s Hvd (since 0(th) Ba (HVHH)) and
(2, s 1). By applying Lemma 1.5 we have that for any n s Hva and x E X:
1
Σ Σ
Σ
(()) RA
(1)
(a|z)) (()a)>((aa)))))
(120((10)) (x.a)
be| K] teT(k) aeA
<
Σ
Σ Σ
7 (al 2)
x (1x
(z, a) + H7,
4c
()Z(() aeA
32

---

Nreg (og(T/>)
K
+ Σ
Σ
Σ h
(a (a x) "x,a)))))))))) H7
asA
Nrgg log(T/>)
+ H2 driT + Hny,
(49)
E.2
Bounding the Bias Term
Fix epoch & [K], round I(k,, layer h [2.. H], and n' E II. Further, let
Xn,s x X: max
(x) 2 e 1n)(()]]
(50)
aell
be the set of E-reachable states. With this notation, we now bound the bias term in (48) we have
(9h ax) -Q@h (ax)
Σ
ET
Σ (a xn)) (1)))
(e
s Σ ET (EE(())
I[ Xmao Σ (/< σn) (Qh 2 -Q
aeA
Σ
ET
E
(a (T.) (0% (m), (10²) an a)
(())
aed
and so by Lemma 1.1
s
Σ ET
1a Xnocc E x/((a| [xx) 10 (zn,, 2
a)) (
22Nrog Hiee
(EI(N)
acA
Ifan Xn.e} Σ ahaa 2T) (1 Σ (t,, -a) -0 a)
NNegg"
E
(xn,
+2N Hd...
Nrog teI(h)
aeA
Thus, by letting
Q (.,)) Nreg teI(k)
Σ Q (,)ee)
(51)
and using Jensen's inequality (twice), we get
Σ E"
Σ
(a xn) (0% (zn, -()
(EZ(0)
LocA
S (Nrog"
E=
I1 E Xn,cc E Thlaa (1))
Rh (0n, 1//²) (2n, +2N Hd&e,
x(())
aed
(0hh x(1)
(x), - 2//h) (2n,) (2)
NNog
T(xa Kn.c) Σ ( acd
+2Nrug Hdle,
< NNog
Mn,c) max and
7(() Qn
(2n, - (1) (2r)
2N HiPe,
and now by the fact that yoro an () policy cover for layer (see Lemma G.I and Defini tion 4.T.:
F(4)
27 (xx, a) -2) (at,, ( + 2N HdPe,
S NNeg
8Ad max re yeer
Man e Xh,s) max
Q
aeA
Nrog
8A2d
Σ E Wante
+)()) @
(I)) - (z),
2N Nru HdLe.
(52)
megroov
Next, we bound the regression error term in the right-hand side of 52
33

---

E.3 Bounding the Regression Error
Lemma E.1. Let & (0,1) and (0, 1/4) be given. There an event w of probability at least 1 26 under which
(k)) (0) (Ih, (z), an) 16 -Qh a(0) (u))
40H (log((/02)))
Σ XeWA
E Muntr
Funtr
Ereg
(53)
V.Nrog
Fix de (0,1), h [H] and &e [K], and let (2/ aj h') be as in Algorithm define
Proof.
With this,
= 11(( 0 h};
(54)
and note that (2% ab I000 are identically and independently distributed. Further, for t E I(k) and ı IT, let 0h By (HVd) be such that
( x (h, = (1, a) O
Such of is guaranteed to exist by the low-rank MDP structure Assumption 2.1 and Assump-
tion 2.2 With this, note that for 2n ((6)
as in (5T) we have
u) on (x (*) where
Σ
0f 0
(55)
Nreg (EZ(N)
For the rest of this proof, we let F be the function class
F= ( (2, 0) - on ( c Cu (
where C is minimal (Nieg) -- -cover of B(H Vd) in distance. Further, for E ((k) we let
=
Σ
f (al
ai);
1=h
7 = Σ
E (at ai)
Σ
20th (2% at; ah;
(56)
Nreg te
1=h
and
T(J) E 1h (f(a), - 2/:2
(57)
(eT(M)
for f F. Finally, let (x, = of a (()) where 0 is as in 55 and f(z,a) = (x,
(x,
With this, note that f. and f satisfy f. (ah, a 2 eh and f argmin yer I(f).
Now, since fe argmin Je T.(f), we have
02 f(ff) T.(..) = v. -
(58)
where V denotes directional derivative and
|l 1 f-1 Σ I (f(x), a;) ff a (EI(N)
Rearranging 58
and using that fx at)) 2 s// we get that
fl f-12 - vD(f.) - f.],
2 Σ I (z), - ff a))) ff',
2 Σ I eh (f(2), at) f. a!)). teZ(9)
(59)
We now bound the right-hand side of For any h [H), & [K] and any f. S. F, we apply Lemma 1.2 with
34

---

8 = o/ () ():: where t; (k 1). Nzeg +
The random variable w" set as the difference
w' l1 or h" hJ sh (f(0) a².) -
-E [T( = or h s hj ch (f(a)) a/) ( 18
where & = (1: 1) Nreg + i;
7t =NNeee = [
R= 2:/411;;0 and
- 1=11(()HH²;
to get that there is an event & of porbability at least 1 - under which
Σ I -h (f(*), a f. (4) af))
teI(k)
Σ E.[T oh (f(#)) a f. f. a]])]
tEI(A)
Σ B. (e)) (f(#), ah)) (w) a) 16 16 1og((
8H
teZ(N)
s Σ E,T E (f(x)) a/,) - f. (z) af)))]
(eZ(A)
1
Σ E.TT (f(2h, a/)) f. (1 af) 16 log((11/))
(60)
where [-[-] is defined E [. 1 3 and the last step uses that | s 2H, for all e z()), For the rest of the proof, we condition on & and to simplify notation
A f(ah, at.)) f. (a/h a.
(61)
Using the expression of e in 56
we have
Σ (EZ(A)
[
= Σ
Eg
I
(
Σ Qh (1)
(62)
Nreg reI(e)
(eI(N)
1=h
Now, since I 11
0 or h s h),, we have
E
Σ Maa at) ah a I
Q afi
Plugging this into 62 and using the law of total expectation, we have
Σ teZ(k)
E.
c A
Σ (k
E,
1/ @ (hin)) Nreg rez(k)
Σ
Σ (zZ(k)
Eg
th Thth) ahi Ail
Σ
Σ Eg
I Q ghthM (#t ahi A
N reZ(k) te
(63)
On the other hand, since (o/ aj In sezi are i.d.d and Ll is chosen by oblivious adversary, have
(1))
E, Ih " (fi E²) - Nieg rez(k)
Σ Er
Ih
Thth (0; 1.) 2/
35

---

Plugging this into 63 shows that
Σ
[T[
Ex
A =0.
(64)
(
Combining this with (60 and (59) we get that
1
Σ hn (f aj) f. (a a ) tezO
& Σ B.[Th (f(x) aA) fo a )
4 teI(
+ 16H log(1F1/0))
(65)
Now, since (a) a/ 11) (e are ii.d., we have by Lemma 1.3 that there is an event E' of probability
least 1 8 under which we have
Σ E. [ (f(m)) a)) f- (a a s Σ T (f(a), al) (1)h, teI(N)
882 log(2[FF/6))
(66)
Combining this with (65) and rearranging. we get that under 800 E n
2 log log(2[F1/5)
Σ Ee [ (f(#)) f-( af))]
(67)
Nreg z(
Nreg
On the other hand, we have that for all t I(k):
E. [Th. (fah), a/) - (m { | E.
=1 [1) ai) S. (a a²))
Σ
Bosst [[f(xt) a/)) f. f.(1),,,)) ) (68)
Hd R
Plugging this into 667 and using the expressions of and f., get
(xx..n)) 0/. Qn Jnth) (00 (zn,.
(3n, )
40// (lgg(1)
Σ ReW
VN
E.4 Putting It All Together
By combining (48 (2)). (53). and (49) we have that under the event : goov nTR (where goo
and greg are as in Lemma G. and Lemma E. respectively):
Reg. HTo Σ
Σ
EE (T (x1;)))
k=[ teZ(h)
Ne log(t/))) HHddTT + Hy. (69)
HT HTD T
V 8.Ad c
"
Thus, plugging in the expression of To from Algorithm 3 and ignoring polynormal factors d, A. H. log( (111), get that
1
Nreg
Regr <
TE TV+ Noog / /APd Eing 2
2N Hds
rgg
+ 1/T, "
2/3 + vT + T 8A2d. o?
TN (by setting e = 1/3 and 17 (Nreg/ 1/2)
1/3
2 DT + T
TN (used the expression of 2 in 53
vNrog
1/4
2/3 + vT T + /T
(by setting Nreg 1/2
4/5
(70)
where the last step follows by setting 1/5
36

---

F Proof of Theorem 4.2 (Model-Free, Bandit Feedback, Adaptive Adversary)
We let ((k) denote the rounds in the &th epoch:
I (To (k- 1)- -Nreg + 1, ..... To + k. NNeeg:
(71)
where To is as in Line 8 of Algorithm 4] Throughout the analysis, we condition on the event
E = gooy n Ereptspan efreed
(72)
where goor, greptsppnn and gfreed are as in Lemma G.I Corollary F.1 and Lemma F3 respectively. We start our analysis by applying the performance difference lemma.
Applying the performance difference lemma. For any ks e [K], 1 E I(4, and let (*)) be the distribution of the random policy:
I((" 03 714) + I[(' = 1} TT' once1 ((),
(73)
with 5¹ Ber(v). h² uniuuiiffu ([ and TT unif unif(u (.))
B BR [iTT (II; 7thh 1 )} 1/"" (
= (1- (v (11; (r1; H - VT" (α); H (11;
11-11
Σ
Σ
V17 ( (21; (ei: VI (æ1; ()):
Hd be[
Troo
H
(1 (1-12 v) Σ
E
Σ
(k) Th (al xx.) - x "xx0((10))
(xh, a; H² H
+ H Niggg
h=1
uEA
H
= (1- Σ
E
Σ
(k) i
(al x.h) mh(a| m))
71--1
HHNreg
h=1
LuEA
H
+ +(1-v)
Σ
E""
Σ LoEA
(1) n (al xn)) (0% (1 ( - (2x,)) 7
h-1
+ +1-
Σ E""
Σ (a xR) ( (h (I), x(()
( 7
h=1
LoE
Thus, by the triangle inequality, we have
Σ (e)(C)
E (Er-ptns E
[V7 (21:7 - VTT (x1:H(-1))
H
s v)- Σ
ET
Σ A
(k) (1(0()) (a xx)) m (al mx)) (/00 (2r, a) H²-1
H NNogg
(EZ(k)
h=1
H
+ 2( - v)
Σ
max w'll
Σ (EZ(()
ET
Σ A
Taalal mn) (en))((0t* (zn, - (xx, 7
h=1
(74)
We start by bounding the first term on the right-hand side of (74) (the regret term).
F.1 Bounding the Regret Term
Fix E [H] and define #. x)) == (1->/T) (. x) + T x)/T for all x, where y is as
in Algorithm 4 We have that (2(h) (x) (x, T ((² &H (since ((A) e eBaa(4Hdd) and
10 rer (z, | [0) (z, a)l + 11
prop az)) s 2). By applying L.5
we have that for any 17 s अेे and
E X:
Σ Σ
Σ
x) - (<)l))><(aaa))) 2/:b0² (x.a)
k]] teT(k) aeA
Σ Σ Σ
(H)
(a) 2) * (1x (z.a) + H7,
4c
()Z(())()))))) aeA
37

---

Nreg (og(T/>)
K
+
Σ
Σ
Σ h
(a (a|x) (I,a)² (x,a) +7,
(e) anA
Nrgg log(T/>) + 64H2 2 d rT -+ +
Hyy
(75)
F.2 Bounding the Bias Term
To bound the bias term (second term (74) ). we make use of the following result.
Lemma F1. For t & [T]. E [H], and π II, there exists 0% (2a(Hvd) such that for all
(z,0) & & and history H = [* lit=1 1===),
(r, H²11) 2 (ar,a) 0'""" where 6 [[oloss . R2d
(76)
Proof. Fix [T], [H] and π II. By the low-rank MDP structure and the normalizing assumption on P in Assumption 2.1| there exists whi BB((H - s) such that for all (x, a) e X' x A and history H - = (#|. .0i:
H Σ 1s-++1
BT
azi azi ohh x, an (2, a) (TaT))/' whh1-
(77)
Now, with l as in Assumption 4.2 denotes the vertical stacking of vectors) satisfies the desired property.
15 and 77 implies that 0² [gh 1, hh1 R (where [+-]]
Fix epoch [K], round & (7k), layer [2.. H), and x' II. By Lemma F1 there exists @r IBaa (2) such that for all (x, a) E X x A.
Qha (I,a: H Th. (z, a) a g
h+1
(.)())
With this,
let hh1
Ba(3Hd be in Corollary F.1 with f(x)
H Hauzs maX 2h a).a) g1 note that this function belongs to the function class Fn+l
in Algorithm 4 With this, we define
g4,00))
(.7(() B2a(4Hd))
gh.
h+1 h+1
(78)
where g Ba(1) is such that en (x, a; H. H(
Bloss (a, a) gh.
With this notation, we now bound the bias term in Eq. (74) we have
Σ ET tez(k)
Σ (a xn) (0% (In, a; H²-1) -) (xn, a)) 7
s Σ
E
Σ .65A
(/a wn)) (0, (xt,) g. (2))((0), (2)) 7
(tz
Σ ET' (EZ(()
Σ o xn) ( (In, a; H LasAA
Jrep ( a) (3. 7
and by Corollary F.T
(in particular (92)
s Σ
ET
Tye (a ux)) (
(5t0 ( a) gr
T
Trep Jre ( 0)0) H
+ Nreg Exept
tcZ(k)
Lo
and by Corollary again (in particular
(93 and the triangle inequality
2
Σ
Σ E (k
Fo an) T p an) TO( -
Nreg Espan + Nrog Erops
mee regapon
2 Σ
Σ
ET
Q az a; H²11)
J.op (xp, ) To(k)) H + Nieg Espan NNeg Srep
TEe Paan h
(EZ((k)
38

---

(a a 10 Qhh (0h, a; 7 71-11 7 ]
+2
Σ
Σ
Trep hh
(triangle inequality)
span Tee A
(EZ(())
2
Σ
Σ (ET((
E"
2
a
a; a; 71-11 - 1i (xn, and T 77 H2-111 Noog Sspan -33.NN Nog. Sreps
NEW TEV sppnn
(79)
where the last inequality follows by Corollary F.1 (in particular (92))
Next, we bound the estimation error term in the hight-hand side of (79).
F.3
Bound the Regression Error
By
Lemma F.3
(Freedman's 's inequality), we have that for all uapan and O (2d(4Hd)))
H
Nrgg @freed
Σ (=2())
T(h' h1 TF' 5= 11 ( a
Σe
Σ s=h
Σ AEI
E 1hh' h n, =²
(, T
(
Σ e
(80)
a-h
On the other hand, we have
0/ (10 a 0-
Σ 1k7(k)
E
I(h' h1 T' = = =
Σ
et 7
s=h
H
Σ
E (T
2h ( an) 0- Σ Eg H4-1
Hd teT(()
s=h
Σ E"
Trop (aa, an) ((( (oh, a H H1
(81)
Hd teT(())
Now, by Corollary F.I
(in particular 92
and the triangle inequality, we have
Nieg Srep 2
Σ 1
0
(hh, an) Qh (on, a; H²-1) 7
(eZ(k)
Σ E
Trep (Ih, ar) 0 " an) ( 1
(k
Σ E
Trep
(xx, an) Q (I a; H! H1'11
hh
(eZ(()
E
rep (khh an )
Nreg 0- Σ
h
(EI(A)
Thus, by combining
80
81
and
82 we have
Σ Σ
I(h h T n. C' = 13
Trep (2/, (TeP
T
Σ e
se dpan
(EZ(k)
amh
< <dNreg Efreed + V.regErep
Nreg 0- Σ g1,000 tkZ(k)
H
Hd
Σ
E Σ
Trep oh
(I),
h
Rev
(tz((k)
Using that (()))) is the minimizer over Bea( (HH(4dd)) of the left-hand side, and the right-hand side evaluted to d.rrgg Streed + MNecx with = Now EiEOas (..5t) B2a(4HH)) we have that
H
T ( T0(K))
VNroggrep
Σ Σ 1ftt' h, T' = -, ==,5=11 =1] mnan
Σ et
S <dNeeg Efreed
H
((k)
39

---

Now, combining this with (80
and (8
with 0 =0 we get that
Σ
Σ
E
9h
rop
(0
an (1a)) Qh (oh, a H H1-11
ThE 10
(EZ(N)
H of SreeStreed
Hd
Σ
1(h2 h x' =-, =1
T.oe (2)
(c) T0
Σ
"
V
V
xevapan
(EZ(A)
swh
2Hd Neegeeeeeeee freed
d.N d.Nrege Erep
(83)
F.4
Putting It All Together
By combining
74
and 75 we have that under the event (72
Reg, = HTo
Σ
Σ
p(
VT (I1; 7
11" (z1:
ke[ (eZ(A)
2H TT
$ HTo HT T Espan + 3dT Erep" +
Nrg ((7) 6AH d' + Hy.
dTeppppp
(84)
"
Thus, plugging in the expression of Tu, freedd, and (Espan; from Algorithm 4 Lemma F.3 and
Corollary F.I respectively, and ignoring polynormal factors A, H. log - 0 we get that
T
Nreg T/T,
Regr < 22 + Te Tu+
Nieg
1
2/3
TN 1/3
/TNIRR
(by setting e 1/3 (Nrog/ No1
(85)
T/4 (Nieg= 7
(86)
where the last step follows by setting Nreg 72/33
F.5
Spanner Guarantee
Algorithm 7 Spanner:
Computing Approximate Spanner.
Require: Layer h, feature classes क policy covers VLH, feature map Ø X' A
2d
# of
episodes n.
1: Define G= {g: (I, a) + ((x, a) w Φ w Ba(2vT)).
2: For 0 E addd and (x, a) E X' x A, define
re F((x,,;0) = 5n a for t= h otherwise.
(87)
3: Set Gr. = ((x,a) a 0 (2a(1)), and for / e [h - 1], set G. G.
4: For each E [h]. set P. = (V..
5: For 0 e 2d define LinOpt(0) PSDP Fin (s 01.h Pin,, n) E TT.
// PSDP in
Mhammedi et al.
2023
6: For 0 E 20
and π II, define LinEst(r)) EstVec h, Zn. n, // EstVec in Mhammedi
at al. 2023
7: Set 1:24 RobustSpanner LinOpt LinEst(-),
Adl (og(ndif()//8
on
Robust.Spanner in Mhammedi
2023
8: Return: Policy cover ,,,..., T2d)
Lemma F2 (Spanner Guarantee). Let s, 8, (0,1), h H)) 2 1, and tn X x A 2d
be given. Suppose that AAssmmtiin 2.7 and Assumption 4. hold, and let Vish be such that for
all [h]. V is an (a,ε)-policy cover for layer with VVa 2d. Then, the output y u
40

---

Spanner(h, Φ, 1ı.. n).n) (Algorithm 70 is such that ( 2d and, with probability at least 1 6, for all x' =II, there exist (8x E 22, : π E 1or such that
Σ Br E" [ and] s (n, me
E"
(88)
where
Espan (n,, (,,0 cH dA. (dloo((nV/HH)) log(nl01/0)) H22
(89)
on
where e> 0 is large enough absolute constant. Furthermore, the number of episodes Tspan (n) used by the call to Spanner is at most (HH2dn)).
Proof. To derive the desired bound, we will use the generic guarantee of Robust SabusttSpanner from (Mhammedi al. 2023 Proposition E.I). To invoke this result, first need derive guarantees for the optimization and estimation subroutines LinOpt and LinEst withn the Spanner algorithm (Algorithm 7). In particular, we need to show that there is some e' (0, 1) such that (with high probability) for any 0 IR2d (0) and IT, the outputs सg LinOpt(0/|00) and d=th LinEst(R) satisfy
sup E" (xn, an)] s " (Kh, an)] ] E ||0|| and 11 E [on (2 ax)]ll s well
(90)
With this, we can apply MMhammedi et al. 2023 Proposition E.1) to get that the output Ti2d (Liust)p LinEst)(
for e & 2e is such that for all e II, there exist BI,..., Ba [- 2] satisfying
E" (2% ax)) Σ 3e E [ (x an)]
s 6ds'.
(91)
1=1
Since LinOpt is based on PSDP as in Line 5 of Algorithm and V 1,...., Mr are (a, -ooiicy covers for layers 1 to h. respectively, (Mhammedi et al. [023] Corollary H.1) implies that there is event gPSDP of probability at least 1 0/2 under which for any e gdd satisfies
x {0), the output âg = LinOpt(!))
sup rell
M [ (an, an)] 0 B (xn,,
dA (dlog((nn//ul log())))00))))) H² 8/2
110
cH2
an
for large enough absolute constant e > 0. On the other hand, since LinEst based on Est as in Line 6. (Mhammedi et al.) 20233 Lemma G.3) implies that there is an event E eastee of probability
at least 1 6/2 under which for all II, the output d= = LinEst(T) satisfies
т E [on (xt, ax) s c. (2/0)
for large enough absolute constant 0. Therefore, under CPSDP n gEstVes LinOpt and LinEst satisfy (90) with
cH2 dA (dlog(2nv/(HH) (og()))))))))))))))))
2 2/2
an
Therefore, by (Mhammedi al. 2023 Proposition) and the fact that dy output
Alog(ndH((100) e', the an
Alog(ndH((//00)
T1:2d RobustSpanner
Lin0pt(-). LinEst())
an
is such that for all π e II, there exist
,I...., B2d [[-2,2] satisfying
2d
E [o (x), an)]
Σ
8, E (Zn (z)))a))) S Espau (n, 6),
where Espan (n, an, is as in (8).
41

---

Bounding the number of episodes By (Mhammedi et al. 2023 Proposition E.1), RobustSpanner calls LinOpt and LinEst as most (dd) times. Each call to LinOpt [resp. LinEst] requires H episodes. This implies the desired bound on the number of iterations.
L
F.6 Representation + Spanner
Corollary F.1. Let e, (0, 1), &I:H- and Apar be in Algorithm 4 Then, for all h [H].
hh 2 and [ 2d and there is event greptspan of probability 36/4 under which for all he [
For f Fh+1, with Fn-1 as in (97). there exists w/I1 Ba(3d/22 such that:
VT IT,
E" 0h (an, an) wh E[ Th an
s Erop = 10d (92)
For all n' e II, there exist (3x E [-2,2]: ; E Vaaann such that for oh == [0h %
Ea 1
rop (an; an)]
Σ Br [
( (xn, an)] Espan = 2//2,8/22
(93)
ITE woomm
Proof. From Algorithm
we have
%h rep
Fh. D unif(W/ ( Trep)
and apan Spanner (h, Q With 2h :Tapau);
where
T AH log((
Alog Alo
T span
(94)
ag2
and a = 8.d' By Lemma G.1 there is an event goow of probability at least 1 - 6/4 under which, for all [H]. yo is an a, E) pollic cover for layer h with | d. In what follows, we condition
1
on goov By Lemma G.2 and Lemma F.2 there are events reep and Expan of probability at least
1-6 each such that under g 2 (92) and (93) hold; this follows from (98) and (88) and the
choices of T rep and T span in (94 Finally, the union bound, have P[g n n Capan which completes the proof.
F.7 Martingal Concentration
Lemma F.3. Let K, Nreg. Jrep and (1k) be as in Algorithm 4 for ke [K]. There is an event gfreed of probability at least 1 - 8/4 under which for all 0 Bea 4H d d) h [H], l E [K], and π yapan
Σ ((z(()
l1 = h n = = =11.
rop ( a
Σ amh
Nieg
vlog (dK H Nieg
Σ tEZ())
E 1 =,, = 1} 0h ( at T
Σ eg
H
S Efreed = 4Hd
Nreg
where the random variables h' St n², and - are as in Algorithm
Proof. Fix Ā e B2a(4d?), h e [H]. lo {[K], and æ pa We apply Lemma I.2 inequality) with
(Freedman's
R= 4Hd2:
* n -Nreg
The random variable wt set as the difference
H w² = I( h, th: n, 5h 13 1 (, a
Σ t%:
s=h
I(h" h, n" n, &² -h== 13. Trep (ToP( a
Σ E E
12
(95)
s=h
where = (k- 1) NNeeg +
42

---

The filtration S' set as the o-algebra oHH"
The variance term Vn has the following upper bound
Nick Σ
New
Vn
E
[(ww))
Σ
E
I(h' h TT' - 13 Op
(a
a
Σ
18
8=h
s VNeegi
duN log( ( Neox//
A 111
to get that there is an event efreed k (0) probability at last 1- (Nreg) H K- 1/8 under which
H
Σ
T(h2 h, π = = mm
Trep (a af)
Σ
E
N (2eI(())
s=h
E 11 h n 5T, 5 13 (0) (3. ax)
11
Σ
a
Σ Eg
7
vlog (dk H (
2
(96)
Nreg
Let C be minimal (dHNNreg) -eeeeNee--oooo -ovvr of (22(AHdd) with respect to the || distance. Under the event
gfreed
freed h. (0),
( (eH2a
Eq. (96) holds for all h [H],k: k [K] and 0 Bza(4Hd up to additive O(1/Nreg) error. By the union bound, we have [P[ 2 - 8/4 which completes the proof.
L
43

---

G Policy Cover and Representation Learning Algorithms
In this section, we present guarantees for VoX, RepLearn, and Robust which we need in the analysis of our oracle efficient algorithm. The results are based (Mhammedi et al. 2023).
G.1 Policy Cover
The following result is restatement of (Mhammedi al. 2023 Theorem 12).
Lemma G.1 (VoX Guarantee). Lete, Ó (0, 1) be given.
2.1 2.1
4.1
hold. Then, there is event gsoo of probability at least under which the output Wi:H VoX @b, e, 6) is such that for all he [H]:
wh is a (3 () cover for layer h;
| d.
Furthermore, the number of episodes Toov (e) used by the call to VoX bounded by O(Ad*HH log(2/6))/=2.
G.2 Representation Learning
Lemma G.2 (Representation Learning Guarantee). Let E, a, (0,1), [H 1]. and 2 be given and define the function class
Fh+l f: (z, max 0h+1 (x, 0h+1 [dloss 1 D, ( B2))
(97)
asA
Further, let y be (a.gc-policy cover for layer h with | d. and suppose Assump tion 2.1 and Assumption 4.1 hold. Then, with probability at least 1 1- 6, the output oh RepLearn Fr+1: D unif(V), is such that for all Fht there exists wh e Ba(3d/22
such that:
AHd log( /d
Va II,
E
1e Oh (mn, an)
" -E[((r)-1) an, an) sc.
an
(98)
where e> is a large enough absolute constant. Furthermore, the number of episodes Trep (8) used by the call to RepLearn equal
Proof. By Mhammedi et al. 2023 Theorem F.1) and the assumption that |T] = d, there is an event & of probability at least 0/2 under which o satisfies:
Po (æn, Jn E[((vnn)) æn, an)))] s Ad log((
sup inf max ET [(o feFmn (3dP/)) n'ew
n
(99)
where c is large enough absolute constant. We use this to show 998 In what follows, we condition on E. Fix e ll and f G and let wfe be the vector w IB (3d achieving the infimum in (99) for the given choice of f. Let Kn.s be the set of s-reachable states at layer as defined in (50). With this this, we have for all h [H],
ET t P an) Tw [[[(()+1) Chi an]]
[ Kr.e} ( a "w/ (x((()))) The an1)]]
E [1 Xn.c) (o) (wh, an) Tw B[ an, an)))
E [I e Khee) (6) (x) an)) T [[f(()+1) The an]) ?2,
(100)
where the last inequality follows by Lemma
We now bound the first term on the right-hand side of (100). By Jensen's inequality, we have
E
[(xx E Kh.s) (0)
rep (x), an ) w/ h+1 E[f( æh, an.))
44

---

I( e Xh.t) (0 (ah, az) Jw [ f (xh+1) wh. anl)² Er
and so using that v is a (a, -oollic cover (see Definition 4.1,. we have
max ale
Er'
[0 (I an) www E[f((znn) 2n an
A log (1/6
where the last step follows by
99 Combining this with (TO0) yields (98)
45

---

H Lower Bound for Bandit feedback with Unstructured Losses
In full-information, one does not require any structure on the losses. We show that this is not the case for the bandit case via lower bound depending polynomially the number of states. This lower bound implies that the low-rank transition structure with unstructured losses does not give any significant improvements over the tabular setting.
Theorem H.1. There exists a low-rank MDP with S states, A actions and sufficiently large time step with unstructured losses such that any agent suffers at least regret of (VVSAT).
Proof. We assume 48 < VT The construction is an H (i.e. contextual bandit) MDP with uniform initial distribution over states. Each state is copy of an A-armed bandit problem with Bernoulli losses with mean }. and one randomly chosen optimal arm with mean A. Following the standard lower bound construction for bandits (Lattimore and Szepesvári 2020), there exists - ( / /TAS) such that the the regret of playing any individual bandit problem for N s 2T/S rounds lower bounded by (NNA.. Let denote N (s)) the number of time the agent receives the initial state then any agent suffers regret lower bound in our MDP of
S Σ (M))
(s) the sum T Bernoulli random variables with mean 1/8. We have by Hoeffddiggss inequality
P[N(s) > T(Ss))T/S++H x] exp(-2x²/T)
This allows to upper bound the tail
[ x(2x/T exp(-2x² (T)) dæ
([N(s))(NN(s) (
JT/s
4exp(1/VT de
(///VTT2 <exp(x/VT)
$
Tis
<
4exp( (opp(=//VTd dr
(x2T/8>4VT)
T/S
4V T/Tepp(VVT)S) 4VT exppx) (T((SS)
Hence [[m), [ (())))())))))(( > 2T/S)) 2 T/(25) and the regret in the
MDP is lower bounded by 92 (VTSA).
I Helper Results
Lemma L11 Let e, B. 0 and [2.. H] be given. For any function f: f: [-B, and II,
we have
Ea[I Nr.c) [(xx)] BVde.
(101)
where
Xn.e x max (x) 117 xell
(102)
denotes the set of states that are e-reuchable at layer
Proof. Fix f: X - [-B, B) and æ e II. Using the definition of Xr, in (12), we have that x & Xr.s
only if d (3) ellpi (x:]]- Using this, have
EA [I (xn $ Xn,c) f(xx)] Σ I[x Xm,c) (z) f(x),
Ded
Be x
Σ (x)
< M22
(103)
where the last step follows by the normalizing assumption on 4¹ (see Assumption 2.1 and (Mhammedi et al.] 2023] Lemma I.3).
46

---

L11 Martingale Concentration and Regression Results
Lemma 1.2. Let R be given and let w', y-.. .... be sequence of real- random variables
adapted to filtration 8' "", ",,""" Assume that for all i E [n], w & R and IE] [[ww 13-11] = 0. Define S. Ei=1 u' and V, Σi [ 1 Then, for any ō e (0,1) and X E [0,1/R], with
probability at least 1- - 8,
S s AV, + In(1/5)/2.
(104)
We now state two helpful results from Mhammedi et al. (2024b) without a proof.
Lemma 1.3. Let B > O and n E N be given. abstract set. Further, let Q {gg X' x A + [0, BJ} be finite function class and (w² a² e²),..., . (x=", a², be sequence of ii.dd random variables in X x Ax R. Then, for any 8e (0, 1), with probability at least 1- - 6, we have
)
} 1991 2B2 1og(2)21/6) s Illl s 2| + 2B2 1og(2101/6),
Vg Q
2
(105)
where [1g1? = Eien E[o( a aa)² 8 "0 and ||al Σ. ?
Lemma 1.4 (Generic regression guarantee). Let B> O, n E N, and f. X' A + [0, be given. Further, let F S {ff X x A + BJ} be finite function class and (a a' e ),..., (x a" E²)) be a sequence i.i.d. random variables in X A x R. Suppose that
f. FF;
x' = fx a') + +'' for all ie [n]:
b' "!....b" E R (not necessarily i.i.d.);
e' [[-BB B), for all i E [n]: and
E[e' x² a. aa]==0) =0.
Then, for , Targminnes jet Ens (J(x,, a') z and any 5 E (0, 1), with probability at least -
-8/2.
|f f. 8B2 log(2 + {b))
(106)
i=1
where
a²) -
Proof. Fix (0,1) and let T.n(S) = ( aa) 2))2, for I E F, and note that since
f E argmin I (f), we have
0 02 L.. - =I.) -f) 1a
(107)
where V denotes directional derivative. Rearranging, we get that
Ilf f. ll < -f- 1l f.
f.(='..(.._)) -= -.) f. - -1
Σ (e' + +b)(f(a' 1
Σ b' (
(108)
1
3 e - E
(1(('' ( at))²
2 i=1
= Σ g (f(m", a²) - f. - (( +
1
1f f- 11.
(109)
2
a1
=1
Thus, rearranging, we get
1f- $8 Σ e (f(x) - ( -1 f. +8 (b
(110)
1=1
47

---

We now bound the first term on the right-hand side of (TO).. For this, we apply Lemma 1.2 with
w² E¹ (f(*", (a) - (a', a²)), , R = B², X 1/(88²), and 8' Ø, and use
1. the union bound over f F; and
2. the facts that E[[e x', a'l 0,
to get that with probability at least - 5/2.
[1ff-fll,, 1 1 f-ll. + B² (og(
Σ E (('=",a)--f a'))
(111)
4
Combining this with TTOp, we get that with probability at least 1 882.
If f.1. 8B3 log(2 + + (b))
(112)
[-1
This completes the proof.
L
L. Online Learning
The following is the standard guarantee of exponential weights (e.g. Lemma F.4 of Sherman et al. (202b)).
Lemma 1,5 (Exponential Weights), Given a sequence of loss functions {T')T= over a decision set TT, (p' IT is a distribution sequence with p a (II), Vt [T] such that
I E
(T) exp -n
p is a uniform distribution over [I]] and nig (T) 2 for all LE [7] and v e II. Then
E(''.p' p) [ log((II)
1 Σ (T)
max
(II
"
1= xelll
1.3 Reinforcement Learning The following is standard simulation lemma which is first proposed by Abbeel and Ng 2005).
(Pa) h and Lemma 166 (Simulation Lemma). For two finite-horizon MDPs M A, (
M = A,,A, e, (Pr) with horizon H and [[[] $ 1. Let the corresponding value function be Vi (I; E) and Vg (ar; E) step h. E (H). For any policy π X A(A), we have
H (T s H
Σ
E
on. [| 2-1,,,0 22 a) PA 2.
x
The following is the standard performance difference lemma which is first proposed by Kakade and Langford (2002).
Lemma (Performance Difference Lemma). For a finite-horizon MDPs M (X, [P starting Ii, and two policies π, n X A(A), have
V (x1:8) - Vi" (x1;
Σ
Exndy Σ (T/((a/)) (alx)) Q (x, a;
1=1 Laed
48

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can found.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes].
Justification: The main claims made in the abstract and introductio accurately reflect the paper's contributions and scope. The claims are validated by detailed proofs.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should elearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes].
Justification:
The paper discuss the limitations of the work in the discussion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
49

---

The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes].
Justification:
The paper provides detailed assumptions and proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA].
Justification: This is theoretical paper.
Guidelines:
50

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https http://bbllccguuddee//eeeeeeeeee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
51

---

The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA].
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA].
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of emrrrs is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables plots. The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
52

---

Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [NA].
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of individual experimental runs as well as estimate the total compute.
The paper should disclose whether the research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https http::///eurrtiiie http:///wrrippsccccuuelteeee/ee/ httppp/ccceeetiiiiiiiiiee.......
Answer: [Yes].
Justification: The research conducted in the paper conforms, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
This is theoretical work. There is societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
53

---

The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification:
The paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA].
Justification:
This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URI
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwpppawppttaeeeeee twwoee. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
54

---

13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA].
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/cooeemmodel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA].
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According the NeurlPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA].
Justification:
This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
55

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
56


Reviews:
[{"review_id": "hKEUHeu3mb", "reviewer": "Reviewer_XUkU", "summary": "The paper explores regret minimization in low-rank MDPs with adversarial bandit loss and unknown transitions. This means that the transition can be expressed as $P(x' \\mid x,a ) = \\phi^\\star (x,a)^T\\mu^\\star(x')$ for some unknown  $\\phi^\\star$ and $\\mu^\\star$ and the loss is also linear in $\\phi^\\star$. They consider three distinct settings:\n\n1.  **Model-based setting**: Here, the authors assume access to function classes containing $\\mu^\\star$ and $\\phi^\\star$. They use some reward-free algorithm to obtain $\\mu$ and $\\phi$ that approximates the dynamics well, and then run EXP2-style algorithm on some $\\epsilon$-cover of the class of linear policies. This algorithm is computationally inefficient and achieves $T^{2/3}$ regret,  with some logarithmic dependencies on the size of the function classes.\n    \n2. **Model-free setting**: In this setting, they don't assume access to a class that contains $\\mu^\\star$. Once again, the algorithm begins with some of-the-shelf exploration phase that aim to find a policy cover. That is, a (small) set of policies that guarantees some sense of minimal reachability to all reachable states. Next, they run an FTRL-style algorithm in each state with log-barrier regularization on blocks of certain size. Within each block, the algorithm plays the policy derived from the FTRL, mixed with a uniform policy from the policy cover. The policy cover's exploration guarantee allows for good least-squares estimation of the Q-function for the policy employed in that block, subsequently used in the FTRL. This achieves $T^{5/6}$ regret against oblivious adversary.\n    \n3.  **Model-free setting with Adaptive adversary**: Here, the adversary adjusts their strategy based on the learner's actions, and there is additional assumption that the the loss features are known (and the dynamics feature map is still unknown). The algorithm is similar to the algorithm in 2. but adds some representation learning algorithm on top of the reward-free algorithm which suggested to be beneficial against adaptive adversary. The regret bound obtained in this setting is also of order of $T^{5/6}$.", "questions": "Could you please clarify how (41) is obtained from Lemma G.5? (41) bounds the average distance, while, to my understanding, G.5 bounds the distance on the data. It feels like some argument on the generalization gap is missing.\n- Is there a specific reason to use log-barrier and not negative entropy regularization in algorithm 2?", "limitations": "As far as I'm concerned, the authors address most of their limitations.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "-   Low-rank MDPs and representation learning are important areas of study in reinforcement learning, particularly due to the relevance of representation learning to deep RL. The paper advances research in this regime by extending previous results from full-information settings to bandit feedback.\n    \n- The paper introduces three algorithms, each tailored to a distinct setting. These algorithms manage to achieve similar regret guarantees to previous works that dealt with the full-information case (although the settings are not directly comparable). Additionally, the authors provide a compelling justification for why they cannot handle arbitrary (non-linear) loss as in the full-information case by presenting a lower bound that scales with the number of states.", "weaknesses": "-   The approach taken in Algorithm 1 is somewhat generic, employing an off-the-shelf reward-free exploration phase followed by an inefficient EXP2 algorithm. Most of the complexity introduced by the unknown feature maps is largely addressed by leveraging existing reward-free algorithms, possibly underplaying the novelty or the specific challenges directly tackled by the new algorithm itself.\n    \n-   Section 5 lacks detailed explanations. The section does not adequately clarify what specifically becomes more challenging in the adaptive adversary setting, nor does it thoroughly explain how the spanner policies effectively address these challenges. The description merely states that these policies are necessary *\"because the estimation of the Q-functions becomes much more challenging with an adaptive adversary\"*. This lack of detail leaves the reader without a clear understanding of the problem mechanics or the solution’s efficacy in this context.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper and for your valuable feedback. Your questions about the use of the log-barrier and the difficulty of dealing with an adaptive adversary are explained in **Q2** and **Q3** of the global response. We answer your other questions below.\n\n\n**Q1**: *In Algorithm 1, most of the complexity introduced by the unknown feature maps is largely addressed by leveraging existing reward-free algorithms, possibly underplaying the novelty or the specific challenges directly tackled by the new algorithm itself.*\n\n**A**: The main novelty of Algorithm 1 lies in the design of the loss estimators; in a low-rank MDP where the feature map is unknown, standard loss estimators used for linear MDPs fail. The challenge here is that the loss estimators have to be carefully designed to account for any errors in the learned representation from Phase 1. This is a non-trivial challenge that existing methods before our paper do not address.   \n\n\n**Q2**: *Could you please clarify how (41) is obtained from Lemma G.5? It feels like some argument on the generalization gap is missing.*\n\n**A**: You are right. Equation (41) follows from Lemma G.4 and Lemma G.5. We will add the reference to Lemma G.4.", "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": "j84N2WH7EU", "reviewer": "Reviewer_GQHM", "summary": "This work initiates the study on learning adversarial low-rank MDPs with bandit feedback. The authors propose an inefficient algorithm with $T^{2/3}$ expected regret, and an oracle-efficient algorithm with $T^{5/6}$ expected regret. Further, the authors also show an oracle-efficient algorithm with $T^{5/6}$ high probability regret.", "questions": "1.\tIn Eq. (12), log-barrier instead of the common Shannon entropy regularizer is used in FTRL. Is this due to that it is not feasible to bound the stability term in the analysis of FTRL when using Shannon entropy caused by the possibly very large magnitude of the constructed $Q$-function estimates?\n2.\tIntuitively, what is the reason that Algorithm 2 still needs to operate in epochs after the phase of reward-free exploration?", "limitations": "Not applicable.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThis work further advances the understanding of learning adversarial MDPs with general function approximation and the algorithmic designs are of interest.", "weaknesses": "1.\tThe first algorithm is generally hard to be implemented due to its computational intractability and thus might be less appealing to practitioners in the area. Besides, the algorithmic design of the first algorithm is similar to those of [1,2] in the sense that learning adversarial MDPs is somewhat reduced to learning adversarial bandits by running exponential weights over the policy set of the corresponding MDP. I would suggest the authors give more comparisons and discussions between the design of the first algorithm and the algorithms in [1,2].\n\n[1] Kong et al. Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimization. TMLR, 24.\n\n[2] Liu et al. Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback. ICLR, 24.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your support and valuable feedback. Your question about why we use log-barrier is explained in **Q2** of the global response. We answer your other questions below.\n\n\n**Q1**: *The first algorithm is similar to learning adversarial MDPs by reducing to learning adversarial bandits.  I would suggest the authors give more comparisons and discussions between the design of the first algorithm and the algorithms in linear MDPs [1,2].*\n\n**A**: Our Algorithm 1 takes a different approach from reducing learning MDPs to linear bandits.  \n\nIn a linear MDP with a known feature map $\\phi$ and a linear loss $\\ell_h(x,a) = \\phi(x,a)^\\top g_h$, we have: \n$$V_1^\\pi(x_1, \\ell) = \\mathbb{E}^\\pi\\left[\\sum_{h=1}^H \\ell_h(x_h, a_h)\\right] = \\mathbb{E}^\\pi\\left[\\phi(x_h, a_h)\\right]\\sum_{h=1}^H g_h.$$\n\nThis means that the linear MDP problem can be reduced to a linear bandit instance where the action set is $\\\\{\\mathbb{E}^\\pi\\left[\\phi(x_h, a_h)\\right]: \\forall \\pi \\\\}$ and $\\sum_{h=1}^H g_h$ is the hidden loss vector. This action set can be estimated by estimating occupancy measures; is the approach taken by [1,2]. With this, [1,2] use the standard linear bandit loss estimator with estimated actions.\n\nThe reduction to linear bandits in [1,2] relies crucially on the linearity of the loss functions. In contrast, our Algorithm 1 does not require linear losses. Instead, it only relies on the linear structure of the transitions (i.e. the low-rank structure). \nMoreover, since the feature maps are unknown in our setting, we cannot use the standard linear bandit loss estimator as in [1,2]. To address this, Algorithm 1 learns a representation in an initial phase, which is then used to compute a new loss estimator carefully designed for low-rank MDPs.\n\n**Q2**: *Why Algorithm 2 still need to operate in epochs after the phase of reward-free exploration?*\n\n**A**: The role of the reward-free phase is to learn a policy cover; a set of policies with good coverage over the state space. In the non-adversarial setting, once such a policy set is computed, finding a near-optimal policy is relatively easy. However, in the adversarial setting, the losses change across rounds and the algorithm needs to constantly estimate the $Q$-functions to play good actions. The algorithm uses epoch for this estimation task, where the larger the epoch (the more episodes in an epoch) the more accurate are the estimated $Q$-functions.", "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": "f7wBrHhwWb", "reviewer": "Reviewer_rtoB", "summary": "This paper studies adversarial Low-Rank MDPs with unknown transition and bandit feedback. The authors give three main results, targeting either tighter regret or computational efficiency. The authors show that the linear structure of the reward function is necessary for the case of bandit feedback to achieve regret without dependence on the number of states.", "questions": "1. Is polynomial dependence on the number of actions necessary? Can the authors provide some intuition about the reason or discuss the possibility of improving the dependence on the number of actions?", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper addresses a novel and challenging problem of adversarial Low-Rank MDPs with unknown transition and bandit feedback. The problem is well-motivated and has practical implications in real-world applications.\n2. The theoretical results are strong and the analyses are sound. The authors provide a comprehensive analysis of the proposed algorithms and prove the theoretical guarantees. The authors combine several techniques to handle the unknown transition and bandit feedback, which is non-trivial.\n3. The paper provides a lower bound to show we could not gain too much from a low-rank transition structure compared with tabular MDPs. This lower bound is insightful and provides a clear motivation for the linear reward structure in the bandit feedback setting.", "weaknesses": "1. The computational cost of the proposed algorithms is huge, even for the oracle efficient algorithms. The authors should provide more discussions on the computational complexity of the proposed algorithms.\n2. Though this paper is the first work to study adversarial Low-Rank MDPs with unknown transition and bandit feedback, the $O(T^{5/6})$ regret bound is not very satisfying. Moreover, the results have a linear dependence on the number of actions, which is not ideal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your support and valuable feedback. Your question about $poly(A)$ dependence in regrets is explained in **Q1** of the global response. We answer your other questions below.\n\n\n\n**Q1**: *The authors should provide more discussions on the computational complexity of the proposed algorithms.*\n\n**A**: The main result in [Mhammedi et al., 2023] guarantees that the number of calls to the optimization Oracle within VoX is polynomial in $d$, $A$, $\\log |\\Phi|$, and $1/\\epsilon$. Due to this, VoX is an Oracle-efficient algorithm. Since our algorithm (Algorithm 2 in this context) makes a single call to VoX, it automatically inherits its Oracle efficiency. All the other steps in Algorithm 2 can be performed computationally efficiently; in fact, the most computationally expensive step is the call to VoX.\n\nOur Algorithm 1 is generally computationally inefficient. The computational complexity scales with $|\\Pi|$ because we need to maintain exponential weights over policy class $\\Pi$. For the linear policy class defined in Line 235, the computational complexity of Algorithm 1 has order $|\\Phi| T^d$.\n\n[Mhammedi et al., 2023]  Mhammedi, Z., Block, A., Foster, D. J., and Rakhlin, A. (2023). Efficient model-free exploration in low-rank mdps. arXiv preprint arXiv:2307.03997", "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": "mHtRZLkdPX", "reviewer": "Reviewer_3DuN", "summary": "This paper studies online learning in low-rank MDPs with adversarial losses (having linear structure), and derives a set of regret guarantees:\n\n1. A model-based and inefficient algorithm ensures $T^{2/3}$ regret, assuming the loss feature vector is unknown. The algorithm has a two-stage design: the first stage is an initial reward-free exploration stage from [1] to ensure low estimation error for the second (exploitation) stage.\n\n2. A model-free and oracle-efficient algorithm ensures $T^{5/6}$ regret, assuming the loss feature vector is unknown. This is thanks to recent advances in exploration for low-rank MDP by [2].\n\n3. A model-free and oracle-efficient algorithm ensures $T^{5/6}$ regret against adaptive adversaries, assuming the loss feature vector is known, by leveraging a representation learning algorithm from [2].", "questions": "Questions here are mainly for curiosity and will not affect my recommendation/rating much.\n\n1. Typically, such two-stage design (initial exploration for warm-up + standard online learning) may not give rate-optimal guarantee. In adversarial linear MDPs, [3] performs estimation on-the-fly to get the first rate-optimal regret. I was wondering what would be the difficulty of doing similar things here (and enjoying better regrets). Could the authors point out some other places where the sub-optimality comes from?\n\n2. In Thm. 4.1, the regret scales with the size of the function class. I think it makes some sense but any similar results in the literature?\n\nReferences\n\n[1] Cheng, Yuan, Ruiquan Huang, Yingbin Liang, and Jing Yang. \"Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPs.\" In The Eleventh International Conference on Learning Representations. 2022.\n\n[2] Mhammedi, Zakaria, Adam Block, Dylan J. Foster, and Alexander Rakhlin. \"Efficient Model-Free Exploration in Low-Rank MDPs.\" arXiv preprint arXiv:2307.03997 (2023).\n\n[3] Liu, Haolin, Chen-Yu Wei, and Julian Zimmert. \"Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback.\" In The Twelfth International Conference on Learning Representations. 2023.", "limitations": "In the checklist, it says \"The paper discuss the limitations of the work in the discussion section\", but I didn't find a section named \"discussion\".\n\n====== update after author-reviewer discussion ======\n\nDuring the initial rebuttal and the discussion phase, the authors addressed my clarification question, so as of now I increase my score from 5 to 6", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "By adopting recent progress in representation learning and low-rank MDP from the literature, the paper provides a set of results for low-rank MDPs with adversarial (linear) losses under bandit feedback. This is the first set of results for the more challenging bandit feedback.", "weaknesses": "I overall appreciate the contributions from this work, in which the authors take advantage of SOTA techniques in the literature, but also with some original adaptations, to give a complete picture on regret bounds in a new setup. However, I think the author could do a better job in presentation and delivering insights, which may make readers benefit more from reading this paper. Below are some questions that I think should be made clear(er) in the paper (and I don’t get an answer after reading the paper):\n\n1. Maybe I missed it somewhere, but what is exactly the “oracle” that is referred to throughout this paper? Is it hidden in the VoX algorithm?\n\n2. Even with linear loss struction, the regret still has to be $\\Omega(\\sqrt{A})$, is this a common result in the low-rank MDP literature, or unique due to the adversarial losses (and bandit feedback)?\n\n3. In Thm. 4.1, is $\\delta$ the failure probability for the regret guarantee? In other words, is Thm. 4.1 stating a high-probability regret bound? If so, why is the way of stating a high-prob. bound in Thm. 4.1 different from that in Thm. 5.1? If not, then the use of notation $\\delta$ is not consistent in the paper.\n\n4. What’s the difficulty of obtaining regret bounds against adaptive adversaries, without knowing the loss feature map? In section 5, the sentence “Given the difficulty of this setting, we make the additional assumption” fails to yield a smooth transition, as I don’t get the connection between the difficulty (it’s not even clear what it is) and the need for the assumption.\n\n5. Does the difficulty lie in obtaining high-prob regrets against oblivious adversaries? Is it true that with the help of the known loss feature, one can establish high-prob. regret bound, which easily implies regret bounds against adaptive adversaries?\n\n6. If algorithm 4 is mostly from other papers and there’s no novel modification, the authors may consider moving it to appendix to save some space in the main body for more informative messages.\n\n7. In line 10 of algorithm 1, “Define $\\sum_h^t = \\sum$”, anything missing before the $=$?\n\n8. Sketched proofs in the main body for deriving regret bounds would be very helpful, but I fully understand it due to the page limit.\n\n9. If a reference has been accepted to a conference, the authors may want to cite the conference version rather than arXiv, unless there's a significant update.\n\nI will consider increasing my rating to 6 and supporting acceptance if the authors can address these questions so that I can have a clearer understanding of the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your support and valuable feedback. We will adopt your writing suggestions in our future version.\n\nYour questions about $poly(A)$ dependence in regrets and the difficulty of adaptive adversaries are explained in **Q1** and **Q3** of the global response. We answer your other questions below. \n\n**Q1**: *What is exactly the “oracle” that is referred to throughout this paper? Is it hidden in the VoX algorithm?*\n\n\n**A**: Yes, the oracle is hidden in VoX. A call to VoX requires a polynomial number of calls to a min-max optimization Oracle over a class of value functions to learn a good representation; the Oracle is required by the RepLearn subroutine within VoX. We note that this Oracle is by now standard and has been used in many other works such as  [Mhammedi et al., 2023;  Zhang et al.,2022b].\n\n**Q2**: *In Thm. 4.1, is $\\delta$ the failure probability for the regret guarantee? In other words, is Thm. 4.1 stating a high-probability regret bound?* \n\n**A**: Thank you for pointing it out. This is just a typo in the statement of the theorem. The result in Theorem 4.1 is in expectation and $\\delta$ should be replaced by $poly(1/T)$.\n\n**Q3**: *Does the difficulty of adaptive adversaries lie in obtaining high-prob regrets against oblivious adversaries? Is it true that with the help of the known loss feature, one can establish high-prob. regret bound, which easily implies regret bounds against adaptive adversaries?*\n\n**A**:   The situation is a little more subtle than this. Even with a known feature loss, Algorithm 2 would still fail against an adaptive adversary because the estimation of the average $Q$-functions within an epoch can no longer be reduced to a standard least-squares regression problem with i.i.d.~data; see the answer to **Q3** in the general response. Instead, the algorithm in Section 5 aims at estimating the average $Q$-functions, not in a least-squares sense, but in expectation over roll-ins using policies in $\\Psi_{\\texttt{span}}$; the ``in-expectation'' estimation task is in a sense easier. Here, $\\Psi_{\\texttt{span}}$ is a set of policies with good coverage over state-action pairs. More specifically, $\\Psi_{\\texttt{span}}$ is required to be such that $\\\\{ \\mathbb{E}^{\\pi}[\\phi^{\\texttt{loss}}(x_h, a_h)]   |  \\pi \\in \\Psi_{\\texttt{span}} \\\\}$ essentially covers all directions in $\\mathbb{R}^d$. For this reason, we need $\\phi_{\\texttt{loss}}$ to compute $\\Psi_\\texttt{span}$.\n\n\n**Q4**: *In line 10 of algorithm 1, Define $\\Sigma_h^t = \\sum$, anything missing before the $=$ ?*\n\n**A**: $\\Sigma_h^t$ is the covariance matrix of time $t$ and step $h$ whose definition is on the right-hand side of ``$=$''. The $\\sum$ on the right-hand side is the summation notation.\n\n**Q5**: *In adversarial linear MDPs, [3] performs estimation on-the-fly to get the first rate-optimal regret. I was wondering what would be the difficulty of doing similar things here (and enjoying better regrets). Could the authors point out some other places where the sub-optimality comes from?*\n\n**A**: Indeed, the suboptimal regret of Algorithm 1 is due to the two-stage design. The online occupancy estimation technique in [3] relies crucially on the transition feature being known. It is unclear how to extend this to the low-rank setting with unknown features. Getting the optimal regret is still a challenging open problem.\n\n**Q6**: *If a reference has been accepted to a conference, the authors may want to cite the conference version rather than arXiv, unless there's a significant update.*\n\n**A**:  Thank you for the suggestion. For the case of [Mhammedi et al., 2023] in particular, the paper has significant updates on arXiv compared to their camera-ready NeurIPS version (removes the reachability assumption with different analysis). Thus, we cite both versions in our paper. We will change other references to the conference version.\n\n**Q7**:  *In Thm. 4.1, the regret scales with the size of the function class. I think it makes some sense but any similar results in the literature?*\n\n**A**:  For low-rank MDP, the $\\log(|\\Phi|)$ in Theorem 4.1 matches the best-known result in the stochastic setting [Mhammedi et al., 2023; Zhang et al., 2022b]. Most papers on low-rank MDP have worse dependence $\\log(|\\Phi||\\Upsilon|)$ under the model-based assumption (e.g. [Agarwal et al., 2020; Uehara et al., 2022]). \n\n\nMoreover, the logarithmic dependence on the size of the function class is very common in RL with general function approximation. For example, in the general decision estimation coefficient (DEC) framework, such dependence appears in both model-based (Theorem 3.3 in [Foster et al., 2021]) and model-free (Theorem 2.1/Corollary 2.1 in [Foster et al., 2023]) algorithms.\n\n**References**:\n\n[Mhammedi et al., 2023]  Mhammedi, Z., Block, A., Foster, D. J., and Rakhlin, A. (2023). Efficient model-free exploration in low-rank mdps. arXiv preprint arXiv:2307.03997\n\n[Zhang et al., 2022b] Zhang, X., Song, Y., Uehara, M., Wang, M., Agarwal, A., and Sun, W. (2022b). Efficient reinforcement learning in block mdps: A model-free representation learning approach. ICML.\n\n\n[Agarwal et al., 2020] Agarwal, A., Kakade, S., Krishnamurthy, A., and Sun, W. (2020). Flambe: Structural complexity and representation learning of low rank mdps. NeurIPS.\n\n\n[Uehara et al., 2022] Uehara, M., Zhang, X., and Sun, W. (2022). Representation learning for online and offline rl in low-rank mdps. ICLR.\n\n[Foster et al., 2021] Foster, D. J., Kakade, S. M., Qian, J.,  Rakhlin, A. (2021). The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487.\n\n[Foster et al., 2023]  Foster, D. J., Golowich, N., Qian, J., Rakhlin, A., Sekhari, A. (2023). Model-free reinforcement learning with the decision-estimation coefficient. NIPS.", "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:
## **Global Response**

We thank all the reviewers for their valuable feedback. We would like to clarify several common concerns here.

**Q1** : *The $poly(A)$ dependence in the regret bound looks not ideal. Is it common in low-rank MDP literature?*

**A**: We would like to point out that poly-dependence of action set size $A$ is unavoidable anyway even in non-adversarial low-rank MDPs with linear loss; this follows the lower bound from Theorem 4.2 and Appendix B of [Zhao et al. 2024]. 


[Zhao et al. 2024]  Zhao, C., Yang, R., Wang, B., Zhang, X., and Li, S. (2024). Learning adversarial low-rank markov decision processes with unknown transition and full-information feedback. NeurIPS.


**Q2**: *Why we use log-barrier?*

**A**: For the $Q$-function estimator $\widehat{Q}$ with learning rate $\eta$, negative entropy regularization requires $\eta \widehat{Q} \ge -1$ to ensure the stability term in the regret is small. Using the log barrier, we can get rid of this constraint, leading to more flexibility in the choice of $\eta$ and ultimately a better regret bound (compared to the negative entropy) after tuning $\eta$.

The price of using the log-barrier is a poly-dependence in the number of actions $A$. However, as discussed in **Q1**, such dependence is unavoidable for low-rank MDPs.



**Q3**:  *Section 5 lacks detailed explanations. Why does the estimation of the Q-functions become much more challenging against an adaptive adversary without knowing the loss feature map?*


**A**:  Our algorithm for oblivious adversaries works in epochs, where at each epoch $k$ the algorithm commits to a policy $\widehat{\pi}^{(k)}$ for $N_{reg}$ episodes. The algorithm then uses these trajectories to compute an estimate $\widehat{Q}^{(k)}$ of the average $Q$-function $\frac{1}{N_{reg}} \sum_{t \text{ in epoch } k}Q^{\widehat{\pi}^{(k)}}_h(\cdot,\cdot ;\ell^t)$. In the case of an oblivious adversary, this estimation problem can be reduced to a standard regression problem with i.i.d. data. This is possible because the regression target is an average of $Q$-functions over $t$ episodes in epoch $k$, and this target is invariant to any permutation of the episodes $t$ thanks to the fact that losses are oblivious. And so, by randomly shuffling the episodes in epoch $k$, one can reduce the regression problem to an i.i.d. one. When dealing with an adaptive adversary, the order of the episodes within an epoch matters and the average $Q$-function targets are no longer invariant to permutations of the episodes. For this reason, we cannot rely on standard regression guarantees with i.i.d. data.

Meta-review: The paper explores regret minimization in low-rank MDPs with adversarial bandit loss and unknown transitions. Several regret bounds are obtained under different settings. It is the first attempt to low-rank MDPs in the adversarial environment, and involves a nontrivial reduction to linear bandit (where the reduction differs from previous works). All reviews are positive, and during the discussion period all reviewers and I have reached a consensus that the manuscript has significant contributions. Concerns on Theorem 4.1 and on different regularizers have been adequately addressed during the rebuttal. I therefore recommend acceptance.
Decision: Accept (poster)