Learning Adversarial Linear Mixture Markov Decision Processes with Bandit Feedback and Unknown Transition
Authors: Canzhe Zhao
Ruofeng Yang
Baoxiang Wang
Shuai Li
Venue: ICLR 2023 poster (2023)
Keywords: Reinforcement learning theory
Reinforcement learning with adversarial losses
Reinforcement learning with linear function approximation

Abstract: We study reinforcement learning (RL) with linear function approximation, unknown transition, and adversarial losses in the bandit feedback setting. Specifically, the unknown transition probability function is a linear mixture model \citep{AyoubJSWY20,ZhouGS21,HeZG22} with a given feature mapping, and the learner only observes the losses of the experienced state-action pairs instead of the whole loss function. We propose an efficient algorithm LSUOB-REPS which achieves $\widetilde{O}(dS^2\sqrt{K}+\sqrt{HSAK})$ regret guarantee with high probability, where $d$ is the ambient dimension of the feature mapping, $S$ is the size of the state space, $A$ is the size of the action space, $H$ is the episode length and $K$ is the number of episodes. Furthermore, we also prove a lower bound of order $\Omega(dH\sqrt{K}+\sqrt{HSAK})$ for this setting. To the best of our knowledge, we make the first step to establish a provably efficient algorithm with a sublinear regret guarantee in this challenging setting and solve the open problem of \citet{HeZG22}.

