Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Design
Authors: Andrew Wagenmaker
Kevin Jamieson
Venue: NeurIPS 2022 Accept (2022)
Keywords: reinforcement learning
reinforcement learning theory
sequential decision making
function approximation
PAC
instance-dependence

Abstract: While much progress has been made in understanding the minimax sample complexity of reinforcement learning (RL)---the complexity of learning on the ``worst-case'' instance---such measures of complexity often do not capture the true difficulty of learning. In practice, on an ``easy'' instance, we might hope to achieve a complexity far better than that achievable on the worst-case instance. In this work we seek to understand this ``instance-dependent'' complexity of learning in the setting of RL with linear function approximation. We propose an algorithm, PEDEL, which achieves a fine-grained instance-dependent measure of complexity, the first of its kind in the RL with function approximation setting, thereby capturing the difficulty of learning on each particular problem instance. Through an explicit example, we show that PEDEL yields provable gains over low-regret, minimax-optimal algorithms and that such algorithms are unable to hit the instance-optimal rate. Our approach relies on a novel online experiment design-based procedure which focuses the exploration budget on the ``directions'' most relevant to learning a near-optimal policy, and may be of independent interest.

Instance-Dependent Opar- Policy Identification in Linear MDPs via Online Experiment Design
Andrew Wagenmaker's & Kevin Jamieson'
Paul G. Allen School of Computer Science & Engineering University of Washington Seattle, WA 98195
Abstract
While much progress has been made in understanding the minimax sample com- plexity of reinforcement learning (RL)-the complexity of learning the "worst- case" instance-Sun such measures of complexity often do not capture the true difficulty of learning. In practice, plexity far better than that achievable on the worst-case instance. In this work we complexity of learning near-optimal
"easy" instance, might hope achieve com-
seek to understand the "instance-dependeni policies (PAC RL) in the setting of RL with linear function approximation. We propose an algorithm, PEDEL, which achieves fine-grained instance-dependent measure of complexity, the first of its kind in the RL with function approximation setting, thereby capturing the difficulty of learning on each particular problem instance. Through an explicit example, we show that PEDEL yields provable gains over low-regret, minimax-on optimal algorithms and that such algorithms are unable to hit the instance-optimal rate. Our approach relies on novel online experiment design-band based procedure which focuses the exploration budget on the "directions" most relevant to learning near-optimal policy, and may be of independent interest.
Introduction
In the PAC (Probably Approximately Correct) reinforcement learning (RL) setting, an agent tasked with exploring unknown environment in order to learn policy which maximizes the amount of reward collected. In general, we are interested in learning such a policy using as few interactions with the environment (as small sample complexity) possible. We might hope that the number of samples needed would scale with the difficulty of identifying a ncar-optimal policy in our particular environment. For example, in "hard" environment, would expect that more samples might be required, while in an "easy" environment, fewer samples may be needed.
The RL community has tended to focus on developing algorithms which have optr-optimal worst- case sample complexit--sappee complexities that are only guaranteed be optimal on "hard" in- stances. Such algorithms typically have complexities which scale, for example, as O (pool((d, H))+?), for d the dimensionality of the environment, H the horizon, and c the desired level of optimality. While we may be able to show this complexity is optimal on hard instance, it is unable to distinguish between "hard" and "easy" problems. The scaling is identical for two environments as long as the dimensionality and horizon of each are the of the problem-and we therefore have no guarantee that our algorithm is solving the problem with complexity scaling the actual difficulty. Indeed, as recent work has shown (Wagenmaker et al.,
consideration is given to the actual difficulty
"j ajwagenecs. washington. edu j jami amiesondca. washington.ede
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

2021b), this is not simply an analysis issue: worst-case optimal algorithms can be very suboptimal on "easy" iistaaces.
Towards developing algorithms which overcome this, we might instead consider the instance- dependent difficulty- the hardness of solving particular problem instance and hope to obtain sample complexity scaling with this instance-dependee "easy" problems using only small number of samples, but still obtain the worst-case optimal rate on "hard" problems. While progress has been made in understanding the instance-dependent complexity of learning in RI, the results are largely limited environments with finite number of states and actions. In practice, real-world RI. problems often involve large (even infinite) state-spaces and, in order solve such problems, we must generalize across states. To handle such settings, the RI. community has turned to function approximation- in large state-space environments. However, while worst-case optimal results have been shown, little is understood on the instance-dependent complexity of learning in these settings.
difficulty, thereby guaranteeing that we solve
methods, which allow for provable learning
In this work we aim to bridge this gap. We consider, in particular, the linear MDP setting, and develop an algorithm which provably learns a near-optimal policy with sample complexity scaling as the difficulty of each individual instance. Furthermore, by comparing to instance- deetedeed measure of complexity, we show that low-regret algorithms are provably suboptimal for PAC RL in function approximation settings. Our algorithm relies a novel online experiment design- based procedure adapting classical techniques from linear experiment design to settings where navigation is required to measure particular covariate which may be of independent interest.
1.1 Contributions
Our contributions are as follows:
We propose an algorithm, PEDEL., which learns e-optimal policy with instance-dependent sample complexity scaling as (up to H factors):
11 112
H
A
(d + log )
inf max Keep TEll (Vr
for Φuth h the "average feature vector" of policy æT, Aexpp the expected covariance of the policy Texp, and Vü Vi" the "policy gap". We show that PEDEL also has worst-case optimal dimension- dependence- its sample complexity never exceeds (d HJ /2) but that on "easy" instances it achieves complexity much smaller than the worst-case optimal rate.
It is well-known that low-regret algorithms achieve the worst-case optimal rate for PAC RL. We construct an explicit example, however, where the instance-dependen complexity of Pedel improves on the complexity of any low-regret algorithm by a factor of the dimensionality, providing the first evidence that low-regret algorithms are provably suboptimal on "easy" instances for PAC RI in function approximation settings.
We develop general experiment design- design-based approach to exploration in MDPs, which allows us to focus our exploration the directions most relevant to learning near-optimal policies. Our approach is based on the key observation that, while solving experiment design in an MDP would require knowledge of the MDP dynamics, we can approximately solve one without knowledge of the dynamics by rumning regret minimization algorithm carefully chosen reward function, inducing the correct exploration.
2 Related Work
The sample complexity of RL has been studied for decades (Kearns & Singh, 1998; Brafman & Tennenholtz, 2002; Kakade, 2003). The two primary problems considered are the regret minimization problem (where the goal is to obtain large online reward) and the PAC policy identification problem (where the goal is to find near-optimal policy using as few samples as possible), which is the focus of this work. the tabular RL setting, the question of obtaining worst-case optimal algorithms is nearly closed (Dann& & Brunskill, 2015; Dann et al., 2019; Ménard et al., 2020; Zhang et al., 2020). As such, in this section we focus primarily on results the RL. with function approximation literature, as well results instance-dependent RL.
2

---

Sample-Efficient RL with Linear Function Approximation. To generalize beyond MDPs with a finite number of states and acions, the RL community has considered function approximation. replacing the tabular model with more powerful settings that allow for generalization across states. Such settings have been considered in classical works (Baird, 1995; Bradtke & Barto, 1996; Sutton et al., 1999; Melo & Ribeiro, 2007), yet these works do not provide polynomial sample complexities. More recently, there has been intense interest in obtaining polynomial complexities for general function classes (Jiang et al., 2017: Du et al., 2021; Jin et al., 2021; Foster et al., 2021), and, in particular, linear function classes ( (Yang & Wang, 2019; Jin et al., 2020; Wang et al., 2019; Du et al., 2019; Zanette et al., 2020a.b; Ayoub et al., 2020; Jia et al., 2020; Weisz et al., 2021; Zhou et al., 2020, 2021; Zhang et al., 2021: Wang et al., 2021).
In the linear MDP setting, the state-of-the-art in PAC RL is the work of Wagenmaker et al. (2022), which proposes computationally efficient algorithm achieving a complexity of (dd /e²) for the more general reward-free RL problem, and shows a matching lower bound of (2 11 / for the PAC RL problem. While this result obtains tight cemeenion--dpendeee complexity. Other works of note in this category are (Jin et al., 2020; Zanette al., 2020b; Zhou et al., 2020), which establish regret guarantees in the setting of linear MDPs and the related setting of linear mixture MDPs. Jin et al. (2020) and Zanette et al. (2020b) obtain regret guarantees of O dV (( and O( respectively, though the approach of Zanette et al. (2020b) is computationally inefficient. Via an online-to-batoe conversion (Jin et al., 2018), these algorithms achieve PAC complexities of Od O(d and D((11+/))) In the setting of linear mixture MDPs, Zhou et al. (2020) show a regret bound of O H3K and matching lower bound, yielding the first provably tight and computationally efficient algorithms for RL with function approximation.
it is still worst-case,
and offers no insight on the mustance-dependee
Pustance-Dependeee RL. Much of the recent work on instance-dependent RL has focused on the tabular setting. Ok et al. (2018) provide an algorithm which achieves asymptotically optimal instance-dependent regret, yet it is computationally inefficient. Simchowitz & Jamieson (2019) show that standard optimistic algorithms achieve regret bounded as O(E,,a [x(aa ). for (s.s
log
the value-function gap, a result later refined by (Xu et al., 2021; Dann et al., 2021). Obtaining eestance-dependens guarantees for policy identification has proved more difficult, yet a variety of results do exist (Zanette et al., 2019; Jonsson et al., 2020; Marjani & Proutiere, 2020; Marjani et al., 2021). In the tabular setting, the most comparable work to ours is that of Wagemmaker et al. (2021b), which propose a refined instance-dependens measure of complexity, the gap-visitation complexity, and show that it is possible to learn e-optimal policy with complexity scaling as the gap-ving visitation complexity. While the gap-visitation complexity is shown to be tight in certain settings, no general lower-bounds exist. Towards obtaining sharp guarantees, Tirinzoni et al. (2022) show that in the simpler setting of deterministic MDPs, a quantity similar in spirit to the gap-visitation complexity is tight, providing matching upper and lower bounds.
In the setting of RL with function approximation. to our knowledge, only two existing works obtain guarantees that would be considered iustance-dependenn" Wagenmaker et al. (2021a) show a "first-order" regret bound of Ol HV, K), where V/ is the value of the optimal policy on the particular MDP under consideration. He et al. (2020) show that standard optimistic algorithms achieve regret guarantees of O Hogg mixture MDPs, respectively, for Amin the minimum value-function gap. While both these works do obtain restndee-eeeeneent results, the instance- dependdeee is rather coarse, depending on only a single parameter (V/* or Amin) our goal will instead be to obtain more refined instance-dependee guarantees.
log K and O d2 log" K in the settings of linear MDPs and linear Amii
Amju.
Experiment Design in Sequential Environments. Experiment design a well-developed subfield of statistics, and full survey is beyond the scope of this work (see Pukelsheim (2006) for an overview). We highlight several works on experiment design in sequential environments that are particularly relevant. First, the work of Fiez et al. (2019) achieves the instance instance-optimal rate for best-arm identification in linear bandits and relies on an adaptive experiment design- based. The approach of Fiez et al. (2019), as well as the related work of Soare et al. (2014), provides inspiration for our algorithm-in some sense PEDEL can be seen as a generalization of the RAGE algorithm to problems with horizon greater than 1. Concurrent to our work, the R algorithm was extended to the setting of contextual bandits Li al. (2022), achieving the instance-optimal rate. Second, the work of Wagenmaker et al. (2021c) provides experiment design- based algorithm in the setting
3

---

of linear dynamical systems, and show that it hits the optimal cestance-dependere rate for learning in such systems. While their results are somewhat more general. they specialize to the problem of identifying near-optimal controller for the LQQ problem-thereby solving the PAC RL problem optimally the special case of quadratic losses and linear dynamical systems. It is not clear, however, if their approach generalizes beyond linear dynamical systems. Finally, while the current work was in preparation, Mutny et al. (2022) proposed an approach to solving experiment design problems in MDPs. To our knowledge, this is the only existing work that directly considers the problem of experiment design in MDPs. However, they make the simplifying assumption that the transition dynamics are known, which essentially reduces their problem to computational one in contrast, our approach handles the much more difficult setting of unknown dynamics, and shows that efficient experiment design is possible even in this more difficult setting. We remark as well that our online experiment design approach is somewhat related to several existing algorithms (Hazan et al., 2019; Zahavy et al., 2021).
3 Preliminaries
We let |ج Th Ap, ||. llpp denote the matrix operator norm (matrix 2-norm), and || ||r denote the Frobenius norm. O() hides absolute constants and log factors of the arguments. S denotes inequality up to constants. E, and Fx, denote the expectation and probability measure induced by playing some policy π in our MDP. We let Øh.7 == Φ(5p,r ah,r) denote the feature vector encountered at step h of episode T (and similarly define rh,7).
Markov Decision Processes. In this work, study episodic, finite-horizon, time inhomogeneous Markov Decision Processes (MDPs), denoted by tuple, M = (S H, { We let S denote the state space, A the action space, H the horizon, (ir the transition kernel, and / the reward distribution, where Pr(-|s, a) E As denotes the distribution over the next state when playing action in state at step h, and vn (s, a) E [o. denotes the corresponding distribution over reward. We overload notation and let (s. a) also refer to the expected reward. We assume that every episode starts in state 81, and that [ and { are initially unknown.
Let {Tr, 1/4 denote a policy mapping states to distributions over actions, Th : S AA- When æ is deterministic, we let (s) denote the action policy π takes at (s, h). An episode begins at state 81. The agent takes action a T (s)), transitions to state $2 (- a1), and receives reward ri (81, a1) ~ (i(81, 41). In 82, the agent chooses new action d2 ~ (*2))). and the process repeats. After H steps, the episode terminates, and the agent restarts 81.
In general, we are interested in learning policies that collect a large amount of reward. We can quantify the performance of policy in terms of the value function. In particular, the Q- value function, 27 (s, a), denotes the expected reward that will be obtained if we are in state at step h, play action and then play policy x for the remainder of the episode. Formally, ()) == E, E Th (Sw, )ss)
8, a₁ = a] The value function is similarly defined as (s) = E. |Σ = Tw (Sw, am))s,, |sa. = s]. For deterministic policies, Vo5 (s) = (s, We denote the optimal Q-value function by (7, a) sup, Q7 (s. a) and the optimal value function by (s) = sup, V (s). where the suprema is taken over all policies, both deterministic and stochastic. We define the value of policy Vo V/" > expected reward policy " achieves over an entire episode- and say policy æ is optimal V/" = Vg. For some set of policies II (which may not contain an optimal policy), we let Vo (II) = sup Vo"
PAC Reinforcement Learning. In PAC RL, the goal is to identify some policy र using as few episodes as possible, such that, with probability at least 5,
5,
VÚ V <e
We say that such a policy is e-optimal, and an algorithm with such a guarantee on every environment and reward function is (e, PPCC. We will also refer to this problem as "policy identification".
3.1 Linear MDPs
In this work, we are interested in the setting where the state space could be infinite, and the learner must generalize across states. In particular, we consider the linear MDP model defined as follows.

---

Definition 3.1 (Linear MDPs (Jin et al.. 2020)). We say that an MDP is d-dimensional linear MDP, there exists some (known) feature map Φ(s, a) : S x A R H (unknown) signed vector-valued measures μa E Rdd over S, and H (unknown) reward vectors 02. E Rd, such that:
Pa((|s, a) (d(s, a), (*),,) E[va(s, a)] = (Ø(s, a), 0n)
We will assume [| a)ll2 - for all s, a; and for all h, [|]|]|(() ll J.ES (s) & vd and |00112 5 vd.
Linear MDPs encompass, for example, tabular MDPs, but can also model more complex settings, such as feature spaces corresponding to the simplex (Jin et al., 2020), or the linear bandit problem. Critically, linear MDPs allow for infinite state-spaces, well as generalization across states rather than learning the behavior in particular states, we can learn in the d-dimensional ambient space. Note that the standard definition of linear MDPs, for example given in Jin et al. (2020), assumes the rewards are deterministic, while we assume the rewards are random but that their means are linear. We still assume, however, that the random rewards, ra(s, a). are contained in [0, almost surely.
For given policy т, we define the featureevisitaaion at step the expected feature vector policy encounters at step h, as Φ A == E, [e(),, an)]- Note that this is direct generalization of state-visitations in tabular RL-if our MDP is in fact tabular, [ = [=[s - 8, On = a], so the feature visitation vector corresponds directly to the state visitations. Note also that we can write the value of policy as VØ" Σ (0=,h, On)- Denote the average feature vector induced by π in a particular state 8 as (s) = Eawny(-le) (0(8 (1))), a)). We also define Az, = E, (o(n. an (i(()((s))) sn. on) "1 the expected covariance of policy π at step h, Amin, = sup, Amin (Ar.)) the largest achievable minimum cigenvalue at step h, and Xmiin = min, min, We will make the following assumption.
Assumption (Full Rank Covariates). In our MDP, Xmin >
We remark that Assumption 1 is analogous to other explorability assumptions found in the RL with function approximation literature (Zanette al., 2020c; Hao al., 2021; Agarwal et al., 2021).
To reduce uncertainty in directions of interest, we will be interested optimizing over the set of all realizable covariance matrices on our particular MDP. To this end, define Ω2 := {B. [Ar,A] E }2)} for I the set of all valid distributions over Markovian policies (both deterministic and stochastic). We can think of 22, then, the set of covariance matrices realizable by distributions over policies at step h.
Near-Optimal Policy Identification in Linear MDPs
We are now ready to state our algorithm, PEDEL.
PEDEL Description. PEDEL is policy-elimmnnation-syyy algorithm. It takes as input some set of policies, II, and proceeds in epochs, maintaining a set of active policies, IIg, such that all π e II, are guaranteed satisfy VT 2 Vo² 4eg, for é, 2- After running for [log 21 epochs, it returns any of the remaining active policies, which will be guaranteed to have value at least Vo (IT) -c
In order to ensure II, only contains 4c--optimal policies, sufficient exploration must be performed at every epoch to refine the estimate of each policy's 's value. While works such as Wagenmaker et al. (2022) have demonstrated how to efficiently traverse a linear MDP and collect the necessary observations, existing exploration procedures are unable to obtain the mnstacc-ddepnnde we desire. To overcome this, PEDEI. relies on novel online experiment design procedure to ensure exploration is focused only on the directions necessary to evaluate the current set of active policies.
complexity
In particular, one can show that, we have collected some covariates Ax,e, the uncertainty in our estimate of the value of policy at step h scales as || ll 1, for Ti the estimated feature- visitation for policy π at epoch f. To reduce our uncertainty at each round, we would therefore like to collect covariates such that ( IlA, S <e. Collecting covariates which satisfy this using the minimum number of episodes of exploration possible involves solving the experiment design:
inf max - A=1- En, TELT;
(4.1)
NNoe that KA.e random and is the number of episodes Algorithm 2 runs for.
5

---

Algorithm Policy Learning via Experiment Design in Linear MDPs (PEDEL)
1: input: tolerance e, confidence 6, policy set II
2: lo - [log2 da/2
H II, + II, Φ1 f Ba-n((le)(((ss e
3: for = lo. to + 1..... [log 1 do
4:
c - 2-22,, 8g +- 64H log
5: for 2....... H do
Solve (4.1) 1) by running Algorithm 2, collect data' ((@n,r, Ph,r, 1h+1,-) Ka.t such that:
6:
max 1
5 for An. - Σ Ikne Ph Ph, &h + 1/dd1 hit
welli
7: for E 1I do
1/ Estimate feature-visitations for active policies Kie - (9h+1,) Am. Ri,
8: 3hh f
9:
0 A E==1 Thr
// Estimate reward vectors
Remove provably suboptimal policies from active policy set
11++1 1I VØ sup
VØ - -cee for Vo = ==> C O
s'ell,
11: if |4+1| then return ı E I1++1
12: return any E II2+1
Note that this design has the form of an XY-experiment design (Soare et al., 2014). Solving (4.1) will produce covariance Aexp which reduces uncertainty in relevant feature directions. However, solve this design we require knowledge of which covariance matrices are realizable on our particular MDP. In general we do know the MDP's dynamics, and therefore do not have access to this knowledge. To overcome this and solve (4.1), in Section 5 we provide an algorithm, Algorithm 2, that is able to solve (4.1) in an online manner without knowledge of the MDP dynamics by running low-regret algorithm on carefully chosen reward function.
Estimating Feature- Visitations. We remark briefly on the estimation of the feature-visitaioon on Line 8. we assume that { Ka.t if is fixed and that all randomness is due to $4+1,7, then it is easy to see that, using the structure present in linear MDPs given in Definition 3.1,
E EE Kine ( And = EKa
Ka. (S (s)ddn (pnr) A
=s)n)+1())ddn
By Definition 3.1, we have Φr,4+1 (f (s) (s) )or,h. Comparing these, we see that our estimator of &r,,+1 on Line is (conditioned on { f ka.e) unbiased, assuming Φ 2a,
4.1 Main Results
We have the following result on the performance of PEDEL.
Theorem 1. Consider running PEDEL with some set of Markovian policies II on any linear MDP satisfying Definition
3.1 and Assumption 1. Then with probability at least 1 5, PEDEL outputs policy &t E II such that V 2 2V² c, and runs for at most
| 112 _|=-
(log III log ) +
C
Σ inf
h=1 Aeap En, mVx VO" AT Alm. c72
episodes, with Cy log 1 poly log log ?), C₁ = poly(d, H, x-_ log } log ? log [I]),
A 11 min = Vit max (V) Vūr, and St the set of covariance matrices realizable on our MDP.
The proof of Theorem given in Appendix Theorem quantifies, in a precise instance- dependent way, the complexity of identifying policy Ω with value at most factor of from the

---

value of the optimal policy in II. At a high level, the complexity measure can be thought of as quantifying the difficulty of exploring the MDP so as to eliminate suboptimal policies. || A quantifies the difficulty of collecting data necessary to eliminate policy и (in particular, Φn,h is the direction we need to explore to learn about the performance policy n, and A quantifies how easily we can reach directions the MDP to do this), while Vo (IT) - Vo quantifies how suboptimal policy π is, and therefore how many samples are needed to distinguish it from the optimal policy in the class. Thus, rather than scaling only with factors such as d and e, our complexity scales with instance-dependent quantities-the covariance matrices we can obtain and the feature vectors we expect to observe on our particular MDP, and the policy gaps on our MDP. Our complexity measure has close resemblance to the complexity measure for best-arm identification in linear bandits found in Fiez et al. (2019), but generalizes it to problems with long horizon where navigation is required. Theorem 1 holds for an arbitrary set of policies, yet. in general, we are interested in learning policy which has value within factor of e of the value of the optimal policy on the MDP, V Such a guarantee is immediately attainable by applying Theorem with a policy set II such that su Vi N V c. The following result shows that is possible to construct such a set of policies, and therefore learn a globally near-opiine cear-optimal policy.
Corollary 1. There exists set of policies II, such that log [II S Ö(dH² log 1/c) and. for any linear MDP satisfying Defimition 3.1, sup+eu, VO- 2 Vo- e. If we run PEDEL with II t II then with probability at least 1 - 5, it returns a policy πे such that Vi² 2 Vă - 2c, and runs for at most
H
CoH+.
Σ
inf max sell. max (Vo co,c
(dH² + log 3) + Ci
Aexp EQn, Eln
1=1
episodes, for Co = poly log(d, H)
Note that the policy set constructed in Corollary 1, II., is guaranteed to contain an c-optimal policy for any linear MDP. Thus, this result states that without any prior knowledge of our MDP, PEDEL can be applied to find an coppimall policy. While Theorem and Corollary quantify the instance-dependen complexity of learning, it is natural to ask what the worst-case complexity of PEDEL is. The following result provides such bound.
Corollary 2. For any linear MDP satisfying Definition 3.1, inf EQ,, maX I Azd. S d,
so the sample complexity of Algorithm when run with <- 11, is no larger than
dH ddH + log 1/8) + C.
Corollary 2 shows that PEDEL has worst-case optimal dimension dependence, matching the lower bound of 20d given in Wagenmaker et al. (2022), up H and log factors?.
Remark 4.1 (Performance on Linear Contextual Bandits). Corollary 1 applies directly to linear contextual bandits by setting Hl 1.. To our knowledge, this is the first instance-dependent result on PAC policy identification in linear contextual bandits. Furthermore, Corollary 2 shows that we also obtain a worst-case complexity of ( (22) on linear contextual bandits, which is the optimal rate (Wagenmaker et al., 2022).
4.2 Low-Regret A Algorithms Suboptimal for PAC RI. in Large State-Spaces
We next show that there are problems on which the instance-dependent complexity of PEDEL improves on the worst-case lower bound shown in Wagenmaker et al. (2022), thereby demonstrating that we do indeed obtain favorable complexities on "easy" instances.
Proposition 2. For any d > 2, there exists a d-dimensional linear MDP with H = 2 such that with probability 5, PEDEL. identifies an c-optimal policy on this MDP after running for only Ö 1/8 + (oly (d., log 1 3: log !)) episodes.
The complexity given in Proposition 2 is factor of df better than the worst-case lower bound of aid (e2. While this shows that PEDEL yields a significant improvement over existing worst-case
We remark that the focus of this work is on mnstance-dependenee and dimension -eeenddeee,,eeeeeeeee not in optimizing H factors, and we leave improving our H dependence for future work.
We describe the exact mapping linear contextual bandits in Appendix B.3.
7

---

lower bounds on favorable instances, it is natural to ask whether the same complexity is attainable with existing algorithms, perhaps by applying tighter analysis. Towards answering this, we will consider a class of low-regret algorithms and an online-to-batee learning protocol.
Definition 4.1 (Low-Regret Algorithm). We say that an algorithm is a low-regret algorithm its expected regret is bounded as, for all K:
B[Rx] Ex=E
EIV. - vo s SCKKK +C2
for some constants C₁, and a E (0,
Protocol 4.1 (Online-to-Batch Learning). The online-to-batch protocol proceeds as follows:
1. The learner plays a low-regret algorithm satisfying Definition 4.1 for K episodes.
2. The learner stops at a (possibly random) time and, using the observations has collected in any way it wishes, outputs a policy ă it believes is c-optimal.
general, by applying online-to-bal batch learning. one can convert a regret guarantee of C + CC2 to PAC complexity of ((((2)))))))))))(()))
+ Se) (Jin et al., 2018), allowing low-regret algorithms such as that of Zanette et al. (2020b) to obtain the minimax-optimal PAC complexity of O(d*H*/²)) The following result shows, however, that this protocol is unable to obtain the instance-optimal rate.
Proposition 3. On the instance of Proposition 2, for small enough any learner that is (c, 6)-PAC follows Protocol 4. with stopping time K must have [E[]] 2 52( 4lllo116)
Together, Proposition 2 and Proposition 3 show that running low-regret algorithm to learn least a factor of worse than the
near-optimal policy in a linear MDP is provably suboptimal instance-dependen rate obtained by PEDEL. While a similar observation was recently made in the setting of tabular MDPs (Wagenmaker al., 2021b), to our knowledge, this is the first such result in the RL with function approximation setting. implying that, in this setting, low-regret algorithms are insufficient for obtaining optimal PAC sample complexity. As standard optimistic algorithms are also low-regret, this result implies that all such optimistic algorithms are also suboptimal.
4.3 Tabular and Deterministic MDPs
To relate our results to existing results instance-dependent RL, we next turn to the setting of tabular MDPs, where it is assumed that S = |S| < 0o, A |A| < cc. Define:
An(s. a) (s) (s.
w (s, a) = [s = s, an = a].
(s a) denotes the funttin gap, and quantifies the suboptimality of playing action in state s at step h and then playing the optimal policy, as compared to taking the optimal action in (s, f). wof (s, a) denotes the state-action visitation distribution for policy æ, and quantifies how likely policy x is to reach (s, a) at step h. Note that (dr,,l(s.a) = wo, (s, a). We obtain the following corollary.
Corollary 3. In the setting of tabular MDPs, PEDEL outputs an c-optimal policy with probability at least 1 - 8, and has sample complexity bounded as
Σ h=1 inf max max Ha Teep TETT 8,0 wy, (s.a)
1 u (ssa)))nssaa)3)
w (f(aaa (1)2,
(SH log C:).
for C = poly (S, A, H, ming min, sup, [e) log z: log !) and II the set of all deterministic policies.
For tabular MDPs, the primary comparable result on instance-dependent policy identification is that obtained by Wagenmaker et al. (2021b), which introduces a different measure of complexity. the gap- visitation complexity, and an algorithm, MOCA, with sample complexity scaling as the gap-visitation complexity. The following result shows that the complexity PEDEL obtains on tabular MDPs and the gap- visitation complexity do not have a clear ordering.
Proposition 4. Fix any 1/2) and S > log2(1/e). Then there exist tabular MDPs Mi and M2, each with H = 2, S states, and (S) actions, such that:
On M1, the complexity bound of PEDEL given in Corollary 3 scales as poly(S, log 1/8), while the gap-visitation complexity scales as ((1/2)).
On M2, the complexity bound of PEDEL given Corollary 3 scales as 2(11ee), while the gap-visitation complexity scales as poly(S, log 1/6).
8

---

The lack of ordering between the two complexity measures arises because, on some problem instances, it is easier to learn in policy-space (as PEDEL does), while on other instances, it is easier to learn near-optimal actions on individual states directly, and then synthesize these actions into a near-optimal policy (the approach MOCA takes). This difference arises because, in the former instance, the mínimum policy gap is large (V: - V = 52(1) for every deterministic policy π # x*), while in the latter instance, the minimum policy gap is small, but all value-function gaps are large, satisfying As a) 211) for all A arg a Q7, (s, a) and all and h. Thus, on the former instance, it is much easier to learn over the space of policies, while on the latter it much easier to learn optimal actions in individual states. Resolving this discrepency with algorithm able to achieve the "best-of-bote woff-boohwweee both-worlds" is an interesting direction for future work.
Deterministic MDPs. Finally, we turn to the simplified setting of tabular, deterministic MDPs. Here, for each (s,a, a, h), there exists some s' such that (s (ss'|ss,)) a) 1. We still allow the rewards to be random, however, so the agent must still learn in order to find a near-optimal policy, Following the same notation as the recent work of Tirinzoni et al. (2022), let Igaah = { deterministic $ a, = at. where 5% and aj are the state and action policy will be in at step h (note that these quantities are well-defined quantities for deterministic policies). Also define the deterministic return gap (n a) == Vi maxxell... Vo" and let Amin == min aa.d,, (s.a)=0 An As,8, a) in the case when there exists unique optimal deterministic policy, and Amin == 0 otherwise. We obtain the following.
Corollary 4. In the setting of tabular, deterministic MDPs, PEDEL outputs an e-optimal policy with probability at least 1 1 8, and has sample complexity bounded as
H
δ H ΣΣ h=1 8,a
max An a), Amin: e}² (H + log ()) + poly (S, H, log $. log #)
Up to H and log factors and lower-order terms, the rate given in Corollary 4 matches the instance- dependent lower bound given in Tirinzoni et al. (2022)*. Thus, we conclude that, in the setting of tabular, deterministic MDPs, PEDEL is (nearly) instance-optimal. While Tirinzoni et al. (2022) also obtain instance-optimality in this setting, their algorithm and analysis are specialized to tabular, deterministic MDPs contrast, PEDEL requires no modification from its standard operation.
5 Online Experiment Design in Linear MDPs
As described in Section 4, to reduce our uncertainty and explore in a way that only targets the relevant feature directions, we must solve an XY-experimen design problem of the form:
inf max Esx 4E
(5.1)
This is not, in general. possible solve without knowledge of the MDP dynamics. In this section we describe our approach to solving 15 without knowledge of the MDP dynamics by relying on low-regret algorithm as an optimization primitive.
Approximating Frank-Ward via Regret Minimization. Given knowledge of the MDP dynamics, we could compute Ωr directly, and apply the celebrated Frank-Wole pondinnate-descent algorithm (Frank& & Wolfe, 1956) to solve 15. In this setting the Frank-War Wolfe update for (5.1) is:
T. arg minren, (V (maxşe# [
Ac+1 = (1 - 7), + , (5.2)
for step size Tt. Standard Frank- analysis shows that this update converges to near-optimal solution to 15. at polynomial rate. However, without knowledge of Qn, we are unable to solve for T, and run the Trank-Wolfe update.
Our critical observation is that the minimization over S2 in (5.2) can be approximated without knowledge of S2 by running a low-regret algorithm on a particular objective. Some calculation shows that (except on measure-zero set, assuming & is finite) V (maxxee || A _)AA-A,
-A, क. A,
for Φh = arg se |/>1] A. If = A = (.b for some n, we have
V A (maxøe* | ) r) -t tr T A, AT,,) = - E., [10) --
"The lower bound of Tirinzoni et al. (2022) depends on a slightly different (but nearly equivalent) minimum gap term, A Similar to our upper bound, the upper bound of Tirinzoni et al. (2022) scales with Amin instead of A A We offer more in-depth discussion of this point in Appendix B.3.

---

Now, if we run low-regret algorithm on the (deterministic) reward (s, a) = (Ø(s, a) AA x for sufficiently large number of episodes K, we will be guaranteed to collect reward at rate close to that of the optimal policy, which implies we will collect some data (Φ ) such that
K-1 Φ. x == ( 32 x sup, [= A, (b
(5.3)
However, this implies the covariates we have collected, ЛK. approximately minimize (5.2). In other words, running low-regret algorithm on vf. allows us to obtain covariates which approximate the Frank-Wolfe update-without knowledge of f2,, we can solve the Frank-Wolfe update by running a low-regret algorithm, and therefore solve (5.1). This motivates Algorithm 2.
Algorithm 2 Online Frank- Wolfe via Regret Minimization (informal)
input: uncertain feature directions O step h, regularization Ag
2: Ko f sufficiently large number of episodes to guarantee (5.3) holds
3: Run any policy for Ko episodes, collect data {Øh,r 1Kee set A + Ko Exe Ko Φh, Sh.
4: to..,,...,17 T- do
5: Φ arg øa |1 I 1, (s, + (0(s, (A. + Ao) 1,)2
6: Run low-regret algorithm on of for Ko episodes, collect covariates N KD.
7: Set A4+1 + (1 A) + Ko Ko for 71- E-1
8: return: covariates T AT = EE= T + A1 Kg
Theorem 5 (informal). Consider running Algorithm 2 with some Ao O. Then with properly chosen settings of Kn and T, we can guarantee that, with probability at least - 6, we will run for at most
inf Arep AmepEE. EQ,, maxØE# / Koll(Aon
N < 20
+ poly (d. H, ||A, llop. log lol 1/8)
Cexp
episodes, and return covariance RN satisfying max |1 (((((A+ I Eexp-
Note that this rate is essentially optimal, up to constants and lower-order terms. If we let wexp denote the distribution over policies which minimize (5.1), then to collect covariance AN such that max | 2 (Ax+NA,)-1 S Cexp in expectation, we would need play wexp for least
inf max |
Coxp
Ea, $E
episodes, which is the same scaling as obtained in Theorem 5.
practice, we instead run Algorithm on a smoothed version of the objective in (5.1). We provide full definition of Algorithm 2 with exact setting of I and Ko in Appendix C. Theorem 5 is itself a corollary more general result, Theorem 8, given in Appendix C, which shows our Frank- Wolfe procedure can be applied to minimize any smooth experiment-design objective-for for example, collecting covariates which optimally maximize the minimum eigenvalue, E-optimal design.
6 Conclusion
In this work, we have shown that it is possible to obtain instance- eestance-depeneet guarantees in RL with function approximation, and that our algorithm, PEDEL. yields provable gains over low-regret algorithms. As the first result of its kind in this setting, opens several directions for future work.
The computational complexity of PEdEL scales as poly(d, H, r: [[], |A], log }). In general, to ensure II contains c-optimal policy, [II must be exponential in problem parameters, rendering PEDEL computationally inefficient. Furthermore, the sample complexity of PEDEL scales with X the "hardest-to--ee to-hcch direction. While this is not uncommon in the literature, we might hope that a direction is very difficult to reach, learning in that direction should not be necessary, as we are unlikely to ever encounter it. Obtaining an algorithm with similar instance-dependence but that is computationally efficient and does not depend on X is an interesting direction for future work.
Extending our results to the setting of general function approximation is also an exciting direction. While our results rely on the linear structure the MDP, we believe the online experiment-desige. approach we propose could be generally applicable in more complex settings. As a first step, it could be interesting to extend our approach to the setting of Bilinear classes (Du al., 2021), 1), which also exhibits a certain linear structure.
10

---

Acknowledgements
The work of AW was supported by an NSF GERP Fellowship DGE-1762114 The work of KJ was funded in part by the AFRL and NSF TRIPODS 2023166.
References
Agarwal, N., Chaudhuri, S., Jain, P., Nagaraj, D., and Netrapalli, P. Online target q-learning with reverse experience replay: Efficiently finding the optimal policy for linear mdps. arXiv preprint arXiv:2110.08440, 2021.
Ayoub, A., Jia, Z., Szepesvari, C., Wang, M., and Yang, L. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning. pp. 463-474. PMLR, 2020.
Baird, L. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pp. 30-37. Elsevier, 1995.
Bradtke, S. and Barto, A. G. Linear least-squares algorithms for temporal difference learning. Machine learning, 22(1 22(1):33-57, 1996.
Brafman, R. I. and Temnenholtz, M. R-max-a general polynomial time algorithm for near-optimal reinforcement learning. Journal of Machine Learning Research, 310c)):2 2002.
Dann, C. and Brunskill, E. Sample complexity of episodic fixed-horizon reinforcement learning. arXiv preprint ar arXiv: arXiv: 1510.0890, 2015.
Dann, C., Li, L., Wei, W., and Brunskill, E. Policy certificates: Towards accountable reinforcement learning. In International Conference Machine Learning, pp. 1507-1516. PMLR, 2019.
Dann, C., Marinov, V., Mohri, M., and Zimmert, Beyond value-function gaps: Improved instance- dependent regret bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
Du, S. S., Kakade, S. M., Wang, R., and Yang. L. F. Is good representation sufficient for sample efficient reinforcement learning? arXiv preprint arXiv: 1910.03016, 2019.
Du, S. S., Kakade, S. M., Lee, J. D., Lovett, S., Mahajan, G., Sun, W., and Wang. R. Billnear classes: structural framework for provable generalization in rl. arXiv preprint arXiv:2103. 10897, 2021.
Epasto, A., Mahdian, M., Mirrokni, V., and Zampetakis, E. Optimal approximation-smoothnee tradeoffs for soft-max functions. Advances Neural Information Processing Systems, 33:2651- 2660, 2020.
Fiez, T., Jain, L., Jamieson, K. G., and Ratliff, L. Sequential experimental design for transductive linear bandits. Advances in neural information processing systems, 32, 2019.
Foster, D. J., Kakade, S. M.. Qian, and Rakhlin, A. The statistical complexity of interactive decision making, arXiv preprint arXiv:2112.13488 2021.
Frank, M. and Wolfe, P. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2):95-110, 1956.
Freedman, D. A. On tail probabilities for martingales. the Annals of Probability, pp. 100-118, 1975.
Hao, B., Lattimore, T., Szepesvári, C., and Wang. M. Online sparse reinforcement learning. In International Conference Artificial Intelligence and Statistics, pp. 316-324. PMLR, 2021.
Hazan, E., Kakade, S., Singh, K., and Van Soest, A. Provably efficient maximum entropy exploration.
In International Conference on Machine Learning, pp. 2681-2691, PMLR. 2019.
He, J., Zhou, D., and Gu, Q. Logarithmic regret for reinforcement learning with linear function approximation. arXiv preprint arXhv:2011.11566 2020.

---

Jia, Z., Yang, L., Szepesvari, C., and Wang, M. Model-basee reinforcement learning with value- targeted regression. In Learning for Dynamics and Control, pp. 666-686. PMLR, 2020.
Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. Contextual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning, pp. 7714-1713. PMLR, 2017.
Jin, C., Allen-Zhu, Z., Bubeck. S., and Jordan, M. I. q-learning provably efficient? Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 4868 -4888, 2018.
Jin, C., Yang. Z., Wang. Z., and Jordan, M. I. Provably efficient reinforcement learning with linear function approximation. In Conference Learning Theory, pp. 2137-2143. PMLR, 2020.
Jin, C., Liu, Q. and Miryoosefi, S. Bellman eluder dimension: New rich classes of problems, and sample-efficient algorithms. arXiv preprint urXiv:2102.0081/ 2021.
Jonsson, A., Kaufmann, E., Ménard, P. Domingues, O. D., Leurent, E., and Valko, M. Plan- ning in markov decision processes with gap-dependent sample complexity. arXiv preprini 2rXiv:2006.0587, 2020.
Kakade, S. M. On the sample complexity of reinforcement learning. PhD thesis, UCL (University College London), 2003.
Kaufmann, E., Cappé, O., and Garivier, A. On the complexity of best-arm identification in multi- armed bandit models. The Journal of Machine Learning Research, 17(1):1-42, 2016.
Kearns, M. and Singh, S. Finite-sample convergence rates for q-learning and indirect algorithms. Advances in neural information processing systems, 11, 1998.
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cambridge University Press, 2020.
Li, Z., Ratliff, L., Nassif, H., Jamieson, K., and Jain, L. Instance-optimal pac algorithms for contextual bandits. arXiv preprint arXiv:2207.0233 2022.
Marjani, A. A. and Proutiere, Best policy identification in discounted mdps: Problem specific sample complexity. arXiv preprint arXiv:2009, 13405, 2020.
Marjani, A. A., Garivier, A., and Proutiere, Navigating the best policy in markov decision processes. arXiv preprint arXiv:2/06.0280 2021.
McSherry, and Talwar, K. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 007), pp. 103. IEEE, 2007.
Melo, S. and Ribeiro, M. Q-learning with linear function approximation. In International Conference on Computational Learning Theory, pp. 308-322, Springer, 2007.
Ménard, P., Domingues, O. D., Jonsson, A., Kaufmann, E., Leurent, E., and Valko, M. Fast active learning for pure exploration in reinforcement learning. arXiv preprint arXiv:2007.13442 2020.
Mutny, M., Janik, T., and Krause, A. Active exploration via experiment design in markov chains. arXiv preprint ar0i 1..6./433 /4332, 2022.
Ok, J., Proutiere, A., and Tranos, D. Exploration in structured reinforcement learning. arXiv preprint 180.00075 2018
Pukelsheim, F. Optimal design of experiments. SIAM, 2006.
Simchowitz, M. and Jamicson, K. Non-asymptotic gap-dependent regret bounds for tabular mdps. arXiv preprint arXiv:1905.03888 2019.
Soare, M., Lazaric, A., and Munos, R. Best-arm identification in linear bandits. Advances Neural Information Processing Systems, 27, 2014.
12

---

Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y. Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12. 1999.
Tirinzoni, A., Al-Marjani, A., and Kaufmann, E. Near instance-optimall pac reinforcement learning for deterministic mdps. arXiv preprint Xxv:22003009251, 2022.
Vershynin, R. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint 1011::7011.3027, 2010.
Wagenmaker, A., Chen, Y., Simchowitz, M., Du, S. S., and Jamieson, K. First-order regret in reinforcement learning with linear function approximation: A robust estimation approach. arXiv preprint arXiv:2112.034522 2021a.
Wagenmaker, A., Simchowitz, M., and Jamieson, K. Beyond no regret: Instance-dependent pac reinforcement learning. arXiv preprint arXiv:2 2021b.
Wagenmaker. A., Chen, Y., Simchowitz, M., Du, S., and Jamieson, K. Reward-free no harder than reward-aware rl in linear markov decision processes. arXiv preprint arXiv:2201. //2200..1//0,, 2022.
Wagenmaker, J., Simchowitz, M., and Jamieson, K. Task-optimal exploration explorrraionoooniiiiiiinooooooo in linear dynamical systems. In International Conference on Machine Learning. pp. 10641-10652. PMLR, 2021c
Wang, Y., Wang, R., Du, S. S., and Krishnamurthy, A. Optimism in reinforcement learning with generalized linear function approximation. arXiv preprint 1xXivv:992.04 2019.
Wang, Y., Wang, R., and Kakade, M. An exponential lower bound for linearly-realizable mdps with constant suboptimality gap, arXiv preprint arXiv:2103. 2021.
Weisz, G., Amortila, P., and Szepesvári, C. Exponential lower bounds for planning in mdps with Linearl-rrealizable optimal action-value functions. In Algorithmic Learning Theory, pp. 1237-1264. PMLR, 2021.
Xu, H., Ma. T.. and Du S. S. Fine-grained gap-dependent bounds for tabular mdps via adaptive multi-step bootstrap. arXiv preprint arXiv:2102.04692, 2021.
Yang, L. and Wang. M. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pp. 6995-7004. PMLR, 2019.
Zahavy, T., O'Dooghue, B., Desjardins, G., and Singh, S. Reward is enough for convex mdps. Advances in Neural Information Processing Systems, 34:25746-25759, 2021.
Zanette, A., Kochenderfer, M. J., and Brunskill, E. Almost horizon-free kructure-awaae best policy identification with a generative model. In Advances in Neural Information Processing Systems, volume 32, Curran Associates, Inc., 2019.
Zanette, A., Brandfonbrener,
D., Brunskill, E., Pirotta, M., and Lazaric, A. Frequentist regret bounds for randomized least least-squares value iteration. In International Conference on Artificial Intelligence and Statistics, pp. 1954-1999 1964.1964. PMLR, 2020a.
Zanette, A., Lazaric, A., Kochenderfer, M., and Brunskill, E. Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pp. 10978-10989. PMLR, 2020b.
Zanette, A., Lazaric, A., Kochenderfer, M. J.. and Brunskill, E. Provably efficient reward-agnostir navigation with linear value iteration. Advances in Neural Information Processing Systems, 33: 11756-11766 2020c.
Zhang, Z., Ji, X., and Du. S. Is reinforcement learning more difficult than bandits? near-optimal algorithm escaping the curse of horizon. arXiv preprint arXiv:2009. 13503, 2020.
Zhang, Z., Yang. J., Ji, X., and Du, S. S. Variance-awand confidence set: Variance-dependee bound for linear bandits and horizon-free bound for linear mixture mdp. arXiv preprint 1277:.2 2021.
13

---

Zhou, D., Gu, Q. and Szepesvari, C. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. arXiv preprint arXiv:2012.08507, 2020.
Zhou, D., He, J., and Gu, Q. Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning, pp. 12793-12802. PMLR, 2021.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "mUH4KvKuMp3", "reviewer": "Reviewer_b4C6", "summary": "This paper studies the problem of sample complexity of RL with linear function approximation. Recent works have extensively studied this problem with a range of results for different versions and structural assumptions. However, this paper presents the first instance dependent sample complexity analysis for the linear MDP setting. The proposed algorithm is based on a policy elimination scheme which iteratively maintains a set of policies which lie within a $2^{-l}$ optimality gap from the optimal policy. The update step for this algorithm is based on a novel online experiment-design procedure which guarantees the collection of a sufficiently 'exploratory' dataset of state-action pairs at each step.\n\nIn terms of the formal results, the authors show the first instance-dependent sample complexity analysis for linear MDPs which can be shown to also yield a dimension-optimal rate in the worst case. Further, it is formally shown that there exists instances where the instance-dependent rate improves over the sample complexity of worst case optimal PAC-RL algorithms. Lastly, it is shown that the instance-dependent rate for the linear case recovers the instance-dependent rate for deterministic MDPs whereas it gives another instance-dependent rate for tabular MDP which can be provably better or worse than previous instance-dependent rates for specific instances. ", "questions": "Please see the comments about computational efficiency and $\\lambda_{\\min}^*$ above.\nIn addition, I was wondering if there is a more intuitive interpretation of the complete instance-dependent term in theorem 1 instead of just the individual terms.", "limitations": "The authors do discuss the potential improvements in the conclusion and formally show that their algorithm does not yield the best sample complexity for some tabular domains. As such, I do not have any concerns about the discussions of the limitations.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, this paper is very well written and shows important and novel results for linear MDPs. I especially like the thoroughness of this paper where multiple aspects of instance-dependence are explored:\n1. Instance-dependent analysis for linear MDPs: The algorithm is well explained and a novel method for the experiment design objective in (4.1) is also proposed and analysed. In the final rate, the authors show that the rate depends on factors which relate to hardness of exploring any direction in the feature space $\\phi$, a policy gap term for the input policy class. A final result is obtained by showing that a policy class can be constructed for linear MDPs whose size exponentially scales with $d$ to derive the instance-dependent guarantee with respect to the optimal policy.\n2. Demonstrating the utility of the instance-dependent rate: The authors show using Prop. 3 that there exists linear MDPs such that the instance dependent rate improves over the worst case rate by a factor of $d^2$. Further, it is shown that no existing PAC-optimal algorithm will get a polylog(d) rate for this problem.\n3. Discussions for tabular and deterministic MDPs: I especially like the result in Prop. 5 which shows that the sample comeplxity for their algorithm is in fact another possible instance-dependent rate for tabular domains and can improve over previously shown instance-adaptive algorithms or in some cases perform worse than them. It brings an interesting question of unifying these different instance-dependent measure of complexity, and highlights possibilities of improvement even for the linear MDP case. For deterministic MDPs, previously known rate can be recovered upto $H$ factors.\n\n**Weakness**:\nThis is a strong first result in this direction and hence has certain aspects which can possibly be improved:\n1. Computational efficiency: Since the algorithm follows a policy elimination template, for establishing a guarantee wrt optimal policy, an exponentially large policy set needs to be constructed. The experiment design objective then iterates over the expected feature vectors for each policy to eliminate sub-optimal candidates. As such, it is not clear if a computationally efficient version of the solution can be derived.\n2. Dependence on explorability parameter: The authors need to assume that there exists a policy which generates a full rank covariance matrix for the state-action features. In my understanding, this also affects the algorithm as the covariance matrices constructed in the experiment design steps are guaranteed to be non-singular using this assumption. Can the authors comment about the necessity of this assumption or potential ways to remove this?", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "BftUMMNIjw", "reviewer": "Reviewer_zzUK", "summary": "In this paper, the optimization of instance-dependent sample complexity for reinforcement learning (RL) under linear MDP is studied. The PAC policy learning setting is considered, which is to identify the best policy among all. An elimination-style algorithm with a novel exploration strategy is proposed. The key idea lies in using online Frank-Wolfe to explore the directions which reduce the sample variances most. The algorithm achieves the first instance-dependent sample complexity guarantee for linear MDP. The analysis also shows that low-regret algorithms can be sub-optimal in certain instances, showing the advantage of the proposed algorithm.", "questions": "Please feel free to point out the errors in the weaknesses that I proposed above.\n\n", "limitations": "The limitations and potential negative societal impact are properly discussed. ", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper proposes an algorithm that is the first to achieve the instance-dependent sample complexity guarantee under linear MDP. The result is original and novel.\n\n2. The exploration strategy based on online Frank-Wolfe is interesting and can be of independent interest for other bandit learning problems.\n\nWeaknesses:\n\n1. According to the algorithm, it is implicitly assumed that the policy set has finite cardinality. This assumption is not reasonable. Since there are infinite states in a linear MDP, the number of all policies should also be infinite. I think this is a major limitation of the proposed algorithm and analysis.\n\n2. Another limitation is that the instance-dependent term in Theorem 1 does not have a clear explanation. It is not easy to think out which kind of linear MDP the proposed algorithm can be advantageous. \n\n3. I also have some doubts about the exploration step. In Line 6 of Algorithm 1, the number of data to collect is set to $K_{h, l}$, which is closely related to the overall sample complexity, but there is no explanation of how this number is set. Furthermore, the sample complexity of Algorithm 2 is proposed in Theorem 6, which is of order $O(1/\\epsilon_{exp}$. But there is no definition of $\\epsilon_{exp}$ in the paper. Is $\\epsilon_{exp}=\\epsilon$? If this is true, I can't understand why the instance-dependent bound in Theorem 1 can hold, since as a step of Algorithm 1, Algorithm 2 has already required $O(1/\\epsilon_{exp})$ instances.\n\n4. I think some proofreading needs to be done to improve the notational explanations. There are some notations without defining previously or immediately after their first appearance. \n\nOverall, I think the paper proposes interesting and novel results. But the weaknesses discussed above are not ignorable for me currently.\n\n---\nafter rebuttal:\n\nI increase my score since the responses address most of my doubts. I suggest including the explanations in the paper to improve clarity.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5MRRMEP6yyS", "reviewer": "Reviewer_sWno", "summary": "This paper considers instance-dependent complexity of learning under linear MDPs. Based on a novel online experiment design in linear MDPs, the author proposes an algorithm whose sample complexity scaling with the instance-dependent complexity. This algorithm is worst-case optimal and beats any low-regret algorithm on an explicit example constructed by the author. ", "questions": "- Is the result in Theorem 1 tight with respect to the policy gap and the uncertainty? Does a general lower bound exist? Does the upper and lower bound match?\n- Can the algorithm be applied to linear mixture MDPs setting? \n", "limitations": "Lack of tightness w.r.t instance-dependence. Not tight w.r.t $H$ dependence. Computationally inefficient. The sample complexity result scales with the hardest-to-reach direction.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Interesting question. The question of obtaining worst-case optimal algorithms with linear function approximation has been well-studied recently. When it comes to instance-dependent RL, most of the recent work focuses on the tabular setting. Obtaining computationally efficient algorithms with tight instance-dependent sample complexity under linear MDPs is still an open question in RL.\n- Great novelty. The author uses an online experiment design-based procedure to reduce the uncertainty of their algorithm.\n- Enough comparison with the previous work. In Section 4.3, the author reduces their result to tabular and deterministic MDPs and carefully compares their results with the existing results.\n- Well-written and easy to follow. Clear algorithms, definitions, assumptions and theorems.\n\nWeaknesses:\n- Lack of tightness. The paper does not show if the algorithm obtains tight instance-dependence.\n- Computationally inefficient algorithm. \n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept