Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedback

Authors: haolin  liu
zakaria  mhammedi
chen-yu  wei
julian  zimmert
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 18:21:57

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.

Main paper: 
 introduction: 
 We study online reinforcement learning (RL) in low-rank Markov Decision Processes (MDPs). Lowrank MDPs is a class of MDPs where the transition probability can be decomposed as an inner product between two low-dimensional features, i.e., P (x ′ | x, a) = ϕ ⋆ (x, a) ⊺ µ ⋆ (x ′ ), where P (x ′ | x, a) is the probability of transitioning to state x ′ when the learner takes action a on state x, and ϕ ⋆ , µ ⋆ are two feature mappings. The ground truth features ϕ ⋆ and µ ⋆ are unknown to the learner. This setting has recently caught theoretical attention due to its simplicity and expressiveness (Agarwal et al., 2020; Uehara et al., 2021; 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 are given, such as in linear MDPs (Jin et al., 2020b) and in linear mixture MDPs (Ayoub et al., 2020) . Since feature learning is an indispensable part of modern deep RL pipelines, low-rank MDP is a model that is closer to practice than traditional linear function approximation.Table 1 : Comparison of adversarial low-rank MDP algorithms. O here hides factors of order poly(d, |A|, log T, log |Φ||Υ|). † Algorithm 5 assumes access to ϕ(x, a) for any (ϕ, x, a) ∈ Φ × X × A, while other algorithms only require access to ϕ(x, a) for any (ϕ, a) ∈ Φ × A on visited x. different exploration phase, where it calls VoX (Mhammedi et al., 2023) to learn a policy cover; VoX is a 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 4 /5 -regret model-free oracle-efficient algorithm under bandit feedback (Algorithm 3, Algorithm 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 a 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 deals 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 Algorithm 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 = (X , A, P ⋆ 1∶H ), where X represents a countable (possibly infinite) state space2 , A is a finite action space, and P ⋆ h ∶ X × A → ∆(X ) denotes the transition kernel from layer h to h + 1. We assume that the initial state x 1 ∈ X is fixed for simplicity without loss of generality. For any policy π ∶ X ↦ ∆(A) and arbitrary set of transition kernels {P h } h∈[H] , we let P P,π denote the law over (x 1 , a 1 , . . . , x H , a H ) induced by the process of setting x 1 = x 1 , sampling a 1 ∼ π 1 (⋅ | x 1 ), then for h = 2, . . . , H, x h ∼ P h-1 (⋅ | x h-1 , a h-1 ) and a h ∼ π h (⋅ | x h ). We let E P,π denote the corresponding expectations. Further, we let d P,π h (x) ∶= P P,π [x h = x] denote the occupancy of x ∈ X . We also let d P,π h (x, a) ∶= P P,π [x h = x, a h = a]. Further, we let E π = E P ⋆ ,π , P π = P P ⋆ ,π , and d π h = d P ⋆ ,π h . We use π ○ h π ′ to denote a policy that follows π k (⋅ | ⋅) for k < h and π ′ k (⋅ | ⋅) for k ≥ h. Similarly, π ○ h π ′ ○ h ′ π ′′ denotes a policy that follows π k for k < h, π ′ k for h ≤ k < h ′ and π ′′ k for k > h ′ . 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 (ℓ t 1∶H ∶ X × A → [0, 1]) T t=1 . For each episode t ∈ [T ], the learner starts at state x t 1 = x 1 , then for each step h ∈ [H] within episode t, the learner observes state x t h ∈ X h , chooses an action a t h ∈ A, then suffers loss ℓ t h (x t h , a t h ). The state x t h+1 at the next step is drawn from transition P ⋆ h (⋅ | x t h , a t h ). We consider bandit feedback setting where the learner could only observe the losses ℓ t 1 (x t 1 , a t 1 ), . . . , ℓ t H (x t H , a t H ) at the visited state-action pairs. We let Π ∶= {π ∶ X → ∆(A)} denote the set of Markovian policies. For policy π ∈ Π, loss ℓ and transition kernels P 1∶H , we denote by Q P,π h (⋅, ⋅; ℓ) the state-action value function (a.k.a. Q-function) at step h ∈ [H] with respect to the transitions P 1∶H and loss ℓ; that isEQUATIONfor all (x, a) ∈ X × A. We let V P,π h (x; ℓ) ∶= max a∈A Q P,π h (x, a; ℓ) be the corresponding state value function at layer h. Further, we write Q π h (⋅, ⋅; ℓ) ∶= Q P ⋆ ,π h (⋅, ⋅; ℓ) and V π h (⋅; ℓ) ∶= V P ⋆ ,π (⋅; ℓ). For all of our algorithms except for Algorithm 4, we aim to construct (possibly randomized) policies {π t } t∈[T ] that ensure a sublinear pseudo-regret with respect to the best-fixed policy; that is,EQUATIONForAlgorithm 4, we bound the standard regretEQUATIONwith high probability. This allows it to handle adaptive adversary.Throughout, we will assume that the MDP M is low-rank with unknown feature maps ϕ ⋆ h and µ ⋆ h . Assumption 2.1 (Low-Rank MDP). There exist (unknown) features maps ϕ ⋆ 1∶H ∶ X × A → R d and µ ⋆ 1∶H ∶ X → R d , such that for all h ∈ [H -1] and (x, a, x ′ ) ∈ X × A × X :EQUATIONFurthermore, for all h ∈ [H], the feature maps µ ⋆ h and ϕ ⋆ h are such that sup (x,a)∈X ×A ∥ϕ ⋆ h (x, a)∥ ≤ 1 and ∥ ∑ x∈X g(x) ⋅ µ ⋆ h (x)∥ ≤ √ d, 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 to avoid a sample complexity scaling with the number of states. This linear loss assumption also appears in Ren et 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 ∈ [T ] and layer h, there is a vector g t h ∈ B d (1) such that the loss ℓ t h (x, a) at round t satisfies: ∀(x, a) ∈ X × A, ℓ t h (x, a) = ϕ ⋆ h (x, a) ⊺ g t h .(5)We note that there is no loss of generality in assuming that the losses are expressed using the same features ϕ ⋆ 1∶H as the low-rank structure in (4). This is because if the losses have different features, we can simply combine these features with the low-rank features, and redefine ϕ ⋆ accordingly. For the bulk of our results (and as stated in the prequel), we will assume that the losses {ℓ t h (⋅, ⋅)} h∈ [H] ,t∈[T ] (or equivalently {g t h } h∈[H],t∈[T ] under Assumption 2.2) are chosen by an aversary before the start of the game (i.e. oblvious adversary). In Section 4.3, we will present a 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 ϕ ⋆ 1∶H 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 Υ that contains the feature maps µ ⋆ 1∶H3 . We will formalize these assumptions in their corresponding sections in the sequel.Other notation. For ψ ∶ Π → R d , we define John(ψ, Π) as a distribution µ ∈ ∆(Π) such that ∥ψ(π)∥ 2 G -1 ≤ d for all π ∈ Π, where G = ∑ π∈Π µ(π) ⋅ ψ(π)ψ(π) ⊺ . This is the standard John's exploration or G-optimal design, which always exists. 
model-based algorithms for adversarial low-rank mdps: 
 In this section, we discuss adversarial low-rank MDPs under model-based assumption. The modelbased assumption is formalized in the Assumption 3.1 below. This assumption is standard which also appears in prior works on model-based learning in low-rank MDPs (Agarwal et al., 2020; Uehara 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 to two model spaces Φ and Υ such that ϕ ⋆ ∈ Φ and µ ⋆ ∈ Υ. Moreover, for any ϕ ∈ Φ, µ ∈ Υ, and h ∈ [2 .. H], we have sup (x,a)∈X ×A ∥ϕ h-1 (x, a)∥ ≤ 1, ∑ x ′ ∈X ϕ h-1 (x, a) ⊺ µ h (x ′ ) = 1 and ∥ ∑ x∈X g(x) ⋅ µ h (x)∥ ≤ √ d, for all g ∶ X → [0, 1].We first discuss learning adversarial low-rank MDPs with full information and model-based assumption. This setting aligns with Zhao et al. (2024) , and our Algorithm 1 successfully improves their regret from T 5 /6 to T 2 /3 .Algorithm 1 Model-Based Algorithm for Full-Information Feedback1: Let η = 1 H √ T , ϵ = (Hd 2 |A|(d 2 + |A|)) 1 3 T -1 3 , and T 0 = Õ(ϵ -2 H 3 d 2 |A|(d 2 + |A|)).Let π 1 be a uniform policy. 2: Run (Cheng et al., 2023 , Algorithm 1) for T 0 episodes and get outputs φ ∈ Φ, μ ∈ Υ. 3: Define transitions P1∶H-1 asPh (x ′ | x, a) = φh (x, a) ⊺ μh+1 (x ′ ), ∀(x, a, x ′ ) ∈ X × A × X . 4: for t = T 0 + 1, T 0 + 2, . . . , T do 5:Execute policy π t and observe trajectory (x 1∶H , a 1∶H ) and full information loss ℓ t .Update policy for all h ∈ [H]:π t+1 h (a | x) ∝ exp (-η t ∑ i=1 Qi h (x, a)) where Qt h (x, a) = Q P ,π t h (x, a; ℓ t ).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 et al. ( 2024) performs simultaneous representation learning and policy optimization. With a closer look at their analysis, we find that there is a 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.e., critic) fed to policy optimization, and worsens the overall regret.To address this issue, we design Algorithm 1 as a simple two-phase algorithm that separates representation learning and policy optimization. In the first phase, following Cheng et al. (2023) , we 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 1 where Õ hides logarithmic factors of d, H, T, |Φ||Υ|.EQUATION3 ).The proof for Theorem 3.1 is given in Appendix B. Zhao et al. (2024) also constructs a lower bound Ω (H √ d|A|T ) for this settings. Thus, the poly(|A|)-dependence is unavoidable.In this section, following Assumption 3.1, we introduce the first (model-based) algorithm (Algorithm 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 to construct a proper loss estimator. 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 Algorithm 2, we first conduct an initial representation learning phase to establish accurate transition estimator P and its corresponding features φ and μ based on reward-free exploration algorithms in Cheng et al. (2023) . Then, in the second phase, we use exponential weights to maintain a distribution over the policy space Π ′ where we mix a uniform policy with Π to enhance exploration. At every round t, a behavior policy π t is chosen from the current policy distribution, and we use the data collected by π t to estimate the value for every π ∈ Π ′ . 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, we haveEQUATIONAlgorithm 2 Model-Based Algorithm for Bandit Feedback Input: A policy class Π. (Cheng et al., 2023 , Algorithm 1) for T 0 episodes and get outputs φ ∈ Φ, μ ∈ Υ. 3: Define transitions P1∶H-1 as a) , where dπ h ∶= d P ,π h . 5: Define the policy space1: Set ϵ = T -1 3 , γ = T -1 3 , β = T -1 3 , η = (4Hd|A|) -1 T -2 3 , and T 0 = Õ(ϵ -2 H 3 d 2 |A|(d 2 + |A|)). 2: RunPh (x ′ | x, a) = φh (x, a) ⊺ μh+1 (x ′ ), ∀(x, a, x ′ ) ∈ X × A × X . 4: For all h ∈ [H -1], define φh (π) = ∑ (x,a)∈X ×A dπ h (x, a) ⋅ φh (x,Π ′ = {π ′ ∶ ∃π ∈ Π, π ′ h (⋅ | x) = (1 -β)π h (⋅ | x) + β/|A|, ∀x, h}. 6: for t = T 0 + 1, T 0 + 2, . . . , T do 7: Define p t (π) ∝ exp (-η ∑ t-1 i=1 ( li (π) -b i (π))) , for all π ∈ Π ′ . 8: Let ρ t (π) = (1 -γ)p t (π) + γ H-1 ∑ H-1 h=1 J h , where J h = John( φh (⋅), Π ′ ). // John as in §2 9:Execute policy π t ∼ ρ t and observe trajectory (x t 1∶H , a t 1∶H ) and losses ℓ t h = ℓ t h (x t h , a t h ).10:Define Σ t h = ∑ π∈Π ′ ρ t (π) ⋅ φh (π) φh (π) ⊺ , b t (π) = √ dHϵ ⋅ ∑ H-1 h=1 ∥ φh (π)∥ (Σ t h ) -1, andlt (π) = π 1 (a t 1 | x t 1 ) π t 1 (a t 1 | x t 1 ) ℓ t 1 + H ∑ h=2 φh-1 (π) ⊺ (Σ t h-1 ) -1 φh-1 (π t ) π h (a t h | x t h ) π t h (a t h | x t h ) ℓ t h .11: end for Thus, using the definition of the V -function from Section 2, we have for any loss function ℓ and π:V π 1 (x 1 ; ℓ) -E[ℓ 1 (x 1 , a 1 )] = H ∑ h=2 ∑ (x,a)∈X ×A ϕ ⋆ h-1 (π) ⊺ µ ⋆ h (x)π h (a | x) ⋅ ℓ h (x, a). (7) Letting Λ t h ∶= (E π t ∼p t [ϕ ⋆ h (π t )ϕ ⋆ h (π t ) ⊺ ]) -1 and ingnoring the loss term E[ℓ 1 (x 1 , a 1 )] from the first step (this term can easily be treated as in a bandit setting with H = 1), we have for all π ∈ Π ′ :V π 1 (x 1 ; ℓ) = E π t ∼p t ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ H ∑ h=2 ∑ (x,a)∈X ×A ϕ ⋆ h-1 (π) ⊺ Λ t h-1 ϕ ⋆ h-1 (π t )ϕ ⋆ h-1 (π t ) ⊺ µ ⋆ h (x)π h (a | x) ⋅ ℓ h (x, a) ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ , = E π t ∼p t ⎡ ⎢ ⎢ ⎢ ⎣ H ∑ h=2 ∑ x,a ϕ ⋆ h-1 (π) ⊺ Λ t h-1 ϕ ⋆ h-1 (π t ) ⋅ d π t h (x)π t h (a | x) π h (a | x) π t h (a | x) ⋅ ℓ h (x, a) ⎤ ⎥ ⎥ ⎥ ⎦ , = E π t ∼p t E π t [ H ∑ h=2 ϕ ⋆ h-1 (π) ⊺ Λ t h-1 ϕ ⋆ h-1 (π t ) ⋅ π h (a h | x h ) π t h (a h | x h ) ⋅ ℓ h (x h , a h )] .Thus, for all ℓ and π, ∑H h=2 ϕ ⋆ h-1 (π) ⊺ Λ t h-1 ϕ ⋆ h-1 (π t ) ⋅ π h (a h | x h )π t h (a h | x h ) -1 ⋅ ℓ h (x h , a h ) for π t ∼ p t and (x h , a h ) ∼ d π t h is an unbiased estimator of V π 1 (x 1 , ℓ). However, ϕ ⋆ h-1 (π)is not accessible because both the true feature ϕ ⋆ and occupancy d π for the true transition are unknown. Thus, our estimator incorporates the learned feature φ and the occupancy of P instead as shown in Line 4 and Line 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 t (π) in exponential weights. To further encourage exploration, we additionally perform John's exploration together with exponential weights when selecting behavior policies. The main guarantee of Algorithm 2 is given in Theorem 3.2.Theorem 3.2. Algorithm 2 achieves Reg T (π) ≤ Õ (d 2 H 3 |A|(d 2 + |A|)T 2 /3 log |Π|) for any π ∈ Π.Note that the guarantee in Theorem 3.2 only holds for policy π ∈ Π. To ensure our regret bound is meaningful, at least a near-optimal policy should be contained in the given policy set Π. In general, the size of such a 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. 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 can even handle linear loss with unknown feature, since our Algorithm 2 never explicitly uses the loss feature. The linear structure is only used to control the size of the candidate policy class in the analysis (i.e., making log |Π| irrelevant to the number of states). Specifically, when both loss and transition are linear, the Q-function is also linear, making it sufficient to consider the following linear policy space: d) following standard arguments (e.g, Exercise 27.6 of Lattimore and Szepesvári (2020) ) and if we feed it into Algorithm 2, our regret could avoid dependece on the size of state space as shown in Corollary 3.1.Π lin = {π ∶ X → A | π h (a | x) = I{a = argmin a∈A ϕ h (x, a) ⊺ θ h }, h ∈ [H], ∥θ h ∥ 2 ≤ √ dHT, ϕ ∈ Φ} . The 1 T -cover of Π lin only have size |Φ| ⋅ T O(Corollary 3.1. If the loss function satisfies Assumption 2.2, applying Algorithm 2 with Π as the1 T -cover of Π lin ensures Reg T ≤ Õ (d 3 H 3 |A|(d 2 + |A|)T 2 /3 ).4 Model-free Algorithms for Adversarial Low-rank MDPsIn this section, we consider the model-free setting, where we only assume access to a feature class Φ that contains the true feature map ϕ ⋆ .Assumption 4.1 (Model-free realizability). The learner has access to a function class Φ such thatEQUATIONThis is a standard assumption in the context of model-free RL (Modi et al., 2024; Zhang et al., 2022b; Mhammedi et al., 2024a) . We note that having access to the function class Φ alone (instead of both Φ and Υ 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 Mhammedi et al. (2023) there were no model-free, oracle-efficient 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 as Algorithm 2 but incorporates a model-free initial exploration phase introduced by Mhammedi 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 1 of Liu et al. (2023) to solve the expected feature φ, which is then used in the loss estimator in Line 10 of Algorithm 2. The algorithm, summarized in Algorithm 5, is inefficient but achieves T 2 /3 regret. More details and proofs can be found in Appendix D. 
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 a reward-free exploratorion phase; Line 2 of Algorithm 3. However, unlike in the previous sections where the role of this exploration phase was to learn a model for the transition probabilities, here the goal is to compute a, so called, policy cover which is a small set of policies that can be used to effectively explore the state space. Definition 4.1 (Approximate policy cover). For α, ε ∈ (0, 1] and h ∈ [H], a subset Ψ ⊆ Π is an (α, ε)-policy cover for layer h ifEQUATION)Algorithm 3 Oracle Efficient Algorithm for Adversarial Low-Rank MDPs (Oblivious Adversary).Input: Number of rounds T , feature class Φ, confidence parameter δ ∈ (0, 1).1: Set ε ← T -1/3 , N reg ← T 2/3 , ν ← N -1/2reg , and T 0 ← ε -2 Ad 13 H 6 log(Φ/δ). 2: Get Ψ cov 1∶H ← VoX(Φ, ε, δ). // Compute policy cover with VoX (Mhammedi et al., 2023) .3: for k = 1, . . . , (T -T 0 )/N reg do 4: Define π(k) h (a | x) ∝ exp (-η ∑ s<k Q(s) h (x, a)) for h ∈ [H].5:for t = T 0 + (k -1) ⋅ N reg + 1, . . . , T 0 + k ⋅ N reg do 6:Sample variables ζ t ∼ Ber(ν), h t ∼ unif([H]), and π t ∼ unif(Ψ cov h t ).7: For h ∈ [H] andSet πt = I{ζ t = 0} ⋅ π(k) + I{ζ t = 1} ⋅ π t ○ h t π unif ○ h t +1 π(kI (k) = {T 0 + (k -1) ⋅ N reg + 1, . . . , T 0 + k ⋅ N reg }, compute ( φ(k) h , θ(k) h ): ( φ(k) h , θ(k) h ) ← argmin (ϕ,θ)∈Φ×B d (H √ d) ∑ t∈I (k) (ϕ h (x t h , a t h ) ⊺ θ - H ∑ s=h ℓ t s ) 2 ⋅ I{ζ t = 0 or h t ≤ h}. (9) 12: Set Q(k) h (x, a) = φ(k) h (x, a) ⊺ θ(k)h , for all (x, a) ∈ X × A. 13: end for In Line 2, Algorithm 3 calls VoX (Mhammedi et al., 2023) , a reward-free and model-free exploration algorithm to compute (1/(8Ad), ε)-policy covers Ψ cov 1 , . . . , Ψ cov H for layers 1, . . . , H, respectively, with |Ψ h | = d for all h ∈ [H]. This call to VoX requires O(1/ε 2 ) episodes; see the guarantee of VoX in Lemma G.1. After this initial phase, the algorithm operates in epochs, each consisting of N reg ∈ N episodes, where in each epoch k ∈ [K], the algorithm commits to executing policies sampled from a fixed policy distribution ρ (k) ∈ ∆(Π) with support on the policy covers Ψ cov 1∶H and a policy π(k) specified by an online learning algorithm. Next, we describe in more detail how ρ (k) is constructed and motivate the elements of its construction starting with the online learning policies {π (k) } k∈ [K] .EQUATIONfrom the previous epoch (we will describe how these estimates are computed in the sequel), Algorithm 3 computes policy π(k) for epoch k according toEQUATIONfor all h ∈ [H]. Given a state x ∈ X , such exponential weight update ensures a sublinear regret with respect to the sequence of loss functions given by {π(⋅ | x) ↦ ∑ h∈[H] Q(k) h (x, π h (⋅ | x))} k∈[K]. Thanks to the performance difference lemma, and as shown in Luo et al. (2021) , a sublinear regret with respect to these "surrogate" loss functions translates into a sublinear regret in the low-rank MDP game we are interested in, granted that { Q(k) 1∶H } k∈[K] are good estimates of the average Q-functions (Luo et al., 2021) . In line with previous analyses, we require the Q-function estimates to ensure that the following bias termEQUATIONis small for all h ∈ [H], k ∈ [K], and π ∈ Π.Q-function estimates. Thanks to the low-rank MDP structure and the linear loss representation assumption (Assumption 2.2), the avegare Q-functions in (11) 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 ∑ H s=h ℓ t s onto (x t h , a t h ) for t in the kth epoch (as in ( 9)). However, naïvely doing this using only trajectories generated by π(k) would only ensure that the bias term in (13) is small for π = π(k) . To ensure that it is small for all possible policies π'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 t in each epoch k ∈ [K], we execute policy πt sampled from ρ (k) , where ρ (k) is the distribution of the random policy:EQUATIONwith ζ t ∼ Ber(ν), h t ∼ unif([H]), and π t ∼ unif(Ψ cov h t ).In words, at the start of each episode of any epoch k, we execute π(k) (see ( 12)) with probability 1ν; and with probability ν, we execute a policy in Ψ cov 1∶H selected uniformly at random. As explained in the previous paragraph, this ensures a small bias for all choices of π in (13) thanks the policy cover property of Ψ cov 1∶H . We now state the guarantee of Algorithm 3.Theorem 4.1. Let δ ∈ (0, 1) be given and suppose Assumption 2.1 and Assumption 2.2 hold. This, for T = poly(A, d, H, log(|Φ|/δ)) sufficiently large, Algorithm 3 guarantees Reg T ≤ poly(A, d, H, log(|Φ|/δ)) ⋅ T 4 /5 regret against an oblivious adversary.The proof is in Appendix E. Note that the T -dependence in this regret even outperforms that of the previous best bound by Zhao et al. (2024) (see Table 1 ). Compared to their algorithm, Algorithm 3 is model-free and only requires bandit feedback. This makes the result in Theorem 4.1 rather surprising.In this section, we present a variant of Algorithm 3 (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 ϕ loss , which may be different than the low-rank MDP feature ϕ ⋆ (unlike in Assumption 2.2).). There is a (known) feature map ϕ loss satisfying sup h∈[H],(x,a)∈X ×A ∥ϕ loss h (x, a)∥ ≤ 1 and such that for any round h ∈ [H], t ∈ [T ], and history H t-1 = (x 1∶t-1 1∶H , a 1∶t-1 1∶H ), the loss function at round t satisfiesEQUATIONfor some g t h ∈ B d (1). Note that Assumption 4.2 asserts that the loss at round t depends only on the history H t-1 and the current state action pair. Before moving forward, we introduce some additional notation we will use throughout this section.Additional notation. For any two feature maps ϕ, ψ ∶ X × A → R d , we denote by [ϕ, ψ] ∶ X × A → R 2d the vertical concatenation of the two feature maps. For any h ∈ [H], t ∈ [T ], policy π ∈ Π, and history H t-1 = (x 1∶t-1 1∶H , a 1∶t-1 1∶H ), we denote by Q π h (⋅, ⋅; H t-1 ) the Q-function at layer h corresponding to rollout policy π; that is,EQUATIONFinally, we let V π h (x; H t-1 ) ∶= max a∈A Q π h (x, a; H t-1 ) 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 a feature map ϕ rep . Then, for every h ∈ [H], the algorithm computes a spanner; a set of policies Ψ span h = {π h,1 , . . . , π h,2d } that act as an approximate spanner for the set{E π [ϕ rep h (x h , a h ), ϕ loss h (x h , a h )] ∶ π ∈ Π} ⊆ R 2d, where we 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 k ∈ [K], we execute policy π (k) sampled from ρ (k) , where ρ (k) is set to be the distribution of the random policy:I{ζ t = 0} ⋅ π(k) + I{ζ t = 1} ⋅ π t ○ h t +1 π(k) , with ζ t ∼ Ber(ν), h t ∼ unif([H]), and π t ∼ unif(Ψ span h t ). Here, the main difference to Algorithm 3 (see also (47) ) is that we use π t ∼ unif(Ψ span h t ) instead of π t ∼ unif(Ψ cov h t ). We require these spanner policies instead of policies in the policy cover, as an adaptive adversary's history-dependent losses prevent standard least squares regression due to the lack of permutation invariance of state-action pairs across episodes within an epoch. Estimating the Q-functions is thus more complex, and we approach it in expectation over roll-ins using policies in Ψ span , the "in-expectation" estimation task is in a sense easier.We now state the guarantee of Algorithm 4.Theorem 4.2. Let δ ∈ (0, 1) be given and suppose that Assumption 2.1 and Assumption 4.2 hold. Then, for T = poly(A, d, H, log(|Φ|/δ)) sufficiently large, Algorithm 4 guarantees with probability at least 1δ,EQUATION)where π t is the policy that Algorithm 4 executes at episode t ∈ [T ].Algorithm 4 Oracle Efficient Algorithm for Adversarial Low-Rank MDPs (Adaptive Adversary).Input: Number of rounds T , feature class Φ, loss feature ϕ loss , confidence parameter δ ∈ (0, 1).1: Set ε ← T -1/3 , N reg ← T 2/3 , ν ← N -1/4 reg , and α ← (8Ad) -1 , T cov ← ε -2 Ad 13 H 6 log(Φ/δ). 2: Set T rep ← α -1 ε -2 AH log(|Φ|/δ), T span ← α -2 ε -2 A log(dH|Φ|ε -1 δ -1 ), 3: Define F h = {(x, a) ↦ max a∈A φh (x, a) ⊺ θ | φh = [ϕ loss h , ϕ h ], ϕ ∈ Φ, θ ∈ B 2d (1)}, ∀h ∈ [H]. 4: Get Ψ cov 1∶H ← VoX(Φ, ε, δ/4). 5: Get ϕ rep h ← RepLearn(h, F h+1 , Φ, unif(Ψ cov h ), T rep ), for all h ∈ [H -1]. // RepLearn as in Mhammedi et al. (2023) 6: For all h ∈ [H], set φrep h ← [ϕ loss h , ϕ rep h ] ∈ R 2d . 7: For h ∈ [H], set Ψ span h ← Spanner(h, Φ, Ψ cov 1∶h , φrep h , T span ).// Algorithm 78: Set T 0 ← T cov + T rep + T span . 9: for k = 1, . . . , (T -T 0 )/N reg do 10: Define π(k) h (a | x) ∝ exp (-η ∑ s<k Q(s) h (x, a)) for h ∈ [H].11:for t = T 0 + (k -1) ⋅ N reg + 1, . . . , T 0 + k ⋅ N reg do 12:Define the random variables ζ t ∼ Ber(ν), h t ∼ unif([H]), and π t ∼ unif(Ψ span h t ).13:Set πt = I{ζ t = 0} ⋅ π(k) + I{ζ t = 1} ⋅ π t ○ h t +1 π(k) . 14:Execute πt , and observe trajectory (x t 1 , a t 1 , . . . , x t H , a t H ).15:For h ∈ [H], observe loss ℓ t h ∶= ℓ h (x t h , a t h ; H t-1 ), where H t-1 ∶= (x 1∶t-1 1∶H , a 1∶t-1 1∶H ).16:end for 17:For h ∈ [H] andI (k) = {T 0 + (k -1) ⋅ N reg + 1, . . . , T 0 + k ⋅ N reg }, compute θ(k) h such that θ(k) h ← argmin θ∈B 2d (4Hd 2 ) ∑ π∈Ψ span h ∑ t∈I (k) I{h t = h, π t = π, ζ t = 1} ⋅ ( φrep h (x t h , a t h ) ⊺ θ - H ∑ s=h ℓ t s ) (18) 18: Set Q(k) h (x, a) = φrep h (x, a) ⊺ θ(k) h , for all (x, a) ∈ X × A. 19: end for 
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 √ T regret remains out of reach due to the limitations of our two-phase design. An interesting direction for future work is to perform on-the-fly representation learning to adapt to adversarial losses and achieve optimal regret. Xie, T., Foster, D. J., Bai, Y., Jiang, N., and Kakade, S. M. (2022) . The role of coverage in online reinforcement learning. arXiv preprint arXiv:2210.04157.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 on Machine Learning, pages 26447-26466. PMLR.Zhang, X., Song, Y., Uehara, M., Wang, M., Agarwal, A., and Sun, W. (2022b) Question: Does the paper provide open access to the data and code, with sufficient instructions 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 NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details.• While we 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 a 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: //nips.cc/public/guides/CodeSubmissionPolicy) 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.• The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a 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 to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, 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 not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.• The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [NA] .Justification: This paper does not include experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at 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 to 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 or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors 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 are out of range (e.g. negative error rates).• If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
 
 Appendix: 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-based (Jiang et al., 2017; Jin et al., 2021a; Du et al., 2021; Foster et al., 2021; Zhong et al., 2022) or reward-free (Chen et al., 2022b,a; Xie et 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 a strong requirement. To relax it, Modi et al. (2024) ; Zhang et 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 a 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; Lee et al., 2020; Jin et al., 2021b; Shani et al., 2020; Chen and Luo, 2021; Luo et al., 2021; Dai et al., 2022; Dann et al., 2023) . This line of work has demonstrated not only √ T regret bounds but also several data-dependent bounds.For adversarial MDPs with a large state space which necessitates the use of function approximation, if the transition is known, Foster et al. (2022) shows that adversarial setting is as easy as the stochastic setting even under general function approximation. For full-information loss feedback with unknown transition, √ T 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 T 5 /6 regret (Zhao et al., 2024) .For function approximation with bandit feedback and unknown transition, Zhao et al. ( 2022) provides √ T 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, a series of recent work has made significant progress in improving the regret bound (Luo et al., 2021; Dai et al., 2023; Sherman et al., 2023b; Kong et al., 2023; Liu et al., 2023) . The state-of-the-art result by Liu et al. (2023) gives an inefficient algorithm with √ T regret and an efficient algorithm with T 3 /4 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 to achieve regret bound that do not scale with the number of states.B Proof of Theorem 3.1 (Model-Based, Full Information) Theorem B.1 (Theorem 3 in Cheng et al. (2023) ). With probability 1δ, for any policy π and layer h, Algorithm 1 in Cheng et al. (2023) outputs transition P1∶H and features φh , μh such thatPh (x ′ | x, a) = φh (x, a) ⊺ μh+1 (x ′ ) and E π [∥ Ph (⋅ | x h , a h ) -P ⋆ h (⋅ | x h , a h ) ∥ 1 ] ≤ ϵ, if the number of collected trajectories is at least O ( H 3 d 2 |A|(d 2 +|A|) ϵ 2 log 2 (T dH|Φ||Υ|)).Define V π 1 (x 1 ; ℓ) as the value function of policy π under transition { Ph } H h=1 and loss ℓ. We haveReg T (π ⋆ ) = T ∑ t=1 V π t 1 (x 1 ; ℓ t ) - T ∑ t=1 V π ⋆ 1 (x 1 ; ℓ t ) = T ∑ t=1 (V π t 1 (x 1 ; ℓ t ) -V π t 1 (x 1 ; ℓ t )) Bias1 + T ∑ t=1 ( V π ⋆ 1 (x 1 ; ℓ t ) -V π ⋆ 1 (x 1 ; ℓ t )) Bias2 + T ∑ t=1 ( V π t 1 (x 1 ; ℓ t ) -V π ⋆ 1 (x 1 ; ℓ t )) FTRL + O ( H 3 d 2 |A|(d 2 + |A|) ϵ 2 log 2 (T dH|Φ||Υ|))Bounding the bias term. By Theorem B.1 and Lemma I.6, we haveBias1 + Bias2 ≤ 2H 2 ϵT.Bounding the FTRL term.Since η = 1 H √ T , we have FTRL ≤ T ∑ t=1 H ∑ h=1 E P ,π ⋆ [⟨ Qt h (x h , ⋅), π t h (⋅ | x h ) -π ⋆ h (⋅ | x h )⟩] (Lemma I.7) ≤ H log |A| η + η H ∑ h=1 T ∑ t=1 E P ,π ⋆ ○ h π t [( Qt h (x h , a h )) 2 ] , (Lemma I.5) ≤ H log |A| η + 2H 3 ηT ( Qt h (x h , a h ) ≤ H) = O (H 2 √ T log |A|) .Thus, by setting ϵ = (Hd 2 |A|(d 2 + |A|))1 3 T -1 3 , we have Reg T ≤ O ( H 3 d 2 |A|(d 2 + |A|) ϵ 2 log 2 (T dH|Φ||Υ|) + 2H 2 ϵT + H 2 √ T log |A|) ≤ O (H 3 (d 2 + |A|) T 2 3 log (|A| + dH|Φ||Υ|T )) .C Proof of Theorem 3.2 (Model-Based, Bandit Feedback)Lemma C.1. With P1∶H as in Theorem B.1, we have for any h ∈ [H] and any policy π,∑ x∈X | dπ h (x) -d π h (x)| ≤ h-1 ∑ i=1 E π [∥ Pi (⋅ | x i , a i ) -P i (⋅ | x i , a i )∥ 1 ] ≤ (h -1) ⋅ ϵ.where dπ h ∶= d P ,π h .Proof. We prove the claim by induction. When h = 1, given that the ∥d π 1 -dπ1 ∥ 1 = 0. Assume ∑ x∈X | dπ h (x) -d π h (x)| ≤ h-1 ∑ i=1 E π [∥ Pi (⋅ | x i , a i ) -P i (⋅ | x i , a i )∥ 1 ] .We have∑ x∈X h+1 | dπ h+1 (x) -d π h+1 (x)| = ∑ x∈X ∑ a∈A ∑ x ′ ∈X h+1 | dπ h (x)π h (a | x) ⋅ Ph (x ′ |x, a) -d π h (x)π h (a | x) ⋅ P ⋆ h (x ′ |x, a)| , ≤ ∑ x∈X ∑ a∈A ∑ x ′ ∈X h+1 | dπ h (x)π h (a | x) ⋅ Ph (x ′ |x, a) -d π h (x)π h (a | x) ⋅ Ph (x ′ |x, a)| + ∑ x∈X ∑ a∈A ∑ x ′ ∈X h+1 |d π h (x)π h (a | x) ⋅ Ph (x ′ |x, a) -d π h (x)π h (a | x) ⋅ P ⋆ h (x ′ |x, a)| , ≤ ∑ x∈X ∑ a∈A ∑ x ′ ∈X h+1 Ph (x ′ |x, a)π h (a | x) ⋅ | dπ h (x) -d π h (x)| + ∑ x∈X ∑ a∈A ∑ x ′ ∈X h+1 d π h (x)π h (a | x) ⋅ | Ph (x ′ |x, a) -P h (x ′ |x, a)|, ≤ ∑ x∈X | dπ h (x) -d π h (x)| + E π [∥ Ph (⋅ | x h , a h ) -P h (⋅ | x h , a h )∥ 1 ] , ≤ h ∑ i=1 E π [∥ Pi (⋅ | x i , a i ) -P i (⋅ | x i , a i )∥ 1 ] ,where the last step follows by the induction hypothesis. The second inequality of Lemma C.1 directly comes from Theorem B.1.Our candidate policy space Π ′ has a β mixture of the random policy. For any deterministic policy π ⋆ 0 , define policy π ⋆ such that for any state x ∈ X , we have π⋆ (⋅ | x) = (1 -β)π ⋆ 0 (⋅ | x) + β |A| . We have π ⋆ ∈ Π ′ . Define V π 1 (x 1 ; ℓ)as the value function of policy π under transition { Ph } H h=1 and loss ℓ. For any policy π ⋆ 0 , we haveReg T (π ⋆ 0 ) (19) = E [ T ∑ t=1 ∑ π ρ t (π)V π 1 (x 1 ; ℓ t ) -V π ⋆ 0 1 (x 1 ; ℓ t )] + O ( H 3 d 2 |A|(d 2 + |A|) ϵ 2 log 2 (T dH|Φ||Υ|)) , = E [ T ∑ t=1 ∑ π p t (π)V π 1 (x 1 ; ℓ t ) -V π ⋆ 1 (x 1 ; ℓ t )] + O ( H 3 d 2 |A|(d 2 + |A|) ϵ 2 log 2 (T dH|Φ||Υ|)) (20) + E [ T ∑ t=1 ∑ π (ρ t (π) -p t (π)) V π 1 (x 1 ; ℓ t )] Error1 + E [ T ∑ t=1 V π ⋆ 1 (x 1 ; ℓ t ) -V π ⋆ 0 1 (x 1 ; ℓ t )] Error2 , = E [ T ∑ t=1 ∑ π p t (π) (V π 1 (x 1 ; ℓ t ) -V π 1 (x 1 ; ℓ t ))] Bias1 + E [ T ∑ t=1 V π ⋆ 1 (x 1 ; ℓ t ) -V π ⋆ 1 (x 1 ; ℓ t )] Bias2 + E [ T ∑ t=1 ∑ π p t (π) V π 1 (x 1 ; ℓ t ) -V π ⋆ 1 (x 1 ; ℓ t )] EXP + Error1 + Error2 + O ( H 3 d 2 |A|(d 2 + |A|) ϵ 2 log 2 (T dH|Φ||Υ|)) . (21) Recall that J = John{ φh (π)} π∈Π ′ ,h∈[H] ∈ ∆(Π ′ × H), and we have ρ t (π) = (1 -γ)p t (π) + γ ∑ H h=1 J(π, h) where p t (π) is defined in Line 7 of Algorithm 2. Lemma C.2. We haveError1 + Error2 ≤ HγT + 2H 2 βT. Proof. Error1 = γE [ T ∑ t=1 ∑ π ( H ∑ h=1 J(π, h) -p t (π)) ⋅ V π 1 (x 1 ; ℓ t )] ≤ HγT. Error2 = T ∑ t=1 H ∑ h=1 E π ⋆ [ ∑ a∈A |π ⋆ 0 (a | x h ) -π ⋆ (a | x h )| ⋅ Q π ⋆ 0 h (x h , a; ℓ t )] ≤ 2H 2 βT,where the last step follows by Lemma I.7.Lemma C.3. We haveBias1 + Bias2 ≤ H 2 T ϵ.Proof. This is a direct result combing Theorem B.1 and Lemma I.6.For (x 1∶H , a 1∶H ) ∈ X H × A H and π ∈ Π ′ where Π ′ defined in Line 5 in Algorithm 2 is the mix of a given policy class Π and a uniform policy, and is also the policy class we play with. Recall that the loss estimatorEQUATIONdefined in Line 10 of Algorithm 2.Lemma C.4. For any episode t ∈ [T ], for any policy π we haveV π 1 (x 1 ; ℓ t ) ≤ E π t ∼ρ t E π t [ lt (π; π t , x 1∶H , a 1∶H )] + √ dHϵ H ∑ h=2 ∥ φh-1 (π)∥ (Σ t h-1 ) -1 , V π 1 (x 1 ; ℓ t ) ≥ E π t ∼ρ t E π t [ lt (π; π t , x 1∶H , a 1∶H )] - √ dHϵ H ∑ h=2 ∥ φh-1 (π)∥ (Σ t h-1 ) -1 .Proof. First, from the definition in Line 4 of Algorithm 2, for any x ∈ X with h ≥ 2, we havedπ h (x) = ∑ x ′ ,a ′ dπ h-1 (x ′ , a ′ ) ⋅ Ph-1 (x | x ′ , a ′ ) = φh-1 (π) ⊺ μh (x)where φh-1(π) = ∑ x ′ ,a ′ dπ h-1 (x ′ , a ′ ) φh-1 (x ′ , a ′). We now prove the first inequality:V π 1 (x 1 ; ℓ t ) = H ∑ h=1 ∑ x h ∈X ∑ a h ∈A dπ h (x h )π h (a h | x h ) ⋅ ℓ t h (x h , a h ), = ∑ a1∈A π 1 (a 1 | x 1 ) ⋅ ℓ t 1 (x 1 , a 1 ) First + H ∑ h=2 ∑ x h ∈X ∑ a h ∈A φh-1 (π) ⊺ μh (x h )π h (a h | x h ) ⋅ ℓ t h (x h , a h ) Remain (23)Through importance sampling, we haveFirst = E π t ∼ρ t E π t [ π 1 (a 1 | x 1 ) π t 1 (a 1 | x 1 ) ⋅ ℓ t 1 (x 1 , a 1 )] .We now bound the remaining term in (42) Since Σ t h-1 = E π t ∼ρ t [ φh-1 (π t ) φh-1 (π t ) ⊺ ], we have Remain = H ∑ h=2 ∑ x h ∈X ∑ a h ∈A φh-1 (π) ⊺ (Σ t h-1 )-1EQUATIONEQUATIONEQUATIONwhere ( 25) follows by Cauchy-Schwarz, and the last inequality uses Lemma C.1. Adding up First and Remain, and using the defintion of l in ( 22) implies the first inequality of the lemma.The second inequality follows the same procedure except for applying Cauchy-Schwarz inequality in the opposite direction in Eq. ( 24).Lemma C.5. If η ≤ ( 2|A|Hd βγ + dH 2 ϵ √ γ ) -1, thenEXP ≤ log |Π| η + 6dηH 2 |A|T β + 4ηd 2 H 4 ϵ 2 T + 4dH 2 ϵT,where EXP is as in (21).Proof. Recall in Line 10 of Algorithm 2, b t (π) ∶= √ dHϵ ∑ H h=2 ∥ φh-1 (π)∥ (Σ t h-1 )-1 , for all π ∈ Π ′ . By Lemma C.4, we haveEQUATION≤ FTRL + 4dH 2 ϵT,whereEQUATION)We now bound the FTRL term. Sinceρ t (π) = (1 -γ)p t (π) + γ ∑ H h=1 J(π, h), define Σ J = ∑ π∈Π ∑ H h=1 J(π, h) φh (π) φh (π) ⊺ .Note that for any t ∈ [T ] and h ∈ [H], we have Σ t h ⪰ γΣ J . By the triangle inequality, we have for any π, π t and (x 1∶H , a 1∶H ),| lt (π; π t , x 1∶H , a 1∶H )| ≤ | π 1 (a 1 | x 1 ) π t 1 (a 1 | x 1 ) ⋅ ℓ t 1 (x 1 , a 1 )| + H ∑ h=2 | φh-1 (π) ⊺ (Σ t h-1 ) -1 φh-1 (π t ) π h (a h | x h ) π t h (a h | x h ) ℓ t h (x h , a h )| , ≤ |A| β + |A| β H ∑ h=2 | φh-1 (π) ⊺ (Σ t h-1 ) -1 φh-1 (π t )| ,(β-mixure of uniform policy)EQUATION|b t (π)| = | √ dHϵ H ∑ h=2 ∥ φh-1 (π)∥ (Σ t h-1 ) -1 | ≤ dH 2 ϵ √ γ . To ensure η | lt (π; π t , x 1∶H , a 1∶H ) -b t (π)| ≤ 1, it suffices to set η ≤ ( 2|A|Hd βγ + dH 2 ϵ √ γ ) -1. Under this constraint, from Lemma I.5, we haveFTRL ≤ log |Π| η + 2η T ∑ t=1 ∑ π∈Π ′ p t (π) ⋅ E π t ∼ρ t E π t [ lt (π; π t , x 1∶H , a 1∶H ) 2 ] Stability-1 + E [2η T ∑ t=1 ∑ π∈Π ′ p t (π)b t (π) 2 ] Stability-2For any t ∈ [T ], we haveEQUATION≤ H|A| β + 2H|A| β H ∑ h=2 E π t ∼ρ t [Tr ( φh-1 (π t ) φh-1 (π t ) ⊺ (Σ t h-1 ) -1 )] , ≤ 3dH 2 |A| β .where (29) follows by the fact that p t (π) ≤ 1 1-γ ρ t (π) and 1 1-γ ≤ 2. Thus,Stability-1 = 2η ∑ π∈Π ′ p t (π) ⋅ E π t ∼ρ t E π t [ lt (π; π t , x 1∶H , a 1∶H ) 2 ] ≤ 6dηH 2 |A|T β .Moreover,Stability-2 = 2ηE [ T ∑ t=1 ∑ π∈Π ′ p t (π)b t (π) 2 ] , = 2ηdH 3 ϵ 2 E [ T ∑ t=1 H ∑ h=2 ∑ π∈Π ′ p t (π) ∥ φh-1 (π)∥ 2 (Σ t h-1 ) -1 ] , ≤ 4ηdH 3 ϵ 2 E [ T ∑ t=1 H-1 ∑ h=1 ∑ π∈Π ′ ρ t (π) ∥ φh-1 (π)∥ 2 (Σ t h-1 ) -1 ] , ≤ 4ηd 2 H 4 ϵ 2 T. Combing Lemma C.2, Lemma C.3 and Lemma C.5, if η ≤ ( 2|A|Hd βγ + dH 2 ϵ √ γ ) -1, we haveReg T (π ⋆ 0 ) ≤ HγT + 2H 2 βT + H 2 T ϵ + log |Π| η + 6dηH 2 |A|T β + 4ηd 2 H 4 ϵ 2 T + 4dH 2 ϵT + O ( H 3 d 2 |A|(d 2 + |A|) ϵ 2 log 2 (T dH|Φ||Υ|)).By setting ϵ = T -1 3 , γ = T -1 3 , β = T -1 3 , η = 1 4Hd|A| T -2 3 , we have for any π ⋆ 0 ∈ Π, Reg T (π ⋆ 0 ) ≤ O (d 2 H 3 |A|(d 2 + |A|)T 2 3 log |Π| log 2 (T dH|Φ||Υ|)) .D More Details of Inefficient Model-Free Algorithm in Section 4.1In this section, we give a more detailed introduction of the algorithm mentioned in Section 4.1. This algorithm is model-free and achieves T 23 regret, but it is computationally inefficient. We consider the low-rank MDPs with linear losses that satisfies Assumption 2.1 and Assumption 2.2.Let C (S, ϵ ′ ) be ϵ ′ -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Π lin = {π ∶ X → ∆(A) | π h (a | x) = I{a = argmin a∈A ϕ h (x, a) ⊺ θ h }, h ∈ [H], θ h ∈ B d ( √ dHT ) , ϕ ∈ Φ} . Π cov lin (ϵ ′ ) = {π ∶ X → ∆(A) | π h (a | x) = I{a = argmin a∈A ϕ h (x, a) ⊺ θ h }, h ∈ [H], θ h ∈ C (B d ( √ dHT ) , ϵ ′ ) , ϕ ∈ Φ} .Define corresponding function class as followsF π = {f ∶ X → [-1, 1] | f (x) = ∑ a π(a|x)ϕ(x, a) ⊺ θ, for θ ∈ B d ( √ d) and ϕ ∈ Φ} F = {f ∶ X → [-1, 1] | f ∈ ⋃ π∈Π lin F π } .Our main algorithm is given in Algorithm 5, which shares the same structure as Algorithm 2, but with a different initial phase to learn expected feature estimator φh (π) = ∑ (x,a)∈X ×A dπ h (x)π(a|x) φh (x, a)to approximate ϕ ⋆ h (π) = ∑ (x,a)∈X ×A d π h (x)π(a|x)ϕ ⋆ h (x, a) for every h ∈ [H].In Algorithm 2, under Assumption 3.1, it is feasible to use established model-based approach to learn an accurate estimated transition P together with its feature φ. The occupancy estimator dπ 1∶H is induced by P which also enjoy small errors. However, when we move to model-free settings with Assumption 4.1, there is no existing approach that could guarantee a good estimation for dπ h (x) and φ.To tackle this challenge, we first call VoX (Mhammedi et al., 2023) to construct a policy cover Ψ cov 1∶H , and then play every policy in Ψ cov 1∶H for n episodes to collect data. Subsequently, these data are fed into Algorithm 6 to jointly solve estimated occupancy dπ 1∶H and feature φ1∶H . Algorithm 6 is similar to (Liu et al., 2023, Algorithm 1) , which is used to estimate occupancy on the fly for linear MDP. In Algorithm 6, given a target policy π, we jointly solve φ1∶H ∈ Φ, dπ1∶H ∈ [0, 1] |X | , and ( ξ1∶H,f ) f ∈F π ⊂ B d ( √ d) that satisfies four constrains, where ξh,f is the estimation of ξ ⋆ h,f ∶= ∑ x ′ ∈X µ ⋆ h+1 (x ′ )f (x ′ ).The first constraint Eq. ( 30) ensures the estimated occupancy dπ 1∶H are 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 φh (x, a) ⊺ ξh,f . The third constrain Eq. ( 32) and fourth constrain Eq. ( 33) are then used to bound the estimated bias of φh (x, a) ⊺ ξh,f by utilizing the data collected from policies in policy covers Ψ cov 1∶H . Note that applying Eq. ( 33) requires access to the whole state space, which is an additional assumption not needed in previous algorithms. The gurantee of Algorithm 5 is given in Theorem D.1, where the Õ hides the logarithmic dependence on d, H, |A|, T .Theorem D.1. Algorithm 5 ensures Reg T ≤ Õ (d 8 H 6 |A|T Algorithm 5 Model-Free Algorithm for Bandit FeedbackInput: Policy class Π = Π cov lin ( 1 T ). 1: Set ϵ = 18 -1 d 5 2 T -1 3 , γ = T -1 3 , β = T -1 3 , η = (4Hd|A|) -1 T -2 3 , n = 11250d 5 2 |A|T 2 3 log 3dnHT |Φ| δ and T 0 = Õ (ϵ -2 |A|d 13 H 6 log(|Φ|/δ))). 2: Get Ψ cov1∶H ← VoX(Φ, ε, δ) using T 0 episodes. 3: For every policy π ′ ∈ Ψ cov 1∶H , play it for n episodes and get the data set(D π ′ h ) h∈[H]where D π ′ h consists of tuples (x, a, x ′ ) such that (x, a) ∼ d π ′ h and x ′ ∼ P ⋆ (⋅ | x, a). 4: Define the policy spaceΠ ′ = {π ′ ∶ ∃π ∈ Π, π ′ h (⋅ | x) = (1 -β)π h (⋅ | x) + β/|A|, ∀x, h}. 5: Get φh (⋅) ← EOM-PC (Π ′ , (D π ′ h ) h∈[H],π ′ ∈Ψ cov 1∶H) from Algorithm 6.6: for t = T 0 + 1, T 0 + 2, . . . , T do 7:Define p t (π) ∝ exp (-η ∑ t-1 i=1 ( li (π) -b i (π))) , for all π ∈ Π ′ . 8: Let ρ t (π) = (1 -γ)p t (π) + γ H-1 ∑ H-1 h=1 J h , where J h = John( φh (⋅), Π ′ ). // John as in §2 9:Execute policy π t ∼ ρ t and observe trajectory (x t 1∶H , a t 1∶H ) and losses ℓ t h = ℓ t h (x t h , a t h ).10:Define Σ t h = ∑ π∈Π ′ ρ t (π) ⋅ φh (π) φh (π) ⊺ , b t (π) = d 11 2 HT -1 3 ⋅ ∑ H-1 h=1 ∥ φh (π)∥ (Σ t h ) -1, andlt (π) = π 1 (a t 1 | x t 1 ) π t 1 (a t 1 | x t 1 ) ℓ t 1 + H ∑ h=2 φh-1 (π) ⊺ (Σ t h-1 ) -1 φh-1 (π t ) π h (a t h | x t h ) π t h (a t h | x t h ) ℓ t h . 11: end for Algorithm 6 EOM-PC(Π, (D π ′ h ) h∈[H],π ′ ∈Ψ cov 1∶H) (Estimate Occupancy Measure with Policy Cover)Input: The policy class Π, datasets (D π ′ h ) h∈[H] for every π ′ ∈ Ψ cov 1∶H Jointly find φh ∈ Φ, ( dπ h ) π∈Π ∈ [0, 1] |X | , and ( ξh,f ) f ∈F ⊂ B d ( √ d) for any h ∈ [H] such that for all π ∈ Π, ∑ x∈X dπ h (x) = 1, ∀h ∈ [H] (30) ∑ x ′ ∈X dπ h+1 (x ′ )f (x ′ ) = ∑ x∈X ∑ a∈A dπ h (x)π(a|x) φh (x, a) ⊺ ξh,f , ∀f ∈ F, h ∈ [H] (31) ∑ x,a,x ′ ∈D π ′ h (f (x ′ ) -φh (x, a) ⊺ ξh,f ) 2 - min (ϕ,ξ)∈Φ×B d ( √ d) ∑ x,a,x ′ ∈D π ′ h (f (x ′ ) -ϕ(x, a) ⊺ ξ) 2 ≤ 132d 3 2 log(3dnHT |Φ|/δ), ∀π ′ ∈ Ψ cov 1∶H , f ∈ F, h ∈ [H] (32) max x,a | φh (x, a) ⊺ ξh,f | ≤ 1 ∀f ∈ F, h ∈ [H] (33) Output: φh ∶ Π → R d , φh (π) = ∑ (x,a)∈X ×A dπ h (x)π(a|x) φh (x, a), ∀h ∈ [H]. D.2 Analysis of Occupancy Estimation from Algorithm 6 Lemma D.1. With probability 1 -δ, ϕ ⋆ 1∶H , (d π 1∶H ) π∈Π ′ , and ξ ⋆ h,f ∶= ∑ x ′ ∈X µ ⋆ h+1 (x ′ )f (x ′ ), ∀f ∈ F, ∀h ∈ [H] is a solution to Algorithm 6.Proof. Since for any policy π and any h ∈ [H], ∑ x∈X d π h (x) = 1, Eq. ( 30) holds. For any policy π, any f ∈ F π and any h ∈ [H], we have∑ x ′ ∈X d π h+1 (x ′ )f (x ′ ) = ∑ x ′ ∈X ∑ x∈X ∑ a∈A d π h (x)π(a|x)P ⋆ h (x ′ | x, a)f (x ′ ) = ∑ x∈X h ∑ a∈A d π h (x)π(a|x)ϕ ⋆ h (x, a) ⊺ ∑ x ′ ∈X h+1 µ ⋆ h+1 (x ′ )f (x ′ ) = ∑ x∈X h ∑ a∈A d π h (x)π(a|x)ξ ⋆ h,f .Thus, Eq. ( 31) holds. From Exercise 27.6 of Lattimore and Szepesvári (2020), the ϵ-net of B d (R) is ( 3R ϵ ) d . Thus. |Π ′ | = |Π cov lin ( 1 T )| = |Φ| (3 √ dHT 2 ) d . We also have |C (B d ( √ d), 1 T )| = (3 √ dT ) d and for any policy π, |C (F π , 1 T )| = |Φ| (3 √ dT ) d .To consider all possible instances, defineN T ∶= |Π ′ | |C (B d ( √ d), ϵ)| |C (F π , ϵ)| |Ψ cov 1∶H | |Φ|H ≤ dH 2 |Φ| 3 (3 √ dHT 2 ) 3dThus, by union bound, with probability of 1-δ, for every π ∈ Π ′ , everyπ ′ ∈ Ψ cov 1∶H , every f ∈ C (F π , ϵ), every ξ ∈ C (B d ( √ d), ϵ), every ϕ ∈ Φ and every h ∈ [H], we have ∑ x,a,x ′ ∈D π ′ h (f (x ′ ) -ϕ ⋆ h (x, a) ⊺ ξ ⋆ h,f ) 2 - ∑ x,a,x ′ ∈D π ′ h (f (x ′ ) -ϕ(x, a) ⊺ ξ) 2 = -2 ∑ x,a,x ′ ∈D π ′ h (f (x ′ ) -ϕ ⋆ h (x, a) ⊺ ξ ⋆ h,f ) (ϕ ⋆ h (x, a) ⊺ ξ ⋆ h,f -ϕ(x, a) ⊺ ξ) - ∑ x,a,x ′ ∈D π ′ h (ϕ ⋆ h (x, a) ⊺ ξ ⋆ h,f -ϕ(x, a) ⊺ ξ) 2 = -2 ∑ x,a,x ′ ∈D π ′ h (f (x ′ ) -E x ′ ∼P ⋆ (⋅|x,a) [f (x ′ )]) (ϕ ⋆ h (x, a) ⊺ ξ ⋆ h,f -ϕ(x, a) ⊺ ξ) - ∑ x,a,x ′ ∈D π ′ h (ϕ ⋆ h (x, a) ⊺ ξ ⋆ h,f -ϕ(x, a) ⊺ ξ) 2 ≤ 8 ∑ x,a,x ′ ∈D π ′ h (ϕ ⋆ h (x, a) ⊺ ξ ⋆ h,f -ϕ(x, a) ⊺ ξ) 2 log |N T | δ + 4 √ d log |N T | δ - ∑ x,a,x ′ ∈D π ′ h (ϕ ⋆ h (x, a) ⊺ ξ ⋆ h,f -ϕ(x, a) ⊺ ξ) 2 (Freedman's Inequality) ≤ 20 √ d log |N T | δ (AM-GM) ≤ 120d 3 2 log 3dHT |Φ| δ Bounding the distance through 1T -net, we have with probability of 1δ, for every π ∈ Π ′ , everyπ ′ ∈ Ψ cov 1∶H , every f ∈ F π , every ξ ∈ B d ( √ d), every ϕ ∈ Φ and every h ∈ [H], ∑ x,a,x ′ ∈D π ′ h (f (x ′ ) -ϕ ⋆ h (x, a) ⊺ ξ ⋆ h,f ) 2 - ∑ x,a,x ′ ∈D π ′ h (f (x ′ ) -ϕ(x, a) ⊺ ξ) 2 ≤ 120d 3 2 log 3dHT |Φ| δϵ + 12 √ dn T ≤ 132d 3 2 log3dnHT |Φ| δ Thus, Eq. (32) also holds. Finally, for all x, a, we have|ϕ ⋆ h (x, a) ⊺ ξ ⋆ h,f | = | ∑ x ′ ∈X ϕ ⋆ h (x, a) ⊺ µ ⋆ h+1 (x ′ )f (x ′ )| = | ∑ x ′ ∈X P ⋆ (x ′ | x, a) f (x ′ )| ≤ 1. Thus, ϕ ⋆ h , d π h , and ξ ⋆ h,f ∶= ∑ x ′ ∈X µ ⋆ h+1 (x ′ )f (x ′ ), ∀f ∈ F π , h ∈ [H]satisfy all Eq. (30) -Eq. ( 33) and is a solution to Algorithm 6. Lemma D.2. With probability 1δ, for all f ∈ F, any solution dπ from Algorithm 6 for any π ∈ Π ′ satisfies|∑ x ( dπ h (x) -d π h (x))f (x)| ≤ d 5 HT -1 3 Proof.For every solution φ1∶H , ξ1∶H,f∈F π , ( dπ 1∶H ) π∈Π ′ of Algorithm 6, we haveEQUATION)where the last step comes from the constrain Eq. ( 32). On the other hand2 ∑ x,a,x ′ ∈D π ′ h (f (x ′ ) -φh (x, a) ⊺ ξh,f ) 2 -2 ∑ x,a,x ′ ∈D π ′ h (f (x ′ ) -ϕ ⋆ h (x, a) ⊺ ξ ⋆ h,f ) 2 = 4 ∑ x,a,x ′ ∈D π ′ h (f (x ′ ) -ϕ ⋆ h (x, a) ⊺ ξ ⋆ h,f ) (ϕ ⋆ h (x, a) ⊺ ξ ⋆ h,f -φh (x, a) ⊺ ξh,f ) + 2 ∑ x,a,x ′ ∈D π ′ h (ϕ ⋆ h (x, a) ⊺ ξ ⋆ h,f -φh (x, a) ⊺ ξh,f ) 2 = 4 ∑ x,a,x ′ ∈D π ′ h (f (x ′ ) -E x ′ ∼P ⋆ (⋅|x,a) [f (x ′ )]) (ϕ ⋆ h (x, a) ⊺ ξ ⋆ h,f -φh (x, a) ⊺ ξh,f ) + 2 ∑ x,a,x ′ ∈D π ′ h (ϕ ⋆ h (x, a) ⊺ ξ ⋆ h,f -φh (x, a) ⊺ ξh,f ) 2 (35)Combing Eq. ( 34) and Eq. ( 35), we have∑ x,a,x ′ ∈D π ′ h (ϕ ⋆ h (x, a) ⊺ ξ ⋆ h,f -φh (x, a) ⊺ ξh,f ) 2 ≤ -4 ∑ x,a,x ′ ∈D π ′ h (f (x ′ ) -E x ′ ∼P ⋆ (⋅|x,a) [f (x ′ )]) (ϕ ⋆ h (x, a) ⊺ ξ ⋆ h,f -φh (x, a) ⊺ ξh,f ) - ∑ x,a,x ′ ∈D π ′ h (ϕ ⋆ h (x, a) ⊺ ξ ⋆ h,f -φh (x, a) ⊺ ξh,f ) 2 + 264d 3 2 log 3dnHT |Φ| δ ≤ 288d 3 2 log 3dnHT |Φ| δ (Lemma I.2 with λ = 1 8 )Since for every data tuple (x, a, x ′ ) ∈ D π ′ h , (x, a) ∼ d π ′ h independently, by Lemma I.3, for every π ′ ∈ Ψ cov 1∶H we haveE π ′ [(ϕ ⋆ h (x, a) ⊺ ξ ⋆ h,f -φh (x, a) ⊺ ξh,f ) 2 ] ≤ 2 n ∑ x,a∈D π ′ h (ϕ ⋆ h (x, a) ⊺ ξ ⋆ h,f -φh (x, a) ⊺ ξh,f ) 2 + 24d log ( 6 √ d|Φ| δ ) n ≤ 600d 3 2 n log 3dnHT |Φ| δThis implies there exists a representation φ1∶H (x, a) such that for every f ∈ F and any h ∈ [H], there exists ξh,f such thatEQUATIONEq. ( 36) matches Eq. ( 99) with a different error bound on the right hand. From Lemma G.1, we have Ψ cov h is a ( 1 8Ad , ε)-policy cover for layer h, following the rest of the proof in Lemma G.2, for every π and every f ∈ F, h ∈ [H], we haveEQUATION)The d 18 T -1 3 into Eq. ( 37), we have for every π and every f ∈ F, h ∈ [H], we have|E π [ϕ ⋆ h (x, a) ⊺ ξ ⋆ h,f -φh (x, a) ⊺ ξh,f ]| ≤ d 5 T -1 3 (38)Utilizing above results, for every π, every f ∈ F and any h ∈ [H -1], we have|∑ x ( dπ h+1 (x) -d π h+1 (x))f (x)| = ∑ x,a dπ h (x)π h (a | x) φh (x, a) ⊺ ξh,f -∑ x,a d π h (x)π(a | x)ϕ ⋆ h (x, a) ⊺ ξ ⋆ h,f(Eq. ( 31))≤ ∑x,ad π h (x)π h (a | x) (ϕ ⋆ h (x, a) ⊺ ξ ⋆ h,f -φh (x, a) ⊺ ξh,f ) + ∑ x ( dπ h (x) -d π h (x)) ∑ a π h (a|x) φh (x, a) ⊺ ξh,f ∈F ≤ d 5 T -1 3 + |∑ x ( dπ h (x) -d π h (x)) f ′ (x)| (Eq. (38))where in the last step, we define f ′ (x) = ∑ a π h (a|x) φh (x, a) ⊺ ξh,f ∈ F. This allow us to use recursion to finish the proof.We begin by proving Lemma D.3, showing that the policy class Π cov lin (ϵ ′ ) suffices to approximate all policies with small error.Lemma D.3. For any policy π, there exists a policy π ′ ∈ Π cov lin (ϵ ′ ) such thatT ∑ t=1 V π ′ 1 (x 1 ; ℓ t ) - T ∑ t=1 V π 1 (x 1 ; ℓ t ) ≤ Hϵ ′ Proof. Let θ t,π h ∈ B d (H √ d) be such that ∀(x, a) ∈ X × A, Q π h (x, a; ℓ t ) = ϕ ⋆ h (x, a) ⊺ θ π,t h .Such a θ π,t h is guaranteed to exist by the low-rank MDP structure (Assumption 2.1) and Assumption 2.2. For every h ∈[H], since ∑ T t=1 θ π,t h ∈ B d ( √ dHT ), we define θ ′ h ∈ C (B d ( √ dHT ) , ϵ ′ ) such that ∥θ ′ h -∑ T t=1 θ π,t h ∥ 2 ≤ ϵ ′ , and let π h (a | x) = I{a = argmin a∈A ϕ ⋆ h (x, a) ⊺ θ ′ h } for every h ∈ [H]. We have π ′ ∈ Π cov lin (ϵ ′ ).From Lemma I.7, we haveT ∑ t=1 V π ′ 1 (x 1 ; ℓ t ) - T ∑ t=1 V π 1 (x 1 ; ℓ t ) = T ∑ t=1 H ∑ h=1 E x∼d π ′ h [ ∑ a∈A (π ′ h (a|x) -π h (a|x)) Q π h (x, a; ℓ t )] = H ∑ h=1 E x∼d π ′ h [ ∑ a∈A (π ′ (a|x) -π(a|x)) ϕ ⋆ h (x, a) ⊺ T ∑ t=1 θ π,t h ] = H ∑ h=1 E x∼d π ′ h [ ∑ a∈A (π ′ h (a|x) -π h (a|x)) ϕ ⋆ h (x, a) ⊺ θ ′ h ] ≤0 + H ∑ h=1 E x∼d π ′ h [ ∑ a∈A (π ′ h (a|x) -π h (a|x)) ϕ ⋆ h (x, a) ⊺ ( T ∑ t=1 θ π,t h -θ ′ h )] ≤ Hϵ ′where the last inequality comes from the fact that πh (a | x) = I{a = argmin a∈A ϕ ⋆ h (x, a) ⊺ θ ′ h } and ∥θ ′ h -∑ T t=1 θ π,t h ∥ 2 ≤ ϵ ′ for every h ∈ [H].From Lemma D.3, for any policy π ⋆ 1 , there exists a policy πEQUATIONOur candidate policy space Π ′ has a β mixture of the random policy. For any policy π ⋆ 0 ∈ Π cov lin ( 1 T ), define policy π ⋆ such that for any state x ∈ X , we have π⋆ (⋅ | x) = (1 -β)π ⋆ 0 (⋅ | x) + β |A| . We have π ⋆ ∈ Π ′ . Define V π 1 (x 1 ; ℓ) = H ∑ h=1 ∑ x h ∈X ∑ a h ∈A dπ h (x h )π h (a h | x h ) ⋅ ℓ t h (x h , a h )Utilizing Eq. ( 39) and the decomposition in Eq. ( 21), together with the fact that |Ψ cov h | ≤ d from Lemma G.1, we have for any policy πEQUATIONFollowing Lemma C.2, we haveEQUATION)Lemma D.4.Bias1 + Bias2 ≤ 2d 5 H 2 T 2 3Proof. For any policy π and any t ∈ [T ],|V π 1 (x 1 ; ℓ t ) -V π 1 (x 1 ; ℓ t )| = H ∑ h=1 ∑ x h ∈X |d π h (x h ) -dπ h (x h )| ∑ a h ∈A π h (a h | x h ) ⋅ ℓ t h (x h , a h ) ≤ d 5 H 2 T -1 3 (Lemma D.2)Thus,Bias1 ≤ d 5 H 2 T 2 3 and Bias2 ≤ d 5 H 2 T 2 3We now prove a modle-free counterpart of Lemma C.4 in Lemma D.5.Lemma D.5. For any episode t ∈ [T ], for any policy π we haveV π 1 (x 1 ; ℓ t ) ≤ E π t ∼ρ t E π t [ lt (π; π t , x 1∶H , a 1∶H )] + d 11 2 HT -1 3 H ∑ h=2 ∥ φh-1 (π)∥ (Σ t h-1 ) -1 , V π 1 (x 1 ; ℓ t ) ≥ E π t ∼ρ t E π t [ lt (π; π t , x 1∶H , a 1∶H )] -d 11 2 HT -1 3 H ∑ h=2 ∥ φh-1 (π)∥ (Σ t h-1 ) -1 .Proof.We now prove the first inequality:EQUATIONThrough importance sampling, we haveFirst = E π t ∼ρ t E π t [ π 1 (a 1 | x 1 ) π t 1 (a 1 | x 1 ) ⋅ ℓ t 1 (x 1 , a 1 )] .We now bound the remaining term in (42) Since Σ t h-1 = E π t ∼ρ t [ φh-1 (π t ) φh-1 (π t ) ⊺ ], we have Remain = H ∑ h=2 ∑ x h ∈X dπ h (x h ) ∑ a h ∈A π h (a h | x h )ϕ h (x h , a h ) ⊺ g t h ∶=f (x h ) , = H ∑ h=2 ∑ x h-1 ∈X h-1 ∑ a h-1 dπ h-1 (x)π h-1 (a h-1 |x h-1 ) φ(x h-1 , a h-1 ) ⊺ξh-1,f (by Eq. ( 31))EQUATION≤ E π t ∼ρ t E π t [ H ∑ h=2 φh-1 (π) ⊺ (Σ t h-1 ) -1 φh-1 (π t ) π h (a t h | x t h ) π t h (a t h | x t h ) ℓ t h (x t h , a t h )] + d 11 2 HT -1 3 H ∑ h=2 ∥ φh-1 (π)∥ (Σ t h-1 ) -1 ,Adding up First and Remain, and using the defintion of l in ( 22) implies the first inequality of the lemma.The second inequality follows the same procedure except for applying Cauchy-Schwarz 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 √ dHϵ to d 11 2 HT -1 3 . This leads to the following changes. Firstly, by a similar argument as Eq. ( 27), we haveEXP = FTRL + 4d 6 H 2 T 2 3whereFTRL ∶= T ∑ t=1 ∑ π p t (π) ⋅ (E π t ∼ρ t E π t [ lt (π; π t , x 1∶H , a 1∶H )] -b t (π)) - T ∑ t=1 (E π t ∼ρ t E π t [ lt (π ⋆ ; π t , x 1∶H , a 1∶H )] -b t (π ⋆ )) .Secondly, now we have|b t (π)| = |d 11 2 HT -1 3 H ∑ h=2 ∥ φh-1 (π)∥ (Σ t h-1 ) -1 | ≤ d 6 H 2 T -1 3 √ γ = d 6 H 2 T -1 6 . (γ = T -1 3 ) To ensure η | lt (π; π t , x 1∶H , a 1∶H ) -b t (π)| ≤ 1, it suffices to set η ≤ ( 2|A|Hd βγ + d 6 H 2 T -1 6 ) -1 = (2|A|HdT 2 3 + d 6 H 2 T -1 6 ) -1 from β = γ = T -1 3 . Thus our choice η = (4Hd|A|) -1 T -2 3satisfies the condition if we assume T ≥ d 6 H 2 . Moreover, now we haveStability-2 = 2ηE [ T ∑ t=1 ∑ π∈Π ′ p t (π)b t (π) 2 ] , = 2ηd 11 H 3 T -2 3 E [ T ∑ t=1 H ∑ h=2 ∑ π∈Π ′ p t (π) ∥ φh-1 (π)∥ 2 (Σ t h-1 ) -1 ] , ≤ 4ηd 11 H 3 T -2 3 E [ T ∑ t=1 H-1 ∑ h=1 ∑ π∈Π ′ ρ t (π) ∥ φh-1 (π)∥ 2 (Σ t h-1 ) -1 ] , ≤ 4ηd 11 H 4 T 1 3 ≤ d 10 H 3 T -1 3 ≤ d 4 HT 2 3 . (Assume T ≥ d 6 H 2 )Putting these two changes back to the proof into Lemma C.5, given η = (4Hd|A|) -1 T -2 3 we haveEQUATIONPutting Eq. ( 41), Lemma D.4, Eq. ( 44) into Eq. ( 40) together with ϵ = 18 -1 d5 2 T -1 3 , we have Reg T ≤ Õ (d 8 H 6 |A|T 2 3 log(|Φ|)))E Proof of Theorem 4.1 (Model-Free, Banfit Feedback)We start by introducting some notation. We let I (k) denote the rounds in the k-th epoch:EQUATIONwhere T 0 is as in Line 1 of Algorithm 3. Throughout the analysis, we condition on the eventEQUATION)where E cov is as in Lemma G.1. Further, for any k ∈ [K], let ρ (k) be the distribution of the random policy:EQUATION) with ζ ∼ Ber(ν), h ∼ unif([H]), and π ∼ unif(Ψ cov h ). We start our analysis by applying the performance difference lemma.Applying the performance difference lemma. For any k ∈ [K], t ∈ I (k) , and ρ (k) as just defined, we haveE π∼ρ (k) E [V π 1 (x 1 ; ℓ t )] -V π ⋆ 1 (x 1 ; ℓ t ) = (1 -ν) ⋅ (V π(k) 1 (x 1 ; ℓ t ) -V π ⋆ 1 (x 1 ; ℓ t )) + ν Hd ∑ h∈[H] ∑ π∈Ψ cov h (V π○ h πunif○ h+1 π(k) 1 (x 1 ; ℓ t ) -V π ⋆ 1 (x 1 ; ℓ t )) , ≤ (1 -ν) ⋅ H ∑ h=1 E π ⋆ [ ∑ a∈A (π (k) h (a | x h ) -π ⋆ h (a | x h )) ⋅ Q π(k) h (x h , a; ℓ t )] + Hν, = (1 -ν) ⋅ H ∑ h=1 E π ⋆ [ ∑ a∈A (π (k) h (a | x h ) -π ⋆ h (a | x h )) ⋅ Q(k) h (x h , a)] + Hν + (1 -ν) ⋅ H ∑ h=1 E π ⋆ [ ∑ a∈A π(k) h (a | x h ) ⋅ (Q π(k) h (x h , a; ℓ t ) - Q(k) h (x h , a))] + (1 -ν) ⋅ H ∑ h=1 E π ⋆ [ ∑ a∈A π ⋆ h (a | x h ) ⋅ ( Q(k) h (x h , a) -Q π(k) h (x h , a; ℓ t ))] .Thus, by the triangle inequality, we haveEQUATION)We start by bound the first term in the right-hand side of (48) (the regret term).h (⋅ | x) ∶= (1 -γ/T ) ⋅ π ⋆ h (⋅ | x) + γπ unif (⋅ | x)/T for all x, where γ is as in Algorithm 3. We have that | Q(k) h (x, a)| = | φ(k) h (x, a) ⊺ θ(k) h | ≤ H √ d (since θ(k) h ∈ B d (H √ d) and ∥ φk h (x, a)∥ ≤ 1). By applying Lemma I.5, we have that for any η ≤ 1 H √ d and x ∈ X :EQUATIONE.2 Bounding the Bias TermFix epoch k ∈ [K], round t ∈ I (k) , layer h ∈ [2 .. H], and π ′ ∈ Π. Further, let X h,ε ∶= {x ∈ X ∶ max π∈Π d π h (x) ≥ ε ⋅ ∥µ ⋆ h (x)∥} (50)be the set of ε-reachable states. With this notation, we now bound the bias term in (48); we have∑ t∈I (k) E π ⋆ [ ∑ a∈A π ′ h (a | x h ) ⋅ (Q π(k) h (x h , a; ℓ t ) - Q(k) h (x h , a))] ≤ ∑ t∈I (k) E π ⋆ [I{x h / ∈ X h,ε } ∑ a∈A π ′ h (a | x h ) ⋅ (Q π(k) h (x h , a; ℓ t ) - Q(k) h (x h , a))] + ∑ t∈I (k) E π ⋆ [I{x h ∈ X h,ε } ∑ a∈A π ′ h (a | x h ) ⋅ (Q π(k) h (x h , a; ℓ t ) - Q(k) h (x h , a))] ,and so by Lemma I.1,≤ ∑ t∈I (k) E π ⋆ [I{x h ∈ X h,ε } ∑ a∈A π ′ h (a | x h ) ⋅ (Q π(k) h (x h , a; ℓ t ) - Q(k) h (x h , a))] + 2N reg Hd 2 ε, = N reg ⋅ E π ⋆ ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ I{x h ∈ X h,ε } ∑ a∈A π ′ h (a | x h ) ⋅ ⎛ ⎝ 1 N reg ∑ t∈I (k) Q π(k) h (x h , a; ℓ t ) - Q(k) h (x h , a) ⎞ ⎠ ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ + 2N reg Hd 2 ε.Thus, by lettingEQUATIONand using Jensen's inequality (twice), we get∑ t∈I (k) E π ⋆ [ ∑ a∈A π ′ h (a | x h ) ⋅ (Q π(k) h (x h , a; ℓ t ) - Q(k) h (x h , a))] ≤ N reg ⋅ E π ⋆ [I{x h ∈ X h,ε } ∑ a∈A π ′ h (a | x h ) ⋅ |Q π(k) h (x h , a) - Q(k) h (x h , a)|] + 2N reg Hd 2 ε, ≤ N reg ⋅ E π ⋆ [I{x h ∈ X h,ε } ∑ a∈A π ′ h (a | x h ) ⋅ (Q π(k) h (x h , a) - Q(k) h (x h , a)) 2 ] + 2N reg Hd 2 ε, ≤ N reg ⋅ E π ⋆ [I{x h ∈ X h,ε } ⋅ max a∈A (Q π(k) h (x h , a) - Q(k) h (x h , a)) 2 ] + 2N reg Hd 2 ε,and now by the fact that Ψ cov h is an ( 1 8Ad , ε) policy cover for layer h (see Lemma G.1 and Definition 4.1):EQUATION)Next, we bound the regression error term in the right-hand side of ( 52).Lemma E.1. Let δ ∈ (0, 1) and ν ∈ (0, 1/4) be given. There is an event E reg of probability at least 1 -2δ under whichEQUATION)Proof. Fix δ ∈ (0, 1), h ∈ [H] and k ∈ [K], and let (x t h , a t h , ζ t , h t ) be as in Algorithm 3. With this, defineEQUATIONand note that (x t h , a t h , I t h ) t∈I (k) are identically and independently distributed. Further, for t ∈ I(k) and π ∈ Π, let θ t,π h ∈ B d (H √ d) be such that ∀(x, a) ∈ X × A, Q π h (x, a; ℓ t ) = ϕ ⋆ h (x, a) ⊺ θ π,t h .Such a θ π,t h is guaranteed to exist by the low-rank MDP structure (Assumption 2.1) and Assumption 2.2. With this, note that for Q π(k) h as in ( 51), we haveEQUATION)For the rest of this proof, we let F be the function classF ∶= {f ∶ (x, a) ↦ ϕ h (x, a) ⊺ θ | θ ∈ C ∪ {θ (k) h }, ϕ ∈ Φ},where C is a minimalEQUATIONandEQUATIONEQUATIONwhere ∇ denotes directional derivative and∥ f -f ⋆ ∥ 2 ∶= ∑ t∈I (k) I t h ⋅ ( f (x t h , a t h ) -f ⋆ (x t h , a t h )) 2 .Rearranging (58) and using that fEQUATIONWe now bound the right-hand side of (59). For any h ∈ [H], k ∈ [K] and any f , f ⋆ ∈ F, we apply Lemma I.2 with• F i = σ({(x j h , a j h , ε j h , ζ j ) ∶ j ≤ t i })where t i ∶= (k -1) ⋅ N reg + i; • The random variable w i set as the differencew i = I{ζ ti = 0 or h ti ≤ h} ⋅ ε ti h ⋅ ( f (x ti h , a ti h ) -f ⋆ (x ti h , a ti h )) -E [I{ζ ti = 0 or h ti ≤ h} ⋅ ε ti h ⋅ ( f (x ti h , a ti h ) -f ⋆ (x ti h , a ti h )) | F i-1 ] where t i ∶= (k -1) ⋅ N reg + i; • n = N reg = |I (k) |.• R = 4H 2 ; and• λ = 1/(16H 2 );to get that there is an event E of porbability at least 1δ under whichEQUATIONwhereE t [⋅] is defined as E [⋅ | F t-1] and the last step uses that |ε t h | ≤ 2H, for all t ∈ I (k) . For the rest of the proof, we condition on E and to simplify notation letEQUATIONUsing the expression of ε t h in (56), we have ∑EQUATIONNow, since I t h = I{ζ t = 0 or h t ≤ h}, we haveE t [ H ∑ l=h ℓ t l (x t l , a t l ) | x t h , a t h , I t h = 1] = Q π(k) h (x t h , a t h ; ℓ t ).Plugging this into (62) and using the law of total expectation, we haveEQUATIONOn the other hand, since (x t h , a t h , I t h ) t∈I (k) are i.i.d. and ℓ t is chosen by an oblivious adversary, we have∀t ∈ I (k) , E t [I t h ⋅ Q π(k) h (x t h , a t h ; ℓ t ) ⋅ ∆ t h ] = 1 N reg ∑ τ ∈I (k) E τ [I τ h ⋅ Q π(k) h (x τ h , a τ h ; ℓ t ) ⋅ ∆ τ h ] .Plugging this into (63) shows thatEQUATIONCombining this with ( 60) and ( 59), we get thatEQUATIONNow, since (x t h , a t h , I t h ) t∈I (k) are i.i.d., we have by Lemma I.3 that there is an event E ′ of probability at least 1δ under which we haveEQUATIONCombining this with (65) and rearranging, we get that under E reg ∶= E ∩ E ′ :EQUATIONOn the other hand, we have that for all t ∈ I (k) :EQUATIONPlugging this into (67) and using the expressions of f and f ⋆ , we get∑ π∈Ψ h E π○ h πunif [( φ(k) h (x h , a h ) ⊺ θ(k) h -Q π(k) h (x h , a h )) 2 ] ≤ 40H 3 d log(2|F|/δ) νN reg .By combining (48), ( 52), (53), and (49), we have that under the event E ∶= E cov ∩ E reg (where E cov and E reg are as in Lemma G.1 and Lemma E.1, respectively):EQUATIONThus, plugging in the expression of T 0 from Algorithm 3, and ignoring polynormal factors d, A, H, log(|Φ|ε -1 δ -1 ), we get thatReg T ≺ 1 ε 2 + T ε + T ν + N reg ⋅ √ 8A 2 d ⋅ ε 2 reg + 2N reg Hdε + N reg η + ηT, ≺ T 2/3 + νT + T ⋅ √ 8A 2 d ⋅ ε 2 reg + √ T N reg , (by setting ε = T -1/3 and η = (N reg /T ) 1/2 ) = T 2/3 + νT + T ⋅ √ 1 νN reg + √ T N reg , (used the expression of ε 2 reg in (53)) ≺ T 2/3 + νT + √ T ⋅ ( T ν ) 1/4, (by settingEQUATIONwhere the last step follows by setting ν = T -1/5 .F Proof of Theorem 4.2 (Model-Free, Bandit Feedback, Adaptive Adversary)We let I (k) denote the rounds in the kth epoch:EQUATIONwhere T 0 is as in Line 8 of Algorithm 4. Throughout the analysis, we condition on the eventEQUATIONwhere E cov , E rep+span , and E freed are as in Lemma G.1, Corollary F.1, and Lemma F.3, respectively.We start our analysis by applying the performance difference lemma.Applying the performance difference lemma. For any k ∈ [K], t ∈ I (k) , and let ρ (k) be the distribution of the random policy:EQUATIONwith ζ t ∼ Ber(ν), h t ∼ unif([H]), and π t ∼ unif(Ψ span h t ). E π∼ρ (k) E [V π 1 (x 1 ; H t-1 )] -V π ⋆ 1 (x 1 ; H t-1 ) = (1 -ν) ⋅ (V π(k) 1 (x 1 ; H t-1 ) -V π ⋆ 1 (x 1 ; H t-1 )) + ν Hd ∑ h∈[H] ∑ π∈Ψ cov h (V π○ h+1 π(k) 1 (x 1 ; H t-1 ) -V π ⋆ 1 (x 1 ; H t-1 )) , = (1 -ν) ⋅ H ∑ h=1 E π ⋆ [ ∑ a∈A (π (k) h (a | x h ) -π ⋆ h (a | x h )) ⋅ Q π(k) h (x h , a; H t-1 ) | H t-1 ] + HN reg ν, = (1 -ν) ⋅ H ∑ h=1 E π ⋆ [ ∑ a∈A (π (k) h (a | x h ) -π ⋆ h (a | x h )) ⋅ Q(k) h (x h , a) | H t-1 ] + HN reg ν + (1 -ν) ⋅ H ∑ h=1 E π ⋆ [ ∑ a∈A π(k) h (a | x h ) ⋅ (Q π(k) h (x h , a; H t-1 ) - Q(k) h (x h , a)) | H t-1 ] + (1 -ν) ⋅ H ∑ h=1 E π ⋆ [ ∑ a∈A π ⋆ h (a | x h ) ⋅ ( Q(k) h (x h , a) -Q π(k) h (x h , a; H t-1 )) | H t-1 ] .Thus, by the triangle inequality, we haveEQUATIONWe start by bounding the first term on the right-hand side of (74) (the regret term).Fix h ∈ [H] and define π⋆ h (⋅ | x) ∶= (1 -γ/T ) ⋅ π ⋆ h (⋅ | x) + γπ unif (⋅ | x)/T for all x, where γ is as in Algorithm 4. We have that | Q(k) h (x, a)| = | φrep h (x, a) ⊺ θ(k) h | ≤ 8Hd 2 (since θ(k) h ∈ B 2d (4Hd 2 ) and ∥ φrep h (x, a)∥ ≤ ∥ϕ loss h (x, a)∥ + ∥ϕ rep h (x, a)∥ ≤ 2). By applying I.5, we have that for any η ≤ 1 8Hd 2 and x ∈ X :EQUATIONTo bound the bias term (second term in ( 74)), we make use of the following result.Lemma F.1. For t ∈ [T ], h ∈ [H], and π ∈ Π, there exists θt,π h ∈ B 2d (H √ d) such that for all (x, a) ∈ X × A and historyEQUATION) Proof. Fix t ∈ [T ], h ∈ [H],and π ∈ Π. By the low-rank MDP structure and the normalizing assumption on µ ⋆ h in Assumption 2.1, there existsEQUATIONNow, with g t h as in Assumption 4.2, ( 15) and ( 77) implies that θt,π h ∶= [g t h , w t,π h+1 ] ∈ R 2d (where [⋅, ⋅] denotes the vertical stacking of vectors) satisfies the desired property.Fix epoch k ∈ [K], round t ∈ I (k) , layer h ∈ [2 .. H], and π ′ ∈ Π. By Lemma F.1, there exists θt,π (k) h ∈ B 2d (Hd 1/2 ) such that for all (x, a) ∈ X × A, Q π(k) h+1 (x, a; H t-1 ) = φ⋆ h+1 (x, a) ⊺ θt,π (k) h+1 .With this, let k) h+1 ; note that this function belongs to the function class F h+1 in Algorithm 4. With this, we defineEQUATIONEQUATIONwhereg t h ∈ B d (1) is such that ℓ h (x, a; H t-1 ) = ϕ loss h (x, a) ⊺ g t h .With this notation, we now bound the bias term in Eq. ( 74): we have∑ t∈I (k) E π ⋆ [ ∑ a∈A π ′ h (a | x h ) ⋅ (Q π(k) h (x h , a; H t-1 ) - Q(k) h (x h , a)) | H t-1 ] ≤ ∑ t∈I (k) E π ⋆ [ ∑ a∈A π ′ h (a | x h ) ⋅ ( φrep h (x h , a) ⊺ θt,π (k) h - Q(k) h (x h , a)) | H t-1 ] + ∑ t∈I (k) E π ⋆ [ ∑ a∈A π ′ h (a | x h ) ⋅ (Q π(k) h (x h , a; H t-1 ) -φrep h (x h , a) ⊺ θt,π (k) h ) | H t-1 ] ,and by Corollary F.1 (in particular (92))≤ ∑ t∈I (k) E π ⋆ [ ∑ a∈A π ′ h (a | x h ) ⋅ ( φrep h (x h , a) ⊺ θt,π (k) h -φrep h (x h , a) ⊺ θ(k) h ) | H t-1 ] + N reg ⋅ ε rep ,and by Corollary F.1 again (in particular (93)) and the triangle inequalityEQUATIONwhere the last inequality follows by Corollary F.1 (in particular ( 92)).Next, we bound the estimation error term in the right-hand side of (79).By Lemma F.3 (Freedman's inequality), we have that for all π ∈ Ψ span h and θ ∈ B 2d (4Hd 2 ):EQUATION)On the other hand, we haveEQUATIONNow, by Corollary F.1 (in particular (92)) and the triangle inequality, we haveEQUATIONThus, by combining ( 80), (81), and (82), we have∑ π∈Ψ span h ∑ t∈I (k) I{h t = h, π t = π, ζ t = 1} ⋅ ( φrep h (x t h , a t h ) ⊺ θ - H ∑ s=h ℓ t s ) ≤ dN reg ⋅ ε freed + νN reg ε rep H + ν Hd ∑ π∈Ψ span h ∑ t∈I (k) E π [ φrep h (x h , a h ) ⊺ ] ⎛ ⎝ N reg ⋅ θ -∑ t∈I (k) θt,π (k) h ⎞ ⎠ .h is the minimizer over B 2d (4Hd 2 ) of the left-hand side, and the right-hand side evaluted todN reg ⋅ ε freed + νNregεrep H with θ = 1 Nreg ∑ t∈I (k) θt,π (k) h ∈ B 2d (4Hd 2 ), we have that ∑ π∈Ψ span h ∑ t∈I (k) I{h t = h, π t = π, ζ t = 1} ⋅ ( φrep h (x t h , a t h ) ⊺ θ(k) h - H ∑ s=h ℓ t s ) ≤ dN reg ⋅ ε freed + νN reg ε rep H .Now, combining this with ( 80) and ( 81) with θ = θ(k) k , we get thatEQUATIONBy combining ( 74), ( 79), ( 83), and (75), we have that under the event E in (72):EQUATIONThus, plugging in the expression of T 0 , ε freed , and (ε span , ε rep ) from Algorithm 4, Lemma F.3, and Corollary F.1, respectively, and ignoring polynormal factors d, A, H, log(|Φ|ε -1 δ -1 ), we get thatEQUATION)where the last step follows by setting N reg = T 2/3 .Algorithm 7 Spanner: Computing an Approximate Spanner.Require: Layer h, feature classes Φ, policy covers Ψ 1∶H , feature map φ ∶ X × A → R 2d , # of episodes n.EQUATION) 3: Set G h = {(x, a) ↦ φh (x, a) ⊺ θ ∶ θ ∈ B 2d (1)}, and for t ∈ [h -1], set G t = G. 4: For each t ∈ [h], set P t = unif(Ψ t ). 5: For θ ∈ R 2d , define LinOpt(θ) = PSDP(h, r 1∶h (⋅, ⋅; θ), G 1∶h , P 1∶h , n) ∈ Π.// PSDP as in Mhammedi et al. (2023) .6: For θ ∈ R 2d and π ∈ Π, define LinEst(π) = EstVec(h, φh , π, n). // EstVec as in Mhammedi et al. (2023) . ).// RobustSpanner as in Mhammedi et al. (2023) .8: Return: Policy cover {π 1 , . . . , π 2d }.Lemma F.2 (Spanner Guarantee). Let ε, α, δ ∈ (0, 1), h ∈ [H], n ≥ 1, and φh ∶ X × A → R 2d be given. Suppose that Assumption 2.1 and Assumption 4.1 hold, and let Ψ 1∶h be such that for all s ∈ [h], Ψ s is an (α, ε)-policy cover for layer s with |Ψ s | = 2d. Then, the outputΨ span h = Spanner(h, Φ, Ψ 1∶h , φh , n) (Algorithm 7) is such that |Ψ span h | = 2dand, with probability at least 1δ, for all π ′ ∈ Π, there existEQUATIONwhereEQUATION)where c > 0 is a large enough absolute constant. Furthermore, the number of episodes T span (n) used by the call to Spanner is at most Õ(H 2 d 2 n).Proof. To derive the desired bound, we will use the generic guarantee of RobustSpanner from (Mhammedi et al., 2023, Proposition E.1) . To invoke this result, we first need to 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 ε ′ ∈ (0, 1) such that (with high probability) for any θ ∈ R 2d ∖ {0} and π ∈ Π, the outputs πθ ∶= LinOpt( θ/∥ θ∥) and φπ ∶= LinEst(π) satisfy supπ∈Π θ⊺ E π [ φh (x h , a h )] ≤ θ⊺ E πθ [ φh (x h , a h )] + ε ′ ⋅ ∥ θ∥ and ∥ φπ -E π [ φh (x h , a h )]∥ ≤ ε ′ .(90) With this, we can apply (Mhammedi et al., 2023, Proposition E.1) to get that the outputEQUATION)Since LinOpt is based on PSDP as in Line 5 of Algorithm 7 and Ψ 1 , . . . , Ψ h are (α, ε)-policy covers for layers 1 to h, respectively, (Mhammedi et al., 2023, Corollary H.1) implies that there is an event E PSDP of probability at least 1δ/2 under which for any θ ∈ R d ∖ {0}, the output πθ = LinOpt( θ) satisfies supπ∈Π θ⊺ E π [ φh (x h , a h )] ≤ θ⊺ E πθ [ φh (x h , a h )] + ∥ θ∥ ⋅ ⎛ ⎜ ⎝ cH 2 √ dA ⋅ (d log(2n √ dH) + log(n|Φ|/δ)) αn + H 2 d 3/2 ε ⎞ ⎟ ⎠ ,for a large enough absolute constant c > 0. On the other hand, since LinEst is based on EstVec as in Line 6, (Mhammedi et al., 2023, Lemma G.3 ) implies that there is an event E EstVec of probability at least 1δ/2 under which for all π ∈ Π, the output φπ ∶= LinEst(π) satisfies∥ φπ -E π [ φh (x h , a h )]∥ ≤ c ⋅ √ log(2/δ) n ,for a large enough absolute constant c > 0. Therefore, under E PSDP ∩ E EstVec , LinOpt and LinEst satisfy (90) withε ′ ∶= cH 2 √ dA ⋅ (d log(2n √ dH) + log(n|Φ|/δ)) αn + H 2 d 3/2 ε.Therefore, by (Mhammedi et al., 2023, Proposition) and the fact that d√ A log(ndH|Φ|/δ) αn ≤ ε ′ , the output π 1∶2d = RobustSpanner ⎛ ⎝ LinOpt(⋅), LinEst(⋅), 2, d √ A log(ndH|Φ|/δ) αn ⎞ ⎠is such that for all π ∈ Π, there exist β 1 , . . . ,β 2d ∈ [-2, 2] satisfying ∥E π [ φh (x h , a h )] - 2d ∑ i=1 β i ⋅ E πi [ φh (x h , a h )]∥ ≤ ε span (n, α, δ),where ε span (n, α, δ) is as in (89).Bounding the number of episodes By (Mhammedi et al., 2023 • For f ∈ F h+1 , with F h+1 as in (97), there exists w f h+1 ∈ B d (3d 3/2 ) such that:EQUATION)Proof. From Algorithm 4, we haveϕ rep h = RepLearn(h, F h+1 , Φ, unif(Ψ cov h ), T rep ) and Ψ span h = Spanner(h, Φ, Ψ cov 1∶h , φrep h , T span ), whereEQUATIONand α ∶= 1 8Ad . By Lemma G.1, there is an event E cov of probability at least 1δ/4 under which, for allh ∈ [H], Ψ cov h is an (α, ε)-policy cover for layer h with |Ψ cov h | = d.In what follows, we condition on E cov . By Lemma G.2 and Lemma F.2, there are events E rep and E span of probability at least 1δ/4 each such that under E rep ∩ E span (92) and ( 93) hold; this follows from ( 98) and ( 88) and the choices of T rep and T span in (94). Finally, by the union bound, we have P[E cov ∩ E rep ∩ E span ] ≥ 1δ which completes the proof.Lemma F.3. Let K, N reg , φrep 1∶H , and I (k) be as in Algorithm 4 for k ∈ [K]. There is an event E freed of probability at least 1δ/4 under which for all θ∈ B 2d (4Hd 2 ), h ∈ [H], k ∈ [K], and π ∈ Ψ span h : 1 N reg ∑ t∈I (k) I{h t = h, π t = π, ζ t = 1} ⋅ ( φrep h (x t h , a t h ) ⊺ θ - H ∑ s=h ℓ t s ) -∑ t∈I (k) E [I{h t = h, π t = π, ζ t = 1} ⋅ ( φrep h (x t h , a t h ) ⊺ θ - H ∑ s=h ℓ t s ) | H t-1 ] ≤ ε freed ∶= 4Hd 2 ν log(dKHN reg /δ) N reg ,where the random variables h t , ζ t , π t , and H t-1 are as in Algorithm 7.Proof. Fix θ ∈ B 2d (4d 2 ), h ∈ [H], k ∈ [K],and π ∈ Ψ span h . We apply Lemma I.2 (Freedman's inequality) with • R = 4Hd 2 ;• n = N reg ;• The random variable w i set as the differenceEQUATIONwhere t i ∶= (k -1) ⋅ N reg + i;• The filtration F i set as the σ-algebra σ(H ti-1 );• The variance term V n has the following upper boundEQUATION)Let C be a minimal (dHN reg ) -1 -cover of B 2d (4Hd 2 ) with respect to the ∥ ⋅ ∥ distance. Under the eventE freed ∶= ⋂ h∈[H],k∈[K],π∈Ψ span h , θ∈B 2d (4Hd 2 ) E freed h,k,π ( θ),Eq. ( 96) holds for all h ∈ [H], k ∈ [K], and θ ∈ B 2d (4Hd 2 ) up to an additive O(1/N reg ) error. By the union bound, we have P[E freed ] ≥ 1δ/4 which completes the proof.In this section, we present guarantees for VoX, RepLearn, and RobustSpanner which we need in the analysis of our oracle efficient algorithm. The results are based on (Mhammedi et al., 2023) .The following result is a restatement of (Mhammedi et al., 2023, Theorem 12) .Lemma G.1 (VoX Guarantee). Let ε, δ ∈ (0, 1) be given. Suppose Assumption 2.1 and Assumption 4.1 hold. Then, there is an event E cov of probability at least 1δ under which the outputΨ cov 1∶H = VoX(Φ, ε, δ) is such that for all h ∈ [H]: • Ψ cov h is a ( 1 8Ad , ε)-policy cover for layer h; • |Ψ cov h | ≤ d.Furthermore, the number of episodes T cov (ε) used by the call to VoX is bounded by Õ(Ad 13 H 6 log(Φ/δ))/ε 2 .Lemma G.2 (Representation Learning Guarantee). Let ε, α, δ ∈ (0, 1), h ∈ [H -1], and n ≥ 1 be given and define the function classEQUATIONFurther, let Ψ be an (α, ε)-policy cover for layer h with |Ψ| = d, and suppose Assumption 2.1 and Assumption 4.1 hold. Then, with probability at least 1δ, the outputEQUATIONwhere c > 0 is a large enough absolute constant. Furthermore, the number of episodes T rep (ε) used by the call to RepLearn is equal to n.Proof. By (Mhammedi et al., 2023, Theorem F.1) and the assumption that |Ψ| = d, there is an event E of probability at least 1δ/2 under which ϕ rep h satisfies:EQUATIONwhere c is a large enough absolute constant. We use this to show (98) . In what follows, we condition on E. Fix π ∈ Π and f ∈ G and let w f h+1 be the vector w ∈ B d (3d 3/2 ) achieving the infimum in (99) for the given choice of f . Let X h,ε be the set of ε-reachable states at layer h as defined in (50). With this this, we have for allEQUATIONwhere the last inequality follows by Lemma I.1.We now bound the first term on the right-hand side of (100). By Jensen's inequality, we have|E π [I{x h ∈ X h,ε } ⋅ (ϕ rep h (x h , a h ) ⊺ w f h+1 -E[f (x h+1 ) | x h , a h ])]| ≤ √ E π [I{x h ∈ X h,ε } ⋅ (ϕ rep h (x h , a h ) ⊺ w f h+1 -E[f (x h+1 ) | x h , a h ]) 2 ],and so using that Ψ is a (α, ε ′ )-policy cover (see Definition 4.1), we have≤ √ α -1 ⋅ max π ′ ∈Ψ E π ′ [(ϕ rep h (x h , a h ) ⊺ w f h+1 -E[f (x h+1 ) | x h , a h ]) 2 ], ≤ √ c ⋅ AHd 5 log(|Φ|/δ) αn ,where the last step follows by (99). Combining this with (100) yields ( 98).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 a lower bound depending polynomially on 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 T with unstructured losses such that any agent suffers at least regret of Ω( √ SAT ).Proof. We assume 4S < √ T . The construction is an H = 1 (i.e. contextual bandit) MDP with uniform initial distribution over states. Each state is a copy of an A-armed bandit problem with Bernoulli losses with mean 1 2 , and one randomly chosen optimal arm with mean 1 2 -∆. Following the standard lower bound construction for bandits (Lattimore and Szepesvári, 2020) , there exists ∆ = Θ(1/ √ T AS) such that the the regret of playing any individual bandit problem for N ≤ 2T /S rounds is lower bounded by Ω(N ∆). Let denote N (s) the number of time the agent receives the initial state s, then any agent suffers a regret lower bound in our MDP ofΩ ( S ∑ s=1 E[min{N (s), 2T /S}]) .N (s) is the sum of T Bernoulli random variables with mean 1/S. We have by Hoeffding's inequalityP[N (s) > T /S + x] ≤ exp(-2x 2 /T ) .This allows to upper bound the tail E[N (s)I(N (s) > 2T /S)] ≤ ∫ ∞ T /S x(2x/T exp(-2x 2 /T )) dx ≤ ∫ ∞ T /S 4 exp(x/ √ T -2x 2 /T ) dx ( 1 2 (x/ √ T ) 2 < exp(x/ √ T )) ≤ ∫ ∞ T /S 4 exp(-x/ √ T ) dx (x ≥ T /S > 4 √ T ) = 4 √ T exp(- √ T /S) ≤ 4 √ T exp(-4) ≤ T /(2S) .Lemma I.1. Let ε, B > 0 and h ∈ [2 .. H] be given. For any function f ∶ X → [-B, B] and π ∈ Π, we haveEQUATIONEQUATIONdenotes the set of states that are ε-reachable at layer h.. Fix f ∶ X → [-B, B] and π ∈ Π. Using the definition of X h,ε in (102), we have that x / ∈ X h,ε only if d π h (x) < ε∥µ ⋆ h (x)∥.Using this, we haveEQUATIONwhere the last step follows by the normalizing assumption on µ ⋆ (see Assumption 2.1) and (Mhammedi et al., 2023, Lemma I.3 ).Lemma I.2. Let R > 0 be given and let w 1 , . . . w n be a sequence of real-valued random variables adapted to filtration F 1 , ⋯, F n . Assume that for all i ∈[n], w i ≤ R and E[w i | F i-1 ] = 0. Define S n ∶= ∑ n i=1 w i and V n ∶= ∑ n i=1 E[(w i ) 2 | F i-1 ].Then, for any δ ∈ (0, 1) and λ ∈ [0, 1/R], with probability at least 1δ,EQUATIONWe now state two helpful results from Mhammedi et al. (2024b) without a proof.Lemma I.3. Let B > 0 and n ∈ N be given. abstract set. Further, let Q ⊆ {g ∶ X × A → [0, B]} be a finite function class and (x 1 , a 1 , ε 1 ), . . . , (x n , a n , ε n ) be a sequence of i.i.d. random variables in X × A × R. Then, for any δ ∈ (0, 1), with probability at least 1δ, we haveEQUATIONwhere∥g∥ 2 ∶= ∑ i∈[n] E[g(x i , a i ) 2 | F i-1 ] and ∥g∥ 2 n ∶= ∑ n i=1 g(x i , a i ) 2 . Lemma I.4 (Generic regression guarantee). Let B > 0, n ∈ N, and f ⋆ ∶ X × A → [0, B] be given. Further, let F ⊆ {f ∶ X × A → [0, B]} be a finite function class and (x 1 , a 1 , ε 1 ), . . . , (x n , a n , ε n ) be a sequence of i.i.d. random variables in X × A × R. Suppose that • f ⋆ ∈ F; • z i = f ⋆ (x i , a i ) + ε i + b i , for all i ∈ [n];• b 1 , . . . , b n ∈ R (not necessarily i.i.d.);• ε i ∈ [-B, B], for all i ∈ [n]; and • E[ε i | x i , a i ] = 0.Then, for f ∈ argmin f ∈F ∑ n i=1 (f (x i , a i )z i ) 2 and any δ ∈ (0, 1), with probability at least 1δ/2,EQUATION)where ∥ ff ⋆ ∥ 2 n ∶= ∑ n i=1 ( f (x i , a i )f ⋆ (x i , a i )) 2 . Proof. Fix δ ∈ (0, 1) and let Ln (f ) ∶= ∑ n i=1 (f (x i , a i )z i ) 2 , for f ∈ F, and note that since f ∈ argmin f ∈F Ln (f ), we haveEQUATIONwhere ∇ denotes directional derivative. Rearranging, we get thatEQUATIONEQUATIONThus, rearranging, we getEQUATION)We now bound the first term on the right-hand side of (110). For this, we apply Lemma I.2 with w i = ε i ⋅ ( f (x i , a i )f ⋆ (x i , a i )), R = B 2 , λ = 1/(8B 2 ), and F i = ∅, and use 1. the union bound over f ∈ F; and 2. the facts that E[ε i | x i , a i ] = 0, to get that with probability at least 1δ/2,EQUATIONCombining this with (110), we get that with probability at least 1δ/2,EQUATION)This completes the proof.The following is the standard guarantee of exponential weights (e.g. Lemma F.4 of Sherman et al. (2023b) ).Lemma I.5 (Exponential Weights). Given a sequence of loss functions {g t } T t=1 over a decision set Π, {p t } T t=1 is a distribution sequence with p t ∈ ∆ (Π) , ∀t ∈ [T ] such thatp t+1 (π) ∝ exp (-η T ∑ t=1 g t (π)) .If p 1 is a uniform distribution over |Π| and ηg t (π) ≥ -1 for all t ∈ [T ] and π ∈ Π. Then The following is standard simulation lemma which is first proposed by Abbeel and Ng (2005) .Lemma I.6 (Simulation Lemma). For two finite-horizon MDPs M = {X , A, ℓ, { Ph } H h=1 } and M = {X , A, ℓ, {P h } H h=1 } with horizon H and ∥ℓ∥ ∞ ≤ 1. Let the corresponding value function be V π h (x; ℓ) and V π h (x; ℓ) for step h ∈ [H]. For any policy π ∶ X → ∆(A), we have| V π 1 (x 1 ; ℓ) -V π 1 (x 1 ; ℓ)| ≤ H H ∑ h=1 E x,a∼d π h [∥ Ph (⋅ | x, a) -P h (⋅ | x, a)∥ 1 ] .The following is the standard performance difference lemma which is first proposed by Kakade and Langford (2002) .Lemma I.7 (Performance Difference Lemma). For a finite-horizon MDPs M = {X , A, ℓ, {P h } H h=1 } starting at x 1 , and two policies π, π ′ ∶ X → ∆(A), we haveV π ′ 1 (x 1 ; ℓ) -V π 1 (x 1 ; ℓ) = H ∑ h=1 E x∼d π h [ ∑ a∈A (π ′ h (a|x) -π h (a|x)) Q π ′ h (x, a; ℓ)]• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a 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.• If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.• Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.• While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (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.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.We assume that X is countable only to simplify the presentation. Our results can easily be extended to a continuous state space with an appropriate measure-theoretic treatment (see e.g.Mhammedi et al. (2023)).The setting where we assume access to function classes that realize both ϕ ⋆ 1∶H and µ ⋆ 1∶H is called model-based because it allows one to model the transition probabilities, thanks to the low-rank structure in (4).log(|Φ|))). 


