Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimization
Authors: Fang Kong
XiangCheng Zhang
Baoxiang Wang
Shuai Li
Venue: Accepted by TMLR ()

Abstract: Learning Markov decision processes (MDP) in an adversarial environment has been a challenging problem. The problem becomes even more challenging with function approximation since the underlying structure of the loss function and transition kernel are especially hard to estimate in a varying environment. In fact, the state-of-the-art results for linear adversarial MDP achieve a regret of $\tilde{\mathcal{O}}({K^{6/7}})$ ($K$ denotes the number of episodes), which admits a large room for improvement. 
In this paper, we propose a novel explore-exploit algorithm framework and investigate the problem with a new view, which reduces linear MDP into linear optimization by subtly setting the feature maps of the bandit arms of linear optimization. This new technique, under an exploratory assumption, yields an improved bound of $\tilde{\mathcal{O}}({K^{4/5}})$ for linear adversarial MDP without access to a transition simulator. The new view could be of independent interest for solving other MDP problems that possess a linear structure.

Published in Transactions on Machine Learning Research (01/2024)
Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimization
Fang Kong" Shanghai Jiao Tong University
jongkong@ustu.edu.co
Xiangcheng Zhang
tc-zhang21 Comails wwwggus..iiiggaaa..oooooo hainaaiissinguu..cc....r edu..c
Tsinghua University
Baoxiang Wang The Chinese University of Hong Kong, Shenzhen
briianguonggecukk.ddd.ccmm
Shuai Li
shuaili8@sjtu.edde edu.cnn
Shanghai Jiao Tong University
Reviewed on OpenReview:
Abstract
Learning Markov decision processes (MDP) in adversarial environment has been chal- lenging problem. The problem becomes even more challenging with function approximation since the underlying structure of the loss function and transition kernel are especially hard to estimate in a varying environment. In fact, the state-of-the-art results for linear adver- sarial MDP achieve a regret of Ö(K%/T) (K denotes the number of episodes), which admits a large room for improvement. In this paper, we propose a novel explore-exploit algorithm framework and investigate the problem with a new view, which reduces linear MDP into linear optimization by subtly setting the feature maps of the bandit arms of lincar opti- mization. This new technique, under exploratory assumption, yields an improved bound of O(K1/5) for linear adversarial MDP without access to transition simulator. The new view could be of independent interest for solving other MDP problems that possess a linear structure.
1 Introduction
Reinforcement learning (RL) describes the interaction between a learning agent and an unknown environ- ment, where the agent aims to maximize the cumulative reward through trial and error (Sutton and Barto, 2018). It has achieved great success in many real applications, such as games (Mnih et al., 2013; Silver et al., 2016), robotics (Kober al., 2013: Lillicrap et al., 2015), autonomous driving (Kiran et al., 2021) and recommendation systems (Afsar et al., 2022; Lin el. al., 2021). The interaction in RL is commonly portrayed by Markov decision processes (MDP). Most works study the stochastic setting, where the reward is sampled from fixed distribution (Azar et al., 2017; Jin et al., 2018; Sinchowitz and Jamieson, 2019; Yang et al., 2021). RL in real applications is in general more challenging than the stochastic setting, as the environment could be non-stationary and the reward function could be adaptive towards the agent's policy. For example, a scheduling algorithm will be deployed to self-interested parties, and recommendation algorithms will face strategic users.
To design robust algorithms that work under non-stationary environments, line of works focuses the adversarial setting, where the reward function could be arbitrarily chosen by an adversary (Yu et al. 2009;
"Equal contribution.
1 "Corresponding author.

---

Published in Transactions on Machine Learning Research (01/2024)
Rosenberg and Mansour, 2019; Jin et al., 2020a; Chen et al., 2021; Luo et al., 2021a). Many works in adversarial MDPs optimize the policy by learning the value function with a tabular representation. Tn this case, both their computation complexity and their regret bounds depend on the state space and action space sizes. In real applications however, the state and action spaces could be exponentially large or even infinite, such as in the game of Go and in robotics. Such cost of computation and the performance are then inadequate.
To cope with the curse of dimensionality, function approximation methods are widely deployed to approxi- mate the value functions with learnable structures. Great empirical success has proved its efficacy in wide range of arcas. Despite this, theoretical understandings of MDP with general function approximation are yet. to be available. As an essential step towards understanding function approximation, linear MDP has been an important setting and has received significant attention from the community. It presumes that the transition and reward functions in MDP follow a linear structure with respect to a known feature (Jin et al., 2020b; He et al., 2021; Hu et al., 2022). The stochastic sctting in lincar MDP has been well studied and near-oplimal results are available (Jin et al.; 2020b; Hu el al., 2022). The adversarial setting in linear MDP is much more challenging since the underlying linear parameters of the loss function and transition kernel are especially hard to estimate while having to adapt to a varying environment.
The research on linear adversarial MDPs remains open. Farly works proposed algorit hmss hms when the transition function is known (Neu and Olkhovskaya, 2021). Several recent works explore the problem without a known transition function and derive policy optimizaation algorithms with the state-of-the-ar regret of Ô (K (Luo et al., 2021a; Dai et al., 2023; Sherman et al., 2023; Lancewicki et al., 2023). While the optimal regret in tabular MDPs is of order Ô (K1/2) (Jin et al., 2020a), the regret upper bounds available for linear adversarial MDPs seem to admit large room for improvement.
In this paper, we investigate linear adversarial MDPs with unknown transitions. We propose a new view that transforms linear MDP to a linear optimization problem by regarding the expected state-action visitation features in MDP as the feature of arms in linear optimization problem. Our algorithum constitutes an exploration and exploitation phase. In the exploration phase, we estimate the feature visitations of the policies in the constructed policy set using reward-free estimation techniques. Then, in the exploitation phase, we operate on set of policies and optimize the probability distribution of which policy to exccute. By carefully balancing the suboptimality in policy construction, the suboptimality in feature visitation estimation, and the suboptimality in policy execution, we deduce new analyses of the problem which achieves the first Ô (K4/5) regret bound for linear adversarial MDPs without a simulator. Let d be the feature dimension and H be the length of each episode. Details of our contributions are as follows.
With an exploratory assumption (Assumption 1), we obtain an H12//5 bound for lincar adversarial MDP. As compared in Table 1, this is the first regret bound that achieves (K445) order when a simulator of the transition is not provided. We also want to note that our exploratory assumption that only ensures the MDP is learnable is much weaker than previous works (Neu and Olkhovskaya, 2021; Luo et al., 2021a). Under this weaker exploratory assumption, our result achieves significant improvement over the Ö(K577) regret in Luo et al. (2021a) and also removes the dependence on X in the main order term which is the minimum eigenvalue of the exploratory policy's covariance that can be small.
regret upper
In a simpler setting where the agent has access to a simulator, our regret can be further improved to O(vi2H&)) This result also removes the dependence on À in the main order of previous works (Neu and Olkhovskaya, 2021; Luo et al., 2021a). Compared with Luo et al. (2021a), our required simulator is also weaker: we only need to have access to the trajectory when given any policy n, while Luo et al. (2021a) requires the next state s' given any state-action pair (s,a).
Our results are the first that achieves 1(K1/2) high probability-tppe regret bound for linear adversar- ial MDP with a simulator and ((K4/5) regret without a simulator when the exploratory assumption holds. Previous works for high probability-typ regret only achieve ((K2/3) bound with access to a simulator for the lincar-Q setting (Lancewicki et al., 2023). And Dai et al. (2023); Luo et al. (2021a); Sherman et al. (2023) which are based on the policy optimization approach are only able to produce the upper bound for the expected regret.
2

---

Published in Transactions on Machine Learning Research (01/2024)
Technically, provide new tool and simpler analysis for linear MDP problems by exploiting the linear features of the MDP and transforming it into a linear optimization problem by setting the expected feature mappings of different policies as arms, We also provide a refined analysis of the Hedge algorithm where the features are approximated instead of being preciscly given. This approach differs from previous policy optimization based algorithms and could be of independent interest in other problems that possess a linear structure.
Table 1: Comparisons of our results with most related works for linear adversarial MDPs.
Exploratory
Simulator
Regret
Computation complexity
Assumption
Neu and Olkhovskaya (2021)* yes yes
O(VK/M
dd, H, (KAH))(H))
yes yes
O(VK/A)
O(K273)
Luo al. (2021a)
no
Ö ( K/ (K/(A)) (A)228)
no yes
poly([A), d, K)
O(K14/15)
n1
n1 Ö(VK)
(KAH)O(H) 5
yes
Dai et al. (2023)
no
O(K8/9)
( d, H, K)
Ö(K2/3)
Sherman al. (2023)
ycs
no
poly([A), d, H, K)
O(K7))
no no
Ö(VK)
Ours
yes
yes
O(K*75 +poly(1A))) KO(dH²)
yes
1 The simulator required in this paper is defined in Assumption 2. Note that the simulators adopted in Dai et al. (2023) and Luo et al. (2021a) are stronger that returns the next state s' when given any state action pair (s, a), while Sherman et al. (2023); Neu and Olkhovskaya (2021) and this paper only need the simulator to return a trajectory given a policy. Our simulator can be implied by theirs.
2 Our exploratory assumption introduced in Assumption 1. It worth noting that our assumption on exploration is also much weaker than Neu and Olkhovskaya (2021); Luo et al. (2021a;b). Specifically, our exploratory assumption only ensures the learnability of the MDP while the other works require policy that can explore the full linear space in all steps. Our assumption can be implied by theirs.
3 X in the regret represents the minimum eigenvalue induced by "good" exploratory policy no. which satisfies Amin (Amo.A) 2 A for all h E [H], where A A is the covariance of To at step h (see Assumption 1). The algorithm of Neu et al. (2010) requires full knowledge of the transition kernel.
5 The exponential complexity is due to the exponential number of calls to the simulator when constructing the dilated bomus Luo et al. (2021a) and Dai et al. (2023).
2 Related Work
Linear Stochastic MDPs. The linear function approximation problem has been studied for a long history (Bradtke and Barto, 1996; Mclo and Ribeiro, 2007: Sutton and Barto, 2018; Yang and Wang, 2019). Until recently, Yang and Wang (2020) propose theoretical guarantees for the sample efficiency in the linear MDP setting. However, it assumes that the transition function can be parameterized by a small matrix. In general cases, Jin et al. (2020b) develop the first efficient algorithm LSVI-UCB both in sample and computation complexity. They show that the algorithn achieves Ó ((V13 H²K) regret where d is the feature dimension and и is the length each episode. This result improved to the optimal order Odd /K) by Hu et al. (2022) with a tighter concentration analysis. A very recent work (He al., 2022a) points out a technical error in Hu et al. (2022) and show a nearly minimax result that matches the lower bound ((d/H3)) in Zhou et al. (2021). All these works are based on UCB-type algorithms. Apart from UCB, the TS-type algorithm has also been proposed for this setting (Zanette al., 2020). The above results mainly focus on minimax optimality, and it is also attractive to derive an instance-dependent regret bound it changes in MDPs
3

