Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamics
Authors: Runzhe Wu
Ayush Sekhari
Akshay Krishnamurthy
Wen Sun
Venue: ICLR 2025 Oral (2025)
Keywords: reinforcement learning theory
linear function approximation
Primary area: reinforcement learning

Abstract: We study computationally and statistically efficient Reinforcement Learning algorithms for the *linear Bellman Complete* setting. This setting uses linear function approximation to capture value functions and unifies existing models like linear Markov Decision Processes (MDP) and Linear Quadratic Regulators (LQR).  While it is known from the prior works that this setting is statistically tractable, it remained open whether a computationally efficient algorithm exists. Our work provides a computationally efficient algorithm for the linear Bellman complete setting that works for MDPs with large action spaces, random initial states, and random rewards but relies on the underlying dynamics to be deterministic. Our approach is based on randomization: we inject random noise into least squares regression problems to perform optimistic value iteration. Our key technical contribution is to carefully design the noise to only act in the null space of the training data to ensure optimism while circumventing a subtle error amplification issue.

Published as a conference paper at ICLR 2025
COMPUTATIONALLY EFFICIENT RL UNDER LINEAR BELLMAN COMPLETENESS FOR DETERMINISTIC DY- NAMICS
Runzhe Wu" Corelll University rw646@corne11.cm edu
Ayush Sckhari' MIT
sekhar 1@mim.m....... edu
Akshay Krishnamurthy Microsoft Research Aushaykrrmicrosofe
Wen Sun
Cornell University ws4550cornel1, edu
ABSTRACT
We We computationally and statistically efficient Reinforcement Learning algo- rithms for the linear Bellman Complete setting. This setting uses linear function approximation to capture value functions and unifies existing models like linear Markov Decision Processes (MDP) and Linear Quadratic Regulators (LQR). While it is known from the prior works that this setting is statistically tractable, it remained open whether a computationally efficient algorithm exists. Our work provides a computationally efficient algorithm for the linear Bellman complete setting that works for MDPs with large action spaces, random initial states, and random rewards but relies on the underlying dynamics to be deterministic. Our approach is based randomization: we inject random noise into least squares regression problems to perform optimistic value iteration. Our key technical con- tribution is to carefully design the noise only act the null space of the training data to ensure optimism while circumventing a subtle error amplification issue.
INTRODUCTION
Various application domains of Reinforcement Learning (RL)-includde including game playing, robotics, self-driving cars, and foundation models feature environments with large state and action spaces. In such settings, the learner aims to find a well performing policy by repeated interactions with the environment acquire knowledge. Due to the high dimensionality of the problem, function approx- imation techniques are used to generalize the knowledge acquired across the state and action space. Under the broad category of function approximation. model-free RL stands out as particularly pop- ular approach due to its simple implementation and relatively better sample efficiency in practice. In model-free RL, the learner uses function approximation (e.g., expressive function class like deep neural networks) to model the state-action value function various policies in the underlying MDP. In fact, the combination of model-free frre RL with various empirical exploration heuristics has led to notable empirical advances, including breakthroughs in game playing (Silver et al., 2016; Berner al., 2019), robot manipulation (Andrychowicz al., 2020), and self-driving (Chen al., 2019).
Theoretical advancements have paralleled the practical successes in RI, with tremendous progress in recent years in building rigorous statistical foundations understand what structures in the environ- ment and the function class suffice for sample-efficient RL. These advancements are supported by optimal exploration strategies that align with the corresponding structural assumptions, and by now we have rich set of tools and techniques for sample-efficient RL in MDPs with large state/action spaces (Russo & Van Roy, 2013; Jiang et al., 2017; Sun et al., 2019; Wang et al., 2020; Du al., 2021; Jin et al., 2021; Foster et al., 2021; Xie et al., 2022). However, despite rigorous statisti- cal foundation, a significant challenge remains: many these theoretically rigorous approaches
Equal contribution.

---

Published as a conference paper at ICLR 2025
for rich function approximation are not computationally feasible, and thus have limited practical applicability. For example, some require solving complex optimization problems that are compu- lationally intractable in practice (Zanette et al., 2020b); others require deterministic dynamics and initial states (Du et al., 2020); and some methods depend on maintaining large and complex version spaces (Jin et al., 2021; Du et al., 2021) which are intractable in terms of memory and computation.
One of the most striking examples of this statistical coniuttcallcmpputttioonllll gap is observed in the Linear Bellman Completeness setting, which is perhaps one of the simplest learning settings. Linear Bell- man completeness serves as a bridge between RL and control theory literature as it provides a unified framework to capture Linear MDPs (Jin al., 2020; Agarwal et al., 2019; Zanette et al., 2020b) and the Linear Quadratic Regulator (LQR), two popular models in RL and control respectively. In partic- ular, the linear Bellman completeness setting captures MDPs where the state-action value function of the optimal policy is linear function of some pre-specified feature representations (of states and actions), and the Bellman backups of linear state-action value functions are linear (w.r.t. some feature representation). Naturally, for this setting, the learner utilizes the function class IF con- sisting of all linear functions over the given feature representation as the value function class for model-free RL. In addition to considering a linear class, we also assume that the class F exhibits low inherent Bellman error- a structural assumption that quantifies the error in approximating the Bellman backup of functions within F. The first assumption, i.e., linearity of optimal state-action value function, is perhaps the simplest modeling assumption one can make in RI. with function ap- proximation. Furthermore, emerging evidence suggests that linearity is practically useful, as with adequate feature representation, linear functions can represent value functions in various domains. The second assumption, i.e. low inherent Bellman error of the class, while being a bit mysterious, is a natural condition for statistical tractability for classic algorithms such as Fitted Q-iteration (FQI) and temporal difference (TD) learning with linear function approximation (Munos, 2005; Zanette et al., 2020b). It is also well-known that linearity alone does not suffice for efficient RL (Wang et al., 2021; Weisz et al., 2021).
While the prior works have shown that RL with linear bellman completeness is statistically tractable, and one can learn with sample complexity that scales polynomially with both d and H (where d is the dimensionality of the feature representation and H is the horizon of the RL problem), the proposed algorithms that obtain such sample complexity in the online RL setting are not compu- tationally efficient. Given the simplicity of the problem, it was conjectured that a computationally efficient algorithm should exist. However, no such algorithms were proposed. Unfortunately, the classical approaches of combining supervised learning techniques with RL in the online setting, e.g., value function iteration, which are computationally efficient by design, fail to extend to be statis- tically tractable due to exponential blowups from error compounding, especially without making norm-boundedness assumptions, On the other hand, the techniques of adding quadratic exploration bonuses, e.g., the one proposed in LinUCB (Li al., 2010) and used in LSVI for linear MDPs, also fail here as Bellman backups of quadratic functions are not necessarily within the linear class F. In fact, the search for a computationally efficient algorithm with large action spaces is open even when the transition dynamics are deterministic.
In this work, we provide the first computationally efficient algorithm for the linear Bellman com- plete setting with deterministic dynamics, that enjoys regret bound of ( HJ/2 d² H3/271/2) for feature dimension d, horizon H, and number of rounds T. Importantly, our algorithm works with large action spaces, stochastic reward functions, and stochastic initial states. The key ideas of our algorithm twofold: using randomization to encourage exploration and leveraging span argument to bound the regret. While adding random noise to the learned parameters has been quite successful in linear function approximation, unfortunately, for our specific setting, since need to add sufficiently large noise to cancel out the estimation error, blind randomization can cause the corresponding parameters to grow exponentially with the horizon. We avoid paying for this blow-up by only adding noise to the null space of the data. In particular, when the dynamics are determinis- tic, by adding exploration noise only in the null space, we can learn the value function exactly for any trajectories that lie within the span of the data seen so far. Additionally, a simple span argument bounds the number of times the trajectories fall outside the span of the historical data. Together, these techniques leads to our polynomial sample complexity bound. The resulting algorithm relies on linear regression oracles under convex constraints, which we show can be approximately solved via a random-wall walk-based algorithm (Bertsimas & Vempala, 2004).
2

---

Published as a conference paper at ICLR 2025
2 RELATED WORKS
Computational Efficient RL under Linear Bellman Completeness. Numerous works have fo- cused on computationally efficient RL within the scope of linear Bellman completeness (LBC). The simplest setting is tabular MDPs where computationally efficient and near-optimal algorithms have been well known (Azar et al., 2017: Zhang al., 2020; Jin et al., 2018). Tabular MDPs can be extended to linear MDPs (Jin et al., 2020), where computationally efficient algorithms are also known (Jin et al., 2020; Agarwal al., 2023; He al., 2023). However, in the setting of linear Bellman completeness, which captures linear MDPs, the existence of computationally effi- cient algorithms remain unclear. Previous works have resorted to various assumptions to achieve computational efficiency, such as few actions (Golowich & Moitra, 2024) and assuming MDPs are "explorable" (Zanette et al., 2020c). We provide a detailed overview the literature in Section 3.2.
Exploration via Randomization. Random noise has been powerful alternative to bonus-based exploration in RL literature. A typical approach is Randomized Least-Squares Value Iteration (RLSVI) (Osband et al., 2016), which injects Gaussian noise into the least-squares estimate and achieves near-optimal worst-case regret for linear MDPs (Agrawal et al., 2021; Zanette et al., 2020a); Ishfaq al. (2023) instead propose posterior sampling via Langevin Monte Carlo for Q-function and also obtain regret bounds for linear MDPs; Ishfaq et al. (2021) developed randomization algorithms for general function approximation assuming bounded eluder dimension and Bellman completeness for any function. Randomization is also explored in preference-based RL, leading to the first com- putationally efficient algorithm with near-optimal regret guarantees for linear MDPs (Wu & Sun, 2024). However, these approaches either have strong assumptions (e.g., Bellman completeness for any function), or inject random noise larger than the estimation error, causing exponential blow- up of parameter values- to mitigate it, they truncate the value, but this is feasible only in low-rank MDPs and challenging under linear Bellman completeness as the Bellman backup of truncated value may longer be linear. Consequently, existing algorithms cannot handle linear Bellman complete problems, and new techniques capable of managing exponential parameter values are needed.
Beyond Linear Bellman Completeness. Many structural conditions capture linear Bellman com- pleteness, such as Bilinear class (Du et al., 2021), Bellman eluder dimension (Jin et al., 2021), Bellman rank (Jiang et al., 2017), witness rank (Sun al., 2019), and cecision-estimationn coeffi- cient (Foster et al., 2021). While statistically efficient algorithms exist for these settings, no compu- tationally efficient algorithms are known.
PRELIMINARIES
A knite-horizon Markov Decision Process (MDP) is given by tuple M (8,A, T,,, Tr,,p) where S is the state space. AA is the action space, H N is the horizon, T:S x A + A(S) is the transition function, r : S A [0, 1] is the reward function and μ A(S) is the initial state distribution. Given a policy
S ((A), we denote Q (s, as E [ rs s/ s, s,a, =] as the layered state-action value function of policy and (s) QT (s. (s)) as the state value function. The optimal value function is denoted by V/ (s) max, (s). and the optimal policy is T².
We focus on the setting of linear function approximation and consider the following linear Bellman completeness, which ensures that the Bellman backup of a linear function remains linear.
Definition 1 (Linear Bellman Completeness). An MDP is said to be linear Bellman complete with respect a feature mapping & if there exists mapping T Rd Bd that, for all 0 e Rdd and all (s. S x A, it holds that
(T0,
E max(0,6(s'.0) ((5,0')'''')) s'-T(a,a) a
Moreover, we require that, for all h E [H] and (s,a) S x A, the random reward is bounded in [0, 1] with mean Tn (s, = (wi, ((s, a)) for some unknown wj. e Rd.
We assume [d(s, a) S 1 for all e S and a E A. Notably, we do not impose any upper bound on [ww la any norm non-expansiveness of the Bellman backup, distinguishing from some exist- ing works-in Section 3.1, we discuss why many existing definitions of linear Bellman completeness fail to capture even tabular MDPs linear MDPs due certain norm boundedness assumptions.
3

---

Published as a conference paper at ICLR 2025
We further assume the feature space spans R., i.e., span(fo(s,a) i S, AA) R.; otherwise, we can project the feature space onto its span or use pseudo-invend inverse in the analysis when needed. We can verify that the linear Bellman completeness captures both linear MDPs and Linear Quadratic Regulators (for a convex subset of linear functions). The proof is in Appendix E.
Next, we consider deterministic state transition.
Assumption (Deterministic transitions). For all 8 E S and a A, there is unique state s' S to which the system transitions to after taking action a on state s.
We emphasize that, although the transition is deterministic, the initial state distribution is stochastic (although we assume that (STT is independently sampled from an initial distribution our results extend to the scenarios when { heT are adversarially chosen). Additionally, the reward signals can be stochastic. Hence, learning is still challenging in this case. The goal is to achieve low regret over T rounds. The regret is defined as
T Reg- = E Σ (V VV'.
The expectation here is taken over the randomness of algorithm and reward signals. While it is defined as an average for simplicity, a concentration inequality can yield the high-probability regret. In this paper, we use asymptotic notations ((-) and O() to hides logarithmic and constant factors.
3.1 OTHER LINEAR BELLMAN COMPLETENESS DEFINITIONS IN THE LITERATURE
Several closely related definitions of Linear Bellman Completeness have been considered in the literature. In the following, we demonstrate that some of these variant definitions face limitations due to additional fe-norm assumptions. We present two commonly imposed assumptions in existing works below, and subsequently provide examples illustrating their potential limitations.
(1) Assuming Bounded ég-norm of Parameters. Golowich Moitra (2024); Zanette et al. (2020b;e) assume that any value function under consideration has its parameters bounded in ly- norm, i.e., when we apply the Bellman backup, the resulting state-action value function always lies in (Q (s,,a) = (c(ss s, aa. 0), ||0||2 I R} where R is a pre-fixed polynomial in the dimension of the feature space. We will show that this assumption might not hold true since [0]|2 is unnecessarily bounded under linear Bellman completeness.
(2) Assuming Non-expansiveness of Bellman Backup in f2-norm. Song et al. (2022) assume that, after applying the Bellman backup, the 82-norm of the value function parameters will not increase, ie., for any 8, they assume the existence of parameter such that ||6' 12 s |0||2 and (ø(s, (s,,a),6)) Es-T(s.a) max (é(s', d'),0) for all s, This assumption is stronger than the previous one and does not hold even in tabular MDPs, as we will show in the second example below.
The following example demonstrates that the two assumptions above do not generally hold under linear Bellman completeness as the norm amplification can actually be arbitrarily large.
Example (Arbitrarily Large f--norm on Parameters). Consider a layered linear MDP with three states, 81, $2, 83, and single action ai. Here $1 is in the first layer and 32 and s3 are in the second layer. For some E and p. we define @(31, (1) = (VE,VP-
((82) = (p/vE,0) and and r(5s.) = 1. We can verify that + +1- p. We assume Q-fuctionn is parameterized by O. Then, since (8(81, a1)) = p, it must hold that ||0]| (ps (ps+1-p)) ppppp=/++++ While can be arbitrarily small, the norm of 0 can be arbitrarily large.
u(ss) (0. (1 pp)). We further define r(2,.) =
(( and P(sy($1,(1) -111=111ppp Hence (($1,a1)=
We may hope to "normalize" the features in this example so that the f2-norm of the parameters bounded. However, it is unclear how to do since changing either or p will change the MDP, and feature search is likely hard problem. Essentially, this example breaks one of the assumptions in the original linear MDP (Jin et al., 2020) which requires the integral / gl to be bounded for any function g [0. 1]. Thus, while being a linear MDP, the original LSVI-UCB algorithm (Jin et al., 2020) indeed will not work for this example. However, we note that our algorithm can still work.
Nevertheless, as the above example leverages a careful design of the feature, we might hope that some ponseveansi properties could hold under stronger representation assumptions (e.g..
4

---

Published as a conference paper at ICLR 2025
when state space is tabular). Unfortunately, the following example shows that Bellman backup can be expansive even in tabular MDPs.
Example 2 (Expansiveness of Bellman Backup in f2-norm). Consider a tabular MDP with horizon H 2, S states {31....,58} in the first layer, single state in the second layer, and a single action a. On taking action a in any state in the first-layer, the agent deterministically transitions s. and on taking action a s deterministically yields a reward of 1. Since linear Bellman completeness captures tabular MDPs with one-hot encoded features where Φ(8;,) e, RR$+1 for i S and ((s,0) a) = PS- (0,.... 0, 1)", the state-action value function at the second layer can be parameterized by 02 (0..... (O....,,,.))) 0, However, applying the Bellman backup, since the return- to-go for any first-layer state s; is (because always yields a reward of 1), the backed-up up value function must be parameterized by 01 = .,) Here, we find that |0, 10/22/|02ll2 VS, thus showing that Bellman backup cannot guarantee con-expansiveness of the norn
Hence, in this paper, we aim to assume any 2--nrrm bound 82-norm non-expansiveness of the parameters. Unfortunately, without these assumptions, the ground truth parameter of the optimal value function can exponentially grow with the horizon as evidenced by the examples above, thus invalidating prior methods requiring bounded parameter. Our key contribution is an algorithm that remains efficient even if the parameter norm blows up but requiring deterministic transition.
3.2 OTHER PRIOR WORKS ON LINEAR BELLMAN COMPLETENESS
In this section, we review prior efforts on RL under linear Bellman completeness and discuss various assumptions underlying these approaches.
Efficient Algorithms under Generative Access. A generative model takes input state-action pair (s, and returns sample s' T(-|s.a) s, a) and the reward signal. With such a generative model. Linear Least-Squares Value Iteration (LSVI) can achieve statistical and computational effi- ciency (Agarwal et al., 2019). However, generative access is a big assumption, and our work aims to operate with only online access.
Efficient Algorithms under Explorability Assumption. Zanette et al. (2020c) propose a reward- free algorithm under the assumption that every direction in the parameter space is reachable. This assumption, when translated into tabular MDPs, means that any state can be reached with prob- ability bounded below by some (large enough) positive constant. This does not hold if there are unreachable states or if the probability of reaching them is exponentially small.
Computationally Intractable Algorithms. Zanette et al. (2020b) present a computationally in- tractable algorithm that requires solving an intractable optimization problem. In our work, we aim to only utilize a tractable squared loss minimization oracle.
Few action MDPs. Golowich & Moitra (2024) propose computationally efficient algorithm under linear Bellman completeness, inspired by the bonus-based exploration approach in LSVI-UCB (Jin al., 2020) for Linear MDPs. While their algorithm extends to stochastic MDPs, both the sample complexity and running time have exponential dependence on the size of the action space. In com- parison, our algorithm extends infinite action spaces but relies on the transition dynamics to be deterministic.
Deterministic Rewards Deterministic Initial State. Several existing studies provide computa- tionally and statistically efficient algorithms for more general settings but under stronger assump- tions; these methods can be extended linear Bellman completeness settings but similarly strong assumptions will also apply. Du et al. (2020) provide an algorithm based on span argument that is efficient for MDPs that have linear optimal state-action value function (a.k.a. the Linear Q" setting), deterministic transition dynamics, deterministic initial state, and stochastic rewards. Unfortunately, their approach cannot extend to settings with stochastic initial states, as we consider in our paper. Another line of work due to Wen & Van Roy (2017) considers the -'-realizable setting with deter- ministic dynamics, deterministic rewards, stochastic initial states, and bounded eluder dimension. Their approach can be extended to the linear bellman completeness setting when both rewards and dynamics are deterministic. However, their algorithm fails to converge when rewards are stochastic and thus may apply the problem setting that we consider.
5

---

Published as a conference paper at ICLR 2025
Efficient Algorithm in the hybrid RL setting. Song et al. (2022) develop efficient algorithms for the hybrid RL setting, where the learner has access to both online interaction and an offline dataset. However, they do not have fully online algorithms.
In summary, no previous work addresses the problem with stochastic initial states, stochastic re- wards, and large action spaces. This is the gap that aim to fill with this work.
ALGORITHM
In this section, we present our algorithm for online RL under linear Bellman completeness. See Algorithm 1 for pseudocode. The input to the algorithm consists of three components. First, the noise variances, {an) h-1 and on, control the scale of the random noise. Second, D-optimal design (defined below) for the feature space.
Definition 2 (D-optimal design). The D-optimal design for the set of features + {0(s,0) S,a A} distribution p over & that maximizes log det [gee p())
There always exist D-optimal designs with at most Odd2 support points (Lemma 23). Many ef- ficient algorithms can be applied to find approximate D-optimal designs such as the Frank-Wolfe The algorithm also requires a constrained squared loss minimization oracle O99, and we introduce an instantiation of 0 in Section 6.
Algorithm Null Space Randomization for Linear Bellman Completeness
Require: Noise variances {ox) h== and OR-
A D-optimal design for 4 {o(ss a) s S, A) given by {(d,, p.))
Squared loss minimization oracle O
1: Define Σ1, Σ p, for all / [H].
2: for t= 1,..., do
3: Let 01, + 0, QuH--1 + 0, V +1++1 + 0.
4: for h H...., do
5:
Let Pt, be the orthogonal projection matrix onto span( (wo(nl aia)) :i= I,...,t-- - 1})
6:
For E [m]] define o,,,, &r and Pi,,, = -I-Ptth Pt,))
Let ArA + Σi p, (o),,))) ( (o,,(
7:
8:
I/ Fit value function and reward using squared loss regression //
9:
Compute b1,, and Ø2,4 using the squared loss minimization oracle Osg as:
IM
02, + argmin (wW(
(0, (0,,,,,, -V.)) (e..ea(
(1)
Wi,h argmin
(1r, -rah))
(L)(1)
10:
// Perturb the estimated parameters by adding Gaussian noise // Update the parameters by sampling:
11:
0e, 0e, Nr - (P.))
We,h 0.,h (0, )12
Define (s, (we. + 0 (s, a)) and Ven(s) max. Qu, for all (s,a)
13:
end for
14: Define the policy such that Te, (3) argmax, (s,a)
15: Generate trajectory (st,1, fr.....,,, St ar, Tr, T
16:
Define Σ1-1A t= ΣLa + ((.LA (st,h, a) ) for all h [H]
17: end for

---

Published as a conference paper at ICLR 2025
The algorithm begins by initializing the covariance matrix Σ1,4 for all h [H] using the optimal design, which differs from most standard LSVI-type algorithms where is initialized to the identity matrix. We believe that the identity matrix is unsuitable here since we do not assume any 22-norm bound on the parameters. Additionally, recalling that we assume the feature space spans RM it ensures Σt, invertible for all and h. Otherwise, pseudo-inverses
be used instead.
At each round e [T]. the algorithm operates in a backward manner starting from the last horizon H. For each h [H] it first constructs the orthogonal projection matrix PE, onto the span of the historical data. It then decomposes the D-optimal design points into the span and null space compo- nents using the projection and constructs 4r.h- By separating the span and null space components, it facilitates clearer concentration bounds for the subsequent Gaussian noise.
The algorithm then performs constrained squared loss regression to estimate the value function and reward function. Here we define (WW) = {0 e IR" |(0, Φ(s, a))l s W for all s S.a A} for any W O. This conver constrained set is defined by the too fe--functional-oom bound instead of the f--nomm because we do not assume any bound on the 2--norm of the learned parameters. Here we define Wn (((d/mFF) H + dd)HH)) (detailed definition deferred to Appendix C). We note that although W, appears exponential, which may seem suspicious, this does not affect sample efficiency due to the span argument that we introduce in the analysis. We note that prior RLSVI algorithms used truncation on value functions to explicitly avoid such an exponential blow-up. However, truncation does not work for linear Bellman completeness setting since the Bellman backup on a truncated value function is not necessarily a linear function anymore.
Next, the algorithm perturbs the estimated parameters by adding Gaussian noise. The noise for the value function act only in the null space of the data covariance matrix. This ensures optimism while keeping the estimate accurate in the span space. It is key modification from the standard RISVV algorithm. The perturbation for the reward function is standard. Finally, the algorithm constructs the value function for the current horizon and the greedy policy with respect to It then generates the trajectory by executing the greedy policy, and the covariance matrix is updated.
5 ANALYSIS
In this section, we provide the theoretical guarantees Algorithm 1. high-level proof sketch can be found in Appendix B and detailed proof's are in Appendix C. We first consider the case where the squared loss minimization oracle is exact. We then extend the analysis to the approximate oracle and the low inherent linear Bellman error setting in subsequent sections.
5.1 PRELUDE: LEARNING WITH EXACT SQUARE LOss MINIMIZATION ORACLE
We first consider the most ideal setting where the squared loss minimization oracle is exact. Assumption (Exact Squared Loss Minimization Oracle). Line 9 of Algorithm 1 is solved exactly.
Then, we have the following regret bound. A proof sketch is provided in Appendix B for the readers convenience.
Theorem (Regret Bound with Exact Oracle). Under Assumptions and 2, executing Algorithm with parameters oR @( dH log( (HT) and σn = (((ddm/()H--/// H-N+1 VmH)) ) we have
Regr ( dd HT22
This result has several notable features. First, it does not depend on the number of actions. The only requirement for the action space is the ability to compute the argmax. Second, the VT-dependenee on T is optimal, as it is necessary even in the bandit setting. Additionally, we emphasize that the dependence on /T arises solely from reward learning due to the application of elliptical potential lemma. fact, if the reward function is known, our regret bound can be as small as O(dH)) depending T up to logarithmic factors. We elaborate on this observation in Appendix B. As standard practice, Theorem can be converted into a sample complexity bound below.
Corollary 1 (Sample Complexity Bound). Let 1. Under the same setting Theorem 1, let- ting T 2 ((d H²)=)), we get that the policy से chosen uniformly from the set Ti,..., Ty enjoys performance guarantee [VV* V*] se.
7

---

Published as a conference paper at ICLR 2025
5.2 LEARNING WITH APPROXIMATE SQUARE Loss MINIMIZATION ORACLE
Assumption 3 (Approximate Squared Loss Minimization Oracle). We assume access to up- proximate squared loss minimization oracle Oapx that takes as inpul a problem of the form: argmingeo(w) g = E(o(s.)) (10, ((5 a)) - -u) where O(W) {0 E IR [00, ((0,0(s,)) a),) s W for some W e RR is a convex set, and DD is dataset of tuples (()(s,a),)) The oracle returns point 0 that satisfies g(0) min 9(0) s Et and 0 O(W +82) where E1, 1 are precision parameters of the oracle.
With an approximate oracle, the regret bound depends on an additional quantity defined below. Assumption 4. There exists a constant such that, for any S d, and for any $1,,,,,..... .,,,,..,, ,, e Q the eigenvalues of the matrix E Σi=1 Φ207 are either zero at least 1/72
As a concrete example, it holds with Y when the MDP is tabular. This assumption implies that the eigenvalues of 2 are at most ?² Consequently, for any vector ó E 4, we have | s 1 ths lower bound on the norm of any vector is exactly what we need for the analysis of an approximate oracle, while Assumption 4 simply serves as a sufficient condition for it. The following theorem provides the regret bound with the approximate oracle in terms of parameters 62 and 7.
Theorem 2 (Regret Bound with Approximate Oracle). Under Assumptions 1, 3 and 4, executing Algorithm I with on ((VHH) and o (((d/mHH)H---IC (ErTV + vd+ VmH), we have
Regr 0 -
Compared to Theorem
the regret bound has an additional term that depends on the approximation error 117. Typically, e is from optimization and thus can be exponentially small with respect the relevant parameters, as we later discuss in Section 6. Hence, we allow y to be exponentially large. Moreover, we note that E2 does not appear in the regret bound since it only affects the constraint violation of the regression, whose effect to the statistical guarantees is of lower order and thus ignored. In addition, note that the regret bound does not depend on the number of actions, and the dependence on remains optimal, similar to the previous theorem.
5.3 LEARNING WITH Low INHERENT LINEAR BELLMAN ERROR
Now we consider the setting where the MDP has low inherent linear Bellman error.
Definition 3 (Inherent Linear Bellman Error). Given éB L, an MDP M is said to have EB- inherent linear Bellman error with respect to a feature mapping & if there exists a mapping T :d Rdd so that, for all E Ra and all (s,a) é S xx A, holds that KTO, (s) Eg-T((,.)) max M(' ,a'))) s ên. Moreover, we require that, for all he [H] and (5.u) & S A. the random reward is bounded in [0, 1] with (r)(s, - (wh, ((s a))l S EB for some unknown wj.- ERd
With low inherent Bellman error, Assumption 4 is still necessary. The following theorem provides the regret bound this case. We assume the exact oracle for simplicity.
Theorem 3 (Regret Bound with Low Inherent Bellman Error). Assume the MDP has Eg sg-inherent Bellman error. Under Assumptions 1, 2 and 4, when executing Algorithm I with parameters oR @(VaH EgHT) and o₁ @((dv (((ddm/H)* H H- Hon HT + VEBT Vd VmH)), we have
Regr ((15 5112 2312 + d /3/2 (en( 10 882 ((2 eBT
8 HT))
Compared to Theorem I, the regret bound includes two additional terms that depend on the in- herent linear Bellman error EB. For both terms, the dependence on T is linear. We believe the T T-dependence is unavoidable, it also appears in similar settings (Zanette et al., 2020b). In addi- tion, it is worth noting that the regret bound does not depend on the number of actions, and the other dependence on T' remains optimal, similar to previous theorems.
8

---

Published as a conference paper at ICLR 2025
6 OPENING THE BLACK-BOX: IMPLEMENTING SQUARED LOSS MINIMIZATION ORACLES IN ALGORITHM
In this section, we detail a practical implementation of the desired squared loss oracle need by our algorithm. The implementation relies on the observation that square loss minimization objective over convex domain can be cast as a convex set feasibility problem- given a convex set K, return a point 0 E K. Thus, we can use algorithms for convex set feasibility to implement the squared loss minimization oracles. However, even given this observation, our key challenge for an efficient algo- rithm is that the corresponding convex set could be exponentially large and only be described using exponentially many number of linear constraints. Fortunately, various works in the optimization literature propose computationally efficient procedures to find feasible points within such ill-defined sets, under mild oracle assumptions.
6.1 COMPUTATIONALLY EFFICIENT CONVEX SET FEASIBILITY
We first paraphrase the work of Bertsimas & Vempala (2004) that provide a computationally ef- ficient procedure for finding feasible points within a convex set by random walks. Notably, the computational complexity of their algorithm only depends logarithmically on the size of the convex set, and thus their approach is well suited for the corresponding convex feasibility problems that appear in our approach.
high level, they provide an algorithm that takes an input an arbitrary convex set K. g Rdd and returns a feasible point 2 e K.. Their algorithm accesses the convex set IC via a separation oracle defined as follows.
Definition (Separation oracle). separation oracle for a convex set K, denoted by Oxe, defined such that on any input 2 E Rd, the oracle either confirms that z e K or returns a hyperplane (a, 2) s that separates the point from the set K.
In order to ensure finite time convergence for their procedure, they assume that the convex set K. is not degenerate and is bounded in any direction. This is formalized by the following assumption.
Assumption 5. The convex set K. is (r, R)- -Bounddd,, i.e. there exist parameters < R such that (a) K. g oo R)), and (b) there exists a vector z RRa such that the shifted cube (z TR. (r)) s K.
The computational efficiency and the convergence guarantee of their algorithm are below. Theorem (Bertsimas Vempala (2004)). Let 8 (0, and IR be an arbitrary convex set that satisfies Assumption 5 for some S r S. R. Then, Algorithm (given in the appendix), when invoked with the separation oracle Oxe w.r.t K., returns a feasible point K. with probability at least 1 - 5. Moreover, Algorithm 2 makes ((llog(B/sr) calls to the oracle Ouep and runs in time Odd log(R R.6r))
Notice that both the number of oracle calls and the running time only depend logarithmically R and r, and thus their procedure can be efficiently implemented for our applications where 12/, may be exponentially large in the corresponding problem parameters.
6.2 COMPUTATIONALLY EFFICIENT ESTIMATION OF VALUE FUNCTION (EQN (1))
We described how to leverage the method by Bertsimas & Vempala (2004) to estimate the parameters for the value functions in (1) in Algorithm 1. Note that for any time t and horizon h [H], the objective in (1) the optimization problem
0, h argmin
(0,0(sL,) Ve (+)h=))))))
OEO(WA)
where W,, - procedure to approximately solve the above given a linear optimization oracle over the feature space.
H-h
d/mH)). We provide a computationally efficient
Assumption 6 (Linear optimization oracle over the feature space). Learner has access to linear optimization oracle Olin that on taking input e R2. returns a feature ó(s',a') a') e argmax, (0,

---

Published as a conference paper at ICLR 2025
The key observation use is that under linear Bellman completeness (Definition 1) and deter- ministic dynamics (Assumption 1), any solution 0 for (3) must satisfy ( @(8i, (i,h)) ",,n-1(ss,h-1 O. On the other hand, the converse also holds that any point @ (W,), for which the objective value is 0 must be a solution to (3), Thus, the minimization problem in (3) is equivalent to finding feasible point within the convex set
K== 0 e Rd (10, (0i,h, (i, V (SEA.))) = 0 for all i s (0, a))l s W,. for all 8,a
(4)
Given the above reformulation of the optimization objective (3) as a feasibility problem, we can now use the procedure of Bertsimas & Vempala (2004) for finding be, K. However, we first need to define a separation oracle for the set IC and verify Assumption 5. Unfortunately, there may not exist any 0 for which (= + oo (r)) K. for some 2 R. in case and thus the above IC may not satisfy Assumption 5. This can, however, be easily fixed by artificially increasing the set K. to allow for some approximation errors. In particular, let
and define the convex set
( (0
(0, (s ai,h)) )) V I s e for all ist (6, ol sch as,n)) V 1, (si, 2 -e for all i st ((saa)) a)M Wa + for all s,a
{ E 18dd
KAPX
(5)
(0, Φ
Clearly, since there exists at least one point 0e,, K., we must have that (0,, + Reo (E)) s KAPx. To ensure an outer bounding box for the set KAPx, we need to make an additional assumption.
Assumption 7. Let Φ = (á(s,a) 8,a S x A}. There exist some R 0 such that Re E b where e, denotes the unit basis vector along the i-th direction in Rdd
The above assumption ensures that K. s Bx R), Recall that
tolerate the parameter R to
be exponential in the dimension d or the horizon H. Finally, a separation oracle can be implemented using O (see Algorithm 4 for details). Thus, to Bertsimas & Vempala (2004), and the guarantee in Theorem 4 to find a feasible point in KAPXx which corresponds to an approximate solution to (3).
can Algorithm 2 (given in appendix), due
Theorem 5. Let 0, 8 (0, 1), and suppose Assumption 7 holds with some parameter R O. Additionally, suppose Assumption 6 holds with the linear optimization oracle denoted by Olin, Then, there exists a computationally efficient procedure (given in Algorithum in the appendix), that for any E [T] and h E [H], returns a point De, that, with probability at least 1 - ô, satisfies
(( M
V 1,00-1 (SL,.1)) (. TE and
F.,1 OWW t).
Furthermore, Algorithm 4 takes Oad log R. time in addition to Oddogg( oe calls to Olln.
The above techniques and Algorithm 4 can be similarly extended to get computationally efficient procedure to estimate the reward parameter in (2). The main difference is that the value of the optimization objective in (2) is not zero at the minimizer (due to stochasticity). Thus, we need to construct set feasibility problem for every desired target value of the objective function within the grid [0, E, 28 ....... ε, 2] and use a separating hyperplane w.r.t. the ellipsoid constraint (2) to implement the separating hyperplane for KAPx (which can be implemented using projections).
CONCLUSION
In this paper, we develop computationally efficient RL algorithm under linear Bellman complete- ness with deterministic dynamics, aiming to bridge the Our algorithm injects random noise into regression estimates only in the null space to ensure opti- mism and leverages span argument to bound regret. It handles large action spaces, random initial states, and stochastic rewards. Our key observation is that deterministic dynamics simplifies the learning process by ensuring accurate value estimates within the data span, allowing noise injection to be confined to the null space. Extending our algorithm to stochastic dynamics remains an open challenge.
gap in this setting.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We thank Yuda Song, Zeyu Jia, Noah Golowich, and Sasha Rakhlin for useful discussions. AS ac- knowledges support from the Simons Foundation and NSF through award DMS-2031883, as well as from the DOE through award DE-SC0022199, WS acknowledges support from NSF IIS-2154711, NSF CAREER 2339395, and DARPA LANCER: LeArinng Network CybERagents.
REFERENCES
Mare Abeille and Alessandro Lazaric. Linear thompson sampling revisited. In Artificial Intelligence and Statistics, pp. 176-184. PMLR, 2017.
Alekh Agarwal, Nan Jiang. Sham M Kakade. and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, 32:96, 2019.
Alekh Agarwal, Yujia Jin, and Tong Zhang. Vo q I: 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.
Priyank Agrawal, Jinglin Chen, and Nan Jiang. Improved worst-case regret bounds randomized least-squares value iteration. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 6566-6573, 2021.
OpenAl: Marcin Andrychowicz, Bowen Baker, Maciek Chociej. Rafal Jozefowicz, Bob McGrew, Jakub Pachocki, Arthur Petron, Matthias Plappert, Glenn Powell, Alex Ray, et al. Learning dexterous in-hand manipulation. The International Journal of Robotics Research, 39(1):3-20) 20, 2020.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International conference on machine learning, pp. 263-272. PMLR, 2017.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemystaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large scale deep reinforcement learning, arXiv preprint 191i::191..000 2019.
Dimitris Bertsimas and Santosh Vempala. Solving convex programs by random walks. Journal of the ACM (JACM), 51(4):540-555 2004.
Rajendra Bhatia. Matrix analysis, volume 169, Springer Science & Business Media, 2013.
Jianyu Chen, Bodi Yuan, and Masayoshi Tomizuka. Model-free deep reinforcement learning for urban autonomous driving. In 2019 IEEE intelligent transportation systems conference (ITSC), pp. 2765 2771. IEEE, 2019.
Simon Du Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in In International Conference Machine Learning, pp. 2826-2836. PMLR, 2021.
Simon Du, Jason Lee, Gaurav Mahajan, and Ruosong Wang. Agnostic q-learning with func- tion approximation in deterministic systems: Tight bounds approximation error and sample complexity. arXiv preprint arXiv:2002.07125, 2020.
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487 2021.
Noah Golowich and Ankur Moitra. Linear bellman completeness suffices for efficient online inforcement learning with few actions. In The Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024.
David Haussler. Decision theoretic generalizations of the pac model for neural net and other learning applications. In The mathematics of generalization, pp. 37-116. CRC Press, 2018.

---

Published as a conference paper at ICLR 2025
Jiafan He, Heyang Zhao, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for linear markov decision processes. In International Conference on Machine Learning, pp. 12790-12822. PMLR, 2023.
Haque Ishfaq. Qiwen Cui, Viet Nguyen, Alex Ayoub, Zhuoran Yang, Zhaoran Wang, Doina Precup, and Lin Yang. Randomized exploration in reinforcement learning with general value function approximation. In International Conference on Machine Learning, pp. 4607-4616. PMLR, 2021.
Haque Ishfaq, Qingfeng Lan, Pan Xu, A Rupam Mahmood, Doina Precup, Anima Anandkumar, and Kamyar Azizzadenesheli. Provable and practical: Efficient exploration in reinforcement learning via langevin monte carlo. arXiv preprint arXiv:2305. 18.44666, 2023.
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, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably effi- cient? Advances in neural information processing systems, 31, 2018.
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 Miryooseti. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances in neural information processing systems, 14113406-34111 2021.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandit approach to personalized news article recommendation. Proceedings of the 19th international conference on World wide web, pp. 661-670, 2010.
Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free rep- resentation learning and exploration in low-rank mdps. Journal of Machine Learning Research, 25(6):1-76, 2024.
Rémi Munos. Error bounds for approximate value iteration. In Proceedings the National Confer- ence on Artificial Intelligence, volume 20, pp. 1006. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2005.
the
Ian Osband, Benjamin Van Roy, and Zheng Wen, Generalization and exploration via randomized value functions. In International Conference on Machine Learning, pp. 2377-2386. PMLR, 2016.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittweeser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game go with deep neural networks and tree search. nature, 529(7587):4844489, 2016.
Yuda Song, Yifei Zhou, Ayush Sekhari, J Andrew Bagnell, Akshay Krishnamurthy, and Wen Sun. Hybrid rl: Using both offline and online data can make efficient. arXiv preprint arXiv:2210.067188 2022.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on learning theory, pp. 2898-2933. PMLR, 2019.
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-611 2020.
12

---

Published as a conference paper at ICLR 2025
Yuanhao Wang, Ruosong Wang, and Sham Kakade. An exponential lower bound for linearly realiz- able mdp with constant suboptimality gap. Advances in Neural Information Processing Systems, 34:9521-9533, 2021.
Gellért Weisz, Philip Amortila, and Csaba Szepesvári. Exponential lower bounds for planning in mdps with linearly-realizable optimal action-value functions, In Algorithmic Learning Theory, pp. 1237-1264. PMLR, 2021.
Zheng Wen and Benjamin Van Roy. Efficient reinforcement learning in deterministic systems with value function generalization. Mathematics of Operations Research, 42(3):762-782, 2017.
Runzhe Wu and Wen Sun. Making rl with preference- based feedback efficient via randomization. In The Twelfth International Conference on Learning Representattinss, 2024.
Tengyang Xie, Dylan J Foster, Yu Bai, Nan Jiang, and Sham M Kakade. The role of coverage in online reinforcement learning. arXiv preprint arXiv:2210.041:5 2022.
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Confer- ence on Artificial Intelligence and Statistics, pp. 1954-1964. PMIR, 2020a.
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, PMIR, 2020b.
Andrea Zanette, Alessandro Lazaric, Mykel J Kochenderfer, and Emma Brunskill. Provably ef- ficient aggostic navigation with linear value iteration. Advances in Neural Information Processing Systems, 33:1 1356-1161777 2020c.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learningvia reference-advantage decomposition. Advances Neural Information Processing Systems, 33: 15198 15207, 2020.
Yinglun Zhu and Robert Nowak. Efficient active learning with abstention. arXiv preprint arXiv:2204.00043 2022.
13

---

Published as a conference paper at ICLR 2025
CONTENTS OF APPENDIX
1
Introduction
2 Related Works
3 Preliminaries
3.1 Other Linear Bellman Completeness Definitions in the Literature
3.2
Other Prior Works on Linear Bellman Completeness
4
Algorithm
5
Analysis
5.1
Prelude: Learning with Exact Square Loss Minimization Oracle
5.2
Learning with Approximate Square Loss Minimization Oracle
5.3
Learning with Low Inherent Linear Bellman Error
6
Opening the Black-Box: Implementing Squared Loss Minimization Oracles in Algo- rithm
6.1
Computationally Efficient Convex Set Feasibility
6.2
Computationally Efficient Estimation of Value Function (Eqn (1))
7
Conclusion
10
A Table of Notation
16
B Proof Overview
17
B.1 Span Argument
17
B.2 Exploration in the Null Space
17
B.3 Proof Outline
18
C Full Proof for Section
18
High-probability Event and Boundedness
19
C.2 Value Decomposition
24
C33 Exploration in the Null Space
27
C.4 Main Steps of the Proof
30
Supporting Lemmas
35
D.1 Pseudo Dimension and Covering Number
38
E Linear MDPs and LQRs imply Linear Bellman Completeness
38
F Computationally Efficient Implementations for Optimization Oracles
39
14

---

Published as a conference paper at ICLR 2025
G Missing Details from Section 6.2
39
G.1 Computationally Efficient Estimation of Reward Function (Eqn. 2) ................................ 39
15

---

Published as a conference paper at ICLR 2025
A
TABLE OF NOTATION
We list the notation used in this paper in table 1, for the convenience of reference.
Table 1: Notation used in the paper.
Symbol
Description
(WW)
(0 Rd (0, a))l s W for all S, e A}
R (W)
(0 : 18) W]
R2(W)
(0 R 10|2 W}
(( 00, Be,h
Me,
w WEA
WAA Wi,h
De,- De,
ghigh
High probability event, defined in Definition
eppan
Event that trajectory at round t is within the span of historical data, defined in (6)
@optm
Optimism event at round f, defined in Lemma 14
U
Value function lower bound, defined in Appendix C.2
BR
Upper bound of [ wi, E,, defined in Definition 5
er
BP
Upper bound of 00., (wi, 0t, )ls... defined in Lemma
err
BR
Upper bound of - I.... defined in Definition
hoise
BP
Upper bound of | AA,,, defined in Definition
noise,
BR
Upper bound of > (5t,,, ac, 1 defined in Lemma 16
By
Upper bound of Σ 1 1 ( ( at,n)ss; defined in Lemma 16
By
Upper bound of [V, conditioning on @.pan and Chigh defined in Lemma 13 Σm P.Oio? + Σlil (88i,, (r,)))) (Si,,, ai.a)
E.h
Eip
EH ((5,,) (s,,))
Wh
Recursively defined as Wh-1 = W₁, 25g + 22d BP Broseeh + 2dd BR with W WH-1= 1
naise
16

---

Published as a conference paper at ICLR 2025
B PROOF OVERVIEW
In this section, we provide a sketch of the proof of Theorem 1 (exact oracle and zero inherent linear Bellman error) with the full proofs deferred to Appendix C. To better convey the intuition, now assume that the reward function is known, as reward learning is largely standard. In particular, we temporarily remove the estimation and perturbation of rewards (Lines and 1 and simply assume Wr,A wi, in Line 12.
B. SPAN ARGUMENT
The very first step of our analysis revolve around two complimentary cases whether the trajectory round is in the span of the historical data or not. Let Dr, == (ø(si.h as.a)) and define e expaa as the event that the trajectory at round I. is in the span of the historical data, i.e.,
@.pan (A (H) d (8tt,, (e,h) span(D(-1.n))
(1) In-span case. When the trajectory generated in the round is completely within the span of historical data, we can assert that the value function estimation is accurate under π,, Particularly, by linear Bellman completeness, the Bayes optimal of the regression Line 9 zeros the empirical risk, as formally stated in the following lemma.
Lemma 1. For any e [T]. we have Ei ((rr,, (i ((
a.,)) - V ( =)==
Define U.(+) version of V.(.) that minimizes V ((( while satisfying the high probability bound (precise definition provided at the beginning Appendix C.2). implics the following.
Lemma 2. For any t [T]. whenever Expan holds, we have V.(st,1)
Vs,,)....
To understand Lemma 2, consider two fact: (1) Te is the optimal policy for the estimated value function Vr, and (2) both V, and U, has accurate value estimate for the trajectory induced by Trs starting from St,1, because it is in the span of the historical data when Eppen holds.
(2) Out-of-xpan case. When any segment of the trajectory is not within the span, we simply pay H in regret and can assert that this will not occur too many times. To see this, we observe the following fact: whenever Capan does not hold, there must exists h E [H] such that dim (Da.) dim dpmn (D ) + 1 by definition. Since the dimension of spans cannot exceed d for any h [H]. the case that e does not hold cannot happen for more than dH times. We formally state it in the following lemma.
Lemma 3. We have Σt 1((e:pan))) 9g s d.H.
Hence, we have the following decomposition:
V" (8t.) V (st,1) = 1 ((C.pan) (v" (*ta)))) (((t))))((()))))))))))(((((()))) ((e (V V (8
dH² when summed over
Therefore, we only need to focus on the rounds where expan holds. This will be the aim of the subsequent sections.
B.2 EXPLORATION IN THE NULI. SPACE
Lemma I implies that the estimation error only comes from the null space of the historical data, i.c., mill( ( ((s),,. (g.n) : I.....t 1)). Therefore, we only need explore in this null space. While adding explicit bonus is infeasible under linear Bellman completeness, we add noise (Line 11) that can cancel out the estimation error in the null space. This achieves the following:
Lemma (Optimism with constant probability). Denote C.ptm as the event that V*(st,)
V V.(..) Then, for any e [T], we have Pr( Pr(pp (-1-1) where is the cumulative dis- tribution function of the standard normal distribution.
This result has been the key idea in randomized RL algorithms, such as RLSVI. In the next section, will explore how this lemma is utilized.
17

---

Published as a conference paper at ICLR 2025
B.3 PROOF OUTLINE
In this section, we outline the structure of the whole proof. Let V denote an i.i.d. copy of V, and Expan C, denote the counterpart of C, e for V. We first invoke Lemma and get
1 ( (V"(s..)) V (st,)) (e (V".s ( s V (st.1) - 1 (
where the last step is by the non-negativity of V*. Next, we apply Lemma and get (U((5),)) "
< E (in H) 1 (
V.
Split it into two parts:
10 (eier"")mmm(ieee H) - 1 ((( Coptrn
[
V.
+
( ( (U( (
Note that the quantity inside the first expectation is non-negative, so we can peel off the conditioning event; the quantity in the second term is simply upper bounded by H. Hence, have
[[eepan { min Ve (s.1). H) 1
C ( [U((s..))] r²(-1) P.
E (1(()ppa)))1
< (-1
Now we split the first term into two parts again:
E
[(e:pan
min((V(((,)))). H|- 1( 1((
(-1
Vi
[((e:pan)C e: [U((,) (2(-1)
1
E V.
(-1
$ 1
(-(-
E V.
| min (V) H) (c (+..) (C
r²(-1)
2
where we used the fact that 1 (C, UU (s.,) H. Taking the expectation over the randomness of the algorithm and use the tower property, which converts into V. we obtain
S (-1-) E [[1[cpan)
1 {(epaa (U((,,)) (²(-1) E. [I((C)Pa))))))
The first term is upper bounded by zero due to Lemma 2, and the second term is upper bounded by 2 by Lemma 3 when summed over l. This finishes the proof.
Remark (Span Argument and Exponential Blow-Up). In the proof sketch above, we did not uti- lize any to-norm bound on 0e.h or oi, as did in many prior works. We actually cannot leverage them since they can be exponentially large due to the addition of exponentially large noise. This phenomenon widely observed the literature (e.g., Agrawal et (2021); Zanette et al. (2020a)) and is addressed through truncation. However, truncation does not work under linear Bellman com- pleteness, as the Bellman backup of a truncated value function is not necessarily linear. This is why use the span argument to circumvent this issue.
C FULL PROOF FOR SECTION 5
In this section, we present and prove the following main theorem, which provides the regret bound in terms of parameters E E2, and Ep. Setting ε E2 EB yields Theorem 1, setting En yields Theorem 2, and setting ê = 82 0 yields Theorem 3.
Theorem 6. Assume the MDP has enhineeeent linear Bellman error. Under Assumptions 1, and 4, when executing Algorithm I with parameters OR /H BR. and 0 2 V (13 + /8m (18mm(We Wn,
E2)). ). we have
Σ V" (st,1) V= (B.1)) δ
5/2 5
2 3 enn
312 +
E
+ (
3/2 d 22 (
2 / d: (TT)
18

---

Published as a conference paper at ICLR 2025
Exact value of parameters dn and Tj in Theorem 6. We define WH+1 and recursively define Wh-1 Wh 282 22d B 2 B Plugging the definition of all these symbols involved and ignoring lower order terms (i.e., logarithmic and constant terms), we get
Wh-1 & dVmH Wh + 61 Hh/H+ + +EB dy/
HT + VEB dVT + d3/2.
(7)
Solving this recursion, we get
Wh a (dVmH) H+1-h + (dVmF) H-h (c1. dy + d HT VEB dvT + d312)
x (dVmH)
H-h H (E1 +EB drv HT + V dVT 2/2 mH)
We insert this into the value of on and get
Th (dV H-h+1
(el TV WTT VEB VT 1 vmH
We can also get the value of on
oR / H (doog(HH) +81 VEnT)
Define A Σ P. It is straightforward that both A and Ar, (constructed in Line of Algo- rithm 1) are invertible. We define À == max,,a lé(s,a)la-1 and X == max,,a (ø(s, ((ss,))llo A77
Lemma 5, The matrices and 4 are invertible. Furthermore, we also have that
x Vd;
A S for all t [T] and all h [H].
Proof of Lemma 5. By the last item in Lemma 23, we have s Vd. In what follows, we will show that A s 2A which implies de, /2X s /2d.
For any x R.d, we have
x Aa
Σ
p: o.)²
Σ TTl + (t
thi,
1=1
1=1
m +2
<
Σ Ps x Pchi)
Ps ot,o))
(using (a+ b)² 22a 26²)
1=1
i=1
2x. Ag.T..
This implies that A 2Ag
C.1 HIGH- PROBABILITY EVENT AND BOUNDEDNESS
Lemma 6 (Reward estimation). With probability at least 1 for any te [T] and h [H].
[ - wills s 1030(1 +d)) ( + 4 16(1
Proof of Lemma 6. For the ease of notation, we fixed and in the proof and simply write the regression problem as
- argmin Σ or))= (L)(1)
where we have dropped the subscripts t and for notational simplicity. Here d and r; are abbrevi- ated notations for ((si,,, ai,x)) and r; respectively, and --
Note that, due to approximate oracle (Assumption 3), w actually belongs to 0 + E2) instead of (1).. Denote C as an -ornrrm a-cover (Definition 6) Ø01 + +62) such that for any 0(1 + E2),
19

---

Published as a conference paper at ICLR 2025
there exists W C, such that Σ w - WT' del/n a. Since 0(1+Ey) is a linear function class, which has
(Definition 8), we have
[C| s (8(1+ (2)e+a)))"/a)
(8)
by Lemma 27. Now define 2/² (w - r:)² ((w*) ) rz)3. Then we have |2+| s 441 + 82)2 and
E B E (wT 0i (T:
2r:)]
E (w Ø; (w (w'''')))''' (w') 2((ww) -r:):)
2 ( Φi - ( -
and moreover,
[[(=))]1 E Φ; - -
16(1
(2)1++=))((4 (w) o; oo (w=)()))
We note that 2;- E, 2, is martingale difference sequence and | E = 8 Applying Freedman's 's inequality (Lemma 22) and a union bound over w C, we have with probability at least 1, for all w CC.
[w (w') (w)) Σ
< Σ 16(1 + 82) (w² v; (w Tw))2+ 8(1 (0++))))og((([))) 4(1 + 82)enT. i-1
"
Recall that W is the least square solution. Denote E as the point that is closest to W, which means that: Σ - di W5 "T na. We can derive the following relationship between w and W:
2 di (w')o,) s (J 6.)² + Σ (w5) Φ, - " 2n + Σ 100 o. 1. (w))
(00
+ 2r:) s 4(1 + E2)
Now plug ã into (9) and re-arrange terms, we get:
Σ (00 o. - o:)² < 1- 16(1 21 (11 - 16)1+=2))2)) Log((C//)) 4(1 4(1+e2)en
8(1+22)
1-16(1+e5) 21
Setting 77 = (32(1 E2) 2)-1 we get
Σ (T0 Φ. - (w") 02) $2> o. 512(1 + (oog(o())))/ 8(1 E2)EBT.
Using the relationships between and e that we derived above, we have:
(w"))
n
2nn 4
Σ
2.5 + 102401 + 2 log([C1/5)- + 16(1 + TT
$ 2n 4
Σ
1024(1 + log(((1))))) 16(1 + 82) 22) 16(1 + T.
Since Ø is the (approximate) least square solution, we have Σ, -ه $ c This implies that:
1024(1 + (e) (lg((((/5) + 16(1 + (na + TB Σ Th Φe - To)) s 2n a² + 45
20

---

Published as a conference paper at ICLR 2025
Now plugging the covering number (8) and setting 1/n, we obtain
E o, (w)) 2 4s (2og(==+))oo((((1111+30+ + (2) +g]]
1102 E2) ((0L==))))doo((((+)))))))))) + 16(
Finally, we have
22 [ - wT IE
m (w")
Here, with some abuse of notation, the di's the right term are the support points of the optimal design. The first term is already bounded above. The second term can be bounded by
E Φ: ---W(") x1)²²
E Ps 4(1+ 62)+
We add it into the constant of the first term. Then, we apply the union bound over all é [T' and h [M] to get the desired result.
Lemma (Value function estimation). Suppose that (( 0c, O(W.). Then,
6(LA,) V 1,h+1 (s )) S TE Furthermore, (0e,- T(we, + 0e, 1s,, s / + 47'g =: BP
Proof of Lemma 7. The Bayes optimal T( + 02,1+1) should achieve the empirical risk of at most BB, i.e.,
[t= ((((),, T (r, - V V SEB.
Since ( + B.. is realizable (i.e., T( be. e O(Wi)), and Fe,n minimizes the objective up precision e1, should satisfy the following
Σ 1
V V, (1,,(11)))))))) 6 Teg.
Combining the above two results, we arrive at the following:
Σ (o(ss,, and), Ben - T(we, + 0c,++1))
< > (in) Ban) (iini() +2 >
V Vepei
T(w + 0 0e (using (a b)2 2a² 21²)
$ 2ee + 4T 2
This implies that
10en - -(wrr +
$ 2 +Dm,
47's.
Definition 5 (High-probabilityy events). Define event @high as e high = VtE [he V [H]: I IAAA S 2dd/22log(6d11223 B D
n vit [T], vh [H]] II LE,,, S 2d (6d(HTT))) =: BR
noise
n (vLE [T], vh [H] IT D.,a s BR
where BR
10330(1 + Id)og (24(1 e2) 4e 16(1 +1 TB7)
21

---

Published as a conference paper at ICLR 2025
Lemma 8. We have Pr( Pr(chishh 1 1/T).
Proof of Lemma 8. Below we show that each event defined in Definition 5 holds with probability at least 1 1 1/(3HT). Then, by union bound, we have the desired result.
Proof of the first event. The way we generate St, is equivalent to first sampling San eP (O,0(an)) (7))) and then set St. (I- Pe, By Lemma 20 and the union bound, we have
Pr ( vh [H] IGAAllA oNy (dlooog s 1/(3HT).
Then, by definition, have
1 1(1 -P.NN
( Σ (ohnnalolnnd + (ot Pi,N)Se PI.Pusi
m
G2 Σ (tt
$ n. Σ (ohn. o
where the third step holds by the fact that of is in the null space and Φi is the span. Hence, we conclude that I s IS
Proof of the second event. Applying Lemma 20 and the union bound, have
Pr ( [T]: I E, o2y/2llo((GHHT2) s 11(3HT)
Proof of the third event. This directly from Lemma 6.
Lemma 9 (Boundness of parameters). Under Assumption conditioning on @high the following hold for all e [T] and h [H]:
1. max, aa (ó(s a), a), Wn, + +
2. max, ( T(W + + m,
Ws.
3. |MANlE,, $ B
4. IMaNlla S 2(W E2) mm:
5. |YHAllN, V3yBer V (w, +
6. max, ((((s,)) a), Ow.)) Wh-1 2dd BR nosse- E2
7. max, (sn(s) = max, Qun (s, (s, Wh-1-
Proof of Lemma 9. Fix e [7]. We prove these items by induction on h. The base (h H 1) clearly holds since there is actually nothing at (H 1)-th step. Now assume they hold for h + 1, and will show that they hold for h well.
Proof of Item 1. It is simply by Line of Algorithm and Assumption 3. Proof of Item By linear Bellman completeness (Definition 1), for any 8, a, have,
(6(8, a), T(Be. + <'~T(a,a)
max(6(s', Wi, + 0.,
max (Ō(s, a), Wa,h B 0
22

---

Published as a conference paper at ICLR 2025
maxx((((s.)) (rh,ll
max ((((s,), a), SPhNl (.
max a)) 02.ht2))
a).
sia
$ (1 + 82) max (8, ( Ligh
L. x.,. (Wn. 2 B moise 82)
=1+ + 2d B moise + (Wn- /2d B Boise 1- 82) Wh.
Proof of Item 3. This is directly from Lemma 7. Proof of Item 4. By triangle inequality, we have
|| A Den (Wwe, + De,n-1) Ill $ 10calla + [T + A 62)
where the last step is by
DeallA
Σ loi Fenn)= $ =
and the similar for T(wet + 0e.
Proof of Item 5. By definition, we have
(on)s 22 (oh "otm man)) (0hm.: mun)
M7, 1,,0
Σ
Ps
1=1
Σ
Pi
(Pandrs nan 1(1- ---PPaass mand
$
Σ
m
3(Pr,10 maddd 2(dr, minh
(using ba+ a² 6²)
1-1
|10 [1othanllez, 1 In Bie )+ ++22 2/ (Cauchy-Schwand) Lemma 25)
3
Pc 81
Σ
We have [ I. IPennillEy l0llss by Lemma 26. By Assumption this is upper bounded by 7. The second term, InLnlls. is upper bounded by B. by Item 3.
Hence, we have
InnallR (B 21
<3>((B -8WW, + =
(Item 4)
Proof of Item We have
max 8.0
a),
max ((((s,)) a), Ocn <.Pa)l 8,0
max 8.0
((((s a) B.,n)) max max 8.a
a), SPAM
< W, + max 10(s, a) Is IAn
Wt. + E2 + 2d B
(Lemma 5)
= Wh-1 2d. BR 1 E2.
Proof of Item
We have
Qe,( = ((((s,)) + (0(s,a),
s ( a), B..a)l 1 + ((((,, a) D.n)) + (1),,,)), (R)
< (Wh-1- - 2d BRg 82) (1+82) 2d BR poiss
Wh-1-
and also, max, [s)( maxx,a (s, Wh-1-
23

---

Published as a conference paper at ICLR 2025
C.2 VALUE DECOMPOSITION
We note that, at any round e [T]. conditioning on all information collected up to round / - 1, the randomness of V. only comes from the Gaussian noise {$ cR St.4/ha1 In other words, V. can be considered a functional of the Gaussian noise. In light of this, we define
Ve.IE ER (B.(.)
functional of the noise variable, which maps the given noise variable to the value func- tion produced by the algorithm by replacing the random Gaussian noise with the variable ........551 S. By definition, we immediately have ER 2R
V+,(+)) T.
Next, we define U, as the minimum of the following program
VE,1 [ET ........
PP 2R .1......5.
2R (st,1)
min EE ET 1..SH 1
BP S.t. Ah [H]: ISE, noise,h
E II B
noise
In other words, U, achieves the minimum value at St,1 while satisfying the high-probabilityy con- straints (Ehigh) on the noise variable. We denote cP. ......,
e S S ..... Sy as the minimizer of the above program, and will always use underlined variables to represent the intermediate variables cor- responding Ue (such as B. @. w. Q, V) to distinguish them from the variables corresponding to Vr. (0, 0, W. W. Q. V). We note that, under @high, we directly have (1( V.(s..).
Below is a decomposition lemma under deterministic transition. Note that it slightly differs from the usual value decomposition lemma under stochastic transitions, where have to take the expec- tation over trajectory randomness. This distinction is crucial to our analysis: by not accounting for trajectory randomness,
effectively leverage span argument.
We denote {st, ) as the trajectory generated by executing x, with initial state $1,1, and { o h-1 as the trajectory generated by executing x² with initial state $7 = St,1-
Lemma 10 (Value decomposition under deterministic transition). Under deterministic transition (Assumption 1), we have
-Ve(s.) =
(Ven+1($e,0+1) (0r, ((sL.. + (w) - We. ((s.n. h-1
Σ
(10)
V'(st.)-V((st))) $
V (ehtz(Si,an)) (Ben ((5 + (wh -e,k-,,,,, p(s,,, ((, ai.)))
h=1
(11)
Similarly, we have
H Σ
(((ss.))Ur(sppp s (Unna()(, (0 H(se,, + (wh - 6 an,)))
h=1
(12)
Proof of Lemma 10. We will prove (10) and (11) altogether, and then prove (12).
Proof of (10) and (11). We consider arbitrary policy Let (& : d' H denote the determin- istic trajectory generated by a with initial state $ 81,1- By definition, have
(7(5(.))Vv((k)
= (((((.1 max (t,
s (QT(()1 ((.
(13)
(5(22) + -0,1,, 0(5 1 7((,)))))
(by definition)
24

---

Published as a conference paper at ICLR 2025
= -V22())))))) + 10 + (wi - -0
Recursively expanding the first term, we obtain
-V. Σ (Venn((s)nan) (Den, (0 d(,x)) twi Wans ol (s d(.)
This proves (11) by specifying т = x². Similarly, (10) can be proved by observing that the only inequality (13) becomes equality when x Tr.
Proof of (12). The proof is quite similar. We have
(*r,),, (s(,)))
= ((.1, max 2 (s),1,
$ (T.1 -2,, (s..1,
(s.2)) + +1 (5L,,, (een ((1,11
(by definition)
= =(22 ( + (U12((1,2) 0(11 (wi Wan ((5.1.
Recursively expanding the first term, we obtain
- Σ
(U,N+1(),,,11)) (Dr, ((sen) + (wh - W 6(s.)
h-1
This completes the proof.
Lemma 11. For any & [T], conditioning Enpan, have the following (in) (in)equalities:
11
V((s
=
Σ
00r,
7(Or.h+1trrnn1l) t ar,))) (Tr,, ((shh
k=1
11
U(($0,1)
Σ
(0nn-
-T(0,, ((sL,, (
Proof of Lemma 11. We will prove the two statements separately, but the proofs are quite similar.
Proof of the first statement. By Lemma 10, we have
V -(s)))-V*((s
Σ
(Peh. (St (E ((s,,, V
v, (, + (w), who (s ar,)))
By linear Bellman completeness (Definition 1). there exists vector, denoted by T TB + te. + ((,))))) Hence, we can rewrite the above as
such that V Ve,+t (.)
Ve(S1,1 - V (8t,1)
H
M(t,, ar.))) + (sf, (e (.) + (Win - who (orn, (wn))) = Σ (Den- - -(0r,hi + we,
Note that by definition of vie we have (st,1) (w" ((s.),) Hence, the above implies
(.(s.))= Σ ((. - twrwii cP aw,)) (Te, (oL
h-1
We remove EPr, since (EL, (.G.,.o(Sss.. (0,(), conditioning Espan
25

---

Published as a conference paper at ICLR 2025
Proof of the second statement. By Lemma 10, we have
T - U,(,,))
Σ
(L,,11) M(sn. + (w) W.n ((5L..
Am1
Again, by the definition of V we conclude that
H
Uc(s1,1) 2
Σ
( o(sn (Ban - -T + + E
h-1
We can remove cP, i
since (5 (1. conditioning on e,
The following lemma shows that, conditioning on the span event C.pan, the value function V, cannot deviate too much from the value function V on average.
Lemma 12. For any & [T], under Assumplion 4 and conditioning on Expan and Thigh, we have
T (v(..))- V* (sL,)) BP 7 B
(B
noise B BB
Proof of Lemma 12. We apply Lemma 11 to decompose V, and obtain
-V*((s,1))
Σ (0r. -0 we,bo d(sn,, (Wer, wh ((
Applying
yields
Ben - -TBB,,tt + (e, (ll.ttt))sss...... [ ar,,)sss; +lween - -wp LØ( (e.))lss
We apply Lemma 7 and Assumption 4 to the left term and Lemmas 6 and 16 and Definition 5 to the right. Then, we obtain
S H BPT + (BR + B BB
This completes the proof.
The following lemma establishes upper bounds on the value functions when conditioning on the span event C.pan
Lemma 13. For any & [T], conditioning on Expan and Chigh we have
(U,(s H HBBR BR Vd+ H (1+ BPrr).
Poisc
Moreover, we have
(e(st,1) s H (BR + -BR Vd+ H (1+ 7P77). noise
We abbreviate By == (BR + BR BR) Vd H. (1 B 7)
Proof of Lemma 13. We will first prove the second statement and then the first statement.
Proof of the second statement. Applying Lemma 11 and the triangle inequality, we have the follow- ing
[.(st.))
Σ Te ol (()))))))))
+
Σ h=1
(0.n ((0 (e,.-)), 6(5L,, ((.)))).))))))
Ti T2.
26

---

Published as a conference paper at ICLR 2025
We bound the two terms separately. For T1, we have
Tı
Σ
( -w,,)) + (Wer - w") wh ((s.)))))))
h=1
H
Σ
(Iwe, Wi,n P w (0 V
(Cauchy-Schwartz)
h=1
B Vd H. For T2, we can use Cauchy-Schwartz:
< SH- (
noise
(Definition 5 and lemma 5)
H1
T2
Σ
10nn
+
H
Σ
10r,h
+ + 1o(s (Cauchy-Schwand Lemma 25)
h-1
$ BB.
(Assumption 4 and lemma 7)
Proof of the first statement. We prove it by establishing a lower bound and an upper bound of U1(51,1) separately. We start with the lower bound, whose derivation is similar to the second state- ment we just proved above:
H
(((51,1)
Cr,1 -T( + + o(sh ac,)) ( o (()))))))))
(Lemma 11)
1=1
B
B
[{ - (D wh) who (s (.,)))
h=11
(following a similar argument as above)
H1
7H1 1
Σ h-1
Wei Ele + Cen w/ (l,,,) 1ō (t.h (4,,))
CCauchy-Sehwart
2 2-B 7 H (B The upper bound of (((,t,1) a consequence of the second statement we just proved above: (by definition)
Boise
BR
Vd.
(Lemma 8)
Uc(st,1) s (E(V((s.,1) chigh] S BB H H (B noise ) .d H.
We finish the proof by combining the lower and upper bounds.
C.3
EXPLORATION IN THE NULL SPACE
Lemma 14 (optimism with constant probability). For any t [T], denote @optm as the event that V*(1),) s (V.(. + B
Then, under Assumption and conditioning on the bigh-probability event Thigh, we have
Pr (r 2 (-1) where T(-) is the CDF of the standard normal distribution.
Proof of Lemma 14. By Lemma 10, we have:
s
Σ
V (sina (Be, ((s (( + (wi - - o(i
1=1
Σ
V (enta(si,nn)) Maannsssi, ((s,
Σ
EP o( ai,w)
h=1
27

---

Published as a conference paper at ICLR 2025
H
H
w
Wi (( ann))
Σ
(E i ain))
(it))
(iv)
Note that, given any state- triple (s, a, s'), we have
V (0r, (ss, a)) = (7( + 0cn+t)) - Br ((s,)))
Plugging this back to (i), we obtain
H
(i) (ii) s
(m E.,, a(,))) Σ - 0%)
h-1
where we abbreviate 07 == (. Next, we split it into two parts:
H
H
(i) - (ii)
Σ
Σ
(n,n. (I (1,)))))
ES 0%
h=1
h=1
h=1
H
H
H E 0%)
Ne 15,, P 1s: h=1
Σ
Σ
Melllan |1(I Pe. Pil
h=1
(Cauchy-Schwand Lemma 25)
H B H HH+ Emp (I- PP.n)) Aaz
H Σ (EEh 0i)
(Assumption 4 and Lemmas 7 and 26)
< +
B
H m 11(T -1, PR Σ (S Φ1) (Cauchy-Schwartz)
Recall that <Pp is sampled from N/ (1 P.,,)) Pc..)) Therefore,
Σ ((e.. N
-N (0. oI o
h-1
Since dn HH I under high nigh-prrobbbiity event Thigh, we have
Pr ((i) (ii) B +11 1(-1).
Next, we consider (iii) - (iv). By a similar argument, we have
H
(iii)
(iv)
Σ
(wh Be,h, Φh) (ER Φi))
h=1
h-1
H
H
Σ
|| 01, 10h lxng
Eleth
h-1
h=1
H
H
Σ
|w Wi,h B., 1 1i
Σ
(eRt
oi.)
4=1
h=1
Recall that <R sampled from \/0, of Er1)) ) and thus, have
Φi) ~ N 0. Σ क E
Σ (cR R
Therefore, since OR VH W.nll l (Lemma 9), we have
Pr (iii) (iv) 0) > I'(-1).
Since the events are independent, the probability that both events happen is least (-1)). 17
28

---

Published as a conference paper at ICLR 2025
Lemma 15. The number of times e does not hold will not exceed dH, i.e.,
T Σ 1 ((eppa) dH.
Proof. By definition, when eapan does not hold, there exists h [H] such that ((5t, (r,a) is not in the span of {0(8r,a, (i.,)) That means, the dimension of the span should increase by exactly after this iteration, i.e.,
dim (span (
dim (span ((((si,,,ai,,)))
However, the dimension cannot exceed d, it only increase at most d times. This argument holds for any E [H], and thus, the total number of times eqpum does not happen will not exceed dH.
Lemma 16. For any h [H]. it holds that
l aeNlle dd/2T log(T' 1) B
T Σ Holes sndv Edd/2dT1n 2dT log (2T B.
Proof of Lemma 16. We prove the two inequalities separately.
Proof of the first inequality. For any t E [T] and e [H], we have the following bound on the norm of features (Lemma 5);
(s.. I (o(ss,,,, Va.
Hence, by Cauchy-Schward have
T 10(8 athh) (1h)
(1.1,, $
T
T Σ min aw d)
T
$ Td Σ min
t=1
$ Td. 2dlog(T +
(elliptical potential lemma, Lemma 21)
d 2T (o +
Proof of the second inequality. We divide the rounds into d consecutive blocks, in each of which the rank of Σx,, remains the same. To be specific, let ( 12................... ... la, la-1 be sequence of integers such that for any i [d] and any i (1i, (1i,4.+,..... 4++1 1), we have rank (F.,,))) =
We will apply the elliptical potential lemma to each block separately. Now let's fix i e [d]] and consider the i-th block. Let the reduced eigen-decompositioon of Σi,, be Ee, UDT where U E dii and D Rixi For each te (f, ... 14111 1), since ((81,,, ar,)) is in the span of E. conditioning on e there exists vector IG such that of (ttth, ar,h) = Uxi.
For any
1}, have
10( ar, 1. = -(st,h )e Er (s
(53 (sgA,, (sn)) ò( d(s.aaae)) j-t,
= = (.)) E Ee,nt +
Σ
29

---

Published as a conference paper at ICLR 2025
=
UDUT+
Σ
UajazUT
Ux
1-1 D+
zt
Σ
It.
Define D+ Ex TjzJ. Hence, we have
f Σ
1( "l(
1 1 H2
By Assumption 4, the eigenvalues of D are lower bounded by 1/72. And clearly, its eigenvalues upper bounded by 4 s 7. Therefore, we have
fu1-1 T.
|= |
(1111
T.
Σ 1 1( min |seellpe' }2]
t-t
Σ 1 ((E)ran) min (1 b..,1)
<
tot:
TV T 2d (T^2(1 + 1/d)) (elliptical potential lemma, Lemma 21)
< <V T 2d (2T
This finishes the summation one block. Notice that we have d such blocks, we complete the proof by multiplying the above by d.
C.4 MAIN STEPS OF THE PROOF
Let 11,, denote an i..d copy of V. conditioned on initial state $1,1 and C.ptm and @high denote the counterparts of @optm and @high but for V((.t.)).
The proof starts with the following decomposition of the regret:
T
E Σ t=1
- V
$ E
1 high Σ
l 1 -VLL))VV(((L))))
t=1
E
1
highhghh Σ
VV
+ E
We will later show that the second and third terms can be casily bounded separately by observing the following two fact: (I) the probability that ehigh doesn't 't hold is very small, and (2) the number of times e doesn't hold is also small. Hence, it remains to bound the first term, which is the most challenging. The most of the proof below is devoted to bounding it.
As the first step, we will add some necessary event conditions to the first term, using the following lemma.
Lemma 17 (Adding necessary event conditions). It holds that
E high
1 (
(V (s..)) V
[ (Tiggh Tapan thigh V.(st.1) ( thigh Thigh T.pan
(eanan)U,(ss (s.,))
E
30

---

Published as a conference paper at ICLR 2025
(dHBB + BeryH 7H (D B Dye dlf2 + +1)
(2(-1)
where the expectation By, is taken over the randomness of Va (an i..d copy V only.
Proof of Lemma 17. We have
T Σ
(( 1
1=1
T
1(
Σ
(V*
(st.1) 1 (eepaay (st.))
(V* is non-negative)
Plugging the condition on @optm (Lemma 14), we get
$ E
I
hiigh
Σ R min H, V((s..)) - [(Tpaa)) (st,1) @ontm
+ B B 7H
We aim to add event indicators, Thigh and expan and thus split the whole thing into several terms:
1 high
1 Thigh p - V @
1 e high
[ (( (,ing ( (st,1)) E
1(chiRh
[ (min(H, (s( 1 7 (st,1) C, C.Ptm]]
+
B B 7H
T1 To + T3
BP HH
Below we bound each term separately.
Bounding Tt. To bound Tj, we will first drop the conditioning event @optm to make things cleaner. To that end, we re-arange it in the following way
E
1
high
( n Cuann) (Vi(st,1) ((C7"""UUisss.))) +1())++(((77 1((E)pan))) By
poptm
C
(4)
T
E
1 ( hight
Σ
[(eligh n ) (U.((t))))) - (s..)) Topum
P4
E
1
Σ
E
[1((@ppan))) By @eptm]
TT.1 T1.2 T1.3
The reason we did this is that we want to make sure (+) is non-negative, so we can drop the conditioning event @optm To see why it is non non-negative, we consider two cases: first, if @xpan holds, then we already have (V - 1( eeeeann (((s)) 0 by definition of Ue(st,);; second, if @span does not hold, then we have 1 (Thigh n gapan (s(,.) + ((()pa)))) By 2 0 by Lemma 13.
(V,
Hence, for T1.1 can drop the conditioning event using the following rule (for non-negative variable X):
- = 1
and using Lemma 14 get
T1.1 5 (=(-1)
1
E
E
1 C
hhgh
n
C.pan) ((C" ( 1(( BB)
31

---

Published as a conference paper at ICLR 2025
E
1
B
Cepenn (P((11))) 14 [[(sa)))
(-1-)
1
R.
110thio
1 ( Cg. Bv
(=1-
1(Clish)
1 1( high n Cلpnn)) (Vi(++,1) 1(E7 ([(""))))))))]]]]
()(-1) E
dHBv
(Lemma 15)
(=
For T1,2, apply Lemma 12 to get
T1 s
1 (
Σ
[
Chigg ":pa)) }1 (V (V.()..) V* (*(()))))
C
Coptm
1=1
(V, 2 U, conditioning @hish)
$ T H (B noise
BR B
We simply upper bound T1.3 zero. Plugging all these upper bounds back, we obtain
T1 S
1
E
1 highh Σ R [
Cepan)
(V((s1,)) 1{ (U((,)))
(-11
dHBB+ B H (B + B BR
(-1-
T
IE 1 Thigh Espan @ hhigh (V(,))) 1 (eppaa n high Thigh E.pany ((paa)U((ss.)))
E
(-1-)
V.
dHBv B H (Bro B B
(-1-))
This is the final bound of TT we need. Next, we go back to bound T2 and T3- Bounding Tz. We upper bound the value function inside the expectation by H and obtain
T2 $ H E
1 ( hhigh
1 [ hhigh 9 @optm
$ H E
E [ ( T
(dropping @high)
= H E
Σ
(Thigh)o n T.ptm) Pr ( (optm))
[==1
< HT
Pr (chish)c)
(-(-1)
1
(Lemma 8)
(²(-1)
Bounding Tg. Similar, we upper bound the value function inside the expectation by H and obtain
Ta s H E
1 C
high
E yC
[
@optm
< H.H.. E
C3
(dropping Chigh)
H E
I
C CespancC E | Pr (
H E
[[) Pr Pr(
32

---

Published as a conference paper at ICLR 2025
H
E
1
(tower rule)
(-1))
dH²
(Lemma 15)
(-1-)
Plugging all these back, we conclude the proof.
The following lemma refines the event conditions established in Lemma 17 to make the whole thing more manageable.
Lemma 18 (Refining event conditions). It holds that
T
E
[(CChihh
Cxpan
ghich (i(e,,) (( @high n Thich T ((Pm))U(($LL]]]
E 1 (( T (i((,.)) 1 -( n @hish n JU.(sL1)]]
V.
+ By 2By/H.
Proof of Lemma 18. We start with refining the event conditions on the first term. We remove un- needed events by splitting the first term into two parts:
E
[ high @xpan n
ghigh (s(1,)) 1 ( ghigh n Thigh n C (U
E 1 ( hhih Eapany ( 1 n thigh Thigh C yU(($11D1
V.
[ hhigh E n ( [.V
E
Here, using Lemma 13, the last term be bounded by
E [ Capan (chish (
I((ebish))) C) ByyBy By s By/H
where used Lemma 8 in the last inequality.
Now we seek to remove unneeded event conditions on U2 as well. We notice the following decom- position
1 [[.paa ghigh n Thigh Cepan (((.,))
2 @a n (st.))
1 n high C
1 C chigh Capan CUU
Plugging this back, we obtain
1 1(Chhigh n @xpan n hhich ) (s 1( ghigh n Thisch n C UUa
E
E-1
s
E
E
1 n T V, 1 n thigh [(ans,))
Thigh
V.
[1(@ppan span n hhigh n (Chith)
+
E
E
V
E
E
[ @ n hhigh n ((
V.
By/H
33

---

Published as a conference paper at ICLR 2025
The first term is exactly what want. Now bound the middle two tenms separately below:
1 Le @hinh n ( (CU
E
< [(er p @high n ( Br]
(Lemma 13)
T P high ))
$ Bv/H
(Lemma 8)
and for the other term we also have
E
1
eleepan Chish n (ε:pan) ( (O)U((s.1)]
V.
[
E
(Lemma 13)
V
By Σ I((e
(tower rule)
dd
(Lemma 15)
Hence, putting all together, we complete the proof.
The following lemma provides a final bound for the first term Lemma 18.
Lemma (Final bound). It holds that
E
Σ E [-1
[1(Cligh n Espan (..,) ((g n (n
V.
SHHBP Be, B 2( 2(B B H HBR.
Proof of Lemma 19. By tower rule, have
E
Σ
Thiggh Tepan) V.(+..)) 1( (eTpnn Chigh J (s(
E
1(
c
high ne eepan V.(s,,) - 1(eppan n thigh (hhiish (C((),1)
We plug in the result in Lemma and get
< E
I g hhgh
espan
H Σ
0on T(Be,-11 + +(on.))) ((()))
H
E
Σ 1 ((Chigh
high
@span
(T (,1 + - -lnn
H
E
Σ 1(
high
@apan
Σ
Wi,
Applying Cauchy-Schwand inequality to each term yields
H Be, T(fr, + w., Sin
E
Σ 1
c hhigh
Espan
h-1
E
1
C high @apan
I (e + (.,))))) Bealls.. 1ø( anl))ss
E
Σ 1(e high @apan
Wii willEra + 1 DEn )Il (nt)ll
34

---

Published as a conference paper at ICLR 2025
The first two terms can be bounded by H using Lemmas 7 and 16. For the last term, condi- tioning on @high, we have
T - E 1iTe, Wa E.,, + 10 - IE,, B BR noise
and similarly for || We, I.... Also, applying Lemma 16, we have
Σ (eNss SHB.
Inserting all these back, we get the upper bound of
2HB B + 2(B + B Boiseee HB
Hence, we complete the proof.
Proof of Theorem 6. We have
T Σ V ($11)) V (*())
T
$ 1 1(chigh
Σ (
(aa (sx.))
T
1 high
(((
Σ
v V' (st,1) -V=(
E
1 ((Cepau)
(( V
TA TB Tc.
For TA, by Lemmas 17 to 19 and re-arranging the results, we have
TA $ (-1) (2Bv (dH + 1/H) + HBP + dH² + +1+ (BR B )2H + 1)B + 2HHB B.B.BBB.
(dH
δ 15 + /  (dH2 32 HVT
VEB d T 2 2 + + (dH2 (HH +12 ((H)
For TB. by Lemma 8, we have
TB S HT Pr
SETT-Pr((hhith ((thish C) 1.
For Tc, by Lemma 15, have
T To s HI E
Σ [[(eppang)) dd12.
Putting everything together, complete the proof.
D SUPPORTING LEMMAS
Lemma 20 (Gaussian concentration). (Abeille & Lazaric, 2017) Let ~ N' 10, for for e
and
E positive definite matrix. Then, for any 5 0, we have Pr [|x|>> 2od (2d))))((dd))) 5 Lemma 21 (Elliptical potential lemma). Assume that X {x
| S 1} is compact and span(X (X) Rdd Let T1,-.., X be sequence of vectors, Eg be a positive definite matrix with each eigenvalue bounded within the range of [a, b] for some a, O, and Ee E, x Then, we have
b T 1
Σ min (1, [, mx} s 2d
a ad
35

---

Published as a conference paper at ICLR 2025
Furthermore, if Σ1 is constructed via optimal design, i.e. Σ₁ Bu-pp xx' where p A(X) is optimal design over X, then we have
Σ min (1,z/ xz) 2d (T +1)
Proof of Lemma 21. First we claim that
min (1, E,,,E 21) 22r,En,100
(14)
To show this, we use Sherman-Morison-Woonee Wooddury formula (Bhatia, 2013) for rank-one updates to a matrix inverse:
E m 2e || 1 1 12
|
1| 2 m
o afe # 2i (2i, + xxæl)" 2t x/ 2
a 122
Now let us consider two cases for the right-hand side of the above:
Case 1 : 1 Ey vr. $ 1. Then, we can lower bound the right-hand side above by | 1 /2.
Case 2 / 2 1. Then the right-hand side above is directly at least 1/2 since the function z/ [ +x) x) is increasing in æ.
Hence, both cases, we have x; -/E2//= 2 min [1,x,1," 24) /2, which finishes the proof of (14).
Since the log-determinant function is concave, we can obtain that log det (E,) log det Ees1 ( (E+- Ex-1)) via first-order Taylor approximation. This gives us the following
det Σr+1 det Σ₁
Σ x 3 24 1=1
Σ tr (27h) (Ee+1 Ex)) $ (log det Ex+1 - log det M., log 1=1
where the last step follows from telescoping. Since each eigenvalue of Σ₁ lower bounded by a, we have det ΣΙ 2 a Towards an upper bound of det Σr = det(E, ΣT" [) let (AI,..., denote the eigenvalues of Σls .ta.T and then we have
det ΣΙ E
I (b+
Ar)
(
(b+ Xi) s b+ d E
T d
Here, the first step is Weyl's inequality, the second step is AM-GM inequality, and the last step is because the trace is bounded by T. Plugging this upper bound back, have
det Σr+1 ddlo (" ad
T
log
det Σ
This completes the proof of the first statement.
For the case where ΣS is constructed via optimal design, we can rewrite Er+1 in the following way:
1
1 1+T
ΣT&1
E TXT gap
Σ xx = IT+
E FI R-p
2527 =: (T+
E xx xmp'
1+T
where we consider (x) ) as an expectation of wx. over a new distribution that we denote by p'. Recall that En is constructed via optimal design, which implies det En 2 det Ex-g/ xx. (Lemma 23). This gives us
del ET+1 log det Σn
(T (I+ det Ex-g xx. log (T++)*) d (T 1).
log
det En
This completes the proof.
36

---

Published as a conference paper at ICLR 2025
The following inequality is well-known. we use the version stated in Zhu & Nowak (2022).
Lemma 22 (Freedman's inequality). Let (Xt) be real-valued martingale different sequence adapted to the filtration Fú. and let E.I-] B1-1 Fi-1). If [Xl] S B almost surely, then for any n (0, 1/),, the following holds with probability at least 1 6:
T
T ST
B Blog(1/6) [
Σ X
"
Lemma 23. (Lattimore Szepesvári, 2020) Assume that F2 compact and span () R2 For distribution over 4 define (p) Eger pl)) and ( = max [ Then, the following are equivalent:
p is minimizer of 9-
p maximizer of f(p) log det A(p).
g(p) =
Furthermore, there exists a minimizer p of such that [supp(p)] s d(d + 1)/2.
Below we show that the Sauchy-Schwarr inequality still valid when the matrix is not invertible under some conditions. We start with the following lemma.
Lemma 24. Let A be positive semi-definite matrix. Let B be square root of A, i.e A= BB". Then range(A) 1) = range(B)
Proof of Lemma 24. We first show that range( (A) S range(B). To see this, for any y é range (A), there exists such that y Az BB"x B(Bxx). Hence y range(B). Next, show that range (B) S range( A). To see this, for any e range B), there exists x such that y = Br. Let 20 21 where 2h mull(B) and #1 rowspace(B). Then, y Br B Since 2 E rowspace(B). there exists such that I = Bº2. Thus, Bι = BB Az. Hence, y rA))
Lemma 25 (Cauchy-Schwarz Schwarz under pseudo-inverse). Let E be a positive semi-defiitte matrix (that is unnecessarily invertible). Then, for any x range(E)) and any TRdd, we have
x y | lyllz-
Proof of Lemma 25. Let B denote the square root of Σ and force B to be positive semi-definite. One can verify that BB the orthogonal projection matrix onto range( B), and hence, range(E) (recalling that range( B) range(E) by Lemma 24). Therefore, for any range(E), have BB x = x. Then, we have
x. y-y=r' B" By
y BBy = 1al
where the inequality follows from the standard Cauchy-Schwarz inequality.
Lemma 26 (Invariance under projection). Let Σ E dgd be positive semi-definite matrix of rank r. For any vector e Rd, we have | = [ yt where P is the projection onto the range of Σ.
Proof of Lemma 26. Assume the digemddecompositionn of Σ UAUT Σt UATUT. Without loss of generality, we assume A has all its non-zero elements at the front and zero elements at the back on the diagonal. Denote U, as the matrix obtained by replacing the last r columns of U by O. Note that the first columns of U is in the range of Σ, so we must have PU U,. Then, we have the following
P PUNNUCTO--
This completes the proof.
37

---

Published as a conference paper at ICLR 2025
D.1 PSEUDO DIMENSION AND COVERING NUMBER
Definition 6 (fi -Co-ernn number). (Definition 4 of Modi et al. (2024)) Given hypothesis class H s (2 R) and Z" (Z1g..., 2n) 2", 8. O, define (e, H, zn) as the minimum cardinality of sel _ H. such that for any h E H. there exists h' EC such that E [[(2;) -k(==))/ We define (e, H, =a (e, ).
Below we define the pseudo-dimension (Haussler, 2018; Modi et 2024).
Definition (VC-dimension). For hypothesis class H. S (X' + {0,1)), we define its VC- dimension VC-dim(H) as the maximal cardinality of a set X = [II....,TIxI} X that sat- isfies |Hxxl 2|X| (or X is shaltered by H), where Hx is the restriction of H to X, i.e. {(h (2.1,....,k (x]xi) h H).
Definition 8 (Pseudo-dimensionn). For hypothesis class H _ (X + R), define its pseudo dimen- sion Pdim as Pdim(()) VCdim (H-*, where H = {(x,t) ~ [h(x)) > { h H) s (X' R
())
The following lemma provides bound on the covering number of a hypothesis class via pseudo dimension.
Lemma 27. (Corollary 42 of Modi al. (2024)) Given hypothesis class H s Z + [a,6] with (P) S d, then, for any n, we have
Ve,HH,
Note that the right-hand side is independent of n.
E LINEAR MDPs AND LQRS IMPLY LINEAR BELLMAN COMPLETENESS
already well known that linear Bellman completeness captures linear MDPs, as demonstrated in works such as Agarwal et al. (2019); Zanette et al. (2020b). Here, we show that it also captures LQRs for a convex subset of linear functions (specifically, when the value function is parameterized by a PSD matrix). We start with the definition.
Definition 9 (Linear Quadratic Regulator). linear quadratic regulator (LQR) problem is defined by a uple ( (A, B, Q, R) where A RRddd, B Rddxm e Raxdd and R Rmxmm The objective is to find a policy π that minimizes the following:
((x) = E
Σ xT,00n + Run
where Th+1 = Ar + Bug, + wh where Wi ~ (O.
Let us focus on an arbitrary step and simply write the transition as the following (ignoring the subscript h for notational simplicity):
x' Ax Bu wA where w -~ w0N(0,E).
(15)
We consider state-action value functions of the form:
x P
Pxu
Q(I, u)
2
Puz
Puu.
u +c.
(16)
linear in the quadratic feature (xx, u) = [x², u? wuu, 2r, u, 1]. Without loss of generality, we
assume P... az- Note that we may not have the Bellman completeness for any such Q. However,
Paz Pru is PSD. Recall that is PSD and only
does hold under the restriction that P
Puu
Paul
(1) P... is PSD, and (2) its Schur complement Pzz- feasible P is a convex set.
Pru P-1 Put is PSD. We note that such set of
Then, consider the Bellman backup of Q (ignoring the per-step reward (cost) for now):
(x w) E.r min Q(x', u/)
(17)
38

---

Published as a conference paper at ICLR 2025
Ar + Bu + w
Pex Pux
Pau Puu.]
Ar Bu w
En
min
u
(18)
Bu + w/² min Miin|LAn [[Ax
Paz [Ax Bu + w] + 2 2[ Bu + w]" Paoil ll Pureff +c.
(19)
Using first-order condition, we know that the optimal u' (for a fixed w) satisfies
u' - au Puz (Ax + Bu + w)),
(20)
which implies that, the term in (17) is equal to min Q(x', u') [Ax + Bu + w]" [Paz Paut Prd un Puz [Ax + Bu+ w
(21)
a'
Plugging the above in (19), we get
((z,u) E. [Ax Bu w/" [[2x (
Pa PauPri Pu uw
[Ax [
Bu + w| +c]
(22)
[Axx + Bu]]
[Par Pzu Pud P uu
[Ar + Bu] + c Tr(( (Pro PauPal Pux) E
(23)
[Ax Bu]"
T [Pa P PauP-rl p.lp P [Ar Bu]
+
(24)
[x AT BTT (Pe-- PauP [A
BJ
+
(25)
u
where c' is some constant. The middle matrix above is PSD if P..: P..P-P au. which holds since is PSD. Thus, we conclude that Q is also linear for some PSD matrix.
We can also easily verify that the reward (cost) function is linear in the quadratic feature. Hence, we complete the proof.
F COMPUTATIONALLY EFFICIENT IMPLEMENTATIONS FOR OPTIMIZATION ORACLES
The convex programming algorithm given in Algorithm 2 is due to Bertsimas Vempala (2004).
In the following, we provide informal description of Algorithm 2 below but refer the reader to Bertsimas & Vempala (2004) for the full details.
At an iteration t T, Algorithm 2 stars with set D: which contains the set K,, and set of 2N points Ut sampled (approximately) uniformly from D, using the SAMPLER subroutine in Algorithm 3. It then uses the first N samples from Ug compute an approximate centroid 2, of the set D, in Line 23; the remaining points from U, are denoted by V,. It then queries the separation oracle O at the point 24. If 24 Kc, then we terminate and return 24. Otherwise, we use the separating hyperplane between 2, and IC to shrink the set D, further into D in Line 29, Finally, it calls SAMPLER again using the set of points V; as a warm start to get 2N new (approximately) i.i.d. sample from D in Line 30. Equipped with the sets D++1 and 21++ another iteration of the algorithm follows.
On receiving convex set D and a set of points V. the SAMPLER protocol in Algorithm first refines V to V" by disposing off any points E / that do not lie in D. Then, it starts random ball walk from the samples in V": order to update the current point we first sample point z' uniformly from the ellipsoid + AA (2BB((1) (where A is defined using the points in V') and then updates 2 z' if z' & D. The analysis of Bertsimas & Vempala (2004) shows that this ball walk mixes fast to uniform distribution over the set D.
G MISSING DETAILS FROM SECTION 6.2
G.1 COMPUTATIONALLE EFFICIENT ESTIMATION OF REWARD FUNCTION (EQN. 2)
The convex set feasibility procedure of Bertsimas Vempala (2004) can also be used to estimate the parameters for the reward functions in Equation (2) in Algorithm 1. Note that for any time and
39

---

Published as a conference paper at ICLR 2025
Algorithm 2 Solving Convex Programs by Random Walks (Bertsimas & Vempala (2004))
Require: Separation oracle Ox" for the convex set KC s R
Parameters r, RR
1: Let T = 2d (1/=>) and N O(dlog(4)))
2: Let D2 be the axis-aligned cube with width R with center 21 0.
3: Sample 2N points Ui := {z],.... ,I,, + (
4: Let V1 = [ and V1 == Ui Vi.
#1
5: tort=lo tor.. T do
6: Compute the point 2t N Exe, 2.
7: if 24 é K then
8:
Return 24 and terminate.
9: else
10:
If 2 & K, shrink the set Dr using separating hyperplane //
11:
Let (at, z) b be the separating hyperplane returned by O (2t).
12:
Let 1 + D; n H4 where Hi denotes the halfspace {= (at, 2) & (at, 21)
13:
Sample 2N points Uz-1 := {=]_-.., 2 < SAMPLER (Dr+1, , N, V.).
14:
Let V4+1 == { 21 and V4-1 == U4-1 V4n1
15:
end if
end for
Terminate and report that K' is empty.
Algorithm SAMPLER used in Algorithm 2
Require: Convex set D.
Parameter N.
Points V {22 ,...,,,
1: Let step size 1 = (4/va), and number of iterations N' =Ō.NN...
2:
Let V = {2 E V lies in D}, and define
1 |
and
A
(=- -2)
IV*
SEV"
3: Let and E V be any arbitrary stating point (note that ū D).
4: while [4] 2.N do
5: Initialize i +- 1.
6: while i N' do
7: Sample z'~ Uniform 1/A I/
// Ball walk
8: if ε DD then
9:
Update + and i i
end if
end while
Update 1 -u (3).
13: end while
14: Return 24
Distribution of samples in 1/ closely approximates Uniform (D) //
horizon à [H], the objective in Equation (1) the optimization problem
(w, ((s,,, - Te.h re.h) ?
Te, + argmin ()) =
Σ
(27)
In the following, we provide a computationally efficient procedure, based off on Algorithm 2, to approximately solve the above squared loss minimization problem given a linear optimization oracle over the feature space (Assumption 6). Note that since TLA. e [0,1], the constraint on the point implies that the objective value in Equation (27) is at most 2. Thus, we solve the above
40

---

Published as a conference paper at ICLR 2025
Algorithm 4 Computationally Efficient Implementation of O for Value Estimation
Require: Data samples ((5 a, u,)
Convex domain (WW).
Approximation parameter E. Linear optimization oracle Olin defined in Assumption 6.
1: // Convert Square Loss Minimization into a Set Feasibility Problem //
2: Define the convex set
(0, ((; a.)) -u, s for all (0, Ø(s, a.)) u, - for all i s ( a) WA for all s,a
KAPX E Rd
(26)
3: // Define Scparation Oracle for the set KAPX using Olin //
4: Definition OKp (Input: parameter A Rd))
For all i S verify if - s (0, d(s;; az)) u4 s for all i
Output any violating constraint as separating hyperplane. Terminate.
Then, verify if max max ((s, a)), m-x,,((00,0(5,,))
W using the linear
optimization oracle Olin (Assumption 6).
If violated, use Olin to compute violating constraint and return it as the separat- ing hyperplane. Terminate.
Otherwise, return that the point 0 Maxxx. Terminate.
5: EndDefinition
6: // Find a feasible point in KAPx //
7: Invoke Algorithm 2 to return a feasible point in the set KAPX with Kav as the separation oracle.
optimization problem upto precision e, by iterating over the set A {,, 28, 2s,..., , solve the set feasibility problem
2- s,2) in order
KA APX
w IRd
Σ Et
) A + (w, s for all 8,
(28)
and stopping the smallest point A for which KA has feasible solution. It is easy that for any A, either A is empty the shifted cube Wr,h Re (E) E KA Furthermore, under Assumption 7 also have that KA R. (R) for any A. Thus, for any A, whenever feasible solution exists, the set KA satisfies the prerequisites for Theorem 4, where recall that can tolerate the parameter to be exponential in the dimension or the horizon H. Furthermore, a separation oracle Srep can be easily implemented by using the linear optimization oracle Olin xax
w.r.t. the feature space (Assumption 6) and by explicitly constructing a separation oracle for the ellipsoidal constraint
E(1u (8i,,, (i,n)) re,n)² As..
We provide the implementation of the above in Algorithm 5, which relies on Algorithm 2 for solving the corresponding set feasibility problems. The guarantee in Theorem 4 to find feasible point in KA (for each A) gives the following guarantee on computational efficiency for Algorithm 5.
Theorem 7. Let & 0, 5 (0. 1), and suppose Assumption 7 holds with some parameter R > 0. Additionally, suppose Assumption 6 holds with the linear optimization oracle denoted by Olin, Then, for any [T] and [H], Algorithm 5 returns point Wi that, with probability at least 5, satisfies
- 2
O(s,ooss,n 2 + and wF
min
Re E 0(1+e)
Furthermore, Algorithm 5 takes O d" log( 5z time in addition to O log( THR)) calls to Olin
41

---

Published as a conference paper at ICLR 2025
Algorithm 5 Computationally Efficient Implementation of Osg for Reward Estimation
Require: Data samples (ss,,,,
Convex domain (1).
Approximation parameter
Linear optimization oracle Olin defined in Assumption 6.
for A e 20,s,2e..... 2, do
2:
// Define Set Feasibility Problem using A //
3: Define the convex set
ACA
w E Rd
s S +
(29)
Kw ((s, + for all s,a
4: // Define Separation Oracle for KA using O
5: Definition O (Input: parameter Rdd) K...
Verify if E!=l ((w, (88,, a.)) r;:²² s &
If not, return a separating hyperplane for the ellipsoid [ls (s) -r, A w.r.t w. Terminate.
Then, verify if max ( a ((s, max,,))),,(a)))) )xx.,)=...0 s using the linear optimization oracle Olin (Assumption 6).
If violated, Olin to compute violating constraint and return it as the separating hyperplane. Terminate.
Otherwise, return that the point w é APX- Terminate.
6: EndDefinition
7: // Find a feasible point in KA
8: Invoke Algorithm with Seep K...
as the separation oracle.
If succeeded in finding a feasible point e IA APX- Return and terminate.
Else, continue.
9: end for
42


Reviews:
[{"review_id": "FK0t6LT0bQ", "reviewer": "Reviewer_VJVt", "summary": "This paper designs the first computationally and statistically efficient algorithm for linear Bellman complete MDPs with deterministic transitions. Instead of adding a quadratic exploration bonus and truncating the value function, this paper adds carefully designed random noises to the regression results so that it can (a) achieve optimism, and (b) prevent error amplification.", "questions": "-\tExample 1 in Section 3.1 is confusing. First of all, is \\mu(s_2) a typo in Line 195? It seems to me that Example 1 proves that, there exists a tabular MDP and a particular feature mapping, such that the norm of the ground-truth parameter has unbounded l2 norm. In other words, this example does not prove that, linear Bellman complete MDPs with unbounded ground-truth parameters is a strict superset of those with bounded ground-truth parameters, since it is still possible that the same MDP can be represented with a different set of features.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "-\tThis paper designs the first computationally and statistically efficient algorithm for linear Bellman complete MDPs with deterministic transitions, which serves as a solid step toward solving the long-standing open question about the statistical-computational gap in the Bellman complete setting.\n-\tThis paper is well written, and the algorithm is straightforward and easy to understand. The technical proofs in the appendix is also well written and easy to follow.\n-\tThis paper clearly discussed the limitations of prior works in the linear Bellman complete setting (Section 3.1 and 3.2). Although the idea of adding noise to the regression result is not new, applying this idea to the specific setting requires non-trivial analysis on the exponential blowup of the norm of the parameters, which is novel in this paper.", "weaknesses": "-\tMy major concern is the organization of this paper --- although the high-level ideas are discussed in detail, all the proofs, including the proof sketch, are deferred to the appendix. I encourage the authors to at least discuss how the key designs of the algorithm (e.g., adding noise to the null space of the current data) enable the regret analysis.\n-\tOne of the major assumptions in this paper is that the transition is deterministic (Assumption 1). However, this assumption is not very well discussed in the paper. The only place where Assumption 1 is used is Lemma 10, which only computes the value decomposition. If I understand correctly, when the transition is not deterministic, a variant of Eq (10) still holds where one only needs to take an expectation w.r.t the randomness of the trajectory on the RHS. Therefore, it is unclear to me what is blocking the analysis from extending to MDPs with stochastic transitions.\n-\tIn the proof sketch (line 885 in particular), the definition of U_t is deferred to Appendix C.2. However, without its definition, it is impossible to understand the proof outline in B.3.\n-\tLine 1662: typo in the displayed equation, mismatched parenthesis.", "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": "SeauYAj2wF", "reviewer": "Reviewer_Z3Wg", "summary": "The paper studies RL under linear Bellman completeness (a generalization of low-rank MDPs) and deterministic transition dynamics. It shows how to design the first algorithm that is both statistically and computationally efficient for this setting, and important open question given the intractability of all existing approaches. The main idea is to drive exploration by injecting noise into the least squares estimates, with the main novelty being that this is done only on the null space of the training data to avoid estimation erros from exploding.", "questions": "1. The paper mentions that \"Many efficient algorithms can be applied to find approximate D-optimal designs such as the Frank-Wolfe\". I think this is the case when S,A are finite, but what if they are infinite? Is there any efficient algorithm?\n2. It is not clear why constrained least squares regression, instead of an unconstrained one, is needed since there is no assumption on boundedness of the true parameters. Could you clarify?\n3. Even though it acts only on the null space, it was not clear to me why the injected noise (ie \\sigma_h) has to be exponential in H\n4. Does the algorithm need to know that the MDP has deterministic transitions? In other words, if applied to a stochastic MDP, would the algorithm still make sense or would it break for some reason?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Designing RL algorithms with function approximation for large state-action spaces that are not only statistically efficient but also computationally efficient is an important open problem, and this paper makes a good step forward in this direction\n2. The \"span argument\" is interesting and novel\n3. Although I only quickly went through the proofs, all results seem sound\n4. The paper is very well written: the problem and its technical challenges are well motivated from the very beginning, notation is clear, and the adopted techniques are well justified\n5. The examples in 3.1 are interesting to motivate why bounded norm assumptions are unreasonable, and further motivate the paper's contributions", "weaknesses": "1. The \"span argument\" is quite interesting, but it also seems quite specific for MDPs with deterministic transitions. Not clear if it extends to stochastic MDPs\n2. While a good step forward and a common setting in practice, the assumption of deterministic dynamics may be a limiting factor\n3. There is no experiment despite the algorithm being computationally efficient (and, I hope, implementable)\n4. Not clear if the dependences on d and H are optimal in the main theorems, or if there is still work to do in that direction", "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": "2oz3GJEKu7", "reviewer": "Reviewer_FXbH", "summary": "The paper proposes a learning algorithm for linear Bellman-complete MDPs with deterministic dynamics. The algorithm randomizes value function estimates to facilitate efficient exploration of the feature space, a commonly used technique. However, the distinguishing feature of this algorithm is that the random noise is injected only into the null space of the collected feature vectors, selectively exploring previously unvisited regions of the feature space and preventing the value function parameters from growing exponentially with the horizon length. Furthermore, the algorithm employs a random walk-based constrained optimization solver, enhancing the computational efficiency of the method. The derived regret bound for the algorithm is optimal in the number of episodes.", "questions": "* There are some typos: e.g., \"to the learn parameters\" in p.2, and \"where the it is\" in p.6.\n* Why are the constrained squared loss minimization problems first converted to the convex feasibility problem, and then solved by random walk method that depends on a separation oracle? It seems that when $\\mathcal{S}$ and $\\mathcal{A}$ are infinite, then it is challenging to design an appropriate separation oracle for $\\mathcal{K}$. Even when  $\\mathcal{S}$ and $\\mathcal{A}$ are finite, then each minimization problem has $d$ decision variables and $2|\\mathcal{S}||\\mathcal{A}|$ constraints, requiring any separation oracle to evaluate the membership for $2|\\mathcal{S}||\\mathcal{A}|$ inequality constraints.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper achieves computational efficiency alongside a low regret bound. As the authors point out, computational considerations in MDP learning are crucial for practical applicability, particularly given that many recent works focus only on the statistical analysis of MDP learning.\n* The idea of injecting random noise exclusively within the null space of the data matrix is brilliant. The insight that this approach promotes efficient exploration of unexplored feature space without redundancy is well-explained throughout the paper. This strategy may be potentially adapted to settings beyond linear Bellman completeness.", "weaknesses": "* To illustrate the computational efficiency of the method, including a simple numerical demonstration would be beneficial.\n* One concern is with the presentation style of the paper. The assumption of deterministic dynamics appears to be critical for the regret analysis, yet it is unclear why stochastic dynamics would impede the success of the method. Although it is mentioned that the deterministic nature of the system enables value decomposition as shown in Lemma 10, the necessity of this condition is not explicitly explained in the main body of the paper.", "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": "MeORiOQqLF", "reviewer": "Reviewer_tw1d", "summary": "The paper considers the problem of learning in an MDP that is endowed with a property known in literature of _linear Bellman completeness_. Intuitively, this property ensures that, whenever a function is linear in a given feature map, it remains linear after applying the  Bellman optimality operator.\n\nEven if existing algorithms (Eleanor) achieve optimal regret guarantees for this setting, no algorithm is known to solve it with polynomial _computational complexity_ in every parameter. \n\nIn this paper, the authors solve the problem in case the process is also deterministic.", "questions": "In appendix E: LINEAR MDPS AND LQRS IMPLY LINEAR BELLMAN COMPLETENESS, the authors prove a result about the Linear Quadratic Regulator.\n\nAt line 2040, the authors claim that, due to the structure of the problem, the optimal actions writes as $Kx$, where $K$ is some matrix. Even if it is true that in the LQR the optimal policy takes this form, I am not convinced from that passage: indeed, what the authors are showing is that\n\n$$E[\\phi(x',\\pi^*(x'))^\\top \\theta] = \\phi(x,u)^\\top \\theta',$$\n\nfor some $\\theta'$, where $\\pi^*$ is the optimal policy. While in fact, what they needed to prove is that\n\n$$E[\\min_u \\phi(x',u)^\\top \\theta] = \\phi(x,u)^\\top \\theta'.$$\n\nThere is a subtle difference between the two things, as first we are using the optimal policy of the MDP, while in the second case $u$ is given by the best action _with respect to the given $\\theta$._ Please, correct me if I am wrong.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The paper introduces an algorithm based an a very original and novel idea, that is to perturb the parameters of the algorithm with a noise that is sampled from the null-space of the features spanned up to the given episode. This idea, which the authors call Null Space Randomization, may have a broader impact in the statistical learning community.\n\nThe paper also introduces some novelty in the proofs of the statistical complexity bounds. Related to the previous point, the authors introduce a Span Argument: indeed, the new features of the state-action pairs visited in the process do not lie outside of the span of the past features too often. In fact, for every time-step h, this can happen at most $d$ times. Using this simple observation, it is possible to avoid exponential blowout in $H$. \nAs the problem of exponential blowout in the horizon appears in a wide family of RL with function approximation works, and is usually solved by truncating the value function, which needs to introduce unrealistic assumptions to ensure that truncation does not bring us outside of the function class, I think this is also a major contribution.\n\nLastly, it is remarkable that the papers deals also with the case of Low Inherent Bellman Error, where the linear model is affected by a misspecification. This scenario, while particularly challenging, is by far more general than assuming exact linearity.\n\nOverall, it is worth mentioning that the algorithm proposed enjoys a regret guarantee which is order-optimal, i.e. scales with $\\sqrt T$ (which is the best dependency) in the case of no misspecification. At the opposite side [1], which is perhaps the most recent \"competitor\" of this work, proves a statistical complexity bound that scales as\n\n$$\\varepsilon^{-O(A)},$$\n\nbeing therefore exponentially dependent on the number of actions and potentially heavily suboptimal even for $A=2$ (due to the $O(\\cdot)$). I see this as a major point for this work over the state of the art.\n\n\n[1]Linear bellman completeness suffices for efficient online reinforcement\nlearning with few actions.", "weaknesses": "The only big weakness of the paper is that the setting is very restrictive, and the contribution does not _at first sight_ seem a big improvement over the state of the art.\n\n1. Assuming deterministic dynamics is very restrictive and, most importantly, does not marry very well with Bellmann completeness. Indeed, given the for of the Bellman optimality operator,\n$$\\mathcal Tf (s,a)=\\int_S p(s'|s,a)\\max_{a'\\in A}f(s',a')\\ ds',$$\n\nOne may hope that a well-behaved density function $p(s'|s,a)$ helps the result to approach the span of the features by smoothing everything (a smooth function is indeed easier too approximate with a linear feature map) thus reducing the inherent bellmann error. This does not happen in case of deterministic dynamics, as we just get\n\n$$\\mathcal Tf (s,a)=\\max_{a'\\in A}f(p(s,a),a'),$$\n\nwhich may be only piecewise smooth due to the maximum.\n\n2. As explained in the paragraph \"Deterministic Rewards or Deterministic Initial State\", an efficient algortihm was already known for the case where the initial state was fixed; generalizing to the case of random $s_1$ is usually easy for general MDPs. Still, it must be noted that the assumption of linear Bellman completeness does not allow for an easy reduction: just creating a fictitious initial state does not work in this case.\n\nOverall, I think these limitations should not divert the attention for the value of the paper, as they are just a consequence of the hardness of the setting.", "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 (Oral)