Decision: 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.

Reviews: review: paper_summary: paper_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:

1.  **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.
    
2. **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.
    
3.  **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}$.
strength_weakness: strength_weakness: -   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.
    
-   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.
questions: 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.
- Is there a specific reason to use log-barrier and not negative entropy regularization in algorithm 2?
limitations: limitations: As far as I'm concerned, the authors address most of their limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1.	The 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].

[1] Kong et al. Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimization. TMLR, 24.

[2] Liu et al. Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback. ICLR, 24.
questions: questions: 1.	In 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?
2.	Intuitively, what is the reason that Algorithm 2 still needs to operate in epochs after the phase of reward-free exploration?
limitations: limitations: Not applicable.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
questions: 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: limitations: NA
paper_summary: paper_summary: This paper studies online learning in low-rank MDPs with adversarial losses (having linear structure), and derives a set of regret guarantees:

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

2. 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].

3. 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].
strength_weakness: strength_weakness: 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):

1. 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?

2. 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)?

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

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

5. 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?

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

7. In line 10 of algorithm 1, “Define $\sum_h^t = \sum$”, anything missing before the $=$?

8. Sketched proofs in the main body for deriving regret bounds would be very helpful, but I fully understand it due to the page limit.

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

I 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.
questions: questions: Questions here are mainly for curiosity and will not affect my recommendation/rating much.

