Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedback
Authors: Canzhe Zhao
Ruofeng Yang
Baoxiang Wang
Xuezhou Zhang
Shuai Li
Venue: NeurIPS 2023 poster (2023)
Keywords: adversarial low-rank mdps
TL;DR: camera ready version

Abstract: In this work, we study the low-rank MDPs with adversarially changed losses in the full-information feedback setting. In particular, the unknown transition probability kernel admits a low-rank matrix decomposition \citep{REPUCB22}, and the loss functions may change adversarially but are revealed to the learner at the end of each episode. We propose a policy optimization-based algorithm POLO, and we prove that it attains the $\widetilde{O}(K^{\frac{5}{6}}A^{\frac{1}{2}}d\ln(1+M)/(1-\gamma)^2)$ regret guarantee, where $d$ is rank of the transition kernel (and hence the dimension of the unknown representations), $A$ is the cardinality of the action space, $M$ is the cardinality of the model class that contains all the plausible representations, and $\gamma$ is the discounted factor. Notably, our algorithm is oracle-efficient and has a regret guarantee with no dependence on the size of potentially arbitrarily large state space. Furthermore, we also prove an $\Omega(\frac{\gamma^2}{1-\gamma} \sqrt{d A K})$ regret lower bound for this problem, showing that low-rank MDPs are statistically more difficult to learn than linear MDPs in the regret minimization setting. To the best of our knowledge, we present the first algorithm that interleaves representation learning, exploration, and exploitation to achieve the sublinear regret guarantee for RL with nonlinear function approximation and adversarial losses.

Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedback
Canzhe Zhao Shanghai Jiao Tong University canzhezhaodgjtu.co edu. cn
Ruofeng Yang Shanghai Jiao Tong University wanshuiyin@sjie tu. edu. cn
Baoxiang Wang
Xuezhou Zhang Boston University xuezhouz@bu.cem edu
The Chinese University Hong Kong. Shenzhen bxiangvang@cuhk. edu. cn
Shuai Li Shanghai Jiao Tong University shuaili80sj tu. edu. en
Abstract
In this work, we study the low-rank MDPs with adversarially changed losses in the full-information feedback setting. In particular, the unknown transition probability kernel admits a low-rank matrix decomposition [Uehara et al., 2022], and the loss functions may change adversarially but are revealed the learner at the end of each episode. We propose policy optimization- based algorithm POLO, and prove that it attains the OKK A dd guarantee, where is rank of the transition kernel (and hence the dimension of the unknown representations), A is the cardinality of the action space, M is the cardinality of the model class that contains all the plausible representations, and Y is the discounted factor. Notably, our algorithm is oracle-efficient and has regret guarantee with no dependence on the size of potentially arbitrarily large state space. Furthermore, we also prove Q 1 regret lower bound for this problem, showing that low-rank MDPs statistically more difficult learn than linear MDPs in the regret minimization setting. To the best of our knowledge, we present the first algorithm that interleaves representation learning, exploration, and exploitation to achieve the sublinear regret guarantee for RL with nonlinear function approximation and adversarial losses.
M1/(1 - 7) regret
1 Introduction
In reinforcement learning (RL), the goal to learn a (near) optimal policy through the interactions between the learner and the environment, which is typically modeled as the Markov decision processes (MDPs) [Feinberg, 1996). When the state and action spaces are finite, many works have established the minimax (near) optimal regret guarantees for MDPs with finite horizon [Azar et al., 2017] and MDPs with infinite horizon [Tossou et al., 2019, He et al., 2021b]. In real applications of RL, however, the state and action spaces may be arbitrarily large and even infinite, which may lead the curse dimensionality. To tackle this issue, a common approach is function approximation, which
"Corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

approximates the value functions of given policies with the leverage of feature mappings. Assuming that the feature mapping which embeds the state-action pairs to a low dimensional embedding space is known, RL with linear function approximation has been well studied recently. In particular, linear mixture MDPs [Ayoub et al., 2020] and linear MDPs [Jin et al., 2020b] are the two models of RL with linear function approximation that have been extensively studied. Notably, their (near) optimal regret guarantees are established by Zhou et al. [2021] and He et al. [2023] respectively. Nevertheless, in scenarios with complex and large-scale data, attaining the true underlying feature mappings might be unrealistic, and thus representation learning is needed. Many empirical works have shown that representation learning can accelerate the sample and computation efficiency of RL [Silver et al., 2018, Laskin et al., 2020, Yang and Nachum, 2021, Stooke et al., 2021, Schwarzer et al., 2021, Xie et al., 2022]. However, representation learning is provably more difficult in RL and other sequential decision- making problems than in non-sequential and non-interactive problems (e.g.. supervised learning) [Du et al., 2020, Wang et al., 2021a, Weisz et al., 2021, Uehara al., 2022]. To pursue sample-efficient RL in the presence of representation learning, recent works have made initial attempts study the theoretical guarantees of representation learning in RL under the fixed or stochastic loss functions [Uchara et al., 2022, Zhang et al., 2022].
In practice, however, it might be stringent to assume that the loss functions are stochastic. To tackle this issue, Even-Dar et al. [2009] and Yu et al. [2009] propose the first algorithms with provably theoretical guarantees that can handle adversarial MDPs, where the loss functions may change adversarially in each episode. Subsequently. most of the works in this line of research focus on learning tabular MDPs with adversarial loss functions [Neu et al., 2010a.b, 2012, Arora et al., 2012, Zimin and Neu, 2013, Dekel and Hazan, 2013, Dick et al., 2014, Rosenberg and Mansour, 2019a,b, Jin and Luo, 2020, Jin et al., 2020a, Shani et al., 2020b, Chen et al., 2021, Ghasemi al., 2021, Rosenberg and Mansour, 2021, Jin et al., 2021b, Dai et al., 2022, Chen et al., 2022]. To learn adversarial MDPs with large state and action spaces, some recent works study RL with adversarial loss functions and linear function approximation [Cai et al., 2020, Neu and Olkhovskaya, 2021, Luo et al., 2021 He et al., 2022, Zhao et al., 2023, Kong et al.. 2023]. However, all these existing works assume that the state-action feature representations are known. As aforementioned, in complex and high- gigh-dimessional environments, the application of these algorithms may be still hindered due to the potential difficulty of knowing the true feature mappings a priori. Therefore, the following question naturally remains open:
Can we devise an algorithm to simultaneously tackle the representation learning and adversarially changed loss functions in reinforcement learning?
In this work, we give an affirmative answer to the above question in the setting of adversarial low- rank MDPs with full-information feedback. Specifically, in this problem, the unknown transition probability kernel admits a low-rank matrix decomposition but the true representations regarding the transitions are not known priori. Mcanwhile, the loss functions are arbitrarily chosen by an adversary across episodes and are revealed to the learner after each episode.
To solve this problem, we propose policy optimization-basse based algorithm, which we call Policy Optimization for LOw-rank MDPs (POLO). Specifically, our POLO algorithm obtains an O(K% AV + M)/(1 - ?) regret guarantee for adversarial low-rank MDPs in the full- information feedback setting and is oracle-efficient. Algorithmically, POLO follows similar ideas of optimistic policy optimization methods in that it first constructs optimistic value function estimates and then runs online mirror descent (OMD) over the optimistic value estimates to deal with the adversarially changed loss functions [Shani et al., 2020b, Cai et al., 2020, He et al., 2022, Chen et al., 2022]. However, in the presence of representation learning, the exploration and exploitation needed to learn the adversarial MDPs are more difficult than them in the tabular case [Shani et al., 2020b, Chen al., 2022] and in the linear case [Cai et al., 2020, He et al., 2022], where the exploration and exploitation can be essentially well balanced by directly modifying the algorithms studying stochastic MDPs in the tabular and linear cases. Concretely, to learn stochastic low-rank MDPs, previous works perform maximum likelihood estimation (MLE) over the experienced transitions [Agarwal al., 2020, Uchara et al., 2022, Zhang et al.. 2022]. Though the balance of representation learning, exploration, and exploitation can be simultancously handled by the algorithms in these works, these algorithms intrinsically have no regret guarantees but only sample complexity guarantees even in the stochastic case, since these algorithms need to take actions uniformly at certain steps
2

---

Table 1: Comparisons of regret bounds with most related works studying adversarial RL with function approximation under unknown transitions. K the number of episodes, d the ambient dimension of the feature mapping, is the discounted factor for infinite-horizon MDPs, and S, A, and M are the cardinality the state space, action space, and model class, respectively. Note that the dependence on is not strictly comparable since some works originally studying finite-horizon MDPs and these results are translated into results for infinite-horizon MDPs by substituting horizon length H with (1/(11 7)). The column of "unknown features" indicates whether the algorithm can work in the case when no true feature mappings are known priori.
Algorithm
Model
Feedback
Regret
Unknown Features
OPPO
Linear Mixture
Full-
δ (dvK/(11-))
X
[Cai et al., 2020]
MDPs
information
POWERS
Linear Mixture
Full-
Ô (dvK/(11-)))
x
[He et al., 2022]
MDPs
information
LSUOB-REES REPS Zhao et al. [2023]
Linear Mixture
Bandit
Ô ((SSVKK + (1-7)
x
MDPs
Feedback
Luo al. [2021a]
Linear MDPs
Bandit
( /166 /1-1///11/11)))) 7)
Feedback
0( 1110,213
Dai et al. [2023]
Linear MDPs
Bandit
(1-7)
Feedback
PO-LSBE
Linear MDPs
Bandit
Ô
A/ [1->}²
(1-7)*
Sherman et al.
Feedback
[2023]
GLAP
Linear MDPs
Bandit Feedback
(//'H'2/2///
Kong et al. [2023]
δ (d'A + VK (1-z)²
OPPO+
Linear MDPs
Full- information
Zhong and Zhang [2023]
10 A A'?ddlu(1+M) (1-7)*
POLO (Ours)
Low-rank MDPs
Full- information
Ω
dAK
in each episode (cf.. Lemma 9 of Uchara et al. [2022]). 2 Hence, straightforward adaption of their methods from the stochastic setting to the adversarial setting will fail to learn adversarial low-rank MDPs. To cope with this issue, we carefully devise an algorithm with doubled exploration and exploitation scheme, which interleaves (a) the exploration over transitions required in representation learning; and (b) the exploration and exploitation suggested by the policy optimization. To this end, our algorithm adopts mixed roll-out policy, which consists of uniformly explorative policy and a policy optimized by OMD. Through carefully tuning the hyper-parameter of the mixing coefficient used in our mixed policy, we can avoid pulling actions uniformly at random to conduct exploration each episode and only conduct uniform exploration at a certain fraction of all the episodes (see Section 3.1 for details). Besides, unlike tabular and linear (mixture) MDPs, it is in general hard to achieve the point-wise optimism for each state-action pair. Therefore, depart from previous methods [Shani et al., 2020b, Cai et al., 2020, He al., 2022] conducting policy optimization in the true model (i.e,, i the transition kernel characterized by the true representation). our algorithm conducts policy optimization in the fixed learned model with the epoch-basee model update, which enables a new analysis scheme that only requires a near optimism at the initial state su (see Section 3.2 for
With the leverage of the common explore-ther then-commir (ETC) style conversion, the modified versions of these algorithms can obtain sublinear regret in the setting of low-ran MDPs with stochastic loss functions, but this conversion is still not able deal with adversarial loss functions.
3

---

details). Also, we prove regret lower bound of order 92( ( loss functions, which thus also serves regret lower bound for our problem and indicates that low-rank MDPs are statistically more difficult to learn than linear MDPs in the regret minimization setting. To the best of our knowledge, this work makes the first step to establish an algorithm with a sublinear regret guarantee for adversarial low-rank MDPs, which permits RL with both nonlinear function approximation and adversarial loss functions. The concrete comparisons between the results of this work and those of previous works are summarized in Table 1.
VdAK) for low-rank MDPs with fixed
1.1 Additional Related Works
RL with Function Approximation Significant advances have emerged in RL with function ap- proximation to cope with the curse of dimensionality in arbitrarily large state space or action space. In general, these results fall into two categories. The first category studies RL with linear function approximation, including linear MDPs [Yang and Wang, 2019, Jin et al., 2020b, Du et al., 2020, Zanette et al., 2020, Wang et al., 2020, 2021b, He et al., 2021a, Hu et al., 2022, He et al., 2023] and linear mixture MDPs [Ayoub et al., 2020, Zhang et al., 2021, Zhou et al., 2021, He et al., 202 a, Zhou and Gu, 2022, Wu et al., 2022, Min al., 2022, Zhao al., 2023]. Remarkably, He al. [2023] and Zhou et al. [2021] obtain the nearly minimax optimal regret Ö(dv K)* in linear MDPs and linear mixture MDPs respectively when the loss functions are fixed or stochastic. The other category studies RL with general function approximation. Amongst these works, Jiang et al. [2017], Dann et al. [2018], Sun et al. [2019], Du et al. [2019], and Jin et al. [202 [a] study the MDPs satisfying the low Bellman-rank assumption, which assumes the Bellman error matrix has low-rank factorization. Also, Du et al. [2021] consider similar but slightly more general assumption termed as bounded bilinear rank. Besides, Russo and Roy [2013], Wang et al. [2020], Jin et al. (2021a). and Ishfaq et al. [2021] study low Eluder dimension assumption, which is originally proposed to characterize the complexity of function classes for bandit problems.
Representation learning in RL arises when the feature mapping that embeds the state-action pairs in RL with linear function approximation no longer known a priori. Such a problem is typically studied in the setting of low-rank MDPs, which does not assume the feature mapping of state-action pairs is known. Consequently, the setting of low-rank MDPs strictly generalizes the setting of linear MDPs, but at the cost of being more difficult to learn due to potential nonlinear function approximation induced by representation learning. In this line of research, algorithms with provably sample complexity guarantees have been developed in both model-based methods [Agarwal et al., 2020, Ren et al., 2022, Uehara et al., 2022] and model-free methods [Modi et al., 2021, Zhang et al., 2022], respectively. The model-based algorithms of Agarwal al. [2020]. Ren et al. [2022] and Uchara et al. [2022] learn the representation from a given model class of transition probability kernels. In contrast, the model-free methods do not require model learning but may bear some limitations. In particular, Modi et al. [2021] assume the MDPs satisfying the minimal reachability assumption, and the sample complexity of the algorithm of Zhang et al. [2022] only holds for special class of low-rank MDPs called block MDPs. Besides, representation learning in Markov games has also been investigated recently [Ni et al., 2022].
RL with Adversarial Losses Recent years have witnessed significant advances in learning RL with adversarial losses in the tabular case [Neu et al., 2010a,b, 2012, Arora et al., 2012, Zimin and Neu, 2013, Dekel and Hazan, 2013, Dick al., 2014, Rosenberg and Mansour, 2019a,b, Jin and Luo, 2020, Jin et al., 2020a, Shani et al., 2020b, Chen et al., 2021, Ghasemi et al., 2021, Rosenberg and Mansour, 2021, Jin et al., 2021b, Dai et al., 2022, Chen et al., 2022]. When it comes to the setting of linear function approximation, various policy optimization- solve adversarial linear mixture MDPs [Cai al., 2020, He al., 2022] and adversarial linear MDPs [Luo et al., 202 b, Dai et al., 2023, Sherman et al., 2023, Zhong and Zhang, 2023]. The other line of works studies RL with linear function approximation and adversarial losses using occupancy measure-based methods [Neu and Olkhovskaya, 2021, Zhao et al.. 2023, Kong et al., 2023]. To the best of our knowledge, however, there are no works in existing literature studying RL with both nonlincar function approximation and ad adversarial loss functions.
methods have been established to
2 Preliminaries
We consider episodic infinite horizon low-rank MDPs with adversarial loss functions, the preliminaries of which are introduced as follows.

---

Episodic Infinite-horizon Adversarial MDPs An episodic infinite horizon adversarial MDP is denoted by a tuple (S,A, P" 1- 7, do). where S is the state space (with potentially infinitely many states), A is the finite action space with cardinality |AA| = A, P S x A x S [0, 1] is the transition probability kernel such that P* (s(s' 8, a) is the probability of transferring to state s' from state s after executing action a, 7 E [0, 1) is the discount factor, do E (SS) is the initial distribution
over the state space, and E. : S x A + [0, 1] is the loss function of episode chosen by the adversary. For the ease of exposition, we assume do is known.
In this work, we consider a special class of MDPs called low-rank MDPs [Agarwal et al., 2020, Uehara et al., 2022. Zhang et al., 2022]. Specifically, instead of assuming known true feature mapping, low-rank MDPs only assume that the transition probability kemne p admits a low-rank decomposition, with the formal definition given as follows.
Definition 2.1 (Low-rank MDPS), An MDP is a low-rank MDP if there exist two feature embedding functions 6* S x A 7 Rd and p= S + R such that for any (s,a,s') E S A S, P* (s' 8, a) = n² (5') (*(s,a), where (s,*(s I 1 and for any function g : S 7
[0, 1I. |I μ² (s)g(s)d(s)(}s S Vd.
Note that the regularity assumption imposed over o² and μ² is only for the purpose of normalization.
Function Approximation When the state space is arbitrarily large, function approximation is usually considered to permit sample-effieien efficienn learning for MDPs. Since the true feature mapping of state-action pairs is not known priori in the low-rank MDPs, to make this problem tractable, assume the access to a realizable model class as previous works [Agarwal et al., 2020, Uehara et al., 2022], detailed in the following.
Assumption 2.1. There exists a known model class M (H, ME de D} satisfying (a) (lo(s, I 1 and f p (s') a(s, a)d (s') = 1 for any (s, a²) E x Ax V & E t; and (b) [I (()))(s))(())) s vd any function g : S + [0, 1]. Moreover, it holds that μ E V and o² E +.
Throughout this paper, for the sake of brevity, we assume that the cardinality of v and are finite, meaning that M also has bounded cardinality M = [M]. However, note that extending the analyses to the function classes with infinite cardinality but bounded statistical complexity (e.g.. VC dimension) is not technically difficult.
We now introduce the interaction protocol between the learner and the environment. To begin with, denote by d)) (1 - 7) Er= Y d a) the state-action occupancy distribution, where p (s,a) is the probability of visiting (s, a) at step 7 under policy and transition P. With slight abuse of notation, let ddp(s) = Ene (s a) be the state occupancy distribution, denoting the probability of visiting state 8 under π and P.
Interaction Protocol
Ahead of time, MDP is decided by the environment, and only the state space S and the action space A are revealed to the learner. Meanwhile, the adversary secretly chooses K loss functions {&x 1KK k= each of which will be used in one episode. The interaction will proceed in K episodes. At the beginning of episode kt the learner chooses a stochastic policy T& : x A + [0, 1]. where [a(aa 8) is probability of taking at state s. Starting from an initial state sp dg. the learner repeatedly executes policy Ty until reaching the termination. After episode is is terminated, the leamnrr observes a trajectory {(kk)) ak.r)) , as well as the loss function Ey.
For each episode and each state-action pair (x, a), the state-action value (T( a) is defined as Q7 a) E Ei= 7 (s( 0k,r) I,, P*, (Sk,o, as.u) (s, a)) Also define (T) ( QQ a)] and V En IV (so)]. The learning objective is to minimize the pseudo regret with respect to n², defined as
K
V."") )]
R = E
V
'Though we focus on episodic infinite- horitte--orzooon MDPs in this work, note that it is not technically difficult to extend the analyses in this work to the case of episodic finite-horizon MDPs
5

---

where the expectation is taken over the potential randomness of the algorithm, x² E arg men Σ V is the fixed optimal policy in hindsight and 11 is the set of stochastic policies.
3 Algorithm
This section presents our POLO algorithm with the pseudocode illustrated in Algorithm 1. At high level, POLO leverages mixed roll-out policy to conduct doubled exploration and exploitation, i.e. (a) the exploration over transitions required by representation learning; and (b) the exploration and exploitation over adversarially changed loss functions required by the policy optimization (Section 3.1). To deal with the issue that only the near optimism at the initial state 80 is available in low-rank MDPs, POLO conducts policy optimization in fixed learned models with the epoch-based model update, which enables new analysis scheme (Section 3.2).
3.1 Doubled Exploration and Exploitation
Let 7t be the policy of episode computed by policy optimization (cf., Eq. (3)). At the beginning of episode our algorithm first collects a state St di. (Line 6) by invoking a geometric sampling roll-in procedure [Kakade and Langford, 2002, Agarwal et al., 2021, Uehara et al., 2022]. Starting from an initial state 8g dg, at each step т, this roll-in procedure will terminate and return state & with probability 1 - 7, and otherwise will take action a ~ #x(- 87) and transfer to the next state 8, ~ (. ST, a.).
Then our algorithm will further interact with the environment in successive two steps after collecting 8% ~ dps (Line Line 11) like previous works studying low-rank MDPs [Agarwal et al., 2020, Uchara et al., 2022, Zhang et al., 2022]. One of the main differences between previous algorithms and ours lies in how to deal with exploration and exploitation when interacting with the environment. In the case of stochastic low-rank MDPs, the key in the analysis is to ensure the (near) optimism of the optimal policy n² in the learned model, which essentially requires to bound the performance gap VE VE" by relating it with the model error regarding n², i.e., (a.a))dpp [| s. P*
8, a) 1,) where Pe is the MLE solution defined in Eq. (1). However, this model error is not directly controllable, as the algorithm does not know the optimal policy x¹ and can not collect data following r" to bound the model error. Fortunately, by empirical process theory [Geer, 2000, Zhang, 2006], the model error (s)))pp [1) s,a) (- 8, a)]l]] regarding the executed policies (
Σ. -i=1 de. (s,a). Therefore, previous works [Agarwal et al., 2020, is bounded, where (s a) k
Uehara et al., 2022, Zhang et al., 2022] ensure the optimism of the optimal policy x* by applying importance weighting to change the measure from dp. to Pk when bounding the model error. The complication is that to control the ratio xt (a (a s) for any (s, a) E S x A and i E [K] in importance weighting, the algorithms in previous works take actions from the uniform distribution U(A) over action space A, which intuitively can be seen as conducting exploration over transitions required by representation learning. Consequently, though these algorithms enjoy excellent sample complexities, they intrinsically do not have regret guarantees due to the uniform exploration over action space, even in the stochastic setting. Moreover, to learn adversarial low-rank MDPs, is required to take actions adaptively according to the observed loss functions in previous episodes instead of uniformly taking actions. To address this "conflict" so as to learn adversarial low-rank MDPs, propose to use mixed roll-out policy to interleave (a) the exploration over transitions required by representation learning; and (b) the exploration and exploitation over the adversarial loss functions by policy optimization, which we call doubled exploration and exploitation and is pivotal to achieving our regret bound as we will shortly see. Formally, our algorithm will conduct the exploration over the transitions with probability & and execute policy मे optimized by OMD with probability 1 - È respectively, as shown in Line 7- Line 11.
After interacting with the environment, the newly collected data in these two steps will be used to update the datasets (Line 14), and the empirical transition Px will be updated by performing MLE over the updated datasets by solving (Line 16)
(ntee 3x)
arg max E ED.DD [in (s)) (n.M)M
(1)
where we denote Ep [f (s, 87)

---

Algorithm Policy Optimization for Low-rank MDPs (POLO)
1: Input: Mixing coefficient Ç. epoch length L, regularization coefficients {A&) bonus coeffi- cients {ax)k=) K model class .M, number of episodes K, learning rate 17.
2: Initialization: Set Do 0. D/ 9.
3: for = 1.,..... |K/ L do
4: Set k; = 1)L 1 and * (- |s) to be uniform for any 8 E S.
5: for k= k; k; + 1,.,.., h;s +
do
6:
Sample sy. from dp..
7:
Sample C2 ~ Ber(1 E).
8:
if ck = 1 then
9:
Sample ag #T(- sk), ~ pT(. Sk: (x. #x(- 1%)), 8% ~ P* ( 1 db).
10:
else
11:
Sample ag UAA,, S'y ~ (. Sk, (k), ~ (A), $ P* dx). end if
12:
Observe the loss function lx. Update datasets D2 = DR-1 U [(S,, ah, 8k)) D' - -D U (1(((//1001 d2. 8%))
14:
15:
if k: k; then
16:
Set the empirical transition Pa(8' 8, (x) a(s,a, 8) E E Axs, via solving Eq. (I).
Update the empirical covariance matrix Σn = E(,,))D, (6(3,a) u) + +Aa. Set the bonus function &y (8, a) min(as || (s, a) 2)/(1 7), v(8,a) ES A.
17:
18:
else
Set the empirical transition Px. = Pk. and bonus function E2- = D
20:
21:
end if
22:
Compute 2 (+,-) Policy-Evaluation PR, Ex ba, mx). Update policy # (.) x #x ()) exp( - (s,
23:
24:
end for
25:
end for
3.2 Policy Optimization in Fixed Learned Models
remains to compute the policy Tk+1 to be used in the next episode. To this end, we resort to the canonical OMD framework to perform policy optimization like previous methods [Shani et al., 2020a, Cai et al., 2020, He et al., 2022]. However, previous OMD-based policy optimization methods for tabular and linear (mixture) MDPs [Shani et al., 2020a, Cai et al., 2020, He al., 2022] critically depend the point-wise optimism for each state-action pair, i.e., Q (s,a) S (x(s a) + y(P' f (s,, a), to enable the decomposition (cf., Lemma I by Shani et al. (2020a])
f (so) V (5o) E
mx( (5) - x-(. (7)s @ (sT..) @f
n², n"tP",
@ nT (s (r) la (a(s), ( [p- (or)
E
7"
T², P 80
-==
where R and Qh are the state value and state-action value functions of 7. on (Pr, lu -xx) with Ex as some bonus function and the expectation is taken over the randomness of sampling
x-" (- |sy,) and sr+1 P* (-1 sy,a,). a.). The summation of the first term in the above display is contributed by competing with the optimal policy x² in the true model p* and can be bounded by common OMD analysis, which thus can be regarded as conducting policy optimization in the true model. The
woint-wise optimism guarantees that the second term is less than or equal to O.
Nevertheless, in low-rank MDPs, due the unknown representation, it is generally hard to obtain the above point-wise optimism, which leaves the second optimism term unbounded. To cope with this issue, instead consider the following decomposition:
V- (so) Vi (so)
7

---

= (so) Vit (so) + V/ (so) - Vi (so)
=E >" (- sk,r) - x" sk,7), 2x (sk.T::) x², Pk. 1 + V (so) - VE (so), (2)
where the first term is contributed by competing against the optimal policy x² in the learned model Ps and can be seen as conducting policy optimization in learned models. This decomposition will be amenable as long as we can achieve a near optimism at the initial state so. f.e., V (so) (so) X O, which turns out to be feasible for low-rank MDPs [Uchara et al., 2022]. However, there remains one more caveat. The first term in Eq. (2) is now no longer directly bounded by OMD analysis, due to the local update nature of OMD-based policy optimization at each state and the state occupancy distribution 4% now varies across different episodes. To address this issue, Algorithm adopts an epoch- based transition update, in which one epoch has episodes and the model is only updated at the first episode in one epoch (Line 15 Line 20). Concretely, Algorithm sets P3. = Pk. and b2 - bR, where k; is the first episode of the epoch to which the episode k belongs. In this manner, the learned model fixed in one epoch, and thus the regret of dealing with the adversarial loss functions by competing against the optimal policy x² can be bounded in one epoch. Subsequently, at the end of episode ks our algorithm first computes the optimistic value estimate TT for current policy Åy. under P& together with the vomus-enhaneed loss functions lx - by by policy evaluation (Line 22). Note that this boils down to planning in the setting of linear MDPs for given features in the learned model and this can be done computationally efficiently [Jin et al., 2020b]. Then the policy is updated by solving
# (+1())))
arg min 17 (a( 6), Q (s. (6.-)) + DP(T(- (ss (x [s)).
*(1))EA(A)
where 17 > 0 is the learning rate be tuned later and Dr((,))==(()) -() VF())) is
the Bregman divergence induced by the regularizer F. With F( $)) - IacA a(a 8) In T(a s)
as the negative entropy, the closed-form solution to the above display is shown in Line 23, which can be regarded as kind of soft policy improvement.
Analysis
4.1 Regret Upper Bound
The regret upper bound of our POLO algorithm for learning adversarial low-rank MDPs is guaranteed by the following theorem.
Theorem 4.1. Suppose K dd 7) For any adversarial low-rank MDP satisfying Definition 2. by setting the epoch length K A-' gg( -)), learning rate n (1 7) /) A/ (2L), bonus coefficient an ((V/(A// + d²) In(Mk/5)) regularization coefficient
A = O (m(
mixing coefficient { = K A/> h/ (1 ()), and 8 = 1/K, then the regret of
Algorithm I is upper bounded by
K A (1 (1+ (
AMK?)
RK = O
71
(1
Remark 4.1. Ignoring the dependence on all logarithmic factors but M, the regret upper bound can be simplified as O(K% A22 + M)/(1 - )) Comparing with the regret lower bound ((G_VdAK) in Theorem 4.2, the regret upper bound in Theorem 4.1 matches in A up to a logarithmic factor but looses in factors of K and d Also, note that when K is large enough such that and I. can be chosen & K 4/6 A// /(1 7) and L. A-
7) K//a A00AA-/000 1-// 4/2 Z 1, meaning that K 2 A?, the regret upper bound can be further optimized to 0(K A/2 2
In(1+ (M) -)) Note that this does not conftict with the regret lower bound in Section 4.3 since the magnitude of this upper bound is still larger than that of the regret lower bound as long as K d 12 7)
'Throughout this paper, we suppose for simplicity that the number of episodes K is divisible by the epoch length L considered.
8

---

4.2 Proof of Regret Upper Bound
We now present the proof of Theorem 4.1. To begin with, recall that in each episode k. after state Sg sampled from dp. the actual roll-out policy will be T& s) = { ((A) (1 E) (x s). Therefore, it holds that
RK= Σ
K
T(ck = =1} (V6--V3 + Ifcx = =0] (vz Vx²)
=
Σ V+= - vz')
EK
S E
+ (1 7)
(4)
where the inequality is due to that Er=o 7" E (8T, ar) E j0, 1 1/(1 - -3)] holds for any episode k and any trajectory {( a, r= We now turn to bound the first term in Eq. (4) by decomposing into the following three terms
V Ru
Vx
V
V
ESTIMATION BLAS TERM
OMD REGRET TERM
OPTIMISM TERM
(5)
Bounding OMD REGRET TERM The OMD REGRET TERM contributed by competing against n² using A. with Q as loss function in the learned model Pk,- This term is thus bounded by standard OMD analysis, detailed in the following lemma.
7) In A/(2)), the OMD REGRET TERM bounded as Lemma 4.1. By setting 7 (1-7)
K E (v---V VI )
Kv2lnA VL(1-7)²
Bounding OPTIMISM TERM
The OPTIMISM TERM is controlled by choosing appropriate bonus coefficient ag. Note that different from tabular and linear cases, the bonus functions and coefficients here are not devised to control the optimism for each actenn pair. Instead, they devised to provide a (near) optimism only at the initial state 8u-
Lemma 4.2. By setting O(V7(A/E + d)) In (MK/5) and A = O(dln(Mk/0)) with prob- ability 1 - 5, the OPTIMISM TERM is bounded as ΣK (VE VE (L+ (L+ Alo(MN/5)
E(1-))>
Bounding ESTIMATION BIAS TERM It remains to bound the ESTIMATION BIAS TERM, which comes from the difference between the values of rumning the same policy मे the true model (i.e., p* and (x) and the learned empirical model (i.e., P& and & - by). respectively. This term can be translated into the eиror between the truc model and the learned model using the common simulation lemma, which is thus bounded by the summation of bonus functions. Note that since the empirical features used to construct our bonus functions vary in each episode, we first relate the bonus functions with the fixed true feature o² using the one-step trick [Uehara et al., 2022, Zhang et al., 2022], and finally bound this term with the leverage of the canonical elliptical potential lemma. The result is shown in the following lemma.
Lemma 4.3. By setting ag = O(V2(A/E + dd) ln(M//8)) and d O(dIn(Mk/o))
with probability 1 - 5, the ESTIMATION BIAS TERM is bounded as Ek (v k
<
O (AVKL 5(1-))
Mn(1+ K) (n(K/55)
We refer the readers to Appendix A for the proof of the above lemmas. The proof of Theorem 4.1
is now concluded by first combining Eq. (4), Eq. (5), Lemma 4.1, 4.2, and 4.3 and then choosing
L 1/2 A 1/ 7), K K-16 1/2 /l (1
7), and 6 = 1/K.

---

Intuitively, the epoch length L illustrates trade-off between dealing with the adversarial losses and the representation learning over the unknown transitions. When L is large, there will be fewer restarts in the running of OMD and thus the learner will suffer less regret contributed by dealing with the adversarial losses as shown by Lemma 4.1. In contrast, a smaller 1. enables more frequent model updates, which leads to more accurate model estimation and less regret contributed by the representation learning as shown by Lemma 4.2 and 4.3.
4.3 Regret Lower Bound
This section presents the regret lower bound for learning adversarial low-rank MDPs with fixed loss functions in Theorem 4.2, which thus also serves as a regret lower bound for learning adversarial low-rank MDPs with full-information feedback.
Theorem 4.2. Suppose d 2 8, S 2 d 1, A d d-3. 3, and K 2 2(d - 2. Then for any algorithm Alg, there exists an episodic aefimite-horizon low-rank MDP MAig, with withfixed loss function such that the regret for this MDP lower bounded by 52( x² 1-y vdAK).
Proof Sketch. At a high level, we construct dA hard-to-learn low-rank MDP instances, which are difficult to distinguish in KL divergence but have very different optimal policies. In particular, all the constructed low-rank MDP instances have three levels of states, in which the only state in the first level is a fixed initial state and the states in the third level are absorbing states. Moreover, only one unique absorbing state in the third level has the lowest loss, which is termed as the "good state". In the constructed low-rank MDP instance Ma), the learner can only take specific action to transfer to state $2, in the second level and then take the other specific action to transfer to the unique good state. Due to the unknown representations of state-action pairs, the learner needs to distinguish all these dA low-rank MDP instances, which is essentially equivalent to dealing with a bandit problem with dA "arms". The detailed proof of Theorem 4.2 is postponed to Appendix B.
Remark 4.2. Theorem 4.2, to the best of our knowledge, provides the first regret lower bound for learning low-rank MDPs with fixed loss functions. We note that this regret lower bound can hold when d < S and d < A. which thus means that this lower bound is non-trivial. Besides, the regret upper bound in our Theorem 4.1 matches the regret lower bound in A up to a logarithmic factor but looses a factor of Ö (K /(11 - -))? Importantly, compured with the regret upper bound of linear MDPs [He et al., 2023] (the finite horizon H is substituted by the effective horizon (11((1-7) in our infinite-horizon setting for a fair comparison), the dependence on A in the regret lower bound of low-rank MDP shows a clear separation between low-rank MDPs and linear MDPs, which demonstrates that low-rank MDPs are statistically more difficult learn than linear MDPs in the regret minimization setting.
Conclusions
In this work, we study learning adversarial low-rank MDPs with unknown transition and full- information feedback. We prove that our proposed algorithm POLO achieves the OKK% A/*d/
M)/(1-7)3 regret, which is the first sublinear regret guarantee for this challenging problem. The design of our proposed algorithm features (a) a doubled exploration and exploitation scheme to simultaneously learn the transitions and adversarial loss functions; and (b) policy optimization in the fixed learned models with ppoch-based model update to enable new analysis scheme that only requires the near optimism at the initial state instead of the point-wise optimism. Also, we prove an s -س1م -i=VvVA ddAK) regret lower bound for this problem, serving as the first regret lower bound for learning low-rank MDPs in the regret minimization setting. Besides, there also remain several interesting future directions to be explored. One natural question is whether it is possible further optimize the dependence of our regret guarantee on the number of episodes K. The other question how to also learn adversarial low-rank MDPs with only the bandit feedback available. This is also challenging since the current occupancy measure- based methods and policy optimization- methods tackling adversarial MDPs with bandit feedback both depend on the point-wise optimism provided by the true feature mapping, which seems not feasible in low-rank MDPs. We hope our results may shed light on better understandings of RI. with both nonlinear function approximation and ad versarial losses and we Ieave the above extensions our future works.
10

---

Limitations
We note that in general our algorithm is oracle-efficient (given access to the MLE computation oracle in Eq. (I)) but may not be computationally efficient as previous works studying low-rank MDPs [Agarwal et al., 2020, Uehara et al.. 2022, Zhang et al., 2022, Ni et al., 2022]. However, also remark that in practice, these algorithms including ours are computationally feasible since the computation of MLE is only standard supervised learning problem and can be implemented using gradient descent methods. The other limitation is that throughout this paper, assume model class M with bounded cardinality .M and the regret upper bound of our algorithm has a logarithmic dependence on M. We remark that similar assumptions and dependence have also appeared in previous theoretical works studying RL with general function approximation [Jiang et al., 2017, Sun al., 2019]. Also, extending the analyses to an infinite hypothesis class is possible if the hypothesis class has bounded statistical complexity [Agarwal et al., 2020].
Acknowledgement
The corresponding author Shuai Li is supported by National Key Research and Development Program of China (2022ZD01 14804) and National Natural Science Foundation of China (62376154, 62006151 62076161). Baoxiang Wang is partially supported by National Natural Science Foundation of China (62106213, 721 10002) and Shenzhen Science and Technology Program (RCHS2001066910436666 JCYI20211334110011120
References
Pieter Abbeel and Andrew Y. Ng. Exploration and apprenticeship learning in reinforcement learning. In Machine Learning. Proceedings of the Eventy-Secone International Conference (ICML 2005), Bonn. Germany, August 7-11, 2005, volume 119 of ACM International Conference Proceeding Series, pages 1-8. ACM, 2005.
Alekh Agarwal, Sham M. Kakade, Akshay Krishnamurthy, and Wen Sun. FLAMBE: structural complexity and representation learning of low rank mdps. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
Alekh Agarwal, Sham M. Kakade, Jason D. Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. J. Mach. Learn. Res., 22: 98:1-98:76, 2021.
Raman Arora, Ofer Dekel, and Ambuj Tewari. Deterministic mdps with adversarial rewards and bandit feedback. In Nando de Freitas and Kevin P. Murphy, editors, Proceedings of the Twenty- Eighth Conference on Uncertainty in Artificial Intelligence, Catalina Island, CA, USA, August 14-18, 2012, pages 93-101. AUAI Press, 2012.
Alex Ayoub, Zeyu Jia, Csaba Szepesvári, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeter regression. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 463-474. PMLR, 2020.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW. Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 263-272. PMLR, 2017.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration policy opti- mization. In Proceedings of the 37th International Conference on Machine Leurning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 1283- 1294. PMLR, 2020.
11

---

Liyu Chen, Haipeng Luo, and Chen- Yu Wei. Minimax regret for stochastic shortest path with adversarial costs and known transition. Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 1180-1215. PMIR, 2021.
Liyu Chen, Haipeng Luo, and Aviv Rosenberg. Policy optimization for stochastic shortest path. In Po-Ling Loh and Maxim Raginsky, editors, Conference Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pages 982-1046, PMLR, 2022.
Yuan Cheng, 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, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.
Yan Dai, Haipeng Luo, and Liyu Chen. Follow seoow-the-peneee wetee--eruuureddeeeeeeeee for adversarial markov decision processes with bandit feedback. CoRR, 0bbs/2205.1351,, 2022. doi: 215500//rXiv.22051335533
Yan Dai, Haipeng Luo, Chen- Yu Wei, and Julian Zimmert. Refined regret for adversarial mdps with linear function approximation. International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 6726-6759. PMLR, 2023.
Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. On oracle-efficient PAC RL with rich observations. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information P Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 1429-1439, 2018.
Ofer Dekel and Elad Hazan. Better rates for any adversarial deterministic MDP. In Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013, volume 28 of JMLR Workshop and Conference Proceedings, pages 675-683. JMLR.org. 2013.
Travis Dick, András György, and Csaba Szepesvári. Online learning in markov decision processes with changing cost sequences. Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014, volume 32 of JMLR Workshop and Conference Proceedings, pages 512-520. JMLR.org, 2014.
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic rein- forcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learning Theory, 16-19 March 2021, Virtual Conference, Worldwide, volume 132 of Proceedings of Machine Learning Research, pages 578-598. PMLR, 2021.
Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient RL. with rich observations via latent state decoding. In Proceedings of the 36th International Conference on Machine Learning. ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 1665-1674. PMLR, 2019.
Simon S. Du, Sham M. Kakade, Ruosong Wang. and Lin F. Yang. Is good representation suffi- cient for sample efficient reinforcement learning? In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
Simon S. Du, Sham M. Kakade, Jason D. Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in RL. In Proceedings of the 38th International Conference on Machine Learning, (CML.2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 2826-2836. PMLR, 2021.
Eyal Even-Dar, Sham M. Kakade, and Yishay Mansour. Online markov decision processes. Math. Oper. Res., 34(3):726-736, 2009.
A. Feinberg. Markov decision processes: Discrete stochastic dynamic programming (martin I. puterman). SIAM Rev, 38(4):689, 1996.
12

---

Aurélien Garivier, Pierre Ménard, and Gilles Stoltz. Explore first, exploit next: The true shape of regret in bandit problems. Math. Oper. Res., 44(2):377-39, 2019.
Sara A Geer. Empirical Processes in M-estimation, volume 6. Cambridge university press, 2000.
Mahsa Ghasemi, Abolfazl Hashemi, Haris Vikalo, and Ufuk Topeu. No-regret learning with high- probability in adversarial markov decision processes. In Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, UAI 2021, Virtual Event, 27-30 July 2021, volume 161 of Proceedings of Machine Learning Research, pages 992-1001. AUAI Press, 2021.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine PMLR, 2021a.
Learning Research, pages
Jiafan He, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for discounted mdps. In Advances in Neural Information Processing Systems 34: Annual Conference Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 22288 -23000, 2021b.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Near-optimal policy optimization algorithms for learning adversarial linear mixture mdps. In International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pages 4259-4280. PMLR, 2022.
Jiafan He, Heyang Zhao, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for linear markov decision processes. In International Conference on Machine Learning, ICML. 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 12790-12822. PMLR, 2023.
Pihe Hu, Yu Chen, and Longbo Huang. Nearly minimax optimal reinforcement learning with linear function approximation. In International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 8971-9019. PMLR, 2022.
Haque Ishfaq, Qiwen Cui, Viet Nguyen, Alex Ayoub, Zhuoran Yang. Zhaoran Wang, Doina Precup, and Lin Yang. Randomized exploration in reinforcement learning with general value function approximation. In Proceedings of the 38th International Conference Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 4607-4616. PMLR, 2021.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. Con- textual decision processes with low bellman rank are pac-learnable. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 1 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 1704-1713, PMLR, 2017.
Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning adversarial markov decision processes with bandit feedback and unknown transition. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 4860 4869. PMLR, 2020a.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I. Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria], volume 125 of Proceedings of Machine Learning Research, pages 2137-2143. PMLR, 2020b.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of RL problems, and sample-efficien algorithms. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 13406-13418, 202
13

---

Tiancheng Jin and Haipeng Luo. Simultaneously learning stochastic and adversarial episodic mdps with known transition. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
Tiancheng Jin, Longbo Huang, and Haipeng Luo. The best of both worlds: stochastic and adversarial episodic mdps with unknown transition. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 20491-20502, 2021b.
Sham M. Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Claude Sammut and Achim G. Hoffmmann, editors. Machine Learning, Proceedings of the Nine- teenth International Conference (ICMI. 2002), University of New South Wales, Sydney, Australia, Morgan Kaufmann, 2002.
July 8-12, 2002, pages 267-274.
Fang Kong, Xiangcheng Zhang, Baoxiang Wang, and Shuai Li. Improved regret bounds for linear adversarial mdps via linear optimization. CoRR, abs/2302.06834, 2023.
Michael Laskin, Aravind Srinivas, and Pieter Abbeel. CURL: contrasivee unsupervised representations for reinforcement learning. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages $639-5650 PMLR, 2020.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Haipeng Luo, Chen-Yu Yu Wei, and Chung-Wee Wei Lee. Policy optimization in adversarial mdps: Improved exploration via dilated bonuses. CoRR, abs/2107.083 2021a.
Haipeng Luo. Chen-Y: Yu Wei, and Chung-Wer Wei Lee. Policy optimization in adversarial mdps: Improved exploration via dilated bonuses. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, 2021b.
virtual, pages
Yifei Min, Jiafan Hc, Tianhao Wang, and Quanquan Gu. Learning stochastic shortest path with linear function approximation. In International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 15584-1555 15629. PMLR, 2022.
Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free representation learning and exploration in low-rank mdps. CoRR, abs/2102.07035, 2021.
Gergely Neu and Julia Olkhovskaya. Online learning in mdps with linear function approximation and bandit feedback. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 10407-10417, 2021.
Gergely Neu, András György, and Csaba Szepesvári. The online loop-free stochastic shortest-path problem. In Adam Tauman Kalai and Mehryar Mohri, editors, COLT 2010 - The 23rd Conference on Learning Theory, Haifa, Israel, June 27-29, 2010, pages 231-243. Omnipress, 2010a.
Gergely Neu, András György, Csaba Szepesvári, and András Antos. Online markov decision processes under bandit feedback. In Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of a meeting held 6-9 December 2010, Vancouver, British Columbia, Canada, pages 1804-1812. Curran Associates, Inc., 2010b.
Gergely Neu, András György, and Csaba Szepesvári. The adversarial stochastic shortest path problem with unknown transition probabilities. In Proceedings of the Fifreenth International Conference on Artificial Intelligence and Statistics, AISTATS 2012, La Palma, Canary Islands, Spain, April 21-23, 2012, volume 22 of JMLR Proceedings, pages 805-813. JMLR.org, 2012.
Chengzhuo Ni, Yuda Song, Xuezhou Zhang, Chi Jin, and Mengdi Wang. Representation learning for general-sum low-rank markov games. CoRR, abs/2210.16976 2022.
14

---

Tongzheng Ren, Tianjun Zhang, Csaba Szepesvári, and Bo Dai. A free lunch from the noise: Provable and practical exploration for representation learning. In Uncertainty in Artificial Intelligence. Proceedings of the Thigth-Fighth Conference on Uncertainty in Artificial Intelligence, UAI 2022, 1-5 August 2022, Findhoven, The Netherlands, volume 180 of Proceedings of Machine Learning Research, pages 1686-1696. PMLR, 2022.
Aviv Rosenberg and Yishay Mansour. Online stochastic shortest path with bandit feedback and unknown transition function. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 2209-22012111 2019a.
Aviv Rosenberg and Yishay Mansour. Online convex optimization in adversarial markov decision processes. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 5478-5486. PMLR, 2019b.
Aviv Rosenberg and Yishay Mansour. Stochastic shortest path with adversarially changing costs. In Zhi-Hua Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, pages 2936-2941 ijcai.org, 2021.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013.
2013, Lake Tahoe, Nevada, United States, pages
Max Schwarzer, Nitarshan Rajkumar, Michael Noukhovitch, Ankesh Anand, Laurent Charlin, R. De- von Hjelm, Philip Bachman, and Aaron C. Courville. Pretraining representations for data-efficient reinforcement learning. In Advances in Neural Information Processing Systems 34: Annual Con- ference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 12686 12699, 2021.
Lior Shani, Yonathan Efroni, Aviv Rosenberg, and Shie Mannor. Optimistic policy optimization with bandit feedback. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Viriual Event, volume 119 of Proceedings of Machine Learning Research, pages 8604 8613. PMLR, 2020a.
Lior Shani, Yonathan Efroni, Aviv Rosenberg, and Shie Mannor. Optimistic policy optimization with bandit feedback. In Proceedings of the 37th International Conference on Machine Learning, ICML, 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 8604 8613. PMLR, 2020b.
Uri Sherman, Tomer Koren, and Yishay Mansour. Improved regret for efficient online reinforcement learning with linear function approximation. In International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 31117-31150, PMLR, 2023.
David Silver, Thomas Hubert, Julian Schritwieser,, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419): 1140-1144, 2018
Adam Stooke, Kimin Lee, Pieter Abbeel, and Michael Laskin. Decoupling representation learning from reinforcement learning. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 9870-9879, PMLR, 2021.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based RL in contextual decision processes: PAC bounds and exponential improvements over model-free approaches. In Conference on Learning Theory, FOI.T2019 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Research, pages
PMLR, 2019.
15

---

Aristide C. Y. Tossou, Debabrota Basu, and Christos Dimitrakakis. Near-optimal optimistic reinforce- ment learning using empirical bernstein inequalities. CoRR, htss/1905.12425, 2019.
Masatoshi Uchara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline RL in low-rank mdps. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
Ruosong Wang, Ruslan Salakhutdinov, and Lin F. Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12. 2020, virtual, 2020.
Ruosong Wang, Dean P. Foster, and Sham M. Kakade. What are the statistical limits of offline RL with linear function approximation? In 9th International Conference on Learning Representations. ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021a.
Yining Wang, Ruosong Wang, Simon Shaolei Du, and Akshay Krishnamurthy. Optimism reinforce- ment learning with generalized linear function approximation. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021b.
Gellért Weisz, Philip Amortila, and Csaba Szepesvári. Exponential lower bounds for planning in mdps with linearly-realizable optimal action-value functions. In Algorithmic Learning Theory, 16-19 March 2021, Virtual Conference, Worldwide, volume 132 of Proceedings of Machine Learning Research, pages 1237-1264. PMLR, 2021.
Yue Wu, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal regret for learning infinite- horizon reward mdps with linear function approximation. In International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pages 3883-3913. PMLR, 2022.
Zhihui Xie, Zichuan Lin, Junyou Li, Shuai Li, and Deheng Ye. Pretraining in deep reinforcement learning: A survey. CoRR, abs/2211.023 1.03959, 2022.
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In Proceedings of the 36th International Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 6995-7004. PMLR, 2019.
Mengjiao Yang and Ofir Nachum. Representation matters: Offline pretraining for sequential decision making. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 11784 11 1174.. PMLR, 2021.
Jia Yuan Yu, Shie Mannor, and Nahum Shimkin. Markov decision processes with arbitrary reward processes. Math. Oper. Res., 34(3)7737-777, 2009.
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], volume 108 of Proceedings of Machine Learning Research, pages 1954- 1964. PMLR, 2020.
Andrea Zanette, Ching-An Cheng, and Alekh Agarwal. Cautiously optimistic policy optimization and exploration with linear function approximation. In Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 4473 4525. PMLR, 2021.
Tong Zhang. From e-entropy to kl-entropy: Analysis of minimum information complexity density estimation. The Annals of Statistics, 34(5):2180-2210, 2006.
16

---

Xuezhou Zhang, Yuda Song. Masatoshi Uehara, Mengdi Wang, Alekh Agarwal, and Wen Sun. Efficient reinforcement learning block mdps: A model-free representation learning approach. In International Conference on Machine Learning, ICMI. 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 26517-26547. PMLR, 2022.
Zihan Zhang. Jiaqi Yang, Xiangyang Ji, and Simon S. Du. Improved variance- confidence sets for linear bandits and linear mixture MDP. In Advances in Neural Information Processing Systems 34: Annual Conference Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 4342 -355, 2021.
Canzhe Zhao, Ruofeng Yang, Baoxiang Wang, and Shuai Li. Learning adversarial linear mix- ture markov decision processes with bandit feedback and unknown transition. In The Eleventh International Conference on Learning Representations, 2023.
Han Zhong and Tong Zhang. A theoretical analysis of optimistic proximal policy optimization in linear markov decision processes. arXiv preprint arXiv:2305.088: 08844,, 2023.
Dongruo Zhou and Quanquan Gu. Computationally efficient horizon-free reinforcement learning for linear mixture mdps. CoRR, 105/2205.115077 2022.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvári. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. Conference on Learning Theory, COLT 2021, 15-19 August 1021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 4532-4576. PMLR, 2021.
Alexander Zimin and Gergely Neu. Online learning in episodic markovian decision processes by relative entropy policy search. In Christopher J. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q Weinberger, editors, Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pages 1583-1591, 2013.
17


Reviews:
[{"review_id": "QqZB9jBUiu", "reviewer": "Reviewer_qWwQ", "summary": "This work studies low-rank MDPs with unknown and fixed transition and full-information adversarial losses. The proposed algorithm generalize RepUCB from the fixed reward setting to the adversarial reward setting. The main idea of the algorithm is to replace the greedy policy in RepUCB to an incremental policy update with exponential weights. Also, the proposed algorithm interleaves exploration and exploitation to obtain low regret. ", "questions": "See the above sections. ", "limitations": "There is no societal limitation. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- This is an elegant generalization of RepUCB to the adversarial setting. It is also the first paper that simultaneously deals with non-linear function approximation and adversarial losses. ", "weaknesses": "- The technical novelty is a bit limited -- Given OPPO and POWERS, it becomes more or less clear that the key technique for unknown transition + full-information loss feedback setting is to ensure optimism and use a no-regret algorithm over the optimistically-biased losses. Though the form of optimism in low-rank MDP (i.e., optimism only in the initial state) is slightly different from those in linear mixture MDP, with full-information loss feedback, the key challenges is already resolved in RepUCB. It is not surprising that most of the analysis follows those of RepUCB except for the OMD regret term. \n- The proposed algorithm performs an epsilon-greedy styled exploration, which leads to a sub-optimal $K^{3/4}$ regret bound. To improve the technical novelty, I think the paper should try to design some less trivial exploration scheme and improve over the $K^{3/4}$ bound. Another direction to improve the technical novelty is to study the bandit feedback case.  \n- The comparison with Rep-UCB around Line 259-268 and the comment that your algorithm is tighter in $d, A, \\gamma$ is slightly off. The reason is that your bound is better than RepUCB only when $K^{3/4}A^{1/2}d/(1-\\gamma) < d^{4/3}A^{2/3}K^{2/3}/(1-\\gamma)^{4/3}$, which is equivalent to $K<d^4A^2/(1-\\gamma)^4$. In this regime, both regret bounds $K^{3/4}A^{1/2}d/(1-\\gamma)$ and $d^{4/3}A^{2/3}K^{2/3}/(1-\\gamma)^{4/3}$ are at least $K$, meaning that this is an *vacuous* regime where both regret bounds are meaningless. In other words, there is no case your regret bound is better than that of RepUCB. If we calculate the sample complexity, the two algorithms would give $\\frac{A^2d^4}{(1-\\gamma)^4\\epsilon^4}$ and $\\frac{A^2d^4}{(1-\\gamma)^4\\epsilon^3}$ respectively, so there is actually no improvement in terms of $d, A, (1-\\gamma)$. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments and suggestions. Our response to each question is provided in turn below.\n\n**Q1. \"The technical novelty is a bit limited.\"**\n\nAs previous works studying adversarial linear mixture MDPs using policy-optimization (PO) based methods [1,2] relying upon some ingredients of the analyses in stochastic linear mixture MDPs [3,4], our work also relies upon some ingredients of the analyses in stochastic low-rank MDPs [5]. Besides, we would also like to note that our work is not a straightforward combination of Rep-UCB and previous PO-based methods, and new ingredients are needed to achieve our regret guarantee, due to the technical issue which is unique to low-rank MDPs. In specific, as discussed in Section 4.1 and 5.1, the original Rep-UCB algorithm only has a sample complexity guarantee but does not enjoy a regret guarantee in both stochastic and adversarial environments, due to its uniform exploration in each episode. Moreover, a common ETC-style adaption of Rep-UCB also only attains an $\\widetilde{O}(K^{2/3})$ regret in stochastic environments, but committing to a fixed loss function makes it still fail to be extended to adversarial environments. Therefore, directly applying previous PO-based methods [1,2] together with the current Rep-UCB algorithm does not go through our problem. Further, to tackle this issue, our algorithmic design features a new *doubled exploration and exploitation* scheme, which leverages a mixed roll-out policy to simultaneously conduct (a) the uniform exploration over transitions required by representation learning; and (b) the exploration and exploitation over adversarial loss functions. As discussed in Section 4.1 and 5.1, this is critical to achieving our final regret guarantee.\n\nMoreover, we now provide a regret lower bound for learning low-rank MDPs, which is the first regret lower bound for low-rank MDPs and together with our regret upper bound provides a more complete characterization of regret minimization for low-rank MDPs. Please see this in our response to reviewer n9xa.\n\n**Q2. \"The proposed algorithm performs an epsilon-greedy styled exploration...To improve the technical novelty...\"**\n\nIndeed, our doubled exploration and exploitation scheme is similar in spirit to the epsilon-greedy-styled exploration. However, we would also like to note that actually, they are inherently not the same, since the epsilon-greedy styled exploration will only conduct exploitation in certain rounds but our doubled exploration and exploitation scheme will always conduct exploration in all rounds, which will be either the exploration required by representation learning or the exploration (and exploitation) required to tackle the adversarial loss functions. \n\nAs we discussed in Section 6, we do believe further optimizing the current dependence on $K$ and studying the bandit feedback case are interesting and important next steps. However, we would like to remark that our $\\widetilde{O}(K^{3/4})$ regret guarantee obtained by the PO-based method is valuable and meaningful, especially considering that it is the first result for RL with both nonlinear function approximation and adversarial loss functions. In fact, the SOTA regret guarantee obtained by the PO-based method for the more amenable adversarial linear MDPs with given underlying feature mappings in the full-information setting is $\\widetilde{O}(K^{3/4})$, as shown by a concurrent work [6]. Our algorithm obtains the regret guarantee with the same dependence on $K$ and can additionally work when no true feature mappings are known a priori. For the bandit feedback case, due to the local-search nature of PO-based methods, the current PO-based methods for adversarial linear MDPs [7,8,9] depend on the *dilated* exploration bonuses (and its variants), which critically rely on the given underlying true feature mappings, to facilitate global exploration. These PO-based methods are thus not applicable to our problem, with no true feature mappings given a priori. Moreover, we would like to note that, even with the true feature mappings given, learning adversarial linear MDPs with bandit feedback is already rather challenging, where the SOTA regret achieved by the PO-based method is only of $\\widetilde{O}(K^{6/7})$ order [9] when no exploration conditions are given. Overall, learning adversarial low-rank MDPs with bandit feedback is indeed interesting and also particularly challenging, and we believe our work may serve as an important step to further tackle this problem, which we leave as our future study.\n\n**Q3. \"The comparison ... is slightly off.\"**\n\nThank you again for pointing this out. Though we mainly focus on learning low-rank MDPs in adversarial environments, the comparison between the regret guarantee of our algorithm and that of the ETC-style adaption of Rep-UCB in stochastic environments is indeed not accurate, and we will improve our statement on Line 264-266 accordingly in the revised version of our paper. \n\n\n\n[1] Cai et al. Provably Efficient Exploration in Policy Optimization. ICML, 20.\n\n[2] He et al. Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPs. AISTATS, 22.\n\n[3] Ayoub et al. Model-Based Reinforcement Learning with Value-Targeted Regression. ICML, 20.\n\n[4] Zhou et al. Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes. COLT, 21.\n\n[5] Uehara et al. Representation learning for online and offline RL in low-rank mdps. ICLR, 22.\n\n[6] Zhong et al. A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes. arXiv, 23.\n\n[7] Luo et al. Policy optimization in adversarial mdps: Improved exploration via dilated bonuses. NeurIPS, 21.\n\n[8] Dai et al. Refined Regret for Adversarial MDPs with Linear Function Approximation. ICML, 23.\n\n[9] Sherman et al. Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation. ICML, 23."}, {"review_id": "UG3hQXkW7F", "reviewer": "Reviewer_n9xa", "summary": "The authors consider the problem of learning an adversarial low-rank infinite episodic MDP with unknown transition and full information feedback. \nThe idea behind this problem is that in many RL applications, the state and action spaces might be prohibitively large, rending results that scale with these metrics meaningless. Several approaches have used the assumption that there is a feature mapping state-action pairs to a low dimensional embedding space. While the common practice is to assume that this embedding is known, in the present problem the learner has to learn how the data is represented. \nThe second challenge faced by the learner is that the loss functions change adversarially. These two challenges have been studied separately, but this work is the first to study them simultaneously. \n\nTo do so, they work under the assumption that there exists an unknown low-rank embedding of the state-action pairs and propose an algorithm to tackle this problem: Policy Optimization for LOw rank MDPS (POLO). This algorithm relies on the standard Online Mirror Descent technique, combined with a bonus function which lowers the observed losses to favorize exploration.\n\nThe authors then provide a rigourous analysis of the regret and show that their algorithm reaches sublinear regret. \nThe regret analysis follows a standard  decomposition of the regret into an estimation bias term, the OMD regret term and an optimism term, which respectively compare the true value function with the eztimated value function of the policy played by the learner, the difference between the performance of the policy played by the learner and the best policy in hindsight on the estimated value function, and finally the  difference between the estimated value function and the true value function for the best policy. \n", "questions": "Is there a lower bound for this problem, and could you elaborate on the cost of learning the representation? ", "limitations": "The authors provided an interesting discussion of the potential limitations of their work and addressed them adequately. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper tackles a new and challenging problem by combining two notably difficult aspects of online learning with MDPs: handling adversarial losses and having to learn the state-action mapping. Each of these problems has received a lot of attention in the past few years and are really relevant for the online learning  community.\n\nThe authors achieve their goal by presenting an algorithm that adapts to both of these aspects simultaneously and obtains sublinear regret.\nThe algorithm that they present buil;dss upon standard tools in the litterature and has an appreciably clear and compact analysis. \n\nThe authors properly discuss the limitations of their work, notably by questioning the computational efficiency of their approach and ensuring that their algorithm is coomputationally feasible. \n\nOverall, this paper will provide a good baseline for the problems of representation learning of MDPs in adversarial environments.\n", "weaknesses": "It would be interesting to provide a the lower bound for the problem: from the simple online learning with full information feedback, having at least $\\sqrt{K}$ regret from playing adversarial losses is unavoidable.  In this work, it is stated that the first term in the regret bound, which scales with $K^{3/4}/(1 - \\gamma)$ comes from learning the unknown transition kernel $P^\\star$. Do you have a lower bound for this part the representation learning part of the problem?\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments and suggestions. Our response to each question is provided in turn below.\n\n**Q1. \"Is there a lower bound for this problem, and could you elaborate on the cost of learning the representation?\"**\n\nWe now provide a lower bound for the representation learning part of the problem, in the setting of learning low-rank MDPs with deterministic reward functions, which thus also serves as a regret lower bound for learning adversarial low-rank MDPs with full-information feedback. To the best of our knowledge, this is the first regret lower bound for low-rank MDPs. At a high level, we construct $dA$ hard MDP instances, which are difficult to distinguish in KL divergence but have very different optimal policies. Similar instances are first introduced to prove the regret lower bounds for tabular MDPs [1,2] and are recently used to prove the lower bound of sample complexity for learning low-rank MDPs by [3].\n\n**Theorem 1** (Regret Lower Bound)\n\nSuppose $d\\geq 8$, $S\\geq d+1$, $A\\geq d-3$, and $K\\geq 2(d-4)A$. Then for any algorithm $\\operatorname{Alg}$, there exists an episodic infinite-horizon low-rank MDP $\\mathcal{M}_{\\operatorname{Alg}}$ with fixed reward function such that the expected regret for this MDP is lower bounded by $\\Omega\\left(\\frac{\\gamma^2}{1-\\gamma} \\sqrt{d A K}\\right)$.\n\n**Remark 1** \nWe note that this regret lower bound can hold when $d\\ll S$ and $d\\ll A$, which thus means that this lower bound is non-trivial. Besides, our Theorem 5.1 matches the regret lower bound in $A$ up to a logarithmic factor but looses a factor of $\\widetilde{O}(K^{1/4}d^{1/2}/\\gamma^2)$. More importantly, compared with the regret upper bound $\\widetilde{O}\\left(d \\sqrt{ K/(1-\\gamma)^3}\\right)$ of linear MDPs [5] (the finite horizon $H$ is substituted by the effective horizon $\\Theta(1/(1-\\gamma))$), the dependence on $A$ in the regret lower bound of low-rank MDP shows a clear separation between low-rank MDPs and linear MDPs, which demonstrates that low-rank MDPs are statistically more difficult to learn than linear MDPs in the regret minimization setting.\n\n**Proof of Theorem 1**\nTo begin with, we first construct a reference low-rank MDP $\\mathcal{M}_0$, with its elements detailed as follows:\n\n* State space: \n$\\mathcal{S}=\\\\{s_{1,1},s_{2,1},s_{2,2},\\ldots,s_{2,d-4}\\\\}\\cup\\\\{s_g,s_b\\\\}\\cup\\\\{s_o\\\\}\\cup\\mathcal{S}_{\\mathcal{O}}$, \nwhere \n \n$\\mathcal{S}_{\\mathcal{O}}= \\{s_{o,i}\\}_{i=1}^{S-d}$ \n\ndenotes the set of 'outlier states', $s_g$ denotes the 'good state', and $s_b$ denotes the 'bad state'.\n* Action space: $\\mathcal{A}=\\\\{a_1,a_2,\\ldots,a_{A}\\\\}$.\n* Reward function: $r(s,a)=\\mathbb{I}\\\\{s=s_g\\\\}+\\frac{1}{2}\\mathbb{I}\\\\{s\\in\\mathcal{S}_{\\mathcal{O}}\\\\}$.\n* Transitions: \n  * For the initial state $s_{1,1}$, the learner will deterministically transit to state $s_{2,i}$ if taking action $a_i$, $\\forall i\\in[d-4]$, and will transit to state $s_o$ otherwise. Formally, $P^\\star\\left(s_{2,i} \\mid s_{1,1}, a_i\\right)=1$, $\\forall i\\in[d-4]$, and $P^\\star\\left(s_o \\mid s_{1,1}, a_i\\right)=1$, $\\forall i\\in[A]\\setminus[d-4]$.\n  * For state $s_{2,i}\\in\\\\{s_{2,1},s_{2,2},\\ldots,s_{2,d-4}\\\\}$, the learner will transit to good state $s_{g}$ and bad state $s_b$ uniformly at random, no matter what action it takes, $\\textit{i.e.}$, $P^\\star\\left(s_{g} \\mid s_{2,i}, a\\right)=P^\\star\\left(s_{b} \\mid s_{2,i}, a\\right)=\\frac{1}{2}$, $\\forall i\\in[d-4]$ and $a\\in\\mathcal{A}$.\n  * For states $s_o$ and $s_{o,i}\\in\\mathcal{S}_{\\mathcal{O}}$, the learner will uniformly transit to a state\n\n $s_{o,j}\\in\\mathcal{S}_{\\mathcal{O}}$, \nno matter what action it takes. \n\nFormally, $P^\\star\\left(s_{o,j} \\mid s_o, a\\right)=P^\\star\\left(s_{o,j} \\mid s_{o,i}, a\\right)=\\frac{1}{S-d}$, $\\forall s_{o,i},s_{o,j}\\in\\mathcal{S}_{\\mathcal{O}}$ and $a\\in\\mathcal{A}$.\n  * For states $s_g$ and $s_b$, the learner will stay at the current state no matter what action it takes, which means that $P^\\star\\left(s_{g} \\mid s_g, a\\right)=P^\\star\\left(s_{b} \\mid s_{b}, a\\right)=1$.\n\nFurther, the transitions of the above MDP can be realized by $P^\\star(s^\\prime\\mid s,a)=\\langle\\phi^\\star(s,a),\\mu^\\star(s^\\prime)\\rangle$, with the following features, which thus implies that this MDP is indeed a low-rank MDP:\n\n$\\mu^\\star(s_{2,i})=\\mathbf{e}_i,\\forall i\\in[d-4]$\n\n$\\mu^\\star(s_{1,1})=\\mathbf{0}$\n\n$\\mu^\\star(s_o)=(0,\\ldots, 0,1,0)$\n\n$\\mu^\\star(s_g)=(0, \\ldots, 0,1,0,0,0)$\n\n$\\mu^\\star(s_b)=(0, \\ldots, 0,0,1,0,0)$\n\n$\\mu^\\star(s_{o,j})=(0,\\ldots,0,1)$\n\n$\\phi^\\star(s_{1,1},a_i)=\\mathbf{e}_i,\\forall i\\in[d-4]$\n\n$\\phi^\\star(s_{1,1},a_i)=(0,\\ldots, 0,1,0),\\forall i\\in[A]\\setminus[d-4]$\n\n$\\phi^\\star\\left(s_{2,j}, a\\right)=(0, \\ldots, 0, \\frac{1}{2}, \\frac{1}{2}, 0,0),\\forall a\\in \\mathcal{A}$\n\n$\\phi^\\star(s_o,a)=\\phi^\\star(s_{o,j},a)=(0,\\ldots,0,\\frac{1}{S-d}),\\forall a\\in \\mathcal{A}$\n\n$\\phi^\\star(s_g,a)=\\mu^\\star(s_g),\\forall a\\in \\mathcal{A}$\n\n$\\phi^\\star(s_b,a)=\\mu^\\star(s_b),\\forall a\\in \\mathcal{A}$\n\nBased on the reference MDP $\\mathcal{M}_0$, we define other low-rank MDP instances \n\n$\\mathcal{M}_{(i^\\ast,a^\\ast)}$, $\\forall (i^\\ast,a^\\ast)\\in[d-4]\\times \\mathcal{A}$. \nIn specific, the only difference between \n\n$\\mathcal{M}_{(i^\\ast,a^\\ast)}$ \nand \n$\\mathcal{M}_0$ \n\nis that $\\phi^\\star(s_{2,i^\\ast},a^\\ast)=(0, \\ldots, 0, \\frac{1}{2}+\\varepsilon, \\frac{1}{2}-\\varepsilon, 0,0)$, such that $P^\\star\\left(s_g \\mid s_{2,i^\\ast}, a^\\ast\\right)=\\frac{1}{2}+\\varepsilon$, $P^\\star\\left(s_b \\mid s_{2,i^\\ast}, a^\\ast\\right)=\\frac{1}{2}-\\varepsilon$, for some $\\varepsilon>0$ to be defined later.\n\nIn what follows, we denote by\n$\\mathbb{P}_{\\left(i^*, a^*\\right)} \\triangleq$\n\n$\\mathbb{P}_{\\operatorname{Alg},\\mathcal{M}_{\\left(i^*, a^*\\right)}}$\n\nthe probability measure over the outcomes induced by the interaction between\n$\\operatorname{Alg}$ and \n$\\mathcal{M}_{\\left(i^*, a^*\\right)}$, (please see the remaining proof in our 'global' response in the above)\n\n"}, {"review_id": "LYuUCAJ7vh", "reviewer": "Reviewer_ci4p", "summary": "This work focuses on the low-rank MDPs with adversarial losses in the full-information feedback setting. Different from the previous work which assumes known features, this work considers the combination of representation learning and regret minimization problem, and is of the first result under this specific topic. \n\nThe low-rank MDPs are defined in Definition 3.1, which admit certain low-rank feature structure that the transition dynamics can be presented with respect to two feature embedding functions. As described in the interaction protocol, the learner does not have accesses to the feature functions, and is required to learn these functions via the interaction between the environment. \n\nWhile the learner has to collect enough samples to estimate the feature functions, the goal of the learner is to minimize her regret (defined in Line 201), that is, the difference between the cumulative loss suffered, and that of the optimal policy in hindsight. The loss functions are selected adversarially   that can change from episode to episode arbitrarily. \n\nTo tackle these two problems simultaneously, the authors combine the techniques of representation learning and the RL with linear MDPs and adversarial losses together into Algorithm 1. Line 5-10 follow the idea of Uehara et al. [2022] to collect the samples for representation learning, Line 11-17 follow the idea of learning adversarial Linear MDPs like the work of Cai et al. [2020], given the estimated feature functions solved in Eq. (1). \n\nThe result is presented in Theorem 5.1, which guarantees that the regret of Algorithm 1 is bounded by $\\widetilde{\\mathcal{O}}( \\frac{K^{3/4}}{1-\\gamma} + \\frac{\\sqrt{K}}{(1-\\gamma)^2})$, where the first term is attributed to the representation learning of unknown features, and the second term is for the adversarial losses. ", "questions": "1. This result $\\mathcal{O}(K^{3/4})$ does not match the $\\sqrt{K}$ regret lower bound for the adversarial losses. Any specific conjecture on the lower bound/upper bound? \n2. Any conjecture on the bandit feedback setting when limited the MDPs to the linear Mixture MDPS of Zhao et al. [2023]? \n3. The loss function $\\ell_k$ is designed as a function of $ S \\times A \\rightarrow [0,1]$, which does not admit the linear structure. Any idea to improve the result given the fact that $\\ell_k(s,a) = \\theta_k^\\top \\phi^\\star(s,a) $ when $\\theta_k$ is revealed at the end of the episode $k$? \n4. The second term in the regret bound, comparing with the regret bound of OPPO and LSUOB-REPS, shaves a factor of $d$? Could you explain why this holds true, and whether this implies that your algorithm achieves better performance given the feature functions? ", "limitations": "This work is pure theoretical, does not have any potential negative societal impact. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Prior to this work, it is unknown whether the regret minimization problem and the representation learning problem can be dealt simultaneously with adversarial losses. This work is the first one to achieve sub-linear regret, which sheds light on this direction. \n2. Based on the previous works on the representation learning of MDPs (such as Uehara et al. [2022] and Agarwal et al. [2020]), and on the linear MDPs (or low-rank MDPs) with adversarial losses (such as Cai et al. [2020] and Luo et al. [2021a]), the authors combine the techniques of these two fields hierarchically, under a novel scheme `doubled exploration and exploitation', to address the regret minimization problem. ", "weaknesses": "1. The designed algorithm suffers from huge computation cost (Line 13, 15, 16, and 17) when the state space is very large, which is the same as the previous algorithm OPPO in the previous work of Cai et al. [2020]. It is not very clear whether this could be improved with any planner oracle. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments and suggestions. Our response to each question is provided in turn below.\n\n**Q1. \"The designed algorithm suffers from huge computation cost ....\"**\n\nIndeed, our algorithm has nearly the same computation efficiency as previous works studying policy-optimization (PO) methods for RL with linear function approximation and adversarial losses [1,2], except for the MLE procedure over the experienced transitions proceeded on Line 13 of our algorithm, which might be an additional computation bottleneck due to its nonconvex nature. However, as mentioned in Section 7, the same MLE procedure is also required in previous works studying low-rank MDPs [3,4,5], arising from the fact that the underlying feature mappings are no longer known a priori in low-rank MDPs. More importantly, though being a nonconvex optimization problem, the MLE procedure can be approximately solved by gradient descent methods (*e.g.*, using neural networks), which is thus computationally feasible in practice.\n\n**Q2. \"Any specific conjecture on the lower bound/upper bound?\"**\n\nWe conjecture that the part dealing with adversarial losses in our regret upper bound is tight. Besides, the dependence on action space size $A$ of the part in our upper bound dealing with representation learning is tight as shown by our upper bound as well as our new regret lower bounds (please see this in our response to reviewer n9xa), and we conjecture that the dependence on $\\gamma$ of this part in our upper bound is tight but the dependence on $K$ might be further improved.\n\n**Q3. \"Any conjecture on the bandit feedback setting when limited the MDPs to the linear Mixture MDPS of Zhao et al. [2023]?\"**\n\nWhen learning in linear Mixture MDPS with given true feature mapping, we can construct ellipsoid confidence sets of transitions so as to construct optimistically biased loss estimates to tackle bandit feedback as in [7], but this is not aligned with our motivation to study adversarial RL where the true feature mappings are not known a priori, and thus beyond the scope of our paper.\n\n**Q4. \"Any idea to improve the result given the fact that $\\ell_k(s, a)=\\theta_k^{\\top} \\phi^{\\star}(s, a)$ when $\\theta_k$ is revealed at the end of the episode $k$?\"**\n\nSince we study adversarial low-rank MDPs with full-information feedback, imposing structural assumptions over loss functions or not actually does not affect the polynomial dependence on the number of entries of the loss functions. Indeed, due to our Lemma 5.1, the regret contributed by dealing with the adversarial loss functions does not have polynomial dependence on $S$ or $A$. In fact, as shown by, for example, Proposition 28.6 and 28.7 in [6], optimizing the online linear optimization problem with full-information feedback using OMD leads to no polynomial dependence on the number of entries of the loss functions in the unit-ball and probability simplex space, even if there are no structural assumptions imposed over the loss functions. On the other hand, in the bandit feedback case, additional structural assumptions over the loss functions are indeed needed to lift the dependence on the number of entries of the loss functions.\n\n**Q5. \"The second term in the regret bound, comparing with the regret bound of OPPO and LSUOB-REPS, shaves a factor of $d$? Could you explain why this holds true, and whether this implies that your algorithm achieves better performance given the feature functions?\"**\n\nIndeed, the second term in our upper bound does not depend on $d$, but this does not mean that our regret upper bound shaves a factor of $d$, compared with previous works [1,2,7]. Specifically, in adversarial environments with full-information feedback, the regret contributed by dealing with the adversarial losses (*i.e.*, the OMD Regret Term in Eq. (4) of our paper) does not have polynomial dependence on dimension $d$ as well as $S$ and $A$, as previous works studying adversarial linear mixture MDPs with full-information feedback [1,2]. For instance, the analogous term in [2] is their term $I_1$, which can be bounded by $\\widetilde{O}(H^2\\sqrt{K})$ as shown in their Section 6 and thus corresponds to our second term $\\widetilde{O}(\\sqrt{K}/(1-\\gamma)^2)$. For the dependence on $d$ of regret in [1,2], it mainly comes from the difference between the values of the same policy in the learned and true models, which results from the model error and corresponds to the Estimation Bias Term in Eq. (4) of our paper. Such dependence on $d$ appears in both their bounds and the first term in our bound. For the dependence on $d$ in [7], it comes from the estimation error between the occupancy measures induced by the learned model and true model respectively, which is thus also due to the model error. In a nutshell, the fact that there is no polynomial dependence on $d$  in the second term of our regret upper bound does not conflict with the results in previous works. For the same reason, it might not be appropriate to interpret this as that our algorithm will achieve better performance given the feature functions. \n\nThanks for pointing this out and we will include the above discussions in the revision of our paper for clarity.\n\n\n\n[1] Cai et al. Provably Efficient Exploration in Policy Optimization. ICML, 20.\n\n[2] He et al. Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPs. AISTATS, 22.\n\n[3] Agarwal et al. FLAMBE: structural complexity and representation learning of low rank mdp. NeurIPS, 20.\n\n[4] Uehara et al. Representation learning for online and offline RL in low-rank mdps. ICLR, 22.\n\n[5] Ni et al. Representation learning for general-sum low-rank markov games. ICLR, 23.\n\n[6] Lattimore et al. Bandit algorithms. Cambridge University Press, 20.\n\n[7] Zhao et al. Learning adversarial linear mixture markov decision processes with bandit feedback and unknown transition. ICLR, 23."}, {"review_id": "dRXkzPiLC3", "reviewer": "Reviewer_aWbZ", "summary": "The paper studies low-rank MDPs with adversarially changing losses in the full-information feedback setting. They assume the unknown transition probability function admits a low-rank matrix decomposition. They present POLO algorithm, a policy optimization-based algorithm, and prove it has sublinear regret in the number of episodes $K$, but linear dependency in $d$ which is the rank of the transition kernel. The regret is w.r.t the optimal policy for the discounted return value function.\nThe authors claim they are the first to present and algorithm that interleaves representation learning, exploration, and exploitation to achieve the sublinear regret  guarantee for RL with nonlinear function approximation and adversarial losses.\n", "questions": "1.\tWhat is the difference between low-rank MDPs to Generalized Linear Model? As I see it, GLM is more general model. Do your results hold for this setting as well?\n2.\tSame question for low Bellman rank MDPs, that also seem to generalize low-rank MDPs.\n3.\tDo you have thoughts about how to remove the full-information assumption? \n", "limitations": "n/a", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.\tPOLO is the first algorithm that achieves sublinear regret with unknown features (although the setting is full information).\n2.\tThe authors provide a clear comparison between their work to previous works in the area, which emphasis their contribution.\n3.     Regret upper bound stated clearly, the analysis sketch is standard and clear (not fully checked).\n", "weaknesses": "1.\tThe full information feedback is a restrictive and unrealistic assumption.\n2.\tThe extensive literature review in Section 2 can be shorter, and instead use that space to have more proof sketches. That, in my opinion, can benefit the reader.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments and suggestions. Our response to each question is provided in turn below.\n\n**Q1. \"The full information feedback is a restrictive and unrealistic assumption.\"**\n\nWe do believe that extending the analysis of our work to the bandit feedback case is an interesting and important next step, as mentioned in Section 6. However, we would like to note that, even if in linear mixture MDPs with given true feature mappings, it is also common to first study adversarial environments with full-information feedback [1,2], before moving to the bandit feedback case [3]. Moreover, the SOTA regret guarantee obtained by policy optimization (PO) based methods for the more amenable adversarial linear MDPs with given true features in the full-information setting is $\\widetilde{O}(K^{3/4})$ (omitting other dependence), as shown by a concurrent work [4]. Our algorithm obtains the regret guarantee with the same dependence on $K$ and can additionally work when no true feature mappings are known a priori. Besides, we would like to remark that, learning adversarial linear MDPs with bandit feedback is already rather challenging even with the true feature mappings given, where the SOTA regret is only of $\\widetilde{O}(K^{6/7})$ order [5] (to the best of our knowledge) when no simulators or exploratory assumptions are given.\n\n**Q2. \"The extensive literature review in Section 2 can be shorter, ... can benefit the reader.\"**\n\nWe will revise our paper accordingly to make Section 2 more succinct and include more proof sketches for better readability. In specific, we plan to (a) merge Section 2.1 and 2.2 into a new section; and (b) include more proof sketches and discussions of our Theorem 5.1 and related key lemmas in Section 5.\n\n**Q3. \"What is the difference between low-rank MDPs to Generalized Linear Model? ...\"**\n\nIn GLMs, it is assumed that $\\mathbb{E}[Y \\mid X]=\\mu\\left(X^\\top \\theta^\\star\\right)$, where $\\theta^\\star \\in \\mathbb{R}^d$ is the unknown parameter, $X$ is the **known** feature vector, $Y$ is the response variable, and $\\mu: \\mathbb{R} \\rightarrow \\mathbb{R}$ is the link function. On the other hand, in low-rank MDPs, the transition $P^\\star$ is assumed to admit a low-rank decomposition, meaning that $\\mathbb{E}[\\mathbb{I}\\{s=s_{t+1}\\} \\mid s_t,a_t]=\\mu^{\\star}\\left(s\\right)^{\\top} \\phi^{\\star}(s_t, a_t)$, where both the feature vectors $\\mu^{\\star}\\left(s\\right)$and $ \\phi^{\\star}(s_t, a_t)$ are **unknown**. Therefore, in general, these two models can not imply each other and the results for each model might not be directly comparable.\n\n**Q4. \"Same question for low Bellman rank MDPs, ...\"**\n\nIndeed, there exist some other works studying RL with general function approximation [6,7,8], which subsumes low-rank MDPs as a special case. However, we note that the algorithms in these works are version space algorithms and thus are generally not computationally efficient. In contrast, the algorithms in previous works studying low-rank MDPS including ours are computationally feasible in practice, as discussed in our Section 7. Besides, they assume deterministic reward functions, and thus their results are not applicable in our setting.\n\n**Q5. \"Do you have thoughts about how to remove the full-information assumption?\"**\n\nTo tackle bandit feedback, if we restrict our attention to PO-based methods, one may consider the *dilated* bonuses to facilitate improved global exploration, which is vital for current PO-based methods to learn adversarial linear MDPs with bandit feedback [9,10,5]. Nevertheless, the construction of such dilated bonuses critically relies on the unknown true feature mapping $\\phi^\\star(\\cdot,\\cdot)$, and thus it is currently not clear whether they can be extended to low-rank MDPs. Also, as aforementioned, the SOTA regret of such methods to learn adversarial linear MDPs with bandit feedback is only of $\\widetilde{O}(K^{6/7})$ order [5]. Besides, if occupancy measure-based methods are also under consideration, the feasible way might be constructing some sort of confidence set for the learned empirical transitions, like the confidence intervals constructed in tabular MDPs [11] and the ellipsoid confidence sets constructed in linear mixture MDPs [3], to construct optimistically biased loss estimates to tackle bandit feedback. However, as mentioned in Section 6, it is also not very clear how to guarantee such point-wise optimism at each state-action pair in low-rank MDPs. Overall, learning adversarial low-rank MDPs with bandit feedback is indeed interesting and also particularly challenging, and we believe our work may serve as an important step to further tackle this problem, which we leave as our future study.\n\n\n[1] Cai et al. Provably Efficient Exploration in Policy Optimization. ICML, 20.\n\n[2] He et al. Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPs. AISTATS, 22.\n\n[3] Zhao et al. Learning adversarial linear mixture markov decision processes with bandit feedback and unknown transition. ICLR, 23.\n\n[4] Zhong et al. A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes. arXiv, 23.\n\n[5] Sherman et al. Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation. ICML, 23.\n\n[6] Jiang et al. Contextual decision processes with low bellman rank are pac-learnable. ICML, 17.\n\n[7] Sun et al. Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. COLT, 19.\n\n[8] Du et al. Bilinear classes: A structural framework for provable generalization in rl. ICML, 2021.\n\n[9] Luo et al. Policy optimization in adversarial mdps: Improved exploration via dilated bonuses. NeurIPS, 21.\n\n[10] Dai et al. Refined Regret for Adversarial MDPs with Linear Function Approximation. ICML, 23.\n\n[11] Jin et al. Learning Adversarial Markov Decision Processes with Bandit Feedback and Unknown Transition. ICML, 20."}]

Author rebuttal:
**Proof of the Regret Lower Bound (Cont.)**
and by 
$\mathbb{E}_{\left(i^*, a^*\right)} \triangleq$

$ \mathbb{E}_{\operatorname{Alg}, \mathcal{M}_{\left(i^*, a^*\right)}}$ 

the expectation with respect to $\mathbb{P}_{\left(i^*, a^*\right)}$.

**Step 1: Regret of $\operatorname{Alg}$ over $\mathcal{M}_{(i^\ast,a^\ast)}$** 
For some $\mathcal{M}_{(i^\ast,a^\ast)}$, 
its optimal policy 

$\pi^\ast_{(i^\ast,a^\ast)}:\mathcal{S}\to\mathcal{A}$ 

satisfies that $\pi^\ast_{(i^\ast,a^\ast)}(s_{1,1})=a_{i^\ast}$ and $\pi^\ast_{(i^\ast,a^\ast)}(s_{2,i^\ast})=a^\ast$, with the optimal value function

$$
\begin{align}
V_{0}^*(s_{1,1}) & =\mathbb{E}\left[\sum_{\tau=0}^{+\infty} \gamma^\tau r(s_{\tau}, a_\tau) \mid \pi^\ast_{(i^\ast,a^\ast)},P^\star_{(i^\ast,a^\ast)}, s_0=s_{1,1}\right]=\sum_{\tau=2}^{+\infty} \gamma^\tau \left(\frac{1}{2}+\varepsilon\right)=\frac{\gamma^2}{1-\gamma}\left(\frac{1}{2}+\varepsilon\right).\tag{1}\label{eq:lb_eq1}
\end{align}
$$

For some policy $\pi$, it is also clear that its value function satisfies

$V_{0}^\pi(s_{1,1})$

$$
=\frac{\gamma^2}{1-\gamma}(\frac{1}{2}+\varepsilon\mathbb{P}_{(i^*, a^*)}((s_2,a_2)=(s_{2,i^*},a^*))).\tag{2}\label{eq:lb_eq2}
$$


Combining Eq. $\eqref{eq:lb_eq1}$ and Eq. $\eqref{eq:lb_eq2}$ shows that the regret of 
$\operatorname{Alg}$ in $\mathcal{M}_{(i^\ast,a^\ast)}$ 
satisfies

$R_K(\operatorname{Alg}, \mathcal{M}_{(i^\ast,a^\ast}))$

$$
=\frac{\gamma^2\varepsilon}{1-\gamma}K\left(1-\frac{1}{K}\mathbb{E}_{(i^*,a^*)}\left[N^K_{(i^*,a^*)} \right]\right)\notag\,,
$$

where we define $N^K_{(i^\ast,a^\ast)}= \sum_{k=1}^K\mathbb{I}\{(s^k_2,a^k_2)=(s_{2,i^\ast},a^\ast)\}$.

**Step 2: Maximum regret of $\operatorname{Alg}$ over all possible $\mathcal{M}_{(i^\ast,a^\ast)}$**  
With $R_K(\operatorname{Alg}, \mathcal{M}_{(i^\ast,a^\ast}))$ in the above equation, we can deduce that

$$
\begin{align}
    \max_{(i^\ast,a^\ast)}R_K(\operatorname{Alg},\mathcal{M}_{(i^\ast,a^\ast)})&\geq \frac{1}{(d-4)A}\sum_{(i^\ast,a^\ast)}R_K(\operatorname{Alg},\mathcal{M}_{(i^\ast,a^\ast}))\notag\\
    &\geq \frac{\gamma^2\varepsilon}{1-\gamma}K\left(1-\frac{1}{K(d-4)A}\sum_{(i^\ast,a^\ast)}\mathbb{E}_{(i^\ast,a^\ast)}\left[N^K_{(i^\ast,a^\ast)} \right]\right)\,.\tag{3}\label{eq:lb_eq3}
\end{align}
$$

To lower bound the above display, it remains to upper bound 

$\sum_{(i^*,a^*)}\mathbb{E}_{(i^*,a^*)}[N^K_{(i^*,a^*)}]$. 

To this end, by Lemma 1 in the work of [4] together with the fact that $N^K_{(i^\ast,a^\ast)}/K\in[0,1]$, it holds that

$$
\begin{align*}
    \operatorname{KL}\left(\operatorname{Ber}\left(\frac{1}{K}\mathbb{E}_0\left[N^K_{(i^\ast,a^\ast)}\right]\right),\operatorname{Ber}\left(\frac{1}{K}\mathbb{E}_{(i^\ast,a^\ast)}\left[N^K_{(i^\ast,a^\ast)}\right]\right)\right)\leq \operatorname{KL}\left(\mathbb{P}_0,\mathbb{P}_{(i^\ast,a^\ast)}\right)\,.
\end{align*}
$$


This implies that

$$
\begin{align*}
    \frac{1}{K}\mathbb{E}_{(i^\ast,a^\ast)}\left[N^K_{(i^\ast,a^\ast)}\right]
    &\leq \frac{1}{K}\mathbb{E}_0 \left[N^K_{(i^\ast,a^\ast)}\right]+\sqrt{\frac{1}{2}\operatorname{KL}\left(\mathbb{P}_0,\mathbb{P}_{(i^\ast,a^\ast)}\right)}\\
    &=\frac{1}{K}\mathbb{E}_0 \left[N^K_{(i^\ast,a^\ast)}\right]+\varepsilon\sqrt{2}\sqrt{\mathbb{E}_0\left[N^K_{(i^\ast,a^\ast)}\right]}\,,
\end{align*}
$$

where the inequality is due to Pinsker’s inequality that $(p-q)^2 \leq \frac{1}{2} \operatorname{KL}(\operatorname{Ber}(p), \operatorname{Ber}(q))$, for $p,q\in[0,1]$, and the equality comes from Lemma 15.1 of  [1] and Lemma 14 of [2] as well as assuming $0\leq\varepsilon\leq\frac{1}{4}$. 

Based on this, one can see that

$$
\begin{align}
    \frac{1}{K}\sum_{(i^\ast,a^\ast)}\mathbb{E}_{(i^\ast,a^\ast)}\left[N^K_{(i^\ast,a^\ast)}\right]
    &\leq \frac{1}{K}\sum_{(i^\ast,a^\ast)}\mathbb{E}_0 \left[N^K_{(i^\ast,a^\ast)}\right]+\varepsilon\sqrt{2}\sum_{(i^\ast,a^\ast)}\sqrt{\mathbb{E}_0\left[N^K_{(i^\ast,a^\ast)}\right]}\notag\\
    &\leq 1+\varepsilon\sqrt{2}\sqrt{(d-4)AK}\,,\tag{4}\label{eq:lb_eq4}
\end{align}
$$

where the second inequality follows from using the Cauchy-Schwartz inequality together with the fact that $N^K_{(i^\ast,a^\ast)}\leq K$.

**Step 3: Optimizing $\varepsilon$ to lower bound the maximum regret** Substituting Eq. $\eqref{eq:lb_eq4}$ into Eq. $\eqref{eq:lb_eq3}$ leads to

$$
\begin{align*}
    \max_{(i^\ast,a^\ast)}R_K(\operatorname{Alg},\mathcal{M}_{(i^\ast,a^\ast)})
    &\geq\frac{\gamma^2\varepsilon}{1-\gamma}K\left(1-\frac{1}{(d-4)A}-\varepsilon\sqrt{2}\sqrt{\frac{K}{(d-4)A}}\right)\\
    &\geq\frac{1}{4\sqrt{2}}\cdot\frac{\gamma^2}{1-\gamma}\left(1-\frac{1}{(d-4)A}\right)^2\sqrt{(d-4)AK}\\
    &\geq \frac{361}{1600\sqrt{2}}\cdot\frac{\gamma^2}{1-\gamma}\sqrt{(d-4)AK}\,,
\end{align*}
$$
where the second inequality comes from by choosing $\varepsilon=\frac{1}{2\sqrt{2}}\left(1-\frac{1}{(d-4)A}\right)\sqrt{\frac{(d-4)A}{K}}$ and the last inequality is due to $d\geq 8$ and $A\geq d-3$. Finally, note that  $\varepsilon\leq \frac{1}{4}$ is guaranteed when $K\geq 2(d-4)A$. The proof is thus concluded.
**Q.E.D.**

[1] Lattimore et al. Bandit algorithms. Cambridge University Press, 20.

[2] Domingues et al. Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited. ALT, 21.

[3] Cheng et al. Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPs. ICLR, 23.

[4] Garivier et al. Explore first, exploit next: The true shape of regret in bandit problems. Mathematics of Operations Research, 19.

[5] He et al. Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes. ICML, 23.


Meta-review: The paper makes a great first algorithmic contribution in an interesting and practically relevant reinforcement learning setting.
Decision: Accept (poster)