Simultaneously Learning Stochastic and Adversarial Markov Decision Process with Linear Function Approximation
Authors: Fang Kong
XiangCheng Zhang
Baoxiang Wang
Shuai Li
Venue: Submitted to ICLR 2023 (2023)

Abstract: Reinforcement learning (RL) has been commonly used in practice. To deal with the numerous states and actions in real applications, the function approximation method has been widely employed to improve the learning efficiency, among which the linear function approximation has attracted great interest both theoretically and empirically. Previous works on the linear Markov Decision Process (MDP) mainly study two settings, the stochastic setting where the reward is generated in a stochastic way and the adversarial setting where the reward can be chosen arbitrarily by an adversary. All these works treat these two environments separately. However, the learning agents often have no idea of how rewards are generated and a wrong reward type can severely disrupt the performance of those specially designed algorithms. So a natural question is whether an algorithm can be derived that can efficiently learn in both environments but without knowing the reward type. In this paper, we first consider such best-of-both-worlds problem for linear MDP with the known transition. We propose an algorithm and prove it can simultaneously achieve $O(\text{poly} \log K)$ regret in the stochastic setting and $O(\sqrt{K})$ regret in the adversarial setting where $K$ is the horizon. To the best of our knowledge, it is the first such result for linear MDP. 

Under review as a conference paper at ICLR 2023
SIMULTANEOUSLY LEARNING STOCHASTIC AND AD- VERSARIAL MARKOV DECISION PROCESS WITH LIN- EAR FUNCTION APPROXIMATION
Anonymous authors Paper under double-blind review
ABSTRACT
Reinforcement learning (RL) has been commonly used in practice. To deal with the numerous states and actions in real applications, the function approximation method has been widely employed improve the learning efficiency, among which the linear function approximation has attracted great interest both theoretically and empirically. Previous works on the linear Markov Decision Process (MDP) mainly study two settings, the stochastic setting where the reward is generated in a stochastic way and the adversarial setting where the reward can be chosen arbitrarily by an adversary. All these works treat these two environments separately. However, the learning agents often have no idea of how rewards are generated and a wrong reward type can severely disrupt the performance of those specially designed algorithms. So a natural question is whether an algorithm can be derived that can efficiently learn in both environments but without knowing the reward type. In this paper, we first consider such bosttoo-oott-woldds problem for linear MDP with the known transition. We propose an algorithm and prove it can simultaneously achieve Oppoly log K) regret in the stochastic setting and Ö(VK) regret in the adversarial setting where K is the horizon. To the best of our knowledge, it is the first such result for linear MDP.
INTRODUCTION
Reinforcement learning (RI) studies the problem where learning agent interacts with the environ- ment over time and aims to maximize its cumulative rewards in given horizon. It has a wide range of real applications including robotics (Kober et al., 2013), games (Mnih et al., 2013; Silver et al., 2016), etc. The environment dynamics are usually modeled by the Markov Decision Process (MDP) with a fixed transition function. We consider the general episodic MDP setting where the interactions last for several episodes and the length of each episode is fixed (Jin et al., 2018; 2020b; Luo et al., 2021; Yang et al., 2021). In each episode, the agent first observes its current state and would decide which action take. After making the decision, it receives an instant reward and the environment will then transfer to the next state. The cumulative reward in an episode is called the value and the objective of the agent is equivalent to minimizing the regret defined the cumulative difference between the optimal value and its received values over episodes.
Many previous works focus on the tabular MDP setting where the state and action space are finite and the values can be represented by table (Azar et al., 2017; Jin et al., 2018; Chen et al., 2021; Luo et al., 2021). Most of them study the stochastic setting with the stationary reward in which the reward of state-action pair is generated from fixed distribution (Azar et al., 2017; Jin et al., 2018; Simchowitz & Jamieson, 2019; Yang et al., 2021). Since the reward may change over time in applications, some works consider the adversarial MDP where the reward can be arbitrarily generated among different episodes (Yu et al., 2009; Rosenberg & Mansour, 2019; Jin et al., 2020a; Chen et al., 2021; Luo et al., 2021). All of these works pay efforts to learn the value function table find the optimal policy and the computation complexity highly depends on the state and action space size.
However, in real applications such the Go game, there are numerous states and the value function table is huge, which brings a great challenge to the computation complexity for traditional algorithms in the tabular case. To cope with the dimensionality curse, rich line of works employ the function

---

Under review as a conference paper at ICLR 2023
approximation methods, such the linear function and deep neural networks, to approximate the value functions or the policies to improve learning efficiency. These methods also achieve great success in practical scenarios such the Atari and Go games (Mnih et al., 2013; Silver et al., 2016). Despite their great empirical performances, it also brings a series of challenges in deriving theoretical analysis. To build a better theoretical understanding of these approximation methods, lots of works start from deriving regret guarantees for linear function classes
The linear MDP a popular model which assumes both the transition and reward at a state-action pair are linear in the corresponding d-dimensional feature (Jin et al., 2020b; He et al., 2021; Hu et al., 2022). There are also mainly two types of the reward. For the stochastic setting, Jin et al. (2020b) provides the first efficient algorithm named Least-Square Value Iteration UCB (LSVI-UCB) and show that the its regret over K episodes can be upper bounded by O(VK). To seek for tighter result with respect the specific problem structure, He et al. (2021) provide a new analysis for LSVI-UCB and show it achieves an (poly log K) instance- -eeanneddeeendent regret upper bound. The adversarial setting is much harder than the stochastic one since the reward can change arbitrarily but the agent can only observe the rewards on the experienced trajectory. For this more challenging case, a regret upper bound of order O O(vK) is only obtained in the case with known transition by Neu & Olkhovskaya (2021). All these works separately treat two environment types.
However, the learning agent usually has no idea of how the reward is generated. And once the reward type is wrong, the specially designed algorithm for a separate setting may suffer great loss. Thus deriving an algorithm that can adapt to different environment types becomes natural solution for this problem. This direction has attracted great research interest in simpler bandit (Bubeck & Slivkins, 2012; Zimmert al., 2019; Lee et al., 2021; Kong al., 2022) and tabular MDP settings (Jin & Luo, 2020; Jin et al., 2021 b) but still remains open in linear MDP.
In this paper, we try answer the question of deriving linear MDP. Due to the challenge of learning in the adversarial setting, we also consider the known transition case. We propose an algorithm that continuously detects the real environment type and adjusts its strategy. It has been shown that our algorithm can simultaneously achieve (pooyy log K) regret in the stochastic setting and Ö(VK) regret in the adversarial setting. To the best of our knowledge, these are the first BoBW results for linear MDP. It is also worth noting that our BoBW algorithm relies on an algorithm that can achieve a high-probabiiltyy guarantee for the adversarial setting, which previous works fail to provide. And we propose the first analysis for high-probability regret bound in the adversarial linear MDP.
sitt-of-bbth-wolle (BoBW) guarantees for
RELATED WORK
Linear MDP. Recently, deriving theoretically guaranteed algorithms for RL with linear function approximation has attracted great interests. The linear MDP model is one of the most popular one. Jin et al. (2020b) develop the first efficient algorithm LSVI-UCB both in sample and computation complexity for this setting. They show that the algorithm achieves O(Vd3 H K) regret where d is the feature dimension and H is the length of each episode. This result recently improved to the optimal order (dH VK) by Hu et al. (2022) with a tighter concentration analysis. Apart from UCB, the TS-type algorithm has also been proposed for this setting (Zanette et al., 2020a). All these results do not consider the specific problem structure. In the stochastic setting, deriving an instanee-dependent regret is more attractive to show the tighter performances of algorithms in a specific problem. This type of regret has been widely studied under the tabular MDP setting (Simchowitz & Jamieson, 2019; Yang et al., 2021). He et al. (2021) is the first to provide this type of regret in linear MDP. Using different proof framework, they show that the LSVI-UCB algorithm can achieve (dd H3 log K/A) where A is the minimum value gap in the episodic MDP.
All these works consider the stochastic setting with stationary rewards. Neu & Olkhovskaya (2021) first attempts to analyze the more challenging adversarial environment. They consider a simplier setting with known transition and provide an O( O(vdH K) regret upper bound. For unknown transition case, Luo et al. (2021) provide ( K2/3) upper bound with the help of simulator and O 144/1))) guarantee for the general case. Above all, even in the separate adversarial setting, O O(VK) regret is only derived for known transition case. We also study the known transition
2

---

Under review as a conference paper at ICLR 2023
setting and try to provide Ö(VK) regret in the adversarial setting while simultaneously achieving O (poly log K') regret if the environment is truly stochastic.
beot-of--oth-worlds. The question of reaching best-of- hoffbboth-orddds results is first proposed by Bubeck & Slivkins (2012) for bandit setting, special case of episodic MDP with H = 1. Their proposed algorithm assumes the setting is stochastic and continuously detects whether the assumption is satisfied. Such detection-based method is shown to achieve (ppoly log K) regret in the stochastic setting and O(VK) in the adversarial setting, which later improved by Auer & Chiang (2016). Similar detection- based techniques have also been adopted in more general linear bandit (Lee et al., 2021) and graph feedback (Kong et al., 2022) settings to achieve BoBW guarantees. Another line of works consider using Follow-the- HagllottheRRegulriizeee Regularized-Leadee (FTRL) to adapt to different environment types (Zimmert Seldin, 2019; 2021). 1). This type of algorithm is shown to be tighter than Bubeck & Slivkins (2012); Auer & Chiang (2016) in the bandit setting and also attracts lots of interest in more complex problems such as combinatorial bandits (Zimmert et al., 2019; Chen et al., 2022).
The first BoBW result in the MDP setting is provided by Jin & Luo (2020) in the tabular case. Due to the challenge of the problem, they first study the known transition setting. Their approach to achieving BoBW is the FTRL algorithm with a newly designed regularizer, which result is later improved by Jin et al. (2021b) and also generalized to the unknown transition case. To the best of our knowledge, are the first to consider the BoBW problem in linear MDP. We also start from the known transition setting and our algorithm is based on detection.
RL with general function approximation The linear mixture MDP is another popular RL model with linear function approximation. It assumes the transition function can be approximated by weighted average over several transition kernels. In the stochastic setting, both mastance-independee (Ayoub al., 2020; Zhou al., 2021) and dependent regret bound (He et al., 2021) have been derived. And in the adversarial setting, only full information case has been studied, where the agent has access to the rewards of all state-action pairs (Cai al., 2020; He et al., 2022). Apart from linear function approximation, there is also rich line of works considering general function classes, such as the setting with low Bellman rank (Jiang et al., 2017; Zanette et al., 2020b), low Eluder dimension (Wang et al., 2020; Kong et al., 2021) and low Bellman Eluder dimension (Jin et al., 2021a).
SETTING
We consider the episodic MDP setting where the agent interacts with the environment for K episodes with known transition. The episodic MDP can be represented by M(S, A, H, {r=)k=n P) where is the state space, is the action space, H is the length of each episode, Ta = (rw,)) h=1 is the reward function and P {Ph) is the known transition probability function. Specifically, at each episode k and step transition probability at state a E S by taking action a E A. respectively.
/
[H], T a) [0 and Px s, a) E [o, 1]1s1 are the reward and
We focus on stationary policies. Denote to an action distribution where тr S + AA. For each episode E [K], the agent would start from the first state sk,1 S1 and determine the policy тk. Then at each step h E [H] of episode k, it first observes the current state SK, and then perform the action 0g Tg.n( 8k,h)- The agent would receive random reward yk,, Tk.k (8k, h. (k.b) CR,,, where 6x,h is independent zero-mean noise. The environment then transfers to the next state Sk,b+1 based on the transition function P( 5k,h, n.). The episode ends when the last state Sk, H+1 1 reached.
H
policy mapping from the state space
We focus on linear MDP with known transition where the reward functions are linear in given feature mapping (Jin et al., 2020b; He et al., 2021). The formal definition is as follows.
Assumption 1. (Linear MDP with known transition) M(S, A, H, (ra J P) is linear MDP with a known feature mapping Φ : S x A + Rdd such that for each step h E [H), there exists an unknown vector 8j, where for each (s, a) E S x A, (s, = (ő(s, a), 12.
'The deterministic starting state is only for expositional convenience. Our algorithm and analysis can directly handle random starting states with distribution.
3

---

Under review as a conference paper at ICLR 2023
In the stochastic setting, the reward function (rx {rx] or namely the reward parameter (0x 1 k=1 is fixed over different episodes [K]. And the adversarial setting, the reward parameter {0x [ can be chosen arbitrarily by adversary (which may be possibly dependent on previous policies).
K
evaluate the performance step h, denote the Q-value function Q (s, a) the expected reward that will be obtained by the agent starting from (8k,hs (k.h) (s, a.) with policy which is formally defined as
policy æ by its value functions. Specifically, for any episode & and
H Σ
(T) E
yk.
TT, 8k,h 8, 0A,A
Similarly, the value function VE, (s) of any state s is defined as
H
(* = E
Σ
8k,h
M=h
In the following paper, we abuse a bit notation by using VE = VV,1 ($1) to represent the value of policy at the starting state 81 and episode k. Define Φx = E [o(sn, an) T| the expected feature vector that the policy и visits at step h. It is worth noting that this recovers the state-action visitation probability in the tabular setting. And according the definition, the value function of policy ı at episode
be represented V Σト (0x,A, 02,n)-
In this paper, we consider optimizing both the stochastic and adversarial environments within a finite policy set II. Given policy set II, the learning agent would determine the policy Tæ II in each episode [K] Let x* E arg max, Σk V be one optimal policy IT that maximizes the cumulative value functions over K episodes, which is assumed to be unique in the stochastic setting similar to previous works tabular MDP (Jin Luo, 2020; Jin et al., 202 lb) and bandit setting (Lee et al., 2021: Zimmert& & Seldin, 2019; 2021). Denote the cumulative regret compared with " E Il over episodes as
Reg( [;
Σ 1=1
(VV - V
(1)
4 ALGORITHM
In this section, we propose a detection-based algorithm to optimize both stochastic and adversarial environments for linear MDP with a given policy set II. Our algorithm mainly inspired by the detection technique of Lee et al. (2021) for BoBW in linear bandits. At high level, the algorithm first assumes the environment is truly adversarial and continuously detect whether could be a stochastic one. Its design relies on new linear MDP algorithm that can return cell-concentrated estimators for values of policies and also achieve sub-linear regret in the adversarial setting with high probability.
Previous works adversarial linear MDP fail to provide high-probabilit guarantee and thus existing algorithms satisfy this property. In Appendix D, we propose a variant of Geometric Hedge (Algorithm 4), which is initially designed for the simple bandit case (Bartlett al., 2008), and provide a new analysis for it in the linear MDP setting. We show that this algorithm satisfies the following properties and can be used to derive the BoBW results. It is also worth noting that this algorithm is the first to achieve
biggbprobabylity regret guarantee for adversarial linear MDP.
Theorem 1. Given a policy set II, the regret of our proposed Algorithm in the adversarial setting can be upper bounded by
Reg(K;II) SO (V log (111/5
with probability at least 8-
Further, each episode Algorithm 4 returns value estimator V for each policy n E II. Choosing constant Lo AdH log (1))8), Ci 215 log (K]TT)/) and C2 2 20, it holds that for any
4

---

Under review as a conference paper at ICLR 2023
ku 2 Lo and policy II.
Kn
Ciko - C2 VE Vx S
Σ
1 k - Vi²)
with probability larger than
Our main BoBW algorithm is phased algorithm and is presented in Algorithm 1. It takes Algorithm 4 satisfying Theorem with parameter Lo and C1 as input. The first epoch is of length Lu and the length of the following epochs would grow exponentially Line 4. During each epoch, it executes Algorithm 2, which we refer to as the BoBW main body (Line 3).
Algorithm 1 BoBW for linear MDP
1: Input: Algorithm with parameter C1 and Lu; Set L == Lo. Maximum duration K.
2: while number of episodes & < K do
3: Execute Algorithm 2 (BoBW main body) with parameter T. and receive output kn
4: Set I. 2kg
5: end while
Algorithm 2 (BoBW main body) takes the Algorithm 4 with parameter C₁ and L as input. Here L can just be regarded as the minimum number of episodes that Algorithm needs run to collect enough observations. The algorithm first assumes the environment is adversarial and executes Algorithm 4 in least episodes (which we refer to as the first phase). As shown in Theorem 1, Algorithm 4 guarantees that when running for more than L episodes, the regret compared with any policy and the distance between its estimated V value and the real V value would be no larger. Based on these concentration properties, if policy ø shows consistent better performance than all of the other policies (Line 5), we have the reason to believe that the environment is truly stochastic. Being aware of this, shown in Line 6, Algorithm 2 would transfer to the stochastic phase (Line 9-18, which refer to as the second phase) with the estimated V values returned by Algorithm 4.
Since the estimated values by Algorithm 4 can well approximate the real values of policies, the exploration in the stochastic setting can be conducted by the estimated value gaps to obtain a problem- dependent regret bound. The objective is identify the optimal policy and maximize the collected rewards, which can be implemented by an optimization problem (Algorithm 3). Taking the estimated value gap Å as input, Algorithm 3 would return probability distribution p' over the policy set II. Intuitively, p" maximizes the expected values of policies while ensuring the uncertainty of all policies to be smaller than its sub-optimality gap. In Appendix A, we show that when å estimated accurately, selecting policies based on p" can reach a problem-dependen regret upper bound.
Back to the main body of Algorithm 2, after computing the distribution pic based on the current estimated À (Line 10), also mixes this policy distribution with a one-hot vector éş to ensure that the estimated optimal policy ? can be observed for enough times and the variance of its following estimators can thus be low (Line 11). The algorithm then samples a policy Ty according to this mixed distribution and executes it in this episode. Then based on the received rewards Uk.k at each step h and the total reward Y% Eh=1 Mk.h. the value estimations of policies can be further updated. Due to the technical reason, here for the estimated optimal policy î and other policies म. we use different estimators. Specifically, we use the importance weighted estimator to approximate the value of स. The reason for using mixed policy distribution f is just to ensure the low variance of this estimator. And for other policies, we use the standard least square estimators (Line 13). Based on these newly estimated values of policies, the algorithm can then update the estimation for their sub-optimality gaps as Line 14. To get a tighter analysis, when computing the value gap of æ, we use the traditional estimator of it by Algorithm 4 in the first kn episodes and the Catoni estimator for the recent i - Ko episodes. Formally speaking, the Catoni estimator Catoni, ((X,, X2, ... X,)) is defined as the unique root of f(z) Ei. T (a (X, 2)), where & (v) log (1 + y + y² /2) if y 2 and (b))
log (1 y + yd /2) otherwise. The hyper- 4 log (K/II//)/ / E k1+1 (2m + 9dH) which mainly follows Lee
parameter og is set as al. (2021) but with the careful consideration in MDP setting.
5

---

then Under review as a conference paper at ICLR 2023
Algorithm 2 BOBW main body
Input: new instance of Algorithm with parameter C1, parameter L
2: Define: fK log K
3: for each episode k = 2, do
4: Execute and update Algorithm 4, receive value estimators V for each n
5: if :: 2 I. and there exists policy ă E II such that
Σv
V
(3)
s=1
Σ
Y Σ
V 25 JRCi,,
VT #
(4)
6:
kp k: A ko {
V V.
break
mEll
7:
end if
8: end for
9:
for episode A: = k0 + 1, Ko 22, do
10:
Compute P OP k A)
11:
Compute PT((T) = 2 cx + (T). where ea is a one-hot vector with 1 only at policy Å
12:
Sample Th Ps and execute Ti
Receive rewards Yv=
Σ n= y and calculate Vi for each क E II follows
!!
H
VT x न
Σ
AWlh, where ΣR, = Σ (e
(5)
h=1
Ys
V
1 = #}
(6)
Pk (f)
14:
For each π + ât compute Å as
ko
Åg
V + (k - Ko)Ro
Σ p , with Roba, = Catoniag (1V7) (==ktt]
K
(7)
15:
if
3r # म. A & (0.39... 1.81
(8)
Σ (v++ -v.)
y.) 2 20
(9)
11+1
then
16:
Return Ag
17: end if
18: end for
Is is worth noting that an adversarial setting may be disguised as stochastic scenarios and fool the algorithm to enter the stochastic phase. Thus the agent still needs to be vigilant about the possible change of the environment. The detection conditions (Line 15) are set for this objective. To be specific, if the estimated sub-optimality gap of a policy changes obviously compared with the original estimation by Algorithm 4 in the adversarial phase the regret compared with f is large, the algorithm can determine that the environment may not be stochastic and would terminiate the current epoch and enter in the next epoch with parameter ko (Line 16).

---

Under review as a conference paper at ICLR 2023
Algorithm 3 Optimization problem (OP) k; A
1: Define 3x = 2 log (ITT) k/6)
2: Return the minimizer p" of the following constrained optimization problem
min
P
(10)
sENl
H
s.t.
1 1 S
4dH and Pr
Σ
11=1,
(11)
Bx
h=1
xell
where En(p) Ex P
5 THEORETICAL ANALYSIS
this section, we provide the theoretical guarantee and the analysis of Algorithm both stochastic and adversarial settings
The first is about the stochastic setting. Since the value function remains the same for different episodes, simplify the notation and use V to represent the real value of policy E I1. Before presenting the main results, we first introduce the sub-optimality gaps that will be used.
For each policy æ E 11, define An V=* - V as the sub-optimality gap of π compared with the optimal policy x² E arg max V Further let Amin min Ar be the minimum non-negative value gap.
Definition 1.
Theorem provides regret upper bound for Algorithm 1 in the stochastic setting.
Theorem 2. (Regret bound in the stochastic setting) With probability at least 1 - 8, Algorithm I guarantees that
(dH ddH2log(AA log((s (K) log (1I)
Reg K; IT) SO
(12)
A
Amin
And if the environment is adversarial, the regret Algorithm can be upper bounded as Theorem Theorem 3. (Regret bound in the adversarial setting) With probability at least 1 5, Algorithm I guarantees that
Reg( (K; S 0 10000vvv (Varr log log(K) log ((TT)/0)
(13)
Due to the space limit, the full proof of these two theorems are deferred to Appendix B and C. We will provide proof sketch for them in later sections.
Technique challenge and novelty. There are mainly two types of algorithms to deal with the BoBW problem: the switch-based method which actively detects the environment type, e.g. Bubeck Slivkins (2012), and the FTRL-based method which adapts to different environments, e.g. Zimmert Seldin (2019). The approach in Bubeck & Slivkins (2012) first assumes the setting to be stochastic and would detect whether a policy's 's value has changed. Such an approach in our setting brings an O(VIII) dependence in the regret for adversarial setting which is not idealistic as the policy set size can be large. And the success of FTRL for BoBW mainly relies on a self-bounding inequality that bounds the regret by the chosen probabilities of policies. But such a technique is challenging with linear structure. discussed by Lee et al. (2021), even for the single-state linear bandit setting, connecting FTRL with OP is hard.
Our approach relies on a new observation that the value of each policy can be written as the inner product between the expected state-action visitation feature &x and the unknown reward feature 0. From this view, we are able to reduce the problem to linear optimization and existing techniques for linear optimization can be used. To the best of our knowledge, are the first introduce this type of linear optimization for the regret minimization problem in MDP and such reduction may be of independent interest.
7

---

Under review as a conference paper at ICLR 2023
Relationship between our A and the gap min in He et al. (2021). To compare our A, with gapmin in He at al. (2021), we assume the optimal policy x² E II is just the global optimal policy. Recall that gap is defined as ming, (ga a) gap, (s, a) > 0} where gap, (5,a) = (s)-
(s. In general, A can be decomposed as A (s) VT (s1 = (s1 (s). (si (i)))
gap, (s),a') where the first equality follows He et al. (2021, Eq. (B.2)) and Ph (s, a) is the visitation probability of state-action (s, a) at step h by following т. This shows that Ar 2 p gapmin in the worst case where pd is the minimum none-zero visitation probability of policy T at some state-action pair.
And there are also cases where our defined A is larger than that in He et al. (2021), When both the policy and transition are deterministic (Ortner, 2010; Tranos & Proutiere, 2021; Dann et al., 2021; Tirinzoni et al., 2022), we have A = ->n= gap; (Sh, as)) 2 gapmin And in the stochastic transition case, if all sub-optimal policies happen to not select the optimal action in arg max, (i a). A, = (s1) V (s1) = (s1) - Q7 ($1, a') 2 (s1(
(i{ a') = gapı ($1, a') 2 gapmin where a' is the action selected by π at the first step and the last inequality is due gap, (5), a') O.
In the above two cases, our our sub-optimality gap is larger than previously defined gap and our dependence on the gap is better.
To the best of our knowledge, Algorithm is the first that can simultaneously achieve (poly log K) regret in the stochastic setting and Ö(VK) regret in the adversarial setting for linear MDP problem. is also worth noting that previous works on the separate adversarial setting only provide the upper bound for the expected regret (Neu & Olkhovskaya, 2021), and are the first to provide high-probability guarantee.
5.1 REGRET ANALYSIS IN THE STOCHASTIC SETTING
In the stochastic setting, we consider the regret in two phases of each epoch separately. We first show that, the first phase (which we call as the adversarial phase, Line 3-8 in Algorithm 2) will terminate after ko episodes where ko [64 Ci 900fx and the optimal policy x" E Il can be identified. Lemma I summarizes the formal claims. Lemma 1. In the stochastic setting, in each epoch, the following 4 claims hold.
with high probability,
1. With probability at least 1 48, ko I mmax With probability at least 8, tt- = n²
900 T.
A
3. With probability at least 28, ko 2 GA/KCs
A
4. With probability at least 35, Á, [0.7A,, 1.34]] VT *T"
The detailed proof of Lemma 1 is deferred to Appendix B. We next will give proof sketch of Theorem 2 based on the results of Lemma 1. According to claim I in Lemma 1, we know that kn O (IxCi/A so we can bound the regret in the first phase using the guarantees of Algorithm in Theorem by VC = (oo/loo(K///n
And after ko episodes, the algorithm would transfer to the second phase, which we call as the stochastic phase (Line 9-18 in Algorithm 2). If the environment is truly stochastic, the values of all policies would remain stationary and the detection condition (Line 15 in Algorithm 2) would never be satisfied. Thus the stochastic phase will not end (proved in Lemma in Appendix B). As for the regret suffered in this phase, we can analyze it using the properties of OP. According to claim 4 in Lemma
A / v3A, Thus performing policies based on the solution of OP with Å can reach the real instance optimality.
1, the estimated sub-optimality gap is close to the real sub- sub-optimality gap as Å E
Specifically, we can first bridge the gap between the expected regret and the regret that occurred using Freedman inequality (Lemma 12).
k
2 2 Σ Σds(t) + 2H log (5)
A
1=
1=
Recall that P is computed based on OP under Å, which is close to the real sub-optimality gap A. The regret occurred in phase 2 in episodes larger than problem dependent constant M
8

---

Under review as a conference paper at ICLR 2023
O 3 which is the dominating part in the expected regret, can be bounded using Lemma 7 with /- 3:
72d
=0 [dH ( log(k)
ΣΣ
Amn88
Amin
A
Above all, we can conclude that with probability at least 6, the regret can be upper bounde as
dH dH [ O
dH log()) log (II]K/0)
Reg (I; = O
Amin
Amin
5.2 REGRET ANALYSIS IN THE ADVERSARIAL SETTING
In the adversarial setting, the regret in the first phase can be guaranteed with the property of Algorithm 4 in Theorem Here we will mainly analyze the second phase. We first show that in the second phase of each epoch, the returned policy á is actually the optimal policy in IT.
Lemma 2. For any episode k in the second phase, the policy â has the most accumulated value in 11 during episodes to k. That is, ñ E arg max Σx= V
Since Ω is the optimal policy in II. the regret can be written as the sum of the deviation between the value the selected policy n, and V
V - Vi20)
Σ
[V* -V== (Y.1l = #1 1 # V.²) =
== k0
(V = #) Y, = =)) + (Y, Vim
According to the detection condition (equation 9) Algorithm 2, the first term can be upper bounded by O (VoxCi As for the second and last term, Freedman inequality (Lemma 12) also provides an upper bound O (C) for them. Above all, the regret in single epoch can be upper bounded by O (vTxC According to the choice of the minimal duration each epoch, the length ko of the first phase in an epoch is most half of that in the next epoch. Thus the final regret can be bounded as
Reg (K: O (VC)Klog(K)) = (VdrKBBxlog(())
CONCLUSION
In this paper, we propose the first BoBW algorithm for linear MDP that can simultaneously achieve Oppoly log K) regret in the stochastic setting and Ö(vK) regret in the adversarial setting. Our approach relies on the new observation that the value function of a policy can be written as the sum of the inner products between the expected state-action visitation feature ox, A and the unknown reward parameter 6₂ at different steps h E [H]. And the problem can thus be regarded as an online linear optimization problem.
Apart from these BoBW results, we also propose new analysis that can reach high-probabiliiy regret guarantee for adversarial linear MDP, which also the first such result in the literature.
An important future direction is to remove the assumption of unique optimal policy in the stochastic setting. This assumption also appears in previous BoBW works for tabular MDP (Jin Luo, 2020; Jin et al., 2021b) and linear bandits (Lee et al., 2021) which destroys the generality of the results but challenging to be removed due to the hardness of the BoBW objective and the complex structure of MDP. Extending the current results to the unknown transition setting is also prospective. This is hoped to be solved by some new techniques since the current approach highly depends on the known state-action visitation feature. Deriving an FTRL-type algorithm for this objective is also an interesting future direction. It still remains open even in the simpler linear bandit setting without the transition between different states.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Peter Auer and Chao-Kat Kai Chiang. An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits. Conference on Learning Theory, pp. 116-120. PMLR, 2016.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pp. 463-474. PMLR, 2020.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference on Machine Learning, pp. 263-272. PMLR, 2017.
Peter Bartlett, Varsha Dani, Thomas Hayes, Sham Kakade, Alexander Rakhlin, and Ambuj Tewari. High-probability regret bounds for bandit online linear optimization. In Proceedings of the 21 Annual Conference on Learning T'heoryCCOLs 2008, pp. 335-342. Omnipress, 2008.
Sébastien Bubeck and Aleksandrs Slivkins. The best of both worlds: Stochastic and adversarial ban- dits. Conference on Learning Theory, pp. 42-1, JMLR Workshop and Conference Proceedings, 2012.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimiza- tion. In International Conference on Machine Learning, pp. 1283-1294, PMLR, 2020.
Cheng Chen, Canzhe Zhao, and Shuai Li. Simultaneously learning stochastic and adversarial bandits under the position-based model. AAAI, 2022.
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, pp. 1180-1215. PMLR, 2021.
Christoph Dann, Teodor Vanislavov Marinov, Mehryar Mohri, and Julian Zimmert. Beyond value- function gaps: Improved instance-dependers regret bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 34:1-14 14:1-12, 2021.
David Freedman. On tail probabilities for martingales. 1975.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. In International Conference on Machine Learning, pp. 4171-4180. PMLR, 2021.
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, pp. 4259-4288 PMLR, 2022.
Pihe Hu, Yu Chen, and Longbo Huang. Nearly minimax optimal reinforcement learning with linear function approximation. In International Conference on Machine Learning, pp. 8971-9019. PMLR, 2022.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire Contex- tual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning, pp. 1704-1713. PMLR, 2017.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is q-learning provably efficient? Advances in neural information processing systems, 31, 2018
Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning adversarial markov decision processes with bandit feedback and unknown transition. In International Conference on Machine Learning, pp. 4860-4869, PMLR, 2020a.
Chi Jin, Zhuoran Yang, Zhaoran Wang. and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. Conference on Learning Theory, pp. 2137-2144 PMLR, 2020b.
10

---

Under review as a conference paper at ICLR 2023
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficien algorithms. Advances in neural information processing systems, 34:13406-1341 -3448. 2021a.
Tiancheng Jin and Haipeng Luo. Simultaneously learning stochastic and adversarial episodic mdps with known transition. Advances in neural information processing systems, 33:16557-16566, 2020.
Tiancheng Jin, Longbo Huang, and Haipeng Luo. The best of both worlds: stochastic and adversarial episodic mdps with unknown transition. Advances in Neural Information Processing Systems, 34: 20491-20502, 2021b.
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. The International Journal of Robotics Reseurch, 32(11):1288-1274, 2013.
Dingwen Kong, Ruslan Salakhutdinov, Ruosong Wang, and Lin F Yang. Online sub-sampling for reinforcement learning with general function approximation. arXiv preprint arXiv:2106.07203, 2021.
Fang Kong, Yichi Zhou, and Shuai Li. Simultaneously learning stochastic and adversarial bandits with general graph feedback. In International Conference on Machine Learning, pp. 11473-11482. PMLR, 2022.
Chung-Wei Lee, Haipeng Luo, Chen- Yu Wei, Mengxiao Zhang, and Xiaojin Zhang. Achieving near instance-optimallty and Manimax-optimalle in stochastic and adversarial linear bandits simultaneously. In International Conference on Machine Learning, 2021.
Haipeng Luo, Chen-Ye Yu Wei, and Chung-Wa Wei Lee. Policy optimization in adversarial mdps: Improved exploration via dilated bonuses. Advances in Neural Information Processing Systems, 34:22931- 22942, 2021.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 1rX1v:131..5602, 2013.
Gergely Neu and Julia Olkhovskaya. Online learning in mdps with linear function approximation and bandit feedback. Advances Neural Information Processing Systems, 14:10407-10417, 2021.
Ronald Ortner. Online regret bounds for markov decision processes with deterministic transitions. Theoretical Computer Science, 41 1223330):22 2010.
Aviv Rosenberg and Yishay Mansour. Online convex optimization adversarial markov decision processes. In International Conference Machine Learning, pp. 5478-54885 5486. PMLR, 2019.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwiessrr, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game go with deep neural networks and tree search. nature, 52947587):4844489, 2016.
Max Simchowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. Advances in Neural Information Processing Systems, 32, 2019.
Andrea Tirinzoni, Aymen Al-Marjani, and Emilic Kaufmann. Near instance-optimal pac reinforce- ment learning for deterministic mdps. Advances in neural information processing systems, 2022.
Damianos Tranos and Alexandre Proutiere. Regret analysis in deterministic reinforcement learning. In 2021 60th IEEE Conference on Decision and Control (CDC), pp. 2246-2251. IEEE, 2021.
Ruosong Wang, Russ Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33:6123-6135 2020.
Chen- Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. CoRR, abs/1 Abs/1801.00 003655265, 2018. URL http:/:////ax/ hbsp//bs/1/s /10b 03265.
11

---

Under review as a conference paper at ICLR 2023
Kunhe Yang. Lin Yang, and Simon Du Q-learning with logarithmic regret. In International Conference on Artificial Intelligence and Statistics, pp. 1576-1584. PMLR, 2021.
Jia Yuan Yu, Shie Mannor, and Nahum Shimkin. Markov decision processes with arbitrary reward processes. Mathematics of Operations Research, 34(3):337775, 2009.
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Conference on Artificial Intelligence and Statistics, pp. 1954 1964. PMLR, 2020a.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill, Learning near optimal policies with low inherent bellman error, In International Conference Machine Learning. pp. 10978-10989. PMLR, 2020b.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pp. 4532-4576. PMLR, 2021.
Julian Zimmert and Yevgeny Seldin. An optimal algorithm for stochastic and adversarial bandits. In International Conference on Artificial Intelligence and Statistics, pp. 467-475. PMLR, 2019.
Julian Zimmert and Yevgeny Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22:1-49 2021.
Julian Zimmert, Haipeng Luo, and Chen-Yu Wei. Beating stochastic and adversarial semi-bandits optimally and simultaneously. In International Conference on Machine Learning, pp. 7683-7692. PMLR, 2019.
12

---

Under review as a conference paper at ICLR 2023
A ANALYSIS OF OP
The analysis of OP mainly follows the op problem for linear bandits (Lee et al., 2021) but with the consideration of the special structure of linear MDP. In this section, provide some useful lemmas for OP linear MDP.
Lemma 3. First, consider the constrained optimization problem:
ΣPS 2
min
In(det(Z(()))))
PEAn
h=1
where (n) Ex Pa Pn
The optimal choice of p" yields that:
2dH
Σ
Am S
FETT
(r)) S fAz + dH, Vn ET.
| E (mr)
Proof. Here we relaxed the constraint that pa be a valid distribution on to Σx Ps S 1 since there must be x* where A = 0, so we can always add up the probability on A" to make it a distribution. Applying the KKT conditions and setting the derivatives with respect to each p= in the Lagrangian to zero, we got:
H
2
A
( Σ
A + +
&
Am1
where Agand and À are the respective Lagrange multipliers for the constraints of px 2 0 and En Pa S 1, thus we have À 2 0 and Σx AnP= 0. Multiplying the above equation with p and summing over E II, we got:
2
P 0 M (xxt)
Axpp + dp=
E h=1
#Ell
2
Σ
P ll D 13 + +1.
P
sEll
h=1xell
Notice that:
Σ
1 10 (p-)
Σ
Hm )oTT
#Ell
#Ell
Σ Tr
(p"))
nell
Tr
Σ
Eridr (0")
xell
= d.
Plugging in this result, we got:
2
0=
Σ
P
HH
+
{
2
>
Σ p Å
dHl
#ell
13

---

Under review as a conference paper at ICLR 2023
So that
D S dH. Σ #E
{
and À I Hd since Σreu P 2 0.
Above all,
$ (Ann Ax +2) (( + +1is 5 + dH.
Σ On || (p²)
2
2
Lemma 4. Suppose that for any E {1, (1,2,... H). { π E II } spans Rd Denote pn as uniform distribution on II and let k (0, 2)) For any G C II, there exists distribution on q E PG such that Σ Ii 2. (g S 2dH, where qC spn (1 r))g and Σn (..)
Enen - &
Proof. Denote pG {kPM + (1 k)q lq Pc).
H 1xxx Ex ((4)
min max gEPOi
REG
h=1
min max
Tr
Σ px
Σ yx vo & &
gEP
PEPa
H
max min
Σ
Tr
Σ FEG
Σ Fenl
(14)
PEPe PGP
1m1
H
< max PE
Pr P T.h
Σ
+ (1 (1-w)pa
Ox,n Toh
[I]
h=1
TEG
<2 max PEPo
Tr
Σ sEll
(1
x))p
Σ #Ell
+ +1 x)pa
π
π
=2dH.
Where the second inequality is due Sion's minimax theorem equation 14 is linear in p and convex in q. The last inequality is due to k 2 2'
Lemma 5. Let p- be the solution of OP, Å), then we have
dH
Σ P < o mEN
(15)
Via
Proof. We transform p" in Lemma 3 to solution satisfying OP.
Choosing & as Yk in Lemma 4, and let G = { E Å < 1 construct the distribution
2x q = 1p" + G.r, G.n. where G.. is the distribution stated above with V in Lemma we have for π E G.
vt
H
H 1 (2-1100) S 4dH;
14

---

Under review as a conference paper at ICLR 2023
and for & G,
11
{
V&A
KÂ? 13
M E3 (0) 2 Σ
()
+ dH
+ 2dH
-
+ 4dH.
2
So distribution q satisfy the constraints of OP. For the optimal solution p of OP, we have:
Σ P
FETT
1
Sq
A
2
2
GK
Ar
dH Bk
H
dHH
O
Vk
2vk:
2
vk
Lemma 6. Given(An ExE, suppose there exists unique & such that Ås 0. and Åmin min A. Sn. Let Px the solution of OP(k; A), when h: 2
16dR3g, we have PrEr S 2
34dH
Amink
min Proof. let G2 = { E 11: 2 < Â < 2' and be the largest index that G, is not
empty. Define 2 2A?...
dH3, and
w2 Define the distribution follows:
For π # n.
GuR 2
pn
for म,
P4 = 1 Σ
Pr.
xF#
We show it's valid distribution over II:
A =1 - Σ pr
=1 Σ Σ
2ign
8/R
21 Σ
ΣVΣΣ
3 Gjikk
2
121
121 TEG; jf1
=1 Σ
Σ
2j
n 11
21
121 TEG; jØt
21
Σ
21
Where the last inequality is due to k > For 4 के and π E G
16dH8s
2
Σ
H
Φz (
H I
Σ 11
@
[Ergn
15
2dH
R
+ 4dH
2,
3x
h=1
15

---

Under review as a conference paper at ICLR 2023
For it,
0A,h 2, (p)
1/ ( (x)
h=1
In (p)0*.1 (fonM0TI))
"
@ (
2
h=1
2
( 1| (F)
2H
where the last inequality is due to Cauchy inequality. So that:
Σ
0a.n E2 (1) S 2H
Thus, I satisfy the constraints of OP. Now bound the result of OP. By the optimality of px:
Σ Pr $ Σ P.A.
ΣΣ
2g9GiN
2,9 GLiN
Σ
2j n22 11
2 Å Amii
121 TEG;
dHBg Bk
d.H. Bk
Σ
n22+1 - À Amink
2 2 Å
Amink k
TEG. iti
dH
24dH Br
22
22 -2 Ammink
Lemma 7. Suppose that d E (n vrda). then the solution pa of () k 2 16rdH
Amin
yields that
24rdH
Σ Pr <
Amink
Proof. By the condition on Ar, we have
2 16rdHf
16AH and that A, A.- 0. Thus,
32
2AdH BR
2rr
ΣPA. Vr
Σ
Pa Å, vT
Amink
Amink
#EIl
Where the inequality is due to Lemma 6.
B ANALYSIS IN THE STOCHASTIC SETTING
Proof of Lemma 1. First, we show the following properties, for any ls in phase
C2
V
< c
Σ V v s /C, + KA
1=1
1=1
16

---

Under review as a conference paper at ICLR 2023
Here we denote DEV k, = R V= V
Claim I's proof: Let k = max 900 [.} and assume that phase 1 has not finished at episode A
k. Set न n². and we show that the termination conditions hold with high probability at episode
k. According to the Azuma-Hoeffiie incquality, since Y, V is martingale sequence and that
YY, - VV H,
Σ Y,
v + Vak
V + VC2k
K
V +ik
s=1
VF' + +3 +3V FKCIk,
equation 3 is satisfied. For all π + πT, we have:
, Y, Σ
Vx ( V.) + (v. - -V*' + (Vo' - -v:0) + (V - -Y,)
8=1
<DEV KA, + VCkk C2DEV + Vak 1 SKCK + C2 (VGR++AA KAr) kdr
S O.955A, + 22.1
Since k >
f0 thus kA, 2 30 30.TRCT for all π + n-. So -.95544, +2.1/RCT S A3
-25 15VFkCK
Thus:
k Y. 2
Σ
T + 25 FrCkk.
8=1
8=1
So equation 4 is satisfied.
Claim 2's proof: Using equation 3 and equation 4, we got:
kn
V 2 20 2010200/CCCC SKC Vx #.
(16)
However, with probability at least - 8, for any + N
ka
Ra
V.- + (V -.T + (V.' -.T)
DEV HoiT DEV RO.TT. Kn
< C2 (VCiho + koda)
C2ko - Ko
C₂
<5 SiCoo.
So must have ã x².
17

---

Under review as a conference paper at ICLR 2023
Claim 3's proof: Suppose that ku is: Ag Amin-
64fxC1
Let be the policy with minimal estimated gap, that mmn
ka
Va
V
<ko Amin + DEV ko.
DEV Kar
kg + 22 + ko Ami
C2
2k min + 22fxxCik
$16 SnCko + +2 2x
=18 - FKCiku.
Which contradicts with equation 16.
Claim 4's proof:
A k
SDEV ko. DEV ko
(2/ + KO C2
SVixCiku - A
C2
50.3kgAr
The last inequality is due to ko 2 61
A
So have:
Å E (0.7A, 1.34], VT *
Lemma 8, With probability at least
6, phase never ends.
Proof. For equation 9, decompose it
Y. - V Po(
Y,
V - Vi5t +
VTL - Y,
1[ = =+] #
s=ka-1
== #1
V P.
1(x = #) V
First we deal with the second term, which is martingale difference sequence. It's variance is bounded as:
vT Y, Y, V*
E
11 [IT, =
(T(
(V. =E Y,)²
1
+
E [vV - Y2) (V.x-Y.)'
Ds (+)
22H² (1 (f))
The third term is also martingale difference sequence, whose variance can be bounded as:
27 #} - V.
E
1|TT
2H2 (1 (5)
(+)
18

---

Under review as a conference paper at ICLR 2023
Thus, using the Freedman inequality for the second and third term, we got:
Σ
k
V
Y,
Y,
V
1 (TT
+
V
1 [T,= = - V
P.(
(A(
K (1)
K 8
S8H
Σ
(1- Ps (+)) log
+ GH log
#=
For the first term, we bound it's variance against it's expectation Σ (T(TT) (V² -V follows:
27
E
V
V
Σps(t) (v=- -V:)
Ed((T) (v 1 -v:)) )²
Σ (T) (v++ (v== v.2)
=p. B
(1- io (+)) E
V --
x/#
Sb. (+) 2 (1 - p. (+))
+ (1- P. (f)) H² (2
S4H² (1 -1- pe (+))
Using Freedman incquality for the martingale difference sequence above:
V
#=
K Σ (1-1a- P. (+)) log #=k++1
K
Σ Σ (T) V.ah -V²) + +4H,
+
2H log
5
#=ko+1 (
(17)
K
K
Σ (T) -as) + 4H
(1 - (1- (+)) log
2H
log
σ
#=
#1
K
K
EE 44H
Σ
(1 (1- Ps (f)) log
+ log
=kk+1n
#1
where the last inequality is conditioned on that ग" = न. Using Lemma and equation 31, we have:
36dH
Σ
(a( S
(18)
Amius
12dH 8
1 - D. (f) <
(19)
A
min'
Finally, we have:
Σ
V Y
k1
36dH By log(k)
12dH3,
K
12H
log
+ 8H log
Amin
A2
8
g
#
52dH By log(k)
d.H log(k)
3x
72
(20)
Amin
Amia
/215
ho
30ddH log(k))
(21)
Cx
19

---

Under review as a conference paper at ICLR 2023
where inequality 21 is due to claim 3 that Ku 64fi
37/xC1, A2
inequality 20 is due to Å
Amin
[0.7A, 1.3A] which is claim 4; and SKC1 2 dH² Bx log(k))
So equation 9 is never satisfied.
According to equation 28 and equation 30, we have:
Ap
1.4kAr
V
(k-
-koo)Robk,n
-
10
s=1
Σ
V V
S2VJRCK S2IIKGSSO.
Where the last inequality is due to equation 27. So:
k
ko
k
k& - A
V
(l Ko Robe,
+
Σ
V
V
S
<0.24k
sml
Thus:
1
Å A S Ar 0.24 S A + 0.244, $1.81
0.7
1
A 2 A 0.24A 2 A - 0.24 2 0.39Å.
1.3
So equation 8 is never satisfied.
Proof of Theorem 2. Now, we bound the deviation between the actual regret and the real regret in phase? 2. Using Freedman inequality on the martingale difference sequence As, - Σ (T)
Σ
(T((T) +2
log
Σ kok
E |
+ H log
s=k
Σ
Ei((T) +2
log
H Σ
E [[An.. + H log g
Reg
(22)
1
(p((T) +2
log
H
Σ
Σd((F) + 11 1og
8
s=k
s=kg+1
2 Σ (p.(T)
+ 2H log
5
Denote M be the episode that first satisfy M >
48dH8M
min
For l 2 M, have:
k
Σ PA(T)A = Σ Po
s=M M
36dH B,
(23)
Amius
==M
dH By log(k)
0
Amin
where the inequality is due to Lemma with 3.
20

---

Under review as a conference paper at ICLR 2023
For M, according Lemma 5 we have:
M Σ #=
M Σ
(+)+))===
Σ
PT(T))
s +1
dH3
V
#
ddHBMVA
During phase 1, we have:
900 f00fx&C
Ci Civlog(K) ()
VV.
Ci
50
A
A min
min
Since we condition that phase never ends, we have:
Ci Civlog(K)
dH Bx log(K)
+ 0 (
n. 50
+0
A Amin
A min
dH log( K
[I[]K')
50
Amin
C ANALYSIS IN THE ADVERSARIAL SETTING
Proof of Lemma 2. First, we bound the deviation of estimation in Phase 1. For any episode k in phase 1, we have:
Σ V V. S Vkk- C2
V
#=1
S
VGK (C2 1)
Σ
x V
+
V
V.
a=1
s=1
Thus:
k
フ V
<
VGKK + >V VT. V.
C2 1
1=1
At time kn:
ko
km
V
<
VGKK + Σ
V
C2 -1
1=1
ko 2 2/C + -n Y,
-1
8=1
(24)
ko
2/C +5 +5CK +
Σ
--
8
(TV + RoAA))
-1-1
21

---

Under review as a conference paper at ICLR 2023
Next, we bound the deviation of (k- Ko) Robi,, for π & a.
The variance of V bounded follows:
27
27
H
E
kc,h
h=1
H
2
H
<
H
- H
Σ)
@ 55mh
N,A
A=1
h=1
<HH
S 2H
4dH
Bx
h=1
Using the properties of the Catoni estimator, have:
V
(k-
Ko Robe,
N=
2
A
2 log
Sag
E
V
V
V
Ko
0
x
4 log
||III
8
Sak
H
+ 9dp
(25)
Bx
O
k=
+1
1|1l|
<4
H log
2
9dH
(26)
k=
Where equation 26 is by our choice of af. Since equation? 3 and equation 4 provides that:
1
Ro
V
20
sKC1
201/
(27)
kn
ko
hio
2nd1
we have 9df < Thus have:
Ba
I|II
Σ k=
V (k - Rob
<4, H log
Bx
x=
I|II
4k
<4
H log
3
Kg
16
Combining terms, we have:
km
1.4K4
-
(1:
Robe,
(28)
10
1=1
Finally, we bound the deviation of V* In the first ky episodes, since Å = 0, according to equation 24, we have that:
ko V
V*a
I SfCCiko
(29)
1=1
22

---

Under review as a conference paper at ICLR 2023
In phase 2, since v A
Vi is an unbiased estimator of the true value function, according to
=
Freedman inequality, and that v1 27
=
1 [TTE
= #}}
H²
S 2H2 we have:
A|11 2H log
k|1l
V
2
2Ha log
S Vak.
6
Combining the two terms, we have:
V
V
$2VfxCsk.
(30)
In sum,
k
Σ V - V²²
k-1
V V 2H
kp
v# (k- kn 1)Roba 1, 22 Fx - 1.4(k- - 1)Ax
V V +
2H
10
ko +1
3(k
1)
2k _) --
2
10
where the second to last inequality is due to equation 27, and the last one is due to equation 8.
Proof of Theorem 3. Finally, we proof the regret bound in adversarial setting. For the regret in phase 2, we can decompose it as follows.
V
+1
( - Y2,] + = + #} V.*)
#1
[ #) - Y. = + +Y, ViL))
The first term is bounded by equation 9:
Σ
V 5 (VInCiko).
The second term is a martingale difference sequence since:
E
Y, + + V ( V.91
Y, Y,
- (+) E
+ + P. (T)) V**
p, (i)
=bs (f)
1
B + (1 - p. (+) V.
ps (
=0.
23

---

Under review as a conference paper at ICLR 2023
It's variance is bounded
(Y, YYllTT = [ + V + #} v.=5)
) 21
IE
{1x-
Y
+ (1 - P.. (+)) (v*)
-ps
Pa (ft)
2
SPs (+)
11-
H² + -1-12 ( H²
pa (f)
$2H² (1 N/a (+))
where the last inequality is due to p. (f) 1
The third term is also martingale difference sequence, whose variance is bounded as:
1 1 = = Y, =)) - (Y, (V,--1,))) 21
$ (1 Po (ft) E (Y, - VV
< (1 Do (ft) AH²
Also, we have:
1 1- Do (R) S 7D (+)
1 - (T)
(T)
Σ
Ps (T)
An
S
12dH Ba
(31)
2 x
Amin
A min 8
Thus, using Freedman inequality on the last two terms, we got:
V
V
Ao
k
k
dH
00
VKKCTkO +
log
2
+ log
5
a min s
(32)
log
k
dH (kg(k)3kko
+ H log k
5o
VInCiko +
SKC1
<o (VIKCıko)
Combining with the regret in phase 1, the regret in one epoch is bounded as:
Σ V - s O
S (VTCCiko)
Since the duration time ko of phase is least twice the length of phase I in the previous epoch, we have that the sum of vko in all the epochs is bounded by an constant factor of the square root of duration time in phase 1 of the last epoch, which is bounded by VK. Summation over all the epochs, we have:
Reg (K; =0 -VVC:Klog(k))) =0 (VV
[I 8
24

---

Under review as a conference paper at ICLR 2023
Algorithm 4 Geometric Hedge for Linear Adversarial MDP Policies
log
1: Input: policy set II, 7 = min
2
K
11
TH
2: Initialize: VT E II, w1 (x) 1, W1 I wh from to H. compute the G-optimal design
Oh (T) on the set of feature visitations: (0n,n, π E IT]. Denote g(x) = 2 (T)
3: for each episode & = 1 to K do
4: VIT E 11.
wh (T)
Pke (x) (1)=
+ +g((T)
W
5: Select Fi. E according to the probability pk (T) and collect rewards Uk.h E bWlk,h and kk = o 0K V/ E "ih
6: Calculate reward estimators: 0n.n
where Σk = En Pk (
7: Compute the optimistic estimate of the value function:
H
log (1:
Fr, + +20 2,,000
dK
h=1
8: And we transform it into loss functions:
L (sh, an) = (s) 12,1 = 1 r7
H
T k.h
H
VE,
h=1
H
H Vi.
k,
h=1
h=1
LE
H
Vi
9: update using the loss estimators:
VT E IT, ( = (T)( exp (-ni,z) W = Σ (
xell
10:
end for
D
HIGH PROBABILITY GUARANTEE FOR ADVERSARIAL LINEAR MDP
First, we bound the deviation between the estimated value and the true value of policy
Lemma 9. Denote DEV K.
Ei=1
V
V
then have:
K
K
DEV K.*
VE
Σ
Lg
L
k=1
k=
K
H
H log (tt)
+ Ozp dKH log (2) +2
dH²
!
H
log
C2
Ex
dK
k=
Proof. First, we show that V is an unbiased estimate of VI=
H Σ
V = Σ
E
E 1
kih
h=1
h=1
25

---

Under review as a conference paper at ICLR 2023
using the tower rule of expectation, have:
E
EE @xxe RRi,b
13 - Dk.
E
VE
Σ
o Ok, = V/
Denote o² =E Var Vi=)
then:
H
2
Ps. 2x Millee
k=
K
H
2
E
k=1
h=1
K
||
1=
A=1
Also, due to the properties of G-optimal design, we have:
1 | (M( )+ S d,
and Σx, = 31 Ex
x. Thus we have | Euth S HP VI II, V S
dh
Using
7
?
Freedman incquality, the sum of the martingale difference sequence V
V is bounded as:
K
K H
1r 12 log (1)
+ dHH +
VE
< 2
log
3
k=1
k=1
h=1
K
H log (t)
d.H
+ C2y dKH log
+
log
C2 where the last inequality is due to the geometric mean-arithmetic mean inequality. Lemma 10.
dk
8
K
L
Pk
(T)
k=1
K
Pk
(T)
Σ
V
k=1
<H (va+1)
dH²
1
2K log
+
+
log
3
Proof.
K
K ΣΣ h=1
(
VT
Σ ( -rb.
(33)
A=1
k=1
Using lemma in Bartlett et al. (2008), we have;
Σ
(vá+1) /
2K log
+ 4 /dH + +1) log (1)
3
1=1
Since 0
dH
Plugging it into equation 33, we finish the proof.
26

---

Under review as a conference paper at ICLR 2023
Lemma 11.
With probability least 1 8, we have
Σ E (T)) (Iz) I 2(d 1)KH² +2 dH3
8dH log (1)
2K log
7
Proof. Since ig = H
V (ig]
+ H2, we have: $ Vi
Σ
pT((T) (iz)
(T) (vx)
+ KH²
k=
R=1
Using
inequality, we have:
(VT)
H Σ
)²
2
k.n
h=1
So,
K
Pe(TT) (FK.
k=
Pe (TT) &T O
K
1h Ok.h
k=1
tu Sk.lh 1i Pmcch
km
Notice that using the definition of Σn, and properties of the G-optimal design,
E
2 Th
d,
dH
TT. k,
mmin 5
7
Applying the Hoeffding bound, we got:
Pe(x) (FT.N) I dK + dH
& V 2 log ())-
A=
Thus:
K
(T) (VE))
H K
<H
Pt(
(17,1)
h= k=1
<2KH² + d.H33
(3)
1
2K log
27

---

Under review as a conference paper at ICLR 2023
And:
H LE
log (1) dK
[
Σ
2Φ 0z,h)
H
Aml
2
H
log (1) dK
22
[
+2
Σ
20
To
nh
k.
H
h=1
52 17
2
+ 2H
H1
4 All
1
5-1
H log (1) dK
h=1
dH
H
Hlog (1) dK
22
+ 2H
+ 8
Σ
?
h=l
So conclude that:
(T( (ix)) 2
k=1
K
(T) (iz) 2
8H log 8
Σ> ΣΣ> Σ
Pk (TT o - P
k=1h=1
<2 + 1)KH² + dH3
11
SdHf3 log (t)
2K log
+
?
Proof of Theorem 1. Now analyze the potential function. Using classical techniques, we got that counter part of equation (2) in Bartlett et al. (2008):
K
Wk W
WR
log
log
WK-1
1=1
K
Wx((T)
Wh-1 exp (-ntiz)
log
K
(T())
-9m
(1-ntž + 17 (T.z) 2)
log
(34)
7-7
k=1
Pk (TT
(T(TT)
11
(-nIž + 1² [I
1 1-7
Am
K
Σ
+ +
Σ Σ
g(()))
1
Σ Σ pT( (iz)
(35)
?
k=1
k=1
28

---

Under review as a conference paper at ICLR 2023
where inequality 34 is due to the constraint that n S 1.
Using Lemma 10, we have:
K
P
k=1
x
log (3) dK
Px( +
Ph:
Σ
Σ
pkc p
E Fkh H
k=
k= h=1
K
1
Pk (T)
+ 2H
log
k=1
x
dH²
Li
H (v V 22 log
H
log
+
+2H
2H
dK log
(8)
7
Using Lemma and choosing C2 2' we have:
log (3) dk
Σ
L% + DEV ΣΣ
20 n, 2x. /
E-1
H
k=1
k=1
k=1h=1
dH2
L +
dKH log
+
+ H
log
k=1
1 {
dH²
SKH + 2\
dKH log
+
+ 1
log
Thus equation 35 becomes:
log
WK
K W
S 17
K
Li + H (vā+1)
2K log
(t)+
+
4
H +
dH²
log
5/2
+ 2H V dKH log
1
dH²
+ 21,y KH +1
2\
dK H log
+2
+
log
2(d 1)K +2 dH3
(2)
8dHH3 log
(1)
+ 277
2K log
+
dH3
1
8dH log (1)
Σ
+ 21²
2(d 1)H2 +
2K 2Klog
7
k=1
H (Vd ( 1)
1
dH²
1
2m
2K log
H +
log
+
2H
dKH log
+217 KH +1
1
dK log
1
+2
dHz
+ H
log
=
1
2
?
(36)
29

---

Under review as a conference paper at ICLR 2023
And also have for V'T II,
W k
log
27
log (IIT)
W1
k=
K
H
log (3) dK
21
Σ
LE DEV
k.
26 20
log (II1)
1==1
(37)
where the last inequality is due to Lemma 9. Plugging equation 36 and equation 37 together, we have that for Vε II:
K
log (t)
LE <DEVET
ΣΣ
2 2x
Pr,
dK
k=
h=1
dH²
log I1
+4
+ H
log
+
+ 5H V
dK log
3
2H (va+1) 1)
2K log
+
8
H
dHH2
log
dH3
112
16nd log !
22KH 4n (d (d+1)KH1²
2K log
7
7
(38)
[1 and 7 S 1/4 When K 2 Lo 4dH log
dH²
H log (+)
4dH²
H + VT S H + i
+ 2\
dK
So the choice of शतस ensures | < becomes:
Plugging in our choice of n, equation 38 then
Σ Th L <
(
1
-2)
Σ
K
Σ
2
0rch
log (?)
C2
dK
+ 0
Varrok log
1
dHz
log
|I|
7 KK
7
Choosing C2 1/2 we have:
K
(
11 {55
dH²
|II
Σ L 50
datsk log
log
+ + KK
(39)
1=1
log
10
at log
And by our choice of 7 -in
we have:
K
K
(
Reg (K; II)
<
L
nb
LT
50
Varr log
III
(40)
8
k=1
30

---

Under review as a conference paper at ICLR 2023
For K & Lo = 4dH log ( we have:
(V log
Reg (I;II) <KHS (KLHH-O
(41)
8
Combining equation 41 and equation 40, we prove the regret bound.
Moreover, when K 2 Lo. choosing C2 2 20 and recalling the definition of DEV k,z in Lemma 9,
T 4:
nh
LE
K
H
log (3) dk
2 h E 0T,
k=
Am1
)
dH²
II
+0
dH K log
log
+ 7 K H
?
daHss log (2)
dH²
< - C-C2EV +0
log
KK
Applying a union bound for all the possible kn E {1,2, ... K}. we conclude with at least probability 1 6, we have:
VE
V S VCiko C2DEV Ko. ko.
1=1
(HH log [ijk] ))
With the constant C1 = O
2 dH2 proving Theorem 1.
E CONCENTRATION INEQUALITIES
Lemma 12. [Freedman inequalityl Freedman, 1975)] Let Fo C Fi .... C be a filtraiion and let X1, 22,X2,... XT be random variables such that X, is Ft measurable, [x = 0, [X < almost surely, and ΣT [x]1= V for some fixed V and b 0. Then, for any 5 E (0,1), have with probability least 6,
T
Σ
X. S 2 2 Vlog (1/8) + blog (1/8)
Lemma 13 (Concentration inequality for Catoni estimators (Wei & Luo, 2018; Lee al., 2021))- Let Fo C Fi C ... C F be filtration and let X2, X,, be random variables such that X, is Fr measurable, E. [[] = p4i for some fixed pi, and Σn E -x,, 11) <
[
for some fixed V. Denote
En pr and let Pn. be the Catoni's robust mean estima- tor of X1,X2, Xn with a fixed parameter a, that is, Pn.a is the unique root of the func- tion: f(z) En & (X, z)), where (ly) log (1 (1+y y x²² 1²12) if 2 and D(y)
-log (1 1-11 y2 22) otherwise.
Then for any 5 E (0, 1), as long as n is large enough that n 2 a V E (14 - w))
2 log (1/8), we have with probability at least 1 - 28,
Aina - a ((V + Ei= (Ei 112)
2 2log (1/0)
+
n
an
31

---

Under review as a conference paper at ICLR 2023
Choosing optimally, we have:
2 11
n
Pn.a 11
2
V
(ei - u)²
log (1/0).
In particular, if pn 122
Mm we have:
2
Lin.a 10| S n
2V 2olog (1/6).
32


Reviews:
[{"review_id": "v0DZ7lKxuk", "reviewer": "Reviewer_GWBz", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 studies linear MDP with possibly adversarial rewards. The authors propose a detection-based algorithm that can simultaneously learn stochastic and adversarial linear MDP. Assuming a known probability transition, it is shown that the proposed algorithm can achieve logarithmic regret in the stochastic case and sublinear regret in the adversarial case.", "summary_of_the_review": "I think this paper studies a meaningful setting and the results are solid. But the overall writing can be further improved, and see detailed comments above. I didn't carefully check the proof in the appendix.\n\nBesides, I have a few more questions as follows:\n\n- In the definition of the Q-function, normally people would include the reward received at the current step, i.e., $r_{k,h}(s,a)$\n- The loops in Algorithm 1 and 2 are a bit weird. Should provide a stopping criterion, otherwise it's not clear when the algorithm ends.\n- If assuming a known transition, do we still need to require the transition probability to be linear? I think without the linear assumption on the probability transition, the value function can still be written as a summation of inner products between the expected feature vectors and the parameters of the rewards.\n\n\n\n---\nOther minor problems:\n\n- Near the bottom of page 5, should be 'standard least square estimators'\n- Under Algorithm 3, should be 'fool the algorithm'", "strength_and_weaknesses": "Strength:\n\n- The authors have done a good job reviewing the related literature.\n- This paper studies an interesting problem of simultaneously learning stochastic and adversarial linear MDP, and the result presents a best-of-both-worlds guarantee.\n- The theoretical analysis provides a high-probability regret guarantee for adversarial linear MDP.\n\nWeaknesses:\n\n- Given the existing literature on RL with function approximation, I believe the setting of linear MDP is already well-motivated. So for the introduction, the authors should discuss more the motivation of best-of-both-world type algorithm and, more importantly, explain the challenges in the algorithm design and theoretical analysis, compared with existing results.\n- Following the previous point, please explain the technical challenges induced by the setting of linear MDP and the novelty of the proposed method.\n- The description of the proposed algorithm in Section 4 is a bit difficult to follow. I would suggest the authors put more effort into reorganizing this section for readability. More specifically, Algorithm 4 seems to be an important subroutine, but it is not clearly explained what this algorithm is doing and why we need it. The description on page 5 could be more carefully structured using some highlighted words/sentences. Also, please provide references to existing related methods in other settings and compare them.\n- It seems crucial to assume a finite policy set. Why is this a reasonable assumption for linear MDP? For example, consider the LSVI-UCB algorithm where the policy is given by the greedy policy w.r.t. the estimated Q-function, and in this case, the policy set is infinite. Even if using a covering argument for the policy set, it would introduce additional dependence on the dimension. Please justify this assumption and discuss its limitation in detail.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "abK3Bfut_od", "reviewer": "Reviewer_WXEg", "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": "The submission studies the BoBW problem under a new setting. The submission proposes and analyzes the first BoBW algorithm for linear MDP with high-probability regret bounds (Algorithm 1). A secondary result is the first algorithm achieving a high-probability regret for the adversarial liner MDP (Algorithm 4).", "summary_of_the_review": "The submission has substantial contributions to the BoBW problem. However, if allowing $|\\Pi|$ to be infinity is the distinctive advantage of function approximation, the concern (e) raised above should be resolved. Therefore, I would like to recommend weak acceptance in the current stage.", "strength_and_weaknesses": "- (a) The submission develops a new component (Algorithm 4 and Theorem 1) for the main algorithm.\n- (b) What prevents the authors from directly analyzing the regret under the general function approximation setting?  \n- (c) The submission did a great job explaining the roles and jobs of the components of the main algorithm. The proof sketch is also easy to follow. It would be better if there were discussions about why other works fail, and how this work succeeds would better justify the technical contributions of this submission.\n- (d) What prevents the authors from removing the known transition assumption? Why can't we leverage existing works on unknown transitions?\n- (e) The paragraph above Section 5.1 discusses a way to handle the case when $\\Pi$ is infinitely large (which is why function approximation was developed to replace the tabular methods). However, simply combining $Reg(K)$ with (14) and (15), the $|\\pi|$ term is still there in the bound. Is there any misunderstanding?\n", "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": "Gzq1hQhjBG4", "reviewer": "Reviewer_PB4v", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 authors tackle the setting of linear MDPs with known transition but unknown reward that achieves $\\text{polylog}(K)$ regret over $K$ episodes when the rewards are stochastic, and $\\tilde O(\\sqrt{K})$ regret when the rewards are adversarial. ", "summary_of_the_review": "A theoretical paper that tackles an interesting and clearly important problem. However, I am not convinced that it tackles the problem sufficiently to distinguish itself from past works. I am willing to consider raising my score if the reviewers provide a response that alleviates my concerns.", "strength_and_weaknesses": "The authors tackle an interesting problem and derive a new algorithm that achieves a \"best-of-both-worlds\" guarantee. The paper is clearly written, and the problem tackled is interesting. However, I do have some technical concerns.\n\n1. I would like some elaboration on the covering approach used to move from finite hypothesis class $\\Pi$ to infinite hypothesis class. Let's say, for example, that I want my hypothesis class to be the set of policies $\\pi_h(s) = \\text{argmax}_a \\langle \\phi(s, a), w_h) \\rangle$ for some weights $w_h$---that is, $W = (w_1, \\dots, w_H) \\in \\mathbb{R}^{d \\times H}$ parameterizes my Q estimates. Naively, I would try to $\\epsilon$-cover the space of all such $W$ by considering discretizations of (say) $[0, 1]^{d\\times H}$ to precision $\\epsilon$. We would thus have $|\\Pi| = (1/\\epsilon)^{dH}$. \n\n    **a)** This would lose factors of $\\sqrt{dH}$ and $dH$ in the adversarial and stochastic regret bounds respectively. I feel like that means it is worth making explicit in the paper--it *does* \"influence the main order of the regret\".\n\n    **b)** If we use such a cover by exponentially many functions, is the algorithm stated in the paper efficient? Many steps in the algorithm seem to involve enumerating policies $\\pi\\in\\Pi$, which would take exponential time.\n\n1. The factor $\\Delta_\\min$ used in this paper seems quite unusually small. For example, Jin & Luo (2020) are able to achieve a bound in the tabular setting with $\\Delta_\\min := \\min_{h, (s, a):a \\ne \\pi^*(s)} V^*_h(s) -  Q_h^*(s, a)$ (which is larger, at least if the hypothesis class $\\Pi$ consists of all deterministic policies). Is it possible for this paper to match that $\\Delta_\\min$?\n\n1. The algorithm seems broadly extremely similar to Lee et al (2021)'s algorithm for the (non-MDP) bandit setting, applied to the set of arms $\\mathcal{X} = \\\\{ \\phi_{\\pi, \\cdot} : \\pi \\in \\Pi \\\\}$. What, if any, is the difference here? \n\nMore generally, it does not seem as though this paper is really using any feature of MDPs--instead, it seems that it is directly applying a non-MDP result to the MDP setting and simply ignoring most of the structure of the MDP. As a result, the main theorems of this paper do not look like what I would typically expect MDP results to look like--for example, I would expect MDP results to have dependencies on \"local\" properties such as the larger $\\Delta_\\min$ (see point 2 above) and \"local\" hypothesis classes, rather than the \"global\" $\\Delta_\\min$ and \"global\" policies $\\pi \\in \\Pi$. \n\nMinor detail: at various points throughout the paper, $O(\\sqrt{K})$ should be $\\widetilde O(\\sqrt{K})$ since the adversarial regret has $\\log K$ dependencies.", "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": {}}]

Author rebuttal:

Decision: Reject