1. 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?

2. 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?

References

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

[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).

[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: 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".

====== update after author-reviewer discussion ======

During 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

Comments: title: Use of the negative entropy vs the log-barrier
Thank you for your response.
Statement of Theorem 4.1
Regarding Q2 and Thm. 4.1
comment: Thanks for your replies. I have no further questions.
Thank you for your comments. After a more careful inspection, we found that using the negative entropy regularizer would lead to a better dependence in $A$ while keeping the dependence in $T$ unchanged compared with the log-barrier regularizer. As mentioned in the rebuttal, using the negative entropy regularizer requires $\eta |\widehat{Q}\_h^{(k)}(x, a)|\le 1$ for any $k,h,x,a$. This prevents one from choosing $\eta$ optimally for the standard loss estimator in the linear MDP setting (due to the large magnitude of the estimator). However, the estimator we use for the low-rank setting in Algorithm 2 has the property that $\widehat{Q}\_h^{(k)}(x,a) \le H\sqrt{d}$ for any $x,a,k,h$. This implies that the optimal choice of $\eta$ in our setting (which satisfies $\eta=1/\text{poly}(T)$) is well within the range implied by the constraint $\eta |\widehat{Q}\_h^{(k)}(x, a)|\le 1$. The same applies in the setting of Algorithm 3 where $\widehat{Q}\_h^{(k)}(x,a) \le 8Hd^2$. 


We would also like to correct a typo in our current proof. In the current analysis of the log-barrier (Lines 495 and 554), the penalty term is missing a factor of $A$. According to Lemma G.1, the correct penalty term should be $\frac{N\_{reg} A \log(T/\gamma)}{\eta}$ instead of $\frac{N\_{reg} \log(T/\gamma)}{\eta}$. On the other hand, for negative entropy, the penalty term is $\frac{N\_{reg} \log(A)}{\eta}$ from Lemma G.6. Thus, since the stability terms for both the log-barrier and the negative entropy are the same, this implies that the correct regret for log-barrier has a slightly worse dependence on $A$ compared with the negative entropy. We will change our algorithm and analysis to negative entropy in the revision (our final regret bounds will remain the same up log factors in $A$).
Dear Reviewers,

The deadline for the reviewer-author discussion period is approaching. Thank you for already providing responses to the rebuttal. If you have any additional questions, please discuss them with the authors at your earliest convenience.

Best wishes, AC
Thanks for your feedback. Could you please elaborate further on the details of the results if the negative entropy instead of log-barrier regularizer is used? What would be the concrete dependence of the results on $T$ and $A$ if negative entropy is employed?
I thank the authors for stating the corrected theorem and walking me through the proof sketch. I now understand that Theorem 4.1 is meant to state an in-expectation upper bound only, and $\\delta$ is just the probability with which some good event doesn't hold.

I don't have any other questions as of now. As I promised, I am increasing my score from 5 to 6.
I thank the authors for their response and have no further questions.
Thank you for your comments. The statement of Theorem 4.1 should read as follows:

**Theorem 4.1.** *Let $\delta\in(0,\frac{1}{T})$ be given and suppose Assumption 2.1. and Assumption 2.2. hold. Then, for $T =\text{poly}(A,H,d, \log(|\Phi|))$ sufficiently large, Algorithm 2 guarantees $Reg_T \leq \text{poly}(A,H,d, \log(|\Phi|T)) \cdot T^{5/6}$ against an oblivious adversary, where $Reg_T :=E_{\rho^{1:T}}[\sum_{t=1}^T E_{\pi^t\sim \rho^t}[V^{\pi^t}(x_1;\ell^t)] -\sum_{t=1}^T V^{\pi}(x_1;\ell^t) ]$.*


Note that $Reg_T$ in this statement is a deterministic quantity; there is no randomness. The $\delta$ in the submission was just a typo. 

We now explain why there is no $\delta$ in the statement above even though the analysis of Theorem 4.1 (in particular Lemma G.4 and G.5) have a $\delta$.  The current analysis of Algorithm 2 implies that under the setting of Theorem 4.1, we have that for any $\delta\in(0,1)$, there is an event $\mathcal{E}(\delta)$ with probability at least $1-\delta$ under which
$\widehat{Reg}\_T \leq \text{poly}(A,H,d, \log(|\Phi|/\delta)) \cdot T^{5/6}$, where $\widehat{Reg}\_{T} := \sum\_{t=1}^T E_{\pi^t \sim \rho^t}[V^{\pi^t}(x\_1;\ell^t)] -\sum\_{t=1}^T V^{\pi}(x\_1;\ell^t);$ Note that the randomness here comes from $\rho^{1:T}$.  

Now, since $Reg_T = E_{\rho^{1:T}}[\widehat{Reg}_T]$ and $\widehat{Reg}_T \leq H T$, we have 

$Reg\_T =P[\mathcal{E}(1/T) ] E\_{\rho^{1:T}}\left[\widehat{Reg}\_T\mid \mathcal{E}(1/T) \right]+ P[\mathcal{E}(1/T)^c ] E\_{\rho^{1:T}}\left[\widehat{Reg}\_T\mid \mathcal{E}(1/T)^c \right]\leq  \text{poly}(A,H,d, \log(|\Phi|/\delta)) \cdot T^{5/6}  + H,$ where we used that $P[ \mathcal{E}(1/T)^c]\leq 1/T$ and the bound on $\widehat{Reg}_T$ under $\mathcal{E}(1/T)$.

Note that the high probability bound on $\widehat{Reg}_T$ above is still not good enough for an adaptive adversary; see the answer to Q3.

We hope this clarifies things. Please let us know if you have any more questions.
Thank you for your rebuttal. I have read through all the other reviews and your responses. At this point, I do not have any further questions. I will reconsider my score based on the discussions and additional inputs provided during the current phase and the next phase of the review process.
I thank the authors for the response. How Thm 4.1 should be corrected is still unclear to me from the response. Could the authors state the corrected Thm 4.1 in this thread? Also, what is the role of $\\delta$ (confidence parameter) here? What happens if we make it very small (close to 0) or large (close to 1)?