Published as a conference paper at ICLR 2023
LEARNING ADVERSARIAL LINEAR MIXTURE MARKOV DECISION PROCESSES WITH BANDIT FEEDBACK AND
UNKNOWN TRANSITION
Canzhe Zhao', Ruofeng Yang', Baoxiang Wang", Shuai Li
'John Hopcroft Center for Computer Science, Shanghai Jiao Tong University Schooo of Data Science, The Chinese University of Hong Kong, Shenzhen fcanzhezhao, wanshuiyin shuaili8 sjuuttuuuuuueus.u.. se jtu.u..uuuuuu..... bx bx Sx.langwangechk.. edu.cn
ABSTRACT
We study reinforcement learning (RL) with linear function approximation, un- known transition, and adversarial losses in the bandit feedback setting. Specifically, the unknown transition probability function is a linear mixture model (Ayoub al., 2020; Zhou et al., 2021; He al., 2022) with a given feature mapping, and the learner only observes the losses of the experienced state-action pairs instead of the whole loss function. We propose an efficient algorithm LSUOB-REPS which achieves Óds2 + VHSAK) regret guarantee with high probability, where d is the ambient dimension of the feature mapping, S is the size of the state space, A is the size the action space, H is the episode length and K is the number of episodes. Furthermore, M(dHVK +HSAA)) for this setting. To the best of our knowledge, we make the first step to establish a provably efficient algorithm with a sublinear regret guarantec in this challenging setting and solve the open problem of He al. (2022).
also prove a lower bound of order
INTRODUCTION
Reinforcement learning (RL) has achieved significant empirical success in the fields of games, control, robotics and so on. One of the most notable RL models is the Markov decision process (MDP) (Feinberg, 1996). For tabular MDP with finite state and action spaces, the nearly minimax optimal sample complexity is achieved in discounted MDPs with a generative model (Azar et al., 2013). Without the access of a generative model, the nearly minimax optimal sample complexity is established tabular MDPs with finite horizon (Azar et al., 2017) and in tabular MDPs with infinite horizon (He et al., 2021b; bb; Tossou et al., 2019). However, in real applications of RL, the state and action spaces are possibly very large and even infinite. In this case, the tabular MDPs are known to suffer the curse of dimensionality. To overcome this issue, recent works consider studying MDPs under the assumption of function approximation to reparameterize the values of state-action pairs by embedding the state-action pairs in some low-dimensional space via given feature mapping. In particular, linear function approximation has gained extensive research attention. Amongst these works, linear mixture MDPs (Ayoub et al., 2020) and linear MDPs (Jin al., 2020b) are two of the most popular MDP models with linear function approximation. Recent works have attained the minimax optimal regret guarantee OddH VKH) in both linear mixture MDPs (Zhou et al., 2021) and linear MDPs (Hu et al., 2022) with stochastic losses.
Though significant advances have emerged in learning tabular MDPs and MDPs with linear function approximation under stochastic loss functions, in real applications of RL, the loss functions may not be fixed or sampled from some certain underlying distribution. To cope with this challenge, Even-Dat et al. (2009); Yu et al. (2009) make the first step to study learning adversarial MDPs, where the loss functions chosen adversarially and may change arbitrarily between each step. Most works in this line of research focus on learning adversarial tabular MDPs (Neu et al., 20:0;;b; 2012; Arora
"orresponding author.

---

Published as a conference paper at ICLR 2023
Table 1: Comparisons of regret bounds with most related works studying adversarial tabular and linear mixture MDPs with unknown transitions. K' is the number of episodes, d is the ambient dimension of the feature mapping. S is the size of the state space, A is the size of the action space, and H is the episode length.
Algorithm
Model
Feedback
Regret
Shifted Bandit UC-O-REPS (Rosenberg & Mansour, 2019a)
Tabular MDPs
Bandit
(HMPSAVA33/))
Feedback
UOB-REPS
Tabular MDPs
Bandit
Ō (HSVAK)
(Jin et al., 2020a)
Feedback
OPPO
Linear Mixture
Full-
δ (dH2VR
(Cai et al., 2020)
MDPs
information
POWERS
Linear Mixture
Full-
δ [HH3/2K))
(He et al., 2022)
MDPs
information
LSUOB-REPS (Ours)
Linear Mixture MDPs
Bandit Feedback
ds VK VHSAK
Ω dHHKK + HSAK
et al., 2012; Zimin & Neu, 2013; Dekel & Hazan, 2013; Dick et al., 2014; Rosenberg & Mansour, 2019a;b; Jin & Luo, 2020; Jin et al., 2020a; Shani et al., 2020; Chen et al., 2021; Ghasemi et al., 2021; Rosenberg & Mansour, 2021; Jín al., 2021b; Dai et al., 2022: Chen et al., 2022a). In contrast, most recent advances regarding learning adversarial MDPs with linear function approximation require some stringent assumptions and we are still far from understanding it well. Specifically, Cai al. (2020); He et al. (2022) study learning episodic adversarial linear mixture MDPs with unknown transition but under full cull-infommatin feedback and Neu & Olkhovskaya (2021) study learning episodic adversarial linear MDPs under bandit feedback but with known transition. In the more challenging setting with both unknown transition and bandit feedback, Luo et al. (2021b) Ib) make the first step to establish a sublinear regret guarantee ( in adversarial linear MDPs under the assumption that there exists an exploratory policy and Luo al. (2021a) (an improved version of Luo al. (2021b)) obtain a regret guarantee Ö (K144/15) in the same setting but without access to an exploratory policy. Therefore, natural question remains open:
Does there exist provably efficient algorithm with Ö(vK) regret guarantee for RL with linear function approximation under unknown transition, adversarial losses and bandit feedback?
In this paper, we give an affirmative answer to this question in the setting of linear mixture MDPs and hence solve the open problem of He et (2022). Specifically, we propose an algorithm termed LSUOB-RENT
for adversarial linear mixture MDPs with unknown transition and bandit feedback. To remove the need for the iall-information feedback of the loss function required by policy- optimization-based methods (Cai et al., 2020; He et al., 2022), LSUOB-REPS extends the general methods for adversarial tabular MDPs with unknown transition
ideas of sccupancy-measure-nne (Jin al., 2020a; Rosenberg & Mansour, 2019a;b; Jin et al., 202 Ib). Specifically, inspired by the UC-O-REPS algorithm (Rosenberg & Mansour, 2019b;a), LSUOB-REPS maintains a confidence of the unknown transition and runs online mirror descent (OMD) over the space of occupancy measures induced by all the statistically plausible transitions within the confidence set to handle the unknown transition. The key difference that we need to build some sort of squares estimate of the transition parameter and its corresponding confidence set to leverage the transition structure of the linear mixture MDPs. Previous works studying linear mixture MDPs (Ayoub et al., 2020; Cai et al., 2020; He al., 202 Zhou al., 2021; He et al., 2022: Wu et al., 2022; Chen et al., 2022b; Min et al., 2022) use the state values as the regression targets to learn the transition parameter. This method is critical to construct the optimistic estimate of the state-action values and attain the final regret guarantee. In this way, however, it is difficult to control the estimation error between the occupancy measure computed by OMD and the one that the leamerr really takes.
To cope with this issue, we use the transition information of the next-states as the regression targets to learn the transition parameter. In particular, we pick certain next-state, which we call the imaginary
2

---

Published as a conference paper at ICLR 2023
next-state, and use its transition information the regression target (see Section 4.1 for details). In this manner, we are able to control the occupancy measure error efficiently. Besides, since the true transition is unknown, the true occupancy measure taken by the learner is also unknown and it is infeasible to construct an unbiased loss estimator using the standard importance weighting method. To this end, we use the upper occupancy measure (Jin et al., 2020a) together with a hyperparameter to conduct implicit exploration (Neu, 2015) to construct an optimisticalyy biased loss estimator. Finally, we prove the O(dSVVK + VHSAK) high probability regret guarantee of LSUOB- BERPS, where the size of the state space, the size of the action space, is the episode length, dimension of the feature mapping, and K is the number of the episodes. Further, we also prove a lower bound of order Q(dHV + VHSAK), which matches the upper bound in d, K and A up to logarithmic factors (please see Table 1 for the comparisons between our results and previous ones). Though the upper bound does not match lower bounds in S, we establish the first provably efficient algorithm with O(VK) regret guarantee for learning adversarial linear mixture MDPs under unknown transition and bandit feedback.
the
2 RELATED WORK
RL with Linear Function Approximation To permit efficient learning in RL with large state-action space, recent works have focused on RL algorithms with linear function approximation. In general, these works can be categorized into three lines. The first line uses the low Bellman-rank assumption (Jiang et al., 2017: Dann et al., 2018; Sun et al., 2019; Du et al., 2019; Jin et al., 2021a), which assumes the Bellman error matrix has low-rank factorization. Besides, Du et al. (2021) consider a similar but more general assumption called bounded bilinear rank. The second line considers the linear MDP assumption (Yang& & Wang. 2019; Jin et al., 2020b; Du et al., 2020; Zanette et al., 2020a; Wang et al., 2020; 2021; He et al., 2021a; Hu et al., 2022), where both the transition probability function and the loss function can be parameterized as linear functions of given state-action feature mappings. In particular, Jin et al. (2020b) propose the first statistically and computationally efficient algorithm with V K) regret guarantee. Hu et al. (2022) further improve this result by using weighted ridge regression and Bernstein-type exploration bonus and obtain the minimax optimal regret bound ((dHvKH), Zanette et al. (2020b) consider a weaker assumption called low inherent Bellman error, where the Bellman backup is linear in the underlying parameter up some misspecification errors. The last line of works considers the linear mixture MDP assumption (Ayoub et al., 2020; Zhang al., 2021; Zhou et al., 2021; He et al., 2021a; Zhou & Gu, 2022; Wu et al., 2022; Min et al., 2022), in which the transition probability function is linear in some underlying parameter and a given feature mapping over state-action- next-stte triples. Amongst these works, Zhou et al. (2021) obtain the minimax optimal regret bound Ö / JK /H) in the inhomogeneous episodic linear mixture MDP setting. In this work, we also focus on linear mixture MDPs.
Learning tabular RL with adversarial losses has been well-studied (Neu et al., 2010a;b; 2012; Arora et al., 2012: Zimin & Neu, 2013; Dekel & Hazan, 2013; Dick et al., 2014; Rosenberg & Mansour, 2019a;b; Jin & Luo, 2020; Jin et al., 2020a; Shani et al., 2020; Chen al., 2021: Ghasemi al., 2021; Rosenberg & Mansour, 2021; Jin et al., 2021b; Dai et al., 2022; Chen et al., 2022a). Generally. these results fall into two categories. The first category studies adversarial RL using occupancy- couuaancc-mesuureeeee mewsure- based methods. In particular, with known transition, Zimin & Neu (2013) propose the O-REPS algorithm, which achieves (near) optimal regret Ö(H K) with full-information feedback and Ö(VHS with bandit feedback respectively. With unknown transition and full-information feedback, Rosenberg & Mansour (2019b) propose UC-O-REPS algorithm, and achieve Ö(HSVAK regret guarantee. When the transition is unknown, and only the bandit feedback is available, Rosenberg & Mansour (2019a) propose the bounded bandit UC-O- REPS algorithm and achieve Ö(HS AK /o:) regret bound with the assumption that all states reachable with probability a. Without this assumption, Rosenberg & Mansour (2019a) only achieve ( k3/4) regret bound. Under the same setting but without the strong assumption of Rosenberg& & Mansour (2019a). Jin al. (2020a) develop the UOB-REPS algorithm, which uses a tight confidence set for transition function and a new biased loss estimator and achieves Ö(HS AA)) regret bound. Besides, we remark that the existing tightest lower bound is 2 /SKK) for the unknown transition and aal--inforaation feedback setting (Jin et al., 2018). The second category
RL with Adversarial Losses
3

---

Published as a conference paper at ICLR 2023
for learning adversarial RL is the policy-optimizztion-asssss method (Neu al., 2010a; Shani et al., 2020; Luo et al., 2021b; Chen et al., 2022a), which aims to directly optimize the policies. In this line of research, with known transition and bandit feedback, Neu et al. (2010b) propose OMDP-BF algorithm and achieve regret of order Ö(K2/3). Recently, Shani et al. (2020) establish the POMD algorithm and attain a (OV55AHH* setting, which is further improved to Ô [H'SVAK + H+*) by Luo al. (2021b) in the same setting.
regret bound for unknown transition and bandit feedback
Recent advances have also emerged in learning adversarial RL with linear function approximation (Cai et al., 2020; He et al., 2022; Neu Olkhovskaya, 2021; Luo al., 202 Most of these works study this problem using policy-optimization-aass methods (Cai et al., 2020; Luo et al., 2021a;b; He et al., 2022). Remarkably, He et al. (2022) achieve the (near) optimal ÖddF3//2 VK) regret bound in adversarial linear mixture MDPs in unknown transition but full-information feedback setting. With bandit feedback but known transition, Neu & Olkhovskaya (2021) I) obtain a Ö(v dH K) regret guarantee in linear MDPs by using an oceupancy- -aaayy---aaua-aaseeeeeee based algorithm called Q-REPS. Luo et al. (2021a) make the first step to establish a sublinear regret guarantee Ö (d 14/15) in adversarial linear MDPs with unknown transition and bandit feedback.
PRELIMINARIES
In this section, we present the preliminaries of episodic linear mixture MDPs under adversarial losses.
Inhomogeneous, episodic adversarial MDPs An inhomogeneous, episodic adversarial MDP is denoted by a tuple M = (S, H, 1 {4+) 1). where S is the finite state space with cardinality |S| S, A is the finite action space with cardinality |.A| A, H is the length of each episode, Pa S S A S - [0, 1] is the transition probability function with (s a) being the probability of transferring to state s' from state and taking action a at stage h, and la S x A + [0. 1] is the loss function for episode & chosen by the adversary. Without loss of generality, we assume that the MDP has a layered structure, satisfying the following conditions:
1
The state space S is constituted by H + disjoint layers So.... Su satisfying S = U Sn and S. SS = for i j..
Sy and Sn are singletons, i.e., Su { and SH = {sH].
Transitions can only occur between consecutive layers. Formally, let h(s)) represent the index of the layer to which state belongs, then Vs' & Sn(s)+1 and Va E A, (s (s) = 0.
These assumptions are standard in previous works (Zimin & Neu, 2013; Rosenberg & Mansour, 2019b;a; Jin et al., 2020a; Jin & Luo, 2020; Jin et al., 2021b; Neu & Olkhovskaya, 2021). They are not necessary for our analysis but can simplify the notations. However, we remark that our layer structure assumption is slightly more general than it in previous works, which assume homogeneous transition functions (i.e., Po = Pi = = PH-1) Hence they require Vs' & Sp(s))11 and Va E A. (s'(ss) a) = O for all h = 0,.... H - 1. Besides, in our formulation, due to the layer structure, Pa,-Is, a) will actually never affect the transitions in the MDP if h f h(s). Hence, with slightly abuse of notation, we define P No and write P(-Is,a) a) Phte) (-s.aa)
H1-1
The interaction protocol between the learner and the environment is given as follows. Ahead of time, the environment decides an MDP, and the learner only knows the state space S, the layer structure, and the action space A. The interaction proceeds in K episodes. At the beginning of episode k the adversary chooses loss function & probably based on the history information before episode k. Meanwhile, the learner chooses a stochastic policy n S x A + [0. 1] with Ty. (als) being the probability of taking a at state 8. Starting from the initial state 8k.0 80, the learner repeatedly selects action ag.h sampled from T& T (-(Sk.)). suffers loss (5 (R.A) and transits to the next state $k,A+1 which is drawn from P(-sskhh 0k,h) h) for h = O.., H 1, until reaching the terminating state sK.H sH. At the end of episode k. the learner only observes bandit feedback, i.e., the learner only observes the loss for each visited state-action pair: (SM,,, au.a) a ) For any (s, a) E S X A. the state-action value (R, a) and state value Ve, are defined as follows: Qu,((s, =
E Σ =h (E an.s) n, P, (8K,6, ak.a) = (s,a) a)) and V = Eawa(-le) (s,
4

---

Published as a conference paper at ICLR 2023
We denote the expected loss of an policy π in episode &s by (x(=) = =E Ekt'' la ($k.n, aRAA) P.
where the trajectory (S (g.h) ] 1m=0 is generated by executing policy under transition function P. The goal of the learner is to minimize the regret compared with n², defined as
H-1
K
K
R(K)- = Σ (TRR)
Σ (x(T), k=1
k=1
where π²' E argmin E (T( is the optimal policy and II is the set of all stochastic policies.
Linear mixture MDPs We consider special class of MDPs called linear mixture MDPs (Ayoub et al.. 2020; Cai et al., 2020; Zhou et al., 2021; He et al., 2022) where the transition probability function is linear in known feature mapping : 8 x Rd. The formal definition of linear mixture MDPs is given as follows.
Definition 1. M (S, H, (Pa) {(+) is called an inhomogeneous, episodic B B-bounded linear mixture MDP if ( s, a.a)l2 S 1 and there exist vectors 0% RR such that Ph. (s'(s, (Ø (s'|s, a) 0%) and 10 S B. (s,a,8') E S x Ax and h = 0, .,. -
We note that the regularity assumption on the feature mapping ((-1.-) -) in this work is slightly different from it of Zhou et al. (2021); He et al. (2022). In particular, they assume || ( a)ll < for any (s, a) E A and any bounded function G + [0, 1), where Φ a) E. ( One can see that our assumption is slightly more general than theirs.
Notation For a vector x and a matrix A, we use x(i) to denote the i-th coordinate of æ and use A(i,:) to denote the i-th row of A. Let Oij (st.g Cijs (s(., di,;)) be the observa- tion of the learner at episode and stage j. We denote by Fe.s the g-algebra generated by fo1.0:..., "0o,0:...,,0,,H- 02,0, .......... ,,,,, .k. Ok,h }- For simplicity, we abbreviate ( as Ex,a The notation (()) in this work hides all the logarithmic factors.
3.1 OCCUPANCY MEASURES
To solve the MDPs with online learning techniques, we consider using the concept of occupancy measures (Altman, 1998). Specifically, for some policy π and transition probability function P. the occupancy measure q= S A - [0, induced by P and π is defined q² F: (s, a) Pr [(hn, a,)) = (s, P, T.. where h = h(s) is the index of the layer of state s. Hence g² (s, a) indicates the probability of visiting state-action pair under policy π and transition we drop the dependence of an occupancy measure on P and when it is clear from the context.
what follows,
Due to its definition, a valid occupancy measure g satisfies the following two conditions. First, since one and only one state in each layer will be visited in an episode in a layered MDP, E(e (8,
wh = o,...,
Second, Vh = 1,..., H 1, and Vs Sn. = Emea a)) With slightly abuse of notation, we write
Exg 1xA P()ss' q(s) 9 as) For given occupancy measure q, one obtain its induced policy by (als) ((s (q(ss) Fixing transition function P of interest, we denote by A(P) the set of all the valid occupancy measures induced by P and some policy n. Then the regret can be rewritten as
R(K)= = Σ (q Pate q (²((x)
(I)
where q- = A(P) is the optimal occupancy measure induced by x².
4 ALGORITHM
In this section, we introduce the proposed LSUOB-REDD algorithm, detailed in Algorithm 1. In general, LSUOB-RERT maintains a ellipsoid confidence set of the unknown transition parameter (Section 4).. Meanwhile, it constructs optimistically biased loss estimator and runs OMD over the space of the occupancy measures induced by the ellipsoid confidence set to update the occupancy measure (Section 4.2).
5

---

Published as a conference paper at ICLR 2023
Algorithm I Least Squares Upper Occupancy Bound Relative Entropy Policy Search (LSUOB-REPP
1: Input: state space S, action space A, episode number K, learning rate 17, exploration parameter
7, regression regularization parameter A, and confidence parameter
2: Initialization: Initialize confidence set Pi as the set of all transition functions. For all h
O,... H - 1 and all (s, a) E S₁ x A, initialize Mo, = AI, occupancy measure 91 (s,a) S x
and policy T1 T
3: for k = 1, ..... K do
4: for h = 0, ,.. H do
5:
Take action dReA ~ (-88))).))
6: Set the imaginary next state S4,41 ar [ssssknn aka))ll 2ma..
7:
Observe truc next state sp,h+1 Pa (-Ise,, (g and loss &x (s ax.)).
8:
MR = M + ( a ( (s |sk, as,h))
9:
bu.b 11- + ((5k 8k, aR ) se, (.)).
10:
OK, = MM
11:
end for
12:
Compute upper occupancy bound: (8k 0k.h) COMP-UOR &k, ag,h, Pk), Vh.
13:
Construct loss estimators for all (s, a): lg (8. a) = (e(e))t
(e(8,))
In {s,a).
14:
Update transition confidence set Pk+1 based on Eq. (3).
15:
Compute occupancy mcasure: 9 = argmin 17 (g. ( + Dr q1). (EA(Pa-1)
16:
Update policy Tk+1 = π T
17:
end for
4.1 CONFIDENCE SETS
One of the main difficulties in learning MDPs comes from the unknown transition P. To deal with this problem, a natural way is to construct its estimator together with the corresponding con- fidence set. Let dy as. E. sbs s, Vs').. With the observation that Pa(-|s, Vi Eves V ( MDPs seek to learn 0f using Φv,, (SE, (K.A) as feature and V (#v,6+1) as the regression target (Ayoub et al., 2020; Cai et al., 2020). Particularly, they construct the estimator On. of 07 as
a), 0%) = (ovi. (s, a), 0%) existing works studying linear mixture
Koranis (1,)) 0) - Vi,,+ (BER+H) +1
k argmin OERd
Zhou al. (2021); He al. (2022) also use a similar method but further incorporate the estiamted variance information to gain a sharper confidence set. This method is termed as the value-targeted regression (VTR) (Ayoub et al., 2020; Cai et al., 2020; Zhou et al., 2021: He al., 2022), which critical to construct the optimistic estimator Q2+1A (:)) of the optimal action-value function Q* and lead to the final regret guarantee.
However, though VTR is popular in previous works studying linear mixture MDPs (Ayoub et al., 2020; Cai et al., 2020; He et al., 2021a; Zhou et al., 2021; He et al., 2022: Wu et al., 2022; Chen et al., 2022b; Min et al., 2022), including the information of the state-value function V-,(-) in the regression makes this method hard to control the estimation error of the occupancy measure coming from the unknown transition P. To overcome this challenge, seek different way, in which 0% is learned by directly using the vanilla transition information.
Specifically, let + Rxx with & (t, s') +fs' [ss'sssa) a) and 6, f0, 1). be the Dirac measure at (i.e,, an one-hot vector with the one entry at 8). To learn 0z from the transition information, one may consider using & s..,, as feature and 6=,, as the regression target. Specifically, OR. could be taken as the solution of the following regularized linear regression problem:
0 kKA argmin BERd
+ S 0 8= Ss 2 1

---

Published as a conference paper at ICLR 2023
However, one obstacle still remains to be solved. Particularly, let 77.h (..(-ss.h, ar.h) 8 84 be the noise at episode i and stage h. Then it is clear that 7/,h [-1,1]s, E,,.A [r.A. = 0 and Eses (7.A(s) (s)= = O. Therefore, conditioning on Fi, the noise A), at each state is I-subgaussian but they are not independent. In this way, one is still not able establish an ellipsoid confidence set for 2g.4 using the nelf-normalized concentration for vector-valued martingales (Abbasi- Yadkori et al., 2011). To further address this issue, we propose to use the transition information of only one state s(,4+1 in the next layer, which we call the imaginary next state. Note that the imaginary next state 8/,41 is not necessary to be the true next state si,b+1 experienced by the learner. More specifically,
we construct the estimator Os,A of 0% via solving
0x, arggin Σ [( (sL,41188n a.,)) ,0) - (es.tt((//tt))) 210112
DERd i=1
The closed-form solution of the above display is 0k. MElbenn where M3 ( &,, + Al is the feature covariance matrix at episode and stage h and by.A = Ei (( |ss. as, ) ( The choice of s may be determined by the learner based on the information of previous steps up to observing (8k,h, (g.h). In particular, we choose 5 k4,4 as
Etsr
$ E aargmax.es... |1 8k, (gAh)) MM
(2)
where the intuition is that the learner chooses to estimate the uncertainties of most uncertain states and hence controls the uncertainties of all the states in next layer. Based on the above construction of Og, we have its ellipsoid confidence set guaranteed by the following lemma.
Lemma 1. Let å (0,1), 1). Then for any k E N, and simultaneously for all h O...., H with probability at least - 6, it holds that 07 E Cu.b. where Ck = (0 E g ||0 - 0% M S
3 with 3x = BvA+ + V2ln(") H1 + In( der(M.-1.)) Xa
Note that the above lemma immediately implies that with probability 1 - 5, P E Pk, where 1H-1- and PA {P 1R=0
Pk. (PA : 30 E Ck,b s.t. ((s,a, s') E Sn x A x S =0) (3)
4.2 LOss ESTIMATORS AND ONLINE MIRROR DESCENT
Loss Estimators When learning the MDPs with known transition P. existing works consider constructing a conditionally unbiased estimator (x(s, a) (=(s.a)
(=.0.) Is {s, of the true loss function lu (Zimin& & Neu, 2013; Jin & Luo, 2020), where I4 {s, a} = if a) is visited in episode k and I4 {s, a} otherwise. To further gain a high-probabilityy bound, Ghasemi al. (2021) extend the idea of implicit exploration in multi-armed bandits (Neu, 2015) and propose an optimistically biased loss estimator ( a) qs (=.a)))+ Is {s, a} with 7 > 0 as the implicit exploration parameter. When transition P is unknown, the true occupancy measure qu taken by the learner is also unknown, and the above loss estimators are no longer applicable. To tackle this problem, we use loss estimator defined as (x(s,a) += lla {s.a} with (n a) = maxpep, P. (s, a) termed as the upper occupancy bound, which is first proposed by Jin et al. (2020a). This loss estimator also optimistically biased since uy (s, a)) 2 [s(8, a) given P E PA with high probability. Note that uj can be efficiently computed using COMP-UOB procedure of Jin et al. (2020a).
(ạ(e,0)
(s(s,))
Online Mirror Descent To compute the updated occupancy measure in each episode, our algorithm follows the standard OMD framework. Since A(P) is unknown, following previous works (Rosenberg & Mansour, 2019b;a; Jin et al., 2020a), ASUOB-REPS runs OMD over the space of occupancy measures (P induced by the transition confidence set PR+1- Specifically, at the end of episode k, LLSOSS-URREE REPS updates the occupancy measure by solving
g
argmin 17 (g. + Dr (q. 9x)
(4)
(EA(Px41)
7

---

Published as a conference paper at ICLR 2023
where lg is the biased loss estimator introduced above, 17 > is the learning rate to be tuned later, ('(an) Esa (q (s, of a)) is the unnormalized KL-divergence. and the potential function F(4)= = Ena ((x,a) In ((8 a) - ((8, a) is the unnormalized negative entropy. Besides, we note that Eq. (4) can be efficiently solved following the two-step procedure of OMD (Lattimore & Szepesvári, 2020). The concrete discussions are postponed to Appendix E. More comparisons between our method and previous methods are detailed in Appendix A.
DF (g. 4') = Es.a q (s, a) In g(e,a)
5 ANALYSIS
In this section, we present the regret upper bound of our algorithm LSUOB-REPS, and a regret lower bound for learning adversarial linear mixture MDPs with unknown transition and bandit feedback.
5.1 REGRET UPPER BOUND
The regret upper bound of our algorithm LSUOB-REPS is guaranteed by the following theorem. Recall d is the dimension of the feature mapping. H is the episode length, K is the number of episodes, S and A are the state and action space sizes, respectively.
Theorem 1. For any adversarial linear mixture MDP .M- (8, A, HI (PP))
(- satis-
fying Definition 1, by setting learning rate 1l and implicit exploration parameter as = =
H HI(HSA//) KSA
with probability at least 1 56, the regret of LSUOB-REPS is upper bounded by
R(K) = O In + V HSAK (nHSA/0) + H (m(H
Proofsketch sketch. Let 9l = q Pitk, Following Jin et al. (2020a), we decompose the regret as
K
K
K
= R(K)
The q EN
9x The (x)
+
gr. 4x - Ex
+
q Es lx
ERROR
BIAS;
BIAS2
We bound each term in the above display as follows (see Appendix C.2 and Appendix C.3 for details). First, the REG term is the regret of the corresponding online optimization problem, which is directly controlled by the OMD and can be bounded by O ( [HSAKII(HSA)) Further, the BIAS2 term measures the overestimation of the true losses by the constructed loss estimators, which can be bounded by O (V VHSAK In(SA/5) via the concentration of the implicit exploration loss estimator (Lemma 1, Neu (2015); Lemma 11, Jin et al. (2020a)). Finally, the ERROR and BIAS, terms are closely related to the estimation error of the occupancy measure, which can be bounded by O ( In (K/6) and O (52d/'hi' (K/8)) + VHSAK (n(HA/88) respectively. Applying a union bound over the above bounds finishes the proof.
+ H (H/)))
Remark 1. Ignoring logarithmic factors, LSUOB-REPS attains an ÓdS /K + (HSAK) regret guarantee when K > H. Compared with the regret bound OdH33/2 /K) of He et al. (2022) for the full-information feedback, our bound introduces the dependence on S and A and is worse than theirs since S > H by the layered structure of MDPs. However, the dependence on S and into the regret bounds is inevitable at the cost of changing from the full-information feedback to the more challenging bandit feedback. Besides, when dS & HVA, the regret bound of LSUOB-REER REPS improves the regret bound Ö(HSVAK) of Jin et al. (2020a).
shall see in Section 5.2, incorporating
5.1.1 BOUNDING THE OCCUPANCY MEASURE DIFFERENCE
To bound the ERROR and BIAS, terms, it is critical to control (a) the estimation error between q and qei and (b) the estimation error between Ug and yı. both of which can be bounded by the following key technical lemma. We defer its proof to Appendix C.
Lemma 2 (Occupancy measure difference for linear mixture MDPs). For any collection of transition functions {P&) ses such that P E Ps for all s, let qf q PE. If X 2 5, with probability at least
1 - 25, it holds that Ek= Elsa)eSKA (ot(,, a) qu (s, a)l = 0 d5 (12
8

---

Published as a conference paper at ICLR 2023
Remark 2. Comparing with the occupancy measure difference Ö (HSVAK, for tabular MDPs in Lemma 4 of Jin et al. (2020a), our bound Ö (ds*VK) dose not have the dependence on A, though it is worse by a factor of S. The main hardness of simultaneousty eliminating the dependence of the occupancy measure difference on S and A is that though the transition P of a linear mixture MDP admits linear structure, its occupancy measure still has a complicated recursive form: gu(s,a) = [ 11 af x , s'))
We leave the investigation on whether it is possible to also eliminate the dependence on S as our future work. Besides, we note that our bound for occupancy measure difference is not straightforward extension of its tabular version of Jin et al. (2020a). Specifically, let q% (s, alsm) be the probability of visiting (s, a) under the event that 8m is visited in layer m. Jin et al. (2020a) decompose qi (s, ()sm))) as (gf (s, a) sm)m 9k (s. a..aasm)) a)sm)) + qu (s, alsm) and (gg (s, alsm) 9k (s, alsm)) will only contribute an O(H A (KSSA)))) term. However, in the linear function approximation setting, the above term will become a leading term with an Ö (H²dS2 (d + 5)K) order. Hence we do not follow the decomposition of Jin et al. (2020a) and directly bound of (s, a 8m) instead.
5.2 REGRET LOWER BOUND
In this subsection, we provide a regret lower bound for learning adversarial linear mixture MDPs with bandit feedback and unknown transition.
Theorem 2. Suppose A(H/2-11 1) 2 S 2-/H/4 - 1-----3334444 2 2 443H/2. 2K 2 d, B 2 d/ /4KK, and H 2 8. Further assume H/4 and H/2-1
2-/3/ are integers. Then for
any algorithm, there exists an inhomogeneous, episodic B-bounded adversarial linear mixture MDP M = A, H. (Pr) H-- 1 satisfying Definition 1, such that the expected regret for this MDP is lower bounded by Q(dHVK VHSAK).
Proof sketch. At a high level, we construct an MDP instance such that it simultaneously makes the learner suffer regret by the unknown transition and the adversarial losses with bandit feedback. Specifically, we divide an episode into two phases, where the first and the second phase include the first 2 + layers and the last H/2 + 1 layers (layer H/2 belongs to both the first and the second phase). In the first phase, due to the unknown lincar mixture transition functions, we can translate learning in this phase into simultancously learning H/4 d-dimensional stochastic linear bandit problems with lower bound of order QddH In the second phase, due the adversarial losses with bandit feedback, we show that learning in this phase can be regarded as learning a combinatorial multi-armed bandit (CMAB) problem with semi-bandit feedback, the lower bound of which is Q HSKK). The proof concluded by combining the bounds of the two phases. Please see Appendix D for the formal proof.
Remark 3. The regret upper bound in Theorem matches the lower bound in d. K, and A up to logarithmic factors but looses a factor of S2 / H. The dependence of regret lower bound on S and A inevitable since only the bandit feedback information of the adversarial losses is revealed to the learner and the loss function is nonstructural.
6 CONCLUSIONS
In this work, we consider learning adversarial linear mixture MDPs with unknown transition and bandit feedback. We propose the first provably efficient algorithm -SUBBRRED in this setting and prove that with high probability, its regret upper bound by Ö(ds² + VHSAK). which only losses an extra 5²/H factor compared with our proposed lower bound. To achieve this result, we propose a novel occupancy measure difference lemma for linear mixture MDPs by leveraging the transition information of the imaginary next state as the regression target, which might be of independent interest. One natural open problem is how to close the gap between the existing upper and lower bounds. Besides, our lower bound suggests that it is not possible to eliminate the dependence of the regret bound on S and A without any structural assumptions on the loss function. Generalizing the definition of linear mixture MDPs by further incorporating the structural assumption on the loss function (e.g., the loss function is linear in the other unknown parameter) to eliminate the dependence on S and A also seems like interesting future direction. We leave these extensions as future works.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
The corresponding author Shuai Li is supported by National Natural Science Foundation of China No. 62006151 and Shanghai Sailing Program. Baoxiang Wang is partially supported by National Natural Science Foundation of China (62106213, 72150002) and Shenzhen Science and Technology Program 000S5022220001114440000000000000
REFERENCES
Yasin Yadakr,, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems 24: 25th Anmual Conference on Neural Information Processing Systems 2011. Proceedings of a meeting held 12-14 December 2011, Granada, Spain, pp. 231 2-220, 2011.
Eitan Altman, Constrained markov decision processes with total cost criteria: Lagrangian approach and dual linear program. Math. Methods Oper. Res., 48(3):887-41) 1998.
Raman Arora, Ofer Dekel, and Ambuj Tewari. Deterministic mdps with adversarial rewards and bandit feedback. In Proceedings of the Twenty-lighth Conference on Uncertainty in Artificial Intelligence, Catalina Island, CA, USA, August 14-18, 2012, pp. 93-101. AUAI Press, 2012.
Jean-Yves Audibert, Sébastien Bubeck, and Gábor Lugosi. Regret in online combinatorial optimiza- tion. Math. Oper. Res., 3911)311-45, 2014.
Alex Ayoub, Zeyu Jia, Csaba Szepesvári, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In Proceedings of the 37th International Conference on Machine Learning, ICMI. 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 463-474, PMLR, 2020.
Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J. Kappen. Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model. Mach. Learn., 91):): 325-349, 2013.
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, pp. 263-26222222 272. PMLR, 2017.
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 19-26. JMLR Workshop and Conference Proceedings, 2011.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy opti- mization. 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, pp. 1283-1294. PMLR, 2020.
Liyu Chen, Haipeng Luo, and Chen- Yu Wei. Minimax regret for stochastic shortest path with adversarial costs and known transition. In Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 Proceedings of Machine Learning Research, pp. 1180-125.. PMLR, 2021.
Liyu Chen, Haipeng Luo, and Aviv Rosenberg. Policy optimization for stochastic shortest path. In Conference on Learning Theory, 2-5 July 2022, London, UK. volume 178 of Proceedings of Machine Learning Research, pp. 982 1046. PMLR, 2022a.
Yuanzhou Chen, Jiafan He, and Quanquan Gu. On the sample complexity of learning infinite-horizon discounted linear kernel mdps. In International Conference Machine Learning. ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 3149-3183 PMLR, 2022b.
10

---

Published as a conference paper at ICLR 2023
Yan Dai, Haipeng Luo, and Liyu Chen. follow-the-perturbed--eeee for adversarial markov decision processes with bandit feedback. CoRR, (as/2205513451, 2022. doi: 10.48550/arXiv22205. 134551
Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert Schapire. On oracle-efficient PAC RL with rich observations. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 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, pp. 683. JMLR.org. 2013.
Travis Dick, András György, and Csaba Szepesvári. Online learning in markov decision processes with changing cost sequences. In 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, pp. 512-520. oog. 2014.
Simon S. 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, pp. 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 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, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 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 1. puterman). SIAM Rev, 38(4):689, 1996.
Mahsa Ghasemi, Abolfazl Hashemi, Haris Vikalo, and Ufuk Topcu. 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, pp. 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 Learning Research, pp. -171-4180 PMLR, 2021a.
Jiafan Hc, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for discounted mdps. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NewrIPS 2021, December 6-14, 2021, virtual, pp. 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, pp. 4259-4280. PMLR, 2022.
Pihe Hu, Yu Chen, and Longbo Huang. Nearly minimax optimal reinforcement learning with linear function approximation. In International Conference Machine Learning, 1CML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 8971-9019. PMLR, 2022.
11

---

Published as a conference paper at ICLR 2023
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. Con- textual decision processes with low bellman rank are pac-learnabe. 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, pp. 1704-1713. PMLR, 2017.
Chi Jin, Zeyuan Allen-Zhu, Sébastien Bubeck, and Michael I. Jordan. Is q-learning provably efficient? In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 4868-4874 2018.
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, pp. 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, pp. 2137-2143. PMLR, 2020b.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of RL problems, and sample-efficient algorithms. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 13306-13411 2021a.
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, viriual, pp. 20491-20502, 2021b.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Haipeng Luo, Chen-Yo Wei, and Chung-Was Wei Lec. Policy optimization in adversarial mdps: Improved exploration via dilated bonuses. CoRR, 0is/21177.0844 2021a.
Haipeng Luo, Chen-Ye Yu Wei, and Chung-Wei 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, NeurIPS 2021, December 6- 14, 2021, virtual, pp. 22931 22942, 2021b.
Yifei Min, Jiafan He, Tianhao Wang, and Quanquan Gu. Learning stochastic shortest path with linear function approximation. In International Conference on Machine Learning, 1CML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 15584-15629. PMLR, 2022.
Gergely Neu. Explore no more: Improved high-probabilityy regret bounds for non-stochastic bandits. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Informa- tion Processing Systems 2015, December 7-12, 2015, Montreal, Quebec. Canada, pp. 3168-3177 2015.
Gergely Neu and Julia Olkhovskaya. Online learning 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, pp. 10407-10417, 2021.
Gergely Neu, András György, and Csaba Szepesvári. The online loop-free stochastic shortest-pan -ath problem. In COLT 2010 The 23rd Conference on Learning Theory, Haifa, Israel, June 27-29, 2010, pp. 231-243 Omnipress, 2010a.
12

---

Published as a conference paper at ICLR 2023
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, pp. 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 Fifteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2012, La Palma, Canary Islands, Spain, April 21-23, 2012, volume 22 of JMLR Proceedings, pp. 805-813. JMLR.org, 2012.
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, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 2209-2218, 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, pp. 5478-5486. PMLR, 2019b.
Aviv Rosenberg and Yishay Mansour. Stochastic shortest path with adversarially changing costs. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event Montreal, Canada, 19-27 August 2021, pp. 2936-2942 2942. ijcai.org, 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, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 8604 8613. PMLR, 2020.
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- -ree approaches. In Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, PMLR, 2019.
volume 99 of Pruceedings of Machine Learning Research, pp.
Aristide C. Y. Tossou, Debabrota Basu, and Christos Dimitrakakis, Near-optimal optimistic reinforee- ment learning using empirical bernstein inequalities. CoRR, abs/1905. 121119555.22...... 2019.
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.
Yining Wang, Ruosong Wang, Simon Shaolei Du, and Akshay Krishnamurthy, Optimism in 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, 2021.
Yue Wu, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal regret for learning infinite- horizon average-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, pp. 3883-3913. PMLR, 2022.
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. 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, pp. 6995 7004. PMLR,
Jia Yuan Yu, Shie Mannor, and Nahum Shimkin. Markov decision processes with arbitrary reward processes. Math. Oper. Res., 34(3):737-757, 2009.
13

---

Published as a conference paper at ICLR 2023
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, pp. 1954-1964. PMLR, 2020a.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In Proceedings of the 37th International Conference on Machine Learning, ICMI. 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 10978- PMLR, 2020b.
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, pp. 4342-4355, 2021.
Dongruo Zhou and Quanquan Gu. Computationally efficient horizon-free reinforcement learning for linear mixture mdps. CoRR, abs/2205.11500 2022.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvári. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 Proceedings of Machine Learning Research, pp. 4532 4576. PMLR, 2021.
Alexander Zimin and Gergely Neu. Online learning in episodic markovian decision processes by relative entropy policy search. In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pp. 1583-1591, 2013.
14


Reviews:
[{"review_id": "ypxCYit04B_", "reviewer": "Reviewer_1UrW", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "\n\nThe paper studies RL in linear mixture MDP with unknown transition, adversarial loss, and bandit feedback. This paper gives the first algorithm in this setting whose regret scales with sqrt(#episode) and supplements a lower bound, which matches the upper bound for the $d$ and $K$ dependency, where $K$ is #epsiode and $d$ is the ambient dimension of the linear mixture MDP. ", "summary_of_the_review": "\nThis paper contains some novel results and techniques, but it could be made better if the authors could come up with more complete results.", "strength_and_weaknesses": "\n### Strength\n\n1. This paper studies a reasonable setting of \"adversarial\" RL with linear function approximation, and designs and proves the first algorithm with sqrt(K) regret. \n2. This paper goes beyond the classical VTR (value-targeted regression) framework of analysis for linear mixture MDP, coming up with a novel technique (imaginary roll out of state) to cope the challenge arouse in adversarial setting.\n\n### Weakness\n\n1. There are many settings of linear RL theory besides linear mixture MDP, such as linear MDP. Also, recently, there are unified framework such as Bellman-rank and bilinear classes for RL with general function approximation. In particular, these frameworks include linear mixture MDP as their special cases. While the theory of RL with function approximation is certainly an important topic, it could become much less important when the scope is restricted to linear mixture MDP.\n2. This paper does not prove tight lower bound to complete the theoretical research in their setting.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "mBgYmHbttk", "reviewer": "Reviewer_knov", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers the adversarial linear adversarial MDP and proposes the first efficient algorithm that achieves $\\sqrt{K}$ bound. Moreover, they also give a lower bound. Their techniques are based on the occupancy measurements which is initially proposed by Jin et al. (2020b). Compared to previous techniques, this paper adopts some nontrivial extensions, the main one, as stated in the paper, is the use of a carefully chosen \" imaginary next state\", which solves the dependence between the actual next states and thus allows the usage of regular linear regression to estimate the $\\theta$", "summary_of_the_review": "Overall I think it has good results and relatively novel techniques. But the explanation of some techniques seems not very clear to me. So I give 6 and would like to raise my score if I can better understand the novelty of the paper.", "strength_and_weaknesses": "Strength: The results are significant. The techniques seem novel to me -- (1) the use of \" imaginary next state\" is novel (2) the further improvement on H, S compared to Jin et al. (2020b) seems also interesting (but it is not very clearly stated)\n\nWeakness: Some of the technique contributions are not clearly stated in the paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "MbVSr4dmEH", "reviewer": "Reviewer_Buht", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies adversarial linear mixture MDPs with unknown transition and bandit feedback. The authors propose an algorithm with an upper bound $\\tilde{O}(dS^2 \\sqrt{K} + \\sqrt{HSAK})$, and prove an almost near-matching lower bound (in $d, K, A$). The authors highlight the use of a novel occupancy measure difference lemma for linear mixture MDPs, which might be of independent interest.", "summary_of_the_review": "The paper studies adversarially linear mixture MDPs. The main results are interesting with a relatively novel analysis. However, there is little innovation in the algorithm design, and the implications of the main results are unclear: what did we gain from the linear MDPs assumptions if the upper bound still depends on $S$?", "strength_and_weaknesses": "Strengths:\n\n(+) The upper bound is accompanied by a near-matching lower bound. The authors also justify the dependence on $S$ and $A$ via the lower bound.\n\n(+) The use of a novel occupancy measure difference lemma (Appendix B.1).\n\nWeaknesses:\n\n(-) The bound depends on $S$, which is unusual and undesirable given the linear mixture MDPs assumption.\n\n(-) The writing can be improved, especially the main results.\n\nDetailed comments:\n\n- I am familiar with statistical RL theory, but not so much in the adversarial setting. Hence, I will comment more on the writing/correctness aspects of the paper rather than the novelty/contribution.\n\n- (main concern) Since the upper bound in Theorem 1 has a dependence on both $S$ and $A$, would this be just the tabular setting? I don’t quite understand where the linear approximation comes in when we still have the dependence on $S$.\n\n- I encourage the authors to make it more explicit which elements are novel, particularly in your algorithm design. For example, how does your proposed algorithm differ from Jin et al. (2020b)?\n\n- The main results (Theorem 1 and 2) should be made more detailed and self-contained. I encourage the authors to at least briefly introduce the settings and various relevant notations in the Theorems.\n\n- The lower bound contains a term $dH\\sqrt{K}$, which is linear in the horizon $H$. However, the upper bound only has a $\\sqrt{H}$ dependence. Would this lead to a contradiction, or am I missing something here?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "8WHhe952M9", "reviewer": "Reviewer_ZddW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies inhomogeneous adversarial linear mixture MDPs. It presents an efficient algorithm called LSUOB-REPS which provably achieves $\\tilde{\\mathcal{O}}(d S^2 \\sqrt{K} + \\sqrt{HSAK})$. The algorithm relies on occupancy measure based techniques, which maintains a confidence set of the unknown transition function and runs online mirror descent over the space of occupancy measures. One novelty is the construction of a specific linear regression objective function to solve for the transition parameter. To this end, this paper proposes to use an imaginary next state to construct the regression target. Furthermore, a lower bound of order $\\Omega(dH\\sqrt{K} + \\sqrt{HSAK})$ is proven, which shows that the algorithm has close-to-optimal performance. ", "summary_of_the_review": "My current recommendation is accept. \n\nThe reasons are the following:\n\n1. Solid contribution: this paper gives the answer to a quite challenging and important field of reinforcement learning theory. \n\n2. Some novelty: to solve certain technical challenges, some novel ideas have been proposed.\n", "strength_and_weaknesses": "Strength:\n\n1. This paper gives the first answer to a quite challenging problem, i.e., the adversarial linear MDPs. Both an upper bound and a lower bound (under certain assumptions) are given.\n\n2. The paper is very well-written. This is a very technical paper. Techniques are presented with rather detailed explanations, making it easier for the readers to follow.\n\n3. The paper has some novelty. The technical challenges are also discussed quite thoroughly, showing the technical contributions of the paper clear. For example, the imaginary next-state seems like a quite interesting idea to deal with the challenge of constructing a confidence ellipsoid when the classical self-normalized concentration technique cannot be directly applied. \n\n---\nWeakness: \n\nThere is no major weakness as far as I can tell. There are some comments though. \n1. The dependence of the upper bound on $|S|$ is unpleasant under the linear mixture MDP setting. \n\n2. The paper lacks a very detailed comparison with [1]. Although it seems that [1] studies tabular MDPs which is different from linear mixture MDP, the major idea of algorithmic design is very similar. Furthermore, in the case of representing a tabular MDP by a linear mixture MDP, we would have a relation $d = |S|^2 |A|$. In this case the bound in this paper would actually be worse than that of $1$ (but I can understand this since representing a tabular MDP by a linear mixture is inefficient. Still a more detailed comparison would be good to have).\n\n3. There is no discussion on computational efficiency of the algorithm, so it might be inappropriate to call the algorithm ‘efficient’.    \n\n[1] Jin, Chi, et al. \"Learning adversarial markov decision processes with bandit feedback and unknown transition.\" International Conference on Machine Learning. PMLR, 2020.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster