Misspecified  $Q$-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error
Authors: Ally Yalei Du
Lin Yang
Ruosong Wang
Venue: ICLR 2025 Poster (2025)
Keywords: misspecification error
reinforcement learning theory
sample complexity
sparsity
Primary area: learning theory

Abstract: The recent work by Dong and Yang (2023) showed for misspecified sparse linear bandits, one can obtain an $O(\epsilon)$-optimal policy using a polynomial number of samples when the sparsity is a constant, where $\epsilon$ is the misspecification error. This result is in sharp contrast to misspecified linear bandits without sparsity, which require an exponential number of samples to get the same guarantee. In order to study whether the analog result is possible in the reinforcement learning setting, we consider the following problem: assuming the optimal $Q$-function is a $d$-dimensional linear function with sparsity $k$ and misspecification error $\epsilon$, whether we can obtain an $O(\epsilon)$-optimal policy using number of samples polynomially in the feature dimension $d$. We first demonstrate why the standard approach based on Bellman backup or the existing optimistic value function elimination approach such as OLIVE (Jiang et al., 2017) achieves suboptimal guarantees for this problem. We then design a novel elimination-based algorithm to show one can obtain an 
$O(H\epsilon)$-optimal policy with sample complexity polynomially in the feature dimension $d$ and planning horizon $H$. Lastly, we complement our upper bound with an $\tilde \Omega(H\epsilon)$ suboptimality lower bound, giving a complete picture of this problem.

Published as a conference paper at ICLR 2025
MISSPECIFIED Q-LEARNING WITH SPARSE LINEAR FUNCTION APPROXIMATION: TIGHT BOUNDS ON AP- PROXIMATION ERROR
Ally Yalci Du
Lin F. Yang
Carnegie Mellon University ayduêandzer cmu. edu
University of California, Los Angeles 1 linyang@ee ucla. edu
cmu.
Ruosong Wang
CFCS and School of Computer Science Peking University
ruosongwanggepku.cc edu. en
ABSTRACT
The recent work by Dong & Yang (023) showed for misspecified sparse lin- ear bandits, one can obtain an ( (pttimall policy using polynomial number of samples when the sparsity is a constant, where é is the misspecification er- ror. This result is in sharp contrast to misspecified linear bandits without sparsity, exponential number of samples to get the same guarantee. In
which require order to study whether the analog result is possible in the reinforcement learning setting, we consider the following problem: assuming the optimal Q-function is a d-dimensional linear function with sparsity and misspecification error c, whether we can obtain O (cp-omai policy using number of samples polynomially in the feature dimension We first demonstrate why the standard approach based on Bellman backup the existing optimistic hypothesis class elimination approach such as OLIVE Diang et al.) (0177) achieves suboptimal guarantees for this prob- lem. We then design novel elimination- based algorithm to show one can obtain an O (He)- policy with sample complexity polynomially in the feature di- mension and planning horizon H. Lastly, we complement our upper bound with Q (He) suboptimality lower bound, giving a complete picture this problem.
INTRODUCTION
Bandit and reinforcement learning (RL) problems in real-world applications, such autonomous driving (Kiran et al.) 2021). healthcare (Esteva et al. 2019). recommendation systems (Bouneffouf al.) 2012). and advertising (Schwartz et al. 2017). face challenges due to the vast state-action space. To tackle this, function approximation frameworks, such as using linear functions or neural networks, have been introduced to approximate the value functions or policies. However, real-world complexities often mean that function approximation is agnostic; the function class captures only an approximate version of the optimal value function, and the misspecification error remains unknown. A fundamental problem is understanding the impact of agnostic misspecification errors in RL.
Prior works show even minor misspecifications can lead exponential (in dimension) sample com- plexity in the linear bandit settings (Du al. 2020 Lattimore al. 2020) if the goal is to learn policy within the misspecification error. That is, finding an Oce)-optimal action necessitates at least ((exp(d)) queries (or samples) the environment, where is the misspecification error. Recently, Dong & Yang (2023) demonstrated that by leveraging the sparsity structure of ground-truth parame- ters, one overcome the exponential sample barrier in the linear bandit setting. They showed that with sparsity k in the ground-truth parameters, it is possible to learn an O(e)-optimal action with
only O ((d/e)*) samples. In particular, when & is a constant, their algorithm achieves a polynomial sample complexity guarantee.

---

Published as a conference paper at ICLR 2025
A natural question is whether can obtain similar sample complexity guarantee in the RL setting. This question motivates us to consider a more general question:
Given a that the Q" function is d-dimensional linear function with sparsity and misspecification error e, can we learn an O (e) -optimal policy using poly(d, (d, 1/c) samples, when k is constant !
turns out that by studying this question, we obtain a series of surprising results which cannot be explained by existing RI. theories.
1.1 OUR CONTRIBUTIONS
In this paper, we propose an RL algorithm that can handle linear function approximation with spar- sity structures and misspecification errors. We also show that the suboptimality achieved by our algorithm is near-optimal, by proving information-theoreti hardness results. Here we give a more detailed description of our technical contributions.
Our Assumption. Throughout this paper, we assume the RL algorithm has access to feature map where, for each state-action pair (s, a), we have the feature ((s, a) with [Ø(s, a)ll S 1. We make the following assumption, which states that there exists sequence of parameters 0" (o....., 10- where each 0% E @ is k-sparse, that approximates the optimal Q-function up an error of c. Assumption 1. There exists 0 (0%..... -.a....,00. (0ū....,HH--) -1 where each 0% Sd-1 is k-sparse, such that Kő(s, a), 0%) - Q" (s, a)) S
for all h E [H). all states in level h, and all actions in the action space.
When H 1, Assumption is equivalent the bandit setting in Dong & Yang (2023). Note that we have different optimal parameter 0, for each level / E [M]-
We can approximate 0" using an e-net of the sphere S and the set of all k-sized subset of [d]. Therefore, when k is a constant, we may assume that each 0% lies in a set with size polynomial in d. Then, natural idea is to enumerate all possible policies induced by the parameters in that finite set, and choose the one with the highest cumulative reward. However, although the number of parameter candidates in each individual level has polynomial size, the total number of induced policies would be exponential in H, and the sample complexity of such approach would also be exponential in H.
The Level-by-level Approach. Note that when the horizon length H consideration is equivalent to bandit problem, which can be solved by previous approaches (Dong Yang, 2023). For the RL setting, natural idea to first apply the bandit algorithm Dong & Yang (2023) the last level, and then apply the same bandit algorithm on the second last level based on previous results and Bellman- -bakkps, and so on. However, we note that to employ such an approach, the bandit algorithm needs to provide a "for-all" guarantee, i... finding parameter that approximates the rewards of all arms, instead of just finding a near-optimal arm. On the other hand, existing bandit algorithms will amplify the approximation error of the input parameters by constant factor, in order to provide a for-all guarantee. Concretely, existing bandit algorithms can only find a parameter so that 0 approximates the rewards of all arms by an error of 2e. As we have H levels in the RL setting, the final error would be exponential in H, and therefore, such a level-by-level approach would result in suboptimality that is exponential in H.
the problem under
One may ask if we can further improve existing bandit algorithms, so that we can find a parameter 0 that approximates the rewards of all arms by an error of plus a statistical error that can be made arbitrarily small, instead of 2c. The following theorem shows that this is ceffommationthhooreiiio impossible unless one pays a sample complexity proportional the size of the action space.
Theorem 1.1. Under Assumption with d = k = 1, any bandit algorithm that returns estimate such that (F(a) r(a)l < 2e for all arms a with probability at least 0.95 requires at least 0.9n samples, where is the total number of arms.
Therefore, amplifying the approximation error by a factor of is not an artifact of existing bandit algorithms. Instead, it is anformation-theoreticllll theoretically impossible.
Strictly speaking, as will be demonstrated in this paper, the best one do is O (e -pptimalll policy where H the horizon length.
2

---

Published as a conference paper at ICLR 2025
Geometric error amplification is common issue in the design of RL algorithm with linear function
approximation (Zanette et al. [219 Weisz et al.] 2021 Wang et al. [2020a] 2021a). It is interesting (and also surprising) that such issue arises even when the function class has sparsity structures.
Optimistic Value Function Elimination. Another approach for the design of RL algorithm is based on optimistic value function elimination. Such approach was proposed by Jiang al. (2017) and
was then generalized to broader settings (Sun et al. 2019: Du et al.) 2021 Jin et al. 2021] Chen
al. 2022b). At each iteration of the algorithm, we pick the value functions in the hypothesis class with maximized value. We then use the induced policy to collect a dataset, based on which we
eliminate a bunch of value functions from the hypothesis class and proceed to the next iteration.
When applied to our setting, existing algorithms and analysis achieve a suboptimality that depends on the size of the parameter class, which could be prohibitively large. Here, we use the result Jiag et al. (2017) as an example. The suboptimality of their algorithm is H /Mc, where M is Bellman rank of the problem. For our setting, we can show that there exists an MDP instance and a feature map that satisfies [ssumption[] whose induced Bellman rank is large.
Proposition 1.2. There exists an MDP instance M = AS, H, P.r) with |A| 2, H = log d, [S] = d 1, with d-dimensional feature map & satisfying Assumption 7 with k 1, such that its Bellman rank is d.
Given Proposition 1.2 one naively applies the algorithm in Jiang et al. (017)). the suboptimality would be O de) in our setting, which necessitates new algorithm and analysis. In Section we design new RL algorithm whose performance is summarized in the following theorem.
Theorem 1.3. Under Assumption 0 with probability at least - 6, Algorithm 7 returns a policy
with suboptimality at most (ACstat + nen + 2 H by taking Okdd H3 -IndH (n(dH/(nett) ck Statt) samples.
Here Cstat is the statistical error. Compared to the existing approaches, Theorem 1.3 achieves a much stronger suboptimality guarantee. Later, we will also show that such a guarantee is npar-optimal.
Although based on the same idea of optimistic value function elimination, our proposed algorithm differs significantly from existing approaches (Jiang al. 2017, (Sun et al. 2019 Du et al. 2021 Jin et al. [022]] Chen et al., (0225)) to exploit the sparsity structure. While existing approaches based on optimistic value function climination try to find a sequence of parameters that maximize the value of the initial states, our new algorithm selects a parameter that maximizes the empirical roll-in distribution at all levels. Also, existing algorithms eliminate large set of parameters in each iteration, while we only eliminate the parameters selected during the current iteration in our algorithm.
These two modifications are crucial for obtaining a smaller suboptimality guarantee, smaller sample complexity, and shorter running time. existing algorithms, parameters at different levels are interdependent, i.e. the choice of parameter at level h affects the choice of parameter at level h + 1. Our new algorithm simplifies this by maintaining a parameter set for each level, so each level operates independently. Further, error at any level h, since otherwise we would have found another parameter with larger induced value function at level h + to make the error small. Consequently, since eliminate at least one parameter at each iteration, we obtain fewer iterations and enhanced sample complexity.
can falsify and climinate any parameter showing large Bellman
The Hardness Result. One may wonder if the suboptimality guarantee can be further improved. In Section 3 we show that the suboptimality guarantee by Theorem 1.3 is near-optimal.
We first consider weaker setting where the algorithm is not allowed to take samples, and the function class contains a single sequence of functions. Lee. we are given a function Q S x A R. such that [Q(s, a) (s a)l S for all as,a) S A.
We show that for this weaker setting, simply choosing the greedy policy with respect to Q, which achieves suboptimality guarantee of (He,, is actually optimal. To prove this, we construct hard instance based on binary tree. Roughly speaking, the optimal action for each level is chosen uniformly random from two actions 0₁ and ag. At all levels, the reward is e if the optimal action is chosen, and os 0 otherwise. For this instance, there exists a fixed Q that provides a good approxima- tion the optimal Q-function, regardless of the choice of the optimal actions. Therefore, Q reveals
3

---

Published as a conference paper at ICLR 2025
no information about the optimal actions, and the suboptimality of the returned policy would be least (e) The formal construction and analysis and construction will be given in Section 3.1
When the algorithm is allowed to take samples, we show that in order to achieve a suboptimality guarantee of H/Ce, any algorithm requires exp(O((C)) samples, even when Assumption
[ is sat-
isfied with d = k 1. Therefore, for RL algorithms with polynomial sample complexity, the suboptimality guarantee of Theorem 1.3 is tight up to log factors.
To prove the above claim, still consider the setting where d = k = 1, i..., a good approximation to the Q-function is given to the algorithm. We also use a more complicated binary tree instance, where we divide all the H levels into H/C blocks, each containing C levels. For each block, only one state-action pair at the last level has reward of and all other state-action pairs in the block has reward of Therefore, the value of the optimal policy would be H/C e since there are H/C blocks in total. We further show that there is a fixed function Q. which provides a good approximation to the optimal Q-function universally for all instances under consideration.
Since Q reveals no information about the state-action pair with reward for all blocks, for RL algorithm to return a policy with a non-zero value, it must search for a state-action pair with non- zero reward in brute force manner, which inevitably incurs sample complexity of cxp()I(C)) since each block contains C' levels and exp()((C) state-action pairs at the last level. The formal construction and analysis and construction will be given in Section 3.2
1.2 RELATED WORK
A series of studies have delved into MDPs that can be represented by linear functions of predeter- mined feature mappings. achieving sample complexity or regret that depends on the feature map- ping's dimension. This includes linear MDPs, studied in Jin et al. (2020); Wang et al. (011)); J: Neu & BirkeBurke| (2020), where both transition probabilities and rewards are linear functions of feature mappings on state-action pairs. Zanette et al. (2020a b) examines MDPs with low inherent mellman error, indicating value functions that are almost linear with respect to these mappings. Another focus is on linear mixture MDPs (Modi et al. 2020 Jia et al. 2020 Ayoub et al. 2020 Zhou et al.) 202T Cai et al.) 2020), characterized by transition probabilities that combine several basis kernels linearly. While these studies often assume known feature vectors, Agarwal et al. (2020) investigates a more challenging scenario where both features and parameters of the linear model are unknown.
The literature has also witnessed a substantial surge of research in understanding how function general approximations can be applied efficiently in the reinforcement learning setting (Osband &
Van Roy]
2014; Sun et al.) 2019 Ayoub et al.] 2020; Wang et al.] 2020b Foster et al.
|021] Chen
al.
2022b Zhong al. [022 Foster et al. [023]] Wagenmaker & Foster 2023
Zhou & Gu
2022
Jiang et al. 2017 Wang et al. 2020b Du et 2021 et al. 2021 Kong et al. 202 Dann
ctt al.
2021| Zhong al. 2022 Liu al. 2023 Agarwal et al.] (2023) ). To obtain good sample, error,
or regret bounds, these approaches typically impose benign structures on values, models, or policies, along with benign misspecification. Amongst these works, Diang et al. (2017) is particularly related to our work their iisiinattionbbseed algorithm, OLIVE, can be directly applied to our setting. However, as mentioned in Section I.I worse than our result.
the suboptimality guarantee of their algorithm is significantly
In another line of works, Du et al. (2020): Dong & Yang (202)): Lattimore et al. (2000) specifically focuses understanding misspecification in bandit and RL scenarios. Du et al. 22000) illustrated that to find an Occ)-mll policy in reinforcement learning with e-misspecified linear features, an agent must sample an exponential (in d) number of trajectories, applicable to both value-based and model- learning. Relaxing this goal, Lattimore et al. (2020) indicated that poly(d/c) sam- ples could suffice to secure an ((e/d)-optimal policy in simulator model setting of RL, though achieving policy with an error better than (ce/d) would still require an exponential sample size. Recently, Dong & Yang (2023) introduced a solution, showing that incorporating structural infor- mation like sparsity in the bandit instance could address this issue, making it feasible to attain O(e) with ((d/e)*) sample complexity, which is acceptable when the sparsity k is small. Another re- cent independent work (Amortila et al.) 2024) also obtains a suboptimality guarantee of O(He). However, their result depends on a coverability assumption and uses a different technique called disagreement- regression (DBR), which is distinct from our assumption and techniques.
4

---

Published as a conference paper at ICLR 2025
2 PRELIMINARIES
Throughout the paper, for a given positive integer n, we use [n] to denote the set {0. 1,.,,,.... n- 1}.
In addition, f(n) = (gg(n) denotes that there exists constant > O such that [f(n)] S clg(n))- f(n) = ([g(()) denotes that there exists a constant с > such that [n() 2 clg(n).. For a set S, (SS) represents the set of all probability distributions defined over S.
2.1 REINFORCEMENT LEARNING
Let M (S, H, Pr be a Markov Decision Process (MDP) where the state space, the action space, H E Σ,, is the planning horizon, P : S A + A(S) is the transition kernel which takes a state-action pair as input and returns a distribution over states, r S A + A((O, 1J) the reward distribution. We assume Σne(h) Nh [0, 1] almost surely. For simplicity, throughout this paper, we assume the initial state Sn is deterministic. To streamline our analysis, for each h E [H], we use S₁, S S to denote the set of states at level h, and assume S₁, do not intersect with each other.
A chooses an action for each state, and may induce trajectory denoted by (So. Oo, Tu..... ......,.HH.. $1 -,,-,,7 -1), where 8h+1 P(sh, ax),, aд = m(s)). and rh ~ r(sh, a%) for all [H]. Given policy π and h E [H], for a state-action pair (8, a) Sn. x A, the Q-function and value function is defined as
A policy x : S
H-1
H-1
("(saa)= =
Σ r(sns, aw 18a = 8, a, (8) = E LW
Σ LK=h
r(sw, an |8h
We use V" to denote the value of the policy n, i.e., V== =V==V"(so)) (so)) We use X" to denote the optimal policy. For simplicity, for state 8 E S, we define (*))) = V" (s), and for a state-action pair (s, a) E S x A. we define Q" a) = Q" (s) The suboptimality difference between the value of and that of n², i.e. V* V*.
policy æ is defined as the
For any sequence of k-sparse parameter 0 (Oo....,Ore 0n-1), 1). we define we to be the greedy strategy based on 0. In other words, for each h E [H] for state E Sh, (s()) arg max (06 ()) 0n)- For each h E [H] a parameter 0% and a state E Sn, we also write Ve, (s) = max (0(s, a). 0n)
We will prove lower bounds for deterministic systems, i... MDPs with deterministic transition P and deterministic reward r. In this setting, P' and can be regarded as functions rather than distribu- tions. Since deterministic systems can be considered as special case for general stochastic MDPs, our lower bounds still hold for general MDPs.
Interacting with an MDP. An RL algorithm takes the feature function & and sparsity as the input, and interacts with the underlying MDP by taking samples in the form of trajectory. To be more specific, at each round, the RI algorithm decides a policy ı and receives a trajectory (so, 0o, To, .., -H-1, Qg-1, -111) as feedback. Here one trajectory corresponds to H samples. We define the total number of samples required by an RL algorithm as its sample complexity. Our goal is to design an algorithm that returns near-optimal policy while minimizing its sample complexity.
The Bandits Setting. this paper, we also consider the bandit setting, which equivalent to an MDP with H = 1. Let A be the action space, and r A + ([00, 1]) be the reward distribution. At round t, the algorithm chooses an action a₂ E AA and receives a reward ra ~ r(at). In this case, Assumption asserts that there exists 6", such that (o(a), 0*) R[[(a)]] S for all a E A.
3 HARDNESS RESULTS
we prove that the suboptimality of any RL algorithm is (?HH)) if the algorithm is not allowed to take samples. This serves warmup for the more complicated construction in Section 3.2, where we show that for any C' satisfying < 2C < H, any RL algorithm requires exp( samples in order to achieve suboptimality of (H
We prove our hardness results. In Section 3.1
3.1 WARMUP: HARDNESS RESULT FOR RL WITHOUT SAMPLES
We prove that the suboptimality of any RL algorithm without sample is ((He). Specifically, we consider setting where the feature is 1-dimensional and equal to the optimal Q-value with an
5

---

Published as a conference paper at ICLR 2025
error of e. This provides a simplified scenario where approximate optimal Q-function is readily available to the algorithm. Theorem 3.1 suggests that even in such a simplified context, the best achievable suboptimality is O(He).
Theorem 3.1. Given a MDP instance satisfying Assumption 7 the suboptimality of the policy re- turned by any RL algorithm is S(HH)) with a probability of 0.99 if the algorithm is not allowed to take samples. This holds even when the dimension and sparsity satisfies d = k 1 and the underlying MDP is a deterministic system.
The formal proof of Theorem 3.1 is given in Section A.1 of the Supplementary Material. Below give the construction of the hard instance (illustration of the hard instance is given in Appendix[A.I)) together with an overview of the hardness proof.
Our hardness result is based on a binary tree instance. There are H levels states, and level h [H] contains 2 distinct states. Thus have 2" states in total. We use su,..., 82 -2 to denote all the states, where Su is the unique state at level O, and $1, 82 are the states at level 1, etc. Equivalently, S {82+ (82h-11....) -2)+1-2)- The action space A contains two actions, ai and a2- For each h E [H - IJ, a state E Sn, we have P(*:, a1) = *2i+1 and P(8;, a2) = 82:42. For each h [H], there exists an action af E [di,a2]: such that x² (s) a for all s E Sp. Based on qu aj, ................................ -1 for state s E Sh. we define the reward function as r(s, a) = if a aj and r(s, a) = 0 otherwise. The corresponding Q-function is Q (*,88a = (H h)e if a - oj and (s, = (H h 1)e otherwise.
Now we define the 1 1-dimensional feature function &. For each h E [H] for all (s, a) E Sp x A. o(s, a) H h 1)e. Clearly, by taking 0r = 1, Assumption Tis satisfied for our Φ. This finishes the construction of our hard instance.
Since the RL algorithm is not allowed to take samples, the only information that the algo- rithm receives is the feature function Φ. However, & is always the same no matter how we set an: .ef.....,77711 which means the RL algorithm can only output fixed policy. On the other hand, if 0z is drawn uniformly random from {a,, .2), for any fixed policy æ. its expected suboptimality will be He/2, which proves Theorem 3.1 Our formal proof in Section A. of the Supplementary Material is based on Yao's minimax principle in order to cope with randomized algorithms.
3.2 HARDNESS RESULT FOR RL WITH SAMPLES
In this section, we show that for any 1 < 2C < H, any RI. algorithm requires exp(S((C)) samples in order to achieve a suboptimality of (2HH/C.)).
Theorem 3.2. Given a RI. problemm instance satisfying Assumption 7 with misspecificatioon < 1/H and let C E TR. such that < 2C < H. Any algorithm that returns a policy with suboptimality less than (2C) with probability at least 0.9 needs least 0.1 C.....2 2c samples. This holds even when the dimension and sparsity satisfies d = k = 1 and the underlying MDP is a deterministic system.
In the remaining part of this section, we give an overview of the proof of Theorem 3.2 define the MULTI-INDEX -IDEIIIDDE--URRYYYYY problem.
We first
Definition 1. (MULTI-INDEX QUERY) In the m- problem, we have a sequence of indices
i, -) [m] In each round, the algorithm guesses a pair (j.i) i) [m] x [n] and queries whether = The goal is to output (j, i7) for any j E [m], using as few queries as possible.
Definition 2. (8-correct algorithm) For 8 E (0. 1), we say randomized algorithm A is d-correct for m-INDQ, for any i Jemm with probability at least 1- 8, outputs (ū,25) for some j.
We first prove a query complexity lower bound for solving m-INDD,,- Lemma 3.3. Any 0.1-correct algorithm that solves m-INDQ, requires at least 0.9n queries.
Our proof is based on Yao's minimax principle Yao 1977). See Section A.2 for the full proof.
Now we give the construction of our hard instance, together with the high-level intuition of our hardness proof. For simplicity, here we assume C' is an integer that divides H.
The Hard Instance Again, our hardness result is based on a binary tree instance. The state space, action space, and the transition kernel of our hard instance are exactly the same as the instance in

---

Published as a conference paper at ICLR 2025
8.
5. (sy, D)
Sy002-2
F21e1
P' (e.. 1)
8-20
$
(5p
A- +
P' P'G,.
$26-2429
8- -1
Spi-1
Figure I: Illustration of the hard instance for Theorem 3.2
Section 3.11 Moreover, similar the instance in Section 3.1 for each [H], there exists an action a% E {e1, h such that T (s) = oj for all s E S,.
To define the reward function r, we first define an operator P", which can be seen as applying the transition kernel for multiple steps by following the optimal policy. For some q E [H/C], a state E Skc, and an integer e [C], define P'(s, c) = s if
P(P* (s, 1), a acc+ (* C 1) for some s' E Syc where q E [H/C] and a a= ==0G++C-1 For all other (s, E S x A, we define r(s,a) O. Accordingly, for each cq [H/C]x[C]
and P* (s.
otherwise. The reward function as).a) is then defined to be e if s
E SyC+es and a E A, we have (s, (H/C-q)c if = (s', c) for some s' E Sec and a = Go+te. For all other (s, E S x A, we have (*(saa)= = (H/C q 1)c. This also implies that the value of the optimal policy is H/C.6.
We define the 1-dimensional feature function @ such that, for each (g. c) E [H/C] x [C], E S00+t and a E A. Φ(s, a) = (H/C q)e. Clearly, Assumption is satisfied when taking 0* = 1. This finishes the construction of our hard instance. An illustration is given in Figure
The Lower Bound. Now we show that for our hard instance, if there is an RL algorithm that returns a policy with suboptimality less than H/C e, then there is an algorithm that solves m-INDQ, with n = = and m = H /C. Therefore, the correctness of Theorem is implied by Lemma 3.3
We first note that there exists a bijection between {al, o2) C and [2 We use g [2 + 02) 02)"
to denote such a bijection. Given an instance of m-INDQ,, with n 2c and m = H/C. for each q E [H] we set S9cc:,944........ ..ieti................. -/+1)C--) = g(()),, where (17, 27, 22....,, / are the target indices in the instance of m-INDQ,,. Each time the RI algorithm samples a trajectory (so, do, To. ... $ -H-1, ). we make H/C sequential queries (0, io), (1, (1,
(H/C-
1, 1,(1/C-1) 1 to m-IND where for each E [H/C], ig is the unique integer in [2 with g(1,) =
(anc, CgC+1........................... (ggga(((gcc))a ((++1)C-1). For each E [H). we have Tn if (q 1)C 11 and 4 2 for some E [H/C). Otherwise, we have r)
Suppose there is an RL algorithm that returns policy æ with suboptimality less than H/C and since the value of the optimal policy H/C- c, we must have rh. c for some E [H] where (so, 4g, ... - --- -1) 1) is the trajectory obtained by following the policy æ. This
implies the existence of q E [H/C] with g(t²)) = (agc, UgC+1, (g)+))c-)) Therefore, if there
an RI. algorithm that returns a policy with suboptimality less than H/C e for our hard instance, then there is an algorithm for solving m-INDQ, with n 2 and m H/C.
Remark 1. Our construction is significantly different from Du et al. (2020). Specifically, we split binary tree with H levels into H blocks. For each block, we show that any algorithm must incur a sample complexity 2 in order to find a policy with suboptimality less than c. In order to show that the overall suboptimality of the RL algorithm is H/C e, we develop reduction from an intermediate problem called MULTI-INDEX QUERY to RL, which different from the one used in
Du et al. 22220.
7

---

Published as a conference paper at ICLR 2025
4 MAIN ALGORITHM
In this section, we present our main algorithm that achieves the guarantee in Theorem 1.3
Algorithm Elimination Algorithm for Finding the Optimal Hypotheses
1: Input: feature map é, sparsity k; approximation error e, statístical enror estats Enets failure rate
2: For each h [4], initialize PA P% {0 : 8M e N M k, [d], where A the maximal ent /2sepprraee subset the Euclidean sphere S*
3: Calculate m = 16k [n[[In -6.
Stat
4: for iteration / 0, 2.... do
5: Choose 8 = arg max Vo(su).
6: for h 1, 2. H. do Define a policy off where Tf{ Te, (6) if E Sn. with N/' < h, and arbitrary otherwise.
7:
Collect m trajectories following TH as a dataset
Dj. = {(o)) ab ro...., 6/ - T HH1H)))emm
8: Choose f arg max Eieim) Vo(s),,, where st are from dataset D/.-
9: end for
10: Collect m trajectories following a policy Tge as a dataset D'H {(s) ab, ................................ sh. TH 1)mmm
11: For each h E [H], calculate using dataset Di,:
1 Σ i=1
(10(5), (1), 0/) - r/ - Vor (sh+t))) i E [H 1] 1 E (10(5)-1:00) -- 01) HH-1) if = H -
& =
12:
if ε) < 26 + 2Enet + 36stat for each E H - 1]. and èt S 6 enct + 6stat then
Terminate and output iTr..
14: else
Update Pı, Pa\(6)) for all h E [H-1] satisfying 2t +2neet t 36sttt or h H satisfying E >e + Enet + Estat-
16: end if
17:
end for
Overview. Here give overview of the design of Algorithm 1 We remark that, by Assump- tion [ each horizon h has a different optimal f). Therefore, a brute-force algorithm would have sample complexity with exponential dependency on H, while our algorithm has polynomial dependency on H.
First, approximate all candidate parameter 0 with finite set by creating maximal /net/2 separated subset of the euclidean sphere g denoted by A and a set all k-sized subset of [d]. Then, for each h [W]. we maintain a of parameter candidates Pa. Initially, PA, is set to be all parameters approximated by V and k-sized subset of [d], i.e. Ph = (0 0M E g [M| = k. M S [d]} where fM the k-dimension sub-vector of with indices corresponding M. The set Ph then finite for all h E [#]: PP S (1 + 4/Enet)* (+) Dong & Yang 2023).
During the execution of Algorithm 1 for all [4], we eliminate parameter candidates 0 from Pk. we are certain that 0 * 07, where 0r (0; or.... Ph and is closest to the 0* that satisfies Assumption
0;-z) is sequence of parameters that is in i.e. 07 arg minlggoo | 0|). Therefore, ---1) if 0n P, for all [H]. In the t-th iteration, we choose a parameter 0 (0%, .f................... 0 01))) so that 0% maximizes B (s%)) and
Algorithm [ we only consider 0 (0., 0
0f E Pr, for all E [H). We then collect trajectories form dataset Dr, by following the
8

---

Published as a conference paper at ICLR 2025
policy induced by 0r. Based on Dir, we calculate the empirical Bellman error E for each h E [H], which is the empirical estimate of the average Bellman error defined as follows.
Definition 3 (Average Bellman enror). For sequence of parameters 6 (0% 08 .............................. -1 the
average Bellman error of is defined E [[((((sh: an); 0%) -r(sh: on) Vih., (sh- 1)] when
h E [H 1 1] and - = B[( aH-1), n- - r(sH-1, -,,,,, -)) for level H - 1. Here, (80: 0o, ro,- 81 11 is a trajectory obtained by following Tge.
Intuitively, the Bellman error at level h measures the consisteney of 0 and 0h+1 for the state-action distribution induced by TTe. In each iteration of Algorithm [ we check if E is small for all & E [M]. If so, the algorithm terminates and returns the policy gee. Otherwise, for all levels h [H] where E/ is large, we eliminate f% from Pa and proceed to the next iteration.
Now we give the analysis of Algorithm 1
Sample Complexity. To bound the sample complexity of Algorithm I. it suffices give an upper bound on the number of iterations, since in each iteration, the number of trajectories sampled by the algorithm is simply Hm = (6 (n((1 + 4/enet)d) + In(Hn H (c The following lemma gives an upper bound on the number of iterations of Algorithm The proof is given by counting the number of parameters in the parameter space. The detailed proof is given in Appendix [..]
Lemma 4.1. For any MDP instance with horizon H and satisfying Assumption 7 with sparsity k Algorithm 7 runs for at most (1 4/Emet) / (+) iterations.
Remark 2. Previous works (Weisz et al. 2022 Wang et al. 2021b) show that even when the op- timal Q-function is well-specifted, any RL. algorithm would require sample size with exponential dependency on d or H. Note that this is equivalent to the case where the sparsity k = d and the approximation error e = 0 in our setting. Therefore, in our misspecified setting, which is strictly harder, exponential dependency on k is unavoidable, unless we can accept an exponential depen- dency on H.
Suboptimality of the Returned Policy. We now show that with probability at least 1 - d, the suboptimality of the returned policy at most (2c + 26net + 46stat) H. H. First. we define a high probability event E, which we will condition on in the remaining part of the analysis.
Definition 4. Define E as the event that (E Eg1 S Estat and s,, Vo(sn) - Eigími Vo(o1) S
Estat. (where s), is from D for all iterations t, horizon E [H], and parameter E Ph. Lemma 4.2. Event E holds with probability at least 1 1-16 8.
To prove Lemma 4.2 we first consider a fixed level h and iteration t. Since the empirical Bellmen
error E is simply the empirical estimate of E/ and Eiem)) (o())) is simply an empirical estimate of
En Vo(ss). applying the
incquality respectively would suffice. Moreover,
the number of iterations has an upper bound given by Lemma 4.1 Therefore, Lemma follows
by applying union bound over all h E [H] t [(1 + 4/Cnet)* ( H] and parameter f E PR-
We next show that, conditioned on event E defined above, for the sequence of parameters 0* (0% .r.... (H.1) that satisfies Assumption 1 we never eliminate 0) from Ph, for all h E [H] Lemma 4.3. Conditioned on event E defined in Definition + for a sequence of parameters
(0%, 0r,..,0;,,11 that satisfies Assumption and their approximutions 07, = arg minleeg 11%
011, during the execution of Algorithm 0z is never eliminated from for all h E [M].
To prove Lemma 4.3 the main observation that, for E [H - the average Bellman error induced by 0r and 0h+1 = arg max Ex (8)+ is always upper bounded by fnct) regardless of the distribution of (sh, an) (cf. Definition 3 Conditioned on event E, the empirical Bellman error induced by 0; and 0% is at most 2e+ +3 Similarly, the empirical Bellman error induced by 0 is at most é + Enet + Estat In Algorithm we climinate function 8% only when the empirical Bellman error is larger than these (Line 15). Thus, 0 is never eliminated.
We now show the suboptimality of the policy returned by Algorithm is at most (2e + 26net + A H.

---

Published as a conference paper at ICLR 2025
Lemma 4.4. For any MDP instance satisfying Assumption conditioned event E defined in Definition 4 A returns a policy π satisfying V I (2c + 2e + 46stat H.
To prove Lemma 4.4 we first recall the policy loss decomposition lemma (Lemma in Jiang et al.
(217 ) which states that for policy induced by a sequence of parameters 0 = (0o, .1..... 0H-1) (x0) - Ve is upper bounded by the summation of average Bellman error over all levels h E [H] When Algorithm [ terminates, the empirical Bellman error must be small for all h E [H], and therefore, the average Bellman error is small by definition of the event E. Moreover, in Line of Algorithm
[ we always choose a parameter 0 that maximizes (s())) Since the sequence of functions 6" (0g. .i.....07+ -11 is never eliminated by Lemma 4.3 we must have Vo, (5o) > Voz (su) 2 V V Cuet: which gives an upper bound on the suboptimality of the policy returned by [Igorithm[]] Combining Lemma 4.1 Lemma 4.2 and Lemma 4.4 we can prove Theorem I.3]
Remark 3. While Algorithm 7 Jassmmes the sparsity constant k is known, it can be easily adapted to the setting where k is not known beforehand. For such setting, we could enumerate starting from k = 1, and use the following observations: 1) If the true k, say k", is larger than k, then running our algorithm with sparsity k will eliminate all the parameters in the parameter space Ph for some horizon h. 2) If for all h, there exists one parameter in Ph that has not been deleted, the we have identified k². The sample complexity of this process is asymptotically the same as running Algorithm 7 with known since the true k dominates the sample complexity.
Implications. We can think of the bandit setting as MDP with H = 1 and derive the following.
Corollary 4.5. For the bandit setting satisfying Assumption 7 Algorishm returns an action â such
that r(a") r(ā) S. 2E + net + 4estat-
Remark 4. Here we compare Corollary 4.5 with the result in Dong & Yang (2023). Scrutinizing the
analysis in Dong & Yang 2203), the suboptimality achieved by their algorithm is 4 + Cstat, which worse than our suboptimality guarantee. On the other hand, the algorithm in Dong & Yangl (2023)
also returns a parameter 0 such that K(b(a), 0) r(a)] S 2e + esta for all a E A (which is the best possible according to Theorem 1.1y where our algorithm only returns near-optimal action.
CONCLUSION
We studied the RL problem where the optimal Q-functions can be approximated by a linear function with constant sparsity k. up to error of We design new algorithm with polynomial sample complexity, while the suboptimality of the returned policy is O(He), which is shown to be near- optimal by an information-thhorele hardness result.
While our algorithm achieves near-optimal suboptimality, future work could focus on improving its sample efficiency, particularly by reducing the dependence on the horizon length H or eliminating the exponential dependency on Enet-
Future work could also consider achieving the H/C-e versus exp(C) trade-off the upper bounds, similar to Theorem 3.2 For deterministic transition, we could segment the horizon into blocks and conduct exhaustive exploration within them. For stochastic transitions, importance sampling techniques, such as those of Kearns et al. 1999), could be explored.
REFERENCES
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complex- ity and representation learning of low rank MDPs. Advances in neural information processing systems, 33:20095-20107, 2020.
Alekh Agarwal, Yujia Jin, and Tong Zhang. VOQL: Towards optimal regret in model-free rl with nonlinear function approximation. In The Thirty Sixth Annual Conference on Learning Theory, pp. 987-1063. PMLR, 2023.
Philip Amortila, Tongyi Cao, and Akshay Krishnamurthy. Mitigating covariate shift in misspecified regression with applications to reinforcement learning, 2024.
10

---

Published as a conference paper at ICLR 2025
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value- value-targeted regression. In International Conference on Machine Learning, pp- 463-474. PMLR, 2020.
Djallel Bouneffouf, Amel Bouzeghoub, and Alda Lopes Gançarski. contextual algorithm for mobile context-aware recommender system. In International conference neural informa- lion processing, pp. 324-331. Springer, 2012.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy opti- mization. In International Conference on Machine Learning, pp. 1283-1294, PMLR, 2020.
Fan Chen, Song Mei, and Yu Bai. Unified algorithms for rl with decision-estimatioon coefficients: No-regret, pac, and reward-free learning. arXiv preprint 1rXiv:2209.11755, 2022a.
Zixiang Chen, Chris Junchi Li, Angela Yuan, Quanquan Gu, and Michael Jordan. general framework for samplc-efficient function approximation in reinforcement learning, arXiv preprint arXiv:2209.1500 15634, 2022b.
Christoph Dann, Mehryar Mohri, Tong Zhang, and Julian Zimmert. A provably efficient model-free posterior sampling method for episodic reinforcement learning. Advances in Neural Information Processing Systems, 34:12040-12055 2021.
Jialin Dong and Lin Yang. Does sparsity help in learning misspecified linear bandits? In Interna- tional Conference on Machine Learning, pp. 8317-8333, PMLR, 2023.
Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning, pp. 2826-2836. PMLR, 2021.
Simon S Du, Sham M Kakade, Ruosong Wang, and Lin F Yang. Is good representation sufficient for sample efficient reinforcement learning? In International Conference on Learning Represen- tations, 2020.
Andre Esteva, Alexandre Robicquet, Bharath Ramsundar, Volodymyr Kuleshov, Mark DePristo, Katherine Chou, Claire Cui, Greg Corrado, Sehastian Thrun, and Jeff Dean. A guide to deep learning in healthcare. Nature medicine, 25(1):24-22) 2019.
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487 2021.
Dylan Foster, Noah Golowich, and Yanjun Han. Tight guarantees for interactive decision making with the decision-estimation coefficient. arXiv preprint arXiv:2301.08215, 2023.
Zeyu Jia, Lin Yang, Csaba Szepesvari, and Mengdi Wang. Model-based reinforcement learning with taluettargeted regression. In Learning for Dynamics and Control, pp. 666-686. PMLR, 2020.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire Con- textual decision processes with low bellman rank are pac-leamable. In International Conference on Machine Learning, pp. 1704-1713. PMLR, 2017.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143. PMLR, 2020.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances in neural information processing systems, 34:13406-13418 2021.
Michael Kearns, Yishay Mansour, and Andrew Ng. Approximate planning in large pomdps via reusable trajectories. In S. Solla, T. Leen, and K. Müller (eds.), Ad- vances in Neural Information Processing Systems, volume 12. MIT Press, 1999. URL cc/paper /tte///ap/////999/////. 4 (F39cch9366c77998567793333333333 1aeees5558888. ba Paper.

---

Published as a conference paper at ICLR 2025
B Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A Al Sallab, Senthil Yoga- mani, and Patrick Pérez. Deep reinforcement learning for autonomous driving: A survey. IEEE Transactions Intelligent Transportation Systems, 2021.
Dingwen Kong. Ruslan Salakhutdinov, Ruosong Wang, and Lin Yang. Online sampling for reinforcement learning with general function approximation. arXiv preprint 1xXx::2006002203,, 2021.
Tor Lattimore, Csaba Szepesvari, and Gellert Weisz. Learning with good feature representations in bandits and in RI. with a generative model. In International Conference on Machine Learning, pp. 1660-5670. PMLR, 2020.
Zhihan Liu, Miao Lu, Wei Xiong, Han Zhong, Hao Hu, Shenao Zhang, Sirui Zheng, Zhuoran Yang, and Zhaoran Wang. One objective to rule them all: A maximization objective fusing estimation and planning for exploration. arXiv preprint arXiv:2305. 18258, 2023.
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pp. 2010-2020. PMLR, 2020.
Gergely Neu and Ciara Pike-Burke. A unifying view of optimism in episodic reinforcement learning. Advances in Neural Information Processing Systems, 33:1392-1403, 2020.
Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. Advances in Neural Information Processing Systems, 27, 2014.
Eric M Schwartz, Eric T Bradlow, and Peter S Fader. Customer acquisition via display advertising using multi-armed bandit experiments. Marketing Science, 36(4):500-522, 2017.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on learning theory, pp. 1998-2933. PMLR, 2019.
Andrew Wagenmaker and Dylan J Foster. onttiaiy- in interactive decision making: Toward non-asymptotic theory. In The Thirty Sixth Annual Conference on Learning Theory, pp- 1322 1472. PMLR, 2023.
Ruosong Wang, Dean P Foster, and Sham M Kakade. What are the statistical limits of offline rl with linear function approximation? arXiv preprint arXiv:2010.1 1895, 2020a.
Ruosong Wang, Russ R Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33:6123-6135. 2020b.
Ruosong Wang, Yifan Wu, Ruslan Salakhutdinov, and Sham Kakade. Instabilities offline rl with pre-trained neural representation. In International Conference on Machine Learning, pp. 10948- 10960. PMLR, 2021a.
Yining Wang, Ruosong Wang, Simon S Du, and Akshay Krishnamurthy, Optimism in reinforcement learning with generalized linear function approximation. arXiv preprint wtxXiv:9922.041.00 2019.
Yuanhao Wang, Ruosong Wang, and Sham M. Kakade. An exponential lower bound for linearly- realizable mdps with constant suboptimality gap, 2021b. URL /tR.https/////xw..oogg
2103. 12690
Gellért Weisz, Philip Amortila, and Csaba Szepesvári. Exponential lower bounds for planning in mdps with
optimal action-vales value functions. In Algorithmic Learning Theory, pp. 1237-1264. PMLR, 2021.
Gellért Weisz, Csaba Szepesvári, and András György. Tensorplan and the few actions lower bound for planning in mdps under linear realizability of optimal value functions, 2022. URL https: wwarxxi.orr//bbb. /2tp://bb///111... 021
12

---

Published as a conference paper at ICLR 2025
Andrew Chi-Chin Yao. Probabilistic computations: Toward unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), pp. 222-227. IEEE Computer Society, 1977.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Limiting extrapo- lation in linear approximate value iteration. Advances in Neural Information Processing Systems, 32, 2019.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near op- timal policies with low inherent bellman error. In International Conference Machine Learning, pp. 10978-10989. PMLR, 2020a.
Andrea Zanette, Alessandro Lazaric, Mykel J Kochenderfer, and Emma Brunskill. Provably ef- ficient reward-agnostic navigation with linear value iteration. Advances in Neural Information Processing Systems, 33:1 13:11756-11700 1766, 2020b.
Han Zhong, Wei Xiong, Sirui Zheng, Liwei Wang, Zhaoran Wang, Zhuoran Yang, and Tong Zhang. Gec: unified framework for interactive decision making mdp, pomdp, and beyond. arXiv preprint arXiv:2211.01962, 2022.
Dongruo Zhou and Quanquan Gu. Computationally efficient horizon-frie ffre reinforcement learning for linear mixture mdps. Advances in neural information processing systems, 35:36337-36349, 2022.
Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for dis- counted mdps with feature mapping. In International Conference on Machine Learning, pp. 12793-12802. PMLR, 2021.
13

---

Published as a conference paper at ICLR 2025
A PROOFS IN SECTION
A.1 PROOF OF THEOREM 3.1
== (C) 1)e 42
50
P. T
St
S2
(+ 2)e
0 1 -15
P
4i 4g
h 2
S3
S4
55
56
( ON 50
0.
à = -
S28-1111
S2H-2
00)=
4j-1
44g
aen Prard
Figure 2: Illustration of the hard instance for Theorem 3.1
Proof. Consider an input distribution where az drawn uniformly random from {ai, 02}. By Yao's minimax principle, it suffices to consider the best deterministic algorithm, say A. Note that, since we have no sampling ability, a deterministic algorithm in this setting can be seen as a function that takes in feature function á and returns policy Also, for all instances supported by this distribution, their inputs é are the same. Thus, the policy returned by A is fixed. Denote the policy and denote the trajectory following (so, do To: 81, a1 P1............ SH-1- aH-1: -1 Ph-1). The suboptimality of π can be written as
V V Σ Iaa # anl
h=
Since on fixed and az is drawn uniformly random from {a1, .2). , I[a + anl = with probability 1/2. Thus, (V* V*)/e is binomial random variable, (V* V*) BHH, 1/2). The expectation of (V*- - V*) is then He/2, and its variance is H²² /4. Using Chebyshev inequality, with probability 0.99, we have
V V -
1 He 5c 5
sufficiently large H 100.
A.2 PROOF OF LEMMA 3.3
Proof. Consider an input distribution where i* (i). i..... 1 is drawn uniformly random from [r]m Let e(i* a) be the query complexity of runming algorithm a solve the problem with correct indices i'. Assume there exists 0.1-correct algorithm A for m-INDQ, that queries less than 0.9n times the worst case. Then, using Yao's minimax principle, there exists a deterministic algorithm A' with c(i", A') < 0.9m for all i* E [n]] m2 such that
P[A'' (j. 17) for some [m]] > 0.9.
We may assume that the sequence of queries made by is fixed until it correctly guesses one of in- This is because A' deterministic, and the responses A'' receives are the same (i.e. all guesses are incorrect) until it correctly queries (j,27) for some Let S .s..... Sk } be the sequence of first l guesses made by A', and let TEAD [n]m be set of all possible it's such that the guesses in S
14

---

Published as a conference paper at ICLR 2025
are all incorrect. Denote the number of guesses INDQ in S by ny, then nj are also fixed, and Ej{mm R = k. The size of LAD then satisfies
IADD 1 (n -nz) 2 (n (nkk)n" k)n
Set k as the worst-case query complexity of A'. Then, for all 1" E BADD the output of A' is incorrect. Since it is drawn uniformly random from [n]]", the probability of A' being incorrect is
TBDD [m mm
(n k))m-1
(n - 0.9n)m" m-
P[A' is incorrect]
> 0.1,
n
where in the second to last inequality we used ls 0.9m.
However, this contradicts with the fact that P[A'outputs (j. (j,zg) for some j E [m]] 2 0.9. Thus, there does not exist 0. Iccorect algorithm that solves the problem with less than 0.9r queries in the worst case.
A.3 PROOF OF THEOREM 3.2
Proof. First, we prove our claim based on the assumption that C' is an integer that divides H. We can create the hard instance described in Section 3.2
We reduce the problem to H/C-INDQ2e. Assume there exists algorithm A that takes less than 0.9 2 C' samples, such that, with probability at least 0.9, it outputs a policy æ with subopti- mality -*-V" H/C- e, By definition, at round lowing a trajectory (So, og. To...., SH 1: 1H TH-1): Based on A, we create an algorithm A' for H/C-INDQae as follows. Consider A is querying the trajectory (5o, ag ru .... For eacc q E {0...., H/C 1}, we can map (ag....., ./o ((+1))-11)) an index in (29] "eJuunnn the bi- jection g. Thus, we make a sequenee of H/C guesses, ((g, ((g.g(a glage....................... a (9+1)C-111 -1+1))-1))) 1)) H/C-1 to the H/C-INDQ2e. If the guess (g.g(a'c...... .......................... (1-+)))1))) is correct for some q, A receives a reward o at level (q+ 1)C - i.c. r/ -(g+1)--1 = r( (( ( - = e. For all other state-action pairs in the trajectory, algorithm A receives zero reward. Since A takes less than 0.9. 0.
interacts with the MDP instance by fol-
8 sn ..
2C.C samples, it queries less than 0.9 _ C/ H trajectories, corresponding 0.9 2 guesses to H/C-INDQje in total. Recall that A outputs policy æ with suboptimality V V < H/C e with probability at least 0.9. This means the sequence of guesses to H H/C-INDQza made by π must have at least one of them being correct. Thus, A' a 0.1-correct algorithm that solves H/C-INDQ2e with less than 0.9 2 guesses. However, by Lemma 3.3, such an algorithm does not exist, so A does not exist. We conclude that any algorithm that returns a policy with suboptimality less than H/C with probability at least 0.9 needs to sample at least 0.9 C- 2c times.
Now we consider when C is not an integer that divides H. There are two cases. First, consider C as an integer that does not divide H. Let H' = [H/C- C, then we can make the same construction as above for the first H' horizons, and set the reward as zero for all the state-action pairs in the remaining H H' levels. Because the rewards are the same for levels H' through H 1, different do not make a difference to V*, Therefore, we only care about the first
values of (TH'.... - conclude from our above analysis that, any algorithm that returns policy with [H/C]= e with probability at least 0.9 needs to sample at least 0.9 C. 2 times. For the second case, we consider when C' is not an integer. Let C' [C], we can apply our conclusion from the previous case. That is, any algorithm that returns a policy with suboptimality less than JH/CJ with probability at least 0.9 needs to sample at least 0.9 C _0.20" He 26
H' levels,
suboptimality less than H /C'
times. Since 2C' < H. we have [H/C'] e [H/C] 2 0.1 .C2, we finish the proof.
Also observing that 0.9 C¹. >
15

---

Published as a conference paper at ICLR 2025
B PROOFS IN SECTION
B. PROOF OF LEMMA 4.1
Proof. In each iteration, we either output a policy or delete at least one function in Ps. for some E [M l]. Since there are Exe(H-I] (184) ( S (1 + 4/Enet) functions in total initially, the algorithm is guaranteed to terminate within (1 + Ane (7) iterations.
B.2 PROOF LEMMA
Lemma B.1 (Deviation bound for Er.. For fixed iteration and horizon la [H]. with probability at least 8, we have
In2 In 8
8 S 4v
2m
Hence, we can set m
16(In 2-1n(6))
to guarantee that ( E% Estat
2c
Proof. Recall that the batch dataset D, = {(a); ro s1 -1 -)- is collected by playing policy Tge. We define g (1)) r(hh abh Vos,, (5h+1), then &t EE= &
st,
By definition of Eg, it satisfies
& = B1
Further, since (ő(s, a), 0*) E 1- and r(s, a) [0, 1] for any state-action pair (s, a), we have c) E [-3, 1]. Thus, using Chernoff- Chemoff-Hoeffding inequality, we get, with probability - 8²,
E EN
at ElEL)
S $4V
1n2 In
2m
Lemma B.2 (Deviation bound for Eanwat, Vo(st)). For fixed iteration t, horizon E [H], and parameter E Pho with probability at least 1 8', we have
Exg Vo(on)
Σ Vo(sh)
S
In2 In
2m
[E[m]
1n2 1n2-l guarantee that 18%, - EEil < Cstat
Hence, we can set
2c
Proof. Recall that the batch dataset Dj, {( ag ró. ....... st 1 1h sW is collected
by playing policy th. By definition, satisfies
E my m Vo(sn) = Epg
vo(s
xE(m)
Further, since (s)s) [0, 1] for any state using Chernoff- inequality, have with probability 1 8'
1 Σ vo(st) m (e(m)
In 2 In 8
E Esnoan Vo(sn)
2m
16

---

Published as a conference paper at ICLR 2025
Proof. Define Ef, to be the event
E = f1E) Ex1 S cstath:
then by Lemma B.1 P(E 2 1 - 62(2(1 + 4/cnet) (k) H?) for all iterations E [(1 +
4/Enet) )t ((()) HJ and horizon [/]].
Define Ey,,, to be the event
{ Beannn Vo(sn)
1 Σ Volsh)
S Estat
m
2E(m²
then by Lemma B.2
((E,,.))
8/(2(1 4/cnet) ) (x) HH2) for all iterations t [(1 +
4/Enet) (i) HJ. horizon & E [H]. and E Ph.
We lower bound the probability of E' by union bound
20) Σ
P(E
EE Σ bE(H] DEPs
P(EL))))
2 11-6 8.
AE(M
B.3 PROOF OF LEMMA 4.3
Proof. Let 8" (0) ................................ .6 be the sequence of parameters such that, for each h [H], the
non-zero sub-vector of 0z is in N and is closest to the non-zero indices in 0" Then, since A is Guet/ /ee//mmai we have by Assumption that
Ko(s, a), b (s, < (ō(s, a), 0%) Q* (é(s, - (o(s, 0N S c Cuets
for all s horizon h and action a .A.
At iteration 6, algorithm deletes 0z if and only if one of the following two cases happens: (1)
h H 1, 0% 0g and E 2E + 2Enet + 3estat, (2) h H 1. 0f 07 0 and
ôt - > e Enet + Estat-
For any state-action pair (sh, an) at level where h E [H 1], we observe by definition that
("n, an) B[r(sn, an)
Thus, we can upper bound E by
Ex =E((s(sn an), 0%) - r(sh, an) - Von+. (sh+1)]
<E[(Q" (8n, an) + e + enot) - r((h, an) - Vo, (8h+1)]
(By Assumption I
Here, (8o, 4o, To. an, rT) is a trajectory following TØ, and 8h41 P(sh, az).
Recall that 0f is chosen by taking the function that gives maximum empirical value level h,
Σ Vog
(s)))
1 Σ VOL (sh),
VI vE[m]
TTA (E(m]
where 8), are taken from the dataset D Moreover, we are conditioned under event E, so we have
Vo (sn) E[Vo; (sn)]
Ver (sh) + Cseat]
Veg (sh.) Estat
2Estat
m sE(m)
VE
for all h and f.
17

---

Published as a conference paper at ICLR 2025
For the first case, consider h [H 1]. We have
E% <BI(Q" (5h; an) + e eet)
r(sh, ap) Vor (sh+1)]
( an) r((,, 0b)
(Vii+) (9h+1) 2estat)] ) + + Enot
=E[Q" (sn, an) - r(33: 0h)
fh+t ( (8h+1) }} + + Enet + 2estat
(since Viū+t1 maxaEA shit1 (8++1, a))
=E|Q"(s an) - r(8h, ah) - (Q" (sh+1, Th+ (sh+1)) - c- Cnet) + c ++ Cuet + 2cstat (By Assumption
(s an) - r(sh: 0n) - Q' (sh+1, T (sh+1)))) 26 + 2cet + 26stat
=2c + net + ststat.
(since Q" (sh+1: Thtz (8h+1)) (s+1))) Viita (8h+1))
Given that we are conditioned under event E, E - Eg S Estat for all iteration and all horizon h. Thus, E < 2c + nent + 36stat-
For the second case, we consider H We have
- [B[( ax-1) +) ((SH-1, + Enets
because H 1 is the last level.
Again, given that EH + Estat S + enet + Estat-
conditioned under event E, we have E E-H-1 Cstat so Et fH
B.4 PROOF OF LEMMA 4.4
Proof. Algorithm 1 terminates and returns policy at iteration t only if 0' satisfies the conditions in line 6, and by Lemma 4.3 there always exists a nice sequence of functions {07 1 I-1 h= that satisfies these conditions. Also, Lemma 4.1 indicates that the algorithm terminates within a finite number of iterations. Thus, algorithm is guaranteed to terminate and return policy.
Let the output policy be was i.e. ε% < 2e 2enet + 3estat for all h [H - 2] and E S 6 + <nct. + Estat. The loss of this policy can bounded by
V V*((s) VMa (so) =Q" (so, x" (so)) V (so)
((0(50, मं (so)), 05) + + enet)
V (so)
(By Assumption
H-1
<((0(50 Teg (so)) 03) + +e Enet) E
r(sh, ax)]
h=n
(since of is chosen by taking the maximum)
H-1
+ Cne +
E.
Σ
(o(sn, On) r(sn, an) (0($0+1,0u+1)) 0h+z)
h=0
(telescoping sum)
H
+ Cnc +
E
(h)s ah) r(sh, an) (0(9)++)
h=0
(linearity of expectation)
H-1
H-1
=6 + Ene + Σ E < + Enet + Σ (6) + Estae) S (2e + 2E + 44stat) )
h=0
h=0
C ADDITIONAL PROOFS
C.1 PROOF OF THEOREM L.1
Proof. We construct a hard instance as follows. For each E [n], define Φ(a) = e. Let 6" be ran- domly selected from (-1,1) 1), and let a" is uniformly chosen from A. The reward r is deterministic
18

---

Published as a conference paper at ICLR 2025
and is defined
r(a) [0 _ =
otherwise.
Therefore Ir(a) -0 ((a))) S holds true for all actions a E A.
By Yao's minimax principle, it suffices to consider deterministic algorithms. Let A be deterministic algorithm that, by taking less than 0.9n samples, returns a f with (f(a) - r(a)] < 2e for a E A with probability at least 0.95. We can say the sequence of actions made by A is fixed until it receives a reward r(az) o 0 at some round t. This is because
deterministic, and the responses A receives the same (i.e. all actions have reward 0) until it queries a". Let S (01,..... Oz) be the sequence of actions made by A. Let ABAD C A be the set of actions that are not S. We have
Pl]f(a) - r(a)) < 2e, Va E A =P(]f(a) - r(a)) < 2e, Va E Ala" E ABAD]P(a" E ABAD] P(l((a) r(a)) < 2c, va Ala" ABADDPPa" & ABAD] <P[]f(a) r(a) < 2c, Va E Ala" ABBD]P[(a E ABAD]
(1- ABAD))
Since / < 0.9n and a" is chosen uniformly random from A, the probability that a² E ABAD is
ABBAD|
1 - 0.9n 0.1.
Pla" E ABAD]
[A]
When a" E ABAD. the output of our deterministic algorithm must be fixed. We denote such output
by r'. Consider a fixed a* ABAD, we have (r'(a)) 2e < 2e, then r'(a") E (0, 4e), and
(a*) - (-2e)) > 2e. Similarly, if we have (r'(a*) (-2t) < 2e, then lr'(a)) 2e] > 2t.
Since 8 is chosen uniformly random in {-1,1}, we know r(a") is chosen uniformly random in { {-2e, 2c}. Thus,
Pl]f(a) r(a)) 2e, Va Ala" E A P -(a"" 2ela" ABADI 0.5.
We have
P(i((a) - r(a)] < 2e, Va A] < P(a" E ABADl + + Pla" E AnADl) < 0.5 0.1 0.9 = 0.95.
However, by our assumption on algorithm A, we have P([i(a) r(a)) < 2c, Va E A] > 0.95.
D BELLMAN RANK
The following definition of the general average Bellman error is helpful for proofs in this section.
Definition 5. Given any policy π S + A. feature function S x A + Rd and sequence of parameters = (fb....,0=-1) the average Bellman error of under roll-in policy क at level is defined as
E, T) = (o(ss an), 0n) -hh
aEA
Here, (so, ao. ro...., Sh, an, Th) is a trajectory by following x. and sh+1 P(sh, an)
Definition 6 (Bellman Rank), For a given MDP M, we say that our parameter space F = {0 E Rd is k-sparse, ||0||2 1) has Bellman rank of dimension d if. for all h E [H), there exist functions X F + 12d and Yn F + Hed such that for all 0, 0 e F.
(0, m0)))))) (0), (0)))
For each h E [H], define W, E dxd d as the Bellman error matrix at level h, where the j index of W; is (O, N. Then, the Bellman rank of F is the maximum among the rank of the matrices [Wa) hNEmH-
We prove Proposition
19

---

Published as a conference paper at ICLR 2025
Proof. We again construct deterministic MDP instance with binary trees. For simplicity, sume d is a power 2, and we construct the instance with horizon H = logd d. Thus, we have |S] - - = d states. We also assume the sparsity is k = so the parameter space [F] d. The rest details of state space, action space, and the transition kernel are exactly the same as in Section 3.1
The reward is defined as r(s, aj) = r(s, 02) = c for & E SH-1, and r(s, a) = for all other state- action pairs. Correspondingly, the Q-function satisfies that (* a) for all (s, a) E A.
For feature at horizon h E [H]. for 2 2h+1, we define the j-th index of 6(s, a) as Φ(x a)li je for all (s, E Sh A. For i [2 and is even, 0(822-1+0 an and 1 (2) O. i E [ and is odd, then -1:2 a1) 0 and (8 -1: [z) We also define ((s, a)
for all other state-action pairs.
Notice that, for any h [H] and [2 we have let be the one-hot vector with i-th index being 1, then (Ø(8, a), 0) Q* (s, a)] I for all (s, E Sn. x A, so our construction satisfies assumption]] !
Clearly, for each pair (s, a) E SH-1 x A, we can find 0 = (oo.... 0H-1) such that the trajectory (50,a0, created by following ne, denoted by (50, do, ro..... , -H - -H-1), satisfies s s and 011-1 = a.
Consider two parameter candidates 0,0 0' Let when following Ter Since we are considering deterministic MDP, we can calculate the Bellman error level H as follows
be the state and action level H
1 ) = -(((5-1,, 0H ((sH-1,
max (axH, OH) aEA (since - is the last level)
=(0(5H-1,04-1))004 0 -
0 -
if f 61
-- if 01 * H1
Here, the last equality holds because, for each 0H-1- there only one unique (s, a) E SH-1 A such that (i(s, u), 0H-1) =
Thus, level H submatrix of the Bellman enror matrix, W E RRddd satisfies
Wi E 1 mo,) = {0 if j
otherwise.
In other words, W = e(T - J) where T is the identity matrix and J is d x d matrix with all 1s. Define matrix W [T 1/(n - 1)J), then we have
1
wW' J)
n J=I.
n J J
n
This means W is the inverse matrix of W, and W is full rank. Thus, the Bellman rank is at least d.
20


Reviews:
[{"review_id": "e4R7khNS1D", "reviewer": "Reviewer_5nER", "summary": "The authors found a misspecified sparse linear bandit algorithm based on elimination. They first proved that the traditional approaches such as OLIVE work suboptimally in this environment, and also a naive extension from the previous bandit work [Dong & Yang, 2023] fails. After that, the authors propose a lower bound from the MDP without sample to RL with sample, using the INDQ problem as a mediator. This lower bound matches with the upper bound of their algorithm, showing that their algorithm has a near-optimal rate.", "questions": "1) I don't understand the word 'MDP without sample.' Without any trajectory, how could a learning agent learn something? You mean, 'without learning' the error is bounded by $\\Omega(H\\epsilon)$?\n\n2) Also, it is interesting that this algorithm eliminates the 'most promising candidate' first. In bandits, the elimination eliminates all the suboptimal candidates that show less upper bound than the largest lower bound (eliminate an arm i which is max_j LCB_t(j) > UCB_t (i)). Why does this difference happen?\n\n3) So what is the optimal size of the parameters, $\\epsilon_{net}$ and $\\epsilon_{stat}$? I guess they also should be in the scale of $\\epsilon$. \n\n3-1) Also just to clarify, what is $\\epsilon$-optimal in here, does this mean $V^* - V(\\pi) \\leq \\epsilon$? If so, according to your final result (Lemma 4.4), for the error $\\epsilon'$, one should set $\\epsilon/H$. This means now $m$ is proportional to $H^2$ too and the overall sample complexity also should include $H^2$, I believe. \n\n3-2) In that sense, the line 438 is very confusing. Why it is $H^2 \\cdot m$, including the $\\epsilon_{stat}^2$ in the denominator? You repeat $m$ samplings for $H$ iterations. Shouldn't it be $H\\cdot m$?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) Clarity & Soundness: Their writing was clear on these points. \n- They clearly stated their novelty and significant difference from the misspecified bandit algorithm proposed by Dong & Yang.\n- They tried to demonstrate how they set the lower bound instance by high-level, but an explicit explanation throughout Section 3, with a nice figure. (and also the main difference from Du et al. 2020)\n- The algorithm itself is also quite simple - it follows a traditional method of elimination algorithms, and thanks to the detailed explanation, I could easily get a sketch about how the proof goes on. The technique is also using some simple Hoeffding's inequality. \n\n2) Significance & Novelty: Even though their results are clearly written and easy to understand, many of their results are quite fresh and counter-intuitive. One cannot extend bandit algorithms in this case was quite interesting indeed.", "weaknesses": "1) Computationally intractable. If I understood correctly, they use an $\\epsilon$-net on the candidates for $\\theta_h$ - $P_h^0$ starts from all possible $k$-sparse vectors. After that, for each iteration, this algorithm is searching for argmax over all candidates. Also, eventually they proposed an algorithm that provides $\\epsilon$-optimal.\n\n2) Even though they tried to show their process transparently, there are some parts that I cannot understand. Please check the 'Questions' below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CISHktSPB6", "reviewer": "Reviewer_5fDB", "summary": "This paper considers the problem of online reinforcement learning with linear function approximation. It is well known if that in the presence of epsilon-misspecification (in the sense that Q* is eps-approximately linear), the best one can hope for is a an error guarantee that scales with \\sqrt{d}*eps, where $d$ is the feature dimension, even in the bandit setting where $H=1$. The main result in this paper is to show that if we additionally assume that the optimal parameter is $k$ sparse, it is possible to improve upon this guarantee. In particular:\n\n* 1) The author show that it is possible to achieve an error guarantee that scales as H*eps (with no dependence on dimension), albeit with sample complexity and runtime scaling as roughly (d/eps)^{k}.\n\n* 2) The authors show that the error guarantee above cannot be improved further, in the sense that achieving H/T*eps for any T requires exp(T) sample complexity.", "questions": "Overall, I do think the results are interesting and not necessarily obvious a-priori---they certainly piqued my curiosity. Some questions I was inspired to think about based on the results are as follows:\n\n* Can we get similar guarantees beyond linear function approximation? My thought would be that if we assume that Q*_h is eps-approximately realizable by a class \\mathcal{F}_h, then perhaps we can get H*eps error while paying for roughly max_h{Covering-Number(\\cF_h, eps)} in the sample complexity using a generalization of the algorithm. If so, this would suggest that the linear structure is actually not that important.\n\n* Have the authors thought about whether there exists an algorithm that achieves the H/T*eps error vs exp(T) sample complexity tradeoff in the lower bound?\n\n* Is there any hope of achieving just d^{k} sample complexity instead of (d/eps)^k sample complexity?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "This paper makes a reasonable contribution to the theory of reinforcement learning. Guarantees in the linearly (approximately) realizable setting the authors consider are non-trivial and often somewhat surprising, so I think this paper makes an interesting contribution by filling in another piece of the landscape.", "weaknesses": "The main drawbacks preventing me from giving a higher score are as follows:\n\n* On the upper bound side, the significance of the algorithmic techniques is somewhat narrow. Concretely, the authors consider a setting where we have a separate parameter $\\theta*_h$ for each step $h\\in[H]$. If we instead assume that there is a shared parameter $\\theta*$ for all steps $h$, then I believe that simply enumerating over an epsilon-net for the parameter space and trying each policy one-by-one would be sufficient to achieve the approximation and sample complexity guarantees the authors get. So, the only reason why a non-trivial algorithm is required at all is because there is no parameter sharing across the steps $h$. Indeed, without parameter sharing, an epsilon-net would have size at least 2^H and lead to 2^H sample complexity, so the authors' contribution can be viewed as removing this exponential dependence on $H$ for this setting.\n\n* The problem setting in the paper is fairly niche, and will probably only be interesting/compelling to research working on core RL theory. Broader impact is unclear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YGcwVqamkR", "reviewer": "Reviewer_AMgy", "summary": "In this work, the authors study RL where Q-function is sparse codable up to $\\epsilon$ error.\nTheir main contributions are\ni) showing the existence of a hard instance where achieving suboptimality less than $H \\epsilon / C$ requires sample complexity exponential to C,\nii) establishing a theoretical method achieving suboptimality of $2H \\epsilon + o(1)$ with polynomial sample.", "questions": "Does the proposed method exploit the sparseness except through the cardinality of the epsilon net?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- An interesting work on the RL learnability under limited knowledge of environment.\n- The theoretical results are strong in the sense that almost-matching upper and lower bounds are presented.", "weaknesses": "- The sample complexity grows exponentially to the sparseness $k$, which is unavoidable with the present set of assumptions but undesirable in practice.\n- The construction of the hard instance depends on exponentially large state space. This is not uncommon in the theoretical analysis, but worth discussing if similar results hold with smaller state space.\n\nSome mathematical definitions are confusing: \n- Def of $\\Delta(\\cdot)$ lacking?\n- Why parameters restricted on sphere? (I suspect the authors are confusing sphere and ball)\n- How s_0 is sampled? Is it fixed?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tNGnYwKThi", "reviewer": "Reviewer_FFJt", "summary": "$\\textbf{Background}$ In Q-learning with function approximation, it is assumed that the optimal Q-value function can be written as a linear function of the feature of each state, action pair, i.e., $Q^*(s, a) = <  \\theta^*,  \\psi(s, a)>$.\nIn the misspecified setting, the assumption is relaxed to be such that the optimal Q-value function is $\\epsilon$-close to some linear function of the features, i.e., $| Q^* - <  \\theta^*,  \\psi(s, a)> | < \\epsilon $.\nUnfortunately, it has been shown that exponentially many samples are required in the misspecified setting even when the MDP only has $H=1$ step, which simplifies to the linear bandit setting.\nYet, a prior work shows that the hardness result can be circumvented in the linear bandit setting provided that the optimal secrete vector $\\theta^*$ is further assumed to be $k$-sparse for some constant $k$. In such cases, the sample complexity for linear bandit has been improved to $O( (d/\\epsilon)^k )$.\n\n$\\textbf{Contribution of this work}$ In this work, it has been shown results with a similar favor hold for general multi-step Q-learning as well. In particular, they give an algorithm that uses polynomially many samples and returns an $O(H \\epsilon)$-optimal policy, where $H$ is the number of steps of the MDP.  Interestingly, the error $H \\epsilon$ has been shown to be optimal up to polylogarithmic factors.\n\nThe main novelty of the proposed algorithm, compared to the prior work, is in how it chooses the policy to execute. In particular, the policy is chosen to maximize the so-called “empirical roll-in distribution” at all levels. After that, similar to prior work, the algorithm proceeds to compute average bellman error, and eliminate parameters that lead to large Bellman error (though the algorithm is a bit more conservative in the sense that it always eliminates at most one candidate parameter per level in every iteration).", "questions": "Do the authors have a guess whether the exponential dependency on $k$ in the sample complexity is necessary?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The error guarantee of the algorithm proposed is shown to be optimal though it has a surprising linear scale with the number of steps $H$. The lower bound argument is quite interesting. They first demonstrate a suboptimality gap assuming that the RL algorithm is given no samples using hard instances based on binary trees. They further show that the instance can be modified so that the reward-signal is exponentially sparse. Hence, the algorithm must search the space in a brute-force manner to extract useful information.", "weaknesses": "The algorithm is structurally similar to the algorithm from Jiang et al., 2017. Since the algorithm eliminates one parameter per level every iteration, it is almost doing a brute-force search over the entire parameter space. As a result, the sample complexity and runtime of the algorithm both scales exponentially with the sparsity parameter $k$ of the problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)