---

Published in Transactions on Machine Learning Research (01/2024)
with different hardness. 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 (d H log K/A) where A is the minimum value gap in the episodic MDP.
Adversarial losses in MDPs When the losses at state-action pairs do not follow a fixed distribution, the problem becomes the adversarial MDP. This problem was first studied in the tabular MDP setting. The occupancy measure-based method is one of the most popular approaches to dealing with potential adversary. For this type of approach, Zimin and Neu (2013) first study the known transition setting and derive regret guarantees Ö(HVK) and O(VHSAK) for full-information and bandit feedback, respectively, For the more challenging unknown transition setting, Rosenberg and Mansour (2019) also start from the full-information feedback and derive an Ó(HSV regret. The bandit feedback is recently studied by Jin et al. (2020a), where the regret bound OHHSVAK). The other line of works (Neu et al., 2010; Shani et al., 2020; Chen et al., 2022; Luo et al., 2021a) basod on policy optimization mothods. In the unknown transition and bandit feedback setting, the state-of-the art result in this line is also an Ō(VK) order achieved by Luo et al. (2021a;b).
Specifically, few works focus the linear adversarial MDP problem. Neu and Olkhovskaya (2021) first study the known transition setting and provide an Ō(VK) regret with the assumption that an exploratory policy can explore the full linear space. For the general unknown transition case, Luo et al. (2021a:b) discuss four cases on whether a simulator is available and whether the exploratory assumption is satisfied. With the same exploratory assumption as Neu and Olkhovskaya (2021), they show a regret bound Ō(VK) with a simulator and O(K7/7) otherwise. Very recent two works (Dai al., 2023; Sherman al., 2023) further generalize the sctting by removing the exploratory assumption. These two works independently provide O(K*/9) and Ö(K5/7) regret for this setting when no simulator is available. It is worth noting that the above works provide guarantees for the expected regret. For the stronger higb-probability regret objective, Lancewicki et al. (2023) provide an O(K2/$) upper bound when a simulator is available.
Linear mixture MDP is another popular linear function approximation model, where the transition is a mixture of linear functions. When considering the adversarial losses, Cai et al. (2020) and He al. (2022b) study unknown transition but fulliinorrmation feedback type, in which case the learning agent can observe the loss of all actions in each state. Zhao et al. (2023a) consider the general bandit feedback in this setting and show the regret in this harder enviromment is also Ö(vK). Their modeling does not assume the structure of the loss function which introduces the dependence on S,A in the regret. Apart from linear function approximation, Zhao et al. (2023b) also consider the adversarial losses in low-rank MDPs under full-information feedback.
3 Preliminaries
In this work, we study the episodic adversarial Markov decision processes (MDP) denoted by M(S, A, H, ( {( where S is the state space, A is the action space, H is the horizon of each episode, PA : S Ax S S [0,1] is the transition kernel of step h with Pa(s' s, representing the transition probability from a to s' by taking action a at step h, and &g is the loss function at episode k. We denote T = [ as the learner's policy at each episode k, where T a mapping from cach state to a distribution over the action space of step h, and let Ta,a(a 8) represent the selecting probability of action at state by following policy Fe at step h.
The learner interacts with the MDP M for K episodes. At each episode k = 1.2.... K, the environment (adversary) first chooses the loss function la = { which may be probably based on the history infor- mation before episode k. The learner simultaneously decides its policy गं. For each step h = 1, .,,,....4 H, the learner observes the current state sk,k, takes action 4x,a based on kk.a: and observes the loss l (Sk, ax The environment will transit to the next state sk,t+1 at the end of the step based on the transition kernel (- 8k,h, a..h)-
4

---

Published in Transactions on Machine Learning Research (01/2024)
The performance of policy over episode & can be evaluated by its expected cumulative loss, also known as the value function defined as below:
V E Σ (aa))
where the expectation is taken from the randomness in the transition and the policy n. Denote म² E arginin, -k=1 V as the global optimal policy that sulfers the least expected loss over K episodes. The objective of the learner is to minimize the cumulative regret which is defined the cumulative difference between the value of the taken policies and that of the global optimal policy n²:
K
Reg( K)
Σ
Vill V
Linear adversarial MDP denotes an MDP where both the transition kernel and the loss function are linearly depending on a feature mapping. We give a formal definition as follows.
Definition 1 (Linear MDP with adversarial losses). The MDP A, MDP if there is known feature mapping & S x A + Rdd and unknown signed measures ph.1,---. Phid S + R. forming μn = ( (h,a) S Rd such that the transition probability for any 8, a, h satisfies
(lx)k=1) is a linear
Pa a1 = ()(s,a),
Further, for any episode k and step h, there enists on unknown loss vector Og E TRd such that
(s,n(s, = (ő(s, On.n)
for all state-action pair (s, a). Without loss of generality, we assume 11 (s, a) I 1 for all s,a, Illall (S) ||ves Idun (s)lll Vd, [|0,,l12 Vd for any k. h, and (s,n(s,a) 1 for all k. h, 8,a.
Given policy π, its feature visitation at step h is defined the expected feature mapping this policy encounters at step following policy @n.h E, [ó (sh, an)], where E, [ denotes taking expectation w.r.t the randomness of state transitions and policy æ. Then the expected loss that the policy receives at step h of episode & can be written as
C. = E, Kenh (Sk. 0k.N = ( 0k.h)
(2)
and the value of policy a can be expressed as
H
H (m,,, 0n.0)
V
Σ
Σ
(3)
h=1
A=1
For simplicity, also define &x (s) Eawn (o(s, a)] to represent the expected feature visitation of state at step & by following
For any policy n, define An, == Egor Jaws [Ø(sn, an (s) T as the expected covariance of π al step h. Let Aiiu, = sup, Amin (Ar,h), where Xmni(.) denotes the smallest. eigenvalue of a matrix, and >i mins x Analog to previous works that study the function approximation setting (Neu and Olkhovskaya, 2021: Luo al., 2021a: Hao al., 2021; Agarwal et al., 2021), we make the following exploratory assumption to ensure efficiency in exploring the transition dynamics:
Assumption (Exploratory assumption). A > 0.
When the assumption reduced to the tabular setting, where d(s, a) basis vector in RSAA, this as- sumption becomes Punn := ming max, min, j (s a) > O, where μ (s, a) the probability of visiting the state-action pair (s,a) under the trajectory induced by It simply means that there exists policy with
5

---

Published in Transactions on Machine Learning Research (01/2024)
positive visitation probability for all state-action pairs, which is standard (Li et al., 2020). In the linear setting, it guarantees that all the directions in Rd are able to be visited by some policy.
We point out that this assumption is weaker than the exploratory assumptions used in previous works (Neu and Olkhovskaya, 2021; Luo et al., 2021a), in which they assume such exploratory policy To, satisfying Amin (Aro.h) 2 λ > for all h E [H], is given as input to the algorithm. We only assume such policies to exist, which only requires the transition kernel of the MDP to satisfy certain constraints, while finding an exploratory policy is extremely difficult task.
4 Algorithm
In this section, we introduce the proposed algorithm 1. At a high level, the algorithm is based on our proposed new view that transforms the linear MDP to linear optimization problem by regarding the state-action visitation feature as arms. It takes finite policy class II and the feature visitation estimators (0m, т E II, h E [M] as input and optimizes the probability of selecting each policy in IT. The acquisition of Il and ( π 11, h [H]} will be introduced in Section 4.1 and Section 4.2, respectively.
Recall that the loss value (s, a) is an inner product between the feature o a) and the loss vector 0k. According to this structure, we investigate ridge linear regression to estimate the unknown loss vector. To be specific, in each episode after executing policy Th, the observed loss value can be used to estimate the loss vector 6.. and the value function Vi can be estimated for each policy π (line 9). We then adopt an optimistic strategy toward the values of policies and an optimistic estimation of any policy a's value (line 10). Basod on the optimistic value, the exploitation probability w(rr of a policy æ follows an EXP3-type update rule (line 11). To better explore each dimension of the linear space, the final selecting probability is defined as the weighted combination of the exploitation probability and exploration probability g(T), where the weight is an input paramcter (line 7). Here the exploration probability 9n (x)) is derived by computing the G-optimal design problem to minimize the uncertainly of all policies, i.e.,
Gh. E argmin max PεA(M) well | -
where (p( EvET & This exploratory probability can ensure the magnitude of Vk.r being bounded. As for the computation complexity, outlined Lattimore and Szepesvári (2020, Note of Chapter 21), the optimal design can be approximated efficiently within O(d log log d) ilerations, yielding g(T) that
satisfies the following inequality:
max #ell
S min max PEA(II) #Ell (u(p))
S 2d.
And the constant approximation factor will not change the order of the regret.
If the input δr,b is the true feature visitation Φr,h; we can ensure that the regret of the algorithm compared with the optimal policy in II can be upper bounded. Now it suffices to bound the additional regret caused by the sub-optimality between the optimal policy in II and the global optimal policy, and the estimation bias of the feature visitation, which will be discussed in the following sections.
4.1 Policy Construction
In this subsection, we introduce how to construct finite policy set II such that the global optimal policy x² can be approximated by elements in II. The policy construction method mainly follows Appendix A.3 in Wagenmaaer and Jamieson (2022) but with refined analysis for the adversarial setting.
We consider the linear softmar policy class. Specifically, given a paramcter = fw where wn E Rd.
the induced policy "" would select action E A at state with probability
exp(n(ó (8, a) wx)) The (a|s) = Ee exp (1/ (s, a²), wr))
(4)
6

---

Published in Transactions on Machine Learning Research (01/2024)
Algorithm GoometricHedge for Linear Adversarial MDP Policies (GLAP) ) Input: policy class II with feature visitation estimators ( for any 11, confidence 6, exploration parameter S 1/2
2: Initialize: VT E II, w1 (T) - -, W, [[]] 7
do 4: Compute the G-optimal design go (T) on the set of feature visitations: (6 7 E 113. Denote g(T)
3: for h= 1,
H Eh=19h (T))
5: end for
6: for each episode = 1,2..... . do
7:
Compute the probabilities for any policy π E II:
we (TT)
Pk (Λ) = (1-7)
+ (g(
WR
Select policy wa ~ Pk and observe losses Ex,h (8K, b; ok,a), for any h [H]
Calculate the loss vector and value function estimators:
H
Ozp = Sinhh Doann (KR,h, aR.a) Cr = ST. 0n. V
Σ
Vn E II
h=1
where =n ( Compute the optimistic estimate of the loss function
10:
log (t)
(h,n- - 2
Vx E II
dK
h=1
11:
Update the selecting probability using the loss estimators
VT E IT, (T)) (x( exp (-nV²) Wk+1
Σ (
sell
12: end for
The advantage of such policy class is that given two parameters and u, the value difference between policies induced by them can be upper bounded by the difference between and u, i.c.,
V="
2dHn
E1w - unll2
k=1
where 7) > the parameter in Equation 4. Recall that the structure of linear MDP guarantees that the optimal value can be represented by a linear function, i.e., there exists a weight vector w" (wi)) where |,l < 2d such that Q7, (s, a) = (é(s,a), wg), Vh E [H] (Jin et al., 2020b). Then by constructing a parameter covering W over (dIl for some accuracy E, we can ensure that the optimal parameter w be approximated by parameter w W i.e., Σn ||w, w < Hc. Further based on the above property, the optimal value W can be approximated by the value Va" of some linear softmax policy " with WH. The result of constructing such policy covering shown briefly in the following lemma.
Lemma 1. In the linear MDP problem, there crists a finite policy class II with log cardinality log |I| O (dH2 log K), such that the regrel Keg(K;I] II) compared with the optimal policy in II is close to the vegret Reg(K) compared with the global optimal policy, i.e.,
K
K min
K
Reg K) = Σ k=1
(v
V
V
v +1= Reg KIII) +1.

---

Published in Transactions on Machine Learning Research (01/2024)
The detailed analysis can be found in the Appendix C.
4.2 Feature Visitation Estimation
this subsection, we discuss how to deal with unavailable feature visitations of policies. Our approach is estimate the feature visitation f 1f for each policy and use these estimated features as imput of Algorithm 1. The feature estimating process is described in Algorithm 2, which is called the feature visitation cstimation oracle.
Algorithm 2 FEATURE VISTATION ESTIMATION ORACLE
Imput: policy set I1, tolerance 1/2, confidence å Initialize: 3 = 16 log (o/(4////[1///)) Φr, Bar (d(s)
for h = 1.2..... ..... H do 4: Run procedure in Theorem 2 (Appendix B) with parameters: Coxp + 2/((3)) 8 - 8/(2H), 411())
< 2n (ôn, II, 74 1/(2vd), and denote returned data ) for K2 total number of running episodes, and covariates as [S 4, Sh+ (,) 1=1
A h
(8h,7; (h,7) di (sh.r; (b.r) 1/d.
5: for π E II do
Kn pnh+1 (8h-1,7) oh. gad
where dx (s) = E (1s a)].
end for end for return T b= (0 E 1,2,..., ,
Under linear MDP, for any policy n, first decompose its feature visitation at step h
* ES (6(s8, an)] /
(T.(())duT
=Tr,ndTmn-1
T .T..i..TTTT22m, Tn,20
where T = f (s.n())dpnnn is the transition operator and Φx,1 = (0( (1)) can be directly computed based on policy æ. Thus, to estimate Φx.h for each step h, we need to estimate all transition operator (Ta,))
We use the least square method to estimate the transition operator. Consider currently we have collected K trajectorics, then the estimated value is given by
K t argmin I (To
Σ T(alsa)o(ss.)) a))² + 2
T=1
and the flosod-form solution is that
K
trA =
Σ
((8h-1.7 an ah- 1x (onor) Am
8

---

Published in Transactions on Machine Learning Research (01/2024)
where (51r)) = Ea ((als)))((s) a), and
K (sh (1.0h-h,...-1,)006
A Σ
00 + AI.
Tn order to ensure the accuracy of the estimated feature visitation, we provide guarantee for the accuracy of the estimated transition operator. The intuition is to collect enough data in cach dimension of the feature space. For the design of how to collect trajectories, we adopt the reward-free technique in Wagenmaker and Jamieson (2022) and transform it to an independent feature visitation estimation oracle. At a high level, the reward free algorithm aims to collect transition data in as few interactions as possible that minimize some uncertainly measure, which is approximately maxş || in our setting. To achieve this, instead of maximizing expected reward as standard RL, the algorithm take some uncertainty objective as a surrogate reward and instead optimize over it. The detailed discussion can found in Appendix B. Algorithm 2 satisfies the following sample complexity and accuracy guarantees.
Lemma 2. For any O, 8 E (0, 1), with probability at least 1-6 8, Algorithm 2 could return feature visitation estimation for every policy II in at most Ô (d* 122) episodes that satisfies
| - -aann se/vd, vh E (M)
where Ô here hides log factors and lower order terms.
Since the regret in an episode is less than H, the total regret incurred in the feature estimation process is of order Old ((dt:4/e).. The detailed analysis and results can be found in Appendix B.
5 Analysis
This section provides the regret guarantees for the proposed Algorithm as well as proof sketch. Consider Algorithm 1 with the policy set II constructed in Section 4.1 and the feature of policics estimated in Scction run Algorithm for K rounds. The regret compared with any fixed policy II in these K rounds can be bounded as below.
4.2 input. Suppose
Lemma 3. With probabilily at least 1 6, for any policy n E II,
K (V
11
dH2
II 8
dH2
Vi v====0
= O Hy dk log 8
log
+ +7KH* +
eK
standord regret bound of EXP3
fenture estimation hins
where is the tolerance of the estimated feature visitation bias in Algorithm 2.
Recall that when the policy set is constructed as Section 4.1, the difference between the global regret defined
in Equation (1) and the regret compared with the best policy in II is just constant. So the global regret is in the same order as the regret bound shown in Lemma 3.
Similar to previous works on linear adversarial MDP (Luo et al., 2021a;b; Sherman et al., 2023; Dai el al., 2023) that discuss the cases of whether transition simulator is available, we define simulator in the following assumption.
Assumption 2 (Simulator). The learning agent has access to simulator such that when given policy n, it returns a trajectory based on the MDP and policy π.
It is worth noting that this simulator is weaker than that in Luo et al. (2021a); Dai et al. (2023) which needs to generate the next state given any state-action pair. the learning agent has access to such a simulator described in Assumption 2, then the feature estimation process Soction 4.2 can be regardod as regret-free and the final regret is just shown in Lemma 3. Otherwise, there is an additional Ö(d H H/)2) regret term. Balancing the choice of and yields the following results.

---

Published in Transactions on Machine Learning Research (01/2024)
Theorem 1.
With the constructed policy set in Section 4.1 and the feature visitation estimation process in Section 4.2, selecting < = (KK2//5)) the cumulative regret salisfies
Reg( K) =0 (1/5 log 1og (K/0) (K/0)
with probubility at least 1 6, where C1 = poly (d, H, log 1 1/6, 1/Xmin m log K) is a lower order term. Addition- ally, if Assumption 2 holds, the regret upper bound can be improved to
Reg(K) = (V
Due to the space limit, the proofs of the main results are deferred to Appendix A.
Discussions In this work, we adopt a new view that transforms the problem of linear adversarial MDPs into a linear optimization problem. Under this view, we propose a novel explore-exploit framework and show that it achieves the state-of-the-art result in the literature with the cost that the computational complexity depends the size of the policy covering. Compared with previous works that focus on local properties using policy optimization, our approach provides a completely different design philosophy that globally optimizes the policy set. This framework may be of independent rescarch interest for theoretically analyzing the lincar MDP problem.
Since our work mainly aims to improve Luo et al. (2021a) with an exploratory assumption, we specifically discuss the difference between our work and theirs. It is worth noting that though both works provide guarantees for problems with exploratory assumption and transition simulators, our required assumptions are much weaker and can be implied by that in Luo et al. (2021a).
Benefiting from this new view, our work improves the regret bounds in Luo et al. (2021a) only using weaker assumptions. As shown in Table 1, our result 0(K4/5) explicitly improve the result Ö(KG/T) in Luo et al. (2021a). And it also achieves the state-of-the-art dependence on the horizon K compared with existing works (Luo et al., 2021a; Dai et al., 2023; Sherman et al., 2023). Recall that the result Luo et al. (2021a) also depends on where À is the minimum eigenvalue in the exploratory assumption. In real applications, for each direction in the linear space, it is reasonable that there will be a policy that visits the direction. So one could ensure the exploratory assumption by mixing these policics. However, there is no guarantee the value of X, and the regret depending on 1/A can be very large when À is very small. Compared with Luo et al. (2021a), we remove the dependence of À in the main regret order term
When a transition simulator is available, the number of calls to it (query complexity) is also important to portray the efficiency of the algorithm. Our query complexity O(K2) (the detailed computation is provided in Appendix A) is much more preferred than ((AH)))) in Luo et al. (2021a).
Another important advantage is that our approach can deal with the infinite action space. In some common applications including autonomous driving and robotics, the size of the action space may be infinite. However, previous works fail to apply in these settings as their approaches need to enumerate the entire action set or solve an optimization problem on the action space A(A) (Dai et al., 2023; Luo et al., 2021a; Sherman et al., 2023). We deal with this problem by putting a finite action covering over the action space when constructing the policy set in Section 4.1. More technical details can be found in Appendix C.
It also worth noting that our result achieves the first high-probability regret bound for linear adversarial MDP, given that previous works based on policy optimization approaches only guarantee the expected regret (Luo et al., 2021a; Dai et al., 2023; Sherman et al., 2023).
To conclude, our work improves the results in Luo et al. (2021a) in terms of weaker assumplions, better regret bounds, fewer queries to the simulator (if we use one), and can deal with more general infinite action space with the cost that the computational complexity depending on the size of the policy covering. But we want to note that this dependence of computation is also standard in the reduced linear bandit problem when the cardinality of the decision set is large (Dani et al., 2007, Lemma 3.1).
10

---

Published in Transactions on Machine Learning Research (01/2024)
6 Conclusion
In this paper, we investigate a new view for linear MDP that transforms the visitation feature of policy as the feature of an arm in the lincar optimization problem. Based on this view, we propose a framework that uses the estimated visitation features of policies as input and optimizes the selection probabilities of all candidate policies. With an exploratory assumption, we provide the first O(K4/5) regret without access simulator. Our algorithm enjoys a weaker assumption and a better regret bound with respect to both K and À compared with the results in Luo et al. (2021a).. It also achieves the first high-probability type regret guarantee and can deal with the infinite action space compared with existing works for linear adversarial MDP (Luo et al., 2021a; Dai et al., 2023; Sherman et al., 2023).
Our view contributes a new approach to linear MDP; which could be of independent interest. Future implications of this technique could involve solving other adversarial settings, such as when the loss function is corrupted up to budget, and solving robust linear MDP where the transition kernel could change over episodes. Deriving lower bounds for linear adversarial MDP also important direction.
Acknowledgements
The corresponding author Shuai Li is supported by National Key Research and Development Pro- gram of China (20222D0114804) and National Natural Science Foundation of China (62376154, 62076161). Baoxiang Wang is partially supported by National Natural Seience Foundation of China (62106213, 72150002, 72394361) and Shenzhen Science and Technology Program (RCIBS90210009904336600,, JCY320010834120011101 1032).
References
Afsar, M. M., Crump, T., and Far, B. (2022). Reinforcement learning based recommender systems: A survey. ACM Computing Surveys, 55(7):1-38
Agarwal, N., Chaudhuri, S., Jain, P., Nagaraj, D., and Netrapalli, P. (2021). Online target Q-learning with reverse experience replay: Efficiently finding the optimal policy for linear mdps. arXie preprint 2XX.v:2110008400
Azar, M. G., Osband, I., and Munos, R. (2017). Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263 272. PMLR.
Bradtke, S. J. and Barto, A. G. (1996). Linear least-squares algorithms for temporal difference learning. Machine learning, 22(1-3):33 57.
Cai, Q., Yang, Z., Jin, C., and Wang, Z. (2020). Provably efficient exploration in policy optimization. In International Conference on Machine Learning, pages 1294-1294. PMLR.
Chen, I.., Luo, H., and Rosenberg, A. (2022). Policy optimization for stochastic shortest, path. In Conference on Learning Theory, pages 982 1046. PMLR.
Chen, L., Luo, H., and Wei, C.-Y. (2021). Minimax regret for stochastic shortest path with adversarial costs and known transition. In Conference on Learning Theory, pages 1180 1215. PMLR.
Dai, Y., Luo, H., Wei, C.-Y,, and Zimmert, J. (2023). Refined regret for adversarial mdps with linear function approximation. Xix preprint arXiv:2301.22942
Dani, V., Kakade, M., and Hayes, T. (2007). The price of bandit information for online optimization. Advances in Neural Information Processing Systems, 20.
Freodman, A. (1975). On tail probabilities for martingales. The Annals of Probability, 3(1):100-118
Hao, B., Lattimore, T., Szepesvari, C., and Wang, M. (2021). Online sparse reinforcement learning. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, pages 316-324. PMI.R.
11

---

Published in Transactions on Machine Learning Research (01/2024)
He, J., Zhao, H., Zhou, D., and Gu, Q. (2022a). Nearly minimax optimal reinforcement learning for linear markov decision processes. arXiv preprinl or vrXim:2212.06133
He, J., Zhou, D., and Gu, Q. (2021). Logarithmic regret for reinforcement learning with linear function approximation. In International Conference on Machine Learning, pages 4171 1710-180. PMLR.
He, J., Zhou, D., and Gu, Q. (2022b). Near-optimal policy optimization algorithms for learning adversarial lincar mixture mdps. In International Conference on Artificial Intelligence and Statistics, pages 4259-4280. PMLR.
Hu, P., Chen, Y., and Huang, L. (2022). Nearly minimax optimal reinforcement learning with linear function approximation. In International Conference on Machine Learning, pages 8971-9019. PMTR.
Jin, C., All, Z., Bubeck, S., and Jordan, M. (2018). Is Q-learning provably efficient? Advances in Neural Information Processing Systems, 31.
Jin, C., Jin, T., Luo, H., Sra, S., and Yu, T. (2020a). Learning adversarial markov decision processes with bandit feedback and unknown transition. In International Conference on Machine Learning, pages 4860 4869. PMLR.
Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. (2020b). Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-21433 PMLR.
Kiran, B. R., Sobh, I., Talpaert, V., Mannion, P., Al Sallab, A., Yogamani, S., and Pérez, P. (2021). Deep reinforcement learning for autonomous driving: survey, IEEE Transactions on Intelligent Transportation Systems, 23(6):4909-499)
Kober, J., Bagnell, J. A., and Peters, J. (2013). Reinforcement learning robotics: survey. The Interna- tional Journal of Robotics Research, 32(11):1238 1274.
Lancewicki, T., Rosenberg, A., and Sotnikov, D. (2023). Delay-adapted policy optimization and improved regret for adversarial mdp with delayed bandit feedback. ar preprinl arXin:2305.079)
Lattimore, T. and Szepesvári, C. (2020). Bandil algoritlems. Cambridge Universily Press.
Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2020). Sample complexity of asynchronous Q-learning: Sharper analysis and variance reduction. Advances in Neural Information Processing Systems, 33:7031- 7043.
Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Frez, T., Tassa, Y., Silver, D., and Wierstra, D. (2015). Continuous control with deep reinforcement learning, arXiv preprint arXic:1509.0200
Lin, Y., Liu, Y., Lin, F., Zou, L., Wu, P., Zeng, W., Chen, H., and Miao, C. (2021). A survey on reinforcement learning for recommender systems. arXiv preprint NXw:2109.10663
Luo, H., Wei, C.-Y., and Lee, C.-W. (2021a). Policy optimization in adversarial mdps: Improved exploration via dilated bonuses. Advances in Neural Information Processing Systems, 34:22931-22942
Luo, H., Wei, C.-Y., and Lee, C.-W. (2021b). Policy optimization in adversarial mdps: Improved exploration via dilated bonuses. ar Xiu preprint arXim:2107. 07.08346.
Melo, F. S. and Ribeiro, M. T. (2007). Q-learning with linear function approximation. In Learning Theory: 20th Annual Conference on Learning Theory, COLT 2007, Son Diego, CA, USA; June 13-15, 2007. Proceedings 20, pages 308-322. Springer.
Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglon, I., Wierstra, D., and Riedmiller, M. (2013). Playing atari with deep reinforcement learning. arXiv preprint arXiv: 1812..666.
Neu, G., György, A., Szepesvári, C., et al. (2010). The online loop-free stochastic shortest-path problem. In COLT, volume 2010, pages 231 243.. Citeseer.
12

---

Published in Transactions on Machine Learning Research (01/2024)
Neu, G. and Olkhovskaya, J. (2021). Online learning in mdps with linear function approximation and bandit leedback. Advances in Newral Information Processing Systems, 14:10407-10417.
Rosenberg, A. and Mansour, Y. (2019). Online convex optimization in adversarial markov decision processes. In International Conference on Machine Learning, pages
PMLR.
Shani, I.., Efroni, Y., Rosenberg, A., and Mannor, S. (2020). Optimistic policy optimization with bandit feedback. In International Conference on Machine Learning, pages 8604 8613. PMLR.
Sherman, U., Koren, T., and Mansour, Y. (2023). Improved regret for efficient online reinforcement learning with linear function approximation. ar preprint arXiv:2301.13077
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Pannecrshelvam, V., Lanctot, M., et al. (2016). Mastering the game of go with deep neural networks and tree search. nalure, 529(7587):4844445)
Simchowitz, M. and Jamieson, G. (2019). Non-asymplotic gap-dependent regret bounds for tabular mdps. Advances in Neural Information Processing Systems, 32.
Sutton, R. S. and Barto, A. G. (2018). Reinforcement learning: An introduction. MIT press.
Wagenmaker, A. and Jamieson, K. (2022). Instance-dependent near-optimal policy identification in linear mdps via online experiment design. arXiv preprint arXiv:2207.08575.
Yang, K., Yang, I.,, and Du, S. (2021). Q-learning with logarithmic regret. In International Conference on Artificial Intelligence and Statistics, pages 1576 1584. PMLR.
Yang, L. and Wang, M. (2019). Sample-optimal parametric Q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004. PMLR.
Yang, L. and Wang, M. (2020). Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pages 10746-10756. PMLR
Yu, J. Y., Mannor, S., and Shimkin, N. (2009). Markov decision processes with arbitrary reward processes. Mathemalics of Operalions Research, 34(3):737-775 -57.
Zanette, A., Brandfonbrener, D., Brunskill, E., Pirotta, M., and Lazaric, A. (2020). Frequentist regret bounds for randomized least-squares value iteration. In International Conference on Artificial Intelligence and Statistics, pages 1954-1964. PMLR.
Zhao, C., Yang, R., Wang, B., and Li, S. (2023a). Learning adversarial linear mixture markov decision processes with bandit feedback and unknown transition. In International Conference on Learning Repre- sentations.
Zhao, C., Yang, R., Wang, B., Zhang, X., and Li, S. (2023b). Learning adversarial low-rank markov decision processes with unknown transition and full-information feedback. In Thirty-sevente Conference on Neural Information Processing Systems.
Zhou, D., Gu, Q., and Szepesvari, C. (2021). Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference Learning Theory, pages 4532 4576. PMLR.
Zimin, A. and Neu, G. (2013). Online learning in episodic markovian decision processes by relative entropy policy search. Advances in Neural Information Processing Systems, 26.
13

---

Published in Transactions on Machine Learning Research (01/2024)
A Analysis of Algorithm 1
In this section propose the regret analysis for Algorithm and prove the final regret bounds for main algorithm. We will state the necessary concentration bounds lemmas first and then analyze the regret, proving Lemma 3 and Theorem 1. In the following analysis, we will condition the success of the event in Theorem 3, whose probability is at least 1 1- 8. The following inequality will be used in the analysis and is restated the beginning.
C Fr be filtation and let X2. -r be random variables such that X, is Ft. measurable, E [X 0, [xel S b almost surely, and Σ:= E [x] S V for some fixed V > 0 and > 0. Then, for any 5 E (0, 1), have with probability at least 1 6,
Lemma 4 (Theorem 1.6 in Freedman (1975)). Lel Fo C Fi
X 2 (1/8) + blog (1/8).
To start with, we give the concentration of the feature visitation estimators returned from Algorithm 2, which will be fundamental in the following analysis. Notice that शr, can be computed directly from the initial state distribution and action distribution.
Lemma 5. Suppose the estimation accuracy can be guaranteed as Theorem 3, which holds with prob- ability at least 8. Then we have for all episode and steps h, the feature visitation estimators (gmne h = 1,2, ... H E ET] returned by algorithan 2 satisfy:
(On, den - 2a.n) Se
Proof. Since [10xhll2 S Vd for any ls and h, as in Definition 1, according to Theorem 3, we have:
(0k.n: @n.ii s |2nn @malll 110k, Vd vd
The following Lemma and Lemuna will bound the magnitude for the loss and value estimators in line 9, using the properties of G-optimal design computed in line 4.
Lemma 6. |
dH and ④T 1
0n. < dH for all h and a II.
Proof. According the properties of G-optimal design, we have:
| Ex (x)ddn,NOO Sd.
and Dan Ex 96 @ Thus have |
||
dH So:
1-1
7
0T, 0kin
f Aeen (SKA, anw) - =l
@oai 1-1 S
dH
Vι E II,
where the second last inequality is due to the bound (n,n(sp, an) 1.
Lemma 7. With our choice of zah when K 2 Lo = 4dH log function estimator Vg. |nVe < 1.
111 (T)):
we have for all oplimistác loss
14

---

Published in Transactions on Machine Learning Research (01/2024)
Proof. To make sure |nVE S By Lemma 6, we have
notice that:
H
H Hogg 1/6 dK
VE S
20 n. 2 Σ
(5)
Am1
dH2
log 1/8
V
1 1
2
dK
When K 2 Lo 4dH log
) we have |
2dH
Thus, our choice rj = z satisfy this constraint.
Throughout the following analysis, assuming have rum for some number of episodes K, we let (FR)k=1 the filtration on this, with F& the filtration up to and including episode k. Define Eg [-] = E [-Fa-i)) The next lemma will bound the bias of the loss vector estimator, thus we can bound the bias of the value function estimator.
K
= Ex @u. fu (SK,n, axn)) as the expected value of the loss veclor Lemma 8. Denole Eith = Ex [0.
estimator on Fk-1- Then we have for VTT E II, with probability least 1 1-6 8, the returned feature visitation estimators satisfy:
(ār,h. okth) - (dr,n, Okchh s
dH +1 +1)
2dH c.
c
?
As resull, we also have (ō 0g/p)
24H
7 +
Proof. Using the tower rule of expectation, we have:
Ee ( Ok.na] Ex. Σ Pk (T') 2
Thus,
lōn.n. 02.))
(8m.n. Ok.n)
@ S-1 E
pk (5') @0r,1 (0t. - Ox.n
Σ Ph (7')
1h Su Sen (0t - (z. Okn
Σ Pke (x') d.H. dH c,
where the last inequality is due to Lemma 5 and Lemma 6. Moreover, we also have that (0r.n &n,h, 02.11) & e. Combining the two terms, we proof the lemma as:
(0 O (ohm 0A.N) < (i 0mxp) - (6 ORnn + Kθn - on. 0kn s dH +
Lemma Denote DEVK., K. EK V
VØl
then we have with probability at least 1 8,
H Hlog (2) dKK
1
DEV K.T
52
dKH log 8
2
k=1 1=1
dH²
2dH² cKK
+
log
15

---

Published in Transactions on Machine Learning Research (01/2024)
Proof. First, we bound the bias of the estimated loss of each policy after episode & in step h:
f k = T 0u.h 2x,10n.
22,h R.h
gexp 8T.
- ( 2 000p
2dH
The first term is a martingale difference sequence as Ex pn,h 0ahh
by the definition 2
in Lemma To bound magnitude, notice that (T,n 0i,h T
0 k.
S
T 0n, + 1 OK. +
@T, 1hhh ST,nOu. I dH +1+ 2dH I 2dH according to and Its variance is also bounded as:
Be (JT (JnnOunh 1
2
BR
TT. Ok, Sn O
Exe
Cer (sk. .. GT o th Ex Sn.h)
12 < @Gr,h
S
where the last inequality is due to the fact RR @o tc.h = Sek, and |eE, (on,,,x,,)) S Freedman incquality, we acquire with probability al least 1 - 8:
Using the
DEV K.r
H
K
2dH
2dH
2
1 h
log
log
+
eK
h=1
K
2
(1)
1
2dH²
2dH
2
H
log
8
log
cK
k.a
K
H
log (1)
dH²
2dH²
@
d. H log
+
log
eK
dk
2
8
where the second last and last inequality is due to the Cauchy Schwartz inequality and GM-AM inequality.
Lemma 10. We bound the gap between the actual regret and the expected estimated regret. With probability at least 1 1-6 8,
K
K
2dH (Vd+
1) V 2K log x +
8dH²
1 log 8
2dH² + 2H dK log
Pk (T) VE < 11
7 eK.
37
1=
k=1
Proof. Denote tu.n = En Pk (TT) Sm.n we have that :
Σ Pk (TT) Eg = Bkkn - TK.
= - n b. + (TT. -2h00.))
16

---

Published in Transactions on Machine Learning Research (01/2024)
2dH _ +
(ØT (
Notice that Ex
T gexpl n2 R.h.
= Ek (oh, 8k.n).
We bound its conditional variance as follows:
V ER (oF 0ae - -khDma))
2
] +
(oknOha)) 31
SV Es
Bk
(6)
2dH
c+1+
Pkim -
(7)
?
2dHl
6+14
Σ ph (TT) ST 21,
(8)
2dH 6+1 C+1++ VVd,
(9)
where incquality 6 is duc to Cauchy Schwartz incquality and 8 is due to Jenson incquality. Morcover, s 2dH Applying Bernstein's Inequality, we obtain with probability least 1, 6,
@ k. 2b 0
Σ v
Pk (T)
Vh
kh Σ pa (T) E
k=1
k=1
h= k=l
< H
Vd++
2dH1
ạ c ++111 V
2K log
1
+
8 8
log + 2dH
eK.
3
Y
Since Vr -V = b=
20 =
k.
H log 1/8 dk
have:
Σ pk (T) (vr - -V²)
K ΣΣ
Σ
2p (T) 8T Sr,
H log 1/8 dK
k= 1=1
2HH dKH log 1/5.
Combining the two terms, we prove this lemma.
Lemma 11. With probability at least - 5, we have:
(T( (V2)² 22KH2 dH3
1
8dH log (3)
2K log
7
7
Proof.
27
Σ Pk (T)) (VT)²
Σ Pk (T)
2 (VV
2
+2 Σ
2p (T) IT --12
H log 1/8 dK
2
H
2
H log (1) dK
Pk (T)
2H
@T.1
8T 2 Sn,h
h=1
P& (T)
2
8
dH
H
* Ei.n -1 -
I
H log (+)
Y
dK
h=1
Pk (TT)
(i
SdH log 1/8
(10)
17

---

Published in Transactions on Machine Learning Research (01/2024)
Vx 2 (PE,)) we bound the first term as follows.
Since
Σ ps (x)) (PE.))
2
S Σ Pke (T) oE O S 2
Its conditional expectation is Eg @T
-k, xx.. = =x ph (T)
(T. 1 and also (J $-1
te - -K.Poan
AH
Thus, applying the Hocffding bound, we have with probability at least 1-6, 8,
K
H
dH V2K log 1/6 - dkHf + dH3 V2K log 1/6. 7
ΣΣ Pk (T) (vE)
SH
Σ dk
+
1m
Am1
Plugging it into 10, we finish our proof.
Proof of Lemma 3. Now ready to start analyzing the regret. Using classical potential function analysis techniques in similar algorithms, have:
W WK+1
Wk-1
log
log
W1
Ws
Σ WK((T)
log
exp (-n)a²)
Wh
k=
(T( - 19 (1- niV + n? (Vz)2)
log
(11)
1-7
Am
Pk (TT) 79a
(-nVE + n² (Vz)²)
1-7
K
K
V + Σ Σ V + Σ (T) (vz)²
(12)
1=1
k= a
k=
where inequality 11 is from InV term as:
< 1 guaranteed by Lemma 7. Using Lemma 9, we can bound the second
log (t) dK
V
+ DEV K.sT
2 n. - Sor
k=1h=1
K
dH²
2dH2
V +
dKH log
+ 2
log
④ +
eK
(13)
2
k=1
1
dH²
2d.H2 +
SKH
dK H log
+
log
cK.
2
7
Plugging Lemma 10, Lemma 11 and Equation (13) into Equation (12), notice we condition on y S 1/2, we obtain:
WK+1 W1
dH3
8d log (2)
log
27²
2dKH2 +
2K log
+
dH²
2dH²
+ 2 +1
d.K H log
+2
+2
log
+
ck
(14)
2
7
7
+ 2n
H
Vd
2dH
e +1
2K log
+
d1
log
1
+ 2H V
dKH log 3
2dH²
ek
3
7
z
7
18

---

Published in Transactions on Machine Learning Research (01/2024)
Combining terms, we have:
Wx+1 log
Σ
v +0 H H dy log
1
O
(
dH!
log
1
+ > KH
k=1
(15)
+ +
midkII+
ndH3
2K log
1
+ O dHH eK Syd log (7))
7
7
Plugging 17
into Equation (15), we have:
dH²
log
WK-1 Wi
V
+0 +
H dK Hog log 5)
0
(dH
log
1
+ 7KH)
+ +0 +(
(16)
8
"
km
On the other hand, we have:
W K+
log
21
Σ
V log (IT1)
W1
k=1
K
K H
log (1) dk
Σn
- V
DEVEE,, K. +
2
n. k. 0z
1
H
log (111))
(17)
1=
h=1
1
dH²
1
2dH²
21
VE
2\
dk log
8
2
log
cK
- log (IIT)
?
7
k=
Combining (16) and (17), we have:
Σ
K
V Vs <o H HyaKK log
dH²²
log
+
7K
+
log (IIII
(18)
1=1
Choosing 17 बh and combining terms, we obtain for any policy II, with probability at least 1 6:
K
V³= =0 H dKH log
11
dH²
+0 (offf
log
+ 7KH
(19)
k
We will then present the proof of Theorem based on Equation (19). Notice we condition on K being large enough so that the optimal parameters y and set below are smaller than 2 satisfying the requirements of the algorithm, while the cases of K being small is trivial.
In the case when we have access to simulator, the total regret occurred while we execute the policies K and using the properties of
in II. Set the parameters as +- dH² log K //K, Y + dH log II in Lemma 18, the total regret is bounded as:
Reg(K)= < Reg (I; + 1 max
K ΣV
VT
V
+1=0
K log 8
xEll
Also, according corollary 1, the total number of episodes run on the simulator in the order of Ö HK2).
19

---

Published in Transactions on Machine Learning Research (01/2024)
When don't have access to simulator, we have to take account of the regret occurred while we estimate the feature visitation of each policy. According to corollary 1, the additional regret is in the order of regret is bounded as:
d 4 log
5 + C1).
By our construction of policy set II in Lemma 18, the total
Reg(K)= = ( &HHo
K +
d
K *KH + dH²
K -K + V d g log ④ + (20)
+c))
log
log
8
with C
poly dd H, log 1/6, Xmai log I1 log 1/e)
Set the parameters as 3: the total regret is in the order of:
K K-2/5 9 H9/3 10// log2/5
K
8 <- K-1/5, T/5
7/5 log
/5 K
Reg K) = = ( log2/5
log 1/5
8
B Construct the Policy Visitation Estimators
In this section, we will propose the analysis of Algorithm We then prove theorem and corollary as our main results, which will provide the concentration of the estimators Φ and bound the sample complexity. These results will then be used to proof the final regret bounds in Appendix A.
First, we propose the performance guarantee of the data collecting oracle, which comes directly from theorem 9 in Wagenmaker and Jamieson (2022). Denote:
XY
opt (A) = max [| for A = A Ao
dE#
for Ag be some fixed regularizer. We consider it's smooth approximation:
XY (A) log Σ
1
e اlااا|
1
We also define 2n = (Enow [Ar,al Ar), where Ar is the set of all the distributions over all valid Markovian policies. Ωn is, then, the set of all covariance matrices realizable by distributions over policies at step h. Then we have
Theorem 2. Considering running Algorithm in Wagenmaker and Jamieson (2022) with some e > 0 and functions
(A - XY ope (A)
for Ao (T,Ki) Eg =: Ar and
(1+ ||Azllop)
log |
I ||,7111 11p = A A 11sp (1 (1+M) m/s ||A lloo) M, M, = --,1,,,1 ||
where Σ; is the matric returned by running Algorithm 7 in Wagenmaker and Jamieson (2022) with N + T,Ki, +- // (2i²), and some \ 2 0. Then with probability 1 26, this procedure will collect at most
inf Aen maxşe |1ol + poly d, H, log 1/8,
1 1 X, log b log
20
Coxp
Amin 7o
Eoxp
episodes, where
(Mini)) ) d
X
1 x
d. H, A, log 1 I,
A (A) A min
poly log
H log
7/2
1/6
20

---

Published in Transactions on Machine Learning Research (01/2024)
and will produce covariates Σ Eg such that
max || (S+x.) -1 S
6exp
@ 2
and
Amin
E {
2 max (dlog 1/6, A}
Next, we will propose the concentration analysis of our estimators and bound the total number of episodes run. Throughout this section, assuming we have run for some number of episodes K, we let (Fr) the filtration on this, with F, the filtration up to and including episode т. We also let Fr,5 denote the filtration on all episodes r' r, and on steps h' 1, h of episode Define
2nh = E 1 (n), On (6) Σ (s, Th (als)
and
/==Jonh Da,h (8) dp (s)
T T=
We have from lemma A.7 Wagenmaker and Jamieson (2022): Φn.h = -n. .... Ta,n ... TT, 1r,10 We also denote " = max ||
The following Lemma 12 comes straight from lemma B.1, lemma B.2 and lemma B.3 in Wagen- maker and Jamieson (2022) and provides us with the basic concentration properties of the estimators constructed in line 6 of Algorithm 2.
Lemma 12. Assume that we have collected some data {( oh-1.r where, for each T', 8h,7' F1-1,7 is independent of {(hh-177 ah-1,r, Sh.), ppr- Denote Φn-1,7 = Φ ($4-1,7; 0b-1,)) and A ΣK On 01-1, + +I. Fix a and let
tx. =
Σ
a (00 1 A
Or. -Ta t TT,
Fir Sa-1 Then with probability at least 1 1 5:
(u, dunh dx.N))
h-1
2H 2 log
log 2H
+ vdl
1|0mmol
8
Amin (A,)
Thus, with probability at least 1 - 5,
| @mih
Σ
h-1
21 log
2Hd
+
log 2Hd Amin (Aw)
Vdx
|i
Lemma 13. Let ob denote the event which, for all a E II, the feature visitation estimates returned by line 6 satisfy:
-
- <d h-1
1I 6
log 41 dill
Amin (Aw) || A
3 log
#=1
Then P (c S 2H
Proof. Following similar analysis in lemma B.5 in Wagenmaker and Jamicson (2022), we also have the data collected in Theorem 2 satisfy the independent requirements of Lemma 12. The result follows by setting X 1/d in Lemma 12.
21

---

Published in Transactions on Machine Learning Research (01/2024)
Lemma 14. Let eexp denote the event which: The total number of episodes run in line is at most
d inf AED, maxpeo, [()lA(A)) + poly d, H, log 1/6, ,o, log [MT, log 1/e)
2/3
A
episodes. The covariates returned by line 4, An, satisfy:
4H 8
max DE
10 A
S
Amin (AA) 2 log
(21)
d33"
Then P (= " ch-1 n (n Fexp)
S
8 2H
Proof. By Lemma 15, on the event e n ( we can bound 0 - S s//Vd. Remember
that we condition on K being large enough so that have E 1/2, Also, we can lower bound 110 Z 1 l/vd from lemma A.6 in Wagenmaker and Jamieson (2022). Thus,
| 2 11óm,all2 - -|0mm,mm - teati 2 21/Vde//Vd2 2/V2d
So the choice of 7a zva parameters.
1 is valid. The result then follows by applying Theorem 2 with our chosen
]
Lemma 15. On the event t n (op)) for all a E II,
0r,ht 2n,t2 Sc/Vd.
Proof. On sxmp: we can bound:
4H'd
Amin (A,) 2 log
A.
dvd3
AHdy dlog mlm
so that:
| 0x,n+1
h-1
4H2
log 4
| Il,
S d
3
log
5
Amin (An))
M=1
4II
e
< d
4v log
4tdd 4H d dlog
1=1
à
< dH
HH Vd e/va.
Lemma 16. Define Eexp n and Eest nn Then IP [Eest O E 2 6, and conditioning Eest n Cerp, for all h = 1,2, H -1 and E II, we have:
1 @n Se/Vd.
Proof. Obviously,
H-1
Eoxp U c = U ((p)))) ( ((u(()))))) )
h=l
22

---

Published in Transactions on Machine Learning Research (01/2024)
--1
H
h (1 (( (U (FEx))
U (c
h=1
h=1
(Eopp)
n (EEst A-1 n (M u U (s
h=1
h=1
Using Lemma 13 and Lemma 14, we can bound
H
PP (est
&
(Eexp) "n
"nesst -h-l n (n séxp) + (P((ees) '))
h=1
2 8
2H
hm
<8.
And the inequality follows by Lemma 15.
Thcorem 3. (Full version of Lemma 2) With probability least 1 8, Algorithm will run at most
C inf Aen, max 1 log 5
H2
+poly d, log 1 log [II log 1/c
2
Amia
episodes, and will output policy visitation eslimators + {om,n: h= 1,2, ... ,H, x E ET} with bias bounded
as:
[ 6n,h Se/vd.
Proof. According to Lemma 16, we can condition on the event Eest n Cemps thus we obtain the accuracy desired. According Lemma 14, we have total episodes be bounded
d inf. max | + poly (d, H, 1/5, Xmin
log [T] 1/c)
2/3
d inf maxgee, [()))(()))
H'd
1²2 log
+ poly
d, H,H log 1/6,
log [11, log 1/e)
X
Conditioning on Eest O Eeap: we have for all π E II, (d. @nn
<c/vd, thus we can upper bound:
@n.h 1|2
inf max || [ = inf max AEs, DE
AER, well
A(A)
2 10 21 A(A) 1 200 - Ozi |xxA)-)
< inf max Ac well
2ea
< inf max AEfa wEll
2 1 21 (AA)) + ddmin (A (A))
4e2
< inf max AgS sell
11 +
dDiin
Thus, the total number of episodes is bounded as:
CH2
H Aen, max 10
log
HddlT
poly (d, H. log 1/8, Xm
1
log [TT, log 1/c) (22)
23

---

Published in Transactions on Machine Learning Research (01/2024)
From lemma B.10 in Wagenmaker and Jamicson (2022), we can bound:
inf max ll I S d. AE sell
Thus we have:
Corollary 1. The sample complezity in Algorithm 2 is bounded by:
(
H 2
Hd
o
log
+
+c1)
8
log [1], where Ci = poly (d.H. Hog log 1/5, log
log 1/0)
C Construct the Policy Set
In this section we provide the proof for the policy set II we constructed. The construction techniques follows directly from Appendix A.3 in Wagenmaker and Jamieson (2022) and will prove such construction also works in MDP with adversarial rewards. Our main result is stated in Lemma 18.
Lemma 17. In the adversarial MDP setting, where the loss function changes in each round, the best policy of the MDP M(S,A, H, (Pr) {(x]g=) in rounds 1 to K from the set of all slalionary policies, is the optimal policy of the MDP with fixed loss function being the average. Denote the average MDP M(S, A. H, (Ph) Ph E), with the same transition kernel and the average loss Ł= 1 That is:
K > Ex.
π argmin
VE
then n' argmin V
Where V is the value function associated with the new MDP M.
Proof. Let Ta (($1, a1), (22, ... (sH, aH)) be the trajectory generated by following policy through the MDP. Denote the occupancy mcasure 11, (Sh; an) as the probability of visiting state-action pair (8h, ax)
under trajectory Tx, and पt¹ = (HT, -.,
For any stationary policy n, we have:
V
Σ Σ h=
(5 (s), ax).
(s..ax)SS.xA.
Since the two MDP share the same transition kernel, the occupancy measure generated by the same policy stays unchanged. So we have:
K
Σ
(i an Ae an)
h= (ss (n),, x
H
Σ
p (sh: and
Σ len (sn, an)
(8s an S xd
H1
Σ
Σ
(i(sn, Ki(sn,
A=1
(ES,,)) XA
KV
24

---

Published in Transactions on Machine Learning Research (01/2024)
So x² satisfies:
K V
argmin V
π argmin
Lemma 18. Choose e to be an arbilrury constant, then we can construct a policy set for any lineur adversarial MDP M(S,A, H, (Pn) {(+))==), such that there exists policy II, when compored with the global optimol policy, the regret of which is bounded by 1:
Σ k
V/ 51.
So that:
K
R)g(K)= =
Σ
V
VE
max Tell
VE
Vs Σ k=1
+ Reg (K; & Reg (K; II) 1.
==1
and the size of bounded as:
m S (1+3222 log (1 +1+ 16Hdk))
where d is the dimension of the feature map.
Lemma A.14 in Wagenmaker and Jamieson (2022) that for any linear MDP M(S, A, H, H, with fixed reward function é, we can construct a policy set, that there exists a policy π E II, which approximates the best policy of M with bias f va s E'. And the size of the policy set is bounded as:
Proof. According
an
522 log (1+ 16Hd/e)) (e')²
<
1 +
(23)
Notice this construction is based entirely on the set of state action features & (s, a) and require no information on the loss or reward function. the adversarial case, we choose M to be the average MDP denoted in Lemma 17, and we obtain the regret bound of a in all the K episodes:
K Σ
V
V K (vT - v=)= K (v- - -vx) Ke'
(24)
The proof is finished by taking c' = 11/K in Equation (23).
25


Reviews:
[{"review_id": "by3Y4L9q8R", "reviewer": "Reviewer_7xbT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors propose to run the exponential weight algorithm over the cover set of policies, using the loss estimator for each policy combined with an optimistic term. As an initialization step, the algorithm also computes the G-optimal design for each policy. This result can be seen as a non-trivial adaptation of the Exp4.P algorithm to a linear MDP setting. In general, I think the idea of this work allows avoiding the complications appearing in the previous works, as with this approach problematic terms appearing because of using the performance-difference lemma do not appear here. I also think that idea of computing the exploration distribution via G-optimal design fits nicely here. However, I don’t see a potential to make this approach practical, as it has exponential running time at each time step, and also computing the G-optimal design is computationally costly, and the computational difficulty is never discussed in the paper.\n\nComments:\n•\tfrom Definition 1, it is not clear whether the loss is bounded by one or by \\sqrt{d}\n•\tNo discussion on how to compute G-optimal design\n•\tLemma 1 - never discussed that exponentially large \\Pi makes the runtime at each step of the algorithm exponential in parameters\n•\t the reference for Lemma 4 doesn’t looks correct, to which result in Freedman (1975) are you referring to? This was presumably taken from [1], also it is unclear why the formulation needs to state this concentration inequality for a fixed V.\n•\tIt is not clear if the inequality in Lemma 5 should hold with some probability.\n•\tProof of Lemma 6, last line, bound on loss is missing\n\n\n[1] High-Probability Regret Bounds for Bandit Online Linear Optimization, Bartlett et. al.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers online learning in adversarial MDP where the loss functions can change arbitrarily over K episodes and the state space can be arbitrarily large and provides new algorithms for which improved guarantees on the regret upper bounds are provided.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Could you highlight your technical novelty?\n\nCould you address the questions above?", "broader_impact_concerns": "This is a theoretical work, so no concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "rtot5DzUA6", "reviewer": "Reviewer_mr3v", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper makes another small step towards minimax optimality for this setting. Given how challenging the problem is, this is understandable, and there are some elements of originality in this work that could help the community to progress even further.\n\nThe paper is mostly well written and clear. The theoretical results and their proofs are clear and, as far as I can tell, correct. \nThe only part that is rather obscure is how the algorithm by Wagenmaker and Jamieson works and is used in the overall algorithm.\nThe comparison with related works is complete and detailed.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper is about the very challenging problem of regret minimization of (finite-horizon) linear MDPs with adversarial rewards. Minimax optimality is still open in this setting, but this paper provides significant improvements over previous upper bounds. \nThe proposed algorithm runs an EXP3-like policy with an optimistic value function and a forced-exploration component based on G-optimal design, but the most peculiar part is how the value-function parameters are estimated: using expected (under the state-action visitation probabilities induced by the policy) features, in turn estimated using a known reward-free learning algorithm by Wagenmaker and Jamieson (2022). Depending on whether this \"representation learning\" phase can be done \"for free\" (without suffering any regret) or fully online, the overall algorithm suffers $\\tilde{O}(\\sqrt{K})$ and $\\tilde{O}(K^{4/5})$, respectively. The latter result improves over the previously best known upper bound of $\\tilde{O}(K^{6/7})$. The $\\tilde{O}(\\sqrt{K})$ result was achieved before with a generative model, but never with such a weak notion of simulator. Moreover, in both cases, the exploratory assumption is significantly weaker than in previous works and there is no explicit dependence on the minimum eigenvalue of the feature covariance matrix.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The only critical request is to expand the discussion of the algorithm by Wagenmaker and Jamieson (2022): how it works and how it is employed by your algorithm.\n\nThe following are either suggestions to strengthen the work or questions that could be answered as additional discussions or remarks in the paper:\n\n1. I suggest to explain better what kind of simulator you assume to have access to in Section 1. This becomes clear later in the paper, but it is a bit puzzling in Section 1.\n2. Calling $\\pi*$ \"the optimal policy\" is slightly misleading in this adversarial setting, where you compare with the best policy in hindsight. Also, how would the result change if we considered an arbitrary comparator policy?\n3. You consider the same feature map $\\phi$ for all the stages $h\\in[H]$. How would the results change if you considered a possibly different feature map $\\phi_h$ for each $h$?\n4. Computing the exact G-optimal design seems computationally very hard. What happens if you use one of the common approximation methods? How would this approximation error propagate to the regret bounds?\n5. If I'm not mistaken, from a purely technical point of view, the \"forced exploration\" (optimal design) component is only needed to ensure $\\eta|\\hat{V}|\\le 1$ in the exponential-weights proof. I would highlight this in case someone wants to try to remove this component.\n6. Is the optimistic bonus only needed to obtain high-probability bounds?\n7. In some places, it would be better to remind that we are working under the linear MDP assumption: in the statement of Lemma 1, in the last equation of page 7\n\nOther (minor) remarks:\n- In definition 1, $\\mu_h$ should be *signed* measures\n- The notation $\\mathbb{E}_\\pi$ should be defined explicitly \n- The structure of linear MDPs guarantees that the value functions of *all* policies can be represented by a linear function\n- Algorithm 2 would be more clear by separating the two loops over $h$, and by displaying the estimated transition operator in place of its expression in line 6\n- In the appendices, Theorem 2 is incorrectly referred to as \"Theorem B\" in several places.", "broader_impact_concerns": "Not necessary.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "72ZUuuSlko", "reviewer": "Reviewer_G6Ur", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. This paper exhibits exceptional clarity in its presentation and is remarkably comprehensible.\n\n2. The proposed novel algorithm represents a significant advancement over the original approach, achieving an impressive $O(K^{4/5})$ regret guarantee without the need for a simulator.\n\n3. The work conducted here performs a direct analysis of linear features, transforming them into a single linear optimization problem. This particular aspect of the research could prove to be of substantial independent interest.\n\nWeaknesses:\n\n1. Regarding the exploratory assumption, it raises questions that the regret does not appear to depend on the minimum eigenvalue $\\lambda$. As demonstrated in Table 1, all previous works under similar assumptions demonstrate a clear dependency on $\\lambda$. Providing an explanation in the table or theorem would enhance the paper's clarity.\n\n2. The regret guarantee associated with a simulator necessitates an impractical number of simulator calls, namely $O(K^2)$, to achieve an $O(\\sqrt{K})$ regret guarantee. This requirement is significantly greater than the number of episodes, K, and appears to be unrealistic.\n\n3. According to Lemma 1, the policy class's size is exponential, rendering Algorithm 1 and Algorithm 2 highly inefficient.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This study is centered around the Adversarial Markov Decision Process (MDP) with a linear Q-value function. By leveraging an exploratory assumption, the author introduces innovative algorithms that lead to a substantial enhancement of the previous regret guarantee, reducing it from $O(K^{6/7})$ to $O(K^{4/5})$. Furthermore, if a simulator for the transition is available, the regret guarantee can be pushed even further, achieving an astonishing $O(\\sqrt{K})$ improvement.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weakness.", "broader_impact_concerns": "I do not find any potential negative societal impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers agree that the paper should be accepted. The work is technically solid, and the authors have made some progress on a difficult problem, although optimality remains open. The authors’ algorithmic approach is novel, allowing them to make technical advances over previous approaches. However, there is a concern that this approach may not be along the path towards an efficient algorithm.
Decision: Accept